CPSC 330 Links

Chapter 1 Links

• Range of computing
  • Top 500 supercomputers (according to Linpack)
    • Nov. 2008 - Clemson's Palmetto Cluster is number 60
    • June 2009 - Clemson's Palmetto Cluster is number 89
    • (click LISTS then complete list)
  • Dell servers
  • Computers on wheels ("... as many as 50 microprocessors")
  • computerized running shoe
  • self-tuning Gibson robot guitar

• 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 some also assign credit for the idea of the stored program computer to 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 2	Dell 4600
  date	1946	1955	1965	1978	1992	2003
  addition time	200 usec	24 usec	4 usec	400 nsec	25 nsec	208 psec
  memory cycle time		12 usec	2 usec	200 nsec	80 nsec	3 nsec
  standard memory size		168 KB	64 KB	128 KB	128 MB	256 MB
  rental		$48,000/mo.	$32,000/mo.	$6,000/mo.
  purchase	$500,000	$1,390,000	$409,000	$128,000	$15,000	$800
  constant 2003 dollars	$4.7M	$9.5M	$2.4M	$360,000	$19,600	$800
  CPU technology	17,500 vacuum tubes	5,000 vacuum tubes in CPU	~ 25 K SLT circuits on 72 circuit boards	1500 TTL chips on 20 circuit boards	1.8 M transistors in CY7C601 IU	55 M transistors in Pentium 4

• Microprocessor history timeline
• Intel microprocessor "Hall of Fame" (8/17/09 - broken link)
• Intel microprocessor quick reference guide

• Low-level info
  • Transistors
    • Animation of a transistor
    • How transistors work (You Tube video)
    • Junction and FET transistors
  • 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

• Increasing performance
  • Moore's Law -- number of transistors increasing
  • CPU speed vs. memory speed -- CPU performance had been improving at faster rate
  • CPU clock speeds vs. process shrinks
  • Memory hierarchy
  • 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

• IEC standard prefixes (GB vs. GiB)

Performance Links

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

• performance typcially 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")

• 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

• 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.
  • 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]
  • SPEC -- Systems Performance Evaluation Cooperative, formed in late 1980s by major vendors
    • 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 (reference machine is a 300 MHz Sun Ultra 5 model 10; reference values for this machine are 100 SPECint2000 and
    • SPEC CPU2006 (reference machine is a 296 MHz Sun Ultra Enterprise 2 with two UltraSPARC II CPUs, each having 16 KB I and D L1 caches and an individual 2 MB L2 cache)
  • TPC -- Transaction Processing Council -- 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 -- 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)
• 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)

• 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

Appendix C Links

• Univ. of Surrey logic design tutorials

• logic gates animations and simulators
  • logic gates introduction by Ken Bigelow
  • gates and truth tables by Ana Cristina Fernandez
  • gates and timing diagrams by Alan Felzer
    (similar timing diagrams for seq. circuits, etc.)
  • circuit editor with truth tables (JHU)
  • simple circuit editor by David Viner
  • circuit simulators by Paul Falstad
  • flash animations of circuits by K.W. Rochford
  • Digital Workshop Java applet by Deborah Lynch (includes flip-flops)
  • TkGate by Jeffrey Hansen

• combinational logic design notes
  • PLA notes at U. Maryland
  • decoder
  • multiplexor
  • adder

• sequential logic design notes
  • latch
  • flip-flop (master-slave, edge-triggered)
    • notes from Bob Brown, SPSU
    • one's catching problem in master-slave flip-flops (i.e., a 0-1-0 glitch in an input is taken as 1)
  • sequential circuit
  • finite state machine
  • register
  • counter
  • two sequential logic design examples [pdf]
  • sequential logic tutorial (Univ. Sydney)

• VHDL tutorial by Weijun Zhang
• Verilog tutorial by Deepak Kumar Tala
• hardware design flow
• netlibrary: Verilog Digital System Design, Zainalabedin Navabi, 1999

Chapter 4 Links

• control unit implementation notes
• microprogramming example

• pipelines
• branch prediction overview

