Predicting multiple streams per cycle

Predicting Multiple Streams per Cycle Oliverio J. Santana, Alex Ramirez, and Mateo Valero Departament d’Arquitectura de Computadors Universitat Polit`ecnica de Catalunya Barcelona, Spain email:{osantana,aramirez,mateo}@ac.upc.edu Abstract The next stream predictor is an accurate branch predictor that provides stream level sequencing. Every stream prediction contains a full stream of instructions, that is, a sequence of instructions from the target of a taken branch to the next taken branch, potentially containing multiple basic blocks. The long size of instruction streams makes it possible for the stream predictor to provide high fetch bandwidth and to tolerate the prediction table access latency. Therefore, an excellent way for improving the behavior of the next stream predictor is to enlarge instruction streams. In this paper, we provide a comprehensive analysis of dynamic instruction streams, showing that focusing on particular kinds of stream is not a good strategy due to Amdahl’s law. Consequently, we propose the multiple stream predictor, a novel mechanism that deals with all kinds of streams by combining single streams into long virtual streams. We show that our multiple stream predictor is able to tolerate the prediction table access latency without requiring the complexity caused by additional hardware mechanisms like prediction overriding, also reducing the overall branch predictor energy consumption. 1 Introduction High performance superscalar processors require high fetch bandwidth to exploit all the available instructionlevel parallelism. The development of accurate branch prediction mechanisms has provided important improvements in the fetch engine performance. However, it has also increased the fetch architecture complexity. Our approach to achieve high fetch bandwidth, while maintaining the complexity under control, is the stream fetch engine [12, 17]. This fetch engine design is based on the next stream predictor, an accurate branch prediction mechanism that uses instruction streams as the basic prediction unit. We call stream to a sequence of instructions from the target of a taken branch to the next taken branch, potentially containing multiple basic blocks. Figure 1 shows an example control flow graph from which we will find the possible streams. The figure shows a loop containing an if-then-else 1 Control Flow Code Layout A B C D A CB D Possible Streams A B D A C D Not a Stream B D A B Figure 1. Example of instruction streams. structure. Let us suppose that our profile data shows that A→B→Dis the most frequently followed path through the loop. Using this information, we lay out the code so that the path A→Bgoes through a not-taken branch, and falls-through from B→D. Basic block Cis mapped somewhere else, and can only be reached through a taken branch at the end of basic block A. From the resulting code layout we may encounter four possible streams composed by basic blocks ABD,A, C,andD. The first stream corresponds to the sequential path starting at basic block Aand going through the frequent path found by our profile. Basic block Ais the target of a taken branch, and the next taken branch is found at the end of basic block D. Neither the sequence AB, nor the sequence BD can be considered streams because the first one does not end in a taken branch, and the second one does not start in the target of a taken branch. The infrequent case follows the taken branch at the end of A, goes through C, and jumps back into basic block D. Although a fetch engine based on streams is not able to fetch instructions beyond a taken branch in a single cycle, streams are long enough to provide high fetch bandwidth. In addition, since streams are sequentially stored in the instruction cache, the stream fetch engine does not need a special-purpose storage, nor a complex dynamic building engine. However, taking into account current technology trends, accurate branch prediction and high fetch bandwidth is not enough. The continuous increase in processor clock frequency, as well as the larger wire delays caused by modern technologies, prevent branch prediction tables from being accessed in a single cycle [1, 8]. This limits fetch engine performance because each branch prediction depends on the previous one, that is, the target address of a branch prediction is the starting address of the following one. A common solution for this problem is the prediction overriding technique [8, 20]. A small and fast predictor is used to obtain a first prediction in a single cycle. A slower but more accurate predictor provides a new prediction some cycles later, overriding the first prediction if they differ. This mechanism partially hides the branch predictor 2 access latency. However, it also causes an increase in the fetch architecture complexity, since prediction overriding requires a complex recovery mechanism to discard the wrong speculative work based on overridden predictions. An alternative to the overriding mechanism is using long basic prediction units. A stream prediction contains enough instructions to feed the execution engine during multiple cycles [17]. Therefore, the longer a stream is, the more cycles the execution engine will be busy without requiring a new prediction. If streams are long enough, the execution engine of the processor can be kept busy during multiple cycles while a new prediction is being generated. Overlapping the execution of a prediction with the generation of the following prediction allows to partially hide the access delay of this second prediction, removing the need for an overriding mechanism, and thus reducing the fetch engine complexity. Since instruction streams are limited by taken branches, a good way to obtain longer streams is removing taken branches through code optimizations. Code layout optimizations have a beneficial effect on the length of instruction streams [17]. These optimizations try to map together those basic blocks that are frequently executed as a sequence. Therefore, most conditional branches in optimized code are not taken, enlarging instruction streams. However, code layout optimizations are not enough for the stream fetch engine to completely overcome the need for an overriding mechanism [18]. Looking for novel ways of enlarging streams, we present a detailed analysis of dynamic instruction streams. Our results show that most of them finalize in conditional branches, function calls, and return instructions. As a consequence, it would seem that these types of branches are the best candidates to apply techniques for enlarging instruction streams. However, according to Amdahl’s law, focusing on particular branch types is not a good approach to enlarge instruction streams. If we focus on a particular type of stream, the remainder streams, which do not benefit from the stream enlargement, will limit the achievable performance improvement. This leads to a clear conclusion: the correct approach is not focusing on particular branch types, but trying to enlarge all dynamic streams. In order to achieve this, we present the multiple stream predictor, a novel predictor that concatenates those streams that are frequently executed as a sequence. This predictor does not depend on the type of the branch terminating the stream, making it possible to generate very long virtual streams. The remainder of this paper is organized as follows. Section 2 describes previous related work. Section 3 presents our experimental methodology. Section 4 provides an analysis of dynamic instruction streams. Section 5 describes the multiple stream predictor. Section 6 evaluates the proposed predictor. Finally, Section 7 presents our concluding remarks. 3 2 Related Work The prediction table access latency is an important limiting factor for current fetch architectures. The processor front-end must generate the fetch address in a single cycle because this address is needed for fetching instructions in the next cycle. However, the increase in processor clock frequency, as well as the slower wires in modern technologies, cause branch prediction tables to require multi-cycle accesses [1, 8]. The trace predictor [6] is a latency tolerant mechanism, since each trace prediction is potentially a multiple branch prediction. The processor front-end can use a single trace prediction to feed the processor back-end with instructions during multiple cycles, while the trace predictor is being accessed again to obtain a new prediction. Overlapping the prediction table access with the fetch of instructions from a previous prediction allows to hide the branch predictor access delay. Our next stream predictor has the same ability [18], since a stream prediction is also a multiple branch prediction able to provide enough instructions to hide the prediction table access latency. Using a fetch target queue (FTQ) [13] is also helpful for taking advantage of this fact. The FTQ decouples the branch prediction mechanism and the instruction cache access. Each cycle, the branch predictor generates the fetch address for the next cycle, and a fetch request that is stored in the FTQ. Since the instruction cache is driven by the requests stored in the FTQ, the fetch engine is less likely to stay idle while the predictor is being accessed again. Another promising idea to tolerate the prediction table access latency is pipelining the branch predictor [7, 21]. Using a pipelined predictor, a new prediction can be started each cycle. Nevertheless, this is not trivial, since the outcome of a branch prediction is needed to start the next prediction. Therefore, each branch prediction can only use the information available in the cycle it starts, which has a negative impact on prediction accuracy. In-flight information could be taken into account when a prediction is generated, as described in [21], but this also involves an increase in the fetch engine complexity. It is possible to reduce this complexity in the fetch engine of a simultaneous multithreaded processor [24] by pipelining the branch predictor and interleaving prediction requests from different threads each cycle [3]. Nevertheless, analyzing the accuracy and performance of pipelined branch predictors is out of the scope of this work. A different approach is the overriding mechanism described by Jimenez et al. [8]. This mechanism provides two predictions, a first prediction coming from a fast branch predictor, and a second prediction coming from a slower, but more accurate predictor. When a branch instruction is predicted, the first prediction is used while the second one is still being calculated. Once the second prediction is obtained, it overrides the first one if they differ, since the second predictor is considered to be the most accurate. A similar mechanism is used in the Alpha EV6 [4] and EV8 [20] processors, where a multi-cycle latency branch predictor overrides a faster but less accurate cache line predictor [2]. 4 The problem of prediction overriding is that it requires a significant increase in the fetch engine complexity. An overriding mechanism requires a fast branch predictor to obtain a prediction each cycle. This prediction should be stored for being compared with the main prediction. Some cycles later, when the main prediction is generated, the fetch engine should determine whether the first prediction is correct or not. If the first prediction is wrong, all the speculative work done based on it should be discarded. Therefore, the processor should track which instructions depend on each prediction done in order to allow the recovery process. This is the main source of complexity of the overriding technique. Moreover, a wrong first prediction does not involve that all the instructions fetched based on it are wrong. Since both the first and the main predictions start in the same fetch address, they will partially coincide. Thus, the correct instructions based on the first prediction should not be squashed. This selective squash will increase the complexity of the recovery mechanism. To avoid this complexity, a full squash could be done when the first and the main predictions differ, that is, all instructions depending on the first prediction are squashed, even if they should be executed again according to the main prediction. However, a full squash will degrade the processor performance and does not remove all the complexity of the overriding mechanism. Therefore, the challenge is to develop a technique able to achieve the same performance than an overriding mechanism, but avoiding its additional complexity, which is one of the objectives of this work. 3 Experimental Methodology The results in this paper have been obtained using trace driven simulation of a superscalar processor. Our simulator uses a static basic block dictionary to allow simulating the effect of wrong path execution. This model includes the simulation of wrong speculative predictor history updates, as well as the possible interference and prefetching effects on the instruction cache. We feed our simulator with traces of 300 million instructions collected from the SPEC 2000 integer benchmarks1using the reference input set. To find the most representative execution segment we have analyzed the distribution of basic blocks as described in [22]. Since previous work [17] has shown that code layout optimizations are able to enlarge instruction streams, we present data for both a baseline and an optimized code layout. The baseline code layout was generated using the Compaq C V5.8-015 compiler on Compaq UNIX V4.0. The optimized code layout was generated with the Spike tool shipped with Compaq Tru64 Unix 5.1. Optimized code generation is based on profile information collected by the Pixie V5.2 tool using the train input set. 1We excluded 181.mcf because its performance is very limited by data cache misses, being insensitive to changes in the fetch architecture. We have thoroughly checked that including 181.mcf does not change the conclusions of our work, but makes the plots harder to read. 5 fetch, rename, and commit widths 8 instructions integer and floating point issue widths 8 instructions load/store issue width 4 instructions fetch target queue 8entries instruction fetch queue 32 entries integer, floating point, and load/store issue queues 64 entries reorder buffer 256 entries integer and floating point registers 160 L1 instruction cache 64/32 KB, 2-way associative, 128 byte block, 3 cycle latency L1 data cache 64 KB, 2-way associative, 64 byte block, 3 cycle latency L2 unified cache 1 MB, 4-way associative, 128 byte block, 16 cycle latency main memory latency 350 cycles maximum trace size 32 instructions (10 branches) filter and main trace caches 128 traces, 4-way associative Table 1. Configuration of the simulated processor 3.1 Simulator Setup Our simulation setup corresponds to an aggressive 8-wide superscalar processor. The main values of this setup are shown in Table 1. We compare our stream fetch architecture with three other state-of-the-art fetch architectures: a fetch architecture using an interleaved BTB and a 2bcgskew predictor [20], the fetch target buffer (FTB) architecture [13] using a perceptron predictor [9], and the trace cache fetch architecture using a trace predictor [6]. All these architectures use an 8-entry fetch target queue (FTQ) [13] to decouple the branch prediction stage from the fetch stage. We have found that larger FTQs do not provide additional performance improvements. Our instruction cache setup uses wide cache lines, that is, 4 times the processor fetch width [12], and 64KB total hardware budget. The trace fetch architecture is actually evaluated using a 32KB instruction cache, while the remainder 32KB are devoted to the trace cache. This hardware budget is equally divided into a filter trace cache [14] and a main trace cache. In addition, we use selective trace storage [11] to avoid trace redundancy between the trace cache and the instruction cache. 3.2 Fetch Models The stream fetch engine [12, 17] model is shown in Figure 2.a. The stream predictor access is decoupled from the instruction cache access using an FTQ. The stream predictor generates requests, composed by a full stream of instructions, which are stored in the FTQ. These requests are used to drive the instruction cache, obtain a line from it, and select which instructions from the line should be executed. In the same way, the remainder three fetch models use an FTQ to decouple the branch prediction stage from the fetch stage. Our interleaved BTB fetch model (iBTB) is inspired by the EV8 fetch engine design described in [20]. This iBTB model decouples the branch prediction mechanism from the instruction cache with an FTQ. An interleaved BTB is used to allow the prediction of multiple branches until a taken branch is predicted, or until an aligned 8-instruction block is completed. The branch prediction history is updated using a single bit for prediction block, 6 Fetch Address Next Stream Predictor FTQ RAS Instruction Cache STREAM (a) The stream fetch engine Instruction Cache Fetch Address interleaved BTB / FTB FTQ Next Address Logic 2bcgskew / perceptron RAS Fetch Block (b) Fetch engine using a BTB/FTB and a decoupled conditional branch predictor Trace Cache Trace Identifier Next Trace Predictor Interleaved BTB Instruction Cache Trace Buffers FTQ RHS RAS TRACE (c) Trace cache fetch architecture using a next trace predictor Figure 2. Fetch models evaluated. which combines the outcome of the last branch in the block with path information [20]. Our FTB model is similar to the one described in [13] but using a perceptron branch predictor [9] to predict the direction of conditional branches. Figure 2.b shows a diagram representing these two fetch architectures. Our trace cache fetch model is similar to the one described in [15] but enhanced using an FTQ [13] to decouple the trace predictor from the trace cache, as shown in Figure 2.c. Trace predictions are stored in the FTQ, which feeds the trace cache with trace identifiers. An interleaved BTB is used to build traces in the case of a trace cache miss. This BTB uses 2-bit saturating counters to predict the direction of conditional branches when a trace prediction is not available. In addition, an aggressive 2-way interleaved instruction cache is used to allow traces to be built as fast as possible. This mechanism is able to obtain up to a full cache line in a cycle, independent of PC alignment. 7 The four fetch architectures evaluated in this paper use specialized structures to predict return instructions. The iBTB, the FTB, and the stream fetch architecture use a return address stack (RAS) [10] to predict the target address of return instructions. There are actually two RAS, one updated speculatively in prediction stage, and another one updated non-speculatively in commit stage, which is used to restore the correct state in case of a branch misprediction. The iBTB and FTB fetch architectures also use a cascaded structure [16] to improve the prediction accuracy of the rest of indirect branches. Both the stream predictor and the trace predictor are accessed using correlation, and thus they are already able to correctly predict indirect jumps and function calls. The trace fetch architecture uses a return history stack (RHS) [6] instead of a RAS. This mechanism is more efficient than a RAS in the context of trace prediction because the trace predictor is indexed using a history of previous trace identifiers instead of trace starting addresses. There are also two RHS, one updated speculatively in prediction stage, and another one updated non-speculatively in commit stage. However, the RHS in the trace fetch architecture is less accurate predicting return instructions than the RAS in the rest of evaluated architectures. Trying to alleviate this problem, we also use a RAS to predict the target address of return instructions during the trace building process. 3.3 Branch Prediction Setup We have evaluated the four simulated fetch engines varying the size of the branch predictor from small and fast tables to big and slow tables. We use realistic prediction table access latencies calculated using the CACTI 3.0 tool [23]. We modified CACTI to model tagless branch predictors, and to work with setups expressed in bits instead of bytes. Data we have obtained corresponds to 0.10µm technology. For translating the access time from nanoseconds to cycles, we assumed an aggressive 8 fan-out-of-four delays clock period, that is, a 3.47 GHz clock frequency as reported in [1]. It has been claimed in [5] that 8 fan-out-of-four delays is the optimal clock period for integer benchmarks in a high performance processor implemented in 0.10µm technology. We have found that the best performance is achieved using three-cycle latency tables [18]. Although bigger predictors are slightly more accurate, their increased access delay harms processor performance. On the other hand, predictors with a lower latency are too small and achieve poor performance. Therefore, we have chosen to simulate all branch predictors using the bigger tables that can be accessed in three cycles. Table 2 shows the configuration of the simulated predictors. We have explored a wide range of history lengths, as well as DOLC index [6] configurations, and selected the best one found for each setup. Table 2 also shows the approximated hardware budget for each predictor. Since we simulate the larger three cycle latency tables2, the total hardware budget devoted to each predictor is different. The stream fetch engine requires less hardware resources because it uses a single prediction mechanism, while the other evaluated fetch architectures use some separate structures. 2The first level of the trace and stream predictors, as well as the first level of the cascaded iBTB and FTB, is actually smaller than the second one because larger first level tables do not provide a significant improvement in prediction accuracy. 8 iBTB fetch architecture (approx. 95KB) 2bcgskew predictor interleaved BTB 1-cycle predictor four 64K entry tables 1024 entry, 4-way, first level 64 entry gshare 16 bit history 4096 entry, 4-way, second level 6-bit history (bimodal 0 bits) DOLC 14-2-4-10 32 entry, 1-way, BTB FTB fetch architecture (approx. 50KB) perceptron predictor FTB 1-cycle predictor 256 perceptrons 1024 entry, 4-way, first level 64 entry gshare 4096x14 bit local and 4096 entry, 4-way, second level 6-bit history 40 bit global history DOLC 14-2-4-10 32 entry, 1-way, BTB Stream fetch architecture (approx. 32KB) next stream predictor 1-cycle predictor 1024 entry, 4-way, first level 32 entry, 1-way, spred 4096 entry, 4-way, second level DOLC 0-0-0-5 DOLC 16-2-4-10 Trace fetch architecture (approx. 80KB) next trace predictor interleaved BTB 1-cycle predictor 2048 entry, 4-way, first level 1024 entry, 4-way, first level 32 entry, 1-way, tpred 4096 entry, 4-way, second level 4096 entry, 4-way, second level DOLC 0-0-0-5 DOLC 10-4-7-9 DOLC 14-2-4-10 perfect BTB override Table 2. Configuration of the simulated branch predictors. Our fetch models also use an overriding mechanism [8, 20] to complete a branch prediction each cycle. A small branch predictor, supposed to be implemented using very fast hardware, generates the next fetch address in a single cycle. Although being fast, this predictor has low accuracy, so the main predictor is used to provide an accurate back-up prediction. This prediction is obtained three cycles later and compared with the prediction provided by the single-cycle predictor. If both predictions differ, the new prediction overrides the previous one, discarding the speculative work done based on it. The configuration of the single-cycle predictors used is shown in Table 2. 4 Analysis of Dynamic Instruction Streams Fetching a single basic block per cycle is not enough to keep busy the execution engine of wide-issue superscalar processors during multiple cycles. In this context, the main advantage of instruction streams is their long size. A stream can contain multiple basic blocks, whenever only the last one ends in a taken branch. This makes it possible for the stream fetch engine to provide high fetch bandwidth while requiring low implementation cost. 4.1 The Length of Instruction Streams Figure 3 shows the average length of dynamic basic blocks and dynamic instruction streams. The shadowed part of each bar shows data using our baseline code layout. On average, instruction streams are 55% longer than basic blocks. This fact allows the stream fetch engine to outperform other fetch architectures based on basic blocks, as shown in [17], while requiring similar or even lower complexity. Figure 3 also shows the average length of dynamic instruction traces. The advantage of the trace cache fetch architecture is that it can fetch instructions beyond a taken branch in a single cycle. However, since traces are 9 0% 5% 10% 15% 20% 25% 1234567891 01 11 21 31 41 51 61 71 81 92 02 12 22 32 42 52 62 72 82 93 0+ instruction s per pr e diction single-stream predictor 2-stream multiple predictor (a) baseline code 0% 5% 10% 15% 20% 25% 1234567891 01 11 21 31 41 51 61 71 81 92 02 12 22 32 42 52 62 72 82 93 0+ instruction s per pr e diction single-stream predictor 2-stream multiple predictor (b) optimized code Figure 7. Histograms of dynamic predictions, classified according to the amount of instructions provided, when using a single-stream predictor and a 2-stream multiple predictor. The results presented in these histograms are the average of the eleven benchmarks used. Finally, it should be taken into account that this improvement is achieved by increasing the size of the first level table. Fortunately, the tag array is unmodified and no additional access port is required. We have checked using CACTI [23] that the increase in the predictor area is less than 12%, as well as that the prediction table access latency is not increased. Moreover, our proposal not only avoids the need for a complex overriding mechanism, but also reduces the predictor energy consumption. Although the bigger first level table consumes more energy per access, it is compensated with the reduction in the number of prediction table accesses. The ability of providing two streams per prediction causes a 35% reduction in the total number of prediction table lookups an updates, which leads to a 12% reduction in the overall stream predictor energy consumption. 16 Figure 8. Processor performance when using (full bar) and not using (shadowed bar) overriding. 7 Conclusions Current technology trends create new challenges for the fetch architecture design. Higher clock frequencies and larger wire delays cause branch prediction tables to require multiple cycles to be accessed [1, 8], limiting the fetch engine performance. This fact has led to the development of complex hardware mechanisms, like prediction overriding [8, 20], to hide the prediction table access delay. To avoid this increase in the fetch engine complexity, we propose to use long instruction streams [12, 17] as basic prediction unit, which makes it possible to hide the prediction table access delay. If instruction streams are long enough, the execution engine can be kept busy executing instructions from a stream during multiple cycles, while a new stream prediction is being generated. Therefore, the prediction table access delay can be hidden without requiring any additional hardware mechanism. In order to take maximum advantage of this fact, it is important to have streams as long as possible. We achieve this using the multiple stream predictor, a novel predictor design that combines frequently executed instruction streams into long virtual streams. Our predictor provides instruction streams long enough for allowing a processor not using overriding to achieve a performance close to a processor using prediction overriding, that is, we achieve a very similar performance at a much lower complexity, also requiring less energy consumption. Acknowledgements This work has been supported by the Ministry of Education of Spain under contract TIN–2004–07739–C02–01, the HiPEAC European Network of Excellence, CEPBA, and an Intel fellowship. 17 References [1] V. Agarwal, M. S. Hrishikesh, S. W. Keckler, and D. Burger. Clock rate versus IPC: The end of the road for conventional microarchitectures. In Proceedings of the 27th International Symposium on Computer Architecture, 2000. [2] B. Calder and D. Grunwald. Next cache line and set prediction. In Proceedings of the 22nd International Symposium on Computer Architecture, 1995. [3] A. Falcon, O. J. Santana, A. Ramirez, and M. Valero. Tolerating branch predictor latency on SMT. In Proceedings of the 5th International Symposium on High Performance Computing, 2003. [4] L. Gwennap. Digital 21264 sets new standard. Microprocessor Report, 10(14), 1996. [5] M. S. Hrishikesh, N. P. Jouppi, K. I. Farkas, D. Burger, S. W. Keckler, and P. Shivakumar. The optimal useful logic depth per pipeline stage is 6-8 fo4. In Proceedings of the 29th International Symposium on Computer Architecture, 2002. [6] Q. Jacobson, E. Rotenberg, and J. E. Smith. Path-based next trace prediction. In Proceedings of the 30th International Symposium on Microarchitecture, 1997. [7] D. A. Jimenez. Reconsidering complex branch predictors. In Proceedings of the 9th International Conference on High Performance Computer Architecture, 2003. [8] D. A. Jimenez, S. W. Keckler, and C. Lin. The impact of delay on the design of branch predictors. In Proceedings of the 33rd International Symposium on Microarchitecture, 2000. [9] D. A. Jimenez and C. Lin. Dynamic branch prediction with perceptrons. In Proceedings of the 7th International Conference on High Performance Computer Architecture, 2001. [10] D. Kaeli and P. Emma. Branch history table prediction of moving target branches due to subroutine returns. In Proceedings of the 18th International Symposium on Computer Architecture, 1991. [11] A. Ramirez, J. L. Larriba-Pey, and M. Valero. Trace cache redundancy: red & blue traces. In Proceedings of the 6th International Conference on High Performance Computer Architecture, 2000. [12] A. Ramirez, O. J. Santana, J. L. Larriba-Pey, and M. Valero. Fetching instruction streams. In Proceedings of the 35th International Symposium on Microarchitecture, 2002. [13] G. Reinman, T. Austin, and B. Calder. A scalable front-end architecture for fast instruction delivery. In Proceedings of the 26th International Symposium on Computer Architecture, 1999. [14] R. Rosner, A. Mendelson, and R. Ronen. Filtering techniques to improve trace cache efficiency. In Proceedings of the 10th International Conference on Parallel Architectures and Compilation Techniques, 2001. [15] E. Rotenberg, S. Bennett, and J. E. Smith. A trace cache microarchitecture and evaluation. IEEE Transactions on Computers, 48(2), 1999. [16] O. J. Santana, A. Falc´on, E. Fern´andez, P. Medina, A. Ramirez, and M. Valero. A comprehensive analysis of indirect branch prediction. Proceedings of the 4th International Symposium on High Performance Computing, 2002. [17] O. J. Santana, A. Ramirez, J. L. Larriba-Pey, and M. Valero. A low-complexity fetch architecture for high-performance superscalar processors. ACM Transactions on Architecture and Code Optimization, 1(2), 2004. [18] O. J. Santana, A. Ramirez, and M. Valero. Latency tolerant branch predictors. In Proceedings of the International Workshop on Innovative Architecture for Future Generation High-Performance Processors and Systems, 2003. 18 [19] O. J. Santana, A. Ramirez, and M. Valero. Techniques for enlarging instruction streams. Technical Report UPC-DAC- RR-2005-11, Departament d’Arquitectura de Computadors, Universitat Polit`ecnica de Catalunya, 2005. [20] A. Seznec, S. Felix, V. Krishnan, and Y. Sazeides. Design tradeoffs for the Alpha EV8 conditional branch predictor. In Proceedings of the 29th International Symposium on Computer Architecture, 2002. [21] A. Seznec and A. Fraboulet. Effective ahead pipelining of instruction block address generation. In Proceedings of the 30th International Symposium on Computer Architecture, 2003. [22] T. Sherwood, E. Perelman, and B. Calder. Basic block distribution analysis to find periodic behavior and simulation points in applications. In Proceedings of the 10th International Conference on Parallel Architectures and Compilation Techniques, 2001. [23] P. Shivakumar and N. P. Jouppi. CACTI 3.0: an integrated cache timing, power and area model. Technical Report 2001/2, Western Research Laboratory, 2001. [24] D. Tullsen, S. Eggers, and H. Levy. Simultaneous multithreading: maximizing on-chip parallelism. In Proceedings of the 22nd International Symposium on Computer Architecture, 1995. 19