Computer Organization and Architecture

Computer Evolution and Performance

Outline

• A Brief History of Computers

• Designing for Performance

• Performance Assessment

• Intel x86 and ARM processor families

• Computer Types

A Brief History of Computers

ENIAC – the first computer

• ENIAC，Electronic Numerical Integrator And Computer

• For war purposes, to compute the ballistic trajectory

• Started in 1943, finished in 1946 (too late for war purpose)

• In university of Pennsylvania，By Professor John Mauchly and his student John P Eckert，Use Vacuum Tubes

• Weighted 30 tons, consumes $140kw$ of electric power, 1500 square feet of space, only 5000 addition per second

• As milestone of science development, used until 1995

Detail of ENIAC

• Decimal，not binary

• 10 vacuum tubes represent each digit, at any time only one vacuum tube was in the ON state

• 20 accumulators of 10-digit decimal number

• 5000 additions per second

• Programmed manually by switches

• No microprocessors

• No memory

• Changing the program could take days!

Main shortcoming of ENIAC

• No memory

• The task of entering and altering programs was extremely tedious

How to overcome this problem?

• The stored-program concept had been proposed

  • John von Neumann $\rightarrow$ “father of compute” and "father of game theory",Completed "computer and brain" and "self breeding automata theory", is the embryonic form of "artificial intelligence" field

  • Alan Turing $\rightarrow$ “father of artificial intelligence” & "annual Turing prize"

  • First publication of the idea was in 1945 proposal by von Neumann for EDVAC（Electronic Discrete Variable Automatic Computer)

• Our current computer is still called the von Neumann machine

Characteristics of Stored Program concept

• A main memory, which stores both data and instructions

• Binary numbers for both data and instructions

• An arithmetic-logic unit performs the basic operations

• The data and instructions are stored in the memory, selected by addresses

• The proper sequencing of the operation is controlled by a control unit

The von Neumann Machine

• IAS（Institute of Advanced Studies）,started in 1946

• 5 functional units

  • ALU, memory, control unit, input devices, output devices

• NOT Completed until 1952

• Until now, most computers are still structured based on this concept

• $CPU(Central\ Processing\ Unit)=ALU(Arithmetic-Logic\ Unit)+CU(Program\ Control\ Unit)\newline$

• There are connections between main memory and ALU and CU. Through the connection with CU, it receives the control signal from CU and transmits the data to ALU

• IO device for data input and output

Details of IAS

• IAS: Institute for Advanced Studies, Princeton

• Memory: $1000 \times 40\ bit\ words$ in binary number

  • Both data and instructions are stored there

• Each number is represented by a sign bit and a 39-bit value

---

• A word may also contain two 20-bit instructions

  • an 8-bit operation code

  • a 12-bit address

Registers of IAS

Several registers are set inside the CPU to temporarily save data

• Memory Buffer Register
• Memory Address Register
• Instruction Register
• Instruction Buffer Register
• Program Counter
• Accumulator
• Multiplier Quotient

IAS control unit

• The control unit operates the IAS by fetching instructions from memory and executing them one at a time

Fetch cycle

• If IBR is not empty, directly execute the instruction

• If IBR is empty, first fetch instruction, then execute instruction

Execute cycle

• Instruction enters the control circuit to control the execution of the command

• Address in MAR represents the address of the operand

Instruction types

• Data transfer

  • Memory – ALU registers

  • Register – Register

• Unconditional branch

• Conditional branch

• Arithmetic

• Address modify

Development of computer

• Von Neumann machine : initial stage of computer

• Computer architecture they proposed laid a solid foundation for the development of computers in the future

• Original computers most for special purposes

• With the development of technology, computers have gradually turned from special purpose to commercial use

Commercial Computers

• Eckert-Mauchly Computer Corporation

  • Mauchly and his student Eckert built the first computer ENIAC

  • In 1947,Eckert and Mauchly formed the corporation

  • UNIVAC I: first commercial computer

  • UNIVAC II: backward compatible

  • As a department of Sperry-Rand Corporation

IBM

• The major manufacturer of punched-card processing equipment then

• 1953 - the 701

  • IBM’s first stored program computer

  • Scientific calculations

• 1955 - the 702

  • Business applications

• Lead to 700/7000 series

