Freeway to Memory Level Parallelism in Slice-Out-of-Order Cores

Existing core designs force a trade-off between MLP and energy efficiency. For example, an in-order (InO) core can be highly energy efficient, but it is unable to generate significant MLP, and therefore delivers poor performance. In contrast, OoO cores are generally good at extracting MLP, but at the cost of (much) lower energy efficiency. To exploit MLP while delivering high energy efficiency, a recent design, the Load Slice Core (LSC) (Carlson et al., 2015), proposed a new approach of slice-out-of-order (sOoO) execution. LSC builds on an efficient in-order core and employs separate instruction queues, AIQ and B-IQ, for non-MLP and MLP generating instructions, respectively. This enables MLP generating instructions in the B-IQ to bypass the potentially stalled load consumers in the A-IQ. By exposing MLP in this way, LSC avoids much of the complexity of full OoO architectures.

Figure 1 also demonstrates a major limitation of LSC: it is effective in extracting MLP only when the slices are independent. A dependent slice at the head of the B-IQ stalls MLP extraction by blocking the execution of the subsequent independent slices. In Figure 1, slice S2, a dependent slice as it depends on the load in S1, stalls the B-IQ and delays the execution of the next independent slice S3 until its producer slice S1 receives data from the memory hierarchy. Such slice dependencies limit MLP and overall performance. However, an Ideal sOoO core, that allows fully out-of-order execution among slices, would eliminate this limitation. As shown in Figure 1, an ideal sOoO core matches the MLP generation of a full OoO core.

The slice-out-of-order execution in LSC is a promising step towards energy efficient MLP extraction. However, LSC’s strict FIFO execution of slices limits its potential to extract MLP in the case of dependent slices. To understand this limitation, we next explore its impact on performance.

To quantify the potential MLP available in a sOoO core, we compare LSC, with its in-order B-IQ, to a LSC with a fully out-of-order B-IQ (Ideal-sOoO). While an out-of-order B-IQ would be impractical (it would defeat the efficiency goal of avoiding the complexity of out-of-order instruction selection), it allows us to observe the maximum MLP gains possible if the independent slices can bypass other stalled slices. (Our simulation methodology, including microarchitectural parameters, is detailed in Section 5.)

Figure 2 shows the performance gains obtained by LSC and Ideal-sOoO (LSC with a fully out-of-order B-IQ) over an InO core. The relative difference between the two shows the opportunity missed by LSC due to its FIFO slice execution. As the figure shows, the performance difference between Ideal-sOoO and LSC is 20%, geometric mean, and more than 50% on GemsFDTD, h264ref, hmmer, and leslie3d, due to relatively larger numbers of dependent slices. However, there is little gain for calculix, lbm, and milc, as they have fewer dependent slices (See Section 2.3). Overall, the majority of the workloads demonstrate considerable performance opportunity if we can eliminate the dependent slice bottleneck.

For a deeper understanding of the microarchitectural bottlenecks limiting MLP extraction in LSC, we examine the stall sources afflicting the B-IQ and categorize them as follows:

• $\bullet$

  Slice Dependence Stalls: A dependent slice at the B-IQ head is waiting for its producer to receive data from the memory hierarchy.

• $\bullet$

  Empty B-IQ Stalls: There are no instructions (slices) in the B-IQ.

• $\bullet$

  Load-store Aliasing Stalls: A load at B-IQ head cannot be issued because an older store in the A-IQ is waiting to write to the same address (true alias). This might happen because, in LSC, store data calculations and the store operations themselves go to the A-IQ, whereas, the store address calculation goes to the B-IQ.

• $\bullet$

  Other Stalls: Intra-slice dependencies, unresolved store addresses blocking younger loads, etc.

For this study, we assume an ideal core front-end (no instruction cache or BTB misses and a perfect branch predictor) to isolate the slice execution bottlenecks.

