Welcome

This notebook contains my personal notes for CS6290: High Performance Computer Architecture
offered at the Georgia Institute of Technology. A summary of the course follows:

This course covers modern computer architecture, including branch prediction, out-of-order
instruction execution, cache optimizations, multi-level caches, memory and storage, cache
coherence and consistency, and multi- and many-core processors.

Course links
https://omscs.gatech.edu/cs-6290-high-performance-computer-architecture
https://ebookcentral-proquest-com.prx.library.gatech.edu/lib/gatech/detail.action?
docID=787253

Introduction

What is computer architecture?

We can think of computer architecture similar to how architecture is considered for building.
Buildings are designed to be well-suited for a specific purpose. The same can be said of computers,
as we design different computers for different purposes. Some examples are desktop computers,
laptops, and cellphones; they all have different purposes and require different computer
architectures.
Why do we need computer architecture?
1. To improve performance based upon some specific measure. These measures could include:

Speed
Battery life
Size
Weight
Energy efficiency, etc.

2. To improve the abilities provided by a computer. These abilities could include:

3D graphics
 Debugging support
Security, etc.

The first need for computer architecture is about making computers cheaper, faster, smaller, etc.
while the second need is based around making new things possible/providing new functionality.
Computer architecture utilizes discoveries in fabrication technology and circuit design to achieve the
goals stated above.

Computer architecture and technology trends

Computer architecture is about building future computers. The progress in computer manufacturing
technology is fast. We shouldn't design a new computer with current technology and parts. By the
time we've designed our new computer, it's obsolete and using old technology. We need to track
technology trends in order to predict what's available in the future, allowing us to better design a
new computer using these new technologies.

Moore's law
Moore's law provides a good starting point for predicting what future computers will look like based
upon what is currently available today. As computer architects, we can use these predictions to
guide our expectations of what technologies will be available for use when designing future
computers. Below is a high-level summary of Moore's law:
The memory wall
Processor speed doubles almost every two years, while memory capacity also experiences the same
phenomenon. Memory latency, however, has not kept pace with processor speed and memory
capacity. This is what's called the memory wall and, in order to mitigate these differences in speed
when processors need to access memory, we have been using caches to close that gap. Caches can
be thought of as a series of stairs for memory access speed, and cache misses are the base of the
staircase with the slowest memory access speed possible. A high-level illustration of the memory
wall trend is provided below:
Power consumption
There are two kinds of power that a processor consumes:

Dynamic (active) power - consumed by activity in a circuit

Static power - consumed when powered on but idle

Active power

Below is an illustrative representation of the equation for calculating active power consumption by a
processor. The representation also displays how we can calculate the change in active power
consumption when a different chip configuration is used, and if voltage and chip frequency are
changed. An explanation of each variable in the active power equation follows:

capacitance - roughly proportional to chip area / larger chips will have more capacitance
voltage - quadratic relationship between voltage and power consumption
frequency - clock frequency (GHz) of a processor
alpha - activity factor (percentage of processor transistors active for any given clock cycle)

Static power

Static power is power consumed while the processor is idle. Some of this is due to the voltage being
too low to prevent transistors from leaking/wasting energy, but it can also come from other sources
as well. Below is a high-level representation identifying the relationship between static and active
power as voltage increases or decreases in the circuit. This representation also identifies that there
is some optimal voltage settings for circuits to avoid utilize too much power in bot the active and
static states.

Fabrication cost and yield

The cost to manufacture and convert silicone wafers to useable computer chips is pretty much
static. We, primarily, have to account for chip yield when a silicone wafer is divided into a number
computer chips - some of these chips can have defects while others work fine. Below is high-level
representation of the silicone wafer to computer chip manufacturing process, and how the yield is
derived based upon the number of defects in wafer versus the number of chips extracted from a
wafer.
Below is an example of how we can calculate the fabrication cost per chip based upon chip size.
Smaller chips cost less to manufacture, while larger chips cost the most. Smaller chips, over time
according to Moore's Law, will be able to do more for less as we are able to fit smaller transistors
onto the chips. Larger chips will be able to remain the same size and cost, however, they will be
faster overall due to Moore's Law.
References
1. Lesson 1 Notes

Metrics and Evaluation

This lesson covers latency and throughput, two metrics used to measure computer performance.
Performance
Latency - the total time it takes for an operation to complete, from start to finish.
Throughput - not the inverse of latency; because operations can take place concurrently within
a pipeline, this can be thought of as the number of operations completed per unit measure of
time.

Below is a high-level representation of this concept.

Comparing performance
Knowing how to measure performance, we can now compare the performance of two systems using
our metrics. We want to be able to make a definitive statement about the speedup of a system in
comparison to another system, basically stating that system x is faster than system y. We can
compute this with both latency and throughput, however, our equations are slightly different.
Below is an image showing us the equations for computing speedup using our two metrics.

Speedup
A speedup value larger than 1 means we have improved performance. With improved performance,
we achieve higher throughput and shorter execution time. A speedup less than 1 means that we
have worse performance. When computing speedup, we need to remember that performance is
directly proportional to throughput and performance has an inverse relationship with latency.
Measuring performance
What workload do we use to measure performance of different systems? We can't use an actual
user workload because:

Many different users use computers in many different ways with many different programs.
One workload will not be representative of all users.
How are we supposed to acquire the workload data?

In order to solve this issue, we use benchmark workloads.

Benchmarks
Benchmarks are programs and input data that users and organizations have agreed upon for use in
performance measurements. Usually, we don't have just one benchmark program but a benchmark
suite consisting of multiple programs and input data. Each program within a benchmark suite is
representative of a type of application.

Types of benchmarks
So what types of benchmarks are commonly used to measure performance? We have:

Real applications

Most representative of real workloads.

Also the most difficult to setup on new machines. Our testing environment likely doesn't
have an operating system, hardware, graphics processors, etc.

Kernels

The most time consuming portions of an application, usually a loop of some sort. We've
isolated these processing intensive sections of code to test our machine. Usually good for
testing prototypes.

Synthetic benchmarks

Behave similar to kernels but are simpler to compile. We utilize these benchmarks when
testing early prototypes of a machine. Usually good for design studies.

Peak performance

Performance that's not based on running against actual code. The theoretical highest
number of instructions per second. Usually good for marketing.
Benchmark standard
So how are benchmark suites created? Who makes them and what are the standards? There exist
standards organizations that receive input from manufacturers, user groups, and experts in
academia and these organizations produce standard benchmark suites. Some well known standard
benchmark suites are:

TPC - Benchmarks used for databases, web servers, data mining, and other transaction
processing. [1]
EEMBC - Used for embedded processing. [2]
SPEC - Used to evaluate engineering work stations and raw processors. SPEC encompasses a
large set of workloads, trying to cover a variety of uses for processors in high performance
systems. A breakdown of these workloads is in the image below. [3]
Summarizing performance
To summarize performance, we are looking for the average execution time. A demonstration on
how to calculate this is shown below. We should refrain from averaging the speedups for each
application tested - averaging ratios will not provide useable data to summarize performance. In
order to acquire the average speedup, we need to use the geometric mean for the execution times
of each computer.

Iron Law of performance

Processor time (CPU time) can be expressed as: (instructions/program) * (cycles/instruction)
* (seconds/cycles)
So why do we think about these components of processor time instead of just measuring processor
time directly? These three components allow us to think about the different aspects of computer
architecture.

(instructions/program) - influenced by the algorithm used to create the program, the

compiler used to interpret and generate the program, and the instruction set being used.
(cycles/instruction) - influenced by the instruction set being used, and the processor
design.
(seconds/cycle) - influenced by the processor design, circuit design, and transistor physics.

Computer architecture primarily focuses on instruction set and processor design, and good designs
of these two aspects attempts to balance their effects on CPU time.
Iron Law for unequal instruction times
It's pretty simple to calculate CPU times when we assume that all instructions for a program will take
the same amount of cycles to execute. This isn't always the case, however. We need to be able to
sum all the cycles for each type of instruction before we multiply this with our time per cycle. Below
is a representation of this concept, showing us how to calculate a more realistic CPU time.

Below is an example problem in which we calculate the sum of cycles for a program in order to
determine the CPU time.
Amdahl's Law
This law is useful when we need to calculate the overall speedup of the entire program, but we only
enhanced a fraction of the program. Below is an image that attempts to explain the equation for
Amdahl's Law, a description of each variable in the equation is provided:

(1 - frac_enh) - the fraction of the program that wasn't enhanced.

frac_enh - the fraction of the program that was enhanced.
speedup_enh - the speedup achieved due to the enhancement.

It's very important to understand that frac_enh is a percentage of the original execution time that
is affected by the enhancement.
Implications

It's important to aim for enhancements that achieve a speedup on a larger percentage of execution
time for a program. This is demonstrated mathematically below.
Below is an example of how to use Amdahl's Law to compare multiple possible improvements.
Lhadma's Law
This law is jokingly used to express the opposite of Amdahl's Law. While Amdahl's Law says to
optimize for the common case, Lhadma's warns us that we should avoid attempting to optimize too
much at the expense of other parts of our performance. An example is provided below.
Diminishing returns
This concept covers the idea that as computer architects, we need to continuously review what
needs to be enhanced within a system instead of continuously enhancing the same portion of a
system. This concept stems from Amdahl's Law, as it describes that, eventually, the enhanced
portion of a system will become smaller as we apply enhancements across generations. We will
achieve a diminished speedup if we continue to enhance the same portion of the system. We need
to continually reassess what is the common case when conducting our enhancements. Below is a
high level representation of this idea.
References
1. http://www.tpc.org/tpch/
2. https://www.eembc.org/
3. https://www.spec.org/benchmarks.html
4. Lesson 2 Notes

Pipelining
This lesson reviews pipelining to set the stage for more advanced topics.
Pipelining in a processor
This section covers basic pipelining in a processor. Most processors are much more complex than
the example provided here, however, this is used to review content for students.

In a traditional processor pipeline, we have are series of stages. The following listing of stages is not
all stages, but it encompasses the important ones:

fetch
read
decode
execute
memory access
write

So how does pipelining apply to these stages? Instead of fetching, decoding, and executing one
instruction at a time, while one instruction is being decoded, another instruction can be fetched
from instruction memory. Then, when one instruction is being executed, we can be decoding the
instruction behind it. So, while the latency may not change, the throughput of instructions through
the pipeline increases. Below is a high level representation of this concept:
Below is an example of calculating the latency of process with and without a pipeline.
Below is a similar example as the one above, however, this one applies to instructions and cycles.

Pipeline cycles per instruction

Throughout these notes we've been assuming one cycle per instruction, or a CPI of 1, when our
pipeline is full. In the real-world, however, we'll have billions of instructions to execute - will our CPI
always be 1? Here are some reasons why our CPI might not be 1:

initial fill - when the pipeline initially fills up, our CPI will not be equal to 1. Regardless, as our
instruction number reaches infinity, CPI will begin to approach 1.
pipeline stalls - there exists the possibility that a fault occurs in the pipeline and an instruction
stalls, causing it to have to remain at that stage for a cycle.

Below is a high-level representation of how a CPI can be greater than 1.

