Carnegie Mellon

Program  Op*miza*on  
15-­‐213:  Introduc0on  to  Computer  Systems  
25th  Lecture,  Nov.  23,  2010  

Instructors:    
Randy  Bryant  and  Dave  O’Hallaron  

1
 Carnegie Mellon

Today  
 Overview  
 Generally  Useful  Op*miza*ons  
 Code  mo0on/precomputa0on  
 Strength  reduc0on  
 Sharing  of  common  subexpressions  
 Removing  unnecessary  procedure  calls  
 Op*miza*on  Blockers  
 Procedure  calls  
 Memory  aliasing  
 Exploi*ng  Instruc*on-­‐Level  Parallelism  
 Dealing  with  Condi*onals  

2
 Carnegie Mellon

Performance  Reali*es  
 There’s  more  to  performance  than  asympto1c  complexity  

 Constant  factors  maHer  too!  

 Easily  see  10:1  performance  range  depending  on  how  code  is  wriQen  
 Must  op0mize  at  mul0ple  levels:    
 algorithm,  data  representa0ons,  procedures,  and  loops  
 Must  understand  system  to  op*mize  performance  
 How  programs  are  compiled  and  executed  
 How  to  measure  program  performance  and  iden0fy  boQlenecks  
 How  to  improve  performance  without  destroying  code  modularity  and  
generality  

3
 Carnegie Mellon

Op*mizing  Compilers  
 Provide  efficient  mapping  of  program  to  machine  
 register  alloca0on  
 code  selec0on  and  ordering  (scheduling)  
 dead  code  elimina0on  
 elimina0ng  minor  inefficiencies  
 Don’t  (usually)  improve  asympto*c  efficiency  
 up  to  programmer  to  select  best  overall  algorithm  
 big-­‐O  savings  are  (oWen)  more  important  than  constant  factors  
 but  constant  factors  also  maQer  
 Have  difficulty  overcoming  “op*miza*on  blockers”  
 poten0al  memory  aliasing  
 poten0al  procedure  side-­‐effects  

4
 Carnegie Mellon

Limita*ons  of  Op*mizing  Compilers  

 Operate  under  fundamental  constraint  
 Must  not  cause  any  change  in  program  behavior  
 OWen  prevents  it  from  making  op0miza0ons  when  would  only  affect  behavior  
under  pathological  condi0ons.  
 Behavior  that  may  be  obvious  to  the  programmer  can    be  obfuscated  by  
languages  and  coding  styles  
 e.g.,  Data  ranges  may  be  more  limited  than  variable  types  suggest  
 Most  analysis  is  performed  only  within  procedures  
 Whole-­‐program  analysis  is  too  expensive  in  most  cases  
 Most  analysis  is  based  only  on  sta1c  informa*on  
 Compiler  has  difficulty  an0cipa0ng  run-­‐0me  inputs  

 When  in  doubt,  the  compiler  must  be  conserva*ve  

5
 Carnegie Mellon

Generally  Useful  Op*miza*ons  

 Op*miza*ons  that  you  or  the  compiler  should  do  regardless  
of  processor  /  compiler  

 Code  Mo*on  
 Reduce  frequency  with  which  computa0on  performed  
 If  it  will  always  produce  same  result  
 Especially  moving  code  out  of  loop  
void set_row(double *a, double *b,
long i, long n)
{
long j; long j;
for (j = 0; j < n; j++) int ni = n*i;
a[n*i+j] = b[j]; for (j = 0; j < n; j++)
} a[ni+j] = b[j];

6
 Carnegie Mellon

Compiler-­‐Generated  Code  Mo*on  

void set_row(double *a, double *b,
long i, long n) long j;
{ long ni = n*i;
long j; double *rowp = a+ni;
for (j = 0; j < n; j++) for (j = 0; j < n; j++)
a[n*i+j] = b[j]; *rowp++ = b[j];
}

Where are the FP operations?

