Szimuláció
 G. Michael Schneider 
Using Parallel Merge Sort to Teach Fundamental Concepts in Distributed Parallelism 
című cikke alapján
(??? lelőhely)
A szimuláció során próbálom megmutatni, hogyan lehet hatékony elosztott algoritmust tervezni. Olyat amely számítógépek hálózatán fut és ráadásul gyorsabban, mint egy számítógépes társai.
Ehhez bemutatom a párhuzamos összefésülő rendezés egy változatát, amely rendkívüli rugalmasságának köszönhetően ideálisan formálható a különböző felmerülő problémák megoldására. Ráadásul ennek az algoritmusnak azon előnye is megvan a többi párhuzamos algoritmussal szemben, hogy elég könnyen érthető és implementálható. Én egy PVM-es változatot készítettem, hogy tesztadatokkal is alá tudjam támasztani állításaimat.
Az alap párhuzamos összefésülő rendezés
A párhuzamos összefésülő rendezés egy exkluzív memóriájú, üzenetküldésen és rendezésen alapuló algoritmus. A P darab processzort, amin az algoritmus fut, logikailag tekinthetjük egy teljes bináris fának. 

Tegyük fel, hogy N adatot akarunk rendezni. Az algoritmus szerint kezdetben a processzorok tárolnak N/P adatot a saját memóriájukban. Ezt a kezdeti állapotot úgy tudjuk elérni, hogy mind a P processzor kezdetben legenerál N/P véletlen számot és eltárolja egy tömbben, ekkor minden processzor szinkronizál, hogy ne fussanak, amíg mindenki be nem fejezte a bemenet előállítását. Ezt az időtartamot nem fogjuk belevenni a számításokba.
Az algoritmusnak 2 fázisa van: rendezési és párhuzamos összefésülési.
Rendezési fázis:
Mind a P processzor rendezi az N/P elemét az elérhető leggyorsabb rendező algoritmussal – optimalizált Gyorsrendezővel. Így kapunk P rendezett részlistát.  Minden processzor mutatót állít a legnagyobb még el nem küldött elemére.
Párhuzamos összefésülési fázis:
Minden levél a fázis elején elküldi a legnagyobb értéket a szülő csúcsának. A szülő összehasonlítja a jobboldali gyermekétől, a baloldali gyermekétől kapott értéket és a saját legnagyobb értékét, hogy meghatározza a legnagyobbat a 3 érték közül. Ezt az értéket pedig tovább küldi az ő szülőjének. Ha a legnagyobb érték valamelyik gyermekétől származott, akkor megkéri a megfelelő gyermeket, hogy küldjön egy újabb számot. Ha a legnagyobb szám a sajátja volt, akkor tovább lépteti a mutatóját. Ha egy gyermek felhasználta mind az N/P számát, akkor egy speciális értéket -1 –et küld el, majd leáll. Ha egy szülő mindkét gyermekétől -1 –et kapott és felhasználta az összes számát akkor ő is -1 –et küld tovább és leáll. Így a folyamatok leállási hulláma alulról felfelé halad a fában.

A teljes algoritmus:
Generáljunk le N/P nem negatív véletlen értéket és tároljuk őket az X[1..N/P] tömbben.
Tároljuk el a speciális jelölő értéket -1 -et az X[N/P+1] helyre.
Állítsuk a TETŐ mutatót az első értékre.
Szinkronizáció. // itt várnak, amíg mindenki le nem generálta az értékeit.
Ha (gyökér) akkor elindítja az órát.
// Első fázis
Gyorsrendezés (X, N/P+1) // lerendezi az N/P+1 elemet. A -1 lesz az utolsó elem.
// Második fázis
if levél
	do
		elküld X[TETŐ] a szülőnek.
		TETŐ=TETŐ+1
	while küldött érték nem -1
	Leállás
if belső csúcs
do
	Értéket fogad a jobb oldali gyermektől, amit J-be másolja.
	Értéket fogad a bal oldali gyermektől, amit B-be másolja.
	LEGNAGYOBB = MAX (J, B, X[TETŐ])
if nem gyökér
		LEGNAGYOBB elküldése a szülőnek.
	if a LEGNAGYOBB J volt
		Értéket fogad a jobb oldali gyermekétől, amit J-be másol.
	Else if a LEGNAGYOBB B volt
		Értéket fogad a bal oldali gyermekétől, amit B-be másol.
	else
		TETŐ=TETŐ+1
while az elküldött érték nem -1
if gyökér
	Óra leállítása
Leállás

Eredmények
A szimulációt a karunk klaszterbe fűzött számítógépein végeztem. Ez az elosztott rendszer érhető el számunkra, de megvannak a maga problémái. Viszont pont ezek a problémák azok, amelyeket vizsgálni szeretnék.
Az algoritmust a PVM segítségével valósítottam meg (prog1) és futtattam 7 db Pentium4-es 1.7GHz -es számítógépen. Készült az algoritmusból még egy soros változat is, hogy mérni lehessen a gyorsulást.
Illetve minden változatból van olyan, amely kiírja a képernyőre, hogy éppen hol jár és olyan, amely semmilyen információval nem szolgál futásának állapotáról (ez gyorsabb, hiszen nem kell a lépernyőre írnia, illetve nem is terheli fölöslegesen a hálózatot).

