Motivate Compute Factorials 15 213 int rfact int n if n 1 return 1 return n rfact n 1 The course that gives CMU its Zip Code Optimization II Dec 2 2008 Machines Topics Machine Dependent Optimizations int fact int n int i int result 1 for i n i 0 i result result i return result Intel Pentium 4 Nocona 3 2 GHz z Understanding Processor Operations z Branches and Branch Prediction Intel Core 2 2 7 GHz Compiler Versions Faster Versions 1 for i n i 3 i 3 result result i i 1 i 2 for i 0 i result i return result Machine Compiler Nocona Core 2 3 4 3 4 4 1 rfact 15 5 6 0 3 0 fact 10 0 3 0 3 0 GCC 3 4 2 current on Fish machines GCC 4 1 2 most recent available 15 213 F 08 2 class26 ppt int fact u3a int n int i int result 1 Cycles Per Element z Fish Machines Faster Versions 2 int fact u3b int n int i int result 1 Cycles Per Element Machine Compiler Nocona Core 2 3 4 3 4 4 1 rfact 15 5 6 0 3 0 fact 10 0 3 0 3 0 fact u3a 10 0 3 0 3 0 for i n i 3 i 3 result result i i 1 i 2 for i 0 i result i return result Cycles Per Element Machine Compiler Nocona Core 2 3 4 3 4 4 1 rfact 15 5 6 0 3 0 fact 10 0 3 0 3 0 fact u3a 10 0 3 0 3 0 fact u3b 3 3 1 0 3 0 Loop Unrolling Loop Unrolling Reassociation Compute more values per iteration 3X drop for GCC 3 4 Does not help here No improvement for GCC 4 1 z Very strange 3 15 213 F 08 4 15 213 F 08 Faster Versions 3 Getting High Performance int fact u3c int n int i int result0 1 int result1 1 int result2 1 Don Don t Do Anything Stupid Cycles Per Element Machine Nocona Compiler for i n i 3 i 3 result0 i result1 i 1 result2 i 2 for i 0 i result0 i return result0 result1 result2 Core 2 3 4 3 4 4 1 rfact 15 5 6 0 3 0 fact 10 0 3 0 3 0 fact u3a 10 0 3 0 3 0 fact u3b 3 3 1 0 3 0 fact u3c 3 3 1 0 1 0 Write compiler friendly code refs Tune Code For Machine Exploit instruction level parallelism Avoid unpredictable branches Make code cache friendly z Covered later in course Loop Unrolling Multiple Accumulators 3X drop for all machines 15 213 F 08 5 Modern CPU Design Multiple Instructions Can Execute in Parallel Register Updates Address Fetch Control Retirement Unit Register File 15 213 F 08 6 Pentium IV Nocona CPU Instruction Instruction Control 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 Instruction Load Store Integer Multiply Integer Long Divide Single Double FP Multiply Single Double FP Add Single Double FP Divide Data Data Cache Execution Execution 15 213 F 08 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 Addr Data 7 Watch out for hidden algorithmic inefficiencies z Help compiler past optimization blockers function calls memory 8 Latency 5 10 36 106 7 5 32 46 Cycles Issue 1 1 36 106 2 2 32 46 15 213 F 08 Instruction Control CPUs Nocona vs Core 2 Instruction Instruction Control Control Nocona 3 2 GHz Saltwater fish machines Instruction Load Store Integer Multiply Integer Long Divide Single Double FP Multiply Single Double FP Add Single Double FP Divide Latency 10 10 36 106 7 5 32 46 Cycles Issue 1 1 36 106 2 2 32 46 Load Store Integer Multiply Integer Long Divide Single Double FP Multiply Single Double FP Add Single Double FP Divide 5 3 18 50 4 3 18 32 1 1 18 50 1 1 18 32 15 213 F 08 9 Goal Each Operation Utilizes Single Functional Unit 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 Abstract identifier linking destination of one operation with sources of later operations 15 213 F 08 10 rax I1 addq andq mulq xorq Requires Load Integer arithmetic Store temp1 temp2 rax rbx rcx rbx rbx rdx rbx rdi I1 I2 I3 I4 rbx rdx rcx 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 08 rdi I2 I3 I4 Imperative View Registers are fixed storage locations z Individual instructions read write them 11 Instruction Cache Instrs Instruction Decode Operations Based on current PC predicted targets for predicted branches Hardware dynamically guesses whether branches taken not taken and possibly branch target addq rax 8 rbx rdx 4 load 8 rbx rdx 4 imull rax temp1 store temp2 8 rbx rdx 4 Address Traditional View of Instruction Execution Translating into Operations Fetch Control Grabs Instruction Bytes From Memory Core 2 2 7 GHz Recent Intel microprocessors Retirement Unit Register File 12 Instructions must be executed in specified sequence to guarantee proper program behavior 15 213 F 08 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 Example Computation rcx 0 rdi 0 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 rbx 1 I2 I3 rbx 2 rdx 1 I4 Data Types Functional View 13 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 08 Cycles Per Element Convenient way to express performance of program that operators on vectors or lists Length n T CPE n Overhead double 0 1 15 213 F 08 L33 movl incl imull cmpl jl vsum1 Slope 4 0 eax edx 4 ebx edx ebx ecx esi edx L33 Loop temp d i i x temp i length if goto Loop Performance 600 5 500 vsum2 Slope 3 5 400 Use different definitions of OP and IDENT Inner Loop Integer Multiply 900 Cycles float 14 1000 700 Operations x86 64 Compilation of Combine4 800 Use different declarations for data t int rdi 1 instructions in 2 clock cycles 300 Method 200 Combine4 Integer 2 20 Floating Point 10 00 5 00 7 00 100 0 0 50 100 150 200 Elements …
View Full Document
Unlocking...