CPSC 330 Links

Chapter 1 Links

• Range of computing
  • Top 500 supercomputers (according to Linpack)
    • Nov. 2008 - Clemson's Palmetto Cluster is number 61
    • Nov. 2011 - Clemson's Palmetto Cluster is number 128
    • (click LISTS then complete list)
    • Palmetto cluster
      • 1,541 nodes, 8 cores per node, 85 Tflops on Linpack benchmark
      • Myrinet interconnect
      • 2008 Dell press release and video on Palmetto cluster
      • 2008 cluster presentation by Jim Pepin
      • for more info, see CITI web site
  • Dell servers
  • Computers on wheels ("... as many as 50 microprocessors")
  • computerized running shoe
  • self-tuning Gibson robot guitar
  • 32-bit ARM processor in a computer mouse
  • pitch-speed-sensing digital baseball
  • implantable eye pressure monitor for glaucoma patients

  • but read Christopher Mims, "Do We Really Need an Android-Powered Fridge?", Technology Review, August 2011

• Markets
  • server -- provide high availability, good scalability, and maximum throughput (e.g., transactions per minute, web pages served per second, or file transfer measures)
  • desktop (personal computer and workstation) -- price/performance
  • embedded -- minimize price, memory size, and power
  • others
    • supercomputer -- maximize performance (much of this market now is based upon massive collections of commodity microprocessors with special interconnection networks)
    • mainframe -- large databases (this market is fading into the server market; new IBM mainframes use microprocessors)
    • laptops, netbooks -- track desktop market but with lower power consumption
    • game consoles -- track top performance of embedded market
    • handheld devices and consumer electronics -- subset of embedded market
  • certain instruction sets have gained hold in certain markets
    • PowerPC and x86 in supercomputer market
    • SPARC, x86, and others in server market
    • x86 in desktop market
    • ARM, MIPS, and M68K in embedded market

• History
  • ENIAC - the first electronic digital computer (1943-1946)
    • "programmed" by plugboards and portable function tables
    • description
    • programming a square root

  • John von Neumann (1903-1957)
    • photo
    • biography
    • another biography

  • Burks, Goldstine, and von Neumann, "Preliminary discussion of the logical design of an electronic computing instrument," 1946 (though credit for the idea of the stored program computer should be shared with J. Presper Eckert and John Mauchly)

  • von Neumann machine characteristics
    • random-access, one-dimensional memory (vs. sequential memories)
    • stored program, no distinction between instructions and data (vs. "Harvard architecture" with separate instruction and data memories)
    • binary, parallel by word, two's complement (vs. decimal, serial-by-digit, signed magnitude)
    • instruction fetch/execute cycle, branch by explicit change of PC (vs. following a link address from one instruction to the next)
    • three-register arithmetic -- ACC, MQ, MBR

  • von Neumann's ideas were implemented in Princeton IAS machine (1946-1952)
    • JvN standing in front of IAS machine
    • another view of IAS machine
    • word size of 40 bits, binary, two's complement
    • 20-bit, 1-address instruction format (8-bit opcode, 12-bit address)
  • multiple derivative machines (see list at wikipedia)

• comparison table

  	ENIAC	IBM 704	IBM S/360 M50	VAX 11-780	Sun SPARCStation IPC	Dell 4600
  date	1946	1955	1965	1978	1990	2003
  addition time	200 µsec	24 µsec	4 µsec	400 nsec	40 nsec	208 psec
  memory cycle time		12 µsec	2 µsec	200 nsec	80 or 100 nsec	3 nsec
  standard memory size		168 KB	64 KB	128 KB	8 MB (48 MB max)	256 MB
  rental		$48,000/mo.	$32,000/mo.	$6,000/mo.
  purchase	$500,000	$1,390,000	$409,000	$128,000	$9,995 (w/ color monitor)	$800
  constant 2010 dollars	$5.6M	$11.3M	$2.8M	$428,000	$16,670	$950
  CPU technology	17,500 vacuum tubes	5,000 vacuum tubes in CPU	~ 25 K SLT circuits on 72 circuit boards (2x1 and 1x3 diodes, one transistor, and three printed resistors on AOI module; medium-speed gate was 30 nsec)	1500 Schottky TTL chips on 20 circuit boards (1-4 gates or circuits per chip; 3-nsec gates)	approx. 1 M transistors in LSI S1C0010 IU (separate FPU)	55 M transistors in Pentium 4

