15213 Recitation Section C Shimin Chen Oct 21 2002 Outline Loop Unrolling Blocking Lab 4 Reminders Due Thursday Oct 24 11 59pm Submission is online NOT automatic Class web page Labs L4 http www cs cmu edu afs cs academic clas s 15213 f02 www L4 html 15213 Recitation C 2 Shimin Chen Loop Unrolling void combine5 vec ptr v int dest int length vec length v int limit length 2 int data get vec start v int sum 0 int i Combine 3 elements at a time for i 0 i limit i 3 sum data i data i 1 data i 2 Finish any remaining elements for i length i sum data i dest sum 15213 Recitation C 3 Combine multiple iterations into single loop body Amortizes loop overhead across multiple iterations Finish extras at end Shimin Chen Practice Problem Problem 5 12 and 5 13 15213 Recitation C 4 Shimin Chen Solution 5 12 void inner5 vec ptr u vec ptr v data t dest int i int length vec length u int limit length 3 data t udata get vec start u data t vdata get vec start v data t sum data t 0 Do four elements at a time for i 0 i limit i 4 sum udata i vdata i udata i 1 vdata i 1 udata i 2 vdata i 2 udata i 3 vdata i 3 Finish off any remaining elements for i length i sum udata i vdata i dest sum 15213 Recitation C 5 Shimin Chen Solution 5 12 A We must perform two loads per element to read values for udata and vdata There is only one unit to perform these loads and it requires one cycle B The performance for floating point is still limited by the 3 cycle latency of the floating point adder 15213 Recitation C 6 Shimin Chen Solution 5 13 void inner6 vec ptr u vec ptr v data t dest int i int length vec length u int limit length 3 data t udata get vec start u data t vdata get vec start v data t sum0 data t 0 data t sum1 data t 0 Do four elements at a time for i 0 i limit i 4 sum0 udata i vdata i sum1 udata i 1 vdata i 1 sum0 udata i 2 vdata i 2 sum1 udata i 3 vdata i 3 Finish off any remaining elements for i length i sum0 sum0 udata i vdata i dest sum0 sum1 15213 Recitation C 7 Shimin Chen Solution 5 13 For each element we must perform two loads with a unit that can only load one value per clock cycle We must also perform one floating point multiplication with a unit that can only perform one multiplication every two clock cycles Both of these factors limit the CPE to 2 15213 Recitation C 8 Shimin Chen Summary of Matrix Multiplication ijk jik 2 loads 0 stores misses iter 1 25 for i 0 i n i kij ikj 2 loads 1 store misses iter 0 5 for k 0 k n k for j 0 j n j jki kji 2 loads 1 store misses iter 2 0 for j 0 j n j for i 0 i n i for k 0 k n k sum 0 0 r a i k r b k j for k 0 k n k for j 0 j n j for i 0 i n i sum a i k b k j c i j r b k j c i j sum c i j a i k r 15213 Recitation C 9 Shimin Chen Improving Temporal Locality by Blocking Example Blocked matrix multiplication block in this context does not mean cache block Instead it mean a sub block within the matrix Example N 8 sub block size 4 A11 A12 A21 A22 B11 B12 X B21 B22 C11 C12 C21 C22 Key idea Sub blocks i e Axy can be treated just like scalars C11 A11B11 A12B21 C12 A11B12 A12B22 C21 A21B11 A22B21 C22 A21B12 A22B22 15213 Recitation C 10 Shimin Chen Blocked Matrix Multiply bijk for jj 0 jj n jj bsize for i 0 i n i for j jj j min jj bsize n j c i j 0 0 for kk 0 kk n kk bsize for i 0 i n i for j jj j min jj bsize n j sum 0 0 for k kk k min kk bsize n k sum a i k b k j c i j sum Provides temporal locality as block is reused multiple times Constant cache performance 15213 Recitation C 11 Shimin Chen Blocked Matrix Multiply Analysis Innermost loop pair multiplies a 1 X bsize sliver of A by a bsize X bsize block of B and accumulates into 1 X bsize sliver of C Loop over i steps through n row slivers of A C using same B for i 0 i n i for j jj j min jj bsize n j sum 0 0 for k kk k min kk bsize n k sum a i k b k j c i j sum kk jj jj kk i row sliver accessed bsize times 15213 Recitation C A i B block reused n times in succession 12 C Update successive elements of sliver Shimin Chen Pentium Blocked Matrix Multiply Performance Blocking bijk and bikj improves performance by a factor of two over unblocked versions ijk and jik relatively insensitive to array size 60 Cycles iteration 50 kji jki kij ikj jik ijk bijk bsize 25 bikj bsize 25 40 30 20 10 75 10 0 12 5 15 0 17 5 20 0 22 5 25 0 27 5 30 0 32 5 35 0 37 5 40 0 50 25 0 15213 Recitation C Array size n 13 Shimin Chen Summary All systems favor cache friendly code Can get most of the advantage with generic optimizations Keep working set reasonably small temporal locality Use small strides spatial locality Getting absolute optimum performance is very platform specific Cache sizes Line sizes Associativities etc 15213 Recitation C 14 Shimin Chen
View Full Document
Unlocking...