Efficient VLSI Networks for Parallel Processing Based on Orthogonal Trees
- 1 June 1983
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-32 (6), 569-581
- https://doi.org/10.1109/tc.1983.1676279
Abstract
In this paper we describe two interconnection networks for parallel processing, namely the orthogonal trees network and the orthogonal tree cycles (OTN and OTC). Both networks are suitable for VISI implementation and have been analyzed using Thompson's model of VLSI. While the OTN and OTC have time performances similar to fast networks such as the perfect shuffle network (PSN), the cube comnected cycles (CCC), etc., they have substantially better area * time2 performances for a number of matrix and graph problems. For instance, the connected components and a minimal spanning tree of an undirected N-vertex graph can be found in 0(log4 N) time on the OTC with an area * time2 performance of 0(N2 log8 N) and 0(N2 log9 N) respectively. This is asymptoticaly much better than the performances of the CCC, PSN and Mesh. The OTC and OTN can be looked upon as general purpose parallel processors since a number of other problems such as sorting and DFT can be solved on them with an area * time2 performance matching that of other networks. Finally, programming the OTN and OTC is simple and they are also amenable to pipelining a series of problems.Keywords
This publication has 14 references indexed in Scilit:
- New lower bound techniques for VLSIPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981
- A model of computation for VLSI with related complexity resultsPublished by Association for Computing Machinery (ACM) ,1981
- A Critique and an Appraisal of VLSI Models of ComputationPublished by Springer Nature ,1981
- UltracomputersACM Transactions on Programming Languages and Systems, 1980
- Computing connected components on parallel computersCommunications of the ACM, 1979
- Bitonic Sort on a Mesh-Connected Parallel ComputerIEEE Transactions on Computers, 1979
- Sorting on a mesh-connected parallel computerCommunications of the ACM, 1977
- Bounds to Complexities of Networks for Sorting and for SwitchingJournal of the ACM, 1975
- Cellular arrays for the solution of graph problemsCommunications of the ACM, 1972
- An approach to the implementation of digital filtersIEEE Transactions on Audio and Electroacoustics, 1968