Design Feature: May 9, 1996

The latest generation of content-addressable memories (CAMs) makes it possible to handle list searches and data translation as embedded functions within systems. The combination of a CAM and a state machine creates an economical controller for real-time processes that need to perform look-ups, data translations, and entry maintenance in sparsely populated tables—ones with few entries compared to the address space required for direct look-up.

By simplifying many of the tasks required to deal with lists and tables of data, a CAM can offer you one of two possible benefits. You can simplify the controller by switching to a lower cost processor or a state machine. Or, you can dedicate the additional processing power that the CAM provides to additional features and functions. In either case, more processing power is available to an embedded controller at a lower cost.

A CAM is a hardware implementation of associative processing. Associative processing manipulates data based on matching, or associating, an input value with other values stored in an array. Associative-processing hardware incorporates a limited amount of computational capability at each memory location and allows you to examine an entire memory array at once. CAMs combine these functions with a control structure to perform associative processing.

This type of processing stands in contrast to today's predominant computational architecture: the Von Neumann engine. This architecture relies on address-based memories to store instructions and data. A few computational elements (most often one) sequentially process the instructions, operating on a single element of data at a time. Parallel-computing systems collect many of these processors, either operating together or independently, into large arrays.

CAMs implement associative processing

Associative-processing theory has been around for a long time. However, the first large CAMs were expensive, and only a few specialized applications could effectively use small CAMs. Now, larger, general-purpose CAMs allow you to use associative processing to solve a wider variety of problems. Several vendors make devices that are part of this latest generation of CAMs. Although some differences exist among vendors in array organization, interface specifics, and product variety, many similarities among offerings also exist. The following application examples are based on MUSIC Semiconductors' MU9C1480 LANCAM.

A CAM compares an input value, the comparand, to all the associative data stored in the memory array at once. The output from a CAM can be either a flag that indicates one or more matches or associated data that is related in some way to the matched values.

The external connections to this type of memory device are simple. A data bus provides command inputs (Table 1) and data I/O. Output flags indicate the comparison results and indicate when the memory is full. Flag inputs allow you to connect multiple devices in a daisy chain without external logic, thereby expanding the number of words in the memory array. Table 2 lists the CAM memory and data locations.

Note that the CAM logic symbol has no external address lines (Figure 1). In a CAM, most memory accesses are associative, that is, based on the contents of the memory, so external address lines are unnecessary for most operations. An internal address register, accessible through the command structure of the device, allows address-based random access of the CAM array when necessary. Two mask registers provide bit-level control of the comparand register for compare operations, allowing comparisons on a limited number of bits for special situations. You can also use the mask registers to update specific memory-array bits during moves from the comparand register.

Storing the associative data within the CAM device minimizes the component count in an embedded system. However, if the total number of associative and associated bits exceeds the width of the CAM, you can store the associated data in an external RAM (Figure 2).

CAMs fit into embedded systems

You commonly find CAMs in two types of applications: data filters and data translators. Data filters search a table or list and generate a flag that indicates whether the filter finds the input comparand. An example of a data filter is an address filter in network bridges, routers, and firewalls. Data translators search a table and output data associated with the comparand. Examples are switches (header translation), caches (main storage to cache location translation), and compression (symbol translation).

Various boxes accompanying this article show typical instruction routines for a number of these applications, including network bridges, ATM switches, disk caches, branch tables, and compression. Also see Table 3, which shows the corresponding CAM cycle keys. By studying these routines, you can see how a CAM's associative properties simplify not only the search sequence, but also the maintenance of a data list. The use of a CAM reduces these tasks to operations that simple state machines can easily handle.

As one example, the cycle sequence in Figure 3 shows how the CAM architecture simplifies the control of a 48-bit comparison, a read of the match address, and a read of 16 bits of associated data. (Assume that the CAM has a 16-bit external bus and a 64-bit-wide memory array. Four 16-bit segments, numbered 0 through 3, access the memory array.) When you initialize the device, the memory array comprises 48 bits (segments 1, 2, and 3) of CAM and 16 bits (segment 0) of RAM. Data writes go to segments 1, 2, and 3 of the comparand register; data reads come from segment 0 of the highest priority matching location.

In Figure 3, the first three cycles write the data to the three segments of the comparand register and trigger a comparison. A command-read cycle gets the match address from the status register, which is the default source for command-read cycles. A single read cycle fetches the associated data from segment 0 of the highest priority matching location. Because the device's configuration is programmable, all five cycles deliver and fetch useful data without any additional overhead. This efficiency is very important in time-critical processes.

Searches are only part of the challenge of working with lists of data, however. Many embedded applications must also maintain the list over time by adding or learning new entries and deleting or purging obsolete ones. The associative-processing power of a CAM is well-suited to this task. New entries in the data list typically load into the next empty location in the CAM's memory array. A related concept is learning: After a comparison that finds no match, a single command (MOV NF,CR,V) moves data from the comparand register to the next free address. Because a typical list comprises unique entries with equal priority, the CAM can store a new entry anywhere in the memory array. Thus, you can construct an efficient sequence that adds data to the list by taking advantage of a CAM's ability to associatively access the next empty location.

