AVERAGE-CASE ANALYSIS OF SEARCHING IN ASSOCIATIVE PROCESSING

We introduce an average case analysis of the search primitive operatio ns (equality and thresholding) in associative memories. We provide a g eneral framework for analysis, using as parameters the word space dist ribution and the CAM size parameters: m (number of memory words) and n (memory word length). Using this framework, we calculate the probabil ity that the whole CAM memory responds to a search primitive operation after comparing up to k most significant bits (l less than or equal t o k less than or equal to n) in each word; furthermore, we provide a c losed formula for the average value of k and the probability that ther e exists at least one memory word that equals the centrally broadcast word. Additionally, we derive results for the cases of uniform and exp onential distribution of word spaces. We prove that in both cases the average value of k depends strongly on Ig m, when n > lg m: for the ca se of uniform distribution, the average value is practically independe nt of n, while in the exponential depends weakly on the difference bet ween the sample space size 2(n) and the CAM size m. Furthermore, in bo th cases, the average k is approximately n when n less than or equal t o lg m. Verification of our theoretical results through massive simula tions on a parallel machine is presented. One of the main results of t his work, that the average value of k can be much smaller than n or ev en practically independent of n in some cases, has an important practi cal effect: associative memories can be designed with fast execution t imes of threshold primitives and low implementation complexity, leadin g to high performance associative memories that can scab up to sizes l arger than previous designs at a low cost. (C) 1998 Academic Press, In c.