Nonlinear associative memories using linear arrays of associative memory cells, and methods of operating same

• US 7,657,496 B2
• Filed: 06/26/2006
• Issued: 02/02/2010
• Est. Priority Date: 06/26/2006
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Saffron Technology, Inc. (Intel Corporation)
• Inventors: Aparicio, Manuel IV
• Primary Examiner(s): Vincent; David R
• Assistant Examiner(s): Fernandez Rivas; Omar F
• Application Number:
  US11/426,520
• Publication Number:
  US 20070299797A1
• Time in Patent Office: 1,317 Days
• Field of Search: 706 15- 22, 706/26, 711/128
• US Class Current: 706/26
• CPC Class Codes: G06N 3/044 Recurrent networks, e.g. Hopfield networks
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores

Abstract

Associative memories include associative memory cells. A respective cell includes a sensor input, a prior association representation, a next association representation and an associative output. The cells are serially interconnected to form a linear array, such that the sensor inputs, the prior association representations and the next association representations of the serially connected cells are arranged in a sequence from distal to proximal cells based on affinities of associations among the series of sensor inputs. A respective cell also includes processing logic. The processing logic is responsive to the associated sensor input being active, to send a measure of the next association representation to an adjacent proximal cell and/or to send a measure of prior association representation to an adjacent distal cell. The processing logic may be further responsive to the associated sensor input being active, and to receipt of the measure of the next association representation from an adjacent distal cell, to accumulate an associative count in the associative output.

Claims

1. An associative memory comprising:

a plurality of associative memory cells, a respective cell including a sensor input, a prior association representation, a next association representation and an associative output, the plurality of cells being serially connected to form a linear array, such that the sensor inputs, the prior association representations and the next association representations of the serially connected cells are arranged in a sequence from distal to proximal cells based on affinities of associations among the sensor inputs;

a respective cell also including processing logic therein;

that is responsive to the sensor input of the respective cell being active to send a measure of the next association representation to an adjacent proximal cell and/or to send a measure of the prior association representation to an adjacent distal cell; and

that is further responsive to the sensor input being active, and to receipt of the measure of the next association representation from an adjacent distal cell, to accumulate an associative count in the associative output and/or that is responsive to the sensor input being active, and to receipt of the measure of the prior association representation from an adjacent proximal cell, to accumulate an associative count in the associative output,

wherein the affinities of associations among the sensor inputs are determined by repeatedly swapping inputs, prior association representations and next association representations in the series based upon affinities of associations in the proximal and distal directions.

2. An associative memory according to claim 1 wherein the processing logic is further responsive to receipt of the next association representation from an adjacent distal cell and to the prior association representation being active, to decrement the measure of the next association representation that was received and to send the measure of the next association representation that was decremented to the adjacent proximal cell and/or is further responsive to receipt of the measure of the prior association representation from an adjacent proximal cell and to the next association representation being active, to decrement the measure of the prior association representation that was received and to send the measure of the prior association representation that was decremented to the adjacent distal cell.

3. An associative memory according to claim 2 wherein the processing logic is further responsive to receipt of the measure of the next association representation from an adjacent distal cell and to the prior association representation being inactive, to send the measure of the association representation that was received to the adjacent proximal cell and/or is further responsive to receipt of the measure of the prior association representation from an adjacent proximal cell and to the next association representation being inactive, to send the measure of the prior association representation that was received to the adjacent distal cell.

4. An associative memory according to claim 1 wherein the affinities of associations among the sensor inputs are further determined by extracting bands from the series that has been repeatedly swapped, based on projections.

5. An associative memory according to claim 4 wherein the projections comprise maximal projections, fixed length projections and/or longest nonmaximal projections.

6. An associative memory according to claim 1 wherein the prior association representation and the measure of the prior association representation comprise prior association weights, and the next association representation and the measure of the next association representation comprise next association weights.

7. An associative memory according to claim 1 wherein the prior association representation comprises a prior association vector, the next association representation comprises a next association vector, the measure of the prior association representation comprises a pointer and the measure of next association representation comprises a pointer.

8. An associative memory according to claim 1 wherein the prior association representation and the measure of the prior association representation comprise segments of prior associations, and the next association representation and the measure of the next association representation comprise segments of next associations.

9. An associative memory according to claim 1 further comprising an accumulator that is connected to the associative outputs of the plurality of cells.

10. An associative memory according to claim 1 wherein the sensor input, the prior association representation, the next association representation, the associative output, the measure of the next association representation and the measure of the prior association representation are stored in corresponding registers in a respective cell.

11. An associative memory according to claim 1 wherein the processing logic is configured to operate upon a plurality of sensor inputs in a pipelined manner.

12. A computer-implemented method of determining associations using an associative memory that comprises a plurality of associative memory cells that are serially connected in a sequence from distal to proximal cells to form a linear array, the method comprising:

loading into a respective memory cell a prior association representation and a next association representation for a respective sensor input of the memory cell, wherein the sensor inputs, the prior association representations and the next association representations of the serially connected cells are arranged in a sequence from distal to proximal cells based on affinities of associations among the sensor inputs;

activating selected sensor inputs to determine associations therebetween;

responsive to the sensor input being active, sending a measure of the next association representation to an adjacent proximal cell and/or sending a measure of the prior association representation to an adjacent distal cell;