• Microprocessor history timeline
• Intel microprocessor quick reference guide

• Low-level info
  • Transistors
    • Animation of a transistor
    • Junction and FET transistors
    • tri-gate transistor picture
  • How chips are made
  • Alex Paikin, CMOS inverter
  • CMOS fabrication process
  • Logic gates in CMOS
  • Pentium die photo with overlay (3.1 million transistors)
  • Metal layers on a chip
  • 2 billion transistor Itanium (2008); see also this picture of the Itanium chip
  • Transistor aging article at IEEE Spectrum, April 2011
    • oxide layer effects
      • hot carrier degradation/effects/injection (HCD/HCE/HCI) - charge carriers get trapped in the insulating oxide layer and will slow the transistor switching speed
      • negative/positive bias temperature instability (NBTI/PBTI) - a transient effect that wll also slow the switching speed
      • oxide breakdown - accumulation of electrically-active defects in the oxide layer will eventually cause a short-circuit
    • electromigration of metal layers connecting transistors can lead to a breakdown and an open circuit

• Increasing performance
  • Moore's Law -- number of transistors increasing
  • CPU speed vs. memory speed -- CPU performance had been improving at faster rate
  • Memory latencies

  But recently ...

  • recent CPU clock frequency reductions (Bob Warfield) (but note 5.0 GHz IBM Power 6)
  • Microprocessor power density (Tensilica)
  • Energy per instruction (Intel) (see also the paper Energy per Instruction Trends in Intel Microprocessors [pdf])

  • Gordon Moore in 2007 - end of Moore's Law in 10-15 years?

  • with Moore's Law continuing (so far) yet clock frequency and IPC leveling off, the industry is turning to multicore - see this figure

• IEC standard prefixes (GB vs. GiB)

For fun - media representations of computing power

• relay computers
  • Robbie the Robot from the 1956 film Forbidden Planet. Note the blinking lights and motion of various part to show that he is "on". Especially note the lights and the clacking of the relays as he "thinks".

  • Listen to the relay clicks in the vintage Harwell relay computer (louder clicks are the paper tape reader) and in a recent hobbyist's relay computer.

• 1950s computers
  • Blinking lights, spinning tape drives, and electronic noises in the 1957 film Desk Set.

  • The IBM AN/FSQ-7 (SAGE) computer used as a movie and TV prop

• Starring the Computer - an index of various computers appearing in movies and TV

Performance Links

• until recently, transistor size shrinks led to clock rate improvements (approx. linearly)
• architectural improvements also helped improve performance -- such as caches, pipelining, superscalar, VLIW/EPIC, multithreading, etc. (e.g., see Birnbaum [pdf])
• microprocessors now use multicore as path to improved performance
• microprocessors now dominate all computer markets due to high level of integration and cost advantages of mass production

• performance typically tracks clock frequency within a given processor family, but selected SPEC scores can show an inverse relationship of performance to clock frequency when comparing across processor families
• AMD/Intel marketing example
  • AMD was the first to reach 1 GHz and made sure everyone knew...
  • but Intel was the first to reach 2 GHz
  • AMD marketing response: Intel is "devaluing the meaning of megahertz"
• Apple marketing example - megahetz myth (this is an example of carefully-selected "benchmarketing"; see other Apple Altivec results from 2002 and also John Kheit, "The Real Megahertz Myth: Is Apple The Real Slim Shady?" May 9, 2003)

