Performance analysis and optimization of search and selection algorithms for highly parallel associative memories

Several useful associative memory (AM) algorithms deal with identifying extreme values (max or min) in a specified field of a selected subset of words. Previously proposed algorithms for such extreme-value searches are bit-sequential in nature, even when implemented on fully parallel AMs. We show how the multiple-bit search capability of a fully parallel AM can be used to advantage in reducing the expected search time for finding extreme values. The idea is to search for the all-ones pattern within subfields of the specified search field in lieu of, or prior to, examining bit slices one at a time. Optimal subfield length is determined for fixed-size and variable-size bit groupings and the corresponding reduction in search time is quantified. The results are extended to rank-based selection where the jth largest or smallest value in a given field of a selected subset of words is to be identified. Analyses point to significant reduction in the average number of search cycles