Technical Report CS0696

Authors: Y. Ben-Asher and A. Schuster
PDF - RevisedCS0696.revised.pdf
Abstract: Reconfigurable networks attract increased attention recently, as an extremely strong parallel model which is realizable in hardware. In this work we consider the basic problem of gathering information which is dispersed among the nodes of the network. We analyze the complexity of the problem on reconfigurable linear-arrays. The analysis introduces a novel criteria for the efficiency of reconfigurable network algorithms, namely the {\em Bus-Usage}. The Bus-Usage quantity measures the utilization of the network sub-buses by the algorithm. It is shown how this yields bounds on the algorithm run-time, by deriving a run-time to bus-usage trade-off.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1991
To the main CS technical reports page

Computer science department, Technion