An efficient VLSI dictionary machine

A binary tree machine which can handle all the dictionary machine and priority queue operations as well as some other data queries is designed in this paper. This machine supports operations like Insert, Delete, Extract-Min/Max, Membership and Near and their redundant forms. If the number of keys present in the tree is n, then each of the operations takes O(log n) steps, and can be fed into the tree in a pipeline manner at a constant rate. A machine with N&equil;2**s-1 processors can store upto N-s data elements. The output is generated at a fixed interval. It does not use any horizontal wires as in some previous designs. Moreover, this approach does not require any sorted-order, is potentially applicable to non-binary tree structures, and is significantly simpler to implement than all the previous designs.

• Publication year

  1984

• Venue

  International Symposium on Computer Architecture

• Publication date

  Unknown publication date

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1145/800015.808176
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A Generalized Dictionary Machine for VLSI

  1985influential reference
• Area-Efficient VLSI Computation

  1983cited by this paper
• Introduction to the configurable, highly parallel computer

  1982cited by this paper
• A Dictionary Machine (for VLSI)

  1982cited by this paper
• The Power of a One-Dimensional Vector of Processors

  1980cited by this paper
• Direct VLSI Implementation of Combinatorial Algorithms

  1979cited by this paper
• Decomposable Searching Problems

  1979cited by this paper
• Systolic Priority Queues

  1979cited by this paper
• Systolic Arrays for (VLSI).

  1978cited by this paper
• A cellular computer to implement the kalman filter algorithm

  1969cited by this paper

• Concurrent Data Structures for Hypercube Machine

  1992cites this paper
• Banyan heap machine

  1992cites this paper
• A MULTIPROCESSING MODEL OF NATURAL LANGUAGE PROCESSING

  1990cites this paper
• New designs for priority queue machine

  1990cites this paper
• The De Bruijn Multiprocessor Network: A Versatile Parallel Processing and Sorting Network for VLSI

  1989cites this paper
• Concurrent Access of Priority Queues

  1988cites this paper
• Dictionary Machines on Cube-Class Networks

  1987cites this paper
• Parallel Algorithms for Some Computational Problems

  1987cites this paper
• The application of a geometric arithmetic parallel systolic array processor to database machine design

  1986cites this paper
• Survey on special purpose computer architectures for AI

  1986cites this paper
• An Efficient Unsorted VLSI Dictionary Machine

  1985cites this paper