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

点击翻译按钮获取中文摘要

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.