A Segmented Bloom Filter Algorithm For Efficient Predictors

dc.creatorBreternitz M.
dc.creatorLoh G.H.
dc.creatorBlack B.
dc.creatorRupley J.
dc.creatorSassone P.G.
dc.creatorAttrot W.
dc.creatorWu Y.
dc.date2008
dc.date2015-06-30T19:14:33Z
dc.date2015-11-26T14:40:09Z
dc.date2015-06-30T19:14:33Z
dc.date2015-11-26T14:40:09Z
dc.date.accessioned2018-03-28T21:46:16Z
dc.date.available2018-03-28T21:46:16Z
dc.identifier
dc.identifierProceedings - Symposium On Computer Architecture And High Performance Computing. , v. , n. , p. 123 - 130, 2008.
dc.identifier15506533
dc.identifier10.1109/SBAC-PAD.2008.24
dc.identifierhttp://www.scopus.com/inward/record.url?eid=2-s2.0-58049167634&partnerID=40&md5=75efb7a90dcc87f864e0631e79696e4d
dc.identifierhttp://www.repositorio.unicamp.br/handle/REPOSIP/105391
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/105391
dc.identifier2-s2.0-58049167634
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1250295
dc.descriptionBloom 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.
dc.description
dc.description
dc.description123
dc.description130
dc.descriptionThe 1st JILP Championship Branch Prediction Competition (CBP-1), , http://www.jilp.org/cbp
dc.descriptionBloom, B.H., Space/Time Tradeoffs in Hash Coding with Allowable Errors (1970) Communications of the Association for Computing Machinery, 13 (7), pp. 422-426. , July
dc.descriptionBratbergsengen, K., Hashing Methods and Relational Algebra Operations (1984) Proc. of 10th Int. Conf. on Very Large Databases, pp. 323-333. , August
dc.descriptionDean, J., Ghemawar, S., MapReduce: Simplified Data Processing on Large Clusters (2004) OSDI 2004, pp. 137-150. , Usenix Assoc
dc.descriptionErnst, D., Austin, T., Efficient Dynamic Scheduling Through Tag Elimination (2002) Proc. of 29th Int. Symp. on Comp. Arch, pp. 37-45. , Anchorage, AK, USA, May
dc.descriptionFan, 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, August
dc.descriptionFields, 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, June
dc.descriptionGuthaus, 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, December
dc.descriptionJacobson, 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, December
dc.descriptionLarson, 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, November
dc.descriptionLee, 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, December
dc.descriptionLoh, G.H., Exploiting Data-Width Locality to Increase Superscalar Execution Bandwidth (2002) Proc. of 35th Int. Symp. on Microarchitecture, pp. 395-405. , Istanbul, Turkey, November
dc.descriptionLoh, G.H., Deconstructing the Frankenpredictor for Implementable Branch Predictors (2005) Journal of Instruction Level Parallelism, 7, pp. 1-10
dc.descriptionMcFarling, S., (1993) Combining Branch Predictors, p. 36. , TN, Compaq Computer Corporation Western Research Laboratory, June
dc.descriptionMichaud, P., PPM-like, A., Tag-Based Predictor (2005) Journal of Instruction Level Parallelism, 7, pp. 1-10
dc.descriptionMichaud, 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. , June
dc.descriptionPeir, 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. , June
dc.descriptionPerelman, 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. , September
dc.descriptionRhea, 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. , June
dc.descriptionRoth, A., Store Vulnerability Window (SVW): Re-Execution Filtering for Enhanced Load Optimization (2005) Proc. of 32nd Int. Symp. on Comp. Arch, pp. 458-468. , June
dc.descriptionSanchez, 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, December
dc.descriptionSethumadhavan, 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. , May
dc.descriptionSeznec, A., Analysis of the O-GEometric History Length Branch Predictor (2005) Proc. of 32nd Int. Symp. on Comp. Arch, , Madison, WI, USA, June
dc.descriptionYoaz, 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, June
dc.languageen
dc.publisher
dc.relationProceedings - Symposium on Computer Architecture and High Performance Computing
dc.rightsfechado
dc.sourceScopus
dc.titleA Segmented Bloom Filter Algorithm For Efficient Predictors
dc.typeActas de congresos


Este ítem pertenece a la siguiente institución