15-745IntroductionSeth Copen [email protected]@cs.cmu.EduCMUBased in part on slides by lecture 1, 15-745 © 2002-9 Seth Copen Goldstein 1Based in part on slides by Todd Mowry and Michael VossIntroduction• Why study compilers?Ad i i t i•Administriva• Structure of a Compilerp• Optimization ExampleReference: Muchnick 1.3-1.5lecture 1, 15-745© 2002-9 Seth Copen Goldstein2Moore’s Lawlecture 1, 15-745© 2002-9 Seth Copen Goldstein3Moore’s LawHappyB’dHappyHappyB’DImagine: Computers thatB’dayppyB‘DayB’Daygp•Smallenough to fit inside cells hh b d blImagining it is hard enough •Cheapenough to be disposable•Denseenough to embed a supercomputerImagining it is hard enough, achieving it requires a rethink of h l hDenseenough to embed a supercomputer•Smartenough to assemble themselvesthe entire tool chain.Computers from atomic scale componentslecture 1, 15-745© 2002-9 Seth Copen Goldstein4What is Behind Moore’s Law?• A lot of hard work!•Two most important tools:•Two most important tools:– Parallelism•Bitlevel•Bit-level• Pipeline•Function unitFunction unit• Multi-core– Localityylecture 1, 15-745© 2002-9 Seth Copen Goldstein5Performance: Ops/SecPerformance Ops/Sec1000.00lecture 1, 15-745© 2002-9 Seth Copen Goldstein6HorowitzPerformance: Ops/Clk * Clks/SecPerformance Ops/Clk Clks/Sec1000.00lecture 1, 15-745© 2002-9 Seth Copen Goldstein7HorowitzSpecInt/Mhzlecture 1, 15-745© 2002-9 Seth Copen Goldstein8HorowitzAnother View of Moore’s Law1.E+031E+021.E+02SRAMDRAMCPU l1.E+01CPU cyclelecture 1, 15-745© 2002-9 Seth Copen Goldstein91.E+001980 1985 1990 1995 2000The Computer SystemProcessorProcessorhRegMemory-I/O busCacheMemory-I/O busMemoryI/OcontrollerI/OcontrollerI/OcontrollerDiskDiskMemorycontro rcontrollercontro rDisplay Networklecture 1, 15-745© 2002-9 Seth Copen Goldstein10DDiskThe Memory Hierarchycache virtual memoryCPUCaMemorydisk8 B 32 B 8 KBregsregscheyRegister CacheMemoryDisk Memorysize:speed:$/Mbyte:200 B3 nsRegister CacheMemoryDisk Memory32 KB/4MB6 ns$100/MB128 MB60 ns$ 30/MB20 GB8 ms$0 005/MB$/Mbyte:block size: 8 B$100/MB32 B$.30/MB8 KB$0.005/MBlarger, slower, cheaperlecture 1, 15-745© 2002-9 Seth Copen Goldstein11Compiler Writer’s Job• Improve locality•Increase •Increase parallelismTl t ltn•Tolerate latency• Reduce powerlecture 1, 15-745© 2002-9 Seth Copen Goldstein12Why study compilersTh ll i•They are really amazing• Combines theory & practiceyp– CS is about abstraction• Primary abstraction: programming language• Compiler lowers PL to ISA (or further!)– Compiler is a big system• Crucial for performance–especially for modern processorspy p– practically part of the architecture•I bet: Everyone will write a compilerlecture 1, 15-745© 2002-9 Seth Copen Goldstein13I bet: Everyone will write a compilerWhy study compilersTh ll i•They are really amazing• Combines theory & practiceyp– CS is about abstraction• Primary abstraction: programming language• Compiler lowers PL to ISA (or further!)– Compiler is a big system• Crucial for performance–especially for modern processorspy p– practically part of the architecture•I bet: Everyonewill write a compilerlecture 1, 15-745© 2002-9 Seth Copen Goldstein14I bet: Everyonewill write a compilerWhat this course is aboutHigh-level Low-level Front End Optimizerlanguage(E.g., C)language(E.g., x86)CodeGeneratorSource code IR(E.g., SSA)IR ASM(E g , )• Theory and practice of modern optimizing compilers•No lexing or parsing•No lexing or parsing• Focus on IR, back-end, optimizationsIl f d’ (d ’) illecture 1, 15-745© 2002-9 Seth Copen Goldstein15•Internals of today’s (and tomorrow’s) compilers• Working with a real compilerPrerequisites• 211 & 213 or the equivalent•Parts of 411 or the equivalent•Parts of 411 or the equivalent– Basic compiler data structuresFr m s c llin c nv nti ns d fus –Frames, calling conventions, def-use chains, etc.Don’t really care about frontend–Don t really care about front-end• Proficient in C/C++ programming• Basic understanding of architecturelecture 1, 15-745© 2002-9 Seth Copen Goldstein16My Expectations• You have the prerequisites–If not come see me asapIf not come see me asap• 3 assignments + a projectCl ti i ti•Class participation– THIS IS A MUST!– Read text/papers before class– Attendance is essentially mandatorylecture 1, 15-745© 2002-9 Seth Copen Goldstein17Grading• Class participation ~20%–Throughout the semesterThroughout the semester– During paper presentations–Project presentations–Project presentations• assignments ~20%Pj40%•Project ~40%• Midterm ~20%lecture 1, 15-745© 2002-9 Seth Copen Goldstein18Assignments• Intro to LLVM/Liveness•Dependence analysis•Dependence analysis• Locality/Parallel transformations• All labs and the final project will be pjdone in a state-of-the-art research compiler: LLVMplecture 1, 15-745© 2002-9 Seth Copen Goldstein19The Text• No assigned text. Its really up to you.• Muchnick, Advanced Compiler Design & Impl., 1997pgp• Allen, et.al., Optimizing Compilers for Modern Archs, 2001• Copper, et.al., Engineering a compiler, 2003•Aho et al Compilers: 2006Aho, et.al., Compilers: …, 2006•Papers will be assignedlecture 1, 15-745© 2002-9 Seth Copen Goldstein20pgBefore we get too bored• More admin at the end, but first …• What exactly is an optimizing compiler?A i ii il f –An optimizing compiler transforms a program into an equivalent, but “better” form.Wh t i i l t?–What is equivalent?– What is better?lecture 1, 15-745© 2002-9 Seth Copen Goldstein21Full Employment Theorem• No such thing as “The optimizing compiler”–Why not?Why not?•There is always a better optimizing compiler but compiler, but …– Compiler must preserve correctnessO i X h X i–On average improve X, where X is:•Performance•Power•Power•…–Finish in your lifetimelecture 1, 15-745© 2002-9 Seth Copen Goldstein22Finish in your lifetimeHow might performance be improved?execution time = cycles per instructionΣ instructions• Reduce the number of instructions• Replace “expensive” instructs with “cheap” ones• Reduce memory costy– Improve locality– Reduce # of memory operationslecture 1, 15-745© 2002-9 Seth Copen Goldstein23• Increase parallelismIngredients to a compiler optId if
View Full Document
Unlocking...