Processor pipeline stalls
A processor pipeline stall usually occurs when some instructions depend upon the outcome of
previous instructions that conduct a read/write. In the example below, the program loads a value
into a register, increments the register, and then stores that value into a different register. The load
operation must occur before the increment and load instruction, otherwise the increment
instruction will be incrementing an incorrect value. Because of this dependency, a processor pipeline
stall occurs, and a bubble in the pipeline is created. The increment instruction must wait two cycles
until the memory is read and written into the register that is to be incremented.

This phenomenon causes our CPI to be greater than 1.

Processor pipeline stalls and flushes
A processor pipeline flush occurs when the processor pipeline fetches and decodes instructions that
aren't actually supposed to be executed, so they're removed from the pipeline and replaced with
bubbles. Below is an example demonstrating what happens when a JMP instruction is introduced
into the pipeline. Some instructions behind the JMP are fetched and decoded, however, they are
fetched from an incorrect location in memory. After the ALU determines the destination of the JMP ,
instructions from the JMP destination are fetched and decoded, and the instructions that weren't
destined to be executed are flushed from the pipeline.

This is another phenomenon that could cause the CPI to be larger than 1.
Control dependencies
The problems described in the previous sections that cause these processor pipeline stalls are called
control dependencies. The example provided below provides a high-level representation of a
control dependency. In the scenario, a branch instruction will jump to some label in code, however,
to sections of code depend upon the branch: the code directly after the branch and the code
contained at the label.

This example also shows us how to predict the CPI based upon this concept of control
dependencies. Given a percentage of instructions are branches, given that a percentages of
branches are actually taken, and given that we know that the fetching and decoding of control
dependencies causes at least two bubbles in the pipeline, we can calculate the increase in CPI from
its normal value of 1.
In later discussions, we will cover a concept called branch prediction that is designed to mitigate
the occurrence of these bubbles within the pipeline by predicting where a branch will land in order
to fetch and decode the correct instructions. Control dependencies can cause even more bubbles to
form in a pipeline if the pipeline contains more than 5 stages, so these issues definitely need to be
mitigated to increase performance and normalize the CPI.

Below is an example question from the lectures that asks us to determine the CPI given a
percentage of branches/jumps taken and when the branches/jumps are computed in the pipeline.
Data dependencies
Briefly described in this section, data dependencies occur when one instruction depends upon the
outcome of another instruction. TODO types of dependencies exist:

read after write (RAW) - type of dependency in which one instruction relies upon the previous
instruction writing some data that will be used by the dependent instruction. This type of
dependency is also called a flow dependence because the data flows from one instruction to
the other. This type of dependency is also called a true dependency because the value being
used by the dependent instruction doesn't exist until the previous instruction writes.
write after write (WAW) - type of dependency in which the order of write operations needs to
be preserved. The example provided uses registers, in which a specific value is expected to be
within R1 for future instructions. These writes will not be able to to be conducted out of order
 - they both write to the same location. This type of dependency is also called an output
dependency.
write after read (WAR) - type of dependency in which a previous instruction needs to read
some data, but a future instruction intends to write to that data. These instructions can not be
interleaved, the previous instruction expects the data to be unchanged upon read. The read
will take place before the write, creating the dependency. This type of dependency is also called
an anti-dependency because it reversed the RAW dependency.

The WAW and WAR dependencies are called false or named dependencies. Read after read (RAR)
is not a dependency.

Below is an example from the lectures inspecting a series of instructions to determine what data
dependencies exist.
Data dependencies and hazards
A hazard is when a dependence results in incorrect execution of an instruction. In the example
provided below, there are three instructions that have dependencies but their dependencies will not
result in incorrect values being used for execution.

The DIV instruction, however, will be using a stale value for R4 when it executes and writes to R10
because, when the DIV instruction reaches the decode stage of the pipeline, the SUB instruction
has not yet written its value to R4 .

Hazards can both be a property of the program as well as because of the pipeline. Another example
provided in the image below shows that, in this 5 stage pipeline, true dependencies do not create a
hazard when 3 or more instructions separate the dependent instructions. This is because, by the
time the first instruction in the dependent pair executes and writes, the second dependent
instruction is still being fetched.

Below is an example problem with a 3 stage pipeline, demonstrating how we can inspect
instructions to determine dependencies and hazards.
Handling of hazards
We need to introduce mechanisms to handle hazards we detect in order to protect our CPI and
performance. We don't care about all dependencies that are introduced, only the ones we know will
cause incorrect execution. These are our possible mitigation techniques:

Flush dependent instructions - used for control dependencies. We don't intend to execute
instructions introduced into the pipeline by control dependencies.
Stall dependent instructions - used for data dependencies in order to prevent instructions
from reading invalid values.
Fix values read by dependent instructions - also used for data dependencies, this introduces
the concept of forwarding, providing the a dependent instruction with the value it needs to
 correctly decode and execute.

Below is a high-level representation of these hazard handling mechanisms.

Below is an example problem with a 5 stage pipeline and a series of instructions containing multiple
dependencies and hazards that must be avoided. This example demonstrates how we can use the
pipeline to determine when it is appropriate to flush, stall, or forward to handle hazards.
How many stages?
In the pipelines we've reviewed, the ideal CPI is 1. Later in the course, pipelines with a CPI higher
than 1 are expected because the pipeline is attempting to execute more than one instruction per
cycle. Regardless, each pipeline setup has an ideal CPI that it attempts to achieve.

So what happens if we add more stages? Well, we get more hazards. If a branch is resolved in the
third cycle of a pipeline, we only have to flush the two previous instructions that were fetched and
decoded. If a branch is resolved in, for example, the tenth cycle of a pipeline, now 9 instructions
have to be flushed from the pipeline - kinda wasteful. With more hazards, our CPI also increases.

Inversely, with more stages in our pipeline there's less work being done per stage, decreasing our
cycle time - we can execute cycles faster. Remember the Iron Law?
CPU time = #instructions * CPI * cycle_time

If our number of instructions stays the same, but our CPI increases and our cycle time decreases, we
achieve a balance even with this longer pipeline. We carefully choose the number of stages in our
pipeline to balance the relationship between CPI and cycle time.

Modern processors achieve the most performance with a processor pipeline of 30 - 40 stages as this
strikes a perfect balance between cycle time and CPI. This is great, but with an increase in number or
processor pipeline stages, we also draw a lot of power because we execute a lot of cycles per
second. Thus, a reasonable number of stages for the processor pipeline of modern processors is 10
- 15 stages as this strikes the best balance between performance and power.

Below is a high-level representation of the concepts described above.

References
1. Lesson 3 Notes

Branches
In the previous pipelining lesson, we saw the effects that hazards have on performance. Branches
and jumps are common instructions that introduce control dependencies - our only solution can't
just be to flush the processor pipeline each time a branch or jump is decoded. This lesson covers
techniques used to effectively avoid hazards introduced by control dependencies.

Branch in a pipeline
The example provided below uses a 5 stage processor pipeline to demonstrate the costs of incorrect
branch prediction. The example explains how a branch instruction works: is registers R1 and R2
are equal, the immediate value represented by Label will be added to the program counter, PC ,
and execution will begin at that location in memory. Otherwise, the program counter will be
incremented regularly - R1 and R2 are not equal.

In this scenario, a branch instruction enters the pipeline at cycle 1. The branch instruction isn't
evaluated until cycle 3 by the ALU. Meanwhile, two instructions are fetched and decoded - these are
represented by a ?? because the instructions can be fetched either from memory directly after the
branch instruction or the landing location in memory if the branch instruction is taken.

If we predict the outcome of the branch instruction correctly, the instructions that were fetched and
decoded will execute immediately after the branch instruction leaves the pipeline - the branch will
have taken 1 cycle to complete. If we predicted the outcome of the branch incorrectly and loaded
the wrong instructions into the pipeline, these instructions will have to be flushed and the branch
will have taken 3 cycles to complete.
References
1. Lesson 4 Notes

Prediction

Branch prediction requirements

What do we need in order to successfully predict whether a branch will be taken or not? What do
need in order to determine where the branch is going if it's taken?
The requirements are as follows:

Branch prediction needs to work using only the knowledge of where we fetch the current
instruction from.
We need branch prediction to guess the program counter of the next instruction to fetch.
With branch prediction we must correctly guess:
Is this a branch?
If it is a branch, is it taken?
If it is a taken branch, what is the target program counter?

Branch prediction accuracy

The image below demonstrates how we can calculate the theoretical CPI of a processor using branch
prediction given its branch prediction accuracy, penalty per missed prediction, and percentage of
instructions that constitute branches within a benchmark program. The equation is contains these
components:

base CPI - in the example below, this is 1 .

predictor accuracy - this is the number of mis-predicted branches per instruction.
penalty incurred - the penalty is dictated by the number of stages in a pipeline and when the
branch instruction is evaluated.

A more accurate branch predictor increases our performance, decreasing the number of penalties
taken for mis-predicted branches, thus decreasing our CPI. The amount of help a better predictor
has changes depending upon how long the processor pipeline is. Longer pipelines benefit more
from better branch prediction than shorter ones.
Below is branch prediction example problem. The key to this problem is the fact that no branch
prediction is being conducted so, until each instruction is decoded, another instruction will not be
fetched, thus creating a bubble within the pipeline. So, non-branch instructions will take 2 cycles to
execute and branch instructions will take 3 cycles to execute. Instructions will not be fetched after a
branch instruction is decoded because the branch instruction still has to be evaluated prior to
fetching from the possible branch destination.

In contrast, each instruction for the perfect branch predictor takes 1 instruction, no bubbles exist
within the processor pipeline. This is because the branch predictor knows which instruction will be
fetched next before the previous one is decoded - including the branches.
Performance with not-taken prediction
A simple implementation of branch prediction that has an increase in performance over just not
predicting branches at all is the prediction that all branches are not taken. If no predictions are
made, ever, and instructions are only fetched after previous instructions are decoded, branches will
always take 3 cycles in our example 5 stage pipeline and regular instructions will take 2 cycles.

If we always assume the branch is not taken, sometimes we'll be right and the branch will only use 1
cycle, while sometimes we'll be wrong and the branch will use 3 cycles - this is still better than
making no predictions at all. In this model, regular instructions only take 1 cycle, as well.
Predict not-taken
The predict not-taken predictor is the simplest predictor we can have, all it does is increment the
program counter. No extra hardware is required to support the predict not-taken predictor - we
should always have the ability to increment the program counter.

A rule of thumb in computer architecture is that 20 percent of all instructions are branches. For
branches, about 60 percent of all branches are taken. Thus, the predict not-taken predictor is
correct 80 percent of the time (because of non-branch instructions), plus another 8 percent of the
time (because of branch instructions). Overall, the predict not-taken predictor is incorrect 12 percent
of the time.
Why do we need better prediction?
The image below provides examples for different types of pipelines, showcasing the differences in
performance using a predict not-taken predictor and a branch predictor that is correct 99 percent of
the time. As you can see, as the processor pipeline gets longer and more complex, conducting more
instructions per cycle, branch prediction becomes really important for performance. The ability to
accurately predict branches achieves a speedup of 4 for the case of the 14 stage pipeline with 4
instructions per cycle.
Predictor impact quiz
Below is an example quiz that demonstrates how we can determine the impact of a predictor on the
CPI of a processor pipeline. Given some metrics about the Pentium 4 processor, we are given a final
CPI but not the theoretically ideal CPI of the pipeline. Using the metrics given, we have to derive the
ideal CPI and then calculate the new CPI given a different mis-prediction percentage for our
predictor.
Why we need better prediction, part 2
The below image displays how wasteful flushing the processor pipeline is when we fail to accurately
predict branches. Depending upon how many stages are within a pipeline, while also accounting for
the fact that we could execute multiple instructions per cycle, we see that would fetch and flush
anywhere from 2, to 10, to 40 instructions - pretty wasteful.
How do we get better prediction?
In a previous section, we discussed the requirements that needed to be met in order to conduct
branch prediction. In the image below, the lecture discusses that we don't have the ability to
determine if the instruction is a branch, if the instruction is taken, or what the offset of the branch is
because we still have yet to fetch the instruction.

