 |
These notes provide an introduction to the architecture and organisation of digital computers. These are course notes for the module CSC 722 Computer Architecture, part of the course MSc/PgDip in Computer Science and Applications, School of Computer Science, The Queen's University of Belfast.
A very simple model of a computer is shown in Figure 1.1. At its simplest, the Central Processing Unit (CPU) is a glorified calculator, the memory stores the results of calculations - it is a set of labelled cells - the label is called the address, each cell contains a number - data. The bus is simply a pipeline along which data and addresses can flow.
Both data and addresses are stored as numbers, though data numbers may be interpreted otherwise, e.g. as text characters.
As well as containing data, the memory also contains the program - in the form of numeric instructions. Ultimately, everything is reduced to numbers.
What is a computer program? Take, for example, the C/C++/Java instruction:
z = x + y; /* add variables x and y, result in z*/In a programming language, each variable is associated with a memory cell: e.g.
x at location 0, y at 1, z at 2;
therefore in Figure 1.1
the value in x is 22, in y, 33, and in z, 0. Note the difference between address
(for y, it is 1) and data or value (for y it is 33).
The fact that Java is interpreted, rather than compiled, makes it a little different. Nonetheless, what we say about general computer organisation remains valid. To execute the instruction, the CPU may need to execute a number of sub-instructions (machine instructions), e.g.
Four or five machine instructions per high-level language instruction is typical.
Although we usually talk of just bus, there are three parts to a normal bus: the data-bus, the address-bus, and the control part. The bus operates as follows, take P2 above: first the address (1) is put on the address-bus, then control asserts read-memory, some time later the contents of address 1 (33) is put on the data-bus.
Some detail is missing:
The answer to these is that the machine instructions are just another form of data, and the controller in the CPU must fetch them from memory, and execute them; thus, there are two sorts of data flowing along the bus - actual numeric values, and machine instructions; the controller is in a continuous cycle:
This is the famous fetch-execute cycle.
In the remainder, I will fill in some more detail - going from an overview to increasing detail; the idea is that you stop when the detail gets too much.
A CPU and memory aren't much use without a keyboard and screen, and a disk drive, i.e. a useful computer is actually a computer system.
Figure 1.2 shows the organisation of a simple computer system with one CPU, memory and three input-output (I/O) devices - peripherals: a disk and a keyboard & screen. As always, the components are connected by a system bus - this is the same as the bus mentioned above; communication with peripherals can be done in a manner similar to memory reading/writing.
Figure 1.3 shows main memory; it is essentially a sequential collection of cells, each of which, typically, can store eight binary digits - bits - BInary digiTs. Each bit is like a sub-cell that can be `0' or `1'. Bits have much in common with light-bulbs - they are either on - value 1, or off - value 0.
We commonly term a collection of eight bits a byte.
Each cell has an address.
Addresses run from 0 to N-1, where N is the size of the memory; on a typical PC these days, N is 64 Mega(bytes) - Mega = million, well actually 1048576 = 220.
Each bit is a single binary value: you can count only from 0 to 1 with it;
however, a collection of eight bits, properly interpreted, allows you to count
from 0 up to 255; and 16 bits, 0 ...65535 (64K - 1). The byte shown in address 0
of Figure 1.3
contains 0001 0101 which is decimal (base-10) 22,
hexadecimal (base-16) 15, or octal (base-8) 025. (We will cover
number systems in chapter 2).
Essentially, Figure 1.2 conforms to the so-called von Neumann computer architecture, which has five basic parts:
However, inside the machine, there is nothing to distinguish data from instructions, nor, for that matter, data from addresses - except in how they are used.
A memory location, therefore, can store:
As indicated, the CPU consists of an Arithmetic-Logic-Unit (ALU) - the calculator, and a controller - to do the fetching and executing of the program instructions; in addition, we need a few local memory registers - for storage of temporary data, and buses to transfer data and addresses throughout the CPU.
The ALU is the calculator part. The ALU takes the contents of ALU input buses A and B and combines them in some way (add, subtract, logical OR, etc.) and passes the result onto a C data bus. Let us assume that this is a 16-bit machine, i.e. the buses and ALU take 16-bit numbers - they are 16-bits wide.
A simple ALU is shown in Figure 1.4. It has a number of functions which are selected by function selection control lines F; the control lines are equivalent to selecting the operation on a calculator, e.g. add, subtract. Two condition flags are output: N, set to 1 if last operation caused a negative result; Z, last operation, if a zero result; result flags are important for constructing conditional instructions (if, else).
Figure 1.5 gives a view of a simplified CPU - but not so simplified that we cannot describe how an actual program might operate in it; with few additions figure 1.5 would actually work. The major thing we have left out is control.
In addition to the buses - both internal and system - the system bus is one on the far left), and ALU, all mentioned before, we have just three new items: the memory address register (MAR), the memory buffer register (MBR), and the accumulator register(AC).
Conceptually, registers are no different from main memory cells.
The MAR and MBR are used for communicating with memory: when the CPU needs to read load from memory, it puts the address of the required item into MAR, asserts read on the control part of the system bus, some time later, the system bus will transfer the relevant data item into the MBR; for write store, it puts the address in MAR, the data in MBR, and asserts write, the data are then copied into the relevant memory location.
The AC is used as a general holding register for operand (input) data and results.
All will become clear if we return to the example program statement:
z = x + y;
As in the introduction, assume that z corresponds to location 2, x to 0, and y to 1. The program, as it would appear in machine instructions, is:
Here, and in other modules, you will frequently encounter the term abstraction, most often in the context of an antidote to complexity. It crops up under a variety of guises: separation of concerns, structured levels, modular this and that, information hiding, modelling.
A dictionary definition of abstraction (the verb) is: the process of considering (extracting) certain essential properties of objects while omitting other properties that are not relevant (usually inessential details); the act of abstraction or abstracting produces an abstraction (noun) which collectively refers to the set of chosen properties.
From our point of view abstraction does have two important facets which are related but different, namely, extraction (of the essential from the inessential) and idealisation (i.e. the irrelevant details are deviations from the ideal). Often, somewhat loosely, an abstraction may be called a model.
In the following paragraphs I give examples of abstraction applied to computing and more mundane fields.
Systems engineering, in general, is one of the great breakthroughs of the 20th century. Without it, only very clever people, who could carry the plans for the total system (cathedral, television, satellite...) in their heads, could be effective engineers. With systems engineering a bit of clever decomposition can yield a problem that is solvable by teams of mere mortals.
The key concept here is probably that of a black-box abstraction; a black-box is completely characterised by: (a) what it expects as inputs; (b) what it produces as outputs; and (c) the relationship between inputs and outputs.
It is impossible and undesirable for engineers or programmers to carry in their minds the hundreds of thousands of transistors, resistors, connections ..., and software that make up a computer system. Thus it is necessary to decompose (break-up) the system, into chunks or sub-systems. But we have to be methodical about this: if you break a 2,000,000 component computer into 200,000 sub- systems, you are not much further ahead - where next?
A computer can be viewed as a hierarchy of levels as shown below. At any one time you make up your mind what level concerns you.
Here the computer is viewed as a machine which performs a specific function, e.g. a spreadsheet, a word-processor; the user at this level shouldn't have to be concerned with any details of computer science or engineering, just as the average car driver need not be concerned with the internal details of car engines.
Here the computer is viewed as a (virtual) machine which obeys the instructions or understands the statements of a high-level language such as C, C++, Java, COBOL, etc. A compiler or interpreter converts these instructions into lower level machine or assembly code.
At this level, we view the computer as being run by a program (a sequence) of so called assembly level instructions.
Here we see instructions that explicitly move data around between registers, accumulators, program counters, ports and memory addresses; and instructions that transform or combine their contents (e.g. ADDD, SUBD, LODD). To be effective at this level, the programmer must have a model of the machine - its architecture, or, more specifically, its instruction set architecture (ISA) that properly expresses: (a) the interconnection of registers to indicate allowable data movements, and (b) the repertoire of transformations and combinations that can be performed in the arithmetic-and-logic unit and elsewhere.
Assembly language is just a symbolic form of the language understood by level 2 below (which are coded as numbers). Assembly language is translated into machine language using an assembler.
At this level, we have operating system software in charge of running the assembly language. In some contexts, this level is absent.
Here are the same sort of instructions that we described for the previous level: major difference, they are now coded as numbers, rather than alphanumeric symbols (e.g. 2501 instead of (say) ADDD x). Two points: (a) they are ready for execution in the processor - the Level 1 machine `understands' them; and, (b) human programmers have great difficulty in understanding them!
This level is concerned with the (underlying) engine that implements individual Level 2 instructions by appropriately directing the the components and their interconnections at that level. In some (mostly earlier, but also some modern RISC machines) machines this level does not exist and machine instructions are implemented directly by digital logic.
Here we are at the level of gates and memory cells. The language is made up of 1s and 0s or, at best, binary numbers.
There are certainly levels below level 0 - transistors, p-n junctions, molecules, atoms, ...!), but the six above should be enough for us. In fact, we shall be mainly concerned with level 2 and above, though, just for completeness, we will show how some basic components may be built from digital logic gates.
At each level, the programmer or engineer or physicist must pay attention to different sorts of object or quantity. At level 5 (high-level language,), the programmer deals with the data types provided by the language. At level 4 you are forced to deal with physical storage locations, registers and the like. And so on, until at level 0 you are concerned with bits (1s and 0s).
The major point is that, the higher the level of abstraction, the more powerful the machine becomes. For example, you want to type a letter on a word-processor. At level 6 you just do it. At level 5 you first have to write a word-processor program - allocate a few years or so for that! At level 4 you have to write a compiler so that you can write the word-processor - there isn't much point in trying to write a word-processor in assembler, it'll take so long and be so error prone that the project will never end.
And so on. Down to level 0, where you first have to make a computer from thousands of chips, then write the microcode, ..., then write the compiler, the write the word-processor, ..., then type the letter.
The difference between working at level 4 (say) and level 2 is like discovering that you can take 100 metre strides, instead of the 1.5 meters of ordinary mortals.
These notes, and whatever is handed out at lectures, constitute the essential reading. However, in addition to handing out some extra notes and exercises during lectures, I may also inform you that certain sections of these notes are not part of the course, and as such are off limits for examinations and other assessment.
You cannot but gain from reading from other textbooks, and articles and I strongly encourage you to read as widely as possible.
These notes were originally based on [Tanenbaum, 1990]. This is now in its 4th edition [Tanenbaum, 1999]. Like all Tanenbaum's work, these are brilliant books. The only reason I have developed these notes is that I figure they are slightly advanced for a course like this - okay to read once you've attended the lectures, but not teach-yourself. What really differentiates these book from many others is the lack of waffle; this man understands everything he writes about - unlike some other authors.
If you want an easy but comprehensive introduction to computer science [Brookshear, 1999] is clear and easy to read; it covers many of the topics on this course.
If I had to teach without these notes, i.e. make you buy a textbook instead of handing out notes, it would probably be [Stallings, 2000] - just that little bit more introductory than [Tanenbaum, 1999] and [Tanenbaum, 1990]. The same comments go for [Clements, 1993].
The two books by Patterson and Hennessy are achieving the status of "bibles" of computer architecture theory, [Hennessy and Patterson, 1996], [Patterson and Hennessy, 1994].
Hillis [Hillis, 1999] gives a very readable account for lay-persons, but could be very interesting to you for its numerous insights on the basics of computers.
[BBC, 1992] is the book of the TV program that the BBC ran at the end of 1991. We may get a chance to watch parts of the videos.
If this course gives you an appetite for electronics, and you want to teach yourself more, then I cannot recommend better than [Horowitz and Hill, 1989].
Having said that these notes constitute the essential reading, that does not mean that a quick couple of reads through them will allow you to pass the examination, or otherwise become educated in the subject.
Education is an active, not passive process. Thus, I strongly encourage you to:
z = x + y.
(b) Assuming the address is limited to 1 bit, 4 bits, 8 bits, 16 bits, 32 bits; in each case how would this limitation become evident to a programmer.
Pentium III.
nanosecond. Why is this impossible; explain what is possible. Hint:
What is the speed of light! Translate this to feet per nanosecond.
seconds?
; there are 18 character per in. horizontally, and 6 lines per in.
vertically. Assume uniformity of pages, and ignore any differences due to
programs, diagrams. Start by calculating characters per page.