Dictionary Machines for Cube-Class Networks.
Abstract
A dictionary is a data structure that supports insertion, deletion, and retrieval operations. To maintain a database, a dictionary machine accepts an arbitrary sequence of instructions at a constant rate. This idea presents two new VLSI dictionary machines on networks that emulate the binary cube. One machine runs on a shuffle-exchange network. The other machine runs on a cube-connected cycles network. These two designs demonstrate that general purpose networks can perform dictionary operations. Chapter 1 includes a definition of the dictionary machine problem and an overview of previous work. Chapters 2 and 3 present the bulk of this idea: two dictionary algorithms that run on cube-class architectures. The design in Chapter 2 uses bitonic merge to perform dictionary operations on the SEN. It also presents a novel architecture to implement pipelining. This architecture is an important contribution. The dictionary algorithm of Chapter 3 runs on the CCC and borrows heavily from previous work on tree machines. Chapter 4 places these new designs in perspective with previous work and offers concluding remarks.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 05, 1985
- Accession Number
- ADA161393
Entities
People
- Alan M. Schwartz
Organizations
- University of Illinois Urbana–Champaign