• Made IBM the dominant computer manufacturer

Summary of first generation

• Use electronic tubes as the main components

  • Electronic tube is composed of wire, metal sheet, glass shell and vacuum tube

  • Large in volume, hot and expensive

  • Restrict the development of computer. use.

Second generation : transistors

• Replaced vacuum tubes

  • Invented 1947 at Bell Labs

  • Smaller

  • Cheaper

  • Less heat dissipation

  • Made from Silicon

• This results

  • More complex arithmetic, logic units, control units

  • More powerful, more complex control

  • High-level language, system software

• Transistors are the hallmark of the second generation of computers

Transistor based computer(history)

• Second generation machines

• NCR & RCA produced small transistor machines (front-runner of this field, RCA is more successful)

• IBM 7000 series

  • 1960: 7090

  • 1964: 7094，the lase member of the 7000 series

    • Data Channel

    • Multiplexer

• DEC（Digital Equipment Corporation,Alpha chip）- 1957

• Produced PDP-1

Example of transistor board(history)

• Philco 212 Transistor Boards, 1962

  • Electronic components are manually welded to the circuit board to form a complex circuit board

  • Heavy workload

  • Easy to fail

IBM 7094

• IBM 7094 is a representative of the second generation

  • It is a central-switched architecture

  • It uses data channels and multiplexor

    • A data channel is an independent I/O module with its own processor and its own instruction set

    • Multiplexor is the central termination point for data channels, the CPU, and memory

Configuration of 7094

• Total 4 data channels are connected to multiple devices, including disks, tapes, printers, etc

• Four channels, CPU and memory are connected to the multiplexer for scheduling and independent accessfail

Shortcoming of transistor and development

• Shortcoming of transistor

  • Discrete components were manufactured separately

  • The entire manufacturing process, from transistor to circuit board, was expensive and cumbersome

  • More than 10000 transistor in computer

• Development: Microelectronics

  • The invention of the integrated circuit in 1958

  • The third generation of computers

Microelectronics

• Two elements (gates and memory cells) are necessary for the main functions of computer–storage, movement, processing, and control

• From the view of microelectronics , a computer consists of

  • Gates: processing

  • memory cells : storage

  • interconnections among these elements: movement and control

• Transistors, resistors, and conductors can be made by semiconductor

• The whole circuit is mounted on a very small silicon chip instead of an equivalent circuit made of discrete components

• A silicon wafer is divided into several chips, each chip contains exactly the same circuit

• After cutting, packaging and adding pins, it becomes a chip

Moore’s Law

Pronounced in 1965 by Gordon Moore- cofounder of Intel

The number of transistors on a semiconductor chip doubles approximately every 18 month(or increases ten-fold approximately every 5 years) $\rightarrow Moore’s\ Law\newline$

$N=a \times 10^{\frac{1}{5} \times t}\newline$

Microprocessors get smaller,more compact and faster and faster!

---

Some facts revealed by Moore‘s Law

• Cost of a chip has remained almost unchanged: the cost of computer has fallen

• Higher packing density means shorter electrical paths, giving higher speed

• Smaller size making it more convenient to place in a variety of environments

• Reduced power and cooling requirements

• Fewer interconnections increases reliability

The computer family concept

• The characteristics of a computer family are

  • Similar or identical instruction set

  • Similar or identical operating system

  • Increasing speed

  • Increasing number of I/O ports

  • Increasing memory size

  • Increasing cost

---

IBM System/360

• By 1964, IBM announced System/360 family, this was the industry‘s first planned family of computers.

  • The family covered a wide range of performance and cost

  • A program written can be executed by all models of the family, with only a difference in the speed

  • The customer can start with lower model and upgrade to the higher when it is needed

---

DEC PDP-8

• In the same year(1964), Digital Equipment Corporation (DEC) announced PDP-8

  • Small，desktop
  • Lower cost，$16k

• These features enabled another manufacturer to purchase a PDP-8 and integrate it into a different system for resale

  • These manufacturers came to be known as original equipment manufacturers (OEMs)

---

Detail of DEC PDP-8

• Later models used the bus structure consists of 96 signal lines to carry control, address, and data signals

• The architecture is highly flexible, allowing modules to be plugged into the bus to create various configurations

