Atallah, Mikhail J.; Kosaraju, S. Rao A generalized dictionary machine for VLSI. (English) Zbl 0555.68011 IEEE Trans. Comput. 34, 151-155 (1985). We show that a machine in which the processors are interconnected as a binary tree can support all the dictionary and priority queue operations as well as some other data queries. Everyone of the operations takes O(log n) steps where n is the number of keys present. A sequence of operations can be pipelined at a constant rate. In previous designs, either an operation required \(\Omega\) (log N) steps where N is the total capacity of the machine, i.e., the maximum number of keys that can be stored in it, or O(log n) performance was achieved at the expense of additional wires. Cited in 1 ReviewCited in 4 Documents MSC: 68N25 Theory of operating systems Keywords:parallel processing; pipelining; tree machine; VLSI; binary tree; dictionary; priority queue; data queries PDFBibTeX XMLCite \textit{M. J. Atallah} and \textit{S. R. Kosaraju}, IEEE Trans. Comput. 34, 151--155 (1985; Zbl 0555.68011) Full Text: DOI