A2 - pipelines

stages

• even basic operations take multiple cycles
• these can be divided into a series of simpler stages
• the stages are simpler, so each stage takes less time

int N = 1000;
double A[N];  /* static arrya */

< some code >

for (i = 0; i < N; i++) {
	A[i] = A[i] * A[i];
}

< more code >

• here, each operation in the loop is independent of the others

// a 'normal' code to sum over an array
double A[1000];

sum = 0.0;
for (i = 0; i < N; i++) {
	sum += A[i];
}
// slow as each increment of the sum cannot begin until the previous result is known


// optimise: unrolling the loop
double A[1000];

t1 = 0.0;
t2 = 0.0;
t3 = 0.0;
t4 = 0.0;
t5 = 0.0;

for (i = 0; i < N; i +=5) {
	t1 += A[i];
	t2 += A[i+1];
	t3 += A[i+2];
	t4 += A[i+3];
	t5 += A[i+4];
}
sum = t1 + t2 + t3 + t4 + t5
// 5x faster

• usually, compilers can do a much better job at unrolling the loop

int N = 1000;
double A[N];
int j:

< set j >

sum = 0.0
for (i = 0; i < N-j; i++) {
	sum += A[i] + A[i+j]
}

• here, the compiler does not know in advance what $j$ will be
• hence, it doesn't unroll the loop
• setting $j$ as a constant helps complier know that, and hence it can unroll the loop

branches

• to avoid stalling an $M$-stage pipeline, one must be able to 'see' $M$ operations into the future
• branches, such as if statements make this impossible
• therefore, if statements inside loops must be avoided
• consider a boundary condition enforced inside the loop:

double A[N], B[N];

for (i=0; i<N; i++) {
    if (i==0) {              /* LH Boundary */
        B[i] = 0.5*(A[N-1] + A[i+1]);
    } else if (i==N-1) {     /* RH Boundary */
        B[i] = 0.5*(A[i-1] + A[0]);
    } else {                 /* All others */
        B[i] = 0.5*(A[i-1] + A[i+1]);
    }
}

• the boundary conditions can be imposed outside:

double A[N], B[N];

/* LH Boundary */
B[0] = 0.5*(A[N-1] + A[1]);

/* All others */
for (i=1; i<N-1; i++) {
    B[i] = 0.5*(A[i-1] + A[i+1]);
}

/* RH Boundary */
B[N-1] = 0.5*(A[N-2] + A[0]);

• for larger dimensional problems, the optimised code will be significantly longer

• other approaches to remove branching:

  • using modular arithmetic to compute the index of each neighbour

iL = (i + N - 1) % N;
iR = (i + N + 1) % N;
```
- padding the array by 2 per direction to include 'halo' elements that are duplicates of those on the opposite edge, so the points are valid even at the boundaries

iL = i - 1;
iR = i + 1