A generalized simultaneous access dictionary machine |
| |
Authors: | Fan Z Cheng K-H |
| |
Affiliation: | Adv. Comput. Solutions Inc., Houston, TX; |
| |
Abstract: | A simultaneous access design of a dictionary machine which supports insert, delete, and search operations is presented. The design is able to handle p accesses simultaneously and allows redundant accesses to occur. In the design, processors performing insert or delete operations are free to perform other tasks after submitting their accesses to the design; processors that perform search operations get their response in O(log N) time. Compared to all sequential access designs of a dictionary which require O(p ) time to process p accesses, the presented design provides much higher throughput; specifically, O(p/log p) times better. It also provides a fast mechanism to avoid the sequential access bottleneck in any large multiprocessor system |
| |
Keywords: | |
|
|