What we do know, however, is that, based upon the program counter, we have a historical
precedence for what happened at this program counter in the past. We know how the branch at this
program counter was behaving in the past - we can use this information because it's pretty common
that branches tend to behave the same way each time they are encountered.

We don't know what the current branch instruction to be fetched is going to do, but we can make a
prediction based upon its history / the last time it was executed.
Branch Target Buffer (BTB)
The simplest predictor that uses history is the branch target buffer. So how does it work? The
program counter (PC) is used to index into the BTB. Stored at this index is the predicted next
program counter. The next program counter is fetched into the pipeline. When the branch is
calculated, the real next program counter is determined and compared against the predicted next
program counter that was fetched. If they're the same, the BTB predicted the next program counter
correctly based upon the historical data saved for the program counter used as an index. If they're
not the same, the BTB predicted incorrectly and the next program counter is saved to the BTB using
the index program counter.
How big does the BTB need to be to implement the predictor? Well it serves the purpose of
predicting the next instruction based upon the current instruction in the program counter. So in
order to feasibly predict every next instruction, we need to have an index for every instruction in the
program - meaning the BTB needs to be the same size as the program itself! That's not realistic, let's
see if we can't find another answer.
Realistic BTB
First, we don't need an entry in the BTB for every single instruction in the program - we can have the
BTB contain only the instructions that are most likely to be executed next. The BTB will operate
somewhat like a cache, using values that are most recently used. An example provided in the lecture
is a loop that contains, say, 100 instructions. As the loop executes, the BTB fills with the loop's
instructions and the BTB doesn't change for the duration of the loop.

So how do we avoid program counter index collisions in the BTB? We use a mapping function that's
simple enough to execute within one cycle. In the example provided, if the BTB contains 1024
entries, we use the last 10 bits of our 64 bit program counters as indices. Why are we using the LSB
of our program counters? Because as a program increments, these values are what changes when
each instruction is executed.
BTB Quiz
In the quiz below, we would think that we would just use the last 10 bits of the program counter,
however, because our architecture enforces 4 bytes instructions that are word-aligned, each entry in
the BTB needs to be even and also divisible by 4. So, in a BTB of 1024 entries, we would only be
using 256 of the values - that's a lot of wasted entries.

Our solution is to ignore the last 2 bits of the program counter and use the 10 bits to the left of these
ignored bits - these bits are the ones that are most likely to change. Using this indexing function, a
program counter of 0x0000ab0c will be contained at BTB index 0x2c3 .
Direction Predictor
We further simplify our branch predictor by adding another abstraction, the branch history table.
This table contains a 1 or 0 for each different program counter that indexes into it - we calculate
indices just like we did with the BTB (using the LSBits of a program counter that are most likely to be
unique).

The 0 represents that the branch is not taken. The program counter is incremented and we begin
fetching instructions from that location. No changes are made to the BTB because no branch was
taken.

The 1 represents that the branch is taken. The BTB is referenced to determine the next program
counter based upon the current one being inspected, and we begin to fetch instructions from that
new location.

If the prediction made is incorrect, the branch history table is updated with the correct value at the
index - 0 or 1 . If a not taken prediction was made and this prediction ended up being incorrect, we
update the BTB with the next program counter that is the destination of the branch.

Because the branch history table is only 1 bit for each index, we can have way more entries for
unique program counters. This way, we can use the BTB only for branches and not just regular
instructions.

BTB & BHT Quiz

The below quiz excerpt demonstrates that the BHT needs to be accessed for each instruction.
BTB & BHT Quiz 2
The below quiz excerpt demonstrates how the BHT is indexed using the program counter.
BTB & BHT Quiz 3
The below quiz excerpt demonstrates the conditions required to access the BTB.
BTB & BHT Quiz 4
The below quiz excerpt demonstrates how the BTB is indexed using the program counter.
BTB & BHT Quiz 5
The below quiz excerpt demonstrates how we can calculate the number of mis-predictions for each
instruction using an imperfect BHT.
Problems with 1 bit prediction
So what's wrong with the 1 bit predictor? Why does its performance not satisfy the needs of
computer architecture designers, creating the need to research pattern predictors?

The 1 bit predictor predicts these things well:

Branches that are always taken

Branches that are always not taken
Branches that are taken A LOT more often than not taken
Branches that are not taken A LOT more often than taken

The example below demonstrates how, when a 1 bit predictor encounters an anomaly in
predictions for a particular branch, this can incur two mis-predictions.
The 1 bit predictor does not perform well when:

Branches are taken more often than not, but not by much
Branches are not taken more often than not, but not by much
Encountering short loops

The 1 bit predictor will be bad when:

Branches taken and not taken are about the same in number

2 Bit Predictor
A 2 bit predictor or 2 bit counter (2BP or 2BC) just adds another bit to the BHT to implement a state
machine. The first bit in the 2BP is the prediction bit, and the second bit is called the hysteresis or
conviction bit. These are the states of the 2BP:

00 - strong not-taken state

 01 - weak not-taken state
10 - weak taken state
11 - strong taken state

You can probably see where this is going. We start out in the strong not-taken state for a program
counter. When we mis-predict that a branch is not-taken, we increment the hysteresis bit and
transition to the weak not-taken state. We still don't take the branch until we are proven incorrectly
again. A mis-prediction at this point will transition us to the weak taken state.

So unlike the 1 bit predictor, our affinity to take or not take a branch doesn't flip as easily. This solves
the problem we had earlier where, if we encountered an anomaly for a branch that is usually taken
or not taken, we won't incur a penalty of two mis-predictions.
2 Bit Predictor initialization
The below excerpt from the lectures demonstrates that it's a good idea to initialize the 2 bit
predictor in a weak state, doesn't matter if it's taken or not taken. This is because, at program start,
we don't know the history of the branches, yet, so starting in the weak state only incurs 1 mis-
prediction penalty while starting in a strong state incurs 2.

On the flip-side, if a branch flip-flops and we start in the weak state, we will incur a mis-prediction
penalty every single time we encounter the branch. This isn't common behavior (fortunately).

The evidence provided above would give you the idea that we should always init the 2 bit predictor
in the weak state, but for the sake of practicality, it really doesn't matter and most 2 bit predictors
are initialized at 00 .
2 Bit Predictor Quiz
The below quiz excerpt from the lectures demonstrates how there is a worst-case scenario for the 2
bit predictor, showcasing a series of branches that will cause the predictor to mis-predict every
branch.

The moral of the story is, every predictor will have a worst-case scenario. A good predictor will make
it difficult to find or generate this worst-case sequence of branches.

1 bits, 2 bits... what else?

So we've seen that the 2 bit predictor is better than the 1 bit predictor at handling anomalous
outcomes. Does this get better if we add 3 bits to the predictor? Well, maybe. Another bit will just
increase the number of states, making it more difficult to transition to another prediction - this is
useful if the anomalous behavior comes in streaks. This behavior is not common, however , in
programs. Adding another bit imposes more cost, as it requires more space to store the information
per program counter.

A 2 bit predictor meets the needs we identified earlier of handling anomalous behavior, but what
about that one case where the branch outcome kept flip-flopping? Since increasing the number of
bits to solve this problem doesn't really do anything, what's the next solution?

History Based Predictors

History Based Predictors are designed to recognize and learn patterns based upon the history of
taken or not taken outcomes of a branch. Below is an example that provides a high-level
representation of the concept. The flip-floppy branch outcomes are definitely predictable, just not
with simple N-bit counters.
1 Bit History w/ 2BC
Below is an excerpt from the lectures that provides a high-level representation of a BHT with 1 bit
for history, and two 2BC's to manage the state for taken and not taken branch outcomes.

What the 1 bit history 2BC BHT provides us is a predictor that is able to learn the pattern of a series
of branch outcomes. The 1 bit history bit is used to index into the two 2BC's and, based upon the
branch outcome, updates the state of each 2BC.
1 Bit History Quiz
Below is an a quiz excerpt from the lectures demonstrating the calculation of the number of mis-
predictions for a pattern of branch outcomes following the this pattern: (NNT)* . As we can see from
the outcome of the calculations in the quiz, the 1 Bit History with two 2BC's is not a good solution for
this pattern.
2 Bit History Predictor
The 2 Bit History Predictor works very similar to the 1 Bit History Predictor, now we've just doubled
the number of 2BCs. The 2 Bit History bits are used to index into the four 2BCs. The total cost of the
predictor is 10 bits per branch. Below is a high-level representation of how a 2 Bit History Predictor
can perfectly predict the (NNT)* sequence.
Thinking more about our history predictors, some things become evident. For an N-bit History
Predictor:

We can perfectly predict all patterns of length less than or equal to N+1 .
The cost for an N-bit History Predictor is N + 2 * 2^N per entry
This is wasteful, most of the 2BCs will go unused.
N-bit History Predictor Quiz
The below quiz is an excerpt from the lecture, outlining the cost and waste of different size N-bit
History Predictors.
History Predictor Quiz
The below quiz is an excerpt from the lecture, demonstrating how to calculate the number of entries
in a history predictor necessary to support a branch outcome pattern generated by these two for
loops. As you can see, a lot of 2BCs are wasted just to support an 8 bit history.
History w/ shared counters
As we discussed earlier, N-bit history predictors use 2^N counter per entry, even when we only use
N counters to solve a pattern of N branch outcomes. The idea proposed is to share 2BCs between
program counter entries. We only use N counters for N branch outcomes, so with enough counters
there's a possibility that we can share without having conflicts.
In the excerpt below, we see that designers use the pattern history table abstraction to maintain
history pattern history information in a different table , separating it from the BHT. This way, 2BCs
can be shared across multiple program counters.

Program counters reference into the PHT in the same way they did with the BTH and BTB, using the
least significant bits that are unique. Some translation logic is used to XOR the bits of the program
counter and the pattern history information from the PHT to reference the appropriate 2BC for the
program counter's pattern.

In this example, the size calculation for these two tables is explained, and the overall cost is much
less than the previous implementation of the N-bit history predictor.
The below excerpt showcases how the BHT is used more efficiently with this design. Patterns that
are simple will only end up using 1 2BC, while other patterns that have longer patterns will be able to
utilize more counters because less space is taken up by the patterns of other branches. The only
cost appended to this design is the creation of the pattern history table. Keep in mind, with the
indexing logic shown, it is still possible for branch entries to collide in the BHT.
PShare and GShare
The tail end of the history based predictor lesson describes the beginnings of what's known as the
PShare predictor. What does PShare stand for? Private history for each branch and Shared
counters so that different histories and counters might share the same counter. The PShare
predictor is good for flip-floppy branch outcomes and 8-iteration loops.