Figure 3 shows the breakdown of stall cycles (when no instruction is issued from either the A-IQ or the B-IQ) as a fraction of overall execution time. The figure reveals that instruction issue is stalled for 47% of the execution time on average, and Slice Dependence Stalls are responsible for almost half of these stalls. The Slice Dependence Stalls are particularly significant in gcc, mcf, soplex, and hmmer, where they account for more than 80% of all stalls. Notice that gcc and mcf are the most severely affected workloads, yet they are not the ones that show the highest performance opportunity with Ideal sOoO execution (Figure 2). The reason is that the performance opportunity is a function of not only the number of stalls caused by dependent slices, but also where their producer slices hit in the memory hierarchy. As shown in Figure 4, the majority of producer slices, in gcc and mcf, miss in the on-chip cache hierarchy and must be loaded from memory. This long memory latency stalls instruction retirement, and therefore causes the instruction window to fill which blocks further MLP generation and limits performance. In this work, we use the term instruction window to refer to the window of all in-flight instructions, i.e., the instructions that have been dispatched but not yet committed. Scoreboard and reorder buffer (ROB) are the typical hardware implementations of instruction window in sOoO and OoO cores, respectively.

Empty B-IQ Stalls are the second largest source of stalls. We observe that the primary reason for the B-IQ to be empty is a full instruction window and the oldest instruction is not ready to retire. As a result, no new instructions can enter either instruction queue. This could be remedied through larger instruction windows or methods such as Runahead Execution (Mutlu et al., 2003). The third largest source of stalls are Load-store Aliasing Stalls, and they are particularly severe in bwaves, cactusADM, gromacs, lbm, and povray. However, they account for only 8% of execution time.

Looking at the potential of an Ideal-sOoO, we see that LSC misses about 20% performance opportunity. The majority of this loss is due to Slice Dependence Stalls. Next, we analyze memory slice behaviour to mitigate this bottleneck.

Intuitively, only the dependent slices that stall the B-IQ for many cycles need to be buffered. Such long stalls are typically due to slice’s producers hitting in the LLC or memory. However, unintuitively, we found that 65% of the Slice Dependence Stalls are caused by dependent slices that stall only for a few cycles as their producers hit in the L1 cache. This demonstrates that even the relatively short L1 hit latency (4 cycles in our simulation) can significantly limit the MLP and performance in a sOoO core with strict FIFO slice execution.

Figure 4 shows the breakdown of Slice Dependence Stall cycles based on the producer slice hit site in the memory hierarchy. The results are especially interesting for workloads such as hmmer, where producer slices almost always hit in the L1 cache, and yet dependent slices are responsible for more than 96% of all stall cycles, which accounts for about 31% of the execution time (Figure 3).

These results suggest that it is important to buffer all dependent slices, even those that only stall for the duration of an L1 hit. Interestingly, this also suggests that in many cases we only need to buffer the dependent slices for a few cycles (to cover L1 latency) to achieve much of the MLP benefit. If such limited buffering is sufficient, it would suggest we can achieve these benefits at a low implementation cost.

To mitigate the slice dependence bottleneck, the dependent slices need to be kept in a separate buffer to prevent them from stalling the B-IQ. However, traditional instruction buffers, such as the Waiting Instruction Buffer (Lebeck et al., 2002), are complex, energy intensive, and are designed to buffer instructions for longer time intervals, such as during LLC misses. In addition, those designs require the instructions to be inserted back to the main IQ before issuing them for execution (Lebeck et al., 2002; Sembrant et al., 2015). The extra energy and latency of re-inserting instructions is particularly costly for instruction slices which will only be buffered for a few cycles.

A simple FIFO queue is an attractive alternative instruction buffer due to its low complexity and energy cost. However, as instructions can only be picked from the head of the FIFO queue, buffering all dependent slices in a single queue might cause a bottleneck if the younger slices become ready for execution before the older slices. This occurs for primarily two reasons: First, if a younger slice has fewer slices before it in its dependence chain than a slice in an older chain. Or, second, if the producer of a younger slice hits closer to the core in the memory hierarchy than the producer of an older slice. To understand the implications of these effects, we analyze potential stall sources to determine if a single, cheap, FIFO queue is appropriate for buffering dependent slices.

Using this definition, we observe that a younger slice with a lower dependence depth is likely to become ready before an older slice with higher dependence depth. For example, in Figure 5, S3 (depth 2) will be ready only after both S2 and S1 have received their data, whereas S5 (depth 1) needs to wait only for S4. If all the slices hit at the same level in memory hierarchy, leading to similar execution times, S5, the younger slice, will be ready for execution before S3. However, it will be stalled behind S3 in the FIFO queue, thereby limiting MLP extraction.

To understand the potential bottleneck due to such stalls, we study the slice dependence depth in our workloads in Figure 6. As the figure shows, 78% of all slices are independent slices (depth 0) and do not need to be buffered. Of the remaining slices that do need to be buffered, more than 72% are at dependence depth 1. Therefore, as the majority of dependent slices are at the smallest depth of 1, the stalls caused by slices at larger dependence depths (6% of all slices) are likely to be minimal.

