2008 20th International Symposium on Computer Architecture and High Performance Computing A Segmented Bloom Filter Algorithm for Efficient Predictors October 29-November 01 ISBN: 978-0-7695-3423-7
Bloom Filters are a technique to reduce the effects of conflicts/interference in hash table-like structures. Conventional hash tables store information in a single location which is susceptible to destructive interference through hash conflicts. A Bloom Filter uses multiple hash functions to store information in several locations, and recombines the information through some voting mechanism. Many microarchitectural predictors use simple single-index hash tables to make binary 0/1 predictions, and Bloom Filters help improve predictor accuracy. However, implementing a true Bloom Filter requires k hash functions, which in turn implies a k-ported hash table, or k sequential accesses. Unfortunately,the area of a hardware table increases quadratically with the port count, increasing costs of area, latency and power consumption. We propose a simple but elegant modification to the Bloom Filter algorithm that uses banking combined with special hash functions that guarantee all hash indexes fall into non-conflicting banks. We evaluate several applications of our Banked Bloom Filter (BBF) prediction in processors: BBF branch prediction, BBF load hit/miss prediction, and BBF last-tag prediction. We show that BBF predictors can provide accurate predictions with substantially less cost than previous techniques.
Index Terms:
Bloom Filters, predictors, speculation, banking
Citation:
M. Breternitz, Gabriel H. Loh, Bryan Black, Jeffrey Rupley, Peter G. Sassone, Wesley Attrot, Youfeng Wu, "A Segmented Bloom Filter Algorithm for Efficient Predictors," sbac-pad, pp.123-130, 2008 20th International Symposium on Computer Architecture and High Performance Computing, 2008 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||