In contrast, we have GShare with Global history and shared counters. What does global history
mean? It means we have single history that is used to predict all branch outcomes. So every history,
regardless of program counter, is used to calculate the counter for prediction. The GShare predictor
is good for correlated branches.

What's a correlated branch? These are branches whose decisions rely upon what other branches in
the program are doing. An example is provided in the excerpt below, showcasing a decision
statement where one of two actions will take place depending upon the value of a shape variable.
Only one branch will evaluate to try, thus they are correlated branches.

PShare vs GShare Quiz

Below is a quiz excerpt from the class explaining the differences between PShare and GShare. Given
some C code, we are provided what the C code would resemble in assembly and then asked to
determine how many bits of history would be required to support the branches in the code using
both PShare and GShare.

The quiz demonstrates that it would be easy to predict the first and last branches and that they
don't require any history support. The first branch will have the outcome of not taken 1000 times,
and the last branch will have the outcome of taken 1000 times. The second branch, however, will
flip-flop between taken and not taken, as each different integer will evaluate as even or odd. Thus
our PShare predictor will need 1 bit of history to support perfect prediction of this branch's
outcomes.

In contrast, GShare will require 3 bits of history to support the branches on a global scale and in
order to correctly predict the branch outcomes. Again, the first and last branch outcomes are
unlikely to change, however, the second branch will flip-flop thus we need 3 bits of history to
represent the correlation between these branches. When we see that the first branch was not taken,
we'll also see the second branch either being taken or not taken, and if the first branch wasn't taken
we know that the third branch is taken.
PShare or GShare
Historically, designers would pick one or the other of these history based predictors. Eventually,
designers realized they would need to use both as GShare works well with predicting correlated
branches and PShare works better with self similar branches.

Tournament Predictor
As we discussed in the PShare and GShare section, designers desired to use two predictors to
handle different cases of branches - correlated branches and branches that were self similar. But
how do we determine which predictor will be used for a program counter (instruction) if we don't
know what type of branch it is ahead of time?

The high-level representation below explains how the GShare and PShare predictors are both
indexed by the program counter and each predictor provides a predicted branch outcome for that
program counter value. At the same time, we use the program counter to index into a meta-
predictor table that has a 2BC at each index. We use the meta-predictor to keep track of which
shared predictor gives us the correct answer for the program counter the most often.
Return Address Stack (RAS)
So far we've seen branch prediction done for branch and jump instructions, but what about function
ret instructions? Functions are designed to be called anywhere, so their ret address will not
always be the same location in code. This makes them tougher to predict using our current methods
of branch prediction - how do we prevent from fetching instructions from the wrong location when
returning from a function?
The return address stack is a separate predictor used specifically for predicting returns. It operates
similar to the process stack in that it pushes and pops return address for function calls onto the
stack. The primary difference between a process stack and the RAS is that the RAS is a very small
hardware structure designed to make a prediction very quickly.

So what happens when the RAS is full and we continue to call into more functions? We have two
options:

Don't push any more return pointers into the RAS

Wrap around and overwrite RAS entries

So, is it better to wrap around and overwrite RAS entries? The results of a quiz from the class
provides the justification for why it's better to wrap around and overwrite RAS entries. In the
provided justification below, we demonstrate with a high-level diagram that if we don't push new
entries into the RAS when it's full, all we're doing is saving ourselves from mis-predicting older
functions calls for functions that aren't getting called often.

In contrast, if we wrap around the entries in the RAS, we're more effectively using the entires we
have in the RAS to correctly predict immediate function call returns that are more likely to happen
more often.

So how do we know the instruction is a ret?

Right, we can't push and pop values to/from the RAS without knowing if the instruction is actually a
ret , and we only learn what the instruction is if we fetch and decode. Two methods exist:
We can use a predictor to determine if the program counter contains a ret . Once the program
counter is seen, we now know this program counter contains an instruction that is a ret and
we can then push the value onto the RAS.
We can use pre-decoding!
The processor contains a cache that stores instructions that have been fetched from
memory. The processor fetches instructions from the cache unless the processor incurs a
cache miss - then the process will access memory to acquire the next instruction.
Pre-decoding is a process in which we access memory to acquire the next instruction, and
as we acquire the next instruction we decode a little bit of it to determine if it's a ret
instruction. If it is, we store this information with the instruction in the cache.
Predication

Summary
This lesson covers more topics in relation to control dependencies and the hazards they pose. We
covered a bunch of different branch predictors in lesson 4 and we noticed that some branches are
really difficult to predict, even when we use really sophisticated branch predictors.

This lesson showcases how the compiler can help us to completely avoid hard to predict branches.

Predication explained
Like we covered in the previous lesson, with branch prediction we attempt to guess the landing
location of the branch and we begin fetching instructions from that instruction sequence into the
pipeline. If we are correct in our guess, we incur no penalty. An incorrect guess incurs a penalty and,
depending upon how long our pipeline is, this penalty can be huge.

Contrast this with predication. In predication, we fetch instructions from the instruction sequences
of both possible landing locations for a branch. With this technique, even if we guess correctly or
incorrectly, we still have to toss out 50% of the instructions that have been fetched into the
processor pipeline. We don't incur a penalty anymore, however, because we realistically aren't
making a guess, we're just saying yes to both outcomes of a branch instruction.

So if we're always incurring a penalty with predication, in what context is it better than branch
prediction? Here is a breakdown of the examples showcased in the lecture:

Loops - best application is a branch predictor. Loops are easier to predict as the number of
iterations increases. With predication, we would be continuously fetching instructions from the
instruction sequence after the loop, wasting a lot of effort as those instructions will
continuously flushed from the pipeline - the branch that goes back into the loop will be taken
almost always.
Function calls/ret - best application is a branch predictor. The function will always return,
taking the branch instruction. No reason to fetch instructions from the instruction sequence
after a ret.
Large decision statements (if-then-else) - best application is a branch predictor, dependent
upon the size of the instruction sequence that comprises the decision statement and the
length of the processor pipeline. If two directions in a decision statement were both 100
instructions long and the processor pipeline was 50 stages long, if we mis-predict we only incur
a penalty of 50 stages. If we predict correctly, we incur no penalty. In contrast, a predicator will
always incur the penalty of 100 because we load instructions from both possible instruction
sequences following the branch instruction.
Small decision statements (if-then-else) - the best application is predication. If two
instruction sequence outcomes for a branch are both 5 instructions long, we will always incur a
5 instruction penalty with predication. If we use branch prediction and the processor pipeline is
50 stages long, if we make a mis-prediction, we'll have wasted 50 stages. Dependent upon how
accurate the branch predictor is, we might be able to match the performance of predication in
this use case, however, the more inaccurate the branch predictor the less viable an option it
will be for small decision statements.
Conditional move
This section discusses the conditional move instructions available in the MIPS and x86 instruction
sets. The example below covers MOVZ and MOVN :

MOVZ - takes two sources and a destination register. If the third operand is equal to 0 , the
second operand is loaded into the destination register.
MOVN - takes two sources and a destination register. If the third operand is not equal to 0 , the
second operand is loaded into the destination register.

Example x86 CMOV instructions are shown below.

MOVZ MOVN quiz
Below is quiz a on how to convert code that originally contains branch instruction into code that
uses conditional moves to avoid making predictions. This code models a short decision statement
that loads some values into different variables based upon some condition statement.
MOVZ MOVN performance
The excerpt from the lectures below showcases a comparison of the performance between
traditional branch prediction and the translation we did of the instructions to enable predication.
Give a branch predictor that's correct 80% of the time and incurs a 40 instruction penalty if we
encounter a mis-prediction, we average the number of instructions that can executed between the
two branch instruction sequences, 5 * 0.5 == 2.5 , and then we throw in our inaccuracy and
penalty: 2.5 + 0.2 * 40 == 10.5 .

So, on average, the branch predictor in this example incurs 10.5 instructions worth of work to
evaluate and execute this condition statement. In contrast, for predication, all of the instructions are
fetched and executed because we've translated the branch into conditional move instructions. We
incur 4 instructions worth of work to evaluate and execute this condition statement.
MOVx summary
To summarize predication using MOVx :

Needs compiler support to translate eligible condition statements using MOVx instructions
rather than generating branch instructions
Removes hard-to-predict branches, increasing performance
More registers are needed in order to support predication using MOVx
Results from both instruction sequences have to be calculated and stored
More instructions are executed
No branch prediction is conducted, both instruction sequences are executed and their
results are stored in registers
 MOVx is used to select the results of the condition statement

So what portions of this summarized list are absolutely necessary to implement predication? Well:

Compiler support is definitely necessary

The whole purpose of this is to remove hard-to-predict branches
We don't need more registers to store our results - we can conduct comparison directly
against values in memory
We don't need to use MOVx to select results

How do we remove the unnecessary portions of the summarization above? We make all of our
instructions conditional! With this, we can achieve full predication - but it requires extensive
support in the instruction set.

Hardware support for full predication

Usually, we have a separate opcode for conditional move instructions. For full predication, we add
condition bits to every instruction. Below is an excerpt from the lectures showcasing the Itanium
instruction set's use of qualifying predicates in its instructions to support full predication.
Qualifying predicates specify what register will be used to conduct a comparison for a conditional
move.
Full predication example
The excerpt below now shows our previous condition statement convert to a set of instructions that
uses full predication. The first instruction sets the qualifying predicates, p1 and p2 , to 0 or 1
based upon the value of R1 . If R1 is 0 , p1 is set and the instruction predicated by p1 will actually
store its value into R3 after execution. If R1 is not 0 , p2 is set and the instruction predicated by
p2 will store its value into R2 after execution.

So, in the original code with branch instructions, we have the possibility of executing 2 or 3
instructions based upon our prediction, but we still incur a penalty. In our previous examples using
MOVx , we were able to translate the condition statement into a set of 4 instructions. Now, with
hardware support for full predication, we are able to translate this condition statement into 3
instructions.
Full predication quiz
Below is a the full predication quiz solution from the lecture, conducting a performance comparison
between the original branch version of the condition statement code to the full predication
translation.
References
1. Lesson 5 Notes
Instruction Level Parallelism (ILP)

Parallel instruction execution

The below excerpt from the lectures showcases the hazards that can manifest due to data
dependencies in parallel processor pipelines. As you can see here multiple instructions are destined
to be executed and, if all instructions are able to be executed in parallel, it will take 5 cycles to
execute a number of instructions. As the number of instructions approaches infinity, our CPI
approaches 0 .

This isn't realistic - some instructions will depend upon earlier instructions to write values to
registers before the instruction is executed. If this isn't done, we will encounter data hazards
wherein the registers we use for our instructions will contain stale values, ultimately causing the
program to execute incorrectly.
The execute stage
In previous sections of this notebook we discussed forwarding, a technique that can be used to
resolve data dependencies and remove hazards. Unfortunately, this technique wont' work for us
when we're executing instructions in parallel. The instruction that contains the data dependency will
not receive the outcome of the forwarded instruction before it executes because they are executed
in parallel.