To understand the extent of the potential bottleneck, we study the hit site of producer slices with at least one dependent slice. For this study, we only consider the producer slices at dependence depth 0 because the majority of dependent slices are at depth 1 (i.e. dependence chain lengths of 2 slices). Figure 7 shows that more than 96% of these producer slices hit in the L1 cache. Therefore, as the majority of producer slices hit at the same level, L1, the dependent slices are likely to become ready in the program order, and, hence, incur minimal stalls due to ready younger slices waiting behind stalled older ones.

Overall, Figures 6 and 7 suggest that a single FIFO queue for all dependent slices is sufficient to expose most of the potential MLP available from out-of-order slice execution. This is because most of the dependence slices are at the dependence depth one and the majority of producer slices hit in L1, indicating that it is unlikely that dependence slices will stall behind each other. (Results in Section 6.2 validate that additional queues bring only minimal performance gains.)

The first sOoO design, the Load Slice Core, builds upon an energy efficient in-order, stall-on-use core. LSC identifies MLP generating instructions (slices) in hardware and executes them early (via the B-IQ) with minimum additional resources, thereby achieving both MLP and energy efficiency.

Figure 1 shows an example of slice construction. As soon as the decoder detects a load or store instruction, it starts slice construction. The construction of slice S1 in this figure starts with the load instruction I3. Once the load is detected, IBDA consults RDT to find its producers. In this case, RDT will report I2 to be a producer as it wrote to the input register, r8, of the load instruction I3. Further, I2 will be inserted into the IST as it has been identified to be a part of the slice. During the next iteration, I2 will hit in IST and IBDA will consult RDT to find its producers. However, I2 does not have any producers in the instruction window as its operands are already available when it is decoded. Therefore, IBDA will stop backwards traversal implying completion of slice construction. Notice that a slice includes only data flow but not the control flow required to generate the address for memory access instruction.

While LSC is effective in exploiting MLP when the memory slices are independent, dependent slices cause a serious bottleneck due to LSC’s strict FIFO slice execution. As LSC mixes dependent slices with the independent ones in the B-IQ, it limits MLP by delaying the execution of independent slices stalled behind the dependent ones. To increase MLP, Freeway abandons LSC’s FIFO slice execution and allows independent slices to execute out-of-order with respect to dependent ones with minimum additional hardware.

To enable out-of-order execution among slices, Freeway tracks slice dependencies in hardware and separates dependent slices from independent ones. Freeway uses the slice dependency information to accelerate independent slice execution by reserving the B-IQ exclusively for them. To handle the dependent slices, Freeway introduces a new FIFO instruction queue called the yielding queue (Y-IQ). Dependent slices can then wait in the Y-IQ, yielding execution to the independent slices, until they become ready for execution. As our analysis in Section 3 demonstrated, the dependent slices mostly become ready in program order, therefore, ready dependent slices should rarely stall behind the non-ready ones. This characteristic allows us to use simple hardware to boost MLP by executing the majority of slices from both the B-IQ and Y-IQ without any stalls.

Freeway requires only minimal additional hardware, as shown in Figure 8, to support out-of-order slice execution: extending the RDT entries with one bit to track whether an instruction belongs to a dependent slice; adding a FIFO instruction queue (Y-IQ) for dependent slices; extending each store buffer entry with 7 bits and comparators to maintain memory ordering; and adding logic to issue instructions from the Y-IQ in addition to from the A-IQ and B-IQ.

We first describe the mechanism for tracking slice dependence and then provide details of instruction flow through Freeway, before discussing memory ordering requirements.

Figure 9 presents the performance gains of LSC and Freeway over the baseline in-order core. The figure also shows the performance limits of Ideal-sOoO (MLP limit) and full OoO (MLP+ILP limit) execution. The geometric mean (Gmean) performance difference between Freeway and LSC is 12% as Freeway attains 60% speedup over the in-order execution compared to 48% for LSC. More importantly, Freeway is within 7% of the performance of Ideal-sOoO, which is the upper bound on the performance achievable via MLP exploitation (MLP limit). An OoO core delivers 33% more performance gain than Freeway, over an InO core, as it exploits both ILP and MLP, whereas Freeway targets only MLP. However, this additional performance comes with high area and power overheads (Section 6.7).

