Meshes with multiple buses
- 1 October 1986
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 264-273
- https://doi.org/10.1109/sfcs.1986.32
Abstract
This paper considers mesh computers with buses, where each bus provides a broadcasting capability to the processors connected to it. We first disprove a published claim by showing that on a 2-dimensional mesh with a bus for each row, where each row must solve its own problem with data that is independent of all other rows, there are problems where the rows can cooperatively solve all subproblems faster than any single row can solve its own problem. As a corollary we obtain efficient solutions to some graph problems. We also consider the optimal layout of buses for a given dimension and number of buses per processor, where optimality is defined in terms of the time needed to simulate any other machine with the same constraints. Using new families of layouts, optimal or nearly optimal families of layouts are determined for each possible choice of dimension and number of buses per processor.Keywords
This publication has 11 references indexed in Scilit:
- Data Movement Techniques for the Pyramid ComputerSIAM Journal on Computing, 1987
- Optimal Bounds for Finding Maximum on Array of Processors with k Global BusesIEEE Transactions on Computers, 1986
- Fat-trees: Universal networks for hardware-efficient supercomputingIEEE Transactions on Computers, 1985
- Solving tree problems on a mesh-connected processor arrayPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Solving some graph problems with optimal or near-optimal speedup on mesh-of-trees networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Graph Problems on a Mesh-Connected Processor ArrayJournal of the ACM, 1984
- Finding Maximum on an Array Processor with a Global BusIEEE Transactions on Computers, 1984
- Mesh-Connected Computers with BroadcastingIEEE Transactions on Computers, 1983
- Design of a Massively Parallel ProcessorIEEE Transactions on Computers, 1980
- Computing connected components on parallel computersCommunications of the ACM, 1979