set_row:
testq %rcx, %rcx # Test n
jle .L4 # If 0, goto done
movq %rcx, %rax # rax = n
imulq %rdx, %rax # rax *= i
leaq (%rdi,%rax,8), %rdx # rowp = A + n*i*8
movl $0, %r8d # j = 0
.L3: # loop:
movq (%rsi,%r8,8), %rax # t = b[j]
movq %rax, (%rdx) # *rowp = t
addq $1, %r8 # j++
addq $8, %rdx # rowp++
cmpq %r8, %rcx # Compare n:j
jg .L3 # If >, goto loop
.L4: # done:
rep ; ret 7
 Carnegie Mellon

Reduc*on  in  Strength  

 Replace  costly  opera0on  with  simpler  one  
 ShiW,  add  instead  of  mul0ply  or  divide  
16*x --> x << 4
 U0lity  machine  dependent  
 Depends  on  cost  of  mul0ply  or  divide  instruc0on  
– On  Intel  Nehalem,  integer  mul0ply  requires  3  CPU  cycles  
 Recognize  sequence  of  products  

int ni = 0;
for (i = 0; i < n; i++) for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) for (j = 0; j < n; j++)
a[n*i + j] = b[j]; a[ni + j] = b[j];
ni += n;
}

8
 Carnegie Mellon

Share  Common  Subexpressions  

 Reuse  por0ons  of  expressions  
 Compilers  oWen  not  very  sophis0cated  in  exploi0ng  arithme0c  
proper0es  
/* Sum neighbors of i,j */ long inj = i*n + j;
up = val[(i-1)*n + j ]; up = val[inj - n];
down = val[(i+1)*n + j ]; down = val[inj + n];
left = val[i*n + j-1]; left = val[inj - 1];
right = val[i*n + j+1]; right = val[inj + 1];
sum = up + down + left + right; sum = up + down + left + right;

3 multiplications: i*n, (i–1)*n, (i+1)*n 1 multiplication: i*n

leaq 1(%rsi), %rax # i+1 imulq %rcx, %rsi # i*n

leaq -1(%rsi), %r8 # i-1 addq %rdx, %rsi # i*n+j
imulq %rcx, %rsi # i*n movq %rsi, %rax # i*n+j
imulq %rcx, %rax # (i+1)*n subq %rcx, %rax # i*n+j-n
imulq %rcx, %r8 # (i-1)*n leaq (%rsi,%rcx), %rcx # i*n+j+n
addq %rdx, %rsi # i*n+j
addq %rdx, %rax # (i+1)*n+j
addq %rdx, %r8 # (i-1)*n+j

9
 Carnegie Mellon

Op*miza*on  Blocker  #1:  Procedure  Calls  

 Procedure  to  Convert  String  to  Lower  Case  
void lower(char *s)
{
int i;
for (i = 0; i < strlen(s); i++)
if (s[i] >= 'A' && s[i] <= 'Z')
s[i] -= ('A' - 'a');
}

 Extracted  from  213  lab  submissions,  Fall,  1998  

10
 Carnegie Mellon

Lower  Case  Conversion  Performance  

 Time  quadruples  when  double  string  length  

 Quadra0c  performance  

200 lower
180
160
140
CPU seconds

120
100
80
60
40
20
0
0 50000 100000 150000 200000 250000 300000 350000 400000 450000 500000
String length

11
 Carnegie Mellon

Convert  Loop  To  Goto  Form  

void lower(char *s)
{
int i = 0;
if (i >= strlen(s))
goto done;
loop:
if (s[i] >= 'A' && s[i] <= 'Z')
s[i] -= ('A' - 'a');
i++;
if (i < strlen(s))
goto loop;
done:
}

  strlen  executed  every  itera0on  

12
 Carnegie Mellon

Calling  Strlen  
/* My version of strlen */
size_t strlen(const char *s)
{
size_t length = 0;
while (*s != '\0') {
s++;
length++;
}
return length;
}

 Strlen  performance  
 Only  way  to  determine  length  of  string  is  to  scan  its  en0re  length,  looking  for  
null  character.  
 Overall  performance,  string  of  length  N  
 N  calls  to  strlen  
 Require  0mes  N,  N-­‐1,  N-­‐2,  …,  1  
 Overall  O(N2)  performance  