A closer inspection reveals that Freeway’s performance advantage over LSC is a function of not only the number of stalls caused by dependent slices, but also where producer slices hit in the memory hierarchy. For example, workloads such as gcc, soplex, and omnetpp, where slice dependencies stall execution for more than 45% of time in LSC, benefit only moderately from Freeway. The reason for this behaviour is that more than 70% of the producer slices in these workloads miss in the on-chip cache hierarchy and must be loaded from memory. (Figure 4). This latency stalls instruction retirement, and therefore causes the instruction window to fill, which blocks further MLP generation and limits performance. In contrast, Freeway delivers significantly more performance (95% and 76%, respectively) for hmmer and leslie3d, despite LSC stalling on slice dependencies for only 30% of the execution time. This is because almost all of the producer slices in these workloads hit in the L1 cache. Therefore, the instruction window is rarely full and Freeway can continuously exploit MLP and improve performance.

Finally, Figure 9 also shows that both Freeway and LSC perform similarly on workloads such as zeusmp, milc, lbm, and calculix. These workloads do not have many dependent slices and the corresponding stalls, as shown in Figure 3, are minimal. As a result, Freeway does not have much opportunity for improvement over LSC.

Figure 9 shows that despite its dependence aware slice execution, Freeway lags behind the optimal performance achievable via MLP exploitation (“Ideal-sOoO (MLP limit)”) by 7%. We observe that there are two main factors that cause this gap: First, Freeway addresses only the slice dependence related stalls but not the other stall sources such as Load-Store Aliasing, Empty B-IQ, etc. (described in Section 2.3). Second, buffering all dependent slices in a single Y-IQ leads to stalls when a younger slice becomes ready earlier than an older slice, although this is infrequent. Here we analyze the performance loss due to these factors and explore potential solutions.

As Figure 3 shows, Empty B-IQ is the largest source of stalls after slice dependence stalls. However, mitigating them requires improvements in core components other than instruction scheduling. For example, it either requires a better front-end, if the B-IQ is empty due to branch mispredictions or instruction cache misses, or it requires a larger instruction window, if the window is full when the B-IQ is empty. As the focus of this work is instruction scheduling, we do not explore techniques to mitigate these stalls.

The next largest source of stalls, as Figure 3 shows, is the stalls coming from load-store aliasing. Such load-store aliasing causes LSC to stall for 8% of the execution time. Furthermore, as Freeway enables early execution of independent slices, it can potentially expose more aliasing if some of the aliased loads were earlier hidden behind the dependent slices in the B-IQ of LSC. To quantify the resulting performance loss, we simulate skipping the aliased loads and issuing the subsequent instructions if they are ready. Though impractical, such scheduling shows the potential benefits of eliminating the load-store aliasing related stalls. The skip_Aliased_Load bar in Figure 10 shows that Freeway obtains only 2% additional performance by eliminating all such stalls. As the Other stall sources contribute even less, we do not quantify their impact on performance loss. From this analysis we see that even completely addressing the load-store aliasing related stalls would result in little performance gain.

As discussed in Section 3.2, buffering all dependent slices in a single Y-IQ might lead to stalls if younger slices become ready before the older ones (either the younger slices are at a lower dependence depth or their producers hit closer to the core in the memory hierarchy). As almost all producers hit in the L1 cache (Figure 7), we only consider mitigating stalls due to slice dependence depth by adding a single additional Y-IQ. Here we explore the benefits of having the first Y-IQ buffer only the dependent slices at dependence depth 1, while the rest of the dependent slices go to a second Y-IQ. As a result, the stalls in the first Y-IQ will be reduced as all the slices are at the same dependence depth. The skip_Aliased_Load+Additional_Y-IQ bar in Figure 10 shows that adding a second Y-IQ brings only 1.5% additional performance. These results also confirm our hypothesis that a single Y-IQ is enough to capture the most of the opportunity in out-of-order slice execution.

If combined, the above optimizations would bring performance to within 3.5% of the optimal. However, individually they provide only minimum performance returns on the resource investment.

Our proposed core design, Freeway, generates MLP by enabling slices to bypass the stalled non-slice instructions and enabling independent slices to bypass the stalled dependent ones. In addition, we employ a LLC prefetcher that increases the number of overlapping memory requests, hence MLP, by speculatively generating accesses for cache blocks that are likely to be required soon. This section quantifies the contribution of each of these components towards overall performance.

