Program Optimization II

Instruction-Level Parallelism

Modern CPU Designs are super scaler CPUs, meaning can issue multiple simultaneous instruction executions in one cycle. The instructions are retrieved from a sequential instruction stream and are scheduled dynamically.

• Contrast this to rigid requirements that pipeline CPUs have (only one instruction can use a chunk of hardware).
• Super scaler CPUs have multiple duplicate functional units so that they can do this.
• Benefit: without programming effort, the processor takes advantage of instruction level parallilism that most programs have.

The Instruction Control looks at what instructions are coming up and dispatch to the functional units.

Pipelined Functional Units

Given this code

long mult_eg(long a, long b, long c) {
	long p1 = a*b;
	long p2 = a*c;
	long p3 = p1*p2;
	return p3; 
}

• p1 and p2 do not depend on each other so they can both be started in stage 1.
• p1*p2 depends on both p1 and p2 computations to be done

Each multiplication requires 3 cycles. We complete 3 multiplications in 7 cycles.

Time

	1	2	3	4	5	6	7
Stage 1	a*b	a*c			p1*p2
Stage 2		a*b	a*c			p1*p2
Stage 3			a*b	a*c			p1*p2

Hasswell CPU

4th gen Intel CPU in 2013-2014.

It has multiple instructions that can execute in parallel.

• 2 load, with address computation
• 1 store, with address computation
• 4 integer
• 2 Fp multiple
• 1 FP add
• 1 FP divide

Som instructions take >1 cycles, but can be pipelined.

Instruction	Latency	Cycles/Issue
Load/Store	4	1
Integer Multiple	3	1
Integer/Long Divide	3-30	3-30
Single/Double FP Multiple	5	1
Single/Double FP Add	3	1
Single/Double FP Divide	3-15	3-15

It had 8 total functional units.

Ways to Optimize

Let's see how we can optimize

void combine4(vec_ptr v, data_t *dest) {
	long i;
	long length = vec_length(v);
	data_t *d = get_vec_start(v);
	data_t t = IDENT;
	for (i = 0; i < length; i++)
		t = t OP d[i];
	*dest = t;
}

What this code does is that:

• When IDENT=0 and OP=+: vector sum
• When IDENT=1 and OP=*: vector multiplication
• data_t can be int or double

The inner loop in x86-64 Compilation will be:

.L519: # Loop:
	imull (%rax,%rdx,4), %ecx # t = t * d[i]
	addq$1, %rdx# i++  
	cmpq %rdx, %rbp # Compare length:i jg .L519 # If >, goto Loop

• This has a serial computation of OP = * (multiplication) so there is a sequential dependence, meaning that the performance is determined by latency of the operation.

Loop Unrolling (2x1)

void unroll2a_combine(vec_ptr v, data_t *dest) {
	long length = vec_length(v);
    long limit = length-1;
    data_t *d = get_vec_start(v);
    data_t x = IDENT;
    long i;
    
    /* Combine 2 elements at a time */    
    for (i = 0; i < limit; i+=2) {
        x = (x OP d[i]) OP d[i+1];
    }

    /* Finish any remaining elements */
    for (; i < length; i++) {
	    x = x OP d[i]; 
	}
	*dest = x; 
}

This performs 2x more useful work per iteration.

• Helps integer add by achieving latency bound
• Other operations don't improve because its still a sequential dependency.

Loop Unrolling (2x1) with Reassociation (2x1a)

Change the previous for loop to be

/* Combine 2 elements at a time */
    for (i = 0; i < limit; i+=2) {
        x = x OP (d[i] OP d[i+1]);
    }

Note: this changes the result of the computation for FP. However, it provides a 2x speedup for Int *, FP+, and FP *

• This is because it breaks sequential dependency.
  • The operations in the next iteration can be started earlier since it doesn't depend on the previous operation.
• The overall performance given N elements and D cycles latency/operation
  • (N/2+1)*D cycles:
  • CPE = D/2

Loop Unrolling (2x1) with Separate Accumulators (2x2)

Change the previous for loop to be

 /* Combine 2 elements at a time */    
	 for (i = 0; i < limit; i+=2) { 
		 x0 = x0 OP d[i];
		 x1 = x1 OP d[i+1];
	}

This is a different form of reassociation.

• Int + makes use of two load units as we separate the operations
• This provides a 2x speedup (over unroll2) for Int *, FP +, FP *
• Now, there is two independent "streams" of operation.
• The overall performance given N elements and D cycles latency/operation
  • (N/2+1)*D cycles:
  • CPE = D/2
  • CPE matches prediction

Unrolling and Accumulating

The idea is that you can

• unroll to any degree L
• accumulate K results in parralel
• L must be a multiple of K

Limitations:

• Diminishing returns: you cant go beyond throughput limitations of execution units
• Large overhead for short lengths
  • Finish off iterations equentially

For FP * on Intel Haswell

• Latecy bound: 5.00. Throughput bound: 0.50.

For Int + on Intel Haswell

• Latecy bound: 1.00 Throughput bound: 1.00.

Achievable performance

• Limited only by throughput of functional units
• up to 42x improvement over original, unoptimized code.

Programming with AVX2

There are YMM registers: 16 total, each 32bytes.

Use the SIMD Operations.

• single precision: vaddsd %ymm0, %ymm1, %ymm1
• double precision: vaddpd %ymm0, %ymm1, %ymm1

Make use of AVX (vector) instructions so that you can perform parallel opeartions on multiple data elements.

Dealing with Conditions

Branches provide a challenge: super scaler CPUs have Instructional Control Units that are always looking ahead to see how the Execution Units can get the operations started so that they are always busy. Branches pose a problem because there are two sets of branch instructions that depends on the previous instruction set to be completed. Therefore, it cannot reliably determine where to continue fetching.

In modern CPUs, it will guess where to go, and when the result is known, it tells the Instruction Control that everything was correct and they may procede, otherwise it invalidates any partially executed instructions.

For loops, you typically want to keep looping, so the prediction is that you will continue to loop.

Mispredicted branches are very expensive as it can cost multiple clock cycles on a modern processor. It can be a major performance limiter.