# Instruction Block Movement with Coupled High-Level Program Sequencing

Shyam Murthy<EMAIL_ADDRESS>and  Gurindar Sohi<EMAIL_ADDRESS>Computer
Sciences Department, University of Wisconsin–MadisonMadisonWisconsinUSA53706

###### Abstract.

Efficiency in instruction fetching is critical to performance, and this
requires the primary structures—L1 instruction caches (L1i), branch target
buffers (BTB) and instruction TLBs (iTLB)—to have the requisite information
when needed. This paper proposes a high-level program sequencing mechanism and
a coupled technique for block movement, instruction presending, where
instruction cache blocks, BTB entries, and iTLB entries are autonomously moved
(or sent) from the secondary to the primary structures in a "just in time"
fashion so that they are available when needed.

Empirical results are presented to demonstrate the efficacy of the high-level
sequencing mechanism and block movement. Presending is especially effective
for benchmarks with a high base MPKI, where the movement of instruction blocks
(and BTB/iTLB entries) from secondary to primary structures is frequent.
Presending reduces the number of misses in primary structures by an order of
magnitude as compared to state-of-the-art instruction prefetching schemes, in
many cases, while allowing the processor to operate with small-sized primary
BTBs. This reduction in misses results in performance improvements in cases
where front-end efficiency is important.

##  1\. Introduction

Processor front-ends are designed around the idea of a processor fetching
instructions from memory hierarchies, with multiple levels of caches, and
additional structures such as instruction TLBs (iTLBs) and branch target
buffers (BTBs), used to support and speed up the fetching process. Many modern
applications have active code footprints that are too large to achieve high
hit ratios even with larger (primary) L1i caches, yet fit almost entirely in
cache sizes that are common in on-chip (secondary) L3 caches (Kanev et al.,
2015; Ayers et al., 2019, 2018; Sriraman et al., 2019; Ailamaki et al., 1999;
Cao et al., 1999; Keeton et al., 1998; Lo et al., 1998; Vavouliotis et al.,
2021). A similar situation occurs for relatively small-sized primary iTLBs and
BTBs. Overall, demand missing in primary structures (L1i cache, L1 iTLB, L1
BTB), and movement from secondary structures, is frequent. The question that
arises then is: how to proactively carry out the (frequent) movement from one
part of a processing chip (the secondary structures) to another (the primary
structures)?

Prefetching is used to carry out the movement from the secondary to the
primary structures, and a plethora of instruction prefetching schemes have
been proposed (Hsu and Smith, 1992; Smith, 1982; Park et al., 1997; Zhang et
al., 2002; Spracklen et al., 2005; Srinivasan et al., 2001; Chen et al., 1997;
Reinman et al., 1999; Ferdman et al., 2008, 2011; Kolli et al., 2013; Kaynak
et al., 2015; Aamodt et al., 2004; Kumar et al., 2018, 2017; Ansari et al.,
2020; Ishii et al., 2021; Ros and Jimborean, 2021; McFarling, 1989; Xia and
Torrellas, 1996; Ramirez et al., 2001; Luk and Mowry, 1998; Kallurkar and
Sarangi, 2016; Ayers et al., 2019; Annavaram et al., 2003; Soundararajan et
al., 2021; Gupta et al., 2020; Ansari et al., 2021). Some prefetching schemes
are closely coupled to the processor front-end and rely on the processor’s
low-level (branch-by-branch) sequencing through the program to identify the
(precise) upcoming dynamic instruction stream. This low-level sequencing is
impacted by branch direction predictors and BTBs. Other prefetching schemes
learn about blocks likely to miss and tie them to instruction stream events.

In this paper, we propose a mechanism to sequence through a program at a high
level to identify blocks of instructions likely to be executed (analogous to
(Pnevmatikatos et al., 1993; Sohi et al., 1995)), and couple it with a
presending mechanism to move the blocks from secondary to primary structures.
The high-level sequencing and coupled presending mechanism works with a shadow
program which consists of fragments of a program, with each fragment
containing information about instruction cache blocks, BTB, and iTLB entries
needed to process the instructions in that fragment, and identifiers of
successor fragment(s). The high-level sequencing does not rely on creating the
precise dynamic instructions stream and thus does not need branch predictors,
BTBs, etc. for its operation. The high-level sequencing identifies upcoming
(dynamic) fragments of the program, and the presending mechanism moves the
information for a fragment from secondary to primary structures in a "just in
time" fashion, using information sent from the processor to keep it on track,
and sufficiently ahead of the processor. Presending achieves significantly
lower (e.g., order of magnitude) misses than even the best prefetching
techniques. This translates into equivalent or higher performance than the
best prefetching techniques with smaller-sized primary BTBs.

##  2\. Motivation

###  2.1. Rate of Secondary Structure Involvement

| L1i | iTLB | BTB | Redirects per KI | Send MPKA | Static | %
---|---|---|---|---|---|---|---
| MPK | MPKA | MPKA |  |  |  |  |  |  |  | frag
Bench | I | A | 64 | 128 | 512 | 2k | 2K | 8K | Send | L1i | iTLB | BTB | 95th | (2, >2)
| (1) | (2) | (3) | (4) | (5) | (6) | (7) | (8) | (9) | (10) | (11) | (12) | (13) | (14)
s1 | 10 | 97 | 42 | 14 | 30 | 12 | 7 | 6 | 0.7 | 6.92 | 3.49 | 3.40 | 944 | 9.2,2
s2 | 15 | 121 | 60 | 0 | 76 | 1 | 4 | 4 | 0.1 | 1.44 | 0.15 | 0.55 | 250 | 2.4,0.1
s10 | 24 | 247 | 59 | 43 | 94 | 64 | 16 | 7 | 1.3 | 9.90 | 4.92 | 18.86 | 2638 | 7.6,1.8
s13 | 27 | 272 | 67 | 48 | 108 | 74 | 17 | 7 | 1.3 | 10.39 | 6.65 | 27.52 | 3119 | 7.2,2
s16 | 36 | 438 | 125 | 96 | 185 | 142 | 26 | 5 | 0.2 | 4.08 | 0.04 | 0.57 | 3132 | 3.9,0.3
s19 | 44 | 438 | 127 | 43 | 168 | 2 | 4 | 4 | 0.1 | 3.20 | 0.05 | 0.48 | 606 | 4.9,0.8
s23 | 48 | 444 | 131 | 101 | 252 | 191 | 35 | 6 | 0.2 | 6.34 | 1.47 | 1.44 | 3151 | 4.4,0.5
s26 | 54 | 475 | 144 | 113 | 280 | 222 | 39 | 6 | 0.2 | 3.52 | 0.36 | 0.93 | 3096 | 3.6,0.3
s32 | 63 | 508 | 169 | 133 | 319 | 247 | 42 | 5 | 0.1 | 0.46 | 0.39 | 0.38 | 2129 | 1.8,0
s38 | 79 | 609 | 220 | 123 | 385 | 18 | 6 | 3 | 0.0 | 1.23 | 0.02 | 0.17 | 631 | 2.2,0

Table 1. Select Benchmark Characteristics

When an instruction fetch request can’t be serviced by a primary (L1i) cache,
the secondary (L2/L3) cache gets involved. The canonical and widely
used/understood metric for L1i misses is misses per kilo instructions (MPKI).
However, given that multiple instructions are fetched per cycle and that
consecutive accesses to the same block need not make multiple L1i accesses
(e.g., if the block is buffered in the processor), another illustrative
measure of the rate of L2 cache involvement is the misses per kilo cache
accesses (MPKA).

Table 1 presents some empirical characteristics of a subset of server
benchmarks, with two benchmarks chosen from groups that have a base L1i MPKI
of 0-15, 15-30, 30-45, 45-60, and > 60, respectively. (More details of the
benchmarks and simulation setup are presented in section 6.) The first two
data columns (1 and 2) of Table 1 present the MPKI, and MPKA for a 32KB, 8-way
associative cache. Observe that the MPKA, even for the relatively low MPKI
benchmarks, e.g., s1, are quite high, with nearly 1 in 10 (97 of 1000) L1i
block accesses involving the L2. For the high MPKI applications, e.g., s32,
over half the L1i block accesses involve the L2.

Instruction processing also requires information from iTLBs and BTBs. The
needed iTLB information is uniquely determined by the static code block
containing the instruction. Similarly, the BTB information needed is closely
related to the corresponding static code block. The 3rd and 4th data columns
present the MPKA for iTLBs with 32 and 128 entries, respectively, and the 5th
and 6th data columns the MPKA for BTBs with 512 and 2K entries, respectively;
with 4-way set associativity in each case. The large code footprint also leads
to more frequent primary iTLB and BTB misses, and a high rate of involvement
of secondary TLBs and BTBs.

###  2.2. Prefetching for Block Movement