13
 Carnegie Mellon

Improving  Performance  
void lower(char *s)
{
int i;
int len = strlen(s);
for (i = 0; i < len; i++)
if (s[i] >= 'A' && s[i] <= 'Z')
s[i] -= ('A' - 'a');
}

 Move  call  to  strlen  outside  of  loop  

 Since  result  does  not  change  from  one  itera0on  to  another  
 Form  of  code  mo0on  

14
 Carnegie Mellon

Lower  Case  Conversion  Performance  

 Time  doubles  when  double  string  length  
 Linear  performance  of  lower2  

200
180
160
140
CPU seconds

120
lower
100
80
60
40
20
lower2
0
0 50000 100000 150000 200000 250000 300000 350000 400000 450000 500000
String length

15
 Carnegie Mellon

Op*miza*on  Blocker:  Procedure  Calls  

 Why  couldn’t  compiler  move  strlen  out  of    inner  loop?  
 Procedure  may  have  side  effects  
 Alters  global  state  each  0me  called  
 Func0on  may  not  return  same  value  for  given  arguments  
 Depends  on  other  parts  of  global  state  
 Procedure  lower  could  interact  with  strlen  
 Warning:  
 Compiler  treats  procedure  call  as  a  black  box  
 Weak  op0miza0ons  near  them  
int lencnt = 0;
 Remedies:   size_t strlen(const char *s)
 Use  of  inline  func0ons   {
 GCC  does  this  with  –O2   size_t length = 0;
 See  web  aside  ASM:OPT  
while (*s != '\0') {
s++; length++;
 Do  your  own  code  mo0on   }
lencnt += length;
return length;
}
16
 Carnegie Mellon

Memory  MaHers  
/* Sum rows is of n X n matrix a
and store in vector b */
void sum_rows1(double *a, double *b, long n) {
long i, j;
for (i = 0; i < n; i++) {
b[i] = 0;
for (j = 0; j < n; j++)
b[i] += a[i*n + j];
}
}

# sum_rows1 inner loop

.L53:
addsd (%rcx), %xmm0 # FP add
addq $8, %rcx
decq %rax
movsd %xmm0, (%rsi,%r8,8) # FP store
jne .L53

 Code  updates  b[i]  on  every  itera0on  

 Why  couldn’t  compiler  op0mize  this  away?  
17
 Carnegie Mellon

Memory  Aliasing  
/* Sum rows is of n X n matrix a
and store in vector b */
void sum_rows1(double *a, double *b, long n) {
long i, j;
for (i = 0; i < n; i++) {
b[i] = 0;
for (j = 0; j < n; j++)
b[i] += a[i*n + j];
}
}

Value of B:
double A[9] = init: [4, 8, 16]
{ 0, 1, 2,
4, 8, 16},
i = 0: [3, 8, 16]
32, 64, 128};

double B[3] = A+3; i = 1: [3, 22, 16]

sum_rows1(A, B, 3); i = 2: [3, 22, 224]

 Code  updates  b[i]  on  every  itera0on  

 Must  consider  possibility  that  these  updates  will  affect  program  
behavior  
18
 Carnegie Mellon

Removing  Aliasing  
/* Sum rows is of n X n matrix a
and store in vector b */
void sum_rows2(double *a, double *b, long n) {
long i, j;
for (i = 0; i < n; i++) {
double val = 0;
for (j = 0; j < n; j++)
val += a[i*n + j];
b[i] = val;
}
}

# sum_rows2 inner loop

.L66:
addsd (%rcx), %xmm0 # FP Add
addq $8, %rcx
decq %rax
jne .L66

 No  need  to  store  intermediate  results  

19
 Carnegie Mellon

Op*miza*on  Blocker:  Memory  Aliasing  

 Aliasing  
 Two  different  memory  references  specify  single  loca0on  
 Easy  to  have  happen  in  C  
 Since  allowed  to  do  address  arithme0c  

  Direct  access  to  storage  structures  
 Get  in  habit  of  introducing  local  variables  
  Accumula0ng  within  loops  
  Your  way  of  telling  compiler  not  to  check  for  aliasing  