responsive to the sensor input being active, and to receipt of the measure of the next association representation from an adjacent distal cell, accumulating an associative count and/or responsive to the sensor input being active, and to receipt of the measure of the prior association representation from an adjacent proximal cell, accumulating an associative count; and

repeatedly swapping inputs, prior association representations and next association representations in the series based upon affinities of associations in the proximal and distal directions to determine the affinities of associations among the sensor inputs.

13. A method according to claim 12 further comprising:

responsive to receipt of the next association representation from an adjacent distal cell and to the prior association representation being active, decrementing the measure of the next association representation that was received and sending the measure of the next association representation that was decremented to the adjacent proximal cell and/or responsive to receipt of the measure of the prior association representation from an adjacent proximal cell and to the next association representation being active, decrementing the measure of the prior association representation that was received and sending the measure of the prior association representation that was decremented to the adjacent distal cell.

14. A method according to claim 13 further comprising:

responsive to receipt of the measure of the next association representation from an adjacent distal cell and to the prior association representation being inactive, sending the measure of the association representation that was received to the adjacent proximal cell and/or responsive to receipt of the measure of the prior association representation from an adjacent proximal cell and to the next association representation being inactive, sending the measure of the prior association representation that was received to the adjacent distal cell.

15. A method according to claim 12 wherein repeatedly swapping is followed by:

extracting bands from the series that has been swapped based on projections.

16. A method according to claim 15 wherein the projections comprise maximal projections, fixed length projections and/or longest nonmaximal projections.

17. A method according to claim 15 wherein repeatedly swapping and extracting bands are performed prior to loading and/or after loading.

18. A method according to claim 12 wherein the prior association representation and the measure of the prior association representation comprise prior association weights and the next association representation and the measure of the next association representation comprise next association weights.

19. A method according to claim 12 wherein the prior association representation comprises a prior association vector, the next association representation comprises a next association vector, the measure of the prior association representation comprises a pointer and the measure of next association representation comprises a pointer.

20. A method according to claim 12 wherein the prior association representation and the measure of the prior association representation comprise segments of prior associations and the next association representation and the measure of the next association representation comprise segments of next associations.

21. A method according to claim 12 further comprising:

accumulating the associative counts.

22. A method according to claim 12 wherein activating selected sensor inputs to determine associations therebetween is repeatedly performed on the associative memory in a pipelined manner.

23. An associative memory comprising:

a plurality of associative memory cells, a respective cell including a sensor input, a prior association representation, a next association representation and an associative output, the plurality of cells being serially connected to form a linear array, such that the sensor inputs, the prior association representations and the next association representations of the serially connected cells are arranged in a sequence from distal to proximal cells based on affinities of associations among the sensor inputs,

wherein the affinities of associations among the sensor inputs are determined by repeatedly swapping inputs, prior association representations and next association representations in the series based upon affinities of associations in the proximal and distal directions.

24. An associative memory according to claim 23 wherein the affinities of associations among the sensor inputs are further determined by extracting bands from the series that has been repeatedly swapped, based on projections.

25. An associative memory according to claim 24 wherein the projections comprise maximal projections, fixed length projections and/or longest nonmaximal projections.

26. An associative memory according to claim 23 wherein the prior association representation and the measure of the prior association representation comprise prior association weights, and the next association representation and the measure of the next association representation comprise next association weights.

27. An associative memory according to claim 23 wherein the prior association representation comprises a prior association vector, the next association representation comprises a next association vector, the measure of the prior association representation comprises a pointer and the measure of next association representation comprises a pointer.

28. An associative memory according to claim 23 wherein the prior association representation and the measure of the prior association representation comprise segments of prior associations, and the next association representation and the measure of the next association representation comprise segments of next associations.

29. A method of determining associations using an associative memory that comprises a plurality of associative memory cells that are serially connected in a sequence from distal to proximal memory cells to form a linear array of a series of memory cells, the method comprising:

loading into a respective memory cell a prior association representation and a next association representation for a respective sensor input of the memory cell wherein the sensor inputs, the prior association representations and the next association representations of the serially connected cells are arranged in a sequence from distal to proximal cells based on affinities of associations among the sensor inputs;

activating selected sensor inputs to determine associations therebetween; and

repeatedly swapping inputs, prior association representations and next association representations in the series of memory cells based upon affinities of associations in the proximal and distal directions to determine the affinities of associations among ones of the sensor inputs.

30. A method according to claim 29 wherein repeatedly swapping is followed by:

extracting bands from the inputs, prior association representations and next association representations in the series of memory cells that have been swapped based on projections.

31. A method according to claim 30 wherein the projections comprise maximal projections, fixed length projections and/or longest nonmaximal projections.

32. A method according to claim 30 wherein repeatedly swapping and extracting bands are performed prior to loading and/or after loading.

33. A method according to claim 29 wherein the prior association representation and the measure of the prior association representation comprise prior association weights and the next association representation and the measure of the next association representation comprise next association weights.

34. A method according to claim 29 wherein the prior association representation comprises a prior association vector, the next association representation comprises a next association vector, the measure of the prior association representation comprises a pointer and the measure of next association representation comprises a pointer.

35. A method according to claim 29 wherein the prior association representation and the measure of the prior association representation comprise segments of prior associations and the next association representation and the measure of the next association representations comprise segments of next associations.