9. Előadás - Tömbrangsorolás, vezetőválasztás, lekérdezések

Adott egy láncolt lista, amelynek az elemeit egy tömbben helyezzük el.
Minden elemnek tároljuk a következő elem tömbbeli indexét. (Az egyszerűség kedvéért tekintsünk el az adatrészről, és csak ezzel az indexszel/mutatóval foglalkozzunk.)
Az utolsó elem a 0-ra mutat.
A tömbrangsorolás során meg kell határozni minden elemre, hogy mennyi további elem követi a listában. (Az elem után lévő elem számát nevezzük itt rangnak.)

Példa

Tekintsünk az alábbi 8 elemű listát!

Egy lehetséges tömbbös reprezentációja a tárolt kulcsoknak:

\[L = [1, 2, 3, 4, 5, 6, 7, 8]\]

A következő elemek indexszei:

\[A = [6, 0, 1, 7, 8, 4, 5, 2]\]

Az ehhez tartozó rangok a következők:

\[R = [6, 0, 7, 4, 2, 5, 3, 1]\]

Szekvenciális algoritmus

Tekintsünk egy \(n\) elemű listát, amelyet egy \(n\) elemű tömbben tárolunk.
Feltételezzük, hogy ismerjük a lista első elemének indexét, amelyet \(h\)-val (head) jelölünk.
A fej elemtől indulva, indexről-indexre haladva sorban be lehet állítani a rangokat \(n-1, \ldots, 0\) értékekre.