20
 Carnegie Mellon

Exploi*ng  Instruc*on-­‐Level  Parallelism  

 Need  general  understanding  of  modern  processor  design  
 Hardware  can  execute  mul0ple  instruc0ons  in  parallel  
 Performance  limited  by  data  dependencies  
 Simple  transforma*ons  can  have  drama*c  performance  
improvement  
 Compilers  oWen  cannot  make  these  transforma0ons  
 Lack  of  associa0vity  and  distribu0vity  in  floa0ng-­‐point  arithme0c  

21
 Carnegie Mellon

Benchmark  Example:  Data  Type  for  

Vectors  
/* data structure for vectors */
typedef struct{ len 0 1 len-1
int len;
double *data;
data
} vec;

/* retrieve vector element and store at val */

double get_vec_element(*vec, idx, double *val)
{
if (idx < 0 || idx >= v->len)
return 0;
*val = v->data[idx];
return 1;
}

22
 Carnegie Mellon

Benchmark  Computa*on  
void combine1(vec_ptr v, data_t *dest)
{
long int i; Compute  sum  or  
*dest = IDENT; product  of  vector  
for (i = 0; i < vec_length(v); i++) { elements  
data_t val;
get_vec_element(v, i, &val);
*dest = *dest OP val;
}
}

 Data  Types    Opera*ons  

 Use  different  declara0ons    Use  different  defini0ons  of  
for  data_t OP  and  IDENT
 int   + / 0
 float   * / 1
 double
23
 Carnegie Mellon

Cycles  Per  Element  (CPE)  

 Convenient  way  to  express  performance  of  program  that  operates  on  
vectors  or  lists  
 Length  =  n  
 In  our  case:  CPE  =  cycles  per  OP  
 T  =  CPE*n  +  Overhead  
 CPE  is  slope  of  line  

vsum1: Slope  =  4.0  

vsum2: Slope  =  3.5  

24
 Carnegie Mellon

Benchmark  Performance  
void combine1(vec_ptr v, data_t *dest)
{
long int i; Compute  sum  or  
*dest = IDENT; product  of  vector  
for (i = 0; i < vec_length(v); i++) { elements  
data_t val;
get_vec_element(v, i, &val);
*dest = *dest OP val;
}
}

Method! Integer! Double FP!

Operation! Add! Mult! Add! Mult!
Combine1 29.0! 29.2! 27.4! 27.9!
unoptimized!
Combine1 –O1! 12.0! 12.0! 12.0! 13.0!

25
 Carnegie Mellon

Basic  Op*miza*ons  
void combine4(vec_ptr v, data_t *dest)
{
int i;
int 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;
}

 Move  vec_length  out  of  loop  

 Avoid  bounds  check  on  each  cycle  
 Accumulate  in  temporary  

26
 Carnegie Mellon

Effect  of  Basic  Op*miza*ons  

void combine4(vec_ptr v, data_t *dest)
{
int i;
int 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;
}

Method! Integer! Double FP!

Operation! Add! Mult! Add! Mult!
Combine1 –O1! 12.0! 12.0! 12.0! 13.0!
Combine4! 2.0! 3.0! 3.0! 5.0!

 Eliminates  sources  of  overhead  in  loop  

27
 Carnegie Mellon

Modern  CPU  Design  

Instruc1on  Control  
Fetch   Address  
Re*rement   Control  
Unit   Instruc*on  
Register   Instruc*ons   Cache  
Instruc*on  
File   Decode  
Opera*ons  
Register  Updates   Predic*on  OK?  

Integer/   General   FP   FP   Func*onal  

Load   Store  
Branch   Integer   Add   Mult/Div   Units  

Opera*on  Results  
Addr.   Addr.  
Data   Data  

Data  
Cache  

Execu1on  
28
 Carnegie Mellon

Superscalar  Processor  
 Defini*on:  A  superscalar  processor  can  issue  and  execute  
