复旦大学：《计算机原理 Computer System》课程PPT课件_12b Code Optimization（• Machine-Independent Optimization – Code motion – Memory optimization • Suggested reading）

Code Optimization

1 Code Optimization

Outline Machine-Independent Optimization Code motion Memory optimization Suggested reading -5.2~56

2 Outline • Machine-Independent Optimization – Code motion – Memory optimization • Suggested reading – 5.2 ~ 5.6

Motivation Constant factors matter too easily see 10: 1 performance range depending on how code is written must optimize at multiple levels algorithm, data representations, procedures, and loops

3 Motivation • Constant factors matter too! – easily see 10:1 performance range depending on how code is written – must optimize at multiple levels • algorithm, data representations, procedures, and loops

Motivation Must understand system to optimize performance how programs are compiled and executed how to measure program performance and identify bottlenecks how to improve performance without destroying code modularity and generality

4 Motivation • Must understand system to optimize performance – how programs are compiled and executed – how to measure program performance and identify bottlenecks – how to improve performance without destroying code modularity and generality

5. 2 Expressing Program Performance

5 5.2 Expressing Program Performance

Time Scales P382 Absolute Time Typically use nanoseconds 10-9 seconds Time scale of computer instructions

6 Time Scales P382 • Absolute Time – Typically use nanoseconds • 10–9 seconds – Time scale of computer instructions

Time Scales Clock Cycles Most computers controlled by high frequency clock signal Typical Range 100 MHZ 108 cycles per second Clock period = 10ns ·26Hz 2 X 109 cycles per second Clock period =0.5ns

7 Time Scales • Clock Cycles – Most computers controlled by high frequency clock signal – Typical Range • 100 MHz – 108 cycles per second – Clock period = 10ns • 2 GHz – 2 X 109 cycles per second – Clock period = 0.5ns

CPE P383 1 void vsuml (int n) 2{ in七i 345678 for(i=0;主<n;i++) c[i]=a[i]+b[i];

8 CPE P383 1 void vsum1(int n) 2 { 3 int i; 4 5 for (i = 0; i < n; i++) 6 c[i] = a[i] + b[i]; 7 } 8

CPE P383 9/* Sum vector of n elements (n must be even)*/ 10 void vsum2 (int n) 11{ 12 int i 13 14 for(主=0;i<n;i+=2){ 15 /* Compute two elements per iteration * 16 cli= ali] bli] 17 c[i+1]=a[i+1]+b[i+1]; 18 19}

9 CPE P383 9 /* Sum vector of n elements (n must be even) */ 10 void vsum2(int n) 11 { 12 int i; 13 14 for (i = 0; i < n; i+=2) { 15 /* Compute two elements per iteration */ 16 c[i] = a[i] + b[i]; 17 c[i+1] = a[i+1] + b[i+1]; 18 } 19 }

Cycles per element Convenient way to express performance of program that operators on vectors or lists Length = n T= CPE 大n+ Overhea

10 Cycles Per Element • Convenient way to express performance of program that operators on vectors or lists • Length = n • T = CPE*n + Overhead