Instruction prefetching techniques, some of which we will discuss in section
5, try to get sufficiently ahead of the fetch process and prefetch needed
blocks into the L1i in a timely manner. Similarly, entries can be prefetched
into BTBs; prefetching for iTLBs is not common because of the risk of
pollution in extremely small-sized structures.

Most prefetching techniques (especially BTB/Fetch directed prefetchers) rely
on the identification of the precise instruction fetch stream, which is
impacted by branches. Thus they need a correct branch direction (via a branch
direction predictor) and a correct branch target (via a BTB). The increasing
code footprint has led to the need for very large BTBs, e.g., the IBM Z15
(Adiga et al., 2020) has a 16K entry primary BTB and a 128K entry secondary
BTB. It has also led to innovations in BTB design to achieve high hit rates
without a brute-force increase in size, and combining instruction/BTB
prefetching and BTB design, e.g., the Confluence (Kaynak et al., 2015) and
Shotgun (Kumar et al., 2018) proposals.

A redirect of the fetch process happens when it is determined that fetch was
proceeding down an incorrect path due to a branch mispredict or incorrect
branch target determination. A redirect of fetch typically also redirects the
associated prefetch process. The 7th and 8th data columns present the
redirects per kilo instructions (KI) for BTBs with 2K and 8K entries,
respectively. An 8K BTB size is required to reduce the redirects per KI to the
single digits. (In section 6 we will see that this number stays in the single
digits even with an infinite BTB due to branch mispredicts.)

Figure 1. Example Program Snippet

###  2.3. High-Level Program Structure

Many modern programs are highly structured, with many different
procedures/functions, and the call graph of the program represents the flow of
control at a function level. Within each function there are fragments of code:
a fragment is a set of blocks of code that start at a target of a call/return
instruction, and end at the next (dynamic) call/return instruction.

Figure 1 presents an example. Function F1 is called at site A, which starts
with blocks in fragment frag1. Then, F2 (frag4) may be called at site B,
depending upon the if condition. F3 (frag5) is called at site C. If the
program starts at frag1, the next fragment is either frag4 (F2 is called) or
frag5 (F3 is called). If frag4 is encountered, its next fragment is the return
of F2, i.e., the return of the call to F2 at site B, which is frag2. Likewise,
the next fragments processed after frag2 and frag3 are frag5 and frag6,
respectively.

The 13th and 14th data columns of Table 1 present characteristics of
fragments. The 13th column has the number of static fragments that account for
95% of the execution, and the 14th has a tuple with the percentage of
dynamically executed fragments that have two, or more than two possible next
fragments. For example, for s10, 2638 static fragments account for 95% of the
execution, and 7.6% and 1.8% of the dynamic fragments have two and more than
two next fragments, respectively, the remaining 90.6% having a single next
fragment. This data suggests that a shadow representation with fragments could
be maintained in tables of a few thousand entries and when traversing this
representation, going from one fragment to the next, would rarely encounter
more than two successors for a fragment.

###  2.4. High-level Sequencing and Presending for Block Movement

With a high rate of block movement (section 2.1), a technique where blocks are
proactively sent from secondary to primary structures is worth considering.
The idea of Instruction Presending (or Send) is to have an Instruction
Presending Unit (IPU) traverse a shadow representation of a program,
sequencing at a high level to identify the blocks that the processor executing
the program is going to need imminently and have them moved to the processor.
The IPU doesn’t need information that the processor uses for its instruction
sequencing (e.g., branch predictions or BTB information). It only needs to
track the processor’s progress on program execution, so it can be redirected
if it is proceeding incorrectly in its high-level sequencing. As we shall see,
by selectively proceeding along up to two paths, Send rarely needs to be
redirected in its sequencing, and can be extremely effective in identifying
and moving the blocks needed by the processor in a timely fashion.

The 9th data column is the redirects per KI for Send (details in section 6). A
redirect happens when the program sequencing in the IPU is different from the
correct one identified by the processor’s execution of the program. Note that
they are an order of magnitude lower than those with prefetching with an 8K
BTB (8th data column). That is, Send can "stay on track" in its sequencing,
and its identification of needed blocks much better. Consequently, it can
supply the L1i, iTLB, BTB very well, and achieve the MPKAs reported in the
10th, 11th, and 12th data columns with a 32KB L1i, a 64-entry iTLB, and
512-entry BTB, respectively. Note the nearly two orders of magnitude reduction
in most cases.

##  3\. High-level Sequencing and Presending Mechanism

###  3.1. Overview

Figure 2. Overview of the Instruction Presending Unit (IPU)

The Instruction Presending Unit (IPU), works with a shadow representation (or
shadow), corresponding to a program’s call graph. Each step, or fragment in
the shadow corresponds to a node in the call graph, and the transitions to the
next fragment(s) correspond to edges. The shadow, maintained in a Fragment
Table (FT), tracks the blocks in the fragment and the identifier(s) of the
next fragment(s). The IPU, shown in Figure 2, identifies the blocks in the
fragment, and the identity of the successor fragment(s) (i.e., high-level
sequencing). It then accesses the identified blocks from the L3, if needed,
and arranges for them to be sent to the L1i/processor, and repeats the process
with the next fragment.

The processor sends information about which fragment it is processing to the
IPU which uses it to track where the processor is, take corrective action
(redirect) if needed, and stay sufficiently ahead of the processor. Along with
code blocks, the IPU also sends iTLB and BTB entries from a secondary TLB/BTB
to the primary TLB/BTB.

In this paper, we construct the shadow representation dynamically (section
3.3) and maintain it in hardware tables (section 3.2). We describe the IPU’s
operation in high-level sequencing, block identification, and block movement
collectively, and they are tightly coupled. We first describe the sending of
L1i blocks and then discuss the sending of iTLB and BTB entries.

###  3.2. Shadow Program Representation and Creation

Figure 3. Entry of a Fragment Table

####  3.2.1. Main Fragment Table

The main structure for representing fragments in the shadow representation is
a Fragment Table (FT). A fragment starts at the target of a call or return
instruction. The PC of a call instruction is a natural identifier for the
fragment that starts with the first instruction of the called function.
Further, when that called function returns, the target of the return is the
continuation code from the next PC. We combine both these related fragments
into a single FT entry: (i) a call fragment (Call) and (ii) a return fragment
(Ret). For each fragment, the FT entry, shown in Figure 3, maintains: (a) a
set of blocks that are contiguous in the memory address space, or a region of
memory, (b) a count of the expected number of instructions executed
dynamically in the fragment, (or alternately the number of cycles to execute
the code in that fragment), (c) the identifier for a (single) next fragment,
or fragment target111 We will use the terms next fragment identifier and
target interchangeably.. The information for (a) is easily maintained as the
address of the first code block in the region (Addr) and a Size of the number
of (contiguous) blocks in the region. Additionally, there is a Multi Target
(MT) bit and an Overflow Regions (OR) bit for each fragment, whose use we see
next.

####  3.2.2. Dual Target Table (DTT)

The data in Table 1 suggested that frequently there is only a single target
per fragment, but often there are two, and sometimes more than two, targets
per fragment. To avoid increasing the size of the main FT, where we maintain
only a single target, we maintain these additional targets in other tables. We
use a Dual Target Table (DTT) to maintain the identity of the second target
fragment. Additionally, we have observed that it is useful to maintain aging
bits when there are multiple targets so that the additional (inactive) target
need not be pursued (section 3.4.3). These aging bits for the two paths (one
in the FT and the other in the DTT) are maintained in the DTT for both
paths222Since most fragments in the FT have only a single next fragment there
is no need for aging bits for them..

Like the DTT, information for more than two paths can be maintained in a Multi
Target Table (MTT). For many of the benchmarks we consider, maintaining two
targets for a fragment is adequate though for some benchmarks maintaining
information about multiple targets can be beneficial.

####  3.2.3. Overflow Regions Table (ORT)

For many fragments, there is a single (contiguous block) region that can be
represented in the main FT. However, several fragments have multiple non-
contiguous blocks. For such fragments, we maintain the additional non-
contiguous regions in an Overflow Regions Table (ORT). Like the FT, an ORT
entry has the starting block address and size to represent a code region.

To accommodate the skewed distribution of the number of code regions in a
fragment, we have found it useful to have multiple ORTs with different numbers
of additional code regions. For example, ORT-2, ORT-4, ORT-16, where each
entry can represent 2, 4, or 16 code regions in a fragment.

###  3.3. Shadow Program Construction

Figure 4. Fragment Table Construction Example

We describe how FT (and DTT/ORT) entries are populated in Figure 4 for the
execution of the program snippet of Figure 1. When the processor retires a
call (at PC A), it starts a new fragment A. The instruction blocks accessed by
this fragment are B1, B2, and B10. Say the if condition in function F1 is true
and thus the call at PC B is encountered. At this point the fragment (with ID
A) is terminated, a new fragment (B) starts, and thus, the next fragment for A
is B. The processor also tracks the dynamic number of instructions executed
between the call at PC A and the call at PC B333 Alternatively, we could track
the time between when the two different calls reach a processing (e.g.,
decode) stage..