In order to remove the hazard related to this data dependency, we must stall the instruction until
the previous instruction executes. Then, we will forward the result of the executed instruction to the
dependent instruction. This will increase our CPI.
RAW dependencies
The below excerpt from the lectures showcases how we can calculate the CPI for a set of instructions
based upon the number of data dependencies that exists between them. As you can see, the more
RAW dependencies that exist, the higher our CPI.
WAW dependencies
The below excerpt from the lectures showcases how a WAW dependency can manifest due to a RAW
dependency in previous instructions. The WAW dependency poses a hazard because the previous
instruction is stalled due to a RAW dependency. If this goes ignored, the dependent instruction in the
WAW dependency will write to a register before the previous write, executing instructions out of
order. In order to solve this, the dependent instruction must be stalled twice so that the previous
instruction can write.
Dependency quiz
Below is a quiz from the lectures in the class that showcases how multiple RAW and WAW
dependencies are handled in the processor pipeline.
False Dependencies
We covered this in previous portions of this notebook, but we'll go over the dependency types once
again. We have true dependencies and false or name dependencies. A true dependency is the RAW
(read after write) dependency - pretty obvious because this is how the program is actually intended
to execute. Both the WAR (write after read) and WAW (write after write) dependencies are false
dependencies. In both of these dependencies, we are re-using registers for instructions when we
could change the registers being used to eliminate the false dependencies completely.

Duplicating register values

This is a complicated technique in which we save multiple versions of a value for a register that is
being written to. In the excerpt below, two different writes occur for the register: R4 . This register is
used in two different read operations, but what value will be used if the register is written twice?

To remove the hazard posed by this WAW dependency, we store both versions of R4 and then each
read operation will utilize the appropriate version based upon the chronological order of the writes.
The third instruction in this example will use the outcome of the write in instruction two for its read
operation, even though instruction four writes to R4 before instruction two does. A future
instruction will use the most previous version of R4 for its read operation, even though the write by
instruction two occurs after the write by instruction four.

Essentially, we are keeping track of all possible versions of a register in a parallel pipeline and
different read operations that require the value of register will use the value generated by the most
recent write operation.
Register renaming
So duplicating and managing register values can get pretty complicated and time consuming.
Another technique processors can use to remove hazards created by data dependencies is register
renaming.

In the below excerpt from the lectures, we define some terms:

architectural registers - these are register names used by the programmer and the compiler.
physical registers - these are the physical registers available to the processor to actually store
real values.
 register allocation table - this is a table used by the processor to translate architectural
register names to physical registers. This table defines which physical register contains the data
for a specified architectural register.

The processor rewrites the program it's executing to use the physical registers. Through register
renaming, it will have more registers available to store values and avoid hazards presented by data
dependencies.

RAT example
The below excerpt from the class showcases how a RAT works. Each time a new value is produced, a
different physical register is used to store that value. Values for registers that are being read are
acquired from the RAT after it translates the architectural name to the physical register. We call the
WAW and WAR dependencies name dependencies because the name is the whole problem. If we
rename the register that the value is being written to for each write, the instructions won't overwrite
the work of the other instructions if they're executing in parallel.

In this example, we can see that each write increments the physical register number that's being
written to. This removes the hazard of a register being overwritten by a later instruction before an
earlier instruction can conduct its write. Because the writes are to different physical registers, when
an instruction is decoded and needs to read a register, the value it's reading is going to be from the
instruction prior, not the most recent write to the register.

Register renaming quiz

Below is a quiz for register renaming from the lectures. Pretty straightforward.
False dependencies after renaming
So does renaming actually remove our WAR and WAW dependencies? Yes! In the below excerpt from
the lectures we are shown a program that contains a set of dependencies for each instruction.
Because each instruction has these dependencies, they must be executed in order, causing us to
have a CPI of 1 . However, with renaming, we are able to eliminate the WAR and WAW dependencies
improving our performance to a CPI of 0.33 .
What is ILP?
Instruction level parallelism (ILP) is a property of a program given the fact that it's running on an
ideal processor. What's an ideal processor? An ideal processor has these attributes:

Processor dispatches an entire instruction in 1 cycle.

Processor can do any number of instructions in the same cycle.
The processor has to obey true dependencies when doing this.

So what are the steps to acquire the value of a program's ILP? A program's ILP is equal to the IPC
when executing on an ideal processor following the rules stated above. Obviously ideal processors
like this always aren't achievable, the ILP for a program will be different on actual real-world
processors. ILP gives us a value, however, for the parallel nature of program - defining how many
true dependencies exist within the code.
The steps to acquire the ILP of a program are:

1. Rename the registers, as shown previously.

2. "Execute" the code on the ideal processor.

ILP example
The below excerpt from the lectures showcases how we can compute the ILP for a given set of
instructions: ILP == num instructions/cycles . In this example, the professor identifies the true
dependencies that exists for the set of instructions and sees that the fifth instruction cannot execute
until the writes of instruction one and three are complete. Thus, this program will take 2 cycles on an
ideal processor to execute.

A neat trick that is described in the lecture is that we don't even have to conduct register renaming
in order to calculate the ILP. All we have to do is identify the true dependencies - the register
renaming will take care of the false or name dependencies for us.
ILP quiz
Below is a quiz from the lectures showcase the technique for calculating ILP described above. We
don't conduct register renaming, we just identify the true dependencies to determine on what cycle
instructions are eligible to execute. After we determine the minimum number of cycles to resolve
the true dependencies, we can find the ILP of the program.
Calculating ILP with structural and control dependencies
When calculating ILP, we don't account for structural dependencies. These dependencies result for
architectural issues like not having an adder available for a specific operation, etc. Something
outside of the programmer's control, solely relies with the manufacturing of the processor.

For control dependencies, we essentially ignore them. We assume that we have perfect same-cycle
branch prediction. In the example below, we show that a branch instruction has a data dependency
on instructions prior to it, however, because we have perfect branch prediction we know that we will
jump to the Label . Thus, we fetch the instructions from the Label and execute them, even though
our branch has not been executed, yet.
ILP vs IPC
Below is an excerpt from the class conducting a comparison of the calculations for ILP vs IPC on a
given example processor. The processor has some limitations such as: 2-issue (2 instructions / cycle),
1 MUL and 1 ADD/SUB/XOR components (structural limitations). With this, we calculate the ILP for
the given instructions and then we calculate the IPC twice: once ignoring the structural limitations
and once factoring in the structural limitations.

As we can see, the IPC for a processor can only be equal to or less than the ILP. Real processors will
have limitations and won't always be able to achieve the ILP of a program.
ILP vs IPC quiz
Below is a quiz from the lecture that shows us how to calculate and compare the ILP and IPC of a
program for a given test processor. Note, the processor in this example can only dispatch
instructions in order, thus degrading our performance in comparison with the out of order
processor's we've seen in the past. This limitation causes us to have to stop dispatching instructions
when we encounter a dependency.
ILP vs IPC discussion
This slide sorta restates what we covered earlier - a summary, essentially. The ILP can only be
calculated using the abstract concept of an ideal processor, and it's generally representative of the
best performance of a program. The ILP will always be greater than or equal to the IPC, and the IPC
is calculated using an actual processor with issue and structural limitations.

The limitations for processors and how they affect IPC breaks down like this:
 If a processor narrowly issues instructions (1 - 2 instructions / cycle), and only executes
instructions in order, the processor will mostly be limited by the narrowly issued attribute.
If a processor widely issues instructions (4 or more instructions / cycle) , and only executes
instructions in order, the processor will mostly be limited by the in order attribute.
The best case is when the processor widely issues instructions but also can execute
instructions out of order. To do this, the processor will have to dispatch a lot of instructions
per cycle, eliminate false dependencies through register renaming, and reorder instructions so
they can be executed out of order.

Instruction Scheduling
This lesson covers how instruction scheduling allows us to execute programs faster by dispatching
more than one instruction per cycle while also handling data dependencies.
Improving IPC
As we've seen in previous lectures, there are multiple ways for us to improve IPC:

Handling control dependencies - if we have good branch prediction we can better handle
control dependencies, allowing us to fetch the correct instructions and avoid wasting cycles.
false data dependencies - when we encounter false or name dependencies (WAR and WAW),
we use register renaming to completely eliminate the hazards posed by these data
dependencies.
true data dependencies - we can improve our performance even when RAW dependencies
are present using out-of-order execution. We find instructions that are not dependent upon
the writes of previous instructions and execute those while we wait for the results of an
instruction to be forwarded to dependent instructions.
structural dependencies - to improve our performance we must use wider issuing processors
- we'll be able to dispatch more instructions because we'll have more resources available.

Tomasulo's algorithm
Tomasulo's algorithm is the basis for modern processors' implementation of out-of-order execution.
It solves the requirements for register renaming, and is able to determine which instructions have
input ready and which instructions are dependent upon pending writes. Below is an excerpt from
the class describing what the differences are between Tomasulo's algorithm and how modern
processors are designed.
Tomasulo's algorithm - the big picture
Below is an excerpt from the class drawing out the components that comprise Tomasulo's
algorithm. There are a lot of moving parts and they'll be broken down into more detail later - right
now we're just summarizing the pieces. Here is a quick description of all of the parts:

instruction queue - the instruction queue is pretty self explanatory, this is where instructions
sit and wait to be issued - they are fetched from memory.
reservation station - Tomasulo's algorithm was designed for floating point instructions, so
this is where those types of instructions wait for their required values before being
dispatched. The reservation stations are split into simple instructions that require and adder
and more complex instructions that might require a multiplier. Reservation stations enable
Tomasulo's algorithm to determine which instructions are ready to execute - implementing
out-of-order execution.
 registers - once instructions are dispatched from the reservation stations , the values they
generate are written (broadcasted) to the registers. Instructions in other reservation stations
will be able to acquire their forwarded values so that they can be dispatched as well.

On the left-hand side of this picture, you'll see that there's logic to cover load and store instructions
as well. These were not handled by Tomasulo's algorithm, but modern processors now handle all
instruction types similar to Tomasulo's algorithm. The results of the load and store instructions are
also broadcasted so that other instructions waiting to be dispatched can take advantage of the
values before they are written.

There are three stages of Tomasulo's algorithm:

issue - this is when an instruction is sorted from the instruction queue into either load / store
or a floating point instruction.
dispatch - this is when an instruction is actually executing using processor resources.
write result (broadcast) - this is when the result of the instruction is written to the registers
file for later use by dependent instructions.

Note - the instructions in the reservation stations also have two inputs per station to receive
broadcasts. This is to provide dependent instructions with the necessary values to be dispatched as
early as possible.
References
1. Lesson 7 Notes

Issuing
Here are the steps that occur for issuing in Tomasulo's algorithm:

Take the next instruction, in program order, from the instruction queue.
This must be done in program order in order for register renaming to work correctly.
Determine where input for an instruction originates.
 Are the inputs required located in the register file? Or are we still waiting on an instruction
to generate the necessary values? If we need to wait for an instruction, which one? This
will utilize a RAT.
Find a free reservation station of the correct type (addr or mult).
If all the reservation stations are busy, no instructions are issued this cycle.
Put the instruction in the reservation station.
Tag the destination register for the result of the instruction being issued.
This allows instructions who need this result to be able to reference the correct name and
identify their dependency.

Issuing example
Below is an excerpt from the class that showcases how issuing works. Each instruction is issued from
the example instruction queue, and the instruction queue is shifted when an instruction is
successfully issued. The are plenty of reservation stations available, so no instructions had to wait in
order to acquire a spot in a station.