Figure 11 presents the performance gain achieved by the individual MLP generating components, i.e. Freeway and the LLC prefetcher, as well as the gain when they work together. For this study, we do not model prefetcher in the baseline in-order core to help evaluate the performance gains of the LLC prefetcher. In all other studies, however, our baseline in-order core (and all other evaluated cores including Freeway) does include a LLC prefetcher.

As the figure shows, Freeway provides a much higher performance gain (61%) than the LLC prefetcher (14%). This is because Freeway hides L1, LLC, and to some extent memory latency by generating parallel memory accesses and overlapping their latency. LLC prefetcher, in contrast, hides only the latency between LLC and memory, however the LLC (and even L1) latency is still exposed due to the serial accesses up until LLC. We also evaluated aiding the LLC prefetcher with an L1 prefetcher (stride prefetcher with 4 independent streams); however, it provides only about 1.5% additional Gmean performance.

Looking closely at individual workloads, there are three applications, gcc (expr and g23 inputs), libquantum, and soplex (ref input), where the LLC prefetcher outperforms Freeway. Figure 12 shows that all of these applications have high LLC MPKI (25-34) and thus get most of their data from memory. The LLC prefetcher delivers higher performance due to their prefetch friendly access pattern as it is able to reduce the LLC MPKI to 3-11. In contrast, Freeway is not able to generate enough MLP mainly due to a combination of two factors. First, the high LLC MPKI leads to frequent full instruction window stalls (long memory latency on LLC misses causes instruction window to fill up) which block further MLP generation. Second, and more importantly, as shown in Figure 6, these applications have a larger number of dependent slices which cannot be executed until their parent slices receive data, thus further lowering MLP.

For the other benchmarks with high LLC MPKI, Freeway outperforms the LLC prefetcher either because the benchmarks do not have many dependent slices, and therefore Freeway generates enough MLP, or their access patterns are not prefetch friendly and, therefore the LLC prefetcher does not perform well. For example, lbm does not have any dependent slices and, therefore, Freeway generates significant MLP. Conversely, mcf’s access pattern is not prefetch friendly, therefore, resulting in poor LLC prefetcher performance.

Another important finding from Figure 11 is that combining Freeway with LLC prefetcher provides considerably higher performance gain (82%) than that delivered individually by Freeway (61%) and the LLC prefetcher (14%). This is because, when combined, more memory accesses generated by Freeway are served from LLC due to the prefetched blocks, thereby reducing average memory access time. In addition, if these accesses were causing full instruction window stalls by blocking the instruction commit, their early completion will also enable subsequent memory accesses to enter the instruction window and execute early, thus further improving MLP and performance.

Overall the results in Figure 11 show that MLP generated by Freeway provides significantly higher performance than the LLC prefetcher. These results also imply that if designers must pick one technique among several competing candidates for MLP generation, for example in area-constrained designs, it is better to invest real estate in Freeway rather than in LLC prefetcher.

As Section 6.1 detailed, Freeway performs significantly better than LSC when both are given equal number of instruction queue entries (128). This section investigates the designs’ relative sensitivity to reducing the number of instruction queue entries and explores how few entries Freeway can work with while still delivering similar performance to LSC.

Figure 13 presents the performance gains achieved by LSC and Freeway with a total of 128, 32 and 20 instruction queue entries. We observed that the performance with 128 and 64 entries is similar (<1% difference), therefore we do not show 64-entry design point in the figure. The ratio of entries among different queues remains same as in the 128-entry case i.e. 1:1 (A-IQ:B-IQ) in LSC and 2:1:1 (A-IQ:B-IQ:Y-IQ) in Freeway. The results show that Freeway always performs better than LSC when they both feature equal number of queue entries regardless of whether it’s 128, 32, or 20-entries. Furthermore, Freeway with just 32 entries provides about 6% more gain than 128-entry LSC, over InO core, and Freeway requires barely 20 instruction queue entries to provide similar performance to that of the 128-entry LSC.

Looking at individual benchmarks, there is a set of applications where the 20-entry Freeway performs significantly better the 128-entry LSC. For example, Freeway performs about 50% better on hmmer and leslie3d and about 20% better on GemsFDTD. These are the applications where letting younger independent slices to bypass the older dependent ones offers significant performance opportunities as shown in Figure 2. The results in Figure 13 imply that even a small Y-IQ, with only 5 entries, enables significant number of independent slices to bypass the dependent ones, thus providing a high performance gain. Whereas a larger B-IQ in LSC does not provide additional performance as it simply results in more independent slices sitting behind the stalled dependent ones.

