Přejít k obsahu


Parallel Algorithm for Concurrent Computation of Connected Component Tree

Citace: [] MATAS, P., DOKLÁDALOVÁ, E., AKIL, M., GRANDPIERRE, T., NAJMAN, L., POUPA, M., GEORGIEV, V. Parallel Algorithm for Concurrent Computation of Connected Component Tree. Lecture Notes in Computer Science, 2008, roč. 0, č. 5259, s. 230-241. ISSN: 0302-9743
Druh: ČLÁNEK
Jazyk publikace: eng
Anglický název: Parallel Algorithm for Concurrent Computation of Connected Component Tree
Rok vydání: 2008
Místo konání: Berlin
Název zdroje: Springer-Verlag
Autoři: Petr Matas , Eva Dokládalová , Mohamed Akil , Thierry Grandpierre , Laurent Najman , Martin Poupa , Vjačeslav Georgiev
Abstrakt CZ: Článek předkládá nový paralelní algoritmus pro konstrukci stromu souvislých komponent založený na nezávislém stavění po řádkách a postupném slučování částečných 1-D stromů. Byly vyvinuty dvě strategie paralelizace: Strategie pro maximalizaci paralelismu, která vyvažuje vytížení procesů, a strategie pro minimalizaci komunikace, která minimalizuje komunikaci mezi procesy. Nový algoritmus může zpracovávat libovolný datový typ pixelů, protože nepoužívá hierarchickou frontu. Algoritmus potřebuje jen vstupní a výstupní buffery a malý zásobník. Na 4-jádrové architektuře s procesory Opteron se sdílenou pamětí ccNUMA bylo dosaženo zrychlení 3,57 v porovnání se sekvenčním algoritmem. Porovnání výkonu s existujícím stavem techniky je také probíráno.
Abstrakt EN: The paper proposes a new parallel connected-component-tree construction algorithm based on line independent building and progressive merging of partial 1-D trees. Two parallelization strategies were developed: the parallelism maximization strategy, which balances the workload of the processes, and the communication minimization strategy, which minimizes communication among the processes. The new algorithm is able to process any pixel data type, thanks to not using a hierarchical queue. The algorithm needs only the input and output buffers and a small stack. A speedup of 3.57 compared to the sequential algorithm was obtained on Opteron 4-core shared memory ccNUMA architecture. Performance comparison with existing state of the art is also discussed.
Klíčová slova

Zpět

Patička