TR-135: An Optimal VLSI Dictionary Machine for Hypercube Architectures

Abstract

In this paper we present a VLSI dictionary machine implemented on a hypercube architecture. The proposed machine consists of two structures, a snake and a broadcast net, which are both embedded in and operate simultaneously on the same hypercube. All operations (Insert, Delete, Search, Extract Min, and Find Min) can be pipelined with 0(1) period, and the response time for Search and Find Min operations is O(log n) and 0(1), respectively. Furthermore, the proposed solution is capable of handling duplicate insertions and redundant deletions.