However, the 20-entry Freeway performs worse than the 128-entry LSC for some applications like milc, wrf, zeusmp etc. These applications do not present much performance opportunity as shown in Figure 2. In the absence of performance opportunity, the frequent dispatch (insertion into instruction queues) stalls caused by smaller instruction queues result in 20-entry Freeway performance dropping below that of the 128-entry LSC. The dispatch stalls are more frequent with smaller queues as they fill up quickly and the dispatch stage stalls as soon as any one of the queues is full and the next instruction also needs to be dispatched to that same queue. Though the combination of low opportunity and frequent dispatch stalls causes a performance drop in these applications, Freeway still performs slightly better than LSC when both are given same number of queue entries.

Overall, the results in Figure 13 show that Freeway can tolerate more than 6x reduction in the instruction queue entries (128 to 20) while delivering similar performance as 128-entry LSC due to its dependence aware slice execution.

As the majority of stalls in LSC occurs while producer slices fetch data from L1 cache (Figure 4), we study the sensitivity of Freeway’s performance gain to the L1 cache latency. In addition, we also study how close Freeway comes to the Ideal-sOoO and OoO cores at different L1 latencies. For this study, we vary the L1 latency (load-to-use) from 2 to 8 cycles. The default L1 latency used for the other experiments is 4 cycles.

Figure 14 presents the performance gain of different cores over an in-order core as a function of L1 latency. The first point to notice is that the gain of all cores is smaller at lower latencies. For example, Freeway delivers 60% performance gain over in-order core at 4-cycle latency, whereas it drops down to 38% at 2-cycle latency. This is because the baseline in-order core itself performs increasingly better at lower latencies as the dependent instructions stall for less time on L1 hits. As a result, the performance opportunity, and the achieved gain, for other cores is reduced.

An important finding from Figure 14 is that even though the performance gap between Freeway and LSC is very small (5%) at 2-cycle latency, it widens quickly at larger latencies: 12% at 4-cycle, 18% at 6-cycle, and 25% at 8-cycle latency. This is because the stalled dependent slices prevent the subsequent independent slices from executing for longer intervals at larger latencies in LSC, thereby limiting MLP. In contrast, Freeway keeps executing independent slices from B-IQ while the dependent ones wait longer in the Y-IQ. Overall, these results demonstrate that Freeway is better than LSC in tolerating higher L1 latencies.

The figure also shows that the performance gap between Freeway and Ideal-sOoO (which represents the MLP limit) grows at a significantly lower rate compared to the gap between Freeway and LSC. This gap increases from about 5% at 2-cycle L1 latency to 13% at the 8-cycle latency. As Ideal-sOoO executes slice instructions fully out-of-order, it is able to cover the MLP opportunities missed by Freeway, as discussed in Section 6.2. The performance gap between Ideal-sOoO and fully OoO also increases while going from 2-cycle to 8-cycle latency because OoO can hide the increased latency better by executing more ILP-generating instructions.

The results in Figure 15 show that Freeway not only performs better than LSC while considering equal L1 latency for both but also when it has to tolerate higher latency than LSC. For example, LSC delivers about 48% performance gain over the baseline InO core with a 4-cycle L1 latency, whereas Freeway achieves 50% gain even at a higher latency of 6 cycles. Similarly, LSC provides 35% gain at 6-cycle L1 latency while Freeway attains 41% gain even with 8-cycle latency. These results further validates Freeway’s advantage over LSC in tolerating L1 latency.

These results also imply that Freeway is likely to benefit more from a larger L1 cache (with correspondingly higher access latency) than LSC because of its better L1 latency tolerance.

The instruction window size, e.g. scoreboard size in Freeway, limits the number of in-flight instructions. Consequently, the number of outstanding memory accesses, hence MLP, is also bounded by the size of instruction window. While prior work (Carlson et al., 2015; Kumar et al., 2019) evaluated sOoO cores only at small instruction windows, we analyze their scalability across the full spectrum of instruction window widths and depths (i.e. from wimpy to brawny cores) by varying the instruction window size from 32 to 224 entries. We also size other structures (instruction queues, execution units, etc.) appropriately in accordance with the instruction window size. Furthermore, we use an issue width of 2 for the instruction windows of 32- and 64-entries, while 128-, 168-, 192-, and 224-entry instruction windows use issue widths of 3, 4, 6, and 8 respectively.