As the processor transitions from retiring instructions in fragment A to
fragment B, the processor populates an entry in the FT for Call fragment A
(i.e., frag1). The fragment has two contiguous blocks (B1, B2), and thus the
main FT entry has <B1,1> indicating that B1 is the first block in the
fragment, and there is one additional block. Since B10 is not contiguous, it
is put in the ORT (and the ORT bit set); the ORT entry has <B10,0>. Further,
the Count is set (to 12).

Continuing further, after the call at PC B, blocks B14 and B15 are
encountered, followed by a return. As a result, on retiring the return
instruction, an entry for Call fragment B is created with <B14,1>, with a
Count (of 11) and the next fragment being set to return. The return then
returns to the code block at PC B+4, thus starting the return (ret) fragment
for fragment B. Say code blocks B26 and B27 are accessed, followed by the call
at PC C. On retiring the call instruction at PC C, the entry for the return
(ret) fragment of fragment ID B is created in the FT with <B26,1>, a Count (of
7) with the next fragment being set to C.

At some point later in the program execution the if condition is false, and
after the call at PC A (execution of frag1) execution flows to the call at PC
C. This would force a redirect of the IPU (below) because, as per the current
FT entries, the IPU expected the next fragment following fragment A to be
fragment B. At this point, the control information for the FT entry of
fragment A is updated. Since there is already an FT entry for A with the next
fragment B, an entry is created in the DTT for A with the next fragment C, and
the MT bit in the FT entry set. The blocks accessed by the fragment are also
updated (for the additional blocks before the call to C), if any of the
additional blocks miss in the L1i. Further, aging bits for the two paths (2,2)
are also set (in the DTT).

At the start of program execution, the FT is empty. For each new fragment
retired the IPU is redirected, and an FT entry for that fragment is created.
Once a fragment entry is created, further updates to it happen only on L1i
misses (or IPU redirects) during the fragment’s execution, not every time a
fragment is retired. Otherwise, the information in the FT used by the IPU to
supply the blocks is correct, and no updates are required. We will see that
empirically there are very few L1i misses and IPU redirects, implying that the
FT (and associated tables) are quickly populated and then heavily reused.

1

2 Next_Frag = Starting Fragment from Processor

3while  _not sufficiently ahead (Step 1c)_ do

4 if  _Next_Frag = Call_ then

5

6 Access FT (Step 1a)

7 Push Return Fragment in IPUS

8 FragInfo = FragInfo from FT (Step 1d)

9 Update Next_Frag from FragInfo (Step 1d)

10 else

11 FragInfo = Pop from IPUS

12 Update Next_Frag from FragInfo (Step 1d)

13 Use FragInfo to update UFQ (Step 1b)

14 Add Blocks from FT to UBAQ (Step 2)

Algorithm 1 Operation of the IPU

###  3.4. Operation of the IPU

####  3.4.1. Single Next Fragment

We start by explaining the IPU operation for fragments with a single target in
Algorithm 1, which indicates the steps taken in reference to the elements of
Figure 2. The IPU works with a fragment ID and tries to stay a sufficient
distance ahead of the processor. If the fragment ID is a call, it is used to
access the FT (step 1a) and obtain the call path fragment information (blocks
in fragment, count, and next fragment ID). Further, the fragment information
for the return fragment (also obtained from the FT) is pushed onto a IPU stack
(IPUS). If the next fragment ID is a return, the fragment information is
popped from the IPUS.

The fragment ID is recorded in an Upcoming Fragments Queue (UFQ) (step 1b).
The addresses of the blocks in that fragment (from the FT/ORT)444 If a return
fragment also has entries in the ORT, those regions are also pushed onto the
IPUS along with the information from the FT. are put into an Upcoming Block
Addresses Queue (UBAQ) (step 2). The next fragment ID (step 1d) is used to
repeat the process while the IPU is not sufficiently ahead of the processor
(step 1c). For blocks in the UBAQ, a decision is made (section 4) whether to
read a block from the L3 and send it to the L1i (step 4).

Overall, the operation of the IPU is very simple: read an entry from a table,
send parts of the entry to some buffers (the sending part), and use part of
the entry to get the index of the next entry or two (the high-level sequencing
part) and repeat as needed.

####  3.4.2. Processor-IPU Synchronization

The IPU tries to stay on the correct execution path, and sufficiently ahead of
the processor. For this, it maintains a Processor Fragment Fetch Queue (PFFQ)
to monitor the processor’s progress. As the processor fetches a fragment, it
inserts the fragment ID (call PC or return address) into the PFFQ (step 5).
The IPU compares the PFFQ and UFQ entries to detect when it is on a different
path from the processor and redirects in case of divergence. Redirects happen
when there is complex control flow behavior at the call graph level that the
FTT/DTT have not captured. One example, in our evaluated implementation, is
that we track only two target fragments, and the processor goes down an
untracked path. Another example is when there are unmatched calls and returns.
When redirected, the IPU starts on a new path with the latest fragment ID sent
by the processor, discarding other activity.

Knowing which fragment the processor has reached, the IPU can keep
sufficiently ahead of the processor by using the Count information of the
(remaining) fragments in the UFQ.

####  3.4.3. Multiple Next Fragments

When there are multiple potential next fragments (the MT bit is set in the FT
entry), the IPU has a choice of what to do for the high-level sequencing:
proceed down only one path or down multiple paths? It consults the aging bits
in the DTT/MTT to make this decision. To proceed down multiple paths, the IPU
has separate tracks, each proceeding down a single path. A copy of the IPUS is
created at a fork point and each path is given its own IPUS. The fragment
information for the second path is obtained from the DTT and each track of the
IPU proceeds as if it were on a single path. Eventually, one of the paths is
determined to be the correct path, using information sent by the processor via
the PFFQ. At this point, the incorrect paths are discarded and the IPU
proceeds down the correct path. Aging bits are updated positively for the
correct target (path) and negatively for the incorrect one. Our experimental
results suggest benefits in proceeding down two paths for almost all our
benchmarks, and in proceeding down multiple paths for some.

###  3.5. Additional Program Control Constructs

####  3.5.1. Indirect calls with multiple targets

For direct calls, there is a unique fragment associated with the call, and
thus the PC of the call is an adequate fragment identifier. However, for
indirect calls, there could be multiple targets of the call. To distinguish
between the different targets/fragments, we use a hash of the call PC and the
target PC as the fragment identifier. Note that the IPU works with a fragment
identifier as created; it does not know if the call was indirect or not.

####  3.5.2. Loops and Recursion

Loops and recursion are constructs where the same set of fragments are
executed repeatedly, and eventually execution proceeds to the fragment at the
continuation of the loop or the recursive call. The IPU need not send blocks
from the fragments with the loop/recursion repeatedly as they will likely be
in the L1i after the first time they are sent. After the loop/recursion exit,
the IPU should be sufficiently ahead of the processor to avoid misses on the
continuation path. To achieve this, at a loop/recursion, the IPU proceeds
along two paths, one along the looping/recursion path (which can be of an
indeterminate length), and the other along the continuation path. Along the
former path, the IPU does little after the initial sends other than monitoring
the fragment IDs along this path sent via the PFFQ. Along the latter path, it
attempts to stay a certain distance ahead of the processor, as normal.
Eventually, when the IPU sees a fragment ID from the latter path in the PFFQ,
it discards the former path.

###  3.6. Fragment Table Set Associativity

The FT is a set associative table. On a fragment creation, the FT is accessed
to determine an entry; the associativity helps to reduce the number of
conflicts among different fragments. However, the IPU accesses the FT using
the next fragment ID, not some arbitrary fragment ID. If the next fragment ID
is maintained as an index into the FT, most of the IPU’s FT accesses can be
direct, not set associative555The only time a set associative access would be
needed is when the IPU is redirected and restarts with a new fragment ID..
This can increase the speed and reduce the FT access energy. Likewise,
accesses to the DTT and ORT can also be made directly rather than set
associative, as they merely maintain additional information for a fragment in
the FT.

###  3.7. Enhancements for an iTLB/BTB

To send iTLB entries, the FT entry (and ORT entry) adds a pointer to an L2 TLB
entry with each region. When sending code blocks from a region (step 2), the
pointer is used to access the L2 TLB and put the corresponding entries in an
Upcoming Page Table Addresses Queue (UPTAQ) (step 2), as shown in Figure 2.
From there, they proceed to the iTLB. As in the case of cache blocks,
appropriate presence checks to reduce unnecessary movement can be made, if
needed. Eviction of an L2 TLB entry will result in a subsequent iTLB miss and
a consequent updating of the FT entry.

