Lecture 2 (09/05/2007) — Locality Mechanisms

Lecture 2 Slides

Lecture 2 Discussion

Announcements

First lab will be assigned on next Monday (09/10). The lab will be based on optimizing matrix multiply on a uniprocessor.
Mattan will be out next Wednesday (09/12) for a workshop, and there will be a guest lecture on Wednesday.

Next 3 Lectures Outline

Locality Mechanisms in a CPU

* What

* Why

* How

Another view of locality

* Why

Exploiting locality in a CPU - how to make use of locality to improve performance and power

* Register usage

* Cache-aware algorithms

* Cache-oblivious algorithms (guest lecture)

A CPU-Based Computer

Components include:

* Registers

* ALU

* Control

* Reservation Stations

* Bypass Networks (support for forwarding)

* Cache Hierarchy

* Virtual Memory Support (TLB, etc)

Memory

* Memory Controller

* DRAM

* DMA controller

* Disk

* Network

* Video

Interconnect

* BUS - (implies a shared bus)

* Interconnection Networks - implies some type of point to point connection

* Interconnection Networks can be made from various topologies (e.g. Crossbar, hypercube, cube, mesh torus, ring)

View of a Modern CPU-Based Computer

NOTES:

Relative size of components is arbitrary in the figure above.
A Register File is an array of registers (usually a multi-ported SRAM).
A Bypass network allows a piece of logic, (i.e. an ALU) to forward full or partial values down to a later pipeline stage.
Reservation Stations are specialized forms of registers.

What affects locality?

Which of these components of CPU-based computer deal with locality?

Registers
Reservation Stations
Bypass Networks
Caches

It is important to understand where each of these components fit inside the architecture and how they can be implemented to take advantage of the most locality.

Registers

Typically when referring to a “register” we mean a physical register.
Architectural registers are essentially used outside the compute pipeline. The architectural registers are renamed and the computation takes place using the physical registers.
Data is stored and accessed through the physical registers.
Data is stored to architectural registers on commit.
Rarely data is read from the architectural registers if it is not available in physical registers.

Architecture	Number of Architectural Registers	Number of Physical Registers
x86	4 or 8	~10s or 100s

CPUs

Initially registers were just a form of storage for CPUs (didn’t really figure into locality)
Later registers were used for interfaces (buffers), compact encoding and convenience.

* Accumulator, instruction pointer, status registers

Now registers are used to hide the long access times to memory (they have a shorter access time) and provide a latency benefit.

ASICS (Application Specific Integrated Circuits) - something that is not a CPU

Buffering
Latency
Conserve Power - (not the same method as a traditional CPU)
Improve Bandwidth

* Utilizes many “parallel” registers

Processor-Memory “Performance” Gap

Normalized to the performance of a VAX
The graph was calculated in terms of MIPS(year) / MIPS(VAX 1980)

CPU Performance

Can be measured in several different ways:

* FLOPS - floating point operations per second (only floating point instructions)

* IPC - instructions per cycle (any kind of instruction)

* CPI - cycles per instruction (inverse of IPC)

* MIPS - millions of instructions per second (only integer instructions)

* Peak performance - this metric is not as meaningful. It is easy to increase the number of instructions per second by adding circuitry (ALUs, etc) in the extra area on-chip that does useless/meaningless computation.

* The typical way to measure performance is through a standardized set of benchmarks such as those put together by SPEC (Standard Performance Evaluation Corporation). The programs are run and the time taken and number of instructions are calculated and reported.

Every year we typically see 1 1/2 times the performance of the previous year.

Memory Performance

Memory performance is typically measured as latency of the memory, but latency is hard to measure.
In modern DRAM latency is hard to measure because latency depends on the data being accessed.

* For this reason, latency is measured when the DRAM is empty and is assumed to be doing no other access.

Memory Bandwidth is calculated by running the memory for a long time and measuring how may words were sent from the processor.
Prior to 1980, memory was faster than the computation.

* Now there is almost a 100/1000 to 1 gap in performance.

* It is possible to hide memory latency by doing more things at once.

Pitfalls of the graph

Performance for a CPU is clearly defined
Performance for DRAM is not clearly defined
Memory (DRAM) performance is part of the entire system and the CPU performance takes memory performance into account.

What makes this 50% improvement possible?

Technology improvements (process technology, Moore’s Law)
Scales of technology improvement:

* Feature size shrinks by approximately 1/2 every 3 years

* The number of transistors on chip doubles every 18 months.