The performance results (geometric mean) across the benchmark suite are presented in Figure 16. The results show that Freeway’s performance advantage over LSC increases from about 10% to 14% while moving from 32 to 224 entry instruction window. Their performance difference at the 32-entry window is small because there are not many MLP opportunities in such a small window due to fewer in-flight instructions. However, as the number of in-flight instructions increases with window size, Freeway exposes increasingly more MLP by executing independent slices unobstructed, whereas in LSC most of the additional slices simply sit behind the stalled ones. The performance gap between Freeway and Ideal-sOoO also increases with window size, though Freeway is still within 16% of Ideal-sOoO (limits of MLP) even at a large 8-wide 224-entry instruction window.

The performance gains of fully out-of-order execution increase even more with the larger windows due to its ability to utilize both MLP and ILP. An important finding from the results of Figure 16 is that MLP contributes less to overall performance at large instruction windows. For example, Ideal-sOoO core, which exploits the maximum MLP, is within 18% of full OoO performance at a small 32-entry instruction window. However, the difference grows with instruction window size. This is because larger instruction windows offer more ILP opportunities to OoO execution, thus widening the performance gap with Ideal-sOoO which only extracts MLP.

These results highlight that further research is required for scaling sOoO cores to larger instruction windows. Furthermore, given that MLP’s contribution to overall performance reduces at large windows and that Freeway already extracts a large portion of the available MLP, the research in scaling sOoO cores should focus on ILP rather than capturing the MLP opportunities missed by Freeway.

To evaluate the area and power overheads of different core designs, we use CACTI 6.5 to compute the area and power consumption of each of their major components in 32nm technology. The area overhead of LSC is about 15% over the baseline in-order core. Freeway requires very little additional hardware over LSC: one bit per entry in RDT, 7 bits per entry in the store buffer, and the Y-IQ and logic to issue instructions from it. As a result, it needs only 1.5% additional area. In contrast, as reported by (Carlson et al., 2015), the OoO core incurs an area overhead of 154% over the baseline in-order core.

For power calculations, we use static power consumption and per-access energy values from CACTI and combine them with activity factors obtained from the timing simulations to compute power requirements of each component. Our evaluation, together with prior results (Carlson et al., 2015), show that LSC, Freeway, and OoO core increase the average power consumption by 1.22x, 1.24x, and 12.6x, respectively, over an in-order core. These results demonstrate the exorbitant area and power costs of the moderate performance benefits achieved by OoO core over more efficient slice-out-of-order core designs such as Freeway.

Existing research on tolerating memory access latency to prevent cores from stalling can be divided into two broad categories: techniques that extract MLP by overlapping the execution of multiple memory requests, and techniques that prefetch data proactively into caches by predicting future memory addresses. To some extent, these categories are complementary as prefetching can increase the number of overlapping memory requests by speculatively generating accesses that would otherwise be serialized due to dependencies or lack of resources. However, the energy efficiency of the majority of these techniques is bounded by the underlying energy intensive OoO core. Freeway, in contrast, provides an energy efficient alternative that these techniques can build on to potentially raise overall efficiency.

Helper threads can be generated either in software or dynamically in hardware. On the software side, many prior works have proposed compiler/programmer driven approaches for helper thread generation (Collins et al., 2001b; Kim and Yeung, 2002; Luk, 2001; Zilles and Sohi, 2001; Kamruzzaman et al., 2011; Kim and Yeung, 2004; Koukos et al., 2013) while others have proposed dynamic compilation techniques (Zhang et al., 2007; Lu et al., 2005). These techniques either execute the helpers threads on an available SMT context (Collins et al., 2001b; Kim and Yeung, 2004) or require a dedicated core (Kamruzzaman et al., 2011).

Collins et al. (Collins et al., 2001c) explored helper thread generation in hardware by tracking dependent instruction chains in the back-end. To keep the helper thread generation off the critical path, they introduced large, post-retirement, hardware structures to filter the desired instructions. Once the helper threads were generated, they were stored in a large cache and run on a free SMT context. Annavaram et al. (Annavaram et al., 2001) also extracted the dependent chains of operations that were likely to result in a cache miss in hardware, though from the front-end during instruction decode, and added a dedicated back-end for the execution of such chains.

