P-Bandwidth Priority Queues on Reconfigurable Tree of Meshes
✍ Scribed by Alan A. Bertossi; Alessandro Mei
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 356 KB
- Volume
- 40
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
This paper shows a parallel implementation of a priority queue with bandwidth P and maximum size nP by means of a network with reconfigurable buses. The proposed solution is based on a tree of meshes architecture of O(nP 2 ) processors and O(P log n) maximum subbus length. The computational times required by the operations of a priority queue with bandwidth P are O(1) for all the operations, using the unit-time delay model for broadcasting, while they are O(1) for MIN and O(log P ؉ log log n) for both DELETEMIN and INSERT, using the log-time delay model. The proposed network can be laid out in a classical H-shaped manner to occupy O(nP 2 ) area in the VLSI model. When P ؍ O( 1), the required area is optimal and, using the unit-time delay model, the resulting AT 2 is also optimal. The paper presents also a very simple and efficient way of merging two sorted sequences on a reconfigurable mesh, which is used in the implementation of the priority queue operations.