Topologies Virtuals En Mpi

Què és una topologia virtual?

Fins el moment hem sentit a parlar extensament sobre les diverses topologies de xarxa. S’entén per topologia de xarxa qualsevol disposició física a la que es connecten nodes (processadors, al nostre cas). En funció de la forma en la que estan connectats els nodes la topologia rep un nom diferent: bus, estrella, anell, arbre, malla, hipercub, etc.



Unatopologia virtual és el concepte equivalent a la topologia de xarxa, però extrapolada al nivell software. És a dir, en comptes de tractar-se de maquinari connectat físicament, en una topologia virtual es connecten processos de forma lògica.

La forma gràfica de representar les topologies virtuals, al igual que les topologies de xarxa, és mitjançant un graf. Els nodes del graf representen elsprocessos, i les arestes els camins de comunicació entre dos processos. Per tant, si dos processos estan connectat directament per una aresta al graf, significa que poden comunicar-se directament. En canvi, si entre dos processos no estan connectats directament hauran de comunicar-se a través d’altres nodes. Com més gran és el camí de comunicació, més cost suposa el fet de comunicar-se.
Per a queserveix una topologia virtual?

La tasca d’associar processos a processadors per tal que s’executin en paral•lel no sempre és eficient. El sistema ha de repartir els processos de forma que es minimitzi el cost de comunicació entre els diferents processadors de la màquina paral•lela.

La descripció de la topologia virtual depèn única i exclusivament de l’aplicació, és a dir, aquesta topologia éstotalment independent del maquinari. Tanmateix, si l’aplicació a executar disposa d’una topologia virtual, el sistema la fa servir com a ajuda per mapejar els processos als processadors d’una manera més òptima.

Fa molts anys que s’estudien formes òptimes de mapejar processos a processadors. S’han desenvolupat diverses heurístiques per a mapejar topologies particulars, tanmateix existeixenarquitectures amb múltiples nivells d’interconnexió que fan que la tasca no sigui gens senzilla.

La figura (a) representa una topologia virtual amb quatre processos: A, B, C i D, cada un d’ells comunica amb els seus veïns. (b) és una configuració hardware amb dos nivells de comunicació, els processadors que comparteixen memòria es comuniquen molt més ràpid entre ells que no pas si han de fer-hoamb un processador de fora amb el que cal utilitzar la xarxa per comunicar-se. De la configuració hardware es dedueix el graf (c), on cada comunicació entre processadors porta associat el cost de la mateixa.

El problema de mapejar el graf (a) al (c) es coneix com “Graph embedding problem”. Es formalitza aquest problema de la següent manera:
Es graf (a) corresponent a la topologia virtual seràV=(X,E) on X és el conjunt de processos i E els camins de connexions entre ells. El graf (c) de la connexió física (b) es representa amb N=(P,C) on P és el conjunt de processadors i C les arestes balancejades. correspon al cost associat a l’aresta . En conseqüència, el cost total de comunicació de V mapejada a N és el següent:



On i són els extrems de l’aresta e. L’objectiu ésaconseguir un mapejat que minimitzi , és a dir, que minimitzi el cost de comunicació entre els processadors.

Com ens permet MPI treballar amb elles?

Per entendre la gestió de les topologies que fa MPI cal introduir primer el concepte de comunicador.

Un comunicador és una col•lecció de processos els quals es comuniquen a través d’enviar i rebre missatges. MPI_COMM_WORLD és un comunicadorque inclou a tots els processos.



Existeixen dos tipus de comunicadors:

1. intra-comunicadors: s’utilitzen per enviar missatges entre els processos en un mateix comunicador. Estan formats per:

 un grup, que és una col•lecció de n processos. A cada procés del grup se li assigna un rang entre 0 i n-1

 un context, que és un identificador que associa el sistema al grup.

...