To summarize, helper threads incur significant overhead as they require: 1) an independent execution context (SMT, a CMP core, or dedicate hardware) for their execution, 2) a mechanism to construct them either in hardware or software, 3) duplicated instruction execution in the main thread and helper thread.

Instruction scheduling is one of the most energy hungry operations in modern OoO cores (Palacharla et al., 1997). Therefore, researchers have proposed a number of techniques to reduce its energy requirements. Recent research in this domains exploits two properties, instruction readiness and instruction criticality, to minimize scheduling energy overhead.

Shioya et al. (Shioya et al., 2014) observed that a large fraction to total dynamic instructions is either ready for execution at dispatch stage or becomes ready within a few cycles of dispatching to the issue queue. These instructions do not benefit from OoO scheduling as they would execute without stalls even in an in-order pipeline. Therefore, they propose an architecture that attempts to execute all instructions via in-order pipeline stages before dispatching the unexecuted ones to OoO pipeline, thereby reducing scheduling energy. FIFOrder (Alipour et al., 2019), instead of trying to execute all instruction via in-order stages, dispatches ready instructions to a FIFO issue queue and non-ready instructions to an OoO (content addressable memory based) issue queue. As the OoO queue handles fewer instructions, FIFOrder reduces its depth and width, thus reducing the scheduling energy cost. Another recent architecture, CASINO core (Jeong et al., 2020), also targets ready instructions to simplify instruction scheduling.

Other researchers have targeted instruction criticality to cut the energy cost of scheduling. For example, Long Term Parking (LTP) (Sembrant et al., 2015), at dispatch stage, allocate issue queue entries only to critical instructions, whereas non-critical instructions are parked in a FIFO parking queue. Parked instructions are allocated issue queue entries only when they reach close to the head of reorder-buffer. As the parking queue reduces pressure on issue queue, LTP reduces its dimensions to reduce its energy requirements. A recent work, Delay and Bypass (Alipour et al., 2020), advocates exploiting both readiness and critically simultaneously to further improve energy savings.

Though all of these designs reduce instruction scheduling energy, they still feature CAM based instruction queues, albeit smaller than OoO cores. Therefore, their energy savings are not as high as those of sOoO cores. A recent design, Forward Slice Core(FSC) (Lakshminarasimhan et al., 2020), is the closest approach to sOoO cores in that it builds on a stall-on-use in-order core and uses only FIFO queues for instruction scheduling. Unlike sOoO cores, which specifically target MLP, Forward Slice Core (FSC) aims to extract generic ILP. Therefore, some of its features can be borrowed for ILP extraction in sOoO cores. Specifically, compared to sOoO cores, FSC enables non-slice instructions that do not depend on load instructions to bypass the load dependent instructions via a dedicated IQ, thereby extracting ILP among non-slice instructions. In sOoO cores, in contrast, as all non-slice instructions, whether load dependent or not, share the same IQ, they miss the ILP extraction opportunity. sOoO cores can borrow FSC’s mechanism to split load dependent and independent non-slice instructions into different queues to improve ILP extraction. However, this is only one of the many possible ways of splitting non-slice instructions. Other splitting criteria could include dispatching integer and floating-point instructions to different queues, creating and dispatching slices of branch instructions to dedicated queues to potentially reduce the branch misprediction penalty, or dispatching consumers of high vs. low latency loads to different queues, or splitting instructions based on fanout. Further investigation is needed to understand the trade-offs provided by these criteria.

FSC also shares some features with sOoO cores. For example, its mechanism to create forward slices is very similar to Freeway’s mechanism of identifying dependent slices. Also, as FSC does not explicitly identify address generating instructions (AGIs) and mixes them with non-AGIs in its Main Lane, load/store address generation is likely to be delayed, compared to sOoO cores, which would limit MLP extraction.

Besides instruction scheduling, register renaming is also an energy intensive operation (Palacharla et al., 1997) which has received researchers’ attention. Gonzalez et al. (Gonzalez et al., 1998) proposed to delay the register allocation until a late pipeline stage to reduce register file pressure, thus delivering same performance with a smaller and less energy hungry register file. Tabani et al. (Tabani et al., 2018) proposed a technique that releases physical registers earlier than conventional techniques, thus reducing register file pressure, size, and energy requirements. A recent work, STRAIGHT (Irie et al., 2018), proposes an instruction set architecture that eliminates the register renaming altogether.