\[\begin{split}\begin{align*} &\text{RANKING}(@A, h, @R)\\ &\text{// Input}: A, \text{a következő elemek indexei a tömbben}\\ &\text{//}\quad\quad\quad h, \text{a lista első elemének indexe}\\ &\text{// Output}: R, \text{az adott indexeken lévő elemek rangja}\\ &i \leftarrow h\\ &\text{FOR }c \leftarrow n - 1 \text{ DOWNTO }0\text{ DO}\\ &\quad r_i \leftarrow c\\ &\quad i \leftarrow a_i\\ &\text{RETURN}(R)\\ \end{align*}\end{split}\]

Párhuzamos algoritmus

A problémára adható párhuzamos algoritmus a következő formában.

Állítsuk be minden olyan elemnek a rangját kezdetben 1-re, amelynek van következő eleme.
Az elemek rangját növeljük a következő elemük rangjával.
A következő elem indexét állítsuk át a következő elem rákövetkezőjének indexére.
Az így kapott indexszekkel folytassuk az algoritmust.

Látható, hogy a lépések minden elem esetében függetlenül végrehajthatók.

\[\begin{split}\begin{align*} &\text{DET_RANKING}(@A, @R)\\ &\text{// Input}: A, \text{a következő elemek indexei a tömbben}\\ &\text{// Output}: R, \text{az adott indexeken lévő elemek rangja}\\ &\text{PARALLEL FOR }i \leftarrow 1 \text{ TO }n\text{ DO}\\ &\quad \text{IF }a_i \neq 0\\ &\quad\quad \text{THEN }r_i \leftarrow 1\\ &\quad\quad \text{ELSE }r_i \leftarrow 0\\ &\text{FOR }j \leftarrow 1 \text{ TO }\lceil \log_2 n \rceil\text{ DO}\\ &\quad \text{PARALLEL FOR }i \leftarrow 1 \text{ TO }n\text{ DO}\\ &\quad\quad \text{IF }a_i \neq 0\\ &\quad\quad\quad \text{THEN }r_i \leftarrow r_i + r_{a_i}\\ &\quad\quad\quad\quad\quad\quad a_i \leftarrow a_{a_i}\\ &\text{RETURN}(R)\\ \end{align*}\end{split}\]

Figyelem

Ez az algoritmus az eredeti \(A\) tömb értékeit ki fogja nullázni!

Jól látható, hogy az algoritmus egy konstans idejű lépésből, és azt követően \(\lceil\log_2 n\rceil\) számú, szintén konstans idejű lépésből áll.

A determinisztikus tömbrangsoroló algoritmussal a tömbrangsorolási probléma \(T(n) = \Theta (\log_2 n)\) időben megoldható.

Példa

A	R
[6, 0, 1, 7, 8, 4, 5, 2]	[1, 0, 1, 1, 1, 1, 1, 1]
[4, 0, 6, 5, 2, 7, 8, 0]	[2, 0, 2, 2, 2, 2, 2, 1]
[5, 0, 7, 2, 0, 8, 0, 0]	[4, 0, 4, 4, 2, 4, 3, 1]
[0, 0, 0, 0, 0, 0, 0, 0]	[6, 0, 7, 4, 2, 5, 3, 1]

Vezetőválasztási probléma

Adott egy \(p\) számú csomópontból álló szinkronizált hálózat.

Minden csomópont

egyedi azonosítóval rendelkezik,
van egy logikai értéke, amely jelzi, hogy vezető-e vagy sem,
üzenetet tud küldeni a hálózatban hozzá kapcsolódó csomópontoknak,
üzenetet tud fogadni.

A feladat az, hogy döntsük el, hogy ki legyen a hálózat vezetője úgy, hogy minden csomópont csak a szomszédos elemekkel tud kommunikálni.

Vezetőnek választhatjuk például a legalacsonyabb vagy a legmagasabb azonosítójú processzort.

A feladatban az optimalizálás célja lehet például:

a szükséges lépések száma,
a küldött üzenetek száma,
a küldött üzenetek mérete.

Gyűrűben

Leader Election in Rings

LeLann algoritmus

Feltételezzük, hogy egy egyirányú gyűrűben vagyunk.
A processzorok egy részét kezdő processzoroknak tekintjük. Ezek indexeit egy \(K\) halmazban adjuk meg.
Nem feltételezzük, hogy a processzorok ismerik a hálózat méretét.

Jelölések:

\(A \in \mathbb{N}^p\): a processzorok azonosítóit tartalmazó vektor
\(S \in \{\text{TRUE}, \text{FALSE}, \text{NIL}\}^p\): a processzorok állapota (state) arra vonatkozóan, hogy vezetők-e.
\(C_i \subset \mathbb{N}, 1 \leq i \leq p\): processzorok indexeit tartalmazó halmazok (jelöltek, candidate)
SEND: üzenet küldése a gyűrűben következő processzornak
RECEIVE: üzenet fogadása az gyűrűben előző processzortól

\[\begin{split} \begin{align*} &\text{ELECT_LELANN}(@A, @K, @l)\\ &\text{// Input}: A \in \mathbb{N}^p,\text{ processzor azonosítók}\\ &//\quad\quad\quad\, K \subset \mathbb{N},\text{ kezdő processzorok indexei}\\ &\text{// Output}: l \in \mathbb{N},\text{ a vezető indexe}\\ &\text{PARALLEL FOR }i \leftarrow 1\text{ TO }p\text{ DO}\\ &\quad\text{IF }i \in K\\ &\quad\quad\text{THEN }s_i \leftarrow \text{NIL}\\ &\quad\quad\quad\quad\quad C_i \leftarrow \{a_i\}\\ &\quad\quad\text{ELSE }s_i \leftarrow \text{FALSE}\\ &\text{PARALLEL FOR }i \leftarrow 1\text{ TO }p\text{ DO}\\ &\quad\text{IF }s_i = \text{NIL}\\ &\quad\quad\text{THEN SEND}(a_i)\\ &\quad\text{DO RECEIVE}(j)\\ &\quad\quad\quad C_i \leftarrow C_i \cup \{j\}\\ &\quad\quad\quad\text{IF }j \neq a_i\\ &\quad\quad\quad\quad\text{THEN SEND}(j)\\ &\quad\quad\quad\text{WHILE }j \neq a_i\\ &\quad\text{IF }a_i = \min(C_i)\\ &\quad\quad\text{THEN }s_i \leftarrow \text{TRUE}\\ &\quad\quad\quad\quad\quad l \leftarrow i\\ &\quad\quad\text{ELSE }s_i \leftarrow \text{FALSE}\\ &\text{RETURN}(l)\\ \end{align*}\end{split}\]

A vezető indexét az algoritmus futását követően minden processzor ismeri:

\[l = \min(C_i)\]

Komplexitás

A szükséges lépések száma: \(T(p) = \Theta(p)\)
A küldött (majd fogadott) üzenetek száma: \(M(p) = \mathcal{O}(p^2)\)

Az algoritmus elvégzésekor a nem jelölt processzorok „beragadnak” az üzenet továbbítási állapotukba.

Ez kiküszöbölhető úgy, hogy ha a kiválasztott vezető körbeküld egy üzenetet, jelezve, hogy véget ért a vezetőválasztás.
A \(T(p)\) és \(M(p)\) komplexitásokra ez nincs hatással. (Mindkét függvény értéke természetesen nagyobb lesz.)

Chang-Roberts algoritmus

A LeLann algoritmus javítható azzal, hogy ha minden minden (kezdő) processzor csak a nála kisebb azonosítókat küldi tovább.

A processzoroknak elegendő csak az aktuális vezető jelölt indexét tárolni, így ebben az esetben \(C \in \mathbb{N}^p\).

\[\begin{split} \begin{align*} &\text{ELECT_CHANG_ROBERTS}(@A, @K, @l)\\ &\text{// Input}: A \in \mathbb{N}^p,\text{ processzor azonosítók}\\ &//\quad\quad\quad\, K \subset \mathbb{N},\text{ kezdő processzorok indexei}\\ &\text{// Output}: l \in \mathbb{N},\text{ a vezető indexe}\\ &\text{PARALLEL FOR }i \leftarrow 1\text{ TO }p\text{ DO}\\ &\quad\text{IF }i \in K\\ &\quad\quad\text{THEN }s_i \leftarrow \text{NIL}\\ &\quad\quad\quad\quad\quad c_i \leftarrow a_i\\ &\quad\quad\text{ELSE }s_i \leftarrow \text{FALSE}\\ &\text{PARALLEL FOR }i \leftarrow 1\text{ TO }p\text{ DO}\\ &\quad\text{IF }s_i = \text{NIL}\\ &\quad\quad\text{THEN SEND}(a_i)\\ &\quad\text{DO RECEIVE}(j)\\ &\quad\quad\quad\text{IF }j < c_i\\ &\quad\quad\quad\quad\text{THEN }c_i \leftarrow j\\ &\quad\quad\quad\quad\quad\quad\quad\text{SEND}(j)\\ &\quad\quad\quad\text{WHILE }j \neq a_i\\ &\quad\text{IF }c_i = a_i\\ &\quad\quad\text{THEN }s_i \leftarrow \text{TRUE}\\ &\quad\quad\quad\quad\quad l \leftarrow i\\ &\quad\quad\text{ELSE }s_i \leftarrow \text{FALSE}\\ &\text{RETURN}(l)\\ \end{align*}\end{split}\]

Komplexitás

A szükséges lépések száma: \(T(p) = \Theta(p)\)
A küldött (majd fogadott) üzenetek száma: \(M(p) = \mathcal{O}(p^2)\)
Átlagos esetben azonban: \(M(p) = \mathcal{O}(p \log p)\)

\(\rhd\) Mi az algoritmus szempontjából a legrosszabb eset?

Hirschberg-Sinclair algoritmus

Kétirányú gyűrűt feltételez.
Az üzenetszám minimalizálására törekszik.
Mindkét irányba egyszerre keresi a vezetőt.
Kettő hatvány szerint növelve \(1, 2, 4, 8, \ldots\) távolságokra küld üzenetet.

Komplexitás

A szükséges lépések száma: \(T(p) = \Theta(p)\)
A küldött (majd fogadott) üzenetek száma: \(M(p) = \mathcal{O}(p \log p)\)

Áttekintés

Algoritmus	Év	Topológia	üzenetszám
Le Lann	1977	egyirányú gyűrű	\(M(p) = \mathcal{O}(p^2)\)
Chang-Roberts	1979	egyirányú gyűrű	\(M(p) = \mathcal{O}(p^2)\), átlagosan \(M(p) = \mathcal{O}(p \log p)\)
Hirschberg-Sinclair	1980	kétirányú gyűrű	\(M(p) = \mathcal{O}(p \log p)\)

Fában

Leader Election in Rings

Max-terjed algoritmus

Tekintsünk egy irányítatlan fa gráf topológiát!
Minden csomópont tud üzenetet küldeni a szomszédjának vagy üzenetet fogadni tőle.
Kezdetben minden csomópontról feltételezzük, hogy ő maga lehet a vezető:

\[s_i \leftarrow \text{NIL}, 1 \leq i \leq p.\]

Minden csomópont először elküldi a saját azonosítóját az összes szomszédjának.
Minden csomópont fogad egy üzenetet. Amennyiben az abban szereplő azonosító nagyobb, mint az addigi maximális érték, akkor (az üzenet küldőjét leszámítva) tovább küldi az összes szomszédjának.

Figyelem

Az algoritmus természetesen az előzőekhez hasonlóan minimum kiválasztására is megfelelő.

Mivel a gráfban nincs kör, ezért az algoritmus véges lépésben le fog állni.

Komplexitás

Lánc (busz) esetében \(p - 1\) lépés lehet szükséges, tehát \(T(p) = \mathcal{O}(p)\).
Csillag topológia esetében 2 lépés szükséges.

Keresés

Logaritmikus keresés

Feltételezzük, hogy adott egy rendezett, \(n\) elemű valós sorozat.
Egy elem indexének visszakeresése \(T(n) = \mathcal{O}(\log n)\) időben elvégezhető.
A részintervallumokban való keresés párhuzamosítása nem praktikus.

Bináris keresés esetén a sorozatot minden lépésben 2 részre bontjuk. Ezt általánosíthatjuk \(k\) számú részintervallum vizsgálatára.

Jelölje \(x\) a keresett elemet!
Minél gyorsabban meg szeretnénk határozni, hogy \(x\) melyik intervallumba esik.

CRCW modell és \(p\) számú számítási egység esetén

az intervallum visszakeresése konstans időben elvégezhető, vagyis
a teljes keresés \(\log_p\) idő alatt elvégezhető.

CREW modell esetén minden

intervallum felosztásnál \(\log_p\) idő szükséges a megfelelő intervallum visszakereséséhez, tehát
a keresés időbonyolultsága \(T(p, n) = \mathcal{O}(\log_p n \cdot \log_p)\).
Amennyiben \(p\) értékét rögzítettnek tekintjük, így adódik, hogy a komplexitás ebben az esetben is \(T(n) = \mathcal{O}(\log n)\).
A párhuzamosítással lineáris gyorsítást tudunk elérni.

Szövegek keresése

Tegyük fel, hogy adott egy \(S\)-el jelölt \(n\) hosszúságú szöveg, amelyben egy \(Z\)-vel jelölt, \(m\) hosszúságú szöveget szeretnénk megkeresni.

Naiv algoritmus

A naiv, brute-force algoritmus időigénye: \(T(n, m) = \mathcal{O}(n \cdot m)\).

Az összehasonlítások jól párhuzamosíthatók.
Rengeteg a felesleges számítás.

Rabin-Karp algoritmus

Definiáljunk egy \(h\) hasító függvényt, amelyik a szöveghez egy számértéket (jellemzően egész értéket) rendel.
Számítsuk ki a keresett \(Z\) mintához tartozó \(h(Z)\) értéket!
Haladjunk végig az \(S\) \(m\) hosszúságú részsztringjein!
Számítsuk ki az ezekre vonatkozó hash értéket!
Hasonlítsuk össze a minta hash értékével!
Csak akkor vizsgáljunk teljes egyezést, hogy ha a hash értékek megegyeznek!

Az algoritmus hatékonyságának a kritikus pontja a \(h\) függvény hatékony számítása.

Amennyiben a \(h\) számítása \(m\)-mel arányos, úgy a keresés időigénye továbbra is: \(T(n, m) = \mathcal{O}(n \cdot m)\).
A görgetett hash számítása konstans idejű, így (feltételezve, hogy nem szükséges túl gyakran teljes egyezést vizsgálni a részsztringre) az időbonyolultság: \(T(n, m) = \mathcal{O}(n)\).

\(\rhd\) Adjunk példát görgetett hash számítására!

Párhuzamosítás

Feltételezhetjük, hogy \(n\) lényegesen nagyobb, mint \(m\).
\(p\) számítási egység esetén az \(S\) szöveget \(p\) részre bonthatjuk.
A részsztringek elérésekor az intervallumok átlapolódnak. (Ez CREW modell esetében sem jelent általában problémát, mert a vizsgálatokat az alacsonyabbtól a magasabb indexek felé végzi minden számítási egység).

A keresés céljától függően további optimalizálási lehetőségek is adódnak.

Első találat

Amennyiben csak az első találatot kell visszaadni, úgy a magasabb indexű számítási egységeknek be kell várniuk az alacsonyabbakat.
Hogy ha egy magasabb indexű már talált szöveget, a hátra maradt elemzendő részek feloszthatók újra az összes számítási egység között.

Összes találat

Minden számítási egység egy saját tömbbe/listába gyűjtheti az kapott indexeket, amelyeket a végén összesít az algoritmus.
Lehet használni egy közös tömböt/listát, amelybe folyamatosan belekerülnek az újonnan talált elemek. (A kölcsönös hozzáférést ez esetben meg kell oldani.)

Tetszőleges találat

Az algoritmusnak csak addig kell szöveget keresnie, amíg valamelyik számítási egység nem talált egyezést.
Egy megosztott logikai érték tudja jelezni, hogy szükség van-e még a további keresésre.

Halmazok és műveleteik

A halmaz reprezentációjára/implementációjára számos lehetőség adódik, például:

bittömbös reprezentáció,
tömb/lista,
rendezett tömb/lista,
bináris keresőfa (például piros-fekete fa),
hasítótábla.

Tartalmazás vizsgálata

Azt szeretnénk megvizsgálni, hogy egy \(a \in A\) teljesül-e.

Hogy ha \(p = |A|\) és CRCW modellünk van, akkor a vizsgálat konstans időben elvégezhető.

Ez a gyakorlatban ritkán adódik, ezért az alábbi eseteket érdemes fontolóra venni.

Bittömb esetében nincs értelme párhuzamosítani, mert a művelet eleve konstans idejű.
Tömbös reprezentáció esetében a lineáris időt \(p\)-szeresre lehet gyorsítani.
Egyszeresen láncolt listás reprezentáció esetében csak segéd mutatótömb beiktatásával oldható meg a gyorsítás.
Duplán láncolt lista esetében kereshetünk a lista 2 végéről kezdve.
Listák tömbjével a lineáris idő \(p\)-szeresre gyorsítható.
Rendezett tömb esetében logaritmikus keresést használhatunk.
Listák esetében a rendezettség nem segíti a hatékonyabb keresést.
Hasítótábla esetében a hash függvényt és a kipróbálási sorozat vizsgálatát lehet gyorsítani.
Bináris keresőfák esetében lineáris gyorsítás érhető el, hogy ha az \(|A|\) számú elemet \(p\) számú fába tároljuk el, amelyekben párhuzamosan tudunk keresni.

Alapvetően a szekvenciális esetben hatékony struktúrák \(p\) számú párhuzamos használata, majd az eredmények összegzése tud hatékony megoldást adni párhuzamos esetben.

A beszúrás és törlés műveletek kézenfekvő módon adódnak.
A párhuzamosítás a szekvenciális algoritmusok ismeretében könnyen elvégezhető.

\(\rhd\) Hogyan párhuzamosítható az unió és a metszet művelet végrehajtása?

Kérdések

Hogyan nézne ki a LeLann algoritmust egy processzor szemszögéből?

Feladatok

Tömbrangsolorás

Oldjuk meg a tömbrangsorolási problémát, hogy ha a lista elemei az 5, 1, 3, 2, 7, 4, 2 sorrendben követik egymást!

Vezetőválasztás

Készítsünk szimulációt \(p\) elemű gyűrűben, és ellenőrízzük a vezetőválasztáshoz szükséges lépés és üzenet számot a LeLann és a Chang-Roberts algoritmusok esetében!