An efficient implementation of priority queues using fixed-sized systolic coprocessors

DOI10.1016/0020-0190(93)90026-6MaRDI QIDQ685514zbMATH OpenOpenAlexFDO

Authors Jyh-Jong Tsay

Publication date 9 January 1994

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(93)90026-6

zbMATH Keywords

DELETEEXTRACT-MININSERTpriority queuessystolic array

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25)

Review text

We consider the problem of maintaining a set which supports the INSERT, DELETE and EXTRACT-MIN operations on a random access machine to which a linear systolic array of \(p\) processing elements is attached. We give an implementation that performs a sequence of \(n\) INSERT and EXTRACT-MIN operations on-line in time \(O(n \log m/\log p)\) and space \(O(m)\), provided that, at any time instance, there are at most \(m(m\leq n)\) data elements existing. The implementation can be easily modified to handle DELETE operations. This gives \(O(n \log m/\log p)\) time solutions to the problems that can be reduced to the problem of performing a sequence of \(O(n)\) INSERT, DELETE and EXTRACT-MIN operations.

Recommendations

• Priority queues on parallel machines
• Priority queues on parallel machines
• Parallel priority queues
• Randomized priority queues for fast parallel access
• A parallel priority queue with constant time operations

Cites work

• An On-Chip Compare/Steer Bubble Sorter
• On the parallel-decomposability of geometric problems
• Sorting n objects with a k-sorter
• Sorting numbers using limited systolic coprocessors
• The complexity of selection and ranking in X+Y and matrices with sorted columns

This page was built for publication: An efficient implementation of priority queues using fixed-sized systolic coprocessors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685514)