Ternary Content Addressable Memory or in short TCAM is a special type of memory that can execute a certain set of operations in parallel on all of its words. Because ofpower consumption and relatively small storage capacity, it has only been used in special environments. Over the past few years its cost has been reduced and its storage capacity has increased signifi cantly and these exponential trends are continuing. Hence it can be used in more general environments for larger problems. In this research we study how to exploit its computational power in order to speed up fundamental problems and needless to say that we barely scratched the surface. The main problems that has been addressed in our research are namely Boolean matrix multiplication, approximate subset queries using bloomfilters, Fixed universe priority queues and network flow classi cation. For Boolean matrix multiplication our simple algorithm has a run time of O (d(N^2)/w) where N is thesize of the square matrices, w is the number of bits in each word of TCAM and d is themaximum number of ones in a row of one of the matrices. For theFixed universe priorityqueue problems we propose two data structures one with constant time complexity andspace of O((1/ε)n(U^ε)) and the other one in linear space and amortized time complexity ofO((lg lg U)/(lg lg lg U)) which beats the best possible data structure in the RAM model namely Y-fast trees. Considering each word of TCAM as a bloomfilter, we modify the hash functions of the bloomfilter and propose a data structure which can use the information capacity of each word of TCAM more efi ciently by using the co-occurrence probability of possible members. Andfinally in the last chapter we propose a novel technique for network flow classi fication using TCAM.
【 预 览 】
附件列表
Files
Size
Format
View
Exploiting the Computational Power of Ternary Content Addressable Memory
PDF
download
878987797
028-85220240