• performance
  • measures
    • response time (latency) -- time between start and completion
    • throughput (bandwidth) -- rate -- work done per unit time
    • speedup -- B is n times faster than A == exec_time_A/exec_time_B == rate_B/rate_A
    • other important measures
      • power (impacts battery life, cooling, packaging)
      • RAS (reliability, availability, and serviceability)
      • scalability (ability to scale up processors, memories, and I/O)
      • total cost of ownership (TCO)
        • hardware purchase costs
        • software purchase/licensing costs
        • installation costs (e.g., floor space including raised flooring if required for large servers, electrical connections, network connections)
        • software conversion costs and staff retraining if required
        • on-going maintenance/support costs
        • on-going electricity and air conditioning costs
        • on-going system administration costs
        • on-going staff training
        • downtime costs for staff and lost user productivity (depends on reliability/availability)
        • replacement/upgrade costs (depends on useful lifetime and scalability)
    • quest for single marketing number usually leads to problems!

  • time is the measure of computer performance
    • elapsed time = program execution + I/O + wait -- important to user
    • execution time = user time + system time (but OS self measurement may be inaccurate)
    • CPU performance = user time on unloaded system -- important to architect

  • performance is the result of executing a workload on a configuration
    • workload = program + input
    • configuration = CPU + cache + memory + I/O + OS + compiler + optimizations
    • compiler optimizations can make a huge difference!
      e.g., vector add (length 100) on a SPARC using cc (ca. 1996)
      • no optimization: 2210 total instructions executed, 802 load/stores
      • -O2 optimization: 908 total instructions executed, 300 load/stores
      • -O4 optimization: 442 total instructions executed, 201 load/stores
    • BUT workload and configuration (including compiler optimization flags) often are not fully reported and results cannot be duplicated

  • compilers with targeted optimizations
    • for specific programs - see Martin Veitch, "Sun accused of cheating Java benchmarks," ZDNet, Nov. 1997
    • for specific processors - see Agner Fog, "Will Intel be forced to remove the 'cripple AMD' function from their compiler?", blog post, Dec. 2009

• benchmarks
  • real programs -- gcc, Photoshop, SPEC programs
  • kernels -- key, small pieces of real programs
    • Linpack (1985) -- a collection of Fortran program segments used in solving systems of linear equations, including Gaussian elimination, dot products, and matrix multiplication. Linpack is still used as the benchmark for the Top 500 Supercomputers list.
    • Livermore loops (1986) -- a collection of 24 innermost loops found in scientific applications run at LLNL
  • synthetic (artificial) programs -- created to match execution profiles
    • Whetstone (1976) -- designed to simulate arithmetic-intensive scientific programs.
    • Dhrystone (1984) -- designed to simulate systems programming applications. MIPS ratings were often calculated using 1 MIPS = 1,757 Dhrystones/sec (which was the Dhrystone rate on a VAX-11/780).
      • See Alan Weiss, "Dhrystone Benchmark: History, Analysis, 'Scores', and Recommendations,", 2002 [pdf]
      • See also the example of IBM RS/6000 performance reported in a March 26, 1990, InfoWorld advertisement (pp. 37-39). Note that, unless this is a typo, IBM used the old 1984 version 1.1 of Dhrystone instead of the 1988 version 2.1, which had been designed to defeat common compiler tricks known to raise v1.1 scores.
  • SPEC -- Systems Performance Evaluation Cooperative, started in 1988 to provide benchmarks for workstations
    • SPEC89 was a suite of ten real programs that ran for 5-10 minutes each; SPECmark was the geometric mean
    • SPEC92 separated into SPECint and SPECfp
    • SPEC95 introduced baseline measures to reduce compiler optimization flag dependencies and unsafe optimizations
    • SPEC CPU2000
    • SPEC CPU2006
  • TPC -- Transaction Processing Council, started in 1988 to provide benchmarks for transaction processing
    • TPC-C - on-line transaction processing (credit-debit, like a bank)
    • TPC-H - decision support ad hoc queries
    • TPC-R - decision support business reporting
    • TPC-W - web e-commerce
  • EEMBC -- Embedded Microprocessor Benchmark Consortium, started in 1997 to provide benchmarks for embedded processors
    • automotive/industrial (16 microbenchmarks, e.g., bit manipulation)
    • consumer (5 microbenchmarks, e.g., compress and uncompress JPEG)
    • networking (5 microbenchmarks, e.g., packet routing)
    • office automation (3 microbenchmarks, e.g., text processing)
    • telecommunications (16 microbenchmarks, e.g., FFT)
  • Graph 500 benchmark (2010) -- intended to complement the Top 500 list with results using graph algorithms

  • "Benchmarks are $%#&@!! - Secrets and solutions from a reformed benchmarketer," Dan Olds interview of Henry Newman, December 2011

