| Rapid data growth nowadays makes it more critical to reduce search time to improve the performance of search-intensive applications. However, huge data size makes it more difficult to efficiently perform search operations. Representative conventional approaches to reduce search time, such as CAM and in-memory databases, are no longer efficient because of the data explosion: CMOS-based CAM has low capacity which cannot be increased through CMOS scaling, and in-memory databases have performance degradation as data size increases. As a result, we have to exploit emerging nanotechnologies to accelerate search.;Among emerging nanotechnologies, memristors have become promising candidates to build storage structures because of high capacity, short switching time and low power consumption. However, the benefit we can obtain from these storage structures is limited by low endurance of memristors. In order to utilize the computation ability of memristors and deal with the endurance problem, we explore the design space of memristor-based storage structures.;We first propose MemCAM/MemTCAM, a configurable memristor-based CAM/TCAM design, in which we use memristors as both memory latches and logic gates. Computation ability of memristors makes it possible to perform range search and high density of memristors provides an opportunity to build MemCAM/MemTCAM with large capacity and small area. We use SPICE to model the memristor and analyze power and performance at different temperatures. The results show that it is feasible to build MemCAM and MemTCAM which have high capacity and can reduce total search time and energy consumption for search-intensive applications with huge data size.;We then propose four hybrid memristor-based storage structures, Hash-CAM, T-tree-CAM, TB+-tree, and TB+-tree-CAM, to solve the endurance problem. We use an analytical model to evaluate and compare the performance and lifetime of two software-implemented memory-based T-trees and these four hybrid storage structures. The results show that hybrid storage structures can utilize range search abilities, achieve better performance than memory-based T-trees, and improve lifetime from minutes to longer than 60 years. Furthermore, TB+-tree-CAM, a hybrid memristor-based storage structure combining T-tree, B+-tree and CAM, manages to balance between performance and lifetime and can outperform other storage structures when taking both performance and lifetime into consideration. |
