Lecture 3 ( 9/10/2007) --- Locality + Future of Wires
Introduction
- In the CPU, locality optimization is basically done at the Registers and cache.
- Bypass networks and Reservation stations are completely micro-architectural features and cannot be optimized further.
Matrix Multiplication
- The Matrix Multiplication is also called dense matrix-matrix multiplication.
- Let us consider the multiplication of the following matrices:
The most obvious way of doing the multiplication is:
For i
Register Optimization Techniques
Why do Register Optimization?
1. We can reuse the values in the register
2. Provide low latency access which is a result of locality
3. Reduce traffic to memory, i.e., reduces the number of loads and stores
4. As compared to memory, less amount of energy is used to do the same work
5. Fewer instructions to do the same thing for higher performance
Techniques for Register optimization are:
1. Scalar replacement
Here for the last loop (For k), instead of storing the result at the memory location, C[i][j], we store it in a register, say c, and keep reusing it for each iteration of that loop.
For k
{
} C[i][j] = c
2. Better register allocation with fewer spills
Compilers put values in a register and if they run out of registers for a new value, it stores the old value to a stack to be reused again. This is called a “spill”. A “fill” is the popping of value from this stack back into the register. The idea is to allocate registers in such a way that, the spills and fills of register values to and from the stack (where temporary values are stored) are reduced.
3. Loop unrolling
Here the idea is to shift the inner loop a level higher.
For e.g.
For i=0 to 2
Can be unrolled as:
C0 = A0 + B0
C1 = A1 + B1
C2 = A2 + B2
In case of matrix multiplication, we can obtain locality advantage by unrolling the outer loop and the inner loops together. The advantage is that we use a particular data element as much as we can when it is in the register, rather than removing it and putting it back in registers for computations later.
For e.g. Let us consider a 2D matrix multiplication, C = A * B, as mentioned above.
The lower case alphabets are registers and the upper case alphabets represent array elements from memory.
For i = 0:N
The c0 and c1 later get added to form a data elemen t of matrix C.
Here we were able to reuse the values of matrices C and A in the register due to loop unrolling.
4. Loop fusion
Here if we have two loops working on the same data elements, it is better to combine them to a single loop.
For i=0 to 2
For i = 0 to 2
The fused loop would be :
For i=0 to 2
In this case, Ai and Bi could be in registers and can be used for computation of Ci and Di.
Cache Optimization Techniques
- Properties associated with caches are associativity, lines and size.
- Caches were introduced to improve latency, not Bandwidth.
1. Prefetching
Prefetch data from memory into cache before it is used. This is a form of parallelism. This would be further discussed during the lecture on streaming.
2. Spatial
Spatial Locality when utilised can significantly increase bandwidth. One trick is to make things come in stride-1 or atleast come in bunches.
3. Temporal
a) Loop unrolling and fusion
As used in the registers, loop unrolling and fusion techniques can be used to optimize cache locality. Here, instead of registers, we ensure the required data elements remain in cache.
b) Loop Tiling/ Blocking
Loop tiling partitions a loop’s iteration space into smaller chunks or blocks, so as to help ensure data used in a loop stays in the cache until it is reused. The partitioning of loop iteration space leads to partitioning of large array into smaller blocks, thus fitting accessed array elements into cache size, enhancing cache reuse and eliminating cache size requirements.
c) Loop Interchange/Reordering
Loop interchange is the process of exchanging the order of two iteration variables.Cache misses occur if the contiguously accessed array elements within the loop come from a different cache line. Loop interchange can help prevent this. The effectiveness of loop interchange depends on and must be considered in light of the cache model used by the underlying hardware and the array model used by the compiler. For e.g. Row major is used in C programming.
- Implicit Cache allocation can also make things optimal.
- Optimal doesn’t necessarily translate to performance.
Discussion on Paper : The Future of Wires
Definitions
1. FO4 ( Fanout 4) - Time taken by an inverter to drive 4 inverters. This is used as a measure for comparing delays for circuits of different technologies.
2. λ = ½ min feature size , is used to define size of transistors
3. χ = minimal M1 pitch, is used to measure size of wires.
Usually χ = 4 λ
Properties of a wire
The properties of a wire discussed in class were:
1. Resistance
2. Capacitance
3. Inductance
4. Dimensions ( length, breadth, width)
5.Voltage
6. Delay
7. Bandwidth
8. Power
Affect on Resistance
As length and width shrink, χ and λ shrink proportionally, say with factor α. As height shrinks, χ and λ also shrink but in a lesser proportion, say with factor β.
Resistance = ρ * L/A = ( approx) ρ * α /(α * β) = (approx) ρ/ β
Hence, as wires shrink, resistance increases.
Affect on Capacitance
The main contributors to the capacitance are bottom and top plates and sidewalls to other wires. The increase in the sidewall is because of aspect ratio and this a significant affect on Capacitance.
From the equation above, it can be seen that, overall capacitance is going down because of slow improvements in k and a bit because of narrower wires (offset by side-wall).
Affect on Inductance
The affect on inductance is hard to quantify, but is usually negligible.
Affect on Supply Voltage
Previously, voltages scaled well with the reduction in dimensions. However, voltage scaling is not seen in current technologies. This is because there is a limit to which Vth can go down.
Delay Analysis
RC model was used for analysis along with FO4. Model: 1FO4+RC
Local wires that are fixed in χ scale well for now, but might be a bit problematic in terms of delay in future technologies.
It is seen that if χ is kept constant and the physical length is increased, then both R and C increase proportionally with it. Hence, there is a quadratic increase in delay.
One of the solutions proposed to the long wire problem is Repeaters. Using them brings the scaling back to linear. However, the power usage due to repeaters is high.
Bandwidth Analysis
A single global wire has more bandwidth than local wires, but there are fewer of them.
Power Analysis
P = α A f C V * dV + P static
Previously, V was scaling with the shrinkage, hence Power used to scale.
However, with current technologies, V doesn’t scale, hence P isn’t scaling.
