Name
Abstract | ||
|---|---|---|
Several designs are presented for VLSI dictionary machines that combine both a linear (modify) network and a logarithmic (query) network with a novel idea for separation of concerns. The initial design objectives included: (1) single-cycle operability of host-issued modify and query commands (no compress instructions), (2) complete processor utilization (no waste processors), and (3) optimal 2 log n response times, where n is the current population of the machine. The authors sought simple ideas that, for the first time, would allow all three objectives to be achieved simultaneously. They were forced to abandon objective (3), instead achieving a slightly weaker objective, namely, near-optimal (2 log n+R) response times, where R is the time for a round trip through the particular prenetwork used to connect the host to the roots of the query trees in the logarithmic network. Both sorted and unsorted versions of dictionary machines are presented. Those with orthogonal command networks achieve all objectives; those without orthogonal networks achieve only the first and third. |
Year | DOI | Venue |
|---|---|---|
1990 | 10.1109/12.53580 | IEEE Trans. Computers |
Keywords | Field | DocType |
VLSI,database management systems,special purpose computers,trees (mathematics),design objectives,linear network,logarithmic network,optimal VLSI dictionary machines,query trees,single-cycle operability | Population,Binary logarithm,Computer science,Parallel computing,Separation of concerns,Response time,Theoretical computer science,Operability,Logarithm,Very-large-scale integration,Design objective | Journal |
Volume | Issue | ISSN |
39 | 5 | 0018-9340 |
Citations | PageRank | References |
6 | 0.69 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hon F. Li | 1 | 180 | 51.45 |
| David K. Probst | 2 | 103 | 29.79 |