Espai d'adreces global distribuït

En l'àmbit de la computació, un espai d'adreces global distribuït (PGAS) és un model de programació paral·lela que tracta d’aprofitar els avantatges del model de memoria distribuïda amb pas de missatges i el model de memoria compartida. Es basa en la idea de la memòria compartida que es fa servir en sistemes fortament acoblats, però aplicada als clústers de nodes, on tots els nodes tenen una visió global de tota la memòria del sistema encara que aquesta estigui dividida en particions assignades a cada node. El PGA es materialitza mitjançant APIs desenvolupades per llenguatges utilitzats en programació paral·lela com C, C++ o Fortran. Algunes d'aquestes materialitzacions són UPC (extensió de C), Titanium (extensió de Java) i Co-Array Fortran. El model de PGA suporta la comunicació one-sided, que permet que un procés pugui llegir o escriure a un espai de memòria remot sense una sincronització explícita amb la part remota, amb la intenció de millorar el rendiment.

Una variant del model PGAS, l'espai d’adreça global particionat asíncron (APGAS), permet tant la creació de tasques asíncrones locals com remotes. Dos llenguatges de programació que utilitzen aquest model són Chapel i X10.

Llenguatges de programació

UPC

Unfied Parallel C (UPC) és una extensió de l'estàndard ANSI C per afegir paral·lelisme basat en el model de espai d’adreces global particionat. UPC permet accedir a la memòria global distingint l'espai remot de l'espai local. La forma de llegir i escriure a la memòria global es fa amb declaracions simples. Per exemple, quan es declara una variable seguint l'estàndard ANSI C aquesta variable residirà a l'espai local; per declarar-la a l'espai global només cal afegir a l’inici la paraula shared. La versió 1.0 de la especificació es va produir el febrer de 2001 i va ésser un esforç compartir entre govern, indústria i acadèmia. Posteriorment, al maig de 2003 es va llançar la versió 1.1. UPC va atraure l’interés de la comunitat HPC i alguns proveïdors van desenvolupar i comercialitzar compiladors compatibles. Existeixen compiladors per a les plataformes HP, SGI, Sun i Cray, que són de codi propietari; també n’hi ha implementacions de codi lliure com les que han generat la University of California Berkeley (BUPC) i la Michigan Technological University (MuPC), per arquitectures Intel entre d’altres.

Aquest programa implementa la suma de dos vectors utilitzant UPC. És un exemple utilitzat per Victor Eijkhout al seu llibre Introduction to High-Performance Scientific Computing. Les variables v1, v2 i v1plusv2 són compartides entre tots el threads mentre que lea variable i és local a cada thread.

#include <upc_relaxed.h>
#define N 100*THREADS
shared int v1[N], v2[N], v1plusv2[N];
void main() {
 int i;
 for(i=MYTHREAD; i<N; i+=THREADS)
 v1plusv2[i]=v1[i]+v2[i];
}

Coarray Fortran

Coarray Fortran (CAF), antigament conegut com a F--, va començar com una extensió a Fortran 95/2003 com a proposta per a incloure la programació paral·lela creada per Robert Numrich i John Reid a la dècada del 1990. L'estàndard actual de Fortran 2008.

Un programa escrit en CAF el podem veure com un conjunt de còpies (anomenades imatges) d'ell mateix que s'executen asíncronament. Cada imatge té un identificador i un conjunt de variables privades. Es poden declarar variables de tipus Coarray, aquestes poden ser llegides i escrites per a qualsevol imatge. L'existència d'aquestes Coarrays són un clar exemple d'espai d'adreces global distribuït. Les comunicacions de les coarrays són unilaterals, per exemple una crida remota des de la imatge A fins a la B no fa falta que B també faci aquesta crida, al contrari que en MPI cosa que simplifica molt la programació. CAF també incorpora crídes intrínseques de sincronització per ajudar a evitar situacions de competició i interbloqueig. Qualsevol tipus de variable es pot convertir en una coarray, com per exemple: escalars, arrays, intrisics o tipus derivats, punters. Les coarrays es poden declarar i passar a mètodes, també són molt flexibles i es poden utilitzar ens molts àmbits. Per exemple una col·lecció de coarrays de diferents imatges es pot veure com una sola matriu, al contrari del model de lògica partida com es veu a MPI. Un programa amb coarrays també pot servir per a utilitzar el model paral·lel delegant diferents tasques a diferents imatges o grups d'imatges.

Un problema que té la programació amb CAF és que Fortran no té cap eina estàndard per a poder fer entrada/sortida en models paral·lels.

A continuació es mostra un codi d'exemple on s'intercanvien valors entre dues imatges utilitzant coarrays:

$ cat swap.f90
integer :: img, nimgs, i[*], tmp ! i[*] int coarray amb una sola codimensio
 ! sincronitzacio imlicita
 img = this_image()
