Getting High Performance 15 213 Don Don t Do Anything Stupid The course that gives CMU its Zip Code Optimization II September 27 2006 Watch out for hidden algorithmic inefficiencies Write compiler friendly code z Help compiler past optimization blockers function calls memory refs Tune Code For Machine Topics Machine Dependent Optimizations z Understanding Processor Operations z Branches and Branch Prediction Exploit instruction level parallelism Avoid unpredictable branches Make code cache friendly z Covered later in course Modern CPU Design CPU Capabilities of Pentium IV Multiple Instructions Can Execute in Parallel Instruction Instruction Control Control Address Fetch Control Retirement Unit Register File Register Updates 15 213 F 06 2 class09 ppt Instruction Cache Instrs Instruction Decode Operations Prediction OK Integer General Branch Integer FP Add FP Mult Div Load Store Functional Units Some Instructions Take 1 Cycle but Can be Pipelined Operation Results Addr Addr Data Data Data Cache Execution Execution 3 15 213 F 06 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 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 Translating into Operations Instruction Instruction Control Control Retirement Unit Register File Fetch Control Goal Each Operation Utilizes Single Functional Unit Address Instruction Cache Instrs Instruction Decode Operations 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 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 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 Converts Register References Into Tags Abstract identifier linking destination of one operation with sources of later operations 15 213 F 06 5 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 I3 Dataflow View of Instruction Execution rax 0 rbx 0 rdx 0 addq andq mulq xorq I2 15 213 F 06 6 rax rbx rcx rbx rbx rdx rbx rdi rdi 0 rbx 1 rbx 2 rdx 1 I4 Registers are fixed storage locations rdi 0 Functional View z Individual instructions read write them 7 I1 Imperative View I1 I2 I3 I4 I2 I3 I4 rcx 0 Instructions must be executed in specified sequence to guarantee proper program behavior 15 213 F 06 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 Cycles Per Element 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 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 Use different declarations for data t int float double Cycles 600 Data Types Operations 500 300 200 0 100 1 0 0 50 15 213 F 06 x86 64 Compilation of Combine4 Serial Computation d1 Loop eax edx 4 ebx temp d i edx i ebx ecx x temp esi edx i length L33 if goto Loop Computation length 12 d2 d4 d5 Performance d6 N instructions in 2 clock cycles Integer 2 20 d7 Floating Point 10 00 5 00 elements D cycles operation N D cycles d8 7 00 Method Combine4 11 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 Performance Combine4 200 15 213 F 06 Inner Loop Integer Multiply Method 150 10 1 d0 5 100 Elements 9 L33 movl incl imull cmpl jl vsum2 Slope 3 5 400 Use different definitions of OP and IDENT 15 213 F 06 12 Integer 2 20 10 00 Floating Point 5 00 7 00 d9 d10 d11 15 213 F 06 Loop Unrolling Effect of 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 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 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 Don t Improve Sequential dependency z Each operation must wait until previous one completes x x OPER d i OPER d i 1 Perform 2x more useful work per iteration 13 15 Method 15 213 F 06 14 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 While computing result for iteration i can precompute d i 2 d i 3 for iteration i 2 Could change numerical results for FP 15 213 F 06 16 15 213 F 06 Reassociated Computation 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 2 x0 x0 OPER d i x1 x1 OPER d i 1 Finish any remaining elements for i length i x0 x0 OPER d i dest x0 OPER x1 Performance N d0 d1 1 d2 d3 Measured for FP d4 d5 elements D cycles operation cycles Should be …
View Full Document
Unlocking...