Cluster je virtuální počítač složený z několika vzájemně propojených PC. Většinou se jeden počítač určí jako správce úloh, jeho úkolem je řídit rovnoměrné rozdělení úloh mezi ostatní jednotky (Load ballancing). Každá jednotka clusteru paralelně počítá danou úlohu a po jejím skončení předá výsledek řídícímu centru. Clustery se používají hlavně díky příznivému poměru cena/výkon (zvláště na univerzitní půdě, kdy už máme k dispozici PC), snadné rozšiřitelnosti o další jednotky.
Výkon clusterů se nemůže rovnat paralelním počítačům, protože síťový hardware, který se používá pro propojení jednotlivých PC, má mnohem menší propustnost dat a delší odezvu než sběrnice propojující multiprocesory.
PC v clusteru mohou být mezi sebou propojeny téměř čímkoliv, od sítí (jako třeba Ethernet) až po přímé propojení (přes SCSI řadiče, USB). V "Linux paraller computing HOW-TO" je uveden výčet některých možností s údaji jako jsou zpoždění, šířka pásma, pořizovací cena. Protože někteří programátoři preferují programování v assembleru za účelem maximálního výkonu, zatímco jiní preferují přenositelnost programů, existuje několik metod, jak přistupovat k síťovému rozhraní:
a) přes sockety, přičemž téměř každý síťový HW podporuje alespoň dva protokoly - TCP a UDP. Sockety jsou ideální pro použití, pokud vám jde o snadnou přenositelnost paralelního programu na jiné systémy.
b) přes ovladače síťového rozhraní - tato metoda se hodí zejména v případě, kdy nám jde o pouze o přenos dat mezi jednotlivými jednotkami bez nutnosti zajištění služeb transportního protokolu. Ušetříme tím čas potřebný pro přenos dat, ale ztratíme přenositelnost na různé síťové konfigurace.
c) přímým přístupem k registrům zařízení pomocí User-level knihoven. Výhodou této metody je obejití funkcí OS a přístup k zařízení přímo (při použití ovladačů se pro každé volání funkce ovladače volá služba jádra). Samozřejmě se tím ale ztrácí přenositelnost programu na PC s jiným HW. V zásadě existují dva typy přístupu k registrům:
Na platformě x86 lze využít ještě následující způsoby:i) při spuštění programu se spustí funkce OS mmap(), kterou si namapujeme paměťovou stránku zařízení do paměti programu.
ii) přistupovat k registrům přímo (např. *((char *) 0x1234 = 5;).
Např:i) použití OS funkce ioperm() k získání přístupu k zařízení
ii) použití instrukcí i386 pro přímý přístup k registrům
extern inline unsigned char inb(unsigned short port) { unsigned char _v; __asm__ __volatile__ ("inb %w1,%b0" :"=a" (_v) :"d" (port), "0" (0)); return _v; }
Jednou z důvodů, proč se clustery používají, je mimojiné i to, že pro ně existuje spousta prostředí, které lze využít při programování paralelních algoritmů.
Pro demonstraci jednotlivých prostředí použijeme následující algoritmus
pro počítání čísla pi metodou součtu čtevrců (převzato z dokumentace):
#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 je volně šiřitelná, přenositelná knihovna pro předávání zpráv napsaná Knihovny pro programování pod Clusterynad vrstvou socketu. Je všeobecně uznávána jako standard pro přenos zpráv v paralelním programování. PVM běží i nad heterogeními clustery (tj. clustery, složených z PC s rozdílným HW), podporuje jednoprocesorové i SMP verze Linuxu. Poskytuje nástroje pro paralelní správu procesů.
Algoritmus pro výpočet pi napsaný v tomto prostředí:
#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 je (narozdíl od PVM) oficiální standard pro přenos zpráv v paralelním prostředí. Existují 3 na sobě nezávisle vyvíjené, volně šiřitelné verze MPI, které běží na linuxových clusterech:
Rozdíly mezi MPI a PVM:1) LAM (Local Area Microcomputer) je plná implementace MPI 1.1 standardu. Umožňuje MPI programům běžet nad individuálním systémem nebo nad linuxovým clusterem používajícím UDP/TCP.
2) MPICH (MPI Chameleon) nabízí podobnou funkčnost jako LAM. Používá se v případě, že chcete lépe využít možnosti HW a jste ochotni si napsat vlastní funkce pro přístup k síťovému HW.
3) AFMPI (Aggregate Function MPI) implementuje část MPI 2.0 standardu. Je postavena na systému AFAPI (viz dále).
První příklad používá základní volání MPI pro každý procesor, aby poslal jeho část informací procesoru 0, který sečte a vytiskne výsledek.
#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);
}
Druhý příklad používá kolektivní komunikaci.
#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);
}
Poslední příklad používá RMA mechanismus (MPI 2.0) pro přidání vlastních 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);
}
Narozdíl od PVM a MPI nevznikalo AFAPI jako abstraktní, portabilní rozhraní, ale jako hardwarově specifická nízkoúrovňová knihovna pro PAPERS (Purdue's Adapter for Paraller Execution and Rapid Synchronization).
PAPERS je síťové rozhraní, které se snaží snížit zpoždění při přenosu zpráv (až na několik milisekund). Toto rozhraní bylo navrženo pro vybudování superpočítače. Vlastně to, že existuje knihovna pro toto rozhraní pod Linuxem, je pozůstatek z testování na prototypech, na kterých běžel (z finančních důvodů :-)) Linux.
Následuje příklad 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);
}
Dalším zajímavým projektem je MOSIX (http://www.cs.huji.ac.il/mosix/). MOSIX je distribuován formou patche pro jádro Linuxu (2.2.9, 2.2.14) a automaticky zajišťuje load balancing mezi stroji. Z hlediska programátora se jedná o prostředí, které se podobá SMP, stačí tedy vytvořit paralelní proces příkazem fork() a o zbytek se MOSIX postará sám.
Prostředí pro paralelní programování je opravdu hodně. Vzpomeňme např. Condor (navržen pro zpracování dlouhotrvajících úloh, beží nad heterogeními clustery).