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

内容可寻址存储器（CAM）是一种关联查找存储器，包含一组固定宽度的单元，可以保存任意数据位。 CAM将搜索关键字作为查询，并返回包含该关键字的条目的地址（如果有的话）。在三进制CAM（TCAM）中，每个数据位能够存储三种状态之一：0、1或 *，其中 * 与0和1都匹配。这是一个功能强大的原语，在高性能网络路由器和交换机中有很多用途。本项目将开发使用TCAM实现复杂的随机数据结构的一般技术，并将其用于多个数据密集型应用程序。与随机存取存储器（RAM）相比，TCAM消耗更多的功率（大约20倍）。因此，重要的是要研究的应用程序的改进是几个数量级，从而在整体上降低功耗相比，传统的软件解决方案，只使用RAM;这将是本研究的指导原则。TCAM的全部潜力尚未实现，由于缺乏复杂的应用。该项目将帮助这项技术最大限度地发挥其潜力。这项研究预计将对多个数据密集型应用产生影响，如网络流处理，文档/图像相似性，备份和WAN压缩。此外，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.