Construcția arborilor optimi pentru multicasting

Abstract: Eficienta comunicatiei dintre procesoarele oricarei retele interconactate este un element extrem de important in proiectarea unei retele, atat din punct de vedere hard cat si soft. Un serviciu care efectueaza multicast la nivelul sistemului, in care un acelasi mesaj este trimis de la sursa catre un numar oarecare de noduri destinatie, trebuie sa contina primitive eficiente de comunicatie colectiva, incluzand chiat broadcast realizat la nivelul aplicatiei, sincronizari prin bariere, reductii.

Multi algoritmi de multicast bazati pe arbori au fost conceputi, pentru a furniza o implementare eficienta a software-ului pe platforme paralele, care nu au suport hardware multicast.

Acesti algoritmi sunt fie dependenti de arhitectura (deci neportabili), fie independenti de arhitectura (portabili), dar care nu furnizeaza o buna performanta atunci cand sunt mutati pe platforme diferite.

Bazat pe modelul LogP, modelul de comunizatie parametrizata propus in continuare poate descrie mai fidel reteaua de comunicatie a platformelor paralele. Modelul se bazeaza pe anumiti parametri critici de sistem, parametri care pot fi masurati cu usurinta pe o platforma paralela data. De asemeni, sunt prezentate metode eficiente de constructie a arborilor optimali pentru realizarea multicastului pentru arhitecturi de comunicatie single-port. Cuvinte cheie: multicast, model LogP, programare paralela, comunicatie in retea, modelul de comunicatie parametrizata, comunicatie colectiva, arbori optimi de multicast Multicastul este un servici de sistem extrem de important in realizarea comunicatiei colective de tip unu-multi. Diferite servicii de comunicatie colectiva, cum ar fi broadcast-ul sau difuzia mesajelor, sunt un subset sau o derivatie a multicastului.

Drept urmare a importantei multicastului, s-au conceput o multitudine de implementari eficiente in trecut. Desi multicastul produs chiar prin hardware este de preferat, si a fost studiat in profunzime in ultimii ani, multe sisteme folosesc software in forma unei 0librarii de comunicatie pentru a suporta multicastul, bazandu-se pe hardware-ul de comunicatie punct-la-punct existent deja. pentru proiectarile independente de arhitectura, performantele variaza semnificativ de la o platforma la alta In mod evident, performantele optime ale masinilor paralele sunt dependente de arhitectura. Se poate mereu adapta o implementare pentru a obtine o mai buna performanta, bazata pe anumite caracteristici dependente de masina, cum ar fi, de exemplu, topologia retelei. Principala contributie a documentului de fata este de a caracteriza fiecare masina paralela prin anumiti parametri critici, specifici masinii. Implementarea bibliotecii de comunicatie pentru multicast este bazata pe acesti parametri de sistem, parametri care vor fi luati in consideratie in timpul fazei de compilare a bibliotecii. Astfel, algoritmii de multicast propusi sunt portabili si tin cont de aceste particularitatii cheie ale sistemului. In ...