15 213 Riding the Technology Curve Dec 1 1998 Topics Moore s Law Are exponential problems intractable Impact on real world problems The verification challenge Impact of Technology It s the Technology Stupid Computer science has ridden the wave Things Aren t Over Yet Technology will continue to progress along current growth curves For at least 10 more years Difficult technical challenges in doing so Even Technologists Can t Beat Laws of Physics 2 Moore s Law Gordon Moore Co founded Intel in early 70 s Observed in 1972 that number of transistors chip doubled every 1 5 years Really a trend rather than a law Exponential Growth Trends DRAM technology Capacity 4X every 3 years Speed 3X in 10 years Magnetic disk technology Capacity 4X every 3 years Microprocessor Performance SPEC performance 2X every 1 5 years Software complexity Typical program sizes growing 1 5 2X per year 3 Semiconductor Industry Forecast Semiconductor Industry Association 1992 Technology Workshop Year Feature size DRAM cap 1992 0 5 1995 0 35 1998 0 25 2001 0 18 2004 0 12 2007 0 10 16M 64M 256M 1G 4G 16G Gates chip 300K 800K 2M 5M 10M 20M Chip cm2 I Os 2 5 4 0 6 0 8 0 10 0 12 5 500 750 1500 2000 3500 5000 off chip MHz 60 100 175 250 350 500 on chip MHz 120 200 350 500 700 1000 4 Impact of Moore s Law Moore s Law Performance factors of systems built with integrated circuit technology follow exponential curve E g computer speed memory capacities double every 1 5 years Implications Computers 10 years from now will run 100 X faster Problems that appear intractable today will be straightforward Must not limit future planning with today s technology Example Application Domains Speech recognition Will be routinely done with handheld devices Breaking secret codes Need to use large enough encryption keys 5 Solving Hard Problems Conventional Wisdom Exponential problems are intractable Operation Assume problem of size n requires 2n steps Each step takes k years on a Y2K computer Y2K Computer Performance 6 Start computation Jan 1 2000 Keep running same machine until problem solved Would take k 2n years Solving with a Y2K Computer Y2K Computer 1 E 31 1 E 29 1 E 27 1 E 25 Time per Operation 1 E 23 1 E 21 1 E 19 CPU Years 1 E 17 second 1 E 15 minute 1 E 13 hour 1 E 11 day 1 E 09 week year 1 E 07 1 E 05 1 E 03 1 E 01 1 E 01 1 E 03 1 E 05 10 20 30 40 50 60 Problem Size n 7 70 80 90 100 Moore s Law Computer Operation Start computing on Jan 1 2000 Keep upgrading machine being used In year y would have performance 1 587y relative to Y2K machine Performance After y years of operation would have performed as much computation as Y2K machine would do in time Examples y 1 y 2 y 5 y 10 y 100 8 1 27 3 29 20 218 2 53 X 1020 y 1 587 x dx 0 y 2 16 1 587 1 Solving Hard Problems Solution Time Problem of size n Running y years on Moore s Law computer y 2 16 ln 1 0 462 k 2n For large values of n y 1 5 n 2 16 ln k 1 67 O n Complexity 9 Linear in problem size Solving with a Moore s Law Computer Moore s Law Computer 160 140 Time per Operation 120 CPU Years 100 second minute 80 hour day week 60 year 40 20 0 10 20 30 40 50 60 Problem size n 10 70 80 90 100 Effect of Step Complexity Observe Step complexity k adds only additive factor of 2 16 ln k to running time Example For n 100 k 1 second 111 1 minute 120 1 hour 129 1 day 136 1 week 140 1 year 148 Explanation 11 y Final years of computation will be on exponentially faster machines Implications of Moore s Law P NP Effectively Problems of exponential complexity can be solved in linear time Caveat Cannot hold forever Fundamental Limit Argument due to Ed Fredkin Claim that ultimate limit to growth in memory capacity is cubic Cannot build storage device with less than one electron Assume consume all available material to build memories Would soon exhaust planetary resources Cannot travel into outer space faster than speed of light 12 Total amount of material available at time t is t3 This limit will be hit in 400 years How to Be a Visionary Pick a Really Hard Problem Sequencing of human genome Accurate weather prediction Flying helicopter autonomously Make Proclamations Wait In 20 years problem X will be solved But make sure everyone credits you with the vision Maybe make a few contributions to technology Amass Glory Turing Award Citation He She had the foresight to see that this problem could be solved 13 Truly Hard Problems Those That Get Harder over Time Track Moore s law growth How do I make sure my chip will operate correctly How do I make sure my programs are correct How do I manufacture state of the art chips Highlight 14 Research at CMU on formal verification of hardware Motivation for Formal Verification Intel s Challenge ca 1992 Design a high performance state of the art microprocessor to succeed the 486 Maintain compatibility to 20 year old x86 product line Provide new levels of performance on floating point Floating Point Divider Use radix 4 SRT algorithm developed in 1960 s First time ever used by Intel Validation Run lots of simulation tests Make sure it runs set of Windows applications Manufacturing Environment 15 Will produce millions of chips Cannot make any changes after manufacture The Pentium Fiasco Events Prof Thomas Nicely Lynchburg College VA Looking at properties of twin primes Incorrect reciprocals for 824633702441 and 824633702443 Single precision accuracy 4 X 10 9 Contacted others on Oct 30 94 Spreading of Information on Internet news group comp sys intel Terje Mathisen of Norway posts Nicely s findings on Nov 3 Andreas Kaiser of Germany finds 23 bad reciprocals Nov 10 Tim Coe Vitesse Semiconductor Nov 16 Created good enough software model of flawed divide algorithm Discovered nonreciprocal cases with errror up to 6 X 10 5 Later showed 1738 mantissa pairs with less than single precision accuracy out of 7 4 X 1013 single precision mantissa pairs 16 Resolution Free Replacement Policy Dec 20 No need to argue need Complex logistics Many different versions Actual replacement easy Financial Impact 17 Intel charged 475 million to it s 4Q94 earnings Still was 2nd most profitable year ever Few companies could survive such an expensive mistake In the end generated lots of valuable PR for Intel Is There a Better Way Provide Mechanism to Patch Functionality Make chips more malleable so that can update as would software Intel has started to incorporate such mechanisms Future technologies such as field programmable logic could help Seth Goldstein Make Sure Hardware is Really Correct 18 Formal
View Full Document
Unlocking...