• Bus architecture is now widely used

Generations of computer

• Vacuum tube :1946-1957

• Transistor : 1958-1964

• Small scale integration : 1965 on

  • Up to 100 devices on a chip

• Medium scale integration : to 1971

  • 100-3,000 devices on a chip

• Large scale integration : 1971-1977

  • 3,000 - 100,000 devices on a chip

• Very large scale integration : 1978 -1991

  • 100,000 - 100,000,000 devices on a chip

• Ultra large scale integration : 1991 – now

  • Over 100,000,000 devices on a chip

Technology Change

• Hardware

  • Vacuum tubes: Electron emitting devices

  • Transistors: On-off switches controlled by electricity

  • Integrated Circuits( IC/ Chips): Combines thousands of transistors

  • Very Large-Scale Integration( VLSI): Combines millions of transistors

• Software

  • Machine language: Zeros and ones

  • Assembly language: Mnemonics

  • High-Level Languages: English-like

Core Memory

• In the 1950s and 1960s, most computer memory was constructed from tiny rings of ferromagnetic material, each about a sixteenth of an inch in diameter

• Core Memory: Cores are rings of ferrite suspended in a grid of wires

• A charge to a point on the grid magnetizes the ring in a clockwise or counter-clockwise direction, which corresponds to a one or a zero: one bit

• Able to retain information when the electricity is turned off because it holds its state

• fast $(1us)$ but expensive, destructive readout

Semiconductor Memory