More devices fit on chip with scaling (approximately 4 times as many every 3 years).
Frequency & switching speed increases, because it is not necessary to move electrons (and holes) as far.
If we incorporated all the technological improvements, we should be getting around 75% improvement (so we’re not yet getting everything that is possible).
In the past higher parallelism and mostly deeper pipelining were used to improve performance, but we have reached the limit and can’t pipeline any more than we are currently pipelining.
Overall this yields the ~50 improvement per year.
The graph motivates the fact that we have to do something about latencies, but it is misleading because the two quantities are not independent of one another.

Locality

Locality is useful in improving Performance

Frequency jumps over time
(Taking advantage of the ability to make multiple accesses on chip without having to go to memory.
Register accesses can be made in one cycle.

* Cache access take about the same amount of time (maybe a bit longer)

* Memory accesses are much worse.

Locality Improves Power

It takes more energy to read data than to compute data. (Dynamic Power)
To move data across chip can be almost a factor of 20.
To move data off chip can be almost a factor of 100’s.

* When we can, we want to avoid moving things off chip.

Locality Improves Bandwidth

Signaling over shorter distances (pins are limited)
Routing is easier
It’s mostly a matter of wire density
Min wire pitch (chi) is 1/2 intermediate and 1/4 global wire pitches.
For every 2 wires in M1, it’s only possible to do 1 wire for the layer above that.
Vias and repeaters restrict routing and add area.

Rules of Thumb for wires

Latency is directly proportional to distance.
Bandwidth is inversely proportional to distance.
Power density is directly proportional to distance + a step function.
We will cover this more in depth in the next lecture.

Register or Memory?

Defined by implementation?

Register = latches?

Processor registers are created out of SRAM
Characteristics:

* Low latency

* High frequency

* High Power

* Large Area

Memory = SRAM/DRAM?

SRAM cells must be connected to a sense amp that amplifies the small charge stored in the SRAM cell.
Characteristics:

* Higher Latency

* Lower Frequency

* Tricky to Design

* Small bit area

* Amortized periphery area

Latch v. Memory Comparison

	Advantages	Disadvantages
Latch	fast and high bandwidth (high load and large transistors)	uses lots of gates
Memory	uses fewer and smaller transistors than a latch	very sensitive design and precharge circuitry is necessary

Latches are typically only used for pipeline registers today.

Defined by use:

Registers(Latches) = small & fast
Memory = large & slow

Cache-aware programming

Caches are used to hide memory latency

Internal look at a cache

Caches are composed of an array of SRAM blocks.
Banks are used for interleaving.
Cache lines are composed of a number of consecutive bytes that map into main memory.
Tag array stores the rest of the address bits.
Associativity helps decouple the locations in a cache.
Caches are part of the memory hierarchy: if you don’t find the data in one level, you go to the next.
A cache relies on spatial locality (accessing data that is stored close together).

*If there are two addresses in the same line that are part of the access pattern to a location location, it saves additional accesses to memory.

* The access latency of memory is quite large compared to that of a cache, so we might as well bring more in from memory at once when we do an access (we can also pipeline accesses to the cache or to memory.

* Why not build a cache with 1 byte blocks?

It would COST too much! One byte blocks would require more bits in the tag array. The design of a cache is a trade off between what you can implement and the limiting COST.

* How else can you amortize the cost of accessing memory?

Prefetch

However, Prefetch can actually hurt locality if not accessing the next thing in order from memory. This is an important practical issue of building caches.

A cache also utilizes temporal locality (access the same word again soon)

* If a memory location has been accessed once, it’s more than likely to be accessed again so a cache can take advantage of this fact by not immediately evicting the value.

What to consider

Is it necessary to worry about the cache when writing code?

* The cache is traditionally considered part of the micro-architecture.

Even though the cache is not expressed to the architecture, it must be considered when coding.

*Because without using the locality in the cache performance degrades tremendously.

*In modern architectures there are explicit cache-control instructions in the ISA (prefetch, invalidate, flush, line-lock, …)

Example

Code that traverses a linked list:

while(!done)
node=node->next

[$[Get Code]]

translates into:

ld node.next -> n // following instructions cannot proceed until this instruction completes
ld n -> node

[$[Get Code]]

The algorithm will work and is transparent to the architecture, but the code will execute very slowly.
Could try would to re-factor the algorithm.

Methods to improve (re-factor) an algorithm

Change or optimize the data structure.
Prefetch: bring in data and make sure it is in the cache before accessed.
Add parallelism (doesn’t necessarily help).

Summary

The cache is part of the architecture and as a programmer you must be aware of it.

Next Lecture

Optimizations for locality
Wires

* Technological parameters

Lecture 2 Discussion