Enumeration Sort
Enumeration Sort je řadící algoritmus navržený pro efektivní paralelní výpočet na n*n procesorech, kde n je délka vstupního pole. V tomto ideálním případě má logaritmickou asymptotickou časovou složitost, kterí při použití jednoho procesoru stoupá až na kvadratickou. Algoritmus je v některých VLSI aplikacích implementován jako hardware.
Kroky algoritmu
Algoritmus pracuje ve třech hlavních krocích:
- porovnání – porovná dvojice prvků a vytvoří porovnávací matici
- binární sčítání – z porovnávací matice vypočítá výsledné pořadí každého prvku
- přeuspořádání – přeuspořádá prvky podle výsledného pořadí
Porovnání
Během porovnání jsou všechny dvojice prvků v poli vzájemně porovnány a výsledky jsou uloženy do čtvercové matice. Tato matice se označuje jako porovnávací matice (rank matrix) a obsahuje logické hodnoty TRUE (prvek A je větší než prvek B) nebo FALSE (prvek A není větší než prvek B). Není v ní nutné počítat hlavní diagonálu (je zbytečné porovnávat každý prvek sám se sebou) a jednu z polovin matice lze bez vytvořit „překlopením“ podél hlavní diagonály a inverzí hodnot (jednou je prvek A menší než B, podruhé je tomu naopak).
Porovnávání každé dvojice probíhá paralelně. Synchronizace procesorů není nutná, protože každý z nich zapisuje výslednou hodnotu do matice na jinou pozici. Hlavní tělo algoritmu však musí čekat, než všechny procesory dokončí svou práci.
Binární sčítání
Binární sčítání je název metody pro paralelní výpočet součtu pole. Pole je rozděleno na p dvojic, přičemž součet každé dvojice probíhá paralelně na jednom z p/2 procesorů. Vznikne pole poloviční délky s mezisoučty, na kterém je spuštěna další iterace binárního sčítání až do triviálního případu (součet jednoho nebo dvou prvků). Binární sčítání má logaritmickou složitost, je-li k dispozici alespoň n/2 procesorů, kde n je délka nejdelšího sčítaného pole.
V Enumeration Sort je binární sčítání použito k výpočtu pořadí všech prvků. To je rovno počtu logických hodnot TRUE v odpovídajícím sloupci porovnávací matice. Je-li tedy například nejmenší prvek menší než veškeré ostatní, má ve sloupci samé hodnoty FALSE a tak je ve výsledném poli první.
Paralelně probíhá binární sčítání všech sloupců matice, proces tedy vyžaduje n*(n/2) procesorů. Každý procesor zapisuje na jinou pozici, není je tedy nutné synchronizovat. Hlavní tělo algoritmu však musí čekat, než všechny procesory dokončí svou práci.
Přeuspořádání
Poslední fází Enumeration Sort je přeuspořádání všech prvků ze vstupního pole do výstupního. Algoritmus má nyní ve speciálním poli k dispozici výsledné pořadí všech prvků. Je tedy použito n procesorů pro paralelní přesun všech prvků ze vstupního pole na správnou pozici v poli výstupním. Každý procesor opět zapisuje na jinou pozici ve výsledném poli, není je tedy nutné synchronizovat. Potom, co všechny procesory dokončí svou práci, je výstupní pole seřazeno.
Časová složitost
Paralelní provádění
| Krok | Potřebný počet procesorů | Asymptotická složitost pro jeden procesor |
|---|---|---|
| Porovnání | n*n | O(1) |
| Binární součet | (n*n)/2 | O(log n) |
| Přeuspořádání | n | O(1) |
Sloučí-li se všechny uvedené kroky, je za předpokladu použití n*n procesorů asymptotická složitost logaritmická.
Sekvenční provádění
Při použití jednoho procesoru vzroste asymptotická složitost z logaritmické až na kvadratickou. Dominuje především zdlouhavý výpočet porovnávací matice.
Implementace (Java)
Následující implementace nemá logaritmickou složitost, protože využívá vláken, a i když jejich vytváření probíhá v konstantním čase, musí se přeci jen vytvořit. Z toho důvodu má implementace složitost kvadratickou. Toto omezení lze obejít pouze takovou implementací, která nebude žádná vlákna vytvářet a vždy jich bude mít n*n před spuštěním k dispozici. Následující kód je pouze ilustrativní, pro reálné použití není vhodný!
Porovnávací vlákno
Toto vlákno slouží k porovnání dvou čísel a uložení výsledku do porovnávací matice.
* Porovnávací vlákno.
* @param <T> třída prvků
*/
private static class ComparisonThread<T extends Comparable<? super T>> implements Runnable
{
/**
* reference na vstupní pole
*/
final private T input[];
/**
* reference na porovnávací matici
*/
final private boolean matrix[];
/**
* index dvojice v matici (mapování: 2D -> 1D)
*/
final private int index;
/**
* Vytvoří nové vlákno.
* @param input vstupní pole
* @param matrix porovnávací matice
* @param index index dvojice v matici
*/
public ComparisonThread (final T input[], final boolean matrix[], final int index)
{
this.input = input;
this.matrix = matrix;
this.index = index;
}
public void run ()
{
// vypočítat indexy (zpětné mapování: 1D -> 2D)
final int ix = this.index % this.input.length;
final int iy = this.index / this.input.length;
// porovnat prvky a výsledek uložit do matice
if (this.input[iy].compareTo (this.input[ix]) == 1)
{
this.matrix[this.index] = true;
}
else
{
this.matrix[this.index] = false;
}
}
}
zdrojový kód (Java) - zobrazit (1111 znaků)
Sčítací vlákno pro sloupec
Toto vlákno se využívá při součtu sloupce porovnávací matice.
* Vlákno pro součet sloupce.
*/
private static class ColumnSumThread implements Runnable
{
/**
* reference na porovnávací matici
*/
final private boolean matrix[];
/**
* index prvního prvku sloupce
*/
final private int iFirst;
/**
* index posledního prvku sloupce
*/
final private int iLast;
/**
* reference na pole s pořadím prvků
*/
final private int rank[];
/**
* index prvku odpovídajícímu sloupci
*/
final private int index;
/**
* Vytvoří nové vlákno.
* @param matrix porovnávací matice
* @param iFirst index prvního prvku sloupce
* @param iLast index posledního prvku sloupce
* @param rank pole s pořadím prvků
* @param index index odpovídajícího prvku
*/
public ColumnSumThread (final boolean matrix[], final int iFirst, final int iLast, final int rank[], final int index)
{
this.matrix = matrix;
this.iFirst = iFirst;
this.iLast = iLast;
this.rank = rank;
this.index = index;
}
public void run ()
{
// inicializovat délku sloupce
int length = this.iLast - this.iFirst + 1;
// vytvořit pole částečných součtů
final int sums[] = new int[length];
// inicializovat jeho hodnoty podle porovnávací matice
for (int i = 0; i < sums.length; i ++)
{
if (this.matrix[iFirst + i])
{
sums[i] = 1;
}
else
{
sums[i] = 0;
}
}
// vytvořit N/2 vláken
final Thread threads[] = new Thread[length]; // div by two!!!
// opakovat tak dlouho, dokud jsou nějaké páry k dispozici
while (length > 1)
{
// vypočítat počet párů
final int pairs = length / 2;
// vytvořit vlákno pro každý pár
for (int i = 0; i < pairs; i ++)
{
threads[i] = new Thread (new BinarySumThread (sums, i, pairs));
threads[i].start ();
}
try
{
// počkat než vlákna dokončí výpočty
for (int i = 0; i < pairs; i ++)
{
threads[i].join ();
}
}
catch (final InterruptedException x)
{
throw new UnsupportedOperationException ("Error during calculation: ", x);
}
// zmenšit délku sčítaného pole na polovinu
length /= 2;
}
// součet celého pole je nyní v prvním prvku
this.rank[this.index] = sums[0];
}
}
zdrojový kód (Java) - zobrazit (2347 znaků)
Sčítací vlákno pro binární sčítání
Toto vlákno se využívá při binárním součtu pole.
* Vlákno pro binární součet.
*/
private static class BinarySumThread implements Runnable
{
/**
* reference na dočasné pole částečných součtů
*/
final private int sums[];
/**
* index prvního prvku sčítaného páru
*/
final private int index;
/**
* vzdálenost druhého prvku sčítaného páru od prvního
*/
final private int step;
/**
* Vytvoří nové vlákno.
* @param sums dočasné pole částečných součtů
* @param index index prvního prvku sčítaného páru
* @param step vzdálenost druhého prvku sčítaného páru od prvního
*/
public BinarySumThread (final int sums[], final int index, final int step)
{
this.sums = sums;
this.index = index;
this.step = step;
}
public void run ()
{
this.sums[this.index] += this.sums[this.index + this.step];
}
}
zdrojový kód (Java) - zobrazit (815 znaků)
Přesouvací vlákno
Toto vlákno slouží k umístění prvku na správné pořadí.
* Vlákno pro přeuspořádání prvků do výstupního pole podle jejich vypočítaných pořadí.
* @param <T> třída prvků
*/
private static class ReorderThread<T extends Comparable<? super T>> implements Runnable
{
/**
* reference na vstupní pole
*/
final T input[];
/**
* reference na výstupní pole
*/
final T output[];
/**
* reference na pole s pořadím
*/
final int rank[];
/**
* index prvku ve vstupním poli
*/
final private int index;
/**
* Vytvoří nové vlákno.
* @param input vstupní pole
* @param output výstupní pole
* @param rank pole s pořadím
* @param index index prvku ve vstupním poli
*/
public ReorderThread (final T input[], final T output[], final int rank[], final int index)
{
this.input = input;
this.output = output;
this.rank = rank;
this.index = index;
}
public void run ()
{
int iTarget = this.rank[index];
while (this.output[iTarget] != null && this.output[iTarget].compareTo (this.input[index]) == 0)
{
// dva stejné prvky mají stejný index
// proto je třeba každý nový posunout
iTarget ++;
}
this.output[iTarget] = this.input[index];
}
}
zdrojový kód (Java) - zobrazit (1189 znaků)
Tělo algoritmu
* Implementace řazení Enumeration Sort.
* Toto je pouze ilustrativní a neefektivní implementace!
* @param <T> třída řazených prvků
* @param input vstupní pole
* @param output výstupní pole
* @throws InterruptedException chyba
* @author Vojtěch Hordějčuk
*/
public static <T extends Comparable<? super T>> void enumerationSort (final T[] input, final T[] output) throws InterruptedException
{
// vytvořit pole až pro N*N vláken
final Thread[] threads = new Thread[input.length * input.length];
// POROVNÁNÍ
// =========
// vytvořit porovnávací matici
final boolean[] matrix = new boolean[input.length * input.length];
// vytvořit N*N vláken
for (int i = 0; i < (input.length * input.length); i ++)
{
threads[i] = new Thread (new ComparisonThread<T> (input, matrix, i));
threads[i].start ();
}
// počkat na dokončení výpočtu
for (int i = 0; i < (input.length * input.length); i ++)
{
threads[i].join ();
}
// BINÁRNÍ SOUČET
// ==============
// vytvořit pole s výsledným pořadím
final int[] rank = new int[input.length];
// vytvořit N vláken
for (int i = 0; i < rank.length; i ++)
{
threads[i] = new Thread (new ColumnSumThread (matrix, i * rank.length, ((i + 1) * rank.length) - 1, rank, i));
threads[i].start ();
}
// počkat na dokončení výpočtu
for (int i = 0; i < rank.length; i ++)
{
threads[i].join ();
}
// PŘEUSPOŘÁDÁNÍ
// =============
// vytvořit N vláken
for (int i = 0; i < rank.length; i ++)
{
threads[i] = new Thread (new ReorderThread<T> (input, output, rank, i));
threads[i].start ();
}
// počkat na dokončení výpočtu
for (int i = 0; i < rank.length; i ++)
{
threads[i].join ();
}
}
zdrojový kód (Java) - zobrazit (1736 znaků)
Reference
- Dr. Jeane Stynes, Computer Science