Title:
|
A systolic algorithm for the fast computation of the connected components of a graph
|
Author:
|
Núñez, Fernando J.; Valero Cortés, Mateo
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament d'Arquitectura de Computadors; Universitat Politècnica de Catalunya. CAP - Grup de Computació d'Altes Prestacions |
Abstract:
|
The authors consider the description of a systolic algorithm to solve the connected-component problem. It is executed in a ring topology with N processors, requiring O(Nlog N) time without regard to the graph's sparsity. The algorithm-partitioning issue is also addressed, indicating how to optimally map the computations into fixed-size rings or linear arrays. The proposed algorithm leads to simple processing elements, data addressing, and control. These points make the systolic array highly implementable. |
Abstract:
|
Peer Reviewed |
Subject(s):
|
-Àrees temàtiques de la UPC::Informàtica::Arquitectura de computadors -Parallel algorithms -Multiprocessors -Cellular arrays -Computer architecture -Multiprocessing systems -Algorismes paral·lels -Multiprocessadors |
Rights:
|
|
Document type:
|
Article - Published version Conference Object |
Published by:
|
Institute of Electrical and Electronics Engineers (IEEE)
|
Share:
|
|