Systolic tree implementation of data structures

Author

Chang, Jik H. ; Ibarra, Oscar H. ; Chung, Moon Jung ; Rao, Kotesh K.

Author_Institution

Dept. of Comput. Sci., Minnesota Univ., Minneapolis, MN, USA

Volume

37

Issue

6

fYear

1988

fDate

6/1/1988 12:00:00 AM

Firstpage

727

Lastpage

735

Abstract

Systolic tree architectures are presented for data structures such as stacks, queues, dequeues, priority queues, and dictionary machines. The stack, queue, and dequeue have a unit response time and a unit pipeline interval. The priority queue also has a unit response time, but the pipeline interval is 2. The response time and pipeline interval for the dictionary machine are O(log n) and O(1), respectively, where n is the number of data elements currently residing in the tree. In each node of the tree, the mechanism for controlling the transmission and distribution of data is finite state. This feature makes the designs presented here suitable for VLSI. If there are n data elements in the data structure, the depth of the tree is O(log n)

Keywords

data structures; queueing theory; trees (mathematics); data elements; data structures; data transmission; dequeues; dictionary machines; queues; stacks; systolic tree implementation; unit pipeline interval; unit response time; Algorithm design and analysis; Computer science; Data structures; Delay; Dictionaries; Pipelines; Routing; Systolic arrays; Tree data structures; Very large scale integration;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.2211

Filename

2211