To also send BTB entries, the virtual page numbers are extracted from the tag
bits of the corresponding iTLB entries and used along with the block address
in the UBAQ to generate addresses for the L2 BTB. The corresponding entries
accessed (taking multiple accesses as needed) and sent, as also shown in
Figure 2, making presence checks as needed.

###  3.8. Location of the IPU

Since the IPU is intended to operate autonomously, it can be placed at
different points in the overall processing pipeline. One option is to place
the IPU alongside the L1i cache. In this case, the blocks in the UBAQ that are
accessed from the L3 and sent to the L1i can be "pulled" from the L3 just as
if they were L1i misses. The advantage of this placement is the ability to use
existing miss paths. Another option is for the IPU to be near the L3, where it
could potentially be shared by different cores running the same program. In
this case, the IPU would access the needed blocks from L3 and "push" them to
L1i. While we have the processor populating the FT with its retirement stream,
the FT could also be constructed in the L3 from the block references that
reach the L3 between fragment IDs (to be explored later). Or in software.

Regardless of its placement, primed with an FT, the IPU only needs to know the
processor’s fetch fragment IDs to operate and correct its high-level
sequencing. This communication isn’t significant, as we shall quantify. It can
be reduced by communicating once every N fragments, trading off the amount of
communication with the latency of redirection when IPU is proceeding
incorrectly.

###  3.9. Processor Wrong-Path Execution

If the processor inserts fragment IDs into the PFFQ at fetch, then there is
the possibility of incorrect IDs being inserted when the processor is fetching
on a wrong branch path, leading to unnecessary redirects of the IPU. This is a
very infrequent occurrence due to the high-level sequencing that we employ.
First, for many fragments, there is a single successor fragment, and
regardless of the branch outcomes in the fragment, the next fragment inserted
into the PFFQ is the same. (Similar observations were made by other studies
exploiting Control Independence (Al-Zawawi et al., 2007; Cher and Vijaykumar,
2001; Pnevmatikatos et al., 1993; Sohi et al., 1995).) Second, for fragments
with multiple successors, we record two successors in the FT/DTT, and the IPU
proceeds down two paths. Thus the IPU will only be (incorrectly) redirected if
the processor’s execution on a wrong branch path leads to a successor fragment
that is not one of the two fragments recorded in the FT/DTT that the IPU is
pursuing. This happens very infrequently, as we shall quantify in Table 4.
Accordingly, the IPU can continue to operate using processor fetch fragment
IDs, with minimal redirects, in the presence of wrong-path execution. Wrong-
path execution does not affect the training of the tables as they are trained
only on the retired instruction stream.

##  4\. Block Presending Decision Control

By sequencing at the fragment level, without being perturbed by dynamic
fragment-internal branches (an average of over 4 in our experiments), the IPU
can do a better job of keeping on track, with fewer redirections, than
approaches that may be redirected by every (mispredicted) dynamic branch.
However, since the IPU dumps large chunks of block addresses in the UBAQ there
is the potential for a significant increase in the L3 accesses and sending of
blocks that are not useful which could also lead to pollution in the L1i.
Accordingly, a decision needs to be made about which blocks in the UBAQ should
be accessed from the L3 to be sent to the L1i.

Blocks could be wastefully sent because: (i) the IPU proceeds down two paths,
as in section 3.4.3, with blocks from one path not being used, (ii) blocks
within a fragment are not going to be used based upon the branch outcomes
within the fragment, and (iii) a block is already in the L1i.

For the large code footprint applications that we consider, most of the time
there is only a single successor fragment (and path), illustrative examples of
which were shown in Table 1. An infrequent path is also not followed, as per
the aging bits in section 3.4.3. Further, two paths are followed, when needed,
only for a short period. Collectively this results in only a small overhead,
as we quantify in section 6.7.

Large server programs have regions of cold code (Ayers et al., 2019).
Untouched cold code regions aren’t brought into the L3. However, some regions
may have been touched, and thus will be in the FT/DTT/ORT, but are rarely
accessed later. This can result in blocks within a fragment becoming cold
while other blocks continue to be accessed and stay hot. To track the
temperature of code blocks we can associate a set of temperature bits (TBs)
with each block frame in the L3. However, temperature bits with an L3 block
frame would mean probing the L3 cache tags to determine their value, and this
is something that we would like to avoid. Instead, we track a block’s
temperature approximately using a Block Temperature Table (BTT). The BTT is a
linear array that is indexed using bits of the block address (e.g., 11 bits
for a 2K entry table). An entry in the BTT is an n-bit (e.g., 3-bit)
temperature value. The temperature bits in a BTT entry are set to a high
temperature when a block mapping to that BTT entry is sent. Further, an
additional accessed bit is added to each block frame in the L1i. When a block
is sent to the L1i, the accessed bit is reset. Then if it is accessed before
being evicted, the accessed bit gets set. If a block is evicted from the L1i
with its accessed bit reset, the temperature bits in the corresponding BTT
entry are decremented. The BTT entry is checked for blocks put into the UBAQ
and only blocks with an adequate temperature are sent to the L1 cache via the
PBQ. Because multiple blocks and block frames map to the same BTT entry, they
end up sharing and updating the temperature bits collectively. We have found
this aliasing to not be a major concern as the temperature information is
merely advisory.

The approach to not sending blocks that might already be in the L1i depends
upon the placement of the IPU (section 3.8). If the IPU, is alongside the L1i,
it could probe a copy of the L1i tags to make this determination. For an IPU
placement elsewhere, e.g., near the L3, probing L1i tags is not practical.
Instead, we maintain a pseudo-inclusion bit per block, to know whether or not
a block is present in the L1i. These bits are maintained in a Pseudo Inclusion
Bit Table (PIT), analogous to the BTT. The PIT is accessed with the low-order
bits of the block number, and entries updated when a block is moved to, or
replaced from, the L1i. We have observed that using a PIT to control block
movement provides similar results as probing the L1i cache tags.

As we quantify in section 6.7, with the above we can achieve overheads, in
terms of additional L3 blocks sent, on par with a state-of-the-art prefetching
scheme, Entangling Prefetching (EP) (Ros and Jimborean, 2021) for most of our
benchmarks while achieving fewer L1i misses and better performance.

Wasteful blocks can potentially lead to pollution and evict a useful block
from the L1i. We envision presending to be used when block movement from L2/L3
to L1i is frequent due to a high L1i miss rate. When the L1i miss rate is low,
and block movement is infrequent, presending (or prefetching for that matter)
may not be of interest. When the L1i miss rate is high there is a high
fraction of "dead" blocks, i.e., blocks that will be replaced before they are
re-referenced, as has been shown in (Gober et al., 2020) for the benchmarks
that we consider. Consequently, the extra block movement of EP and Send does
not result in significant L1i pollution, as these additional blocks are mostly
replacing dead blocks.

##  5\. Prefetching Schemes and other Related Work

Before evaluating presending we discuss some prefetching schemes to understand
the differences and why presending can be more effective.

Fetch directed instruction prefetch (FDIP) (Reinman et al., 1999; Ishii et
al., 2021) is a widely used and very effective scheme. It works to establish
the upcoming instruction stream by determining branch outcomes, using branch
direction predictors and BTBs, and prefetching the corresponding cache blocks.
Many proposed prefetching schemes improve on FDIP by improving its ability to
determine branch outcomes, typically by improving the primary BTB
capabilities, and improving the identification of blocks to prefetch. Two
recent proposals are Confluence (Kaynak et al., 2015) and Shotgun (Kumar et
al., 2018). Confluence proposes to unify the metadata to prefetch into both
L1i and the primary BTB. Shotgun, which is more effective, goes further and
proposes a novel primary BTB design that has multiple components and is more
effective than a standard BTB of a similar size. An unconditional BTB (UBTB),
based on high-level control flow, maintains a block footprint which is used to
trigger prefetching into the L1i and into a primary conditional BTB (CBTB).
The structure of the UBTB is like the main FT that we employ; information that
we maintain in the ORTs is spread across multiple UBTB entries.

FDIP, and improvements such as Confluence and Shotgun still rely on a branch
predictor, and the primary BTB, to sequence every branch in order to
anticipate the upcoming stream of instructions. Their ability to get ahead is
influenced by the branch predictor/BTB accuracy and effectiveness.

Another class of instruction prefetching schemes, of which Entangling Prefetch
(Ros and Jimborean, 2021) is the most effective, learn about blocks that will
miss and tie them to instruction stream events (e.g., instruction cache
accesses), and prefetch when those events are triggered (Hsu and Smith, 1992;
Smith, 1982; Park et al., 1997; Zhang et al., 2002; Spracklen et al., 2005;
Srinivasan et al., 2001; Ferdman et al., 2008, 2011; Kolli et al., 2013;
Aamodt et al., 2004; Ansari et al., 2020; Ros and Jimborean, 2021). Such
prefetchers, while not relying explicitly on BTBs, etc., are still influenced
by the correctness of the instruction stream which impacts the triggering
events. Moreover, by themselves, they don’t reduce the reliance of the fetch
mechanism on a large primary BTB; this requires a separate BTB prefetching
mechanism or more complex large BTB designs (Bonanno et al., 2013). RDIP
(Kolli et al., 2013) and CGP (Annavaram et al., 2003) also seek to exploit a
higher level of program control flow, though in a very controlled manner,
staying one fragment ahead and prefetching blocks from the next node in the
callgraph. They are not as effective as recent prefetching techniques (Ros and
Jimborean, 2021).