nimgs = num_images()
 i = img ! i inicialitzada

 if (img .eq. 1) then
 sync images(nimgs) ! sincronitzacio explicita amb l'ultima imatge
 tmp = i[ nimgs ]
 sync images(nimgs) ! sincronitzacio explicita amb l'ultima imatge
 i = tmp
 end if


 if (img .eq. nimgs) then
 sync images(1) ! sincronitzacio explicita amb la imatge 1
 tmp = i[ 1 ]
 sync images(1) ! sincronitzacio explicita amb la imatge 1
 i = tmp
 end if
 write (*,*) img, i
 ! la resta d'imatges esperen aqui
end

I si executem aquest codi podem veure com la primera i ultima imatge intercanvien els valors sense necessitat d'enviar missatges:

$ ifort -coarray swap.f90
$ setenv FOR_COARRAY_NUM_IMAGES 5
$ ./a.out
 3 3
 1 5
 2 2
 4 4
 5 1
$

Chapel

Chapel és un llenguatge de programació d'alt nivell paral·lel desenvolupat per Cray. S’està desenvolupant com a part del projecte Cray Cascade, participant en el programa High Productivity Computing Systems (HPCS) de DARPA. Està sent desenvolupat com a projecte de codi obert sota versió 2.0 de la llicència Apache.

En Chapel una tasca pot fer referència a qualsevol variable lèxicament visible del programa, independentment dels llocs on s'emmagatzema la variable i on s'està executant la tasca. Per exemple:

var x: int = 1, y: int = 1;

on Locales[1 % numLocales] do { x = 10; } // Assignar valor 10 a variable 'x' en Locale 1
on Locales[3 % numLocales] do { y = 2; } // Assignar valor 2 a variable 'y' en Locale 3

for loc in Locales do // Per tots el Locales
 on loc do // En el Locale loc
 writeln("Locale ", here.id, ": x*y = ", x*y); // Escriu x*y, que en tots els Locales es 10*2 = 20

El fet que el programador pugui raonar semànticament la localitat dins d'un programa Chapel (és a dir, "A està en el Locale 0, i B està en el Locale 1") el converteix en un llenguatge d’espai d’adreces global distribuït.

Charm++

Charm++ a ser dissenyat per Laxmikant Kale, i es va desenvolupar al Laboratori de Programació Paral·lela (Parallel Programming Laboratory), a la universitat de Illinois, a finals del 1980's. Es un llenguatge de programació paral·lel, orientat a objectes, portable i basat en C++. Aquest llenguatge defineix els Chares com la unitat bàsica de programació paral·lela, sent similar a un procés, però seguint sent un objecte de C++.

Les diferencies bàsiques amb C++ son que aquest no té variables globals, que conté diverses extensions per poder treballar amb execucions paral·leles, i que l'operació i manipulació de Chares estan restringides si les comparem amb els objectes seqüencials, per poder obtenir conformitat amb els requeriments de l'execució paral·lela.

Una de les característiques clau del model de programació es la possibilitat de descompondre el programa en un nombre elevat d'unitats de treball i de dades, i poder especificar la computació en termes de creació d'iteracions entre aquestes unitats, sense cap altre referencia directa al processador on estan aquestes unitats, permetent canviar en temps d'execució, assignant unitats als processadors quan es necessari.

Els Chares es distribueixen entre els processadors lliures del sistema mitjançant un planificador de temps d'execució, interactuant entre ells a través de crides asíncrones a funcions.

Poden ser agrupats en col·leccions, suportant els següents tipus: chare-arrays, chare-groups i chare-nodegroups.

Gràcies al seu model d'execució guiat per missatges, té una tolerància de latència automàtica, modularitat i composició paral·lela. També te tolerància a fallades basada en punts de control distribuïts.

Charm també es capaç de fer balanceig dinàmic de càrrega de les tasques paral·leles.

Per contra, Charm++ no suporta variables globals, ja que cada chare de forma normal només pot accedir a les seves propies dades de forma directa. En canvi, cada chare es accesible pero un nom global vàlid, que fa que suporti l'espai d'adreces global distribuït.

Arxiu exemple.h

class Hello : public CBase_Hello {
public:
Hello(); 
void sayHi(int from);
};

Arxiu exemple.ci (interfaç)

module hello {
 array [1D] Hello {
 entry Hello();
 entry void sayHi(int);
 };
};

Arxiu exemple .cpp

# include "hello.decl.h"
# include "hello.h"

extern CProxy_Main mainProxy;
extern int numElements;

Hello::Hello() {
}

void Hello::sayHi(int from) {

 CkPrintf("Hola desde el chare # %d en el processador %d (dit per %d)\n",
 thisIndex, CkMyPe(), from);

 if (thisIndex < (numElements - 1)) {
 thisProxy[thisIndex + 1].sayHi(thisIndex);
 } else {
 mainProxy.done();
 }
}

# include "hello.def.h"

Enllaços externs

• Espai d'adreces global distribuït - Lloc web oficial
• An Introduction to the Partitioned Global Address Space Model
• Programming in the Partitioned Global Address Space Model Arxivat 2010-06-12 a Wayback Machine. (2003)
• GASNet Communication System - provides a software infrastructure for PGAS languages over high-performance networks
• https://coarrays.sourceforge.io - Curs sobre Coarrays Fortran