A soros algoritmus 700.000 számot Tsoros =0,3 másodperc alatt rendezett le.
Lemértem a párhuzamos változat futási idejét, ahol 7 processzor mindegyike 100.000 számot generált.

Meglepetésemre a Tpárh = 544,5 másodperc futási időt kaptam.
A párhuzamos algoritmus, ami 7 processzort használt 1813 szor lassabban futott a soros algoritmusnál.
Egyértelmű, hogy a párhuzamos rész az, ami sokáig tart. Valószínűleg a kommunikáció okozza a nem várt problémát. Ezt igazolandó lemértem mennyi ideig tart átküldeni 4 byte –ot a hálózaton Tkomm = 19 milliomodmásodperc, és hogy mennyi ideig tart két ilyen méretű lebegőpontos szám összeadása Tszum = 1 milliomodmásodperc (sajnos ezek nem teljesen hitelesek, hiszen csak ennyire pontosan tudtam mérni az időt, illetve a pvm is biztosan hozzátesz valamennyi adatot a csomagokhoz). A mérések még így is azt mutatják, hogy a hálózaton történő adattovábbítás hatalmas költségekkel jár.
Minden belső csúcs elvégez 2 összehasonlítást (hogy meghatározza a maximumukat), majd pedig 2 kommunikációs lépést (elküldi a maximumot a szülőnek, majd kér egy újat a megfelelő gyermekétől). Az algoritmus első változatában ez 1 millió üzenet kerül elküldésre, hiszen a legalsó szinten lévő 400.000 adatot kétszer kell elküldeni, hogy elérje a gyökeret, a 2. szinten lévő 200.000 ezer értéket csak egyszer kell továbbküldeni. Az érzékeny algoritmus és a relatív lassú hálózat okozta a hatalmas lassulást.
Valahogy csökkenteni kell a kommunikációt.
Lapos fa rendezés (prog2)
Próbáljuk meg kilaposítani a fát.
A kétszintes fának 1millió üzenet kellett a rendezéshez, a laposított fával összesen 600.000 üzenetet fogunk csak elküldeni, hiszen ennyi érték található a levelekben, amit el kellene küldeni a szülőnek. Ez 400.000 üzenettel kevesebb, mint a teljes fában elküldött üzenetek száma.
A futási idő Tpárh = 171,2 másodperc volt.
Ez 3 szoros sebesség javulás, de még meg sem közelíti a soros algoritmus futási idejét. Még így is jelentős a kommunikációs költség. A megfelelő mértékű gyorsulás eléréséhez nagyságrendileg kell tudnunk csökkenteni az üzenetek számát. Valamint felmerül az a probléma is, hogy ez már nem párhuzamos algoritmus, hanem soros. Az eredeti több szintes fa esetén, a középső szinten egyszerre 2 csúcs tudott összehasonlításokat végezni. A mostani lapos fa eseten a gyökér végez csak összehasonlításokat. Amíg ő elvégzi az összehasonlításokat, addig az összes levél csúcs várakozik. Mikor elkészült az összehasonlítással akkor is csak az egyik levéltől kér új adatot. Így az összefésülési fázisban mindig csak egy levél dolgozik egyszerre. Ez létrehozott egy rejtett soros algoritmus részt, amely Amdahl törvényének megfelelően felső korlátot szab a program futási sebességének.
Pufferezett párhuzamos összefésülő rendezés (prog4)
A kommunikáció csökkentésére érdemes megpróbálni az üzenetek pufferelését.
Mikor egy gyermek csúcsot megkérnek, hogy küldjön egy adatot a szülőjének, küldhetne akár K darab adatot tartalmazó üzenetet is, ahol K>1. A szülő elfogadná a K darab számot tartalmazó üzenetet, felhasználná az elsőt és pufferelné a maradék K-1 –et. Így csak akkor kell egy folyamatnak új üzenetet küldenie amikor kiürült a szülő csúcs puffere. Ezzel a módszerrel elvileg 1/K –ra lehet csökkenteni a csúcs által elküldött üzenetek számát.
Ezt az algoritmust 10 és 100.000 közötti K értékre futtattuk.
Az algoritmus a vártnak megfelelően viselkedett. Minél több adatot raktunk bele egy üzenetbe annál nagyobb gyorsulást értünk el.
10 adat esetén Tpárh= 85,3 másodperc, 50 adat esetén Tpárh= 18,4 másodperc volt a futási idő.
Ez 29.6 szor gyorsabb, mint a legelső eredmények.
Így a gyorsítás
Sp=Tsoros/Tpárh= 0,3/18,4 =0,01
És a hatékonyság
Ep=Sp/P=0,01/7=0,001

Még nem túl hatékony.
Tesztelve az abszolút optimális esetet mikor egy üzenetbe rakunk bele minden adatot, vagyis K=100.000 . Tpárh=1,4másodperc.
Sp=Tsoros/Tpárh=0,3/1,4=0,21
Ep=Sp/P=0,21/7=0,03