Presending, which sequences the program at a higher (call graph) level,
operates autonomously and does not rely on branch predictors or BTBs, or other
processor microarchitectural events such as cache accesses and cache misses.
It is very loosely coupled to the processor, needing only the identities of
fragments that the processor is executing to stay on track. Since it is not
redirected by branch mispredicts or BTB misses, it can better stay on track
(which we quantify in Section 6.3) for providing instruction blocks (as
opposed to the precise instruction stream), and associated iTLB and BTB
entries. The high-level program sequencing is influenced by the control flow
concepts in Multiscalar, which facilitated the creation of extremely large
instruction windows agnostic of local branch mispredictions (Pnevmatikatos et
al., 1993; Sohi et al., 1995). Presending in effect provides an appearance of
large primary memory hierarchy structures in the processor while having much
smaller structures. Predictor virtualization (Burcea et al., 2008; Bonanno et
al., 2013) has similar objectives, but uses very different techniques.

##  6\. Evaluation

Processor Decoupled Front-end
---
Width | uA1 - 6 instr; uA2 - 8 instr
Fetch queue | 192 instr
Decode queue | 60 entry
Dispatch queue | 60 entry
Branch target buffer | 8K entries
Target cache | 4K entries
Return Address stack | 64 entries
Branch penalty | 2 cycles (decode stage)
Branch Predictor | Hashed perceptron
Processor Back-end
Execute width | uA1 - 4 instr; uA2 - 10 instr
Retire width | uA1 - 5 instr; uA2 - 8 instr
Re-order buffer | uA1 - 352 entries; uA2 - 1000 entries
Load, store queue | 128, 72 entries
Load, store queue (uA2) | 300, 300 entries
Memory hierarchy
L1I cache | 32KB, 8-way, 4 hit cycles, 16 MSHR
L1i TLB | 64-entry, 4-way, 1 hit cycle
L1-D cache | 48KB, 12-way, 5 hit cycles, next-line;
L1-D cache (uA2) | Perfect, 1 hit cycle, next-line
L2 cache | 512 KB, 8-way, 10 hit cycles, spp-dev
L2 BTB | 16K-entry, 8-way, 8 hit cycles
L2 TLB | 2K-entry, 8-way, 8 hit cycles
L3 cache | 2MB, 16-way, 20 hit cycles, no pref
DRAM | 4 GB, one 8B channel, 1600 MT/s
Table 2. Simulated Machine Parameters

Structure | Entries | Entry Size | Storage
---|---|---|---
FT | 4096 | 12.375B | 50688B
DTT | 256 | 3.375B | 864B
ORT-2 | 1024 | 6.375B | 6528B
ORT-4 | 256 | 11.375B | 2912B
ORT-16 | 128 | 41.375B | 5296B

Table 3. Table Storage Requirements

###  6.1. Simulation Details

We evaluate the instruction presending mechanism (abbreviated Send) using the
ChampSim simulator (cha, [n. d.]) using 100 server benchmark traces provided
by Qualcomm Datacenter Technologies. These benchmarks and simulator have been
used in multiple recent papers on prefetching (Chacon et al., 2023; Asheim et
al., 2023; Ros and Jimborean, 2021, 2020). We group the benchmarks into 5
bins, based upon the base MPKI with a default L1i size. Bins I, II, III, IV,
and V correspond to base MPKIs of 0-15, 15-30, 30-45, 45-60, and > 60, and
have 16, 45, 6, 23, 10 benchmarks, respectively.

The baseline configuration (or uA1) described in Table 2, implements a
decoupled front-end modeling FDIP (Reinman et al., 1999), with a BTB, a Target
Cache to predict the target of indirect branches (Chang et al., 1997) and a
return address stack (RAS). The simulated FDIP design has a single-level,
1-cycle BTB, which is more aggressive than designs that employ a small,
1-cycle L1 corrected by a larger L2 BTB with longer access latency. Table 2
also describes uA2, a microarchitecture with wider fetch (8-wide) and a more
aggressive backend (large ROB/SQ/LQ and a perfect D-cache). We simulate a
16K-entry L2 BTB and a 2K-entry L2 TLB from where entries are sent to the
corresponding small-sized L1 structures. Since these structures aren’t used to
"correct" a smaller L1 structure (unlike an L2 BTB for FDIP), but rather are
to provide capacity, they can be slow (8 cycles in our case). Cache blocks are
sent from the L3 to the L1i.

Our comparisons will be against two of the most effective prefetching schemes.
The first is Shotgun (SG); we use a configuration with a 4K entry UBTB and a
1K entry CBTB, for which the storage is about 64KB. Smaller configurations, as
in the Shotgun paper, weren’t as effective for our benchmarks. Further, the SG
configuration that we simulate is very aggressive. For Send, for a fragment
with multiple code regions (due to an unconditional branch from one region to
another), the multiple regions reside in the ORTs and are processed in one
step. In SG, they reside in multiple UBTB entries. Our simulated SG
implementation also processes them in one step, simulating a single access for
the multiple UBTB entries. The second is Entangling Prefetch (EP), and we use
a configuration with a storage overhead of 77.44KB (Ros and Jimborean, 2021).
All schemes are implemented on top of the FDIP baseline shown in Table 2.

For speedup, we will use relative IPC as the metric. In place of coverage and
accuracy, which are commonly used for prefetching schemes, we use MPKI and
Accesses Per KI because they better illustrate the magnitude.

###  6.2. Default IPU Structures and Operation

The default structures and sizes used by the IPU are shown in Table 3. An FT
entry has 2B 666We use an L3 block frame number for the first block, instead
of a full physical address because Send moves blocks from L3 to the L1i. Full
addresses are generated when the first block is read from the L3 using the
tags. for the block address, 0.5B for the block count, 1B for the instruction
count, 1.5B for the next fragment, for each of the call and return fragments,
and 1.75B for the tags/valid bit. A DTT entry has 1.5B for the next fragment,
2 aging bits per path, and 1.25B for tags/valid bit. We use three ORT tables:
ORT-2, ORT-4, and ORT-16, which track 2, 4, and 16 code regions per fragment,
respectively. All tables have 8-way associativity with random replacement. MTT
(multi-target table) is not used, and we limit the number of paths to two at
any point of time. With the additional storage for the IPUS and the various
queues, this totals to about 68KB (plus an additional 19KB for iTLB and BTB
send) of storage with 4K FT entries, and about 43KB (plus 10KB for iTLB and
BTB send) with 2K FT entries. Note that this storage is in (slower) secondary
structures as compared to Shotgun and EP where it is in (faster) primary
structures.

For Send, we have two configurations, SendB, which employs a 2K-entry (768B)
BTT, and SendA, which does not use a BTT. When not explicitly mentioned, Send
refers to SendA. We do not use a Pseudo Inclusion Bit table for the simulation
results presented (for a fair comparison against other schemes). Rather we
simply probe the L1i to check for the presence of a block, like other
prefetching schemes. For an L1i miss latency of 20 cycles, with a 6-wide
processor, the IPU works to keep 6x20=120 instructions ahead 777Metric of
timeliness, we evaluate sensitivity to this parameter in Section 6.8.

We start by evaluating the redirects for FDIP, Shotgun, and Send in section
6.3. The redirects of the program sequencing determine how far ahead in the
instruction a scheme is able to get to correctly and the lower frequency of
redirects due to high-level program sequencing is the main reason presending
can get a better (timely) stream of the instruction blocks over prefetching.
After quantifying the efficacy of the high-level sequencing mechanism, we
present an evaluation of instruction presending, first presenting some
operational characteristics and then evaluating the supply to different
primary structures (iTLB, BTB, and L1i)

Figure 5. RPKI FDIP and Send

###  6.3. Redirects and Operational Characteristics

Figure 5 presents the redirects per KI (RPKI) for FDIP with different sized
BTBs, Shotgun, and Send. The Y axis (note the log scale) is the RPKI, and the
X axis are the 100 different benchmarks. The first (well-known) observation is
that FDIP needs large BTBs (8K) to reduce redirects. But even with an infinite
BTB, the RPKI is in the single digits, due to branch mispredictions. For
Shotgun, the RPKI is similar to the RPKI with an 8K BTB. For Send, it is much
lower, over an order of magnitude in many cases. This demonstrates that,
because of sequencing at a high level, without being perturbed by low-level
control flow changes such as branch mispredicts and BTB misses, Send can avoid
redirection, and proceed correctly much further into discovering the
instruction blocks needed than FDIP or Shotgun.