mul1ple  instruc1ons  in  one  cycle.  The  instruc*ons  are  
retrieved  from  a  sequen*al  instruc*on  stream  and  are  
usually  scheduled  dynamically.  

 Benefit:  without  programming  effort,  superscalar  

processor  can  take  advantage  of  the  instruc1on  level  
parallelism  that  most  programs  have  

 Most  CPUs  since  about  1998  are  superscalar.  

 Intel:  since  Pen*um  Pro  

29
 Carnegie Mellon

Nehalem  CPU  
 Mul*ple  instruc*ons  can  execute  in  parallel  
1  load,  with  address  computa0on  
1  store,  with  address  computa0on  
2  simple  integer  (one  may  be  branch)  
1  complex  integer  (mul0ply/divide)  
1  FP  Mul0ply  
1  FP  Add  

 Some  instruc*ons  take  >  1  cycle,  but  can  be  pipelined  

Instruc1on  Latency  Cycles/Issue  
Load  /  Store  4  1  
Integer  Mul0ply  3  1  
Integer/Long  Divide  11-­‐-­‐21  11-­‐-­‐21  
Single/Double  FP  Mul0ply  4/5  1  
Single/Double  FP  Add  3  1  
Single/Double  FP  Divide  10-­‐-­‐23  10-­‐-­‐23  

30
 Carnegie Mellon

x86-­‐64  Compila*on  of  Combine4  

 Inner  Loop  (Case:  Integer  Mul*ply)  
.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

Method! Integer! Double FP!

Operation! Add! Mult! Add! Mult!
Combine4! 2.0! 3.0! 3.0! 5.0!
Latency 1.0! 3.0! 3.0! 5.0!
Bound!

31
 Carnegie Mellon

Combine4  =  Serial  Computa*on  (OP  =  *)  

1 d0
 Computa*on  (length=8)  
 ((((((((1 * d[0]) * d[1]) * d[2]) * d[3])
* * d[4]) * d[5]) * d[6]) * d[7])
d1
 Sequen*al  dependence  
* d2
 Performance:  determined  by  latency  of  OP  
* d3

* d4

* d5

* d6

* d7

32
 Carnegie Mellon

Loop  Unrolling  
void unroll2a_combine(vec_ptr v, data_t *dest)
{
int length = vec_length(v);
int limit = length-1;
data_t *d = get_vec_start(v);
data_t x = IDENT;
int 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;
}

 Perform  2x  more  useful  work  per  itera*on  

33
 Carnegie Mellon

Effect  of  Loop  Unrolling  

Method! Integer! Double FP!
Operation! Add! Mult! Add! Mult!
Combine4! 2.0! 3.0! 3.0! 5.0!
Unroll 2x! 2.0! 1.5! 3.0! 5.0!
Latency 1.0! 3.0! 3.0! 5.0!
Bound!

 Helps  integer  mul*ply  

 below  latency  bound  
 Compiler  does  clever  op0miza0on  
 Others  don’t  improve.  Why?  
 S0ll  sequen0al  dependency  
x = (x OP d[i]) OP d[i+1];

34
 Carnegie Mellon

Loop  Unrolling  with  Reassocia*on  

void unroll2aa_combine(vec_ptr v, data_t *dest)
{
int length = vec_length(v);
int limit = length-1;
data_t *d = get_vec_start(v);
data_t x = IDENT;
int 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]; Compare  to  before  
}
*dest = x; x = (x OP d[i]) OP d[i+1];
}

 Can  this  change  the  result  of  the  computa*on?  

 Yes,  for  FP.  Why?  
35
 Carnegie Mellon

Effect  of  Reassocia*on  

Method! Integer! Double FP!
Operation! Add! Mult! Add! Mult!
Combine4! 2.0! 3.0! 3.0! 5.0!
Unroll 2x! 2.0! 1.5! 3.0! 5.0!
Unroll 2x, 2.0! 1.5! 1.5! 3.0!
reassociate!
Latency 1.0! 3.0! 3.0! 5.0!
Bound!
Throughput 1.0! 1.0! 1.0! 1.0!
Bound!

 Nearly  2x  speedup  for  Int  *,  FP  +,  FP  *  

 Reason:  Breaks  sequen0al  dependency  
