Clustery pod linuxem

Jiří Škrabal

Obsah

Co je to cluster

PC cluster lze pouzivat jako supervykonny stroj, ale ve skutecnosti je slozen z vice pocitacu, ktere paralelne zpracovavaji ulohy clusteru. PC clusterum se take nekdy rika Beowulf-class computers. Hlavnim duvodem pro pouzivani clusteru je jejich pomerne velky vykon, vzhledem k jejich cene.

Architektura clusteru je zalozena na propojeni nekolika pocitacu velmi rychlou siti. Tyto pocitace mezi sebou sdileji vsechny data a zdroje, nikoliv vsak pamet, jak je tomu u superpocitacu. Nad touto skupinou stoji jeden, ktery se jevi jako server. Ten se stava take konzolou clusteru a zaroven branou k vnejsimu svetu.

Presto, ze jsou clustery velmi efektivnim resenim, nejsou tak siroce pouzivany a to zejmena proto, ze je velmi malo softwaru, ktery by daval moznost, aby se cluster jevil na venek jako jeden pocitac (napriklad prikaz ps). Pak take proto, ze sitove rozhrani neni navrhovano pro multiprocesing - je pomalejsi a chybovejsi

Load balancing

Load balancing je problem minimalizace celkoveho "idle" casu procesoru a minimalizace celkoveho casu cele paralelni aplikace. Typicky byva load balancing jednoduchy proces, ktery rozdeluje zatez.

Load balancing se take lisi podle toho, zda jde o planovani na homogenich ci nehomogenich systemech. Zakladni rozdil je v tom, ze u homogenich systemu jsou predem znamy jednotlive parametry systemu.

Dynamic load balancing

Pri dynamickem "planovani" migruje prace z jednoho procesoru na druhy. A to zejmena kvuli tomu, aby nektere procesory nebyly ve stavu idle a naproti tomu nektere pretizene. Toto muze byt docileno technikami, ve kterych si nevytizeny procesor zada o "praci" napriklad prave u nektereho pretizeneho.

Testy jednotlivych strategii se opet lisi na ruznych konfiguracich. Jsou ale uvadeny studie, ve kterych jsou vykonejsi jednodussi strategie (jako Round-robin), nez jine "inteligentni" techniky.

Asymetric static load balancing

Pokud planovac prideli kazdemu procesoru urcitou cast ulohy, ktera se tam pak bude az do sveho konce provadet, mluvi se o statickem planovani. Zde muze nastat situace, ze jednotlive pozadavky jobu na zdroje nemusi byt vyvazene vzhledem k moznostem stroje. To resi asymetricke planovani, ve kterem planovac prideli kazdemu procesoru takovou cast ulohy, ktera odpovida jeho moznostem.

Network Software Interface

Nejbeznejsim a asi nejrozsirenejsim low-level sitovym rozhranim jsou "sokety" a temer kazdy sitovy hardware podporuje alespon dva typy soket-protokolu: UDP a TCP. Soketove typy jsou zakladem pro vetsinu portabilniho, high-level softwaru pro paralelni pocitani.

Je samozrejme take mozne pouzivat primo rozhrani sitoveho adapteru (popripade si sitovy driver napsat). Funkce driveru lze pak vyvolavat pouze pomoci funkci open() - identifikace odpovidajiciho zarizeni a pak pouzivat funkce read() a write().

Abychom nepristupovali primo k registrum driveru a nevolali take pokazde sluzby OS, jsou vyvinuty a pouzivany tzv. user-level knihovny, ktere pristupuji primo k registrum zarizeni. Na beznem OS jsou dve moznosti, jak mohou user-level knihovny pristupovat primo k zarizeni:

Linux nabizi jeste dalsi reseni:

User-Level knihovny


V nasledujicim textu budu pouzivat pro demonstraci tento algoritmus na vypocitani priblizne hodnoty PI 

#include <stdlib.h>;
#include <stdio.h>;

