An Efficient Unsorted VLSI Dictionary Machine

Abstract

A systolic binary tree machine which can handle all the dictionary machine and priority queue operations such as Insert, Delete, Extract-Min, Extract-Max, Member, and Near is designed in this paper. The operations can be fed into the tree machine in a pipeline manner at a constant rate and the output is correspondingly generated in a pipeline manner. Each processor in the machine stores at most one data element, which consists of a key value and a record associated with the key. The machine has optimal performance since if the number of data elements present in the tree is n, then each operation takes O(log n) steps. Unlike some recent designs, this machine does not use any links other than the binary tree links, provides optimal performance without the need to store data elements in any sorted order by exploiting dynamic rebalancing, has higher throughput, and keeps the logical last level of the tree on one physical level of the tree.