• comparing performance
  • total execution time (implies equal mix in workload)
  • arithmetic average of execution time
  • harmonic mean of rates (rate = 1/execution time)
  • weighted execution time (weighted arithmetic mean)
  • normalized execution time or speedup (normalize relative to reference machine and take average)
    • arithmetic mean sensitive to reference machine choice
    • geometric mean consistent but cannot predict execution time (SPEC and EEMBC use geometric mean)

      comparison of execution times (e.g., in seconds) on three machines

      	machine X	machine Y	machine Z
      program 1	20	10	40
      program 2	40	80	20
      total execution time	60	90	60
      average execution time	30	45	30

      normalized speedups and means (relative to machine X)

      	machine X	machine Y	machine Z
      program 1	1	2	0.5
      program 2	1	0.5	2
      arithmetic mean	1	1.25	1.25
      geometric mean	1	1	1

      ... do machines Y and Z have the same performance?

      normalized speedups and means (relative to machine Y)

      	machine X	machine Y	machine Z
      program 1	0.5	1	0.25
      program 2	2	1	4
      arithmetic mean	1.25	1	2.125
      geometric mean	1	1	1

      ... or does machine Z have more than twice the performance of machine Y?

      same comparisons done using rates (1/execution_time)

      	machine X	machine Y	machine Z
      program 1	0.05	0.1	0.025
      program 2	0.025	0.0125	0.05
      arithmetic mean	0.0375	0.05625	0.0375
      harmonic mean	0.0333	0.0222	0.0333

      ... is machine Y the fastest (according to the arithmetic mean) or the slowest (according to the harmonic mean)?
      ... (at rate of 0.05625 programs/second, an average program would take 17.8 seconds)
      ... (at rate of 0.0222 programs/second, an average program would take 45 seconds)

• CPU performance (user execution time and components that explain it)
  • basic CPU time = IC * CPI / clock rate
    = IC * CPI * CCT
    • instruction count -- depends on algorithm, ISA, and compiler
    • CPI (cycles per instruction) -- depends on ISA, compiler, and processor organization
    • clock rate -- depends on processor organization and hardware technology
  • CPU time = SUM over i of ( CPI[i] * inst. count[i] ) * clock cycle time
  • RISC vs. CISC: reduced CPI is better than smaller instruction count ( see figure E.9 on page E-19 [pdf])

CPU performance

        CPU_time =   IC    *   CPI    *   CCT

                               cycles     secs
                 = i insts * j ------ * k -----  = ijk secs 
                                inst      cycle


                      IC  *  CPI
        CPU_time =  ---------------
                    Clock_Frequency


                                                          IC_i
        CPU_time = sum ( IC * CPI  ) * CCT  =  IC * sum ( ---- * CPI  ) * CCT
                           i     i                         IC       i
                    i                                i

Consider the following instruction mix

                         IC_i / IC          CPI_i
        operation        frequency        cycle count        weighted CPI_i
        ---------        ---------        -----------        --------------
        ALU op              50%                1                   _____
        Loads               20%                2                   _____
        Stores              10%                3                   _____
        Branches            20%                4                   _____


a) What is the average CPI?


	CPI = (.5*1) + (.2*2) + (.1*3) + (.2*4) = .5 + .4 + .3 + .8 = 2.0


b) If branch cycles are reduced to 2, do you have enough information to
   determine how much faster the modified processor will be than the
   original processor?


                    CPU_time_old     IC * CPI_old * CCT     CPI_old
        speedup  =  ------------  =  ------------------  =  -------
                    CPU_time_new     IC * CPI_new * CCT     CPI_new

        CPI_old = 2.0

	CPI_new = (.5*1) + (.2*2) + (.1*3) + (.2*2) = .5 + .4 + .3 + .4 = 1.6

	speedup = 2.0 / 1.6 = 1.25