• 1970 – semiconductor memory: higher density (size of a single core, 256 bits），non-destructive，much faster ,more expensive

• 1974 – the price per bit of semiconductor memory dropped below the price per bit of core memory. – since then, the cost continue decreasing, the density continue increasing

• 13 generations.：The capacity of a single chip has changed from $1K, 4K, 16K, 64K, 256K, 1M, 4M, 16M, 64M, 256M, 1G$ and $4G$. Now a single memory can reach $128G$

---

Resulting New Developments – Microprocessors

• Just as the density of elements on memory chips has continued to rise, so has the density of elements on processor chips

• More and more elements placed on chip

• 1971—First microprocessor Intel 4004

• 1972—Next Intel 8008, the first 8-bit microprocessor

• 1974—Intel 8080，first general-purpose microprocessor. Faster, richer instruction sets, and has stronger addressing capabilities

---

Intel Microprocessors

• Later, 8086 was released in 1978 and 8088 was released in 1979. These two CPUs have been widely used

• In the 1980s, Intel released 286，386，486，etc

• In 1993, Pentium CPU was released, followed by Pentium 2.3

• In 2006, dual core CPU was released

• Intel has firmly occupied the processor market of desktop computers

Designing for Performance

• Performance and storage capacity of the computer are constantly improving, and the price is constantly decreasing

• Computers have been applied to all fields of life, and people’s requirements for computers are getting higher and higher

• Today, the applications require the great power of today’s microprocessor based

  • Image processing

  • Speech recognition

  • Videoconferencing

  • etc……

---

• The factors that affect a computer performance directly
  • Microprocessor speed
  • Performance balance
  • Improvements in chip organization and architecture

Microprocessor Speed

According to Moore’s theorem, by integrating more transistors on the chip and reducing the distance between circuits, the performance of microprocessors can be improved by 4-5 times every three years

• The processor designers must come up with ever more elaborate techniques for feeding a constant stream of work to do

• Branch prediction

• Data flow analysis

• Speculative execution

---

Performance gap of CPU and memory

While CPU power has raced ahead at speed, other critical components have not kept up

! ! ! Performance of memory will seriously affect the performance of CPU!

Solutions about Memory

• Increase number of bits retrieved at one time

  • Make DRAM “wider” rather than “deeper”

• Change DRAM interface

  • Cache

• Reduce frequency of memory access

  • More complex cache and cache on chip

• Increase interconnection bandwidth

  • High speed buses

  • Hierarchy of buses

Typical I/O Device Data Rates

• Same problem in I/O access

• Lots of I/O device types

• Large data rate difference

Solutions about I/O devices

• Caching

• Buffering

• Higher-speed interconnection buses

• More elaborate bus structures

• Multiple-processor configurations

Key factor is balance

Key to solving the problem of computer performance is to balance, that is, to find the best combination scheme among various components

• Processor components

• Main memory

• I/O devices

• Interconnection structures

Process speed

Three approaches to achieving increased processor speed

• Increase hardware speed of processor

  • Fundamentally due to shrinking logic gate size

• Increase size and speed of caches

  • Dedicating part of processor chip

• Change processor organization and architecture

  • Increase effective speed of execution

  • Parallelism

Problems with Clock Speed and Logic Density

• Power

  • Power density increases with density of logic and clock speed

  • Dissipating heat

• RC delay

  • Delay increases as RC product increases

  • Wire interconnects thinner, increasing resistance

  • Wires closer together, increasing capacitance

• Memory latency

  • Memory speeds lag processor speeds

Increasing cache capacity

• Typically two or three levels of cache between processor and main memory

• Chip density increased

  • More cache memory on chip
  • Faster cache access

• Pentium chip devoted about 10% of chip area to cache
• Pentium 4 devotes about 50%

More complex execution logic

Enable parallel execution of instructions

• Pipeline works like assembly line

  • Different stages of execution of different instructions at same time along pipeline

• Super-scalar allows multiple pipelines within single processor

  • Instructions that do not depend on one another can be executed in parallel!

Diminishing returns

• Internal organization of processors complex

  • Can get a great deal of parallelism

  • Further significant increases likely to be relatively modest

• Benefits from cache are reaching limit

• Increasing clock rate runs into power dissipation problem

  • Some fundamental physical limits are being reached

New approach – multiple cores

• Multiple processors on single chip

  • Large shared cache

• Within a processor, increase in performance proportional to square root of increase in complexity

• If software can use multiple processors, doubling number of processors almost doubles performance

CISC and RISC

• The Intel x86 represents the complex instruction set computers(CISC)

  • Personal computer

  • Mainframes

  • Supercomputers

• The ARM architecture represents the reduced instruction set computers (RISC)

  • SUN SPARC，MIPS

  • Apple Macintosh

  • embedded chip

  • Mobile phone

Performance Assessment

About Performance Assessment

• Evaluating the performance of different processor is difficult because of different architectures used

  • One processor is suitable for specific scenario

  • Instruction set, program language, compiler have an impact on the performance of processors

• How to evaluate the performance of the processor?

---

System clock

• System clock speed

  • Related to execution time of Instruction

  • Generated by the crystal oscillator，after analog-to-digital conversion, forms a digital voltage pulse signal

• In Hz or multiples of

• Clock rate, clock cycle, clock tick, cycle time

Clock speed

• Operations need to be synchronized

• Instruction execution in discrete steps

  • Fetch, decode, load and store, arithmetic or logical

  • Usually require multiple clock cycles per instruction

• Instruction is not fully serial

• Pipelining gives simultaneous execution of instructions

• So, clock speed is not the whole story

Instruction execution rate ! ! !

• MIPS: Million Instruction per Second

• CPI，Cycle per Instruction

• CPU constant frequency $f\newline$

• constant cycle time $T=\frac{1}{f}\newline$

• Instruction count $Ic\newline$

• CPI

$$ CPI=\frac{\sum_{i=1}^n(CPI_i \times I_i)}{I_c}\newline $$

Parameter in CPI

• $I_c$: The number of machine instructions executed for that program, not the number of instructions in the object code of the program
• $CPI_i$ be the number of cycles required for instruction type i
• $I_i$ be the number of executed instructions of type i for a given program
• The processor time T needed to execute a given program can be expressed as

$$ T=I_c \times CPI \times T\newline $$

• A processors driven by a clock with a constant frequency f or,equivalently, a constant cycle time , where

$$ T=\frac{1}{f}\newline $$

---

• MIPS

$$ MIPS_{rate}=\frac{I_c}{T \times 10^6}=\frac{f}{CPI \times 10^6}\newline $$

• MFLOPS

$$ MFLOPS=\frac{Number\ of\ floating-point\ operations\ in\ the\ program}{Execute\ time \times 10^6}\newline $$

• Millions of floating point instructions per second (MFLOPS)

• Heavily dependent on instruction set, compiler design, processor implementation, cache & memory hierarchy

---

Example 1

Type of instruction	number of instructions	The number of clock cycles for the instruction
integer arithmetic	50000	1
floating point arithmetic	20000	3
data transfer	25000	2
control instruction	5000	2

$$ CPI=\frac{50000 \times 1 + 20000 \times 3 + 25000 \times 2 + 5000 \times 2}{50000+20000+25000+5000}=1.7\newline $$

Example 2

A computer with a main frequency of 100 MHz performs a section of the program. The number and cycles of various instructions in the program are shown in the table below. Calculate the CPI of this procedure as well as the MIPS

Type of instruction	number of instructions(M)	The number of clock cycles for the instruction
Arithmetic and logical operations	5	1
data access	8	2
control instruction	2	4
other	1	3

$$ \begin{align} &CPI=\frac{5 \times 1 + 8 \times 2 + 2 \times 4 + 1 \times 3}{5 + 8 + 2 + 1}=2\newline &MIPS=\frac{f}{CPI \times 10^6}=\frac{100 \times 10 ^6}{2 \times 10^6}=50\newline \end{align} $$

Benchmarks

Benchmarks: Programs designed to test performance

• Written in high level language

  • Portable

• Represents style of task

  • Systems, numerical, commercial

• Easily measured

• Widely distributed

• System Performance Evaluation Corporation

• Most famous: SPEC 2006

  • Suitable for testing applications of computing intensive

  • 17 floating-point programs written in C, C++ and FORTRAN

  • 12 integer programs written in C and C++

  • total code of more than 3 million lines

---

Result process and analysis! ! !

• Run several different test programs, and then arithmetically process the test results to obtain an average measurement

• Average execution speed

$$ R_A=\frac{1}{m} \sum_{i=1}^m R_i\newline R_i \rightarrow the\ execution\ speed\ of\ the\ high-level\ language\ instructions\ of\ the\ i^{th}\ benchmark\ program\newline $$

• Harmonic mean

$$ R_B=\frac{m}{\sum_{i=1}^m \frac{1}{R_i}}\newline \frac{1}{R_i} \rightarrow Average\ instruction\ execution\ time\ for\ the\ i^{th}\ baseline\ procedure\newline $$

Speed Metric ! ! !

• Ability of a computer to complete a single task

• $r_i=\frac{T_{left}}{T_{suti}}\newline$

• $T_{left}$: execution time of benchmark program i on the reference system

• $T_{suti}$: execution time of benchmark program i on the system under test

• Use geometric mean for more than one benchmark program $\rightarrow r_G=(\prod_{i=1}^n r_i)^{\frac{1}{n}}\newline$

Example 3

According to the following conditions, compare the performance of the two processors by two methods (the average execution speed and the harmonic average) and analyze the significance

benchmark	The MIPS for the processor 1	The MIPS for the processor 2
benchmark 1	2	3
benchmark 2	3	4
benchmark 3	5	3

$$ \begin{align} &The\ average\ execution\ speed\newline &benchmark_1=\frac{2+3+5}{3}=\frac{10}{3}\newline &benchmark_2=\frac{3+4+5}{3}=\frac{10}{3}\newline &The\ harmonic\ average\newline &benchmark_1=\frac{3}{\frac{1}{2}+\frac{1}{3}+\frac{1}{5}}=\frac{90}{31}\newline &benchmark_2=\frac{3}{\frac{1}{3}+\frac{1}{4}+\frac{1}{3}}=\frac{36}{11}\newline \end{align} $$

Processor 2 has better performance

Amdahl’s Law ! ! !

• First proposed by Gene Amdahl

• For program running on single processor and multi processors

  • Fraction f of code infinitely parallelizable with no scheduling overhead

  • Fraction (1-f) of code inherently serial

  • T is total execution time for program on single processor

  • N is number of processors that fully exploit parallel portions of code

$$ Speedup=\frac{time\ to\ execute\ program\ on\ a\ single\ processor}{time\ to\ execute\ program\ on\ N\ parallel\ processors}=\frac{T(1-f)+Tf}{T(1-f)+\frac{Tf}{N}}=\frac{1}{(1-f)+\frac{f}{N}}\newline $$

Conclusions of Amdahl’s Law ! ! !

• f small, parallel processors has little effect

• $N \rightarrow \infty$,speedup bound by $\frac{1}{1-f}\newline$

  • Diminishing returns for using more processors

$$ Speedup=\frac{1}{(1-f)+\frac{f}{SU_f}}\newline $$

Example 5

• Assuming 20% of the program, what is the ideal speed-up ratio for an 8-core processor?

$$ Speedup=\frac{1}{0.2+\frac{0.8}{8}}=3.33\newline $$

• A 4-core processor, if you want to accelerate to a ratio of no less than 3, needs at least what proportion of the instructions that can be executed in parallel

$$ 3=\frac{1}{(1-f)+\frac{f}{N}}\newline f=\frac{8}{9}\newline $$

Intel x86 and ARM processor families

Intel

• 1971-4004

  • First microprocessor

  • All CPU components on a single chip

  • 4 bit

• Followed in 1972 by 8008

  • 8 bit

  • Both designed for specific applications

• 1974 - 8080

  • Intel’s first general purpose microprocessor

  • 8 bit data path

  • Used in first personal computer – Altair

Intel x86(history)

• 1978-8086

  • $5MHz\newline$

  • 29000 transistors

  • much more powerful

  • 16 bit

  • instruction cache, pre-fetch few instructions

• 1982-80286

  • 16 Mbyte memory addressable

  • up from 1GB

• 1985-80386

  • 32 bit

  • Support for multitasking

• 1989-80486

  • sophisticated powerful cache and instruction pipelining

  • Built-in maths co-processor

• 1993-Pentium

  • Superscalar

  • Multiple instructions executed in parallel

• 1995-Pentium Pro

  • Increased superscalar organization

  • Aggressive register renaming 寄存器重命名

  • branch prediction

  • data flow analysis

  • speculative execution

• 1997-Pentium II

  • MMX technology

  • graphics, video & audio processing

• 1999-Pentium III

  • Additional floating point instructions for 3D graphics

• 2000-Pentium 4

  • 42 Million transistors

  • Further floating point and multimedia enhancements

• 2006-Core 2 Duo

  • First x86 with dual core

  • 64 bit architecture

• 2008-Core 2 Quad – 3GHz – 820 million transistors

  • Four processors on chip

• i7、i5、i3……

• x86 architecture dominant outside embedded systems

• Instruction set architecture evolved with backwards compatibility

What is embedded system?

• An embedded system is a special-purpose computer system designed to perform one or a few dedicated functions, often with real-time computing constraints

• It is usually embedded as part of a complete device including hardware and mechanical parts

• Complexity varies from low, with a single micro-controller chip, to very high with multiple units, peripherals and networks mounted inside a large enclosure

Requirements of embedded system

• Different sizes

  • Different constraints, optimization, reuse

• Different requirements

  • Safety, reliability, real-time, flexibility, legislation

  • Lifespan

  • Environmental conditions

  • Static or dynamic loads

  • Slow to fast speeds

  • Computation or I/O intensive

Possible organization

ARM Evolution

• ARM: Advanced RISC Machine

• Designed by ARM Inc., Cambridge, England

• Licensed to manufacturers

• High speed, low power consumption

• PDAs, hand held games, phones PDA

  • E.g. iPad, iPhone

Computer Types

• Microcomputers

• Mainframes

• Supercomputers

Microcomputer

• microcomputer is generally synonymous with:

  • personal computer (PC)

  • A computer that depends on a microprocessor

• Designed to be used by individuals:

  • PCs

  • Workstations

  • Notebook computers

Workstation

• A workstation is a high-end microcomputer designed for technical or scientific applications

• The term workstation has also been used to refer to a mainframe computer terminal or a PC connected up to a network

• Historically, workstations had offered higher performance than personal computers, especially with respect to graphics and CPU power, memory capacity and multitasking ability

Mainframe

The chief difference between a supercomputer and a mainframe is that a supercomputer channels all its power into executing a few programs as fast as possible, whereas a mainframe uses its power to execute many programs concurrently

Important terminology ! ! !

• Bit: a binary digit that can have value 0 or 1

• Byte: defined as 8 bits

• Word: a set of bits constituting the smallest unit of addressable memory

• KB: $2^{10}$ bytes (1024 bytes)

• MB: $2^{20}$ bytes

• GB: $2^{30}$ bytes