15 213 The course that gives CMU its Zip Code Optimization II Dec 2 2008 Topics Machine Dependent Optimizations z Understanding Processor Operations z Branches and Branch Prediction class26 ppt Motivate Compute Factorials int rfact int n if n 1 return 1 return n rfact n 1 Machines 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 Cycles Per Element z Fish Machines Intel Core 2 2 7 GHz Compiler Versions 2 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 Faster Versions 1 int fact u3a int n int i int result 1 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 Loop Unrolling 3 Compute more values per iteration Does not help here 15 213 F 08 Faster Versions 2 int fact u3b int n int i int result 1 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 Reassociation 3X drop for GCC 3 4 No improvement for GCC 4 1 z Very strange 4 15 213 F 08 Faster Versions 3 int fact u3c int n int i int result0 1 int result1 1 int result2 1 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 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 fact u3c 3 3 1 0 1 0 Loop Unrolling Multiple Accumulators 5 3X drop for all machines 15 213 F 08 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 6 15 213 F 08 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 7 15 213 F 08 Pentium IV Nocona CPU 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 Instruction Load Store Integer Multiply Integer Long Divide Single Double FP Multiply Single Double FP Add Single Double FP Divide 8 Latency 5 10 36 106 7 5 32 46 Cycles Issue 1 1 36 106 2 2 32 46 15 213 F 08 CPUs Nocona vs Core 2 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 Core 2 2 7 GHz Recent Intel microprocessors 9 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 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 10 Abstract identifier linking destination of one operation with sources of later operations 15 213 F 08 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 11 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 08 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 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 rcx 0 rdi 0 rbx 1 I2 I3 rbx 2 rdx 1 I4 rdi 1 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 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 14 Operations Use different definitions of OP and IDENT 0 1 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 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 15 15 213 F 08 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 16 Integer 2 20 Floating Point 10 …
View Full Document
Unlocking...