Metric | (I) | (II) | (III) | (IV) | (V)
---|---|---|---|---|---
RPKI | 0.16 | 1.10 | 0.21 | 0.17 | 0.11
Branch-Mispredict-Unique-Successor | 84.6 | 82.1 | 81.8 | 79.7 | 79.5
Branch-Mispredict-Successor-InTable | 98.7 | 98.7 | 98.9 | 99.6 | 99.7
Branches/fragment | 5.4 | 5.2 | 4.6 | 4.2 | 3.6
Instructions/fragment | 30.1 | 27.8 | 26.1 | 24.3 | 19.5
Update | 0.17 | 0.44 | 0.14 | 0.11 | 0.07
ORT-2 | 21.21 | 21.52 | 13.74 | 12.68 | 10.56
ORT-4 | 2.53 | 1.63 | 0.60 | 0.41 | 0.11
ORT-16 | 0.05 | 0.04 | 0.07 | 0.07 | 0.01
DTT | 6.11 | 9.49 | 6.69 | 5.69 | 4.06

Table 4. Send Operational Characteristics

Table 4 presents some operational characteristics of Send for the different
application bins. The first data row (RPKI) shows the RPKI. RPKI is very low
for bins I, III, IV, and V and somewhat higher for bin II.

The second data row (Branch-Mispredict-Unique-Successor) measures the
percentage of fragments containing a branch that is mispredicted and that have
a unique successor fragment. For these fragments, the high-level sequencing
(from fragment to fragment) is unaffected by the presence of mispredicted
branches within the fragment. This percentage is quite high, on average 80%
across all the bins. The third data row (Branch-Mispredict-Successor-InTable)
measures the number of fragments enclosing a branch mispredict that have their
successor fragment entered in either the FT or DTT, i.e., have one or two
recorded successor fragments, as a percentage of total dynamic fragments. This
percentage is about 99% or higher across the different bins. This indicates
that even in the presence of branch mispredicts in the processor, the IPU has
information to operate without a redirect, by pursuing one or two tracks, for
about 99% of the dynamic fragments.

The fourth data row (Branches/fragment) shows the average branches per
fragment. There are on average 3.5-5.5 branches per fragment, which minimally
impact RPKI for Send. In FDIP the prefetch must correctly get past those many
branches in a fragment (correct direction prediction and BTB hit) to get to
the (correct) instruction blocks that Send is able to get to. The fifth data
row (Instructions/fragment) has the average number of instructions per
fragment. If the processor sends the identifier of every fragment it fetches
to the IPU, this number is indicative of the communication rate. For bin II,
the processor will have to send, on average, one fragment ID per 27.8
instructions, or once every 10 cycles if the processor is achieving a
processing speed of 2.78 IPC.

The sixth data row (Update) is the percentage of fragments processed that are
involved in the creation or update of an FT entry. For example, for bin II,
0.44% of the fragments update the FT; 99.56% do not, i.e., once an FT entry is
created/updated, it is used about 225 times. For bin V, this number is over
1400. The low FT update rate (Update) indicates a low rate of communication
from the processor to create and maintain the FT. Additionally, a low RPKI can
be achieved with a low fragment identifier communication
(Instructions/fragment) rate. Collectively these numbers suggest that the IPU
can proceed productively in a mostly decoupled fashion from the processor.

The last data row (DTT) quantifies the percentage of FT accesses which also
involves a DTT lookup. Observe that this percentage is quite small (most FT
accesses have a unique next fragment). The remaining data rows measure the
percentage of FT accesses which involve a look-up to ORT-2, ORT-4, and ORT-16,
respectively. Observe that these percentages are quite small for ORT-4/ORT-16.
Percentages are a little higher for bins I and II because of having more
branches per fragment and more local control flow within a fragment.

Figure 6. iTLB MPKI Figure 7. iTLB Speedups

###  6.4. Instruction TLBs

We first consider using Send for iTLBs alone, using Send to move from a 2K
entry secondary (L2) TLB to a primary iTLB. Figure 6 presents the iTLB MPKI
(log scale) for FDIP (8K entry BTB) for 64-, 256- and infinite-entry iTLBs
(FDIP-64, 256, inf), without additional prefetching, and for Send with 32- and
64-entry iTLBs. Note the significantly smaller iTLB MPKI with Send, two orders
of magnitude in several cases for a 64-entry iTLB. This lower MPKI results in
performance improvement, as shown in Figure 7, which presents the speedup over
a base case of FDIP (8K entry BTB) with a 64-entry iTLB. With Send for an
iTLB, a 32-entry iTLB does better than even a normal 256-entry iTLB
configuration, and a 64-entry iTLB is close to a normal infinite iTLB.

Figure 8. IPC BTB-Send

###  6.5. Branch Target Buffers

We now consider Send for BTB entries alone. Figure 8 presents the IPC of
several configurations, relative FDIP with an 8K BTB. The graph presents the
relative IPC for FDIP with 512, 1K, 2K, and infinite BTB entries, Shotgun, and
Send with 256 and 512 BTB entries. FDIP alone with smaller BTB sizes suffers
significant performance loss, as is already known. The Shotgun configuration
simulated is close to the 8K BTB base, slightly lower for some benchmarks.
Send, on the other hand, achieves better performance than FDIP with 8K BTB
entries with only 256 BTB entries. With 512 BTB entries, Send is close to FDIP
with an infinite BTB. Conventional wisdom is that large primary BTBs are
needed for large code footprint workloads. With Send, even small primary BTBs
suffice, as Send can move the necessary BTB entries from the secondary BTB to
the primary BTB in a timely fashion.

Figure 9. MPKI uA1 Figure 10. IPC uA1 Figure 11. IPC uA2

###  6.6. L1 Cache

We now consider Send for the L1i cache for both uA1 and uA2 as the aggressive
back end of uA2 demands greater L1i efficiency. We use a 512-entry L1 BTB, and
sending from a 16K entry, 8 cycle L2 BTB (though an 8K entry L2 BTB was as
effective in almost all cases). For FDIP we use the normal configuration with
a primary 8K BTB (FDIP) and an infinite BTB (FDIP-Inf). For Entangling
Prefetch (EP), we also use an 8K primary BTB. EP’s effectiveness isn’t
impacted much by the primary BTB size; indeed the L1i MPKI for EP with a
smaller BTB (e.g., 512 entries), not shown, is also very good. But the overall
IPC gets impacted because the smaller BTB (without additional management)
impacts the fetching (and thus the IPC), significantly. The (aggressive)
Shotgun configuration is as described in section 6.1. We also consider an
infinite L1i cache (InfCache).

Figure 9 presents the MPKI (log scale) for the different configurations. FDIP,
with an 8K BTB, or with an infinite BTB, and Shotgun have a similar MPKI. EP
achieves a much lower MPKI, but SendA and SendB are even lower, by an order of
magnitude for some of the benchmarks. There is still some improvement with an
infinite cache. MPKI trends and magnitudes for uA2, not shown, are similar.

These lower MPKIs translate into increased performance, as shown in Figure 10
for uA1 and Figure 11 for uA2. In these figures, IPC is shown relative to the
base FDIP (with an 8K BTB) values. A reason that the aggressive Shotgun can
achieve a better IPC than FDIP, even with an infinite BTB, is because we allow
it to prefetch blocks from multiple code regions in a fragment that spans
multiple UBTB entries in one step, whereas FDIP would take multiple steps to
achieve the same. EP does quite well, performing better than FDIP and Shotgun.
For uA1, SendA and SendB perform only slightly better than EP, even though the
MPKI is much lower. For uA2, because of the higher demands for front-end
efficiency, the performance difference is greater, especially for applications
where Send has much lower MPKI than EP. The performance improvement over EP in
several benchmarks is 2-6%.

###  6.7. L3 Traffic and L1i Pollution Overheads

Figure 12 quantifies the traffic as L3 accesses per KI introduced by SendA,
SendB, EP, Shotgun, and the baseline FDIP, for which the L1i MPKIs and IPCs
were quantified in section 6.6. Here the results for FDIP are somewhat
optimistic as we do a trace-driven simulation, and wrong-path prefetches are
not counted in the traffic. Shotgun’s traffic is like FDIP, and slightly worse
in some cases, for the reason mentioned above. The traffic for Send is higher
than for FDIP (and Shotgun) in almost all cases though the difference is
relatively smaller in cases where the misses were higher. SendB does better
than SendA in some cases, with very similar IPC (figure 10). Note that the
traffic for SendA and SendB is on par with that of EP, which is more accurate
than other prefetching schemes (Ros and Jimborean, 2021). As has been noted by
(Gober et al., 2020), for most of these traces, many L1i blocks are dead.
Though Send and EP move additional (sometimes dead) blocks into the L1i, these
additional blocks mostly replace dead blocks, and thus they can continue to
maintain a low MPKI despite the additional block movement.

