P-Bandwidth Priority Queues on Reconfigurable Tree of Meshes |
| |
Authors: | Alan A Bertossi Alessandro Mei |
| |
Affiliation: | Department of Mathematics, University of Trento, 38050 Povo, Trento, Italy |
| |
Abstract: | This paper shows a parallel implementation of a priority queue with bandwidthPand maximum sizenPby means of a network with reconfigurable buses. The proposed solution is based on a tree of meshes architecture ofO(nP2) processors andO(Plogn) maximum subbus length. The computational times required by the operations of a priority queue with bandwidthPareO(1) for all the operations, using the unit-time delay model for broadcasting, while they areO(1) for MIN andO(logP+ log logn) 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 occupyO(nP2) area in the VLSI model. WhenP=O(1), the required area is optimal and, using the unit-time delay model, the resultingAT2is 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|