Following the steps above, before an instruction is issued its inputs must be translated using the
RAT. If the value is available, the instruction will read the input directly from the register file. The
values that instructions generate will be renamed and the RAT will contain the name of the
reservation station for generated values. This way, when other instructions that depend upon a
register value are issued, they will use the input generated from other instructions by using their
reservation station name.
Issue quiz
Below is a quiz from the lectures where we practice the issuing portion of Tomasulo's algorithm. In
this example, we are unable to issue the second instruction because there are no spots left in the
reservation stations. This example is pretty straightforward.
Dispatching
Below is an excerpt from the class that showcases how dispatching works. The results of an
instruction from a reservation station is broadcast - its generating reservation station number is
attached to the value that it's generating. Instructions that depend upon a value from that
reservation station are able to acquire the values necessary to be dispatched, and they will also
broadcast their results in the same manner.
Dispatching when > 1 instruction is ready
Below is an excerpt from the lectures displaying a situation in which more than one instruction in
the reservation station is ready to execute. How do we go about making the right decision for best
performance? There are three options:

Dispatching the oldest instruction first - the most fair option and most balanced for
performance.
Dispatching the instruction with the most dependencies - the highest performance option,
however, it requires us to search all reservation stations and determine dependencies - power
hungry.
 Randomly dispatching - not a bad option, and at some point every instruction will be
dispatched, but performance could be degraded.

Dispatch quiz
Below is a quiz from the lectures on dispatching. The quiz asks why the instruction held in RS3
hasn't executed before the current state of the reservation stations. Three options are given, but
only two are reasonable.

The first option: "It was issued in the previous cycle" is reasonable because there can definitely
be a time in which the instruction was issued too late so it didn't have time to execute.
The second option: "Another instruction was dispatched to the adder" is possible because
maybe RS1 was currently executing on the adder to generate a value.
 The third option: "RS2 is older than RS3" is not reasonable. The whole purpose of Tomasulo's
algorithm is to support out-of-order execution. Instructions will be executed as soon as their
values are available, despite how old an instruction is.

Writing (Broadcast)
Below is an excerpt from the lectures that shows us what happens when a result is written or
broadcasted to the reservation stations and the register file. Some steps take place:

The result is tagged with the reservation station that is generating this result. This combo is
then emitted onto the bus.
The result is written to the register file. We are able to determine what register is being written
based upon the RAT - it will contain the name of the reservation station for the appropriate
register.
The RAT is then updated, clearing the reservation station name from the table and marking the
location for a register as clear.
The spot the instruction held in the reservation station is freed.
More than 1 broadcast?
There are multiple possibilities that we can consider when handling multiple broadcasts. The first
idea is to make more than one bus available - a bus for each dispatch unit in the processor. While
that sounds like a good idea, the number of structural dependencies to implement this doubles for
each bus - that's a lot of resources and more logic is needed in order to correctly direct the different
values being generated.

Another option is to give priority to one dispatch unit over the other, and this is the more likely case.
In the example below, we give more priority to the slower dispatch unit. Why? Because if one
dispatch unit is slower, it's more likely that faster dispatch units are waiting on values to be
broadcasted by the slower one.
Stale broadcasts
Can we have stale broadcasts? Is that really a thing? Not necessarily. In the example below we see
that a broadcast is occurring for RS4 , but there's no entry for that reservation station in the RAT. So
where will this result be written to - what's its destination?

We can see that RS2 is generating a value and it has overwritten F4 , which was the original
destination of RS4 's value - this is perfectly fine and works as intended. RS2 was the only
instruction that depended on the output of RS4 , it will have the value it needs to update F4 . All
subsequent instructions reading F4 will utilize the value generated by RS2 - the "stale" value being
broadcasted by RS4 won't cause any issues.
Review

Part 1
Below is a summarization of Tomasulo's algorithm. In this algorithm, for each instruction we are:

issuing - resolving the registers for an instruction using the RAT and then updating the RAT
with the reservation station name of an instruction generating values.
capturing - capturing output of instructions while in the reservation station.
dispatching - dispatching ready-to-execute instructions.
writing results - broadcasting the results of instructions to instructions capturing output in the
reservation station, updating the register file and the RAT.
An awesome thing to note as that each of these things is happening for different instructions on
each cycle. Every instruction is in one of these stages as we execute instructions out of order.

Part 2
Below is an excerpt from the lecture that provides some further discussion of Tomasulo's algorithm.
Some questions that are posed:

Can we issue and dispatch an instruction in the same cycle? - no, we cannot. During an
issue and instruction is loaded into the reservation station, we won't be able to dispatch it until
we identify that it is ready for executing. While its dependencies may be resolved when being
entered into the reservation station, we won't know it's ready to be dispatched until the next
cycle.
Can we capture and dispatch an instruction in the same cycle? - also no, for similar
reasons as above. Once an instruction has captured all of its necessary values, it still needs to
 be marked for execution after the reservation stations have resolved which instructions are
ready. This can happen if hardware support is available.
Can we update the RAT entry for an issue and a broadcast in the same cycle? - yes, the
broadcast and the issue can procedures can both update the RAT in the same cycle, however,
the issue will be the last to update the RAT. This way, future instructions will reference the
output of the reservation station by the issue, not by the broadcast.

One cycle quiz part 1

Below is a quiz from the lectures where we practice predicting what values will exist in the register
file and the RAT after one cycle takes place. In this example we have a processor that does not allow
issuing and dispatching in the same cycle, but does allow capturing and dispatching and updating
the RAT and writing to the register file in the same cycle.

Given the values provided for the different parts of the scheduler, we are able to determine that the
F1 entry in the RAT will be updated by the instruction being issued, and the register file entry for
F0 will be updated by the broadcast of RS0 . Simultaneously, the entry for F0 in the RAT will be
cleared.
One cycle quiz part 2
Below is a quiz from the lectures where we practice predicting what values will exist in the
reservation station for a cycle of the processor pipeline. We can see that an instruction is issued, an
instruction is freed from the reservation station upon dispatch, the same instruction that was just
issued is able to capture the broadcast of the dispatched instruction.
One cycle quiz part 3
Below is a quiz from the lectures where we predict what instruction will be dispatched from the
reservation station in the example cycle. We can see that, as soon as the instruction in RS1 captures
its required value, it will be dispatched. The instruction in RS2 will not be eligible for dispatch
because this processor does not allow issuing and dispatching in the same cycle.
Tomasulo's algorithm quiz
Below is a quiz from the lectures quizzing us on what is not true about Tomasulo's algorithm. What's
not true? Tomasulo's algorithm does not dispatch instructions in program order and it does not
write results in program order. Tomasulo's algorithm does issue instructions in program order.
Load and Store
Now that we've discussed how Tomasulo's algorithm handles data dependencies for floating point
instructions, how does it handle memory dependencies? Well first, what memory dependencies are
there? They're actually the same three categories as data dependencies:

RAW - an instruction stores a word to some address and then a different instruction loads a
word from that same address - this is a true dependency.
WAR - an instruction loads a word from memory and then another instruction stores a word
into memory; if these instructions got re-ordered, we could possibly load the value from the
store, thus giving us incorrect program execution.
WAW - two instructions both write to the same address; if these instructions are re-ordered,
it's possible that a stale value is written to the address.

So what do we do about this?:

In Tomasulo's algorithm, we execute load and store instructions in order. Even if a load
instruction is ready to execute, it will be stalled until the store instruction preceding it is
completed - even if that store instruction is stalled waiting on some value.
Modern processors identify dependencies, re-order load instructions, etc. similar to how
floating point instructions are handled by Tomasulo's algorithm. These techniques will not be
discussed in this lesson, however, they will be touched upon later.

Timing
Below is a quiz on timing from the lecture. Now that we understand the inner working of Tomasulo's
algorithm, we predict how long it takes for instructions in the queue to execute based upon the rules
provided.
Timing quiz part 2
Below is the second part of the previous quiz. Of note, instruction 5 is unable to be dispatched until
cycle 11 because the reservation stations are held by instructions 3 and 4. Instruction 6 cannot be
issued until instruction 4 completes its write back and is cleared from the reservation station.
Reorder Buffer (ROB)
Processors can improve performance a lot by reordering instructions. But what happens when the
reordering of instructions causes exceptions to happen, like division by zero? This lesson explains
how processors cleanup reordered instructions when exceptions happen.

Exceptions in out-of-order execution

Below is an excerpt from the lecture showcasing how exceptions can negatively affect processors
that support out-of-order execution. As we can see in this example, instruction 1 takes 40 cycles to
complete, however, it encounters an exception where a divide by zero was attempted.
The program counter is saved and an exception handler takes over. After the exception handler
executes, the program is restarted from the DIV instruction. Unfortunately, the other three
instructions have already executed and have written their results to the registers - thus the DIV
instruction will be using the incorrect value for F0 and it will not execute as intended.

Branch mis-prediction in ooo execution

Below is an excerpt for the lecture covering how branch mis-prediction can also negatively affect our
ability to execute instructions out-of-order. In the provided example, the outcome of a DIV
instruction determines the jump location for the succeeding BEQ instruction.

In this example, mis-predicting the branch causes us to fetch and execute the succeeding ADD
instruction, writing values to R3 . Now, when the branch is actually evaluated and executed, we jump
to the real landing location of the branch, however, because of ooo execution our value for R3 has
been modified incorrectly - succeeding instructions will not execute as intended.
Another example is provided in which we mis-predict the branch and fetch a DIV instruction. This
DIV instruction causes a divide by zero exception, but the DIV instruction was never meant to be
executed - a phantom exception . The processor goes through all of the steps to handle the
exception when, in reality, we were never supposed to execute the DIV anyways.

Correct ooo execution

Below is an excerpt from the lectures explain what needs to be done in order to achieve correct ooo
execution. We can still execute instructions and broadcast their results ooo, however, we must
deposit the resulting values of instructions to registers in order - this is not done by Tomasulo's
algorithm which is why we are having problems handling exceptions.

We utilize a mechanism called the reorder buffer that remembers program order, even after the
issue stage, and keeps results of instructions until it is deemed safe to write these results to
registers.
References
1. Lesson 8 Notes

ROB In Depth

Part 1
The below excerpt from the class gives us a high-level representation of the components of the
reorder buffer. The reorder buffer is a table of values, this is what each column represents:
 reg - the target register for writing
val - the result of an instruction
done - determines if the data contained in the value column is valid for writing

The reorder buffer also uses two pointers for commit and issue, helping to maintain the results of
the instructions in program order. As new instructions are issued they are enqueued into the buffer
using the issue pointer. The commit pointer points to the oldest instruction that will be written to its
respective register. The instructions between the commit and issue pointers have been deemed
valid for writing.
Part 2
The below excerpt from the lectures shows, in detail, how the ROB mechanism is appended into
Tomasulo's algorithm to support handling exceptions for ooo execution.

The changes that are made to the algorithm are:

During an issue operation, the RAT now uses the name of the ROB entry for a register instead
of the reservation station.
During a dispatch operation, the reservation station can be immediately freed because the
results of the operation will be using the ROB name instead of the reservation station name.
Part 3
The below excerpt from the lectures explains the changes between Tomasulo's algorithm with and
without the ROB and how the ROB supports ooo execution with exceptions.

The changes that are made to the algorithm are:

During the write back or broadcast operation, the values are still captured by instructions
waiting in the reservation stations. However, instead of writing the values to the registers and
clearing the RAT like normal, the values are written to the ROB, and the RAT maintains its name
value for the ROB entry.
A fourth operation is appended called commit. In the commit stage, we write the value of the
register pointed to by the commit pointer, and we update the RAT to point to the newly written
register instead of the ROB entry.
Recovery

