COP - ASPRO, CAM

ASPRO, CAM and Find


The goal is to introduce the COP designer to one of the 4 or 5 major structure of computing (see note 1): Content Addressable Memory (CAM). We also briefly mention the very large field of ASociative PROcessors (ASPRO). Behind all that, there is an interesting parallel between CAM and the FIND  instruction.

(note 1) with arithmetic, bit field logic and lookup table.

Introduction

A common problem with Matlab is that IF does not work on vector. This should not be surprising since it fits the DSP ISA principle where we define predicated instructions to replace branching.

• DSP ISA
• IF corresponds to a change of program flow and impacts the very early fetch.
• Predication corresponds to two execution "in parallel" with a final mux to make the right choice. The hardware performance impact is negligable.
•  MATLAB
• IF  can be seen as a change of program flow and it  is difficult to visualize it on vector.
• Predication is implemented with logicals.

Example 

y=(rbit==0)?x+7:x;

in Matlab

y=x;

if rbit==0 , y= x+7;

will work only on scalar. The brute force solution is to create a for loop (like in C).

But if we use logicals

cc= eq(rbit,0)

y(cc)=x(cc)+7;

y(~cc)=x(~cc);

This looks much more like predicated DSP code and it is works on vector.

Now, the funny thing is while it is perfect legal, the standard Matlab style is to use the Find instruction.

FIND

Without going into the details of the usage of Find (see Mathworks) , the implementation of Find as a COP  or as C code is a heck of a challenge. But, as a first order, its structure is bases on a CAM.

CAM
CAM  have been around for a long time and had(?) their hour of glory in Networking chips. In DSP a CAM is a natural for everything 'RECOG' (speech recognition, pattern recognition, etc..).

ASPRO

It is the generalization of the CAM concept to general purpose computing. ASPRO is as old as the world exists and a large body of references is available.

References found in my 2004 garbage can

1. Florin baboescu etc.."hardware implementation of a tree-based IP lookup Algorithm",  ST Microelectronics, Year YYYY
2. Kohonen 1980 .. a book
3. Asanovic and chapman 1990
4. Asanovic"the Space chip"    keyword: PADMAVATI
5. Cypress Ternary CAM
6. Djamshid tavagarian, "flag-oriented parallel Associative Architectures and Applications"  IEEE Nov 1994
7. NeoMagic "the technology of APA" ..this one beats them all! Genius or monumental stupidity? still open after all these years. 
1. there were at least 2 challenges : 
1. software required double optimization and porting
2. iterative algorithm were impossible.We work on that one!
8. Romain Saha MOSAIC " CAM speeds up lossless compression"  EDN 09.29.03
1. see also www.commsdesign.com circa 2003
• Good try romain!
9. ALTERA A.N. "Implementing High Speed Search Applis with Altera CAM" July 2001, A.N 119
10. GEC Plessey "PNC1480 LAN CAM" 
• gosh!

FURTHER : INTELLIGENT MEMORIES seen by COMPUTER DESIGN MAY 1998 !!

• Matrix transposing and Multiplying
• Wavelets transforms
• Lossy and lossless compression
• Cryptography
• Graphics Accelerator

FURTHER: replacing time by space

1. Using GBytes memory to store all possible outcomes. 
• Not your average chip.