Sometimes, you may want to update an entry that exists in the CAM's memory array, such as a time stamp in a segment of the comparand. Either the CAM/RAM configuration or a mask register usually masks out the time-stamp segment from the normal compare operations. When the CAM finds a match for the unmasked portion of the comparand, a single instruction (MOV HM,CR,MR1) moves only the bits indicated by mask register 1 to the highest priority matching location from the comparand register, updating only the time stamp in the process.

When it is time to delete or purge one or more entries from the data list, the CAM can use associative locations Highest Priority Match or All Matching. To perform the purge, the comparand register loads the entry to be removed, which forces a compare. Then, a single instruction (VBC ALM,E) changes the validity bits at all the matching locations to mark them as empty, thus removing them from compare operations and making them available for new entries as the next free location.

CAMs make hash of the alternatives

Choosing between CAMs and the alternatives requires making trade-offs between processing power and speed. Linear and binary searches are one alternative, but they require extensive shuffling of the data list when you add or delete entries. To add to a sorted data list, every entry from the end of the table to the location of the new entry must be read and then written into the next location. Removing an entry requires the same process in reverse. Also, search times depend on the size of the data list.

Another alternative is a hash table. Hash tables are the software implementation of associative processing and are fairly efficient at making the table smaller. However, hash tables require an increased level of computing power to quickly calculate the hash-table key. List maintenance, which comprises calculating the hash key for the new entry and placing the data at this location, is fairly straightforward until a new entry maps to an already-used location, causing a collision. Resolving collisions involves performing additional hash-key calculations until the data finds an open location in the hash table. Collisions cause nondeterministic hash-table search times. That is, the compare time may vary based on the number of collisions that occur when constructing the table.

These alternatives are cumbersome in embedded applications, requiring processing power and long sequences of instructions that are unnecessary with a CAM. In an embedded system, the simple control interface makes it easy for a state machine to control the CAM's operation (Figure 4). Also, a CAM's powerful associative operations reduce the number of instructions required for any application, making it possible for simple state machines to control otherwise-complex operations.

When should you, as a designer, consider using CAMs? A CAM costs more than SRAM, because a CAM cell requires more transistors to build. However, a CAM's advantages outweigh the additional cost compared to other alternatives for the following conditions:

• Sparsely populated tables: The best CAM applications expect far fewer entries in the table than the address space required for direct look-up. For example, direct look-up of a 32-bit comparand would require 2³², or 4 Tera-entries; 48 bits require 2⁴⁸, or 256 Tera-entries. A network bridge that requires 48 bits for source and destination addresses never reaches 2⁴⁸ nodes on the network at once, so CAMs are a way to reduce the look-up-table size.
• Wide comparands: CAMs easily handle comparands up to the width of the memory array, which is wider than the internal architectures of most embedded applications' processors and controllers. Wide comparands may also be a sign of a sparsely populated table.
• Speed: CAMs quickly return match indications. CAMs also work well with state machines. A CAM and a state machine can process fast data streams in real time.
• Deterministic compares: A CAM finds all matching entries in a single comparison. A hash-table collision causes recalculation of the key to find a unique entry, resulting in additional time or timing uncertainty that many high-speed applications cannot tolerate.
• Random data sequences: The sequence of data in the array does not matter. When a new entry must be added to the table, it is not necessary to sort, rekey, or check for collisions with previous entries.
• Multiple searches on the same data: Applications that don't change most entries from compare to compare are candidates for a CAM-based solution. On the other hand, if the CAM's memory array must be loaded or replaced with a new table before most comparisons, the time required to load the CAM's memory array quickly erases the speed advantage of a CAM-based solution. (It is possible, however, to use other techniques, such as tagging entries with a code to identify separate tables stored in one or more CAMs, or storing each table in its own CAM.)
• Frequent table updates: CAMs are well-suited to applications that frequently add or delete a few entries while much of the table remains intact. A CAM's associative properties simplify table maintenance, so that the process of adding or purging entries reduces to a single instruction or two. The stable data maximizes the bus transactions dedicated to compare operations.
• Simplified table maintenance: A single CAM instruction can learn a new entry or purge old data. A CAM's powerful associative instructions lower the processing power required to control the CAM, so that simple state machines can handle table maintenance. The simple, short maintenance instructions make it possible to perform list-maintenance operations quickly between compares, even in a high-speed data stream.
• Dedicated storage: Because data tables always reside in the CAM, the data is always ready for compare operations. In contrast, processors with a data cache may have to retrieve the table from the main processor memory or a disk if the data has not been accessed for a while and has been flushed from the cache. A dedicated storage area avoids these latency delays and can simplify the architecture of many embedded systems.

Your application need not meet all of these conditions for you to choose a CAM. At times, only one of these items may justify the use of a CAM. However, most suitable applications can take advantage of several CAM and associative-processing attributes.

Author's biography

Tom Weldon is director of product marketing and applications at MUSIC Semiconductors (Colorado Springs, CO), where he has worked for six years. He holds a BSE from Harvey Mudd College (Claremont, CA).