x = x OP (d[i] OP d[i+1]);

 Why  is  that?  (next  slide)  

36
 Carnegie Mellon

Reassociated  Computa*on  
x = x OP (d[i] OP d[i+1]);  What  changed:  
 Ops  in  the  next  itera0on  can  be  
started  early  (no  dependency)  
d0 d1

*  Overall  Performance  
d2 d3
1  N  elements,  D  cycles  latency/op  
* d4 d5  Should  be  (N/2+1)*D  cycles:  
* CPE  =  D/2  
* d6 d7  Measured  CPE  slightly  worse  for  
* FP  mult  
*
*

37
 Carnegie Mellon

Loop  Unrolling  with  Separate  Accumulators  

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

 Different  form  of  reassocia*on  

38
 Carnegie Mellon

Effect  of  Separate  Accumulators  

Method! Integer! Double FP!
Operation! Add! Mult! Add! Mult!
Combine4! 2.0! 3.0! 3.0! 5.0!
Unroll 2x! 2.0! 1.5! 3.0! 5.0!
Unroll 2x, 2.0! 1.5! 1.5! 3.0!
reassociate!
Unroll 2x Parallel 2x! 1.5! 1.5! 1.5! 2.5!
Latency Bound! 1.0! 3.0! 3.0! 5.0!
Throughput Bound! 1.0! 1.0! 1.0! 1.0!

 2x  speedup  (over  unroll2)  for  Int  *,  FP  +,  FP  *  

 Breaks  sequen0al  dependency  in  a  “cleaner,”  more  obvious  way  
x0 = x0 OP d[i];
x1 = x1 OP d[i+1];

39
 Carnegie Mellon

Separate  Accumulators  
x0 = x0 OP d[i];  What  changed:  
x1 = x1 OP d[i+1];  Two  independent  “streams”  of  
opera0ons  
1 d0 1 d1
 Overall  Performance  
* d2 * d3  N  elements,  D  cycles  latency/op  
* d4 * d5
 Should  be  (N/2+1)*D  cycles:  
CPE  =  D/2  
* d6 * d7  CPE  matches  predic0on!  

* *
What  Now?  
*

40
 Carnegie Mellon

Unrolling  &  Accumula*ng  

 Idea  
 Can  unroll  to  any  degree  L  
 Can  accumulate  K  results  in  parallel  
 L  must  be  mul0ple  of  K  

 Limita*ons  
 Diminishing  returns  
Cannot  go  beyond  throughput  limita0ons  of  execu0on  units  

 Large  overhead  for  short  lengths  
 Finish  off  itera0ons  sequen0ally  

41
 Carnegie Mellon

Unrolling  &  Accumula*ng:  Double  *  

 Case  
 Intel  Nehelam  (Shark  machines)  
 Double  FP  Mul0plica0on  
 Latency  bound:  5.00.    Throughput  bound:  1.00    
FP  *   Unrolling  Factor  L  
K   1   2   3   4   6   8   10   12  
1   5.00   5.00   5.00   5.00   5.00   5.00  
Accumulators  

2   2.50   2.50   2.50  

3   1.67  
4   1.25   1.25  
6   1.00   1.19  
8   1.02  
10   1.01  
12   1.00  

42
 Carnegie Mellon

Unrolling  &  Accumula*ng:  Int  +  

 Case  
 Intel  Nehelam  (Shark  machines)  
 Integer  addi0on  
 Latency  bound:  1.00.    Throughput  bound:  1.00    
FP  *   Unrolling  Factor  L  
K   1   2   3   4   6   8   10   12  
1   2.00   2.00   1.00   1.01   1.02   1.03  
Accumulators  

2   1.50   1.26   1.03  

3   1.00  
4   1.00   1.24  
6   1.00   1.02  
8   1.03  
10   1.01  
12   1.09  

43
 Carnegie Mellon

