Reconfigurable systolic architectures for hashing

摘要

The authors develop a novel technique in which concepts of bothnbucketing and open addressing schemes are modified in such a manner thatnthey can be suitable for VLSI/WSI implementation, namely, dynamicallynreconfigurable hash tables. In this method, finite storage is allocatednfor each bucket. Instead of searching the entire table or a part of thentable for an empty storage place, the overflowing synonyms are insertedninto the successor's bucket (next to the home bucket). If thensuccessor's bucket overflows, the same technique is repeated until thentable is stable. The host bucket takes care of all the relativenoperations for its guest items. As soon as an empty place arises in thenoriginal bucket, the host bucket returns the guest element to thenoriginal bucket: in essence, dynamically variable capacity buckets havenbeen created. These buckets are designed using systolic arrays