• example processors in game systems
  • Sega Genesis - 7.6 MHz M68000

  • Nintendo 64 - 93.75 MHz MIPS R4300i ( R4300i datasheet [pdf])
  • Nintendo GameCube - 485 MHz customized IBM PowerPC 750CXe "Gekko" ( PowerPC 740/750 manual [pdf])
  • Nintendo GameBoy Advance - 16.8 MHz Sharp ARM7TDMI
  • Nintendo Wii (previously known as Revolution) - will have IBM PowerPC and ATI variants ("Broadway" and "Hollywood"?)

  • Microsoft Xbox - 733 MHz Intel Pentium III and Nvidia GeForce 3.5 variant
  • Microsoft Xbox 360 - 3.2 GHz IBM PowerPC variant (three cores, two threads per core and one 128-bit vector unit per core) and ATI Xenos R500

  • Sony Playstation 1 - 33.9 MHz MIPS R3000A
  • Sony Playstation 2 - 300 MHz Sony Emotion Engine (includes a MIPS R5900 plus a 128-bit FPU and two 128-bit vector units)
  • Sony Playstation 3 - Cell processor (joint work of Sony/IBM/Toshiba) and Nvidia RSX

• parallelism overview
• multiple instruction issue

• Pentium 4 [pdf]

• Transmeta Crusoe [pdf]

• Itanium Processor Family (IPF, IA-64) material
  • Itanium tutorial page
  • Intel software tutorials (Itanium and P4)
  • HP page

• G. Prabhu, DLX pipeline for delayed branches with one delay slot

Chapter 5 Links

• memory addressing notes
• semiconductor memory notes

• How Stuff Works - RAM
• memory access animation
• system level memory access animation

• cache notes
• matrix multiply results
• matrix multiply cache access patterns
• regular matrix multiply versus tiling animation

• locality of reference - Hatfield and Gerald 1971 IBM Syst J memory access trace diagrams (see, e.g., Figure 10, p. 189} [pdf]
• Israel Koren's collection if computer architecture tools at U. Mass

  Cray T3E manual sections on optimizing for cache

• virtual memory - paging

Chapter 6 Links

• I/O topics overview
• RAID storage

• CPSC 231 notes: I/O devices: keyboards, monitors, disk, etc.
• CPSC 231 notes: interrupts, interrupt-driven I/O

Chapter 7 Links

• multiprocessing overview

• MFLOPS = flt. pt. ops in program / (execution time * 10^6)
• MIPS = inst. count / (execution time * 10^6)

• Amdahl's Law (a law of diminishing returns)
  derived from speedup = exec_time_old/exec_time_new
  speedup = 1 / ( (1-f_enhanced) + f_enhanced/speedup_enhancement )
• worksheet
• 1967 conference paper
• Mark Hill (U. Wisc.), "Amdahl's Law in the Multicore Era," Feb. 2009 talk at Google [video]

• CPU vs. GPU GFLOPS trends (slide 2) [pdf]

• The Landscape of Parallel Computing Research: A View From Berkeley

• multithreaded Sun SPARC T1
• Darryl Gove, Coding for Multiple Threads on a CMT System [pdf]

• Larry Seiler (Intel), et al., "Larrabee: A Many-Core x86 Architecture for Visual Computing" [pdf] (note that Intel co-author Stephen Junkins is a Clemson grad)

• Liang T. Chen (Sun), "Developing Applications For Parallel Computing"
• Anwar Ghuloum (Intel), "What Makes Parallel Programming Hard?"
• Michael Wrinn (Intel), "Confronting Manycore: Parallel Programming Beyond Multicore" [PPT]
• Charles Leiserson and Ilya Mirman (CILK Arts), "How to Survive the Multicore Software Revolution (or at Least Survive the Hype)" [38pp ebook]
• Cilk++ Demonstration: Multicore-enabling a Serial App [video]
• Intel's Threading Building Blocks (see TBB code samples)
• RapidMind modules (see a more detailed paper [pdf])
• note that Intel bought Cilk and RapidMind during summer 2009

• Nvidia CUDA (Computer Unified Device Architecture) Programming Guide [pdf]

• Jack Dongarra (UT-K), "An Overview of High Performance Computing and Challenges for the Future," Jan. 2008 talk at Google [video]
• Microsoft Channel 9 Performance Talk on Running LINPACK [video]
• Windows HPC Server 2008: Visualizing MPI traces with Vampir [video]