| 摘要 |
A hardware accelerator (120) for managing a computer database (110). The accelerator (120) includes a key memory (124) for storing a map of record key values to record address values, a search processor (122) for searching the key memory (124) for a given key value and providing the associated record address value to the central processor (102), and a bus interface (130) for interfacing the search processor (122) and the key memory (124) to the central processor (102). Database management software (116) executing on the central processor (102) requests a mapping from key values to record address values by issuing requests over the bus interface (130) to the search processor (122). The accelerator (120) also provides operations to add and delete entries in the key memory (124). The accelerator (124) uses a modified binary search that is particularly useful for searching a memory in which the search values of the entries are not unique; the modified binary search finds the first entry in the memory matching a given value. At each iteration of the binary search, the CARRY generated by the comparison of the probed entry to the given value is used to alter the probe address calculated in the next iteration of the search. Instead of terminating when the given value is found, the search continues until the start and end addresses have converged on the first entry that matches the given entry.
|
