P-BANDWIDTH PRIORITY-QUEUES ON RECONFIGURABLE TREE OF MESHES

This paper shows a parallel implementation of a priority queue with ba ndwidth P and maximum size nP by means of a network with reconfigurabl e buses. The proposed solution is based on a tree of meshes architectu re of O(nP(2)) processors and O(P log n) maximum subbus length. The co mputational 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 II-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 A T? is also optimal. The paper presents also a very simple and efficien t way of merging two sorted sequences on a reconfigurable mesh, which is used in the implementation of the priority queue operations. (C) 19 97 Academic Press.