15 213 The course that gives CMU its Zip Code Optimization II September 27 2006 Topics Machine Dependent Optimizations z Understanding Processor Operations z Branches and Branch Prediction class09 ppt Getting High Performance Don t Do Anything Stupid Watch out for hidden algorithmic inefficiencies Write compiler friendly code z Help compiler past optimization blockers function calls memory refs Tune Code For Machine Exploit instruction level parallelism Avoid unpredictable branches Make code cache friendly z Covered later in course 2 15 213 F 06 Modern CPU Design Instruction Instruction Control 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 Addr Store Functional Units Addr Data Data Data Cache Execution Execution 3 15 213 F 06 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 Latency 5 10 36 106 7 5 32 46 Cycles Issue 1 1 36 106 2 2 32 46 15 213 F 06 Instruction Control Instruction Instruction Control 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 F 06 Translating into Operations Goal Each Operation Utilizes Single Functional Unit addq rax 8 rbx rdx 4 Requires Load Integer arithmetic Store load 8 rbx rdx 4 imull rax temp1 store temp2 8 rbx rdx 4 6 temp1 temp2 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 15 213 F 06 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 rdi I2 I3 I4 Imperative View Registers are fixed storage locations z Individual instructions read write them 7 Instructions must be executed in specified sequence to guarantee proper program behavior 15 213 F 06 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 F 06 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 Use different declarations for data t int float double 9 Operations Use different definitions of OP and IDENT 0 1 15 213 F 06 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 150 200 Elements 10 15 213 F 06 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 5 00 7 00 15 213 F 06 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 elements D cycles operation N D cycles d8 Method Combine4 12 Integer 2 20 10 00 Floating Point 5 00 7 00 d9 d10 d11 15 213 F 06 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 F 06 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 z 3 operations per element Others Don t Improve Sequential dependency z Each operation must wait until previous one completes x x OPER d i OPER d i 1 14 15 213 F 06 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 F 06 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 F 06 Reassociated Computation Performance N elements D cycles operation Should be N 2 1 D cycles d0 d1 1 z CPE D 2 d2 d3 Measured for FP d4 d5 x x OPER d i OPER d i 1 d6 d7 CPE slightly worse d8 d9 d10 d11 17 15 213 F 06 Loop Unrolling with Separate Accum 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 …
View Full Document
Unlocking...