DC: Small: The Use of Ternary Associative Memories in Data Intensive Computing

内容可寻址存储器(CAM)是包含一组可容纳任意数据位的固定宽度单元的关联查找存储器。CAM将搜索关键字作为查询，并返回包含该关键字的条目的地址(如果有的话)。在三值CAM(TCAM)中，每个数据位能够存储三种状态之一：0、1或*，其中a*同时匹配0和1。这是一种功能强大的原语，已在高性能网络路由器和交换机中得到广泛应用。该项目将开发使用TCAM实现复杂的随机化数据结构的通用技术，并将其用于多种数据密集型应用。与随机存取存储器(RAM)相比，TCAM的功耗要高得多(约20倍)。因此，重要的是研究那些改进了几个数量级的应用程序，与只使用RAM的传统软件解决方案相比，总体上降低了功耗；这将是本研究的指导原则。由于缺乏复杂的应用程序，TCAMS的全部潜力尚未实现。该项目将帮助这项技术最大限度地发挥其潜力。这项研究预计将对多种数据密集型应用产生影响，如网络流处理、文档/图像相似性、备份和广域网压缩。此外，PI还将培训研究生并开发一个新课程，该课程将结合这项研究的结果描述现实生活中的相似性搜索、流处理和模式匹配算法。

A Content Addressable Memory (CAM) is an associative lookup memory containing a set of fixed-width cells that can hold arbitrary data bits. A CAM takes a search key as a query, and returns the address of the entry that contains the key, if any. In a Ternary CAM (TCAM), each data bit is capable of storing one of three states: 0, 1, or *, where a * matches both 0 and 1. This is a powerful primitive, and has found much use in high performance network routers and switches. This project will develop general techniques for using TCAMs to implement sophisticated randomized data structures, and use them in multiple data intensive applications. TCAMs consume a lot more power (around 20 times) compared to Random Access Memories (RAMs). Hence, it is important to study applications where the improvements are of several orders of magnitude, resulting in an overall decrease in power consumption compared to traditional software solutions that only use RAM; this will be a guiding principle of this research.The full potential of TCAMs has not been realized due to a lack of sophisticated applications. This project will help this technology maximize its potential. This research is expected to have impact in multiple data-intensive applications such as network flow processing, document/image-similarity, backups, and WAN compression. Also, the PIs will train graduate students and develop a new class which will describe real-life algorithms for similarity search, stream processing, and pattern matching, incorporating results from this research.