Achievable  Performance  
Method! Integer! Double FP!
Operation! Add! Mult! Add! Mult!
Scalar Optimum! 1.00! 1.00! 1.00! 1.00!
Latency Bound! 1.00! 3.00! 3.00! 5.00!
Throughput Bound! 1.00! 1.00! 1.00! 1.00!

 Limited  only  by  throughput  of  func*onal  units  

 Up  to  29X  improvement  over  original,  unop*mized  code  

44
 Carnegie Mellon

Using  Vector  Instruc*ons  

Method! Integer! Double FP!
Operation! Add! Mult! Add! Mult!
Scalar Optimum! 1.00! 1.00! 1.00! 1.00!
Vector Optimum! 0.25! 0.53! 0.53! 0.57!
Latency Bound! 1.00! 3.00! 3.00! 5.00!
Throughput Bound! 1.00! 1.00! 1.00! 1.00!
Vec Throughput 0.25! 0.50! 0.50! 0.50!
Bound!

 Make  use  of  SSE  Instruc*ons  

 Parallel  opera0ons  on  mul0ple  data  elements  
 See  Web  Aside  OPT:SIMD  on  CS:APP  web  page  

45
 Carnegie Mellon

What  About  Branches?  

 Challenge  
 Instruc0on  Control  Unit  must  work  well  ahead  of  Execu0on  Unit  
to  generate  enough  opera0ons  to  keep  EU  busy  

80489f3: movl $0x1,%ecx

80489f8: xorl %edx,%edx Execu*ng  
80489fa: cmpl %esi,%edx
80489fc: jnl 8048a25 How  to  con*nue?  
80489fe: movl %esi,%esi
8048a00: imull (%eax,%edx,4),%ecx

 When  encounters  condi0onal  branch,  cannot  reliably  determine  where  to  

con0nue  fetching  

46
 Carnegie Mellon

Modern  CPU  Design  

Instruc1on  Control  
Fetch   Address  
Re*rement   Control  
Unit   Instruc*on  
Register   Instruc*ons   Cache  
Instruc*on  
File   Decode  
Opera*ons  
Register  Updates   Predic*on  OK?  

Integer/   General   FP   FP   Func*onal  

Load   Store  
Branch   Integer   Add   Mult/Div   Units  

Opera*on  Results  
Addr.   Addr.  
Data   Data  

Data  
Cache  

Execu1on  
47
 Carnegie Mellon

Branch  Outcomes  
 When  encounter  condi*onal  branch,  cannot  determine  where  to  con*nue  
fetching  
 Branch  Taken:  Transfer  control  to  branch  target  
 Branch  Not-­‐Taken:  Con0nue  with  next  instruc0on  in  sequence  
 Cannot  resolve  un*l  outcome  determined  by  branch/integer  unit  

80489f3: movl $0x1,%ecx

80489f8: xorl %edx,%edx
80489fa: cmpl %esi,%edx Branch  Not-­‐Taken  
80489fc: jnl 8048a25
80489fe: movl %esi,%esi
8048a00: imull (%eax,%edx,4),%ecx Branch  Taken  
8048a25: cmpl %edi,%edx
8048a27: jl 8048a20
8048a29: movl 0xc(%ebp),%eax
8048a2c: leal 0xffffffe8(%ebp),%esp
8048a2f: movl %ecx,(%eax)
48
 Carnegie Mellon

Branch  Predic*on  
 Idea  
 Guess  which  way  branch  will  go  
 Begin  execu0ng  instruc0ons  at  predicted  posi0on  
 But  don’t  actually  modify  register  or  memory  data  
80489f3: movl $0x1,%ecx
80489f8: xorl %edx,%edx
80489fa: cmpl %esi,%edx Predict  Taken  
80489fc: jnl 8048a25
. . .

8048a25: cmpl %edi,%edx

8048a27: jl 8048a20 Begin  
8048a29: movl 0xc(%ebp),%eax Execu*on  
8048a2c: leal 0xffffffe8(%ebp),%esp
8048a2f: movl %ecx,(%eax)

