Alloyed Branch History: Combining Global and Local Branch History for Robust Performance

Lu, Zhijian; Lach, John; Stan, Mircea R.; Skadron, Kevin
April 2003
International Journal of Parallel Programming;Apr2003, Vol. 31 Issue 2, p137
Academic Journal
This paper introduces alloyed prediction, a new hardware-based two-level branch predictor organization that combines global and local history in the same structure, combining the advantages of current two-level predictors with those of hybrid predictors. The alloyed organization is motivated by measurements showing that wrong-history mispredictions are even more important than conflict-induced mispredictions. Wrong-history mispredictions arise because current two-level, history-based predictors provide only global or only local history. The contribution of wrong history to the overall misprediction rate is substantial because most programs have some branches that require global history and others that require local history. This paper explores several ways to implement alloyed prediction, including the previously proposed bi-mode organization. Simulations show that mshare is the best alloyed organization among those we examine, and that mshare gives reliably good prediction compared to bimodal (�two-bit�), two-level, and hybrid predictors. The robust performance of alloying across a range of predictor sizes stems from its ability to attack wrong-history mispredictions at even very small sizes without subdividing the branch prediction hardware into smaller and less effective components.


Related Articles

  • Guest Editor's Introduction. Ayguade, Eduard // International Journal of Parallel Programming;Jun2003, Vol. 31 Issue 3, p181 

    This article introduces the articles in volume 31, number 3 of the "International Journal of Parallel Programming". The volume is devoted to a collection of papers on the parallel programming API OpenMP. The papers have been selected from the presentations at the second International Workshop on...

  • Introduction. Evripidou, Paraskevas // International Journal of Parallel Programming;Feb2001, Vol. 29 Issue 1, p1 

    Presents an introduction to articles on parallel programming.

  • Parallel programming in Grid: Using MPI. Heli Xu; Guixin Wu // Proceedings of the International Symposium on Electronic Commerc;Jun2010, p136 

    Compared with the traditional parallel technologies, parallel computing comes true in the Grid, which has a great advantage. According to features of Message Passing Interface (MPI), put forward applying methods of MPI in the grid, include MPI application models based on grid, theories of grid...

  • Restricted admission control in view-oriented transactional memory. Leung, Kai-Cheung; Chen, Yawen; Huang, Zhiyi // Journal of Supercomputing;Feb2013, Vol. 63 Issue 2, p348 

    This paper proposes a Restricted Admission Control (RAC) scheme for View-Oriented Transactional Memory. The scheme can control the number of threads concurrently accessing a view in order to reduce the number of aborts of transactions. The RAC scheme has the merits of both the locking mechanism...

  • Experiences with Sweep3D implementations in Co-array Fortran. Coarfa, Cristian; Dotsenko, Yuri; Mellor-Crummey, John // Journal of Supercomputing;May2006, Vol. 36 Issue 2, p101 

    As part of the recent focus on increasing the productivity of parallel application developers, Co-array Fortran (CAF) has emerged as an appealing alternative to the Message Passing Interface (MPI). CAF belongs to the family of global address space parallel programming languages; such languages...

  • EasyFJP: Providing Hybrid Parallelism as a Concern for Divide and Conquer Java Applications. Mateos, Cristian; Zunino, Alejandro; Hirsch, Matías // Computer Science & Information Systems;Jun2013, Vol. 10 Issue 3, p1129 

    Because of the increasing availability of multi-core machines, clusters, Grids, and combinations of these there is now plenty of computational power, but today's programmers are not fully prepared to exploit parallelism. In particular, Java has helped in handling the heterogeneity of such...

  • Experimental and Theoretical Speedup Prediction of MPI-Based Applications. Elnashar, Alaa; Aljahdali, Sultan // Computer Science & Information Systems;Jun2013, Vol. 10 Issue 3, p1247 

    Prediction of speedup obtained from parallelization plays an important role in converting serial applications into parallel ones. Several parameters affect the execution time of an application. In this paper we experimentally and theoretically study the effect of some of these parameters on the...

  • Performance Comparison of Parallel Programming Environments for Implementing AIAC Algorithms. Bahi, Jacques; Contassot-Vivier, Sylvain; Couturier, Raphaël // Journal of Supercomputing;Mar2006, Vol. 35 Issue 3, p227 

    AIAC algorithms (Asynchronous Iterations Asynchronous Communications) are a particular class of parallel iterative algorithms. Their asynchronous nature makes them more efficient than their synchronous counterparts in numerous cases as has already been shown in previous works. The first goal of...

  • The Join Algorithms on a Shared-Memory Multiprocessor Database Machine. Qadah, Ghassan Z.; Irani, Keki B. // IEEE Transactions on Software Engineering;Nov88, Vol. 14 Issue 11, p1668 

    This paper develops and presents a large set of parallel algorithms for implementing the join operation on a shared-memory multiprocessor database machine. The development of these algorithms follows a structured approach. First, the major steps involved in the processing of the join operation...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics