Kotebe Metropolitan University
Computer Science and Technology Department
Computer Architecture and Organization (CoSc2041)
6. Introduction to Advanced Topics
6.1. Introduction To RISC
Since the development of the stored program computer around 1950, there are few innovations in
the area of computer organization and architecture. Some of the major developments are:
The Family Concept: Introduced by IBM with its system/360 in 1964 followed by DEC, with
its PDP-8. The family concept decouples the architecture of a machine from its
implementation. A set of computers are offered, with different price/performance
characteristics, that present the same architecture to the user.
Microprogrammed Control Unit: Suggested by Wilkes in 1951, and introduced by IBM on
the S/360 line in 1964. Microprogramming eases the task of designing and
implementing the control unit and provide support for the family concept.
Cache Memory: First introduced commercially on IBM S/360 Model 85 in 1968. The
insertion of this element into the memory hierarchy dramatically improves performance.
Pipelining: A means of introducing parallelism into the essentially sequential nature of a
machine instruction program. Examples are instruction pipelining and vector
processing.
Multiple Processor: This category covers a number of different organizations and
objectives.
One of the most visual forms of evolution associated with computers is that of programming
languages. Even more powerful and complex high level programming languages has been
developed by the researcher and industry people.
The development of powerful high level programming languages gives rise to another problem
known as the semantic gap, the difference between the operations provided in HLLs and
those provided in computer architecture.
The computer designers intend to reduce this gap and include large instruction set, more
addressing mode and various HLL statements implemented in hardware. As a result the
instruction set becomes complex. Such complex instruction sets are intended to-
Ease the task of the compiler writer.
Improve execution efficiency, because complex sequences of operations can be
implemented in microcode.
Provide support for even more complex and sophisticated HLLs.
To reduce the gap between HLL and the instruction set of computer architecture, the system
becomes more and more complex and the resulted system is termed as Complex Instruction
Set Computer (CISC).
A number of studies have been done over the years to determine the characteristics and patterns
of execution of machine instructions generated from HLL programs. The instruction execution
characteristics involves the following aspects of computation:
1
Operation Performed: These determine the functions to be performed by the processor and
its interaction with memory.
Operand 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.
Operations:
A variety of studies have been made to analyze the behavior of HLL programs. It is observed that
Assignment statements predominate, suggesting that the simple movement of data is of
high importance.
There is also a presence of conditional statements (IF, Loop, etc.). These statements are
implemented in machine language with some sort of compare and branch instruction. This
suggests that the sequence control mechanism of the instruction set is important.
A variety of studies have analyzed the behavior of high level language program. The next table
includes key results, measuring the appearance of various statement types during execution which
is carried out by different researchers. Students are expected to judge that the table is correct
from their programming experience.
Table: Relative Dynamic Frequency of High-Level Language operation
Study [HUCK83] [KNUTH71] [PATT82] [TANE78]
Language Pascal Fortran Pascal C SAL
Workload Scientific Student System System System
Assign 74 67 45 38 42
Loop 4 3 5 3 4
Call 1 3 15 12 12
IF 20 11 29 43 36
GOTO 20 9 -- 3 --
Other -- 7 6 1 6
[HUCK83] Huck, T; "Comparative analysis of computer architectures", Stanford University Technical
Report
No.83-243.
[KNUTH71] Knuth D; "An Empirical Study of FORTRAN programs ", Software practice and
Experience, Vol. 1,1971.
No.83-243
[PATT82] Patterson, D and Sequin, C; "A VLSI RISC ", Computer, September 1982.
[TANE78] Tanenbaum, A; "Implication of Structured Programming for machine architecture ",
Communication of the ACM, March 1978
These results are instructive to the machine instruction set designers, indicating which type
of statements occur most often and therefore should be supported in an
“optimal” fashion.
2
From these studies one can observe that though a complex and sophisticated instruction set is
available in a machine architecture, common programmer may not use those instructions
frequently.
Operands:
Researches also studied the dynamic frequency of occurrence of classes of variables. The
results showed that majority of references are single scalar variables. In addition references to
arrays/structures required a previous reference to their index or pointer, which again is usually
a local scalar. Thus there is a predominance of references to scalars, and these are highly
localized.
It is also observed that operation on local variables is performed frequently and it requires a
fast accessing of these operands. So, it suggests that a prime candidate for optimization is
the mechanism for storing and accessing local scalar variables.
Procedure Call:
The procedure calls and returns are important aspects of HLL programs. Due to the concept of
modular and functional programming, the call/return statements are becoming a predominate
factor in HLL program.
It is known fact that call/return is a most time consuming and expensive statements. Because
during call we have to restore the current state of the program which includes the contents of local
variables that are present in general purpose registers. During return, we have to restore the
original state of the program from where we start the procedure call.
Thus, it will be profitable to consider ways of implementing these operations efficiently. Two
aspects are significant, the number of parameters and variables that a procedure deals with, and the
depth of nesting.
Implications:
A number of groups have looked at these results and have concluded that the attempt to make
the instruction set architecture close to HLL is not the most effective design strategy.
Generalizing from the work of a number of researchers, three elements emerge in the computer
architecture.
First, use a large number of registers or use a compiler to optimize register
usage. This is intended to optimize operand referencing.
Second, careful attention needs to be paid to the design of instruction pipelines.
Because of the high proportion of conditional branch and procedure call
instructions, a straight forward instruction pipeline will be inefficient. This
manifests itself as a high proportion of instructions that are pre-fetched but
never executed.
Third, a simplified (reduced) instruction set is indicated. It is observed that there
is no point to design a complex instruction (CISC) set which will lead to a
complex architecture. Due to the fact, a most interesting and important processor
architecture evolves which is termed as Reduced Instruction Set Computer
(RISC) architecture.
3
Although RISC system have been defined and designed in a variety of ways by different groups, the
key elements shared by most design are these:
A large number of general purpose registers, or the use of compiler
technology to optimize register usage.
A limited and simple instruction set.
An emphasis on optimizing the instruction pipeline
An analysis of the RSIC architecture begins into focus many of the important issues in computer
organization and architecture.
The comparison of RISC and non-RISC systems is given in the next table.
Table: Characteristics of some CISCs, RISCs and Supersclar Processors
Complex Reduced
Instruction Set Instruction Set
Superscaler
(CISC) Computer (RISC) Computer
Characteristic IBM VAX Intel MIPS Power Ultra MIPS
SPARC
s 370/168 11/780 80486 R4000 PC SPARC R10000
Year
1973 1978 1989 1987 1991 1993 1996 1996
Developed
Number of
208 303 235 69 94 225 -- --
Instructions
Instruction
Size 2-6 2-57 1-11 4 4 4 4 4
(bytes)
Addressing
4 22 11 1 1 2 1 1
modes
Number of
general-
16 16 8 40-520 32 32 40-520 32
purpose
registers
Control
Memory size 420 480 246 -- -- -- -- --
(kbits)
Cache size
64 64 8 32 128 16-32 32 64
(kbits)
Characteristics of Reduced Instruction Set Architecture:
Although a variety of different approaches to reduce Instruction set architecture have been taken,
certain characteristics are common to all of them:
1. One instruction per cycle.
2. Register–to–register operations.
3. Simple addressing modes.
4. Simple instruction formats.
4
1. One machine instruction per machine cycle:
A machine cycle is defined to be the time it takes to fetch two operands from registers,
perform an ALU operation, and store the result in a register.
With simple, one-cycle instructions there is little or no need of microcode, the machine
instructions can be hardwired. Hardware implementation of control unit executes
faster than the micro-programmed control, because it is not necessary to access a micro-
program control store during instruction execution.
2. Register –to– register operations
With register–to–register operation, a simple LOAD and STORE operation is required to
access the memory, because most of the operations are register–to-register. Generally
we do not have memory – to – memory and mixed register/memory operation.
3. Simple Addressing Modes
Almost all RISC instructions use simple register addressing. For memory access only,
we may include some other addressing, such as displacement and PC-relative. Once the
data are fetched inside the CPU, all instruction can be performed with simple register
addressing.
4. Simple Instruction Format
Generally in most of the RISC machine, only one or few formats are used. Instruction
length is fixed and aligned on word boundaries. Field locations, especially the opcode, are
fixed. With fixed fields, opcode decoding and register operand accessing can occur
simultaneously. Simplified formats simplify the control unit.
6.2. Introduction to Pipelining
It is observed that organization enhancements to the CPU can improve performance. We have
already seen that use of multiple registers rather than a single accumulator, and use of cache
memory improves the performance considerably. Another organizational approach, which is quite
common, is instruction pipelining.
Pipelining is a particularly effective way of organizing parallel activity in a computer system. The
basic idea is very simple. It is frequently encountered in manufacturing plants, where pipelining is
commonly known as an assembly line operation.
By laying the production process out in an assembly line, product at various stages can be
worked on simultaneously. This process is also referred to as pipelining; because, as in a
pipeline, new inputs are accepted at one end before previously accepted inputs
appear as outputs at the other end.
To apply the concept of instruction execution in pipeline, it is required to break the instruction in
different task. Each task will be executed in different processing elements of the CPU.
5
As we know that there are two distinct phases of instruction execution: one is instruction fetch
and the other one is instruction execution. Therefore, the processor executes a program by
fetching and executing instructions, one after another.
Let and refer to the fetch and execute steps for instruction . Execution of a program consists
of a sequence of fetch and execute steps is shown in the next figure.
Figure: Sequential Execution.
Now consider a CPU that has two separate hardware units, one for fetching instructions and
another for executing them.
The instruction fetch by the fetch unit is stored in an intermediate storage buffer
The results of execution are stored in the destination location specified by the instruction.
For simplicity it is assumed that fetch and execute steps of any instruction can be completed in one
clock cycle.
The operation of the computer proceeds as follows:
In the first clock cycle, the fetch unit fetches an instruction (instruction , step ) and
stored it in buffer at the end of the clock cycle.
In the second clock cycle, the instruction fetch unit proceeds with the fetch operation for
instruction (step ).
Meanwhile, the execution unit performs the operation specified by instruction which is
already fetched and available in the buffer (step ).
By the end of the second clock cycle, the execution of the instruction is completed and
instruction is available.
Instruction is stored in buffer replacing , which is no longer needed.
6
Step is performed by the execution unit during the third clock cycle, while instruction is
being fetched by the fetch unit.
Both the fetch and execute units are kept busy all the time and one instruction is
completed after each clock cycle except the first clock cycle.
If a long sequence of instructions is executed, the completion rate of instruction
execution will be twice that achievable by the sequential operation with only one unit that
performs both fetch and execute.
Basic idea of instruction pipelining with hardware organization is shown in the next figure.
Figure: Hardware Organization
The pipeline execution of fetch and execution cycle is shown in the next figure.
Figure: Pipeline Execution.
The processing of an instruction need not be divided into only two steps. To gain further speed
up, the pipeline must have more stages.
7
Let us consider the following decomposition of the instruction execution:
Fetch Instruction (FI): Read the next expected instruction into a buffer.
Decode Instruction ((DI): Determine the opcode and the operand specifiers.
Calculate Operand (CO): calculate the effective address of each source operand.
Fetch Operands (FO): Fetch each operand from memory.
Execute Instruction (EI): Perform the indicated operation.
Write Operand (WO): Store the result in memory.
There will be six different stages for these six subtasks. For the sake of simplicity, let us assume
the equal duration to perform all the subtasks. It the six stages are not of equal duration, there
will be some waiting involved at various pipeline stages.
The timing diagram for the execution of instruction in pipeline fashion is shown in the next figure.
Figure: Timing sequence in pipeline execution
From this timing diagram it is clear that the total execution time of 8 instructions in this 6 stages
pipeline is 13-time unit. The first instruction gets completed after 6 time unit, and thereafter in each
time unit it completes one instruction.
Without pipeline, the total time required to complete 8 instructions would have been 48 (6 X 8)
time unit. Therefore, there is a speed up in pipeline processing and the
speed up is related to the number of stages.
6.3. Introduction to Multiprocessors. (Reading Assignment)
Final Assignment: prepare three pages report about computer architecture and
organization of Intel core i5 processors and memory. Presentation date will be notified later.