A Segmented Bloom Filter Algorithm For Efficient Predictors

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. © 2008 IEEE.123130The 1st JILP Championship Branch Prediction Competition (CBP-1), , http://www.jilp.org/cbpBloom, B.H., Space/Time Tradeoffs in Hash Coding with Allowable Errors (1970) Communications of the Association for Computing Machinery, 13 (7), pp. 422-426. , JulyBratbergsengen, K., Hashing Methods and Relational Algebra Operations (1984) Proc. of 10th Int. Conf. on Very Large Databases, pp. 323-333. , AugustDean, J., Ghemawar, S., MapReduce: Simplified Data Processing on Large Clusters (2004) OSDI 2004, pp. 137-150. , Usenix AssocErnst, D., Austin, T., Efficient Dynamic Scheduling Through Tag Elimination (2002) Proc. of 29th Int. Symp. on Comp. Arch, pp. 37-45. , Anchorage, AK, USA, MayFan, L., Cao, P., Almeida, J.M., Broder, A.Z., Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol (1998) Proc. of ACM SIG-COMM Conf. on Applications, Technologies, Architectures and Protocols for Computer Communication, pp. 254-265. , Vancouver, Canada, AugustFields, B., Rubin, S., Bodík, R., Focusing Processor Policies via Critical-Path Prediction (2001) Proc. of 28th Int. Symp. on Comp. Arch, pp. 74-85. , Göteborg, Sweden, JuneGuthaus, M.R., Ringenberg, J.S., Ernst, D., Austin, T.M., Mudge, T., Brown, R.B., MiBench: A Free, Commerically Representative Embedded Benchmark Suite (2001) Proc. of 4th Workshop on Workload Characterization, pp. 83-94. , Austin, TX, USA, DecemberJacobson, E., Rotenberg, E., Smith, J.E., Assigning Confidence to Conditional Branch Predictions (1996) Proc. of 29th Int. Symp. on Microarchitecture, pp. 142-152. , Paris, France, DecemberLarson, E., Chatterjee, S., Austin, T., MASE: A Novel Infrastructure for Detailed Microarchitectural Modeling (2001) Proc. of 2001 Int. Symp. on Performance Analysis of Systems and Software, pp. 1-9. , Tucson, AZ, USA, NovemberLee, C., Potkonjak, M., Mangione-Smith, W.H., MediaBench: A Tool for Evaluating and Synthesizing Multimedia and Communication Systems (1997) Proc. of 30th Int. Symp. on Microarchitecture, pp. 330-335. , Research Triangle Park, NC, USA, DecemberLoh, G.H., Exploiting Data-Width Locality to Increase Superscalar Execution Bandwidth (2002) Proc. of 35th Int. Symp. on Microarchitecture, pp. 395-405. , Istanbul, Turkey, NovemberLoh, G.H., Deconstructing the Frankenpredictor for Implementable Branch Predictors (2005) Journal of Instruction Level Parallelism, 7, pp. 1-10McFarling, S., (1993) Combining Branch Predictors, p. 36. , TN, Compaq Computer Corporation Western Research Laboratory, JuneMichaud, P., PPM-like, A., Tag-Based Predictor (2005) Journal of Instruction Level Parallelism, 7, pp. 1-10Michaud, P., Seznec, A., Uhlig, R., Trading Conflict and Capacity Aliasing in Conditional Branch Predictors (1997) Proc. of 24th Int. Symp. on Comp. Arch, pp. 292-303. , JunePeir, J.-K., Lai, S.-C., Lu, S.-L., Stark, J., Lai, K., Bloom Filtering Cache Misses for Accurate Data Speculation and Prefetching (2002) Proc. of 16th Int. Conf. on Supercomputing, pp. 189-198. , JunePerelman, E., Hamerly, G., Calder, B., Picking Statistically Valid and Early Simulation Points (2004) Proc. of 2003 Int. Conf. on Par. Arch. and Comp. Techniques, pp. 244-255. , SeptemberRhea, S.C., Kubiatowicz, J., Probabilistic Location and Routing (2002) Proc. of 21st Annual Joint Conf. of the IEEE Computer and Communications Societies (INFOCOM), pp. 1248-1257. , JuneRoth, A., Store Vulnerability Window (SVW): Re-Execution Filtering for Enhanced Load Optimization (2005) Proc. of 32nd Int. Symp. on Comp. Arch, pp. 458-468. , JuneSanchez, D., Yen, L., Hill, M.D., Sankaralingam, K., Implementing Signatures for Transactional Memory (2007) Proc. of 40th Int. Symp. on Microarchitecture, pp. 123-133. , Chicago, IL, DecemberSethumadhavan, S., Desikan, R., Burger, D., Moore, C.R., Keckler, S.W., Scalable Hardware Memory Disambiguation for High ILP Processors (2003) Proc. of 36th Int. Symp. on Microarchitecture, pp. 118-127. , MaySeznec, A., Analysis of the O-GEometric History Length Branch Predictor (2005) Proc. of 32nd Int. Symp. on Comp. Arch, , Madison, WI, USA, JuneYoaz, A., Erez, M., Ronen, R., Jourdan, S., Speculation Techniques for Improving Load Related Instruction Scheduling (1999) Proc. of 26th Int. Symp. on Comp. Arch, pp. 42-53. , Atlanta, GA, USA, Jun