15 213 Code Optimization II September 26 2007 Topics class09 ppt Machine Dependent Optimizations Understanding Processor Operations Branches and Branch Prediction 15 213 F 07 Getting High Performance Don t Do Anything Stupid Watch out for hidden algorithmic inefficiencies Write compiler friendly code Help compiler past optimization blockers function calls memory refs Tune Code For Machine Exploit instruction level parallelism Avoid unpredictable branches Make code cache friendly Covered later in course 2 15 213 Intro to Computer Systems Fall 2007 Modern CPU Design Instruction Control Retirement Unit Register File Register Updates Address Fetch Control Instruction Cache Instrs Instruction Decode Operations Prediction OK Integer General Branch Integer FP Add Operation Results FP Mult Div Load Store Addr Addr Data Data Cache Execution 3 15 213 Intro to Computer Systems Fall 2007 Data Functional Units CPU Capabilities of Pentium IV Multiple Instructions Can Execute in Parallel 1 load with address computation 1 store with address computation 2 simple integer one may be branch 1 complex integer multiply divide 1 FP SSE3 unit 1 FP move does all conversions Some Instructions Take 1 Cycle but Can be Pipelined 4 Instruction Load Store Integer Multiply Integer Long Divide Single Double FP Multiply Single Double FP Add Single Double FP Divide LatencyCycles Issue 51 101 36 10636 106 72 52 32 4632 46 15 213 Intro to Computer Systems Fall 2007 Instruction Control Instruction Control Retirement Unit Register File Fetch Control Address Instrs Instruction Decode Operations Instruction Cache Grabs Instruction Bytes From Memory Based on current PC predicted targets for predicted branches Hardware dynamically guesses whether branches taken not taken and possibly branch target Translates Instructions Into Operations for CISC style CPUs Primitive steps required to perform instruction Typical instruction requires 1 3 operations Converts Register References Into Tags 5 Abstract identifier linking destination of one operation with sources of later operations 15 213 Intro to Computer Systems Fall 2007 Translating into Operations Goal Each Operation Utilizes Single Functional Unit Requires Load Integer arithmetic Store Exact form and format of operations is trade secret Operations split up instruction into simpler pieces Devise temporary names to describe how result of one operation gets used by other operations addq rax 8 rbx rdx 4 load 8 rbx rdx 4 imull rax temp1 store temp2 8 rbx rdx 4 6 temp1 temp2 15 213 Intro to Computer Systems Fall 2007 Traditional View of Instruction Execution rax I1 addq andq mulq xorq rax rbx rcx rbx rbx rdx rbx rdi I1 I2 I3 I4 rbx rdx rcx I2 I3 I4 Imperative View Registers are fixed storage locations Individual instructions read write them 7 rdi Instructions must be executed in specified sequence to guarantee proper program behavior 15 213 Intro to Computer Systems Fall 2007 Dataflow View of Instruction Execution rax 0 rbx 0 rdx 0 addq andq mulq xorq rax rbx rcx rbx rbx rdx rbx rdi I1 I2 I3 I4 I1 rcx 0 rdi 0 rbx 1 I2 I3 rbx 2 rdx 1 I4 rdi 0 Functional View 8 View each write as creating new instance of value Operations can be performed as soon as operands available No need to execute in original sequence 15 213 Intro to Computer Systems Fall 2007 Example Computation 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 Data Types 9 Operations Use different declarations for data t int float 0 double 1 Use different definitions of OP and IDENT 15 213 Intro to Computer Systems Fall 2007 Cycles Per Element Convenient way to express performance of program that operators on vectors or lists Length n T CPE n Overhead 1000 900 800 vsum1 Slope 4 0 700 Cycles 600 500 vsum2 Slope 3 5 400 300 200 100 0 0 50 100 Elements 10 15 213 Intro to Computer Systems Fall 2007 150 200 x86 64 Compilation of Combine4 Inner Loop Integer Multiply L33 movl incl imull cmpl jl Loop eax edx 4 ebx temp d i edx i ebx ecx x temp esi edx i length L33 if goto Loop Performance 5 instructions in 2 clock cycles Method Combine4 11 Integer 2 20 Floating Point 10 00 15 213 Intro to Computer Systems Fall 2007 5 00 7 00 1 d0 Serial Computation d1 Computation length 12 d2 1 d 0 d 1 d 2 d 3 d 4 d 5 d 6 d 7 d 8 d 9 d 10 d 11 d3 d4 d5 Performance d6 N d7 N D Combine4 12 Integer 2 20 10 00 Floating Point 5 00 cycles d8 Method elements D cycles operation d9 7 00 15 213 Intro to Computer Systems Fall 2007 d10 d11 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 OPER d i OPER d i 1 Finish any remaining elements for i length i x x OPER d i dest x 13 Perform 2x more useful work per iteration 15 213 Intro to Computer Systems Fall 2007 Effect of Loop Unrolling Method Integer Floating Point Combine4 2 20 10 00 5 00 7 00 Unroll 2 1 50 10 00 5 00 7 00 Helps Integer Sum Before 5 operations per element After 6 operations per 2 elements 3 operations per element Others Don t Improve Sequential dependency Each operation must wait until previous one completes x x OPER d i OPER d i 1 14 15 213 Intro to Computer Systems Fall 2007 Loop Unrolling with Reassociation 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 OPER d i OPER d i 1 Finish any remaining elements for i length i x x OPER d i dest x 15 Could change numerical results for FP 15 213 Intro to Computer Systems Fall 2007 Effect of Reassociation Method Integer Floating Point Combine4 2 20 10 00 5 00 7 00 Unroll 2 1 50 10 00 5 00 7 00 2X2 reassociate 1 56 5 00 2 75 3 62 Nearly 2X speedup for Int FP FP Breaks sequential dependency x x OPER d i OPER d i 1 16 While computing result for iteration i can precompute d i 2 d i 3 for iteration i 2 15 213 Intro to Computer Systems Fall 2007 Reassociated Computation Performance N elements D cycles operation Should be N 2 1 D cycles d0 d1 1 CPE D 2 d2 d3 Measured for FP d4 d5 x x OPER d i OPER d i 1 d6 d7 d8 d9 d10 d11 17 CPE slightly worse 15 213 Intro to Computer Systems Fall 2007 Loop Unrolling with Separate Accum void unroll2a combine vec ptr v …
View Full Document
Unlocking...