Branch mis-prediction recovery part 1

The below excerpt from the lectures provides us a scenario in which a branch mis-prediction occurs
and the use of a ROB allows us to avoid writing incorrect values to the registers. Because the
instructions in red were never supposed to execute in the first place, we avoid making mistakes.

The example gives us a step-by-step view of how values are updated in the RAT and ROB when each
instruction is issued, dispatched, and its values are broadcasted.
Branch mis-prediction recovery part 2
The below excerpt from the lectures further discusses what takes place when we recover from
branch mis-predictions using a ROB. In this example, we can see that these steps are taken to fully
recover from a mis-predicted branch:

The RAT is cleared and points back to the values contained in the registers
The ROB is "emptied" by resetting the issue pointer to the commit pointer
The reservation stations and the computational units (ALU / MUL, etc.) are drained until they
are empty

The mis-predicted branch is only noticed when the commit pointer in the ROB sees that mis-
predicted branch value in the branch's ROB entry.
ROB and exceptions
In the below excerpt, we cover how exceptions are handled using ROB. In summary, we treat
exception as a result like they would be from any other operation. The exceptional instructions are
marked in the ROB and aren't handled until the commit pointer arrives to them in the ROB. We
delay the handling of exceptions until they need to be committed - this provides us a good return
point for an exception handler and prevents us from writing the results of instructions that took
place out-of-order before we noticed the exception. This also resolves the issue of phantom
exceptions - if the branch was mis-predicted we will end up ignoring the phantom exception so
effectively it never happened.
Exceptions with ROB quiz
Below is a quiz from the lectures covering exceptions with ROB. A DIV instruction caused a divide by
zero error - to solve the quiz we must predict the new state of the ROB when the exception is
noticed.

RAT updates on commit

The below excerpt from the lectures showcases how the registers and RAT are updated using the
ROB and why. Upon each commit, the values contained in the ROB are written to the registers. The
RAT, however, is not cleared or updated until the corresponding ROB entry is committed. This is to
help instructions that are being issued to keep track of and use the most recent name for the
outcome of a register.
So why are we writing to the registers on each commit? Because, if an exception takes place, all of
the changes that are valid are written to the registers and saved. The ROB can safely drain the
instructions that aren't meant to be written and the RAT can be cleared and updated to point to the
registers.

ROB Timing
Below are ROB timing quizzes and examples from the lecture.
ROB timing example
ROB timing quiz

Extra Topics

Unified reservation stations

Unified reservation stations are touched upon in the below excerpt for the class . With unified
reservation stations, we gain the ability to issue more instructions because we aren't segregating our
instructions into two groups - instructions will now gain a reservation station based on a first-come-
first-served basis. This will allow our pipeline to stop less often as well, as we will always be able to
make the most of our available space.

A drawback for unified reservation stations is that more logic is required in order to implement this
change. We must now include logic in order to sort between which instructions use what structural
capability (ADDR or MUL) and we also need to be able to selected two instructions for execution per
cycle, one ADDR and one MUL.

Superscalar processors
The below excerpt from the lectures discusses the requirements to implement superscalar
processors. The central takeaway from this discussion is that a superscalar processor will only be as
strong as its weakest link. If an operation in this listing presents itself as a bottleneck, our
performance will only be as good as that one operation.
Terminology confusion
This excerpt from the lectures clears up any possible confusion between the terminology used for
Tomasulo's algorithm in academia and what terms are used in the industry.
Out of order?
In our recent discussions, we've been issuing instructions one-by-one. What is really out of order in
Tomasulo's algorithm that provides us a performance increase? The below excerpt from the lectures
further discusses this.

The central takeaway is that these portions of the pipeline have this behavior:

Fetch, decode, and issue stages happen in program order in order to identify and resolve
dependencies.
Execute and write result (broadcast) stages happen out of order.
The commit stage happens in program order to give the appearance externally that we are
executing instructions in program order.
In-order vs out-of-order quiz
The below excerpt is a quiz from the lecture requiring us to identify what parts of the pipeline are
conducted in program order.
Memory Ordering
In previous lectures we have seen that processors conducting out-of-order execution can track when
instructions use registers populated by preceding instructions. In contrast, load and store
instructions can reference values located in memory, so how does a processor de-conflict load and
store accesses to values in memory when conducting out-of-order execution?

The notes for this lecture can be found here

Memory access ordering
So we've already demonstrated that we can resolve control dependencies by implementing good
branch prediction. We have eliminated false data dependencies for registers using register
renaming. We have also shown that out-of-order execution can respect RAW or true dependencies
by using Tomasulo-like scheduling of instructions in reservation stations.

The two techniques we have used to eliminate data dependencies are only applicable to operations
involving registers. We still have to resolve dependencies that manifest when conducting load and
store instructions on the same locations in memory. How do we execute these instructions out-of-
order?
Memory writes
For store instructions, knowing when memory writes actually happen is important. Memory writes
actually happen when an instruction commits. Memory writes only happen when a commit takes
place for an instruction because it is dangerous to do so, otherwise. If we wrote to memory prior to
an instruction committing, that information could be written but the instruction could be cancelled
due to something like branch mis-prediction or an exception.

To resolve this issue, we delay memory writes and stores until the instruction is committed.

So where and when do load instructions get their data? We want load instructions to get their
data as soon as possible. Do they always have to wait until every store instruction commits?

To resolve this issue, computer architects implement a load-store queue structure to keep all
load and store instructions. More on this in the next section.

Load-Store Queue (LSQ)

The load-store queue is similar to the ROB . This queue contains load and store instructions in the
sequence in which they will be committed. The fields are as follows:

l/s - bit that identifies whether the current entry is a load or store instruction.
addr - the address the instruction is accessing.
val - field for the value that the instruction should be loading or storing.
c - marks if the entry has been committed.

The load-store queue also implements a mechanism called store-to-load forwarding . If a load
operation has a matching store operation preceding it, meaning the load operation in question is
loading from a previously written memory location, we can forward the value of the preceding store
operation in the queue to the load operation in the queue. This affords us the ability to avoid having
to access memory at an already written to location - we already know the value it contains thanks to
the queue.

Below is a high-level representation of the concepts discussed above.

Load-Store Queue part 2
So what happens when we have a load instruction and we know the target address , but we didn't
previously store to this location so we don't know the value for forwarding purposes? We have
three options that have been considered:

in-order - in this case, we execute all the instructions in order to ensure the fidelity of the
contents of our target address. This defeats the purpose of our discussion as we want to
conduct out-of-order execution - we want all the load instructions to execute as soon as
possible.
wait for all stores - in this case, we wait for all previous store instructions to execute before
executing our load instruction.
 go anyway - the most aggressive option - we execute the load instruction as soon as we
resolve the target address.

Two things can happen for the go anyway option:

Previous store instructions will resolve their target addresses and we determine that it was safe
for us to load from our target.
Previous store instructions resolve their target address and we realize that the target was
supposed to be written to before we executed our load instruction. Thus, we've load ed an
incorrect value from memory and we need to recover. In this case, store instructions will
check if any load operations succeeding them match their target address. If so, if they are
marked complete in the queue, the store instruction will mark them incomplete.

Most modern processors use the go anyway option as they produce the best performance.
Store to load forwarding
Some central questions need to be answered for store-to-load forwarding . Below is the lecture
snapshot containing these questions.

LSQ example
Below is a more detailed representation of the load-store queue .
OOO Load/Store Execution
The below example discusses the intricacies of out-of-order execution of load and store instructions.
In the example provided, the sub operation is able to execute out-of-order because it has no
dependencies. Once it produces a value for R1 , we execute the dependent load instruction.
Meanwhile, the first load in the queue encountered a cache miss and is waiting memory addressed
by R6 to be loaded.

When the first load instruction finally completes, the dependent store instruction resolves its target
address with the previous add and notices that the succeeding load also target the same address.
Thus, the succeeding load instruction loaded a stale value from memory and the instructions in the
queue need to be invalidated.

In-order Load/Store Execution

In contrast, an example is provided for in-order load and store execution of the load/store queue. It
discusses how we can dispatch non-load and non-store instructions for execution if they contain no
dependencies. However, this model still enforces that load/store instructions execute in order so,
even if we have our target address calculated, all preceding store instructions must commit before
we can load.

In this example, the first load instruction encounters a cache miss and also resolves a dependency
for the preceding arithmetic operation. Thus, the succeeding store operation is also stalled. The
sub operation further down in the queue is able to be dispatched out-of-order, the load operation,
however, cannot proceed because the previous store operation has not taken place.

While this may avoid us having to recover if the last load reads stale values, this also prevents us
from leveraging a performance increase if the last load didn't actually depend on the preceding
store .

Memory ordering quiz

In this quiz we are instructed to determine how many cycles it would take to execute the instructions
in the provided load-store queue in-order if all load instructions encountered a cache miss of 40
cycles.

Summary

LSQ, ROB, and RS

So how do the load-store queue, reorder buffer, and reservation stations (RS) play together in our
out-of-order processor? The notes from the lecture below provide a high-level discussion.
Memory ordering quiz
Below is a quiz from the lectures wrapping up our understanding of where load instructions acquire
their values using a LSQ.
Compiler ILP
In previous lessons we discussed out-of-order execution processors that attempt to execute more
than one instruction per cycle. In this lesson we will discuss how compilers can support this process.

The notes for this lecture can be found here.

Can compilers improve IPC?

At the processor level, we face a couple of obstacles that prevent us from further improving our IPC
and performance. These include:
 dependence chains - a program can contain dependency chains that could otherwise not exist
if a compiler were to remove the dependencies and use other registers for storing information.
limited "window" into the program - a processor can only see so many instructions at once.
Independent instructions that could be executed concurrently could exist far from each other
in the program, not leveraging the out-of-order execution capability of the processor.

Below is a high level representation of the concepts discussed above with some pseudo-assembly.

Tree Height Reduction

Using Tree Height Reduction, compilers remove dependency chains from the program by
identifying operations than can be conducted concurrently and separating them. In the example
below, our code wants to store the summation of four operands into the register R8 . Without Tree
Height Reduction, our code would create a dependency chain as we execute sequential instructions
to add to register R8 . With Tree Height Reduction, the compiler groups the operations and
removes the dependency by using another register, R7 , to hold the intermediate value.
We aren't able to use Tree Height Reduction all of the time as it uses associativity. If an operation
isn't associative, Tree Height Reduction cannot be applied.

Tree Height Reduction Quiz

Below is a quiz from the lectures showcasing how to conduct Tree Height Reduction with a set of
assembly instructions. To solve the quiz, we must reconstruct the original expression from the
assembly instructions. Then we group together the ADD operations and get the final value for all of
the positive numbers. Next we group together all of the negative numbers with ADD operations, and
then we subtract the two summations.

Once we identify all of the dependencies in the reduced assembly code, we can see that the new
code is able to execute more instructions out-of-order, and we double our ILP.
Instruction Scheduling
The idea behind instruction scheduling is to identify instructions that will take a couple of cycles to
complete and moving instructions that take less cycles to complete to "stall" locations in the
program. This way, we can execute non-dependent instructions while waiting for something else to
happen, like a read from memory.

