SCO 201 - Computer Organization

and Architecture II

Reduced Instruction Set Computers(RISC)

 Major Advances in Computers(1)
 The following are some of the major advances since the birth of the
computer:
 The family concept
 IBM System/360 1964
 DEC PDP-8
 Separates architecture from implementation
 A set of computers is offered, with different price/performance characteristics,
that presents the same architecture to the user. The differences in price and
performance are due to different implementations of the same architecture.
 Microprogrammed control unit
 Idea by Wilkes 1951
 Produced by IBM S/360 1964
 Microprogramming eases the task of designing and implementing the control unit and
provides support for the family concept.
 Cache memory
 IBM S/360 model 85 1969
 The insertion of this element into the memory hierarchy dramatically
improves performance.

2 SCO 201
 Major Advances in Computers(2)
 Solid State RAM
 (See memory notes)
 Microprocessors
 Intel 4004 1971
 Pipelining
 Introduces parallelism into fetch execute cycle
 means of introducing parallelism into the essentially sequential
nature of a machine-instruction program. Examples are instruction
pipelining and vector processing.
 Multiple processors
 This category covers a number of different organizations and objectives.

3 SCO 201
 The Next Step - RISC
 Reduced Instruction Set Computer
 The RISC architecture is a dramatic departure from the historical trend in
processor architecture. An analysis of the RISC architecture brings into focus
many of the important issues in computer organization and architecture.

 Although RISC systems have been defined and designed in a variety of ways by
different groups, the key features shared by most designs are these:

a) Large number of general purpose registers

b) Use of compiler technology to optimize register use
c) Limited and simple instruction set
d) Emphasis on optimising the instruction pipeline

4 SCO 201
 Comparison of processors

5 SCO 201
 Driving force for CISC
 Software costs far exceed hardware costs
 Increasingly complex high level languages
 Semantic gap (difference between the operations provided in
HLLs and those provided in computer architecture)
 Symptoms of this gap are alleged to include execution inefficiency, excessive
machine program size, and compiler complexity.
 Designers came up with designs that leads to:
 Large instruction sets
 More addressing modes
 Hardware implementations of HLL statements
 e.g. CASE (switch) on VAX

6 SCO 201
 Intention of CISC

 Ease compiler writing

 Improve execution efficiency
 Complex operations in microcode
 Support more complex HLLs

7 SCO 201
 Execution Characteristics
 To understand the line of reasoning of the RISC advocates, we
begin with a brief review of instruction execution characteristics.
The aspects of computation of interest are as follows:
• Operations performed: These determine the functions to be performed by
the processor and its interaction with memory.
• Operands used: The types of operands and the frequency of their use
determine the memory organization for storing them and the addressing modes
for accessing them.
• Execution sequencing: This determines the control and pipeline
organization.
 Studies have been done based on programs written in HLLs
 Dynamic studies are measured during the execution of the
program
 Static measurements merely perform these counts on the source
text of a program(give no useful info on performance).
8
SCO 201
 Summary of the results of a number of studies of high-
level-language programs

Operations
 Assignments
 Movement of data
 Conditional statements (IF, LOOP)
 Sequence control
 Procedure call-return is very time consuming
 Some HLL instruction lead to many machine code operations

9 SCO 201
 Weighted Relative Dynamic Frequency of HLL
Operations [PATT82a] (CISC)
Dynamic Occurrence Machine-Instruction Memory-Reference
(Relative frequency of Weighted Weighted
Occurrence) (Surrogate measures of actual (Surrogate measures of actual
time spent executing) time spent referencing memory)
Pascal C Pascal C Pascal C

ASSIGN 45% 38% 13% 13% 14% 15%

LOOP 5% 3% 42% 32% 33% 26%

CALL 15% 12% 31% 33% 44% 45%

IF 29% 43% 11% 21% 7% 13%

GOTO — 3% — — — —

OTHER 6% 1% 3% 1% 2% 1%

10 SCO 201
 Operands (Dynamic Percentage of
Operand References)
 Mainly local scalar variables
 Optimisation should concentrate on accessing local variables

Pascal C Average

Integer Constant 16% 23% 20%

Scalar Variable 58% 53% 55%

(80% Local Variables)

Array/Structure 26% 24% 25%

(+ a reference to an index or a
pointer @ item)

11 SCO 201
 Procedure Calls
 Very time consuming
 Depends on number of parameters passed
 Depends on level of nesting
 Most programs do not do a lot of calls followed by lots of
returns
 Most variables are local
 (c.f. locality of reference)

12 SCO 201
 Implications

 Best support is given by optimising most used and most time

consuming features
 Large number of registers
 Operand referencing
 Careful design of pipelines
 Branch prediction etc.
 Simplified (reduced) instruction set