Figure 12. Traffic Increase for uA1 Figure 13. FT Size Variation

###  6.8. Miscellaneous Results

Figure 13 presents the relative IPC (with respect to a configuration with 4K
FT entries) for different FT sizes for uA2. Observe that even 2K and 3K FT
entries can provide most of the benefit in terms of IPC coming very close to
8K FT entries, for most benchmarks. A reduction of 2K FT entries results in a
storage reduction of 25KB.

| (I) | (II) | (III) | (IV) | (V)
---|---|---|---|---|---
FDIP32-IPC | 2.19 | 2.08 | 1.77 | 1.86 | 2.15
S32-1in1-IPC | 2.28 | 2.61 | 1.99 | 2.02 | 2.49
S32-1in2-IPC | 2.27 | 2.56 | 1.97 | 2.01 | 2.48
S32-1in4-IPC | 2.26 | 2.50 | 1.95 | 2.01 | 2.46
Timeliness Evaluation
FDIP32-MPKI | 5.43 | 24.45 | 40.63 | 50.20 | 69.38
S32-40-MPKI | 0.95 | 3.62 | 5.41 | 6.01 | 7.04
S32-80-MPKI | 0.40 | 2.21 | 1.88 | 1.56 | 1.10
S32-120-MPKI | 0.35 | 2.03 | 1.44 | 1.10 | 0.53
S32-160-MPKI | 0.33 | 2.07 | 1.40 | 1.05 | 0.54

Table 5. Miscellaneous Results

Next, we consider varying the rate of sending fragment IDs from the processor
to the IPU, and the keep ahead distance for Send, for uA2 in Table 5. Row 1
(FDIP) shows the absolute IPC for the different application bins for FDIP with
a 32KB cache. These absolute IPC numbers, which are missing in most papers
that use FDIP, allow the reader to assess the quality of our FDIP baseline.
Rows S32-1in1-IPC, S32-1in2-IPC, and S32-1in4-IPC present the absolute IPC for
the baseline Send configuration with the processor sending to the IPU, every,
1 in 2, and 1 in 4, fragments IDs, respectively. For bin II benchmarks, where
there is more complex control (see DTT entries in Table 4) more frequent
processor-IPU communication is needed to keep the IPU on track. For the other
bins, a reduced rate of communication suffices.

Lastly, we present an evaluation of the sensitivity of the timeliness metric.
Row FDIP32-MPKI presents the L1i MPKI for FDIP and rows S32-40-MPKI,
S32-80-MPKI, S32-120-MPKI, and S32-160-MPKI present the L1i MPKIs with Send
trying to keep 40, 80, 120, and 160 instructions, respectively, ahead of the
processor. In program phases where 6 instructions are being fetched every
cycle, keeping 120 (6x20) instructions ahead is needed to tolerate a 20-cycle
latency. Keeping only 40 instructions ahead helps improve the MPKI
significantly over the base FDIP but leaves more room for improvement. Keeping
80 instructions ahead improves MPKI even more. Beyond 120 instructions, at 160
instructions, the MPKI is nearly the same, with a very slight increase for bin
II, which has more fragments with two targets (DTT accesses, see Table 4), due
to more wasteful blocks sent from two paths.

##  7\. Concluding Remarks

This paper proposed a high-level program sequencing mechanism and a coupled
technique, instruction presending, where code cache blocks, iTLB and BTB
entries, are proactively moved from secondary structures to primary
structures. Working with tables holding a shadow representation, containing
information about fragments of a program, and without branch predictors and
BTBs, the presending hardware operates autonomously to send the requisite
information (iTLB and BTB entries, and instruction cache blocks) to the
processor, in a timely manner.

Presending is very effective, especially for large code footprint
applications, achieving an order of magnitude lower MPKI than state-of-the-art
instruction prefetching techniques in many cases, enabling the processor to
achieve equivalent or higher performance with much smaller-sized primary BTBs.
Effective instruction presending also opens up the possibility of sending
additional information about the instruction stream (possibly obtained via
preprocessing), that can be used to further improve instruction processing.