main(int argc, char **argv)
{
  register double width, sum;
  register int intervals, i;

  /* get the number of intervals */
  intervals = atoi(argv[1]);
  width = 1.0 / intervals;

  /* do the computation */
  sum = 0;
  for (i=0; i<intervals; ++i) {
    register double x = (i + 0.5) * width;
    sum += 4.0 / (1.0 + x * x);
  }
  sum *= width;

  printf("Estimation of pi is %f\n", sum);

  return(0);
}

PVM (Parallel Virtual Machine)

PVM je volne siritelna, portabilni, "message-passing" knihovna, obecne vytvorena nad vrstvou "soketu". PVM je v podstate jako standart pro "message-passing" paralelni pocitani na clusterech. PVM dokaze pracovat nad skupinou pocitacu s ruznou konfiguraci, ruznym poctem procesoru - SMP i single-procesor stroje (heterogenni cluster). PVM take poskytuje nastroje pro paralelni "job control".

Takto vypada vzorovy algoritmus s pouzitim PVM:

#include <stdlib.h>
#include <stdio.h>
#include <pvm3.h>

#define NPROC   4

main(int argc, char **argv)
{
  register double lsum, width;
  double sum;
  register int intervals, i; 
  int mytid, iproc, msgtag = 4;
  int tids[NPROC];  /* array of task ids */

  /* enroll in pvm */
  mytid = pvm_mytid();

  /* Join a group and, if I am the first instance,
     iproc=0, spawn more copies of myself
  */
  iproc = pvm_joingroup("pi");

  if (iproc == 0) {
    tids[0] = pvm_mytid();
    pvm_spawn("pvm_pi", &argv[1], 0, NULL, NPROC-1, &tids[1]);
  }
  /* make sure all processes are here */
  pvm_barrier("pi", NPROC);

  /* get the number of intervals */
  intervals = atoi(argv[1]);
  width = 1.0 / intervals;

  lsum = 0.0;
  for (i = iproc; i<intervals; i+=NPROC) {
    register double x = (i + 0.5) * width;
    lsum += 4.0 / (1.0 + x * x);
  }
  
  /* sum across the local results & scale by width */
  sum = lsum * width;
  pvm_reduce(PvmSum, &sum, 1, PVM_DOUBLE, msgtag, "pi", 0);

  /* have only the console PE print the result */
  if (iproc == 0) {
    printf("Estimation of pi is %f\n", sum);
  }

  /* Check program finished, leave group, exit pvm */
  pvm_barrier("pi", NPROC);
  pvm_lvgroup("pi");
  pvm_exit();
  return(0);
}

MPI (Message Passing Interface)

MPI je relativne novy standard. Existuji 3 nezavisle vyvijene, volne siritelne verze MPI, ktere bezi na linuxovskych clusterech.

Rozdily mezi MPI a PVM:

Prvni MPI program pouziva zakladni "message-passing" volani MPI pro kazdy procesor, aby poslal jeho cast informaci procesoru 0, ktery secte a vytiskne vysledek. 

#include <stdlib.h>
#include <stdio.h>
#include <mpi.h>

main(int argc, char **argv)
{
  register double width;
  double sum, lsum;
  register int intervals, i; 
  int nproc, iproc;
  MPI_Status status;

  if (MPI_Init(&argc, &argv) != MPI_SUCCESS) exit(1);
  MPI_Comm_size(MPI_COMM_WORLD, &nproc);
  MPI_Comm_rank(MPI_COMM_WORLD, &iproc);
  intervals = atoi(argv[1]);
  width = 1.0 / intervals;
  lsum = 0;
  for (i=iproc; i<intervals; i+=nproc) {
    register double x = (i + 0.5) * width;
    lsum += 4.0 / (1.0 + x * x);
  }
  lsum *= width;
  if (iproc != 0) {
    MPI_Send(&lbuf, 1, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD);
  } else {
    sum = lsum;
    for (i=1; i<nproc; ++i) {
      MPI_Recv(&lbuf, 1, MPI_DOUBLE, MPI_ANY_SOURCE,
               MPI_ANY_TAG, MPI_COMM_WORLD, &status);
      sum += lsum;
    }
    printf("Estimation of pi is %f\n", sum);
  }
  MPI_Finalize();
  return(0);
}

