Carnegie Mellon Introduction to Computer Systems 15 213 18 243 spring 2009 13th Lecture Feb 26th Instructors Gregory Kesden and Markus P schel Carnegie Mellon First Exam This lecture 90 Carnegie Mellon Research Opportunities www spiral net Research Interdisciplinary High performance Mathematical libraries Automation source code generation Full time summer research or honor s project Excellent junior or exceptional sophomore Contact pueschel ece Carnegie Mellon Last Time Memory hierarchy Here Core 2 Duo 4 MB 4 GB L2 unified cache Main Memory 500 GB L1 I cache 32 KB CPU Reg Throughput 16 B cycle Latency 3 cycles L1 D cache 8 B cycle 14 cycles 2 B cycle 100 cycles 1 B 30 cycles millions Disk Carnegie Mellon Last Time Locality Temporal locality Recently referenced items are likely to be referenced again in the near future block Spatial locality Items with nearby addresses tend to be referenced close together in time block Carnegie Mellon Last Time E 2e lines per set Caches Address of word t bits S 2s sets tag s bits b bits set block index offset data begins at this offset v tag 0 1 2 B 1 valid bit B 2b bytes per cache block the data Carnegie Mellon Strided Access Question E 2e lines per set Address of word t bits S 2s sets tag s bits b bits set block index offset What happens if arrays are accessed in two power strides Example on the next slide Carnegie Mellon The Strided Access Problem Blackboard Example L1 cache Core 2 Duo 32 KB 8 way associative 64 byte cache block size What is S E B Answer B 26 E 23 S 26 Consider an array of ints accessed at stride 2i i 0 What is the smallest i such that only one set is used Answer i 10 What happens if the stride is 29 Answer two sets are used Source of two power strides Example Column access of 2 D arrays images Carnegie Mellon Today Program optimization Cache optimizations Linking Carnegie Mellon Optimizations for the Memory Hierarchy Write code that has locality Spatial access data contiguously Temporal make sure access to the same data is not too far apart in time How to achieve Proper choice of algorithm Loop transformations Cache versus register level optimization In both cases locality desirable Register space much smaller requires scalar replacement to exploit temporal locality Register level optimizations include exhibiting instruction level parallelism conflicts with locality Carnegie Mellon Example Matrix Multiplication c double calloc sizeof double n n Multiply n x n matrices a and b void mmm double a double b double c int n int i j k for i 0 i n i for j 0 j n j for k 0 k n k c i n j a i n k b k n j j c a i b Carnegie Mellon Cache Miss Analysis Assume Matrix elements are doubles Cache block 8 doubles 64 B as in Core 2 Duo Cache size C n much smaller than n n First iteration n 8 n 9n 8 misses Afterwards in cache schematic 8 wide Carnegie Mellon Cache Miss Analysis Assume Matrix elements are doubles Cache block 8 doubles Cache size C n much smaller than n n Second iteration Again n 8 n 9n 8 misses 8 wide Total misses 9n 8 n2 9 8 n3 Carnegie Mellon Blocked Matrix Multiplication c double calloc sizeof double n n Multiply n x n matrices a and b void mmm double a double b double c int n int i j k for i 0 i n i B for j 0 j n j B for k 0 k n k B B x B mini matrix multiplications for i1 i i1 i B i for j1 j j1 j B j for k1 k k1 k B k c i1 n j1 a i1 n k1 b k1 n j1 j1 c a i1 b c Block size B x B Carnegie Mellon Cache Miss Analysis Assume Cache block 8 doubles Cache size C n much smaller than n Three blocks fit into cache 3B2 C n B blocks First block iteration B2 8 misses for each block 2n B B2 8 nB 4 omitting matrix c Block size B x B Afterwards in cache schematic Carnegie Mellon Cache Miss Analysis Assume Cache block 8 doubles Cache size C n much smaller than n Three blocks fit into cache 3B2 C Same as first iteration 2n B B2 8 nB 4 n B blocks Second block iteration Total misses nB 4 n B 2 n3 4B Block size B x B Carnegie Mellon Summary No blocking 9 8 n3 Blocking 1 4B n3 Suggest largest possible block size B but limit 3B2 C can possibly be relaxed a bit but there is a limit for B Reason for dramatic difference Matrix multiplication has inherent temporal locality Input data 3n2 computation 2n3 Every array elements used O n times But program has to be written properly Carnegie Mellon Today Program optimization Cache optimizations Linking Carnegie Mellon Example C Program main c swap c int buf 2 1 2 extern int buf int main swap return 0 static int bufp0 buf 0 static int bufp1 void swap int temp bufp1 buf 1 temp bufp0 bufp0 bufp1 bufp1 temp Carnegie Mellon Static Linking Programs are translated and linked using a compiler driver unix gcc O2 g o p main c swap c unix p main c swap c Translators cpp cc1 as Source files Translators cpp cc1 as main o swap o Separately compiled relocatable object files Linker ld p Fully linked executable object file contains code and data for all functions defined in main c and swap c Carnegie Mellon Why Linkers Modularity Program can be written as a collection of smaller source files rather than one monolithic mass Can build libraries of common functions more on this later e g Math library standard C library Carnegie Mellon Why Linkers Efficiency Time Separate Compilation Change one source file compile and then relink No need to recompile other source files Space Libraries Common functions can be aggregated into a single file Yet executable files and running memory images contain only code for the functions they actually use Carnegie Mellon What Do Linkers Do Step 1 Symbol resolution Programs define and reference symbols variables and functions void swap swap int xp x define symbol swap reference symbol swap define xp reference x Symbol definitions are stored by compiler in symbol table Symbol table is an array of structs Each entry includes name type size and location of symbol Linker associates each symbol reference with exactly one symbol definition Carnegie Mellon What Do Linkers Do cont Step 2 Relocation Merges separate code and data sections into single sections Relocates symbols from their relative locations in the o files to their final absolute memory locations in the executable Updates all references to these symbols to reflect their new positions Carnegie Mellon Three Kinds of Object Files Modules Relocatable object file o file Contains code and data in a form that can be combined with other relocatable object …
View Full Document
Unlocking...