13 SCO 201
 Large Register File

 Software solution
 Require compiler to allocate registers
 Allocate based on most used variables in a given time
 Requires sophisticated program analysis
 Hardware solution
 Have more registers
 Thus more variables will be in registers

14 SCO 201
 Registers for Local Variables
 Store local scalar variables in registers
 Reduces memory access
 Every procedure (function) call changes locality
 Parameters must be passed
 Results must be returned
 Variables from calling programs must be restored

15 SCO 201
 Register Windows
 The use of a large set of registers should decrease the need to access memory.
 The design task is to organize the registers in such a fashion that this goal is
realized.
 Because most operand references are to local scalars, the obvious approach is
to store these in registers, with perhaps a few registers reserved for global
variables.
 Only few parameters
 Limited range of depth of call
 Use multiple small sets of registers
 Calls switch to a different set of registers
 Returns switch back to a previously used set of registers
 NB: register windows were one of the main features of the Berkeley RISC
design which was commercialized as AMD Am29000, Intel i960, Sun
Microsystems SPARC and Intel Itanium.

16 SCO 201
 Register Windows cont.
 At any time, only one window of registers is visible and is
addressable as if it were the only set of registers (e.g., addresses 0
through N-1).
 The window is divided into three fixed-size areas.
 Parameter registers hold parameters passed down from the procedure
that called the current procedure and hold results to be passed back up.
 Local registers are used for local variables, as assigned by the compiler.
 Temporary registers are used to exchange parameters and results
with the next lower level (procedure called by current procedure).
 The temporary registers at one level are physically the same as the
parameter registers at the next lower level.
 This overlap permits parameters to be passed without the actual
movement of data.

17 SCO 201
 Overlapping Register Windows

18 SCO 201
 Circular Buffer (1)
 To handle any possible pattern of calls and returns, the
number of register windows would have to be unbounded.
Instead, the register windows can be used to hold the few
most recent procedure activations.
 Older activations must be saved in memory and later
restored when the nesting depth decreases. Thus, the actual
organization of the register file is as a circular buffer of
overlapping windows.
 Two notable examples of this approach are Sun’s SPARC
architecture and the IA-64 architecture used in Intel’s
Itanium processor.

19 SCO 201
 Circular Buffer diagram

20 SCO 201
  The circular organization is shown in figure above, which depicts a
circular buffer of six windows. The buffer is filled to a depth of 4 (A
called B; B called C; C called D) with procedure D active.
 The current-window pointer (CWP) points to the window of the
currently active procedure.
 Register references by a machine instruction are offset by this pointer to
determine the actual physical register.
 The saved window pointer (SWP) identifies the window most recently
saved in memory.
 If procedure D now calls procedure E, arguments for E are placed in D’s
temporary registers (the overlap between w3 and w4) and the CWP is
advanced by one window.

21 SCO 201
 Operation of Circular Buffer

 When a call is made, a current window pointer is moved to

show the currently active register window
 If all windows are in use, an interrupt is generated and the
oldest window (the one furthest back in the call nesting) is
saved to memory
 A saved window pointer indicates where the next saved
windows should restore to

22 SCO 201
 Global Variables

 Variables declared as global in an HLL can be assigned memory locations by the

compiler, and all machine instructions that reference these variables will use
memory-reference operands.
 Inefficient for frequently accessed variables
 Alternatively incorporate a set of global registers in the processor. These
registers would be fixed in number and available to all procedures. A unified
numbering scheme can be used to simplify the instruction format.

23 SCO 201
 Large Registers File versus Cache
The register file, organized into windows, acts as a small, fast buffer for holding a subset of
all variables that are likely to be used the most heavily.
From this point of view, the register file acts much like a cache memory, although a much
faster memory.
The question therefore arises as to whether it would be simpler and better to use a
cache and a small traditional register file.

Characteristics of Large-Register-File and Cache Organizations

Large Register File Cache

All local scalars Recently-used local scalars

Individual variables Blocks of memory

Compiler-assigned global Recently-used global

variables variables
Save/Restore based on Save/Restore based on
procedure nesting depth cache replacement
algorithm
Register addressing Memory addressing

24 SCO 201
 Referencing a Scalar - Window Based Register File

25 SCO 201
 Referencing a Scalar - Cache

26 SCO 201
 Compiler Based Register Optimization

 Assume small number of registers (16-32)

 Optimizing use is up to compiler
 HLL programs have no explicit references to registers
 usually - think about C - register int
 Assign symbolic or virtual register to each candidate variable
 Map (unlimited) symbolic registers to real registers
 Symbolic registers that do not overlap can share real registers
 If you run out of real registers some variables use memory

27 SCO 201
 Graph Coloring

 Given a graph of nodes and edges

 Assign a color to each node
 Adjacent nodes have different colors
 Use minimum number of colors
 Nodes are symbolic registers
 Two registers that are live in the same program fragment are