The excerpts below provide a high-level representation of a how a compiler identifies stalls in the
program code for long operations and rearranges instructions to leverage as much concurrency as
possible.
Instruction Scheduling Quiz
The quiz below showcases how we can use instruction scheduling to decrease the number of cycles
it takes to complete a series of instructions. Without instruction scheduling, it takes us 8 cycles to
complete the series of instructions. Once we identify the stalls, we see that we can execute the
second LOAD operation right after the first one if we rename the target register from R1 to R10 .

With instruction scheduling, we are able to execute the example instructions in 6 cycles.
Instruction scheduling and If conversion
We can easily apply instruction scheduling to the blocks of code in different branches, but how do
use instruction scheduling across blocks of code in different branches? If we conduct instruction
scheduling without predication, we would move some instructions in to different branches, however,
if that branch does not execute, the re-scheduled instruction does not get executed, changing the
behavior of the program.

To solve this, we can combine the branches using predication. We prepend the code of if-else
statements with predicates, combine the branches into one block, and execute all instructions. Then
we apply instruction scheduling to increase our efficiency.

Below is a high level representation of this concept.

Loops and If conversion
So, can we conduct instruction scheduling on loops, using If conversion and predication to enable
the movement of instructions in the program? Yes, instruction scheduling can be done on the block
of instructions that comprises a loop, however, in order to remove the branch instruction to conduct
If conversion, we would have to install predicates for each loop of the branch. Is this feasible?
Absolutely not - what if we had a branch that looped a million times, would we install a million
predicates?

Below is an excerpt from the lecture explaining this issue at a higher level.
Loop Unrolling
So how do we get better performance out of loops? Well, we do more work per loop iteration. In
Loop Unrolling, the compiler identifies what work is done each loop and sees if it can execute more
instructions per loop iteration. In the example provided below, the program adds a number to each
element in an array. With Loop Unrolling, the compiler unrolls the loop once and executes the
addition of the variable to the next array item in the loop. The loop iterator is also decremented by 2
instead of 1 to compensate for these changes.
Loop unrolling benefits: Instructions
Loop Unrolling provides us a benefit - we can do less instructions per loop evaluation! In the
example below, we compare two loops, with one being the unrolled loop.

When evaluation the unrolled loop, we actually execute less instructions because we execute the last
two instructions, ADD and BNE , less times! These instructions are what's known as the loop
overhead.
Loop unrolling benefits: CPI
Below is the breakdown of CPI for a branch before and after instruction scheduling is applied. Re-
scheduling the instructions, we see that we can avoid waiting unnecessary cycles for an operation to
complete when other operations that aren't dependent on previous instructions can be dispatched.
The excerpt from the lectures below now does a comparison of the example loop above, however,
we have unrolled the loop once. The unrolled loop without instruction scheduling doesn't see much
of a performance increase. Yes, we execute less instructions because we've unrolled the loop,
however, because the instructions aren't scheduled we have to wait a couple of cycles for
dependencies to be resolved.

Contrast this with the unrolled, re-scheduled loop. We use another register, R10 , to hold the
contents of the next item in the loop at R1 - 4 . We also re-schedule the add instructions because
they are only dependent upon the loads. The add instruction from the loop overhead can also be
conducted in parallel because it has no dependencies. Finally, our STORE instructions are edited to
compensate for the changes made to R1 .

Because of this, we can see that our CPI decreases greatly and we are able to leverage parallelism.
Unrolling downsides
Below is an excerpt from the lectures containing a high-level representation of the downsides to
loop unrolling. Here's a breakdown:

code bloat - depending on how many times we unroll the loop, we can bloat the size of the
code in the program.
unknown number of iterations - what if we don't know the number of iterations? How would
would be able to effectively unroll a loop? With an unknown number of iterations, we could exit
the loop early and not execute the rest of the unrolled loop - which is an issue.
number of iterations if not a multiple of N - what if we're doing an odd number of iterations
and we didn't unroll the loop to fit this? We need to exit the loop early without executing the
rest of the unrolled loop - how do we make that happen?
Function Call Inlining
In Function Call Inlining, the compiler identifies simple functions that can be inlined into the rest of
the program code. The example below shows a simple function that executes one instruction and
then returns. This function is wasteful each time it calls because we have to setup its arguments, call,
and then return - it's unnecessary overhead.

Function Call Inlining eliminates call and return overheads because the code is in the same
location. This also allows us to leverage instruction scheduling because the code is no longer
segregated due to function semantics. We are able to leverage this combination of performance
enhancing measures to gain a shorter execution time.
Function Call Inlining Downsides
Function Call Inlining is subject to code bloat, just like loop unrolling. In the example provided
below, we have a function that is comprised of 10 instructions. If the function is inlined for each
instance it is called, we would end up repeating the same 10 instructions in the program a bunch of
times. We can see how the program code might increase by a large amount if we inlined a function
that was called a lot of times.

We have to be judicious about which functions are inlined. They need to contain small amounts of
code, and it probably makes sense to ensure they aren't called often.
Function call inlining quiz
Below is a quiz from the lectures. In this quiz, we compare the number of cycles it takes to execute a
block of code, with and without function call inlining. In this example, there's no real way we can
conduct instruction scheduling due to the dependencies of the instructions, however, we increase
our performance and execute less cycles when function call inlining is implemented because we
avoid executing the CALL and RET instructions.
VLIW
This lesson covers VLIW and explicitly parallel processors. These processors do not try to identify ILP
on their own, instead doing what the compiler instructs them to do.

The notes for this lesson can be found here

Superscalar vs VLIW
Below is an excerpt from the lectures describing the differences between out-of-order and in-order
superscalar processors and very long instruction word (VLIW) processors.
Superscalar vs VLIW quiz
Below is a quiz from lectures comparing the possible program size between a out-of-order
superscalar processor and a VLIW processor. If each 128-bit instruction for a VLIW processor has no
dependencies and can execute all four operations at once, our programs can be equivalent. If we
have dependent instructions, however, there's a worst-case possibility our 128-bit instructions would
include NOP s for 3/4 operations. This would quadruple the program size.
VLIW: the good and the bad
Below is an excerpt from the lectures providing a high-level description of the pros and cons of VLIW
processors. A quick breakdown of what's not covered in the image below:

Compiler does the hard work - plenty of time. The basic discussion around this is that the
compiler has more time to schedule instructions, and the program will be run many times
afterwards. This is in contrast to superscalar processors that must schedule instructions during
runtime.
Latencies not always the same - this is talking about how the compiler won't be able to
predict how much latency will be present when the code executes on different hardware.
Cache misses might take longer in different environments.
Irregular applications - it's difficult for a compiler to schedule and predict the semantics of an
irregular program. Things that leverage machine learning, etc. are in this group.
VLIW backwards compatibility quiz
Below is quiz about VLIW backwards compatibility. In this instance, the new compiler is not a VLIW
processor. Why? With VLIW, the compiler guarantees that an instruction contains multiple
independent operations. If we increase the number of instructions executed per cycle, we cannot
guarantee that dependencies will not exist between the two instructions being executed - the
compiler did not account for this and we're breaking the contract, anyways.

In order to run a program on this new VLIW processor, we need to re-compile the code so that the
compiler can re-schedule the instructions and resolve dependencies.
VLIW instructions
Below is an excerpt from the lecture, describing the the characteristics of VLIW instructions.
VLIW target market
Below is quiz from the lectures asking us to rank the best application for VLIW processors.
Cache
This section conducts a review of the hardware cache. The notes for this lesson can be found here

Locality
Below is a high-level description from the class describing the concept of locality.
The below image from the lectures describes the concepts of temporal locality and spatial
locality.

Temporal Locality Quiz

The below quiz from the lectures discusses temporal locality with an example section of code. The j
and sum variables are accessed very often, having temporal locality in the cache.
Spatial Locality Quiz
We are likely to access all elements of the array in this loop, thus arr has spatial locality.
Cache Quiz
The quiz below describes the concept and purpose of a processor cache.
Cache Performance
The below excerpt from the class describes the metrics used to measure cache performance.
Hit Time Quiz
This quiz asks some common-sense questions about the timing for a well-designed cache.
Miss Rate Quiz
This quiz asks common-sense questions on the comparison between hit rate and miss rate.
Block Size Quiz
The below quiz covers good use of the cache for variables with specific behaviors.
Block Number Quiz
The below quiz shows us how to calculate the block number.
Cache Tags
The below excerpt from the class describes cache tags.
Valid Bit
The below excerpt from the class describes the valid bit.
Direct Mapped Cache
The below excerpt from the class describes the direct mapped cache structure.

Direct Mapped Cache Quiz

The below quiz demonstrates how to find cache conflicts in direct-mapped caches.
Direct Mapped Cache Quiz
Another direct mapped cache quiz showcasing cache conflicts.
Associative Cache Quiz
The below quiz showcases how we index into an N-way associative cache with an address.
Implementing LRU
The below excerpt from the class describes how the LRU policy is implemented for cache line
replacement.
LRU Quiz
The below quiz demonstrates the LRU cache replacement policy.
Write Policy
The below excerpt from the lecture provides a good discussion of the differences between cache
writing policies.
Cache Summary
The below excerpt from the course summarizes the data used to handle an example cache,
demonstrating how the cache structure influences the data used to track the tags, indices, etc.
Cache Summary Quiz
Below are the answers to the cache summary quizzes that tie all of these concepts together.
Virtual Memory
This lesson discusses the difference between virtual and physical memory. Virtual memory is used
by programs and must be translated to physical memory. Since the translation can be slow, a
Translation Look­Aside Buffer (TLB) is used. The notes for this lesson can be found here.

Page Size Quiz

Below is a quiz from the lectures that has us calculate the number of physical memory frames for a
system and then the number of page table entries for each process.
Address Translation Quiz
Below is a quiz from the lectures that demonstrates how to conduct address translation.
Flat Page Table Size Quiz
Below is a quiz from the lectures that demonstrates how to calculate the size of flat page tables for
multiple architectures.
Two Level Page Table Size
The below excerpt from the course describes how we can save memory using multi level page
tables.
4 Level Page Table Quiz
The below quiz from the lectures demonstrates how to calculate the amount of memory needed for
a page table with 4 levels.
Virtual to Physical Translation Quiz
The below quiz from the lectures demonstrates how to calculate the number of cycles necessary
necessary to conduct virtual to physical address translation.
The below quiz from the lectures demonstrates the same as above except the page table entries are
cached.
TLB Size Quiz
Below is a quiz from the lectures covering how we can calculate the approx. size of the TLB to
achieve similar performance to the cache.
TLB Performance Quiz
Below is quiz demonstrating how to calculate TLB performance for a given set of memory accesses
by a program.
Advanced Caches
Improving the performance of caches is done by improving the hit rate, improving the miss rate, or
improving the miss penalty. The methods to implement these improvements in discussed in this
lesson. The notes for this lecture can be found here.

VIPT Aliasing Avoidance Quiz

Below is a quiz from the class demonstrating how to calculate the maximum size of a VIPT cache
while avoiding aliasing.
NMRU Quiz
Below is a quiz demonstrating how we can keep track of the hit/misses for an NMRU cache.
Prefetch Instructions Quiz
Below is a quiz demonstrating how we can calculate how far ahead and whether or not a prefetch
should be conducted.
Global and Local Miss Rate Quiz
Below is a quiz demonstrating how to calculate the local and global miss rates for two caches.