Druha MPI verze pouziva kolektivni komunikace. 

#include <stdlib.h>
#include <stdio.h>
#include <mpi.h>

main(int argc, char **argv)
{
  register double width;
  double sum, lsum;
  register int intervals, i; 
  int nproc, iproc;

  if (MPI_Init(&argc, &argv) != MPI_SUCCESS) exit(1);
  MPI_Comm_size(MPI_COMM_WORLD, &nproc);
  MPI_Comm_rank(MPI_COMM_WORLD, &iproc);
  intervals = atoi(argv[1]);
  width = 1.0 / intervals;
  lsum = 0;
  for (i=iproc; i<intervals; i+=nproc) {
    register double x = (i + 0.5) * width;
    lsum += 4.0 / (1.0 + x * x);
  }
  lsum *= width;
  MPI_Reduce(&lsum, &sum, 1, MPI_DOUBLE,
             MPI_SUM, 0, MPI_COMM_WORLD);
  if (iproc == 0) {
    printf("Estimation of pi is %f\n", sum);
  }
  MPI_Finalize();
  return(0);
}

Posledni MPI verze pouziva MPI v2.0 RMA mechanismus pro pridani vlastnich lsum do sum na procesor 0: 

#include <stdlib.h>
#include <stdio.h>
#include <mpi.h>

main(int argc, char **argv)
{
  register double width;
  double sum = 0, lsum;
  register int intervals, i; 
  int nproc, iproc;
  MPI_Win sum_win;

  if (MPI_Init(&argc, &argv) != MPI_SUCCESS) exit(1);
  MPI_Comm_size(MPI_COMM_WORLD, &nproc);
  MPI_Comm_rank(MPI_COMM_WORLD, &iproc);
  MPI_Win_create(&sum, sizeof(sum), sizeof(sum),
                 0, MPI_COMM_WORLD, &sum_win);
  MPI_Win_fence(0, sum_win);
  intervals = atoi(argv[1]);
  width = 1.0 / intervals;
  lsum = 0;
  for (i=iproc; i<intervals; i+=nproc) {
    register double x = (i + 0.5) * width;
    lsum += 4.0 / (1.0 + x * x);
  }
  lsum *= width;
  MPI_Accumulate(&lsum, 1, MPI_DOUBLE, 0, 0,
                 1, MPI_DOUBLE, MPI_SUM, sum_win);
  MPI_Win_fence(0, sum_win);
  if (iproc == 0) {
    printf("Estimation of pi is %f\n", sum);
  }
  MPI_Finalize();
  return(0);
}

AFAPI (Aggregate Function API)

Na rozdil od PVM a MPI nevznikalo AFAPI jako abstraktni, portabilni rozhrani, ale jako hardwarove specificka nizkourovnova knihovna pro PAPERS (Purdue's Adapter for Parallel Execution and Rapid Synchronization)

Verze ktera bezi nad Linuxovymi clustery pouzivajici UDP broadcasty, je teprve ve vyvoji. Take bezi nad SMP systemy, kde pouziva "Shared Memory library" ze System V.

Nasleduje priklad s AFAPI: 

#include <stdlib.h>
#include <stdio.h>
#include "afapi.h"

main(int argc, char **argv)
{
  register double width, sum;
  register int intervals, i;

  if (p_init()) exit(1);

  intervals = atoi(argv[1]);
  width = 1.0 / intervals;

  sum = 0;
  for (i=IPROC; i<intervals; i+=NPROC) 
  {
    register double x = (i + 0.5) * width;
    sum += 4.0 / (1.0 + x * x);
  }

  sum = p_reduceAdd64f(sum) * width;

  if (IPROC == CPROC) 
  {
    printf("Estimation of pi is %f\n", sum);
  }

  p_exit();
  return(0);
}

Dokumentace a zdroje