This report describes a paper design and evaluation, and thus serves two purposes: It describes one particular VLSI sorting circuit, and it also serves as a case study in VLSI design methodology. The algorithm is described, the overall chip organization and data flow are presented, and detailed circuits, layouts, and timing analyses are given.

A scheme for maintaining a balanced search tree on O(lgN) parallel processors is described. O(lgN) search, insert, and delete operations are allowed to run concurrently, with each operation executing in O(lgN) timesteps. The scheme is based on pipelined versions of top-down 2-3-4 tree manipulation algorithms.

One of the difficulties of VLSI design is the magnitude of the task. It is not easy to lay out hundred thousand transistors, let alone ten million of them. Yet there is a sense in which the scale of VLSI is advantageous. The complexity of a VLSI chip is so great that asymptotic approximation can give insight into performance evaluation and design.

In our second case, an RC tree which is driven by at least one source has leaky capacitors. We show how to calculate delays for such trees by a linear time algorithm.