49
 Carnegie Mellon

Branch  Predic*on  Through  Loop  

80488b1: movl (%ecx,%edx,4),%eax Assume    
80488b4: addl %eax,(%edi) vector  length  =  100  
80488b6: incl %edx
80488b7: cmpl %esi,%edx i  =  98  
80488b9: jl 80488b1
Predict  Taken  (OK)  
80488b1: movl (%ecx,%edx,4),%eax
80488b4: addl %eax,(%edi)
80488b6: incl %edx
80488b7: cmpl %esi,%edx i  =  99  
80488b9: jl 80488b1 Predict  Taken  
80488b1: movl (%ecx,%edx,4),%eax (Oops)  
80488b4: addl %eax,(%edi)
80488b6: incl %edx Read   Executed  
80488b7: cmpl %esi,%edx i  =  100   invalid  
80488b9: jl 80488b1 loca*on  
80488b1: movl (%ecx,%edx,4),%eax
80488b4: addl %eax,(%edi) Fetched  
80488b6: incl %edx
80488b7: cmpl %esi,%edx i  =  101  
80488b9: jl 80488b1
50
 Carnegie Mellon

Branch  Mispredic*on  Invalida*on  

80488b1: movl (%ecx,%edx,4),%eax Assume    
80488b4: addl %eax,(%edi) vector  length  =  100  
80488b6: incl %edx
80488b7: cmpl %esi,%edx i  =  98  
80488b9: jl 80488b1
Predict  Taken  (OK)  
80488b1: movl (%ecx,%edx,4),%eax
80488b4: addl %eax,(%edi)
80488b6: incl %edx
80488b7: cmpl %esi,%edx i  =  99  
80488b9: jl 80488b1
Predict  Taken  (Oops)  
80488b1: movl (%ecx,%edx,4),%eax
80488b4: addl %eax,(%edi)
80488b6: incl %edx
80488b7: cmpl %esi,%edx i  =  100  
80488b9: jl 80488b1 Invalidate  
80488b1: movl (%ecx,%edx,4),%eax
80488b4: addl %eax,(%edi)
80488b6: incl %edx i  =  101  

51
 Carnegie Mellon

Branch  Mispredic*on  Recovery  

80488b1: movl (%ecx,%edx,4),%eax
80488b4: addl %eax,(%edi)
80488b6: incl %edx
80488b7: cmpl %esi,%edx i  =  99  
80488b9: jl 80488b1
80488bb: leal 0xffffffe8(%ebp),%esp
Definitely  not  taken  
80488be: popl %ebx
80488bf: popl %esi
80488c0: popl %edi

 Performance  Cost  
 Mul0ple  clock  cycles  on  modern  processor  
 Can  be  a  major  performance  limiter  

52
 Carnegie Mellon

Effect  of  Branch  Predic*on  

 Loops   void combine4b(vec_ptr v,
data_t *dest)
 Typically,  only  miss  when   {
hit  loop  end   long int i;
 Checking  code   long int length = vec_length(v);
data_t acc = IDENT;
 Reliably  predicts  that  error   for (i = 0; i < length; i++) {
won’t  occur   if (i >= 0 && i < v->len) {
acc = acc OP v->data[i];
}
}
*dest = acc;
}

Method! Integer! Double FP!

Operation! Add! Mult! Add! Mult!
Combine4! 2.0! 3.0! 3.0! 5.0!
Combine4b! 4.0! 4.0! 4.0! 5.0!
53
 Carnegie Mellon

Gesng  High  Performance  

 Good  compiler  and  flags  
 Don’t  do  anything  stupid  
 Watch  out  for  hidden  algorithmic  inefficiencies  
 Write  compiler-­‐friendly  code  
Watch  out  for  op0miza0on  blockers:    

procedure  calls  &  memory  references  
 Look  carefully  at  innermost  loops  (where  most  work  is  done)  

 Tune  code  for  machine  

 Exploit  instruc0on-­‐level  parallelism  
 Avoid  unpredictable  branches  
 Make  code  cache  friendly  (Covered  later  in  course)  

54