## References

  * (1)
  * cha ([n. d.]) [n. d.].  ChampSim simulator: http://github.com/ChampSim/ChampSim, March 2023.
  * Aamodt et al. (2004) T.M. Aamodt, P. Chow, P. Hammarlund, Hong Wang, and J.P. Shen. 2004.  Hardware Support for Prescient Instruction Prefetch. In _10th International Symposium on High Performance Computer Architecture (HPCA’04)_. 84–84.  https://doi.org/10.1109/HPCA.2004.10028
  * Adiga et al. (2020) Narasimha Adiga, James Bonanno, Adam Collura, Matthias Heizmann, Brian R Prasky, and Anthony Saporito. 2020.  The ibm z15 high frequency mainframe branch predictor industrial product. In _2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA)_. IEEE, 27–39.
  * Ailamaki et al. (1999) Anastassia Ailamaki, David J DeWitt, Mark D Hill, and David A Wood. 1999.  DBMSs on a modern processor: Where does time go?. In _VLDB’99, Proceedings of 25th International Conference on Very Large Data Bases, September 7-10, 1999, Edinburgh, Scotland, UK_. 266–277.
  * Al-Zawawi et al. (2007) Ahmed S Al-Zawawi, Vimal K Reddy, Eric Rotenberg, and Haitham H Akkary. 2007.  Transparent control independence (TCI).  _ACM SIGARCH Computer Architecture News_ 35, 2 (2007), 448–459.
  * Annavaram et al. (2003) Murali Annavaram, Jignesh M Patel, and Edward S Davidson. 2003.  Call graph prefetching for database applications.  _ACM Transactions on Computer Systems (TOCS)_ 21, 4 (2003), 412–444.
  * Ansari et al. (2021) Ali Ansari, Fatemeh Golshan, Pejman Lotfi-Kamran, and Hamid Sarbazi-Azad. 2021.  Mana: Microarchitecting an instruction prefetcher.  _arXiv preprint arXiv:2102.01764_ (2021).
  * Ansari et al. (2020) Ali Ansari, Pejman Lotfi-Kamran, and Hamid Sarbazi-Azad. 2020.  Divide and conquer frontend bottleneck. In _2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA)_. IEEE, 65–78.
  * Asheim et al. (2023) Truls Asheim, Boris Grot, and Rakesh Kumar. 2023.  A Storage-Effective BTB Organization for Servers. In _2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA)_. IEEE, 1153–1167.
  * Ayers et al. (2018) Grant Ayers, Jung Ho Ahn, Christos Kozyrakis, and Parthasarathy Ranganathan. 2018.  Memory hierarchy for web search. In _2018 IEEE International Symposium on High Performance Computer Architecture (HPCA)_. IEEE, 643–656.
  * Ayers et al. (2019) Grant Ayers, Nayana Prasad Nagendra, David I August, Hyoun Kyu Cho, Svilen Kanev, Christos Kozyrakis, Trivikram Krishnamurthy, Heiner Litz, Tipp Moseley, and Parthasarathy Ranganathan. 2019.  Asmdb: understanding and mitigating front-end stalls in warehouse-scale computers. In _Proceedings of the 46th International Symposium on Computer Architecture_. 462–473.
  * Bonanno et al. (2013) James Bonanno, Adam Collura, Daniel Lipetz, Ulrich Mayer, Brian Prasky, and Anthony Saporito. 2013.  Two level bulk preload branch prediction. In _2013 IEEE 19th International Symposium on High Performance Computer Architecture (HPCA)_. IEEE, 71–82.
  * Burcea et al. (2008) Ioana Burcea, Stephen Somogyi, Andreas Moshovos, and Babak Falsafi. 2008.  Predictor virtualization.  _ACM SIGOPS Operating Systems Review_ 42, 2 (2008), 157–167.
  * Cao et al. (1999) Qiang Cao, Pedro Trancoso, J-L Larriba-Pey, Josep Torrellas, Robert Knighten, and Youjip Won. 1999.  Detailed characterization of a quad Pentium Pro server running TPC-D. In _Proceedings 1999 IEEE International Conference on Computer Design: VLSI in Computers and Processors (Cat. No. 99CB37040)_. IEEE, 108–115.
  * Chacon et al. (2023) Gino Chacon, Nathan Gober, Krishna Nathella, Paul Gratz, and Daniel Jiménez. 2023.  A Characterization of the Effects of Software Instruction Prefetching on an Aggressive Front-end. In _2023 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS)_. IEEE, 24–34.
  * Chang et al. (1997) Po-Yung Chang, Eric Hao, and Yale N Patt. 1997.  Target prediction for indirect jumps.  _ACM SIGARCH Computer Architecture News_ 25, 2 (1997), 274–283.
  * Chen et al. (1997) I-Cheng K Chen, Chih-Chieh Lee, and Trevor N Mudge. 1997.  Instruction prefetching using branch prediction information. In _Proceedings International Conference on Computer Design VLSI in Computers and Processors_. IEEE, 593–601.
  * Cher and Vijaykumar (2001) Chen-Yong Cher and TN Vijaykumar. 2001.  Skipper: a microarchitecture for exploiting control-flow independence. In _Proceedings. 34th ACM/IEEE International Symposium on Microarchitecture. MICRO-34_. IEEE, 4–15.
  * Ferdman et al. (2011) Michael Ferdman, Cansu Kaynak, and Babak Falsafi. 2011.  Proactive instruction fetch. In _Proceedings of the 44th Annual IEEE/ACM International Symposium on Microarchitecture_. 152–162.
  * Ferdman et al. (2008) Michael Ferdman, Thomas F Wenisch, Anastasia Ailamaki, Babak Falsafi, and Andreas Moshovos. 2008.  Temporal instruction fetch streaming. In _2008 41st IEEE/ACM International Symposium on Microarchitecture_. IEEE, 1–10.
  * Gober et al. (2020) Nathan Gober, Gino Chacon, DA Jiménez, and P Gratz. 2020.  Temporal ancestry prefetcher.  _The 1st Instruction Prefetching Championship (IPC1)_ (2020).
  * Gupta et al. (2020) Vishal Gupta, Neelu Shivprakash Kalani, and Biswabandan Panda. 2020.  Runjump-run: Bouquet of instruction pointer jumpers for high performance instruction prefetching.  _The First Instruction Prefetching Championship_ (2020).
  * Hsu and Smith (1992) WC Hsu and J Smith. 1992.  Prefetching in supercomputer instruction caches. In _Supercomputing’92_. 588–597.
  * Ishii et al. (2021) Yasuo Ishii, Jaekyu Lee, Krishnendra Nathella, and Dam Sunwoo. 2021.  Re-establishing fetch-directed instruction prefetching: An industry perspective. In _2021 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS)_. IEEE, 172–182.
  * Kallurkar and Sarangi (2016) Prathmesh Kallurkar and Smruti R Sarangi. 2016.  pTask: A smart prefetching scheme for OS intensive applications. In _2016 49th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)_. IEEE, 1–12.
  * Kanev et al. (2015) Svilen Kanev, Juan Pablo Darago, Kim Hazelwood, Parthasarathy Ranganathan, Tipp Moseley, Gu-Yeon Wei, and David Brooks. 2015.  Profiling a warehouse-scale computer. In _Proceedings of the 42nd Annual International Symposium on Computer Architecture_. 158–169.
  * Kaynak et al. (2015) Cansu Kaynak, Boris Grot, and Babak Falsafi. 2015.  Confluence: unified instruction supply for scale-out servers. In _Proceedings of the 48th International Symposium on Microarchitecture_. 166–177.
  * Keeton et al. (1998) Kimberly Keeton, David A Patterson, Yong Qiang He, Roger C Raphael, and Walter E Baker. 1998.  Performance characterization of a quad Pentium Pro SMP using OLTP workloads. In _Proceedings of the 25th annual international symposium on Computer architecture_. 15–26.
  * Kolli et al. (2013) Aasheesh Kolli, Ali Saidi, and Thomas F Wenisch. 2013.  RDIP: Return-address-stack directed instruction prefetching. In _2013 46th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)_. IEEE, 260–271.
  * Kumar et al. (2018) Rakesh Kumar, Boris Grot, and Vijay Nagarajan. 2018.  Blasting through the front-end bottleneck with shotgun.  _ACM SIGPLAN Notices_ 53, 2 (2018), 30–42.
  * Kumar et al. (2017) Rakesh Kumar, Cheng-Chieh Huang, Boris Grot, and Vijay Nagarajan. 2017.  Boomerang: A metadata-free architecture for control flow delivery. In _2017 IEEE International Symposium on High Performance Computer Architecture (HPCA)_. IEEE, 493–504.
  * Lo et al. (1998) Jack L Lo, Luiz Andre Barroso, Susan J Eggers, Kourosh Gharachorloo, Henry M Levy, and Sujay S Parekh. 1998.  An analysis of database workload performance on simultaneous multithreaded processors. In _Proceedings. 25th Annual International Symposium on Computer Architecture (Cat. No. 98CB36235)_. IEEE, 39–50.
  * Luk and Mowry (1998) Chi-Keung Luk and Todd C Mowry. 1998.  Cooperative prefetching: Compiler and hardware support for effective instruction prefetching in modern processors. In _Proceedings. 31st Annual ACM/IEEE International Symposium on Microarchitecture_. IEEE, 182–193.
  * McFarling (1989) Scott McFarling. 1989.  Program optimization for instruction caches. In _Proceedings of the third international conference on Architectural support for programming languages and operating systems_. 183–191.
  * Park et al. (1997) Gi-Ho Park, Oh-Young Kwon, Tack-Don Han, Shin-Dug Kim, and Sung-Bong Yang. 1997.  An improved lookahead instruction prefetching. In _Proceedings High Performance Computing on the Information Superhighway. HPC Asia’97_. IEEE, 712–715.
  * Pnevmatikatos et al. (1993) Dionisios N Pnevmatikatos, Manoj Franklin, and Gurindar S Sohi. 1993.  Control flow prediction for dynamic ILP processors. In _Proceedings of the 26th Annual International Symposium on Microarchitecture_. IEEE, 153–163.
  * Ramirez et al. (2001) Alex Ramirez, Luiz André Barroso, Kourosh Gharachorloo, Robert Cohn, Josep Larriba-Pey, P Geoffrey Lowney, and Mateo Valero. 2001.  Code layout optimizations for transaction processing workloads.  _ACM SIGARCH Computer Architecture News_ 29, 2 (2001), 155–164.
  * Reinman et al. (1999) Glenn Reinman, Brad Calder, and Todd Austin. 1999.  Fetch directed instruction prefetching. In _MICRO-32. Proceedings of the 32nd Annual ACM/IEEE International Symposium on Microarchitecture_. IEEE, 16–27.
  * Ros and Jimborean (2020) Alberto Ros and Alexandra Jimborean. 2020.  The entangling instruction prefetcher.  _IEEE Computer Architecture Letters_ 19, 2 (2020), 84–87.
  * Ros and Jimborean (2021) Alberto Ros and Alexandra Jimborean. 2021.  A Cost-Effective Entangling Prefetcher for Instructions. In _2021 ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA)_. IEEE, 99–111.
  * Smith (1982) Alan Jay Smith. 1982.  Cache memories.  _ACM Computing Surveys (CSUR)_ 14, 3 (1982), 473–530.
  * Sohi et al. (1995) Gurindar S Sohi, Scott E Breach, and TN Vijaykumar. 1995.  Multiscalar processors. In _Proceedings of the 22nd annual international symposium on Computer architecture_. 414–425.
  * Soundararajan et al. (2021) Niranjan K Soundararajan, Peter Braun, Tanvir Ahmed Khan, Baris Kasikci, Heiner Litz, and Sreenivas Subramoney. 2021.  Pdede: Partitioned, deduplicated, delta branch target buffer. In _MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture_. 779–791.
  * Spracklen et al. (2005) Lawrence Spracklen, Yuan Chou, and Santosh G Abraham. 2005.  Effective instruction prefetching in chip multiprocessors for modern commercial applications. In _11th International Symposium on High-Performance Computer Architecture_. IEEE, 225–236.
  * Srinivasan et al. (2001) Viji Srinivasan, Edward S Davidson, Gary S Tyson, Mark J Charney, and Thomas R Puzak. 2001.  Branch history guided instruction prefetching. In _Proceedings HPCA Seventh International Symposium on High-Performance Computer Architecture_. IEEE, 291–300.
  * Sriraman et al. (2019) Akshitha Sriraman, Abhishek Dhanotia, and Thomas F Wenisch. 2019.  Softsku: Optimizing server architectures for microservice diversity@ scale. In _Proceedings of the 46th International Symposium on Computer Architecture_. 513–526.
  * Vavouliotis et al. (2021) Georgios Vavouliotis, Lluc Alvarez, Boris Grot, Daniel Jiménez, and Marc Casas. 2021.  Morrigan: A composite instruction tlb prefetcher. In _MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture_. 1138–1153.
  * Xia and Torrellas (1996) Chun Xia and Josep Torrellas. 1996.  Instruction prefetching of systems codes with layout optimized for reduced cache misses. In _Proceedings of the 23rd annual international symposium on Computer architecture_. 271–282.
  * Zhang et al. (2002) Yi Zhang, Steve Haga, and Rajeev Barua. 2002.  Execution history guided instruction prefetching. In _Proceedings of the 16th international conference on Supercomputing_. 199–208.