joined by an edge
 Try to color the graph with n colors, where n is the number
of real registers
 Nodes that can not be colored are placed in memory

28 SCO 201
 Graph Colouring Approach

29 SCO 201
 Why CISC (1)?
 Compiler simplification?
 Disputed…
 Complex machine instructions harder to exploit
 Optimization more difficult
 Smaller programs?
 Program takes up less memory but…
 Memory is now cheap
 May not occupy less bits, just look shorter in symbolic form
 More instructions require longer op-codes
 Register references require fewer bits

30 SCO 201
 Why CISC (2)?

 Faster programs?
 Bias towards use of simpler instructions
 More complex control unit
 Microprogram control store larger
 thus simple instructions take longer to execute

 It is far from clear that CISC is the appropriate solution

31 SCO 201
 RISC Characteristics
 For purposes of this comparison, the following are
considered typical of a classic RISC:
 1. A single instruction size.
 2. That size is typically 4 bytes.
 3. A small number of data addressing modes, typically less
than five. This parameter is difficult to pin down. In the table,
register and literal modes are not counted and different
formats with different offset sizes are counted separately.
 4. No indirect addressing that requires you to make one
memory access to get the address of another operand in
memory.
32 SCO 201
  5. No operations that combine load/store with arithmetic (e.g.,
add from memory, add to memory).
 6. No more than one memory-addressed operand per instruction.
 7. Does not support arbitrary alignment of data for load/store
operations.
 8. Maximum number of uses of the memory management unit
(MMU) for a data address in an instruction.
 9. Number of bits for integer register specifier equal to five or
more. This means that at least 32 integer registers can be
explicitly referenced at a time.
 10. Number of bits for floating-point register specifier equal to
four or more. This means that at least 16 floating-point registers
can be explicitly referenced at a time.

33 SCO 201
 RISC v CISC
 After the initial enthusiasm for RISC machines, there has
been a growing realization that (1) RISC designs may benefit
from the inclusion of some CISC features and that (2) CISC
designs may benefit from the inclusion of some RISC
features.
 The result is that the more recent RISC designs, notably the
PowerPC, are no longer “pure” RISC and the more recent
CISC designs, notably the Pentium II and later Pentium
models, do incorporate some RISC characteristics.
 Not clear cut
 Many designs borrow from both philosophies
 e.g. PowerPC and Pentium II

34 SCO 201
 RISC Pipelining
 Most instructions are register to register
 Two phases of execution
 I: Instruction fetch
 E: Execute
 ALU operation with register input and output
 For load and store
 I: Instruction fetch
 E: Execute
 Calculate memory address
 D: Memory
 Register to memory or memory to register operation

35 SCO 201
 Effects of Pipelining

36 SCO 201
 Optimization of Pipelining
 Delayed branch
 Does not take effect until after execution of the following instruction
 This following instruction is the delay slot
 Delayed Load
 Register to be target is locked by processor
 Continue execution of instruction stream until register required
 Idle until load complete
 Re-arranging instructions can allow useful work whilst loading
 Loop Unrolling
 Replicate body of loop a number of times
 Iterate loop fewer times
 Reduces loop overhead
 Increases instruction parallelism
 Improved register, data cache or TLB locality

37 SCO 201
 Loop Unrolling Twice
Example
do i=2, n-1
a[i] = a[i] + a[i-1] * a[i+l]
end do

Becomes

do i=2, n-2, 2
a[i] = a[i] + a[i-1] * a[i+i]
a[i+l] = a[i+l] + a[i] * a[i+2]
end do
if (mod(n-2,2) = i) then
a[n-1] = a[n-1] + a[n-2] * a[n]
end if

38 SCO 201
 Normal and Delayed Branch
Address Normal Branch Delayed Branch Optimized
Delayed Branch

100 LOAD X, rA LOAD X, rA LOAD X, rA

101 ADD 1, rA ADD 1, rA JUMP 105

102 JUMP 105 JUMP 106 ADD 1, rA

103 ADD rA, rB NOOP ADD rA, rB

104 SUB rC, rB ADD rA, rB SUB rC, rB

105 STORE rA, Z SUB rC, rB STORE rA, Z

106 STORE rA, Z

39 SCO 201
Use of Delayed
Branch

40 SCO 201
 Controversy
 Quantitative
 compare program sizes and execution speeds
 Qualitative
 examine issues of high level language support and use of VLSI
real estate
 Problems
 No pair of RISC and CISC that are directly comparable
 No definitive set of test programs
 Difficult to separate hardware effects from complier effects
 Most comparisons done on “toy” rather than production
machines
 Most commercial devices are a mixture

41 SCO 201