Computer Science notes ⇒ Introduction to Computer Systems

Systems are hierarchical structures. Each level is a component of a higher level, and each component also has components at lower levels. Some components and levels are logical. Each topic in Computer Science tries to deal with one level at a time. Mixing levels of hierarchy can lead to confusion.

Engineering principles in one area usually apply in some form in other areas (one principle can be applied to, say, civil engineering, just as much as CS). For example, good practice in development, documentation and testing principles, the planning and management, dealing with cost effectiveness and professional oversight are all traits of engineers.

Students rarely meet reality, however engineering is based in reality. Reality is big, messy and imprecise. Reality changes goals and resources during projects, demands evidence of performance and wants things to last forever (but then discards them the following week).

As reality is often too much for engineers to conceive, they simplify it using models. Models are representations of reality. Programs, diagrams, mathematical definitions, CAD, working scale models are all examples of models. Models are used to abstract away detail that is not relevant to the current purpose. Models can be static (diagrams, maths, etc) or dynamic (programs, train layouts, animated CAD drawings, etc).

This is what the system is required to do. This is a constraint also - you should not be making the system do things that is beyond the requirements. Requirements are quite general, as this is looking at the system from a high level. At lower levels, requirements are more specific to a particular architecture, platform, etc...

Testing happens against the requirements, therefore the requirements need to be objective and clear. Requirements also change, and these changes must be documented. Engineers aim to just meet the requirements; extras are not needed, or in some cases desired.

A specification is a contact for a development. It meets the requirements and is an abstract description of the requirements - it is not how the requirements are going to be achieved. It could use diagrams, mathematics or logical analysis. It needs to be rigorous and unambiguous. It should be checked against the requirements.

Verification - This checks that the data is factually correct.
Validation - This checks that the data fits in with it's intended use.
Certification - The checks a system against external documentation and operational standards.

This is less abstract than a specification, however still does not contain any code. There may be different design at different levels. A design also adds more constraints.

This must match the design. It also includes documentation - both of the development and for the users. Implementation is a trivial stage compared to the specification and designs, if they are done right.

Some tips for implementation are:

• Re-use code where ever possible
• Document the original or re-used code
• Document all change and the rationale behind those changes to re-used code.
• Write re-usable code
• Use a good style of coding and document your coding fully
• Document how procedures and packages are used
• Document what each component does and the conditions they take.

This is the most important part. It is dependent on the earlier parts and consists of various parts:

• Unit tests - this tests the internal code
• Module, integration and system tests - testing the individual components and composition verification
• Acceptance or certification testing - validation that works as intended in context and within standards

Testing reveals errors, not correctness; it is impossible to show a program is perfect. Tests should be designed to break the system; you should always be testing for unexpected things (e.g., illegal inputs, out-of-range data). Testing should occur close to or on the boundary of the operational envelope.

The specification and design should be used to identify meaningful tests.

Most systems change after delivery, perhaps a new platform is introduced, etc... Bug fixes may also need to be applied. Documentation and code needs to be maintained..

Regression testing should be performed.

• Work out what tests should and should not still work
• Run all your tests again and check the results
• Don't just test the changed parts.

Few systems are ever thrown away. If a system is used, it is likely to be replaced. You should try to reuse and recycle. There could be lessons to be learnt from an old system, requirements and scenarios could be similar to the new system, components might need to be retained and each of these elements requires careful analysis.

Documentation is crucial

Any input is an event. A command or data sent may change the system state. How an event is determined depends on your view, for example from the view of the CPU only electrical pulses are valid. Logically this could be a single character, a signal, etc... From a human view, this could be a string of text, or a whole mouse movement (which relates to multiple signals).

Keyboard Events

Mouse Event

A filename is a logical reference to a distributed set of addresses. Physically this is an index address and lots of separate data blocks.

A computer takes well formed commands and then uses context to deduce what's intended.

Stallings 1.1

There are different ways you can look at things:

• Internals - above the hardware level but below the operating system
• Architecture - how the programmer sees the system
• Organisation - how features are laid out

Architecture

Organisation

Stallings 1.2

• control unit - controls execution cycle
• ALU - computational core
• registers - internal memory
• connections - connections between other units

Stallings 2.1

John von Neumann was at the Princeton Institute for Advanced Studies (IAS). He came up with the theory for a stored-program computer in about 1945. The first IAS machine was completed in 1952. Although this is later than Turing's efforts in the 1940's, the IAS system was public and open from inception so became more well known.

The IAS architecture stored data and instructions in a single read/write memory. The memory contents were addressable by locations and sequential execution from one instruction to the next occurred.

Main memory is a collection of locations, each holding a binary value. Instructions are stored and read sequentially in one set of addresses. A logical abstraction of this is a stack. All locations have sequential identities (addresses) which data is stored and accessed by.

Architecture functions and organisation are built round groups of addresses.

Main memory has n locations. Instructions are in locations 0-x. The instruction stack is a logical data structure with input at the top, and reads happen at the top too.

Each memory location is 1 word. The IAS machine had 1000 words in memory. The Intel 8088 (1979) had 1 MB. The current Pentium 4 (IA32) architecture has 64 GB of words.

Each word contains a fixed number of bits. The IAS had 40-bits words, but most modern systems have 2ⁿ bits, for example, Intel processors until the 386 had 16 bit words. Early Pentium's had 32 bit words and the Pentium II onwards had 64 bit words.

There are many formats for a word. The simplest is the opcode followed by an operand. The opcode identifies one machine instruction (operation). The operand is the address of data to be operated on.

Computer operations are in a series of cycles. For example, retrieve a word from main memory, execute instruction in a word, etc..

Instructions locations number logically from 0. When the computer systems, a program counter (pc) is set (i.e., to 0). This causes the 0th instruction to be fetched. Instruction is then executed and the pc is incremented. The first instruction is executed next. The fetched instruction is written to the instruction register (ir) for execution.

The pc and ir are CPU registers, like main memory, but fast and inside the CPU. pc and ir are CPU registers. The pc only needs to hold an address. CPU buffers are common, for example, between the pc, ir and main memory. Buffers could include the mar (memory address register) and the mbr (memory buffer register)

The CPU control unit determines when to fetch an instruction. The communication between the main memory and the CPU uses buses for addresses, control signals and data. The control uses a clock tick (this is a regular pulse signal). The control units ticks to start the next element of the F-E cycle.

Fetched instructions might need more memory interaction because an execution can take place - this is an indirect cycle.

The execution that occurs depends on the instruction in the ir. For example, it could be

• moving data among registers, from CPU to main memory, etc
• modifying control
• I/O
• ALU invocation

Assume end-to-end execution of stored programs. The CPU is very efficient compared to other peripherals and the F-E cycle is faster than other devices. Rather than the CPU hanging and waiting for a device, interruptions allow the CPU to continue with another instruction and return to one that's waiting on a device when the interrupt is called.

Different types of interrupts exist:

• Program Interrupts - Illegal processing attempted (for example, a divide by 0, arithmetic overflow or an illegal memory call)
• Timer Interrupts - Allow regular functions to occur (housekeeping, polling for data, etc)
• Device Interrupts - Come from device controllers, such as I/O. These signals could be such as "ready", "error", etc.
• Hardware Failure Interrupts - Power out, memory parity error, etc.

A processor fetches an instructiowww.n which involves a device call. The execution calls a set-up program (I/O program) which prepares buffers for data, etc... The device driver (an I/O command) is then called and the execution terminates.

This is a variant of the fetch cycle. The current pc is stored in a dedicated address. After the interrupt is completed, the control unit reads the stored pc value and resumes at that location.

The CPU knows addresses to be used. The interrupt only starts when the previous instruction is fully executed.

Any device may send an interrupt (signalling that it is ready for I/O, etc), however the handling details are specific - it might include the OS for example.

Devices inside a computer are connected using buses, lines and interfaces.

There are many different types of connections - point-to-point (a dedicated link) or a bus (a link shared by many components). A bus corresponds to a particular traffic type - data, addresses, etc...

Networking can be wired or wireless. Conceptually it is different to internal communications, but physically it is becoming similar to buses. Bus and network protocols are slowly converging.

Internal and external communications have different emphases. Networking has an emphasis on security, whereas buses tend to emphasise robustness.

Buses link at least two components, and traffic is available to all logical components connected to that bus. Logically, a bus is dedicated to either data, addresses or control signals. Physically, a bus comprises of a bundle of separate bus lines.

Buses are things passing values - like a flow of communications. In reality, it carries current, so has values at all points simultaneously - logically this is either 1 or 0. Unfortunately transfer isn't really instant (assuming that it is is a level of abstraction). A pulse that is either on or off doesn't exist in the real world. There is a leading edge and a trailing edge as voltage rises or falls. These edges don't carry any data and signals are not relevant here.

Buses use serial communications, i.e., 1 bit at a time. There are 8 lines for an 8 bit bus.

Parallel buses are buses of serial lines. Each bus still carries one thing, but a communication may be split over many buses. In theory, parallel is faster and more efficient, however serial buses tend to have higher data rates due to the overhead of parallel (assembly and disassembly of packets).

Early buses had separated, unsynchronised clocks - CPU time was wasted waiting for devices to catch up. Modern buses are controlled by a single CPU clock, however, variable speeds are being re-introduced according to application.

Data Bus and Lines

Address Bus and Lines

Control Bus and Lines

Stallings 3.3, 3.4, 7.5

Each computer component is a module with an interface. It is based on the engineering principle of each module being self-contained with minimal interfaces. This is true of modules in any other engineering (software, etc)

Memory Interface

CPU module

DMA

Stallings 3.4

A very simple arrangement is as follows:

However, with external buses there are propagation delays. It takes time to co-ordinate bus use. More components or devices requite long buses, and this makes co-ordination slower. Buses also tend to be bottlenecks, the classic example of this being the "von Neumann bottleneck". Ways to alleviate delays may involve deeper hierarchies (using caches and bridges), dedicated buses for high-volume traffic and separation of slow and fast devices. A more accurate bus diagram may look like this, for example:

However this is still a gross simplification. In reality, there are many more layers than this.

Memory can be simply split up into two forms, internal (registers, caches, main memory, etc) and external (hard disc drives, memory sticks, etc)... The focus in ICS is on internal.

Total storage space is typically expressed in bytes. The size of a byte was variable in earlier architectures, but now is standardised on 8 bits. An alternative way of expressing memory is using words. A word is a "natural" unit of memory, and is architecture specific. Typically, a word is the length required to represent a number or instruction (commonly 8, 16, 32 bits, etc). There are many exceptions to this though - variable/multiple word lengths, word lengths not in the form of 2ⁿ, etc...

Addressable units are the memory locations recognised. Each unit is a word length and the address range is built into the architecture. There are many exceptions, however, the most common being byte-level addressing within words. The number of addressable units is 2ⁿ where n is the number of address bits. 16 bit addressing can cope with 2¹⁶ units, or 65536. These are number from 0 to 65535, for example.

A unit of transfer is physically the number of data lines connected to memory. There are exceptions to this, for example partial words being read, etc...

External transfer units are called a block.

Different architectures have different methods. Older forms used external memory, which use sequential/direct access. Newer architectures tend to use random or associative access.

Stallings 6

Access time is dependent on architecture, hardware and organisation. ICS considers these for random access memory. The parameters used to measure performance are access time )or latency), memory cycle time and transfer rate.

Latency

Cycle Time

Transfer Rate

This needs to be stable and hold two clearly distinct values, such as semiconductor, magnetic media, optical discs, etc...

Memory Volatility

As you move down the hierarchy, you get a lower cost per bit, greater capacity, slower access and rarer use by the CPU.

More information on memory is available on the course web pages.

Errors can occur in the semi-conductor. Hard errors are permanent errors where a cell is always stuck at 0 or 1, or a random value. Soft errors are unintended events changing cell values, physical causes, power surges, alpha particles, etc.

Error detection works on the principle of storing two values, m - the data - and k, which is a function of m.

If m has M bits and k has K bits, then the stored word is M + K bits. When m is read, f(m) is calculated again, giving k', which is compared to the stored value of k.

If k' and k are the same, no error has been detected, however if they're different, two things can occur. m gets sent to the corrector and corrected, if it's correctable, and if not, an error is reported.

This gives three various levels of detection: no detection, uncorrectable detected error, or correctable detected error. However, this is not always accurate. An error could have gone undetected, or a corrected error may not still give the right value.

An early method of detection was parity, which was 1 bit long. If the stored number is even, parity is 0, otherwise if it's odd it's 1. If a double bit flip occurs, no error is detected, so it is limited. Also, it can not correct detected errors.

Hamming Error Detection

Stallings 4

Caching works on block of memory contents, rather than single words. For example, a 16-bit main memory address may identify a block of data (where a block is 4 words in this example). In this case, this make 0000₁₆ the start of the first block, 0004₁₆ the start of the second, etc... A word is then identified by its offset from the start.

Caching is used to improve memory performance (it was first introduced in 1968 on the IBM S/360-85) and has become a feature of all modern computing. Cache is typically the fastest memory available and behaves like a module in the CPU.

All information is still held in main memory. The cache holds copies of some memory blocks (recently accessed data). CPU reads are initiated as normal, the cache is checked for that word, and if it's not cached, the block is fetched into cache and the CPU gets served directly from cache.

Main memory consists of 2ⁿ words with unique addresses 0 to 2ⁿ - 1 assigned to blocks of K words. This makes 2ⁿ / K blocks. Cache consists of C lines of K words, where C holds a block. C <<< M.

There are many different ways of implementing cache. The most common is that all buses lead to cache and the CPU has no direct memory access (logically).

The cache needs to know which memory block contains which word. Two ways of accomplishing this is with direct mapping and associative mapping.

Direct Mapping

Associative Mapping

The ALU performs computation and the other CPU units exist to service the ALU. The ALU is made of simple digital hardware components. It stores bits and performs Boolean logic operations. All data comes to and from registers, input is from the control unit and outputs goes to registers, with status flags going to the control unit. As a module, the ALU may be made up of more modules (4 common ones are the status flag, the shifter, the complementer and the boolean logic unit).

Status Flag

Shift and Complement

There are also circuits for boolean logic and arithmetic, but the implementation details vary from architecture to architecture.

Registers

Instructions

Binary natural numbers aren't a problem for computers, however, integers are signed (can be positive or negative) and normally the msb represents the sign (-ve is binary 1 and +ve is binary 0). Therefore, a binary representation of an integer must contain the sign and the magnitude. The advantage to this method is that negation can happen due to a single bit flip, however, there are now two different representations of 0 and arithmetic must consider both sign and magnitude.

Another method of representing integers is the two's complement method. Here, a positive number has msb 0. In 4 bits, 1111 is the largest representable negative and 0111 is the largest representable positive. The range of representable numbers is -2n^-1 to 2^{n - 1} - 1. For 4 bits, this gives us +7 to -8. 0 is always positive. The main advantages to this method of representation is that there is a single representation of 0, and the arithmetic is simpler (for a computer).

Real numbers are identified by a 32-bit word. There is a 1 bit sign, 8 bit exponent and 23 bits for the significand. This is defined by the IEEE 754 floating point standard. IEEE 754 also defines the 1,11,52-bit standard for 64 bit systems and extended standards which can be used in the internals of a CPU only. The standard also gives standard meanings for extreme values, e.g., 0 is represented by all 0s, infinity is represented by all 1s in exponent and 0s in the significand, etc... A de-normalised number should have an all-0 exponent, whereas all 1s in the exponent and a non-0 significand represents 'NaN' - not a number.

Underflow (the numbers get too close to 0 - i.e., too precise for the 32-bit word to represent) and overflow (numbers get too large) occurs when the exponent can't represent all bits. 0 can not be represented as a floating point.

For integers, a normalised floating point 32-bit word can hold one of 2³² values. Some values are too precise to represent so they get rounded to the nearest one - in the case of underflow errors this is 0.

There is a trade off between precision and range by changing the number of exponent and significand bits.

Text is a thing that you don't do arithmetic on. It consists of printable characters (such as this text) and non-printing characters (newline, escape, bell, etc). Characters are coded in an order and this can be exploited for inequality and mathematical ordering ( 1 < A < a < } )

Computers store binary values, so text must be encoded. The most standard encoding (until recently) was ASCII, but others existed such as the International Reference Alphabet (IRA, IA5), EBCDIC, etc... These traditionally used 7-bits, but extended forms were available. Normally, a parity bit was added to pad it to 8 bits for storage.

International standards have taken longer to develop, and have only recently come to dominate. Most of these standards are derived from ASCII. The modern international standard is Unicode, which was developed by ISO. Unicode was originally 16-bit, but nowadays can be up to 32.

There are far too many to discuss in detail, but other items, such as images, sound, video, etc... needs to be represented also. These are traditionally done using large data structures with special handling procedures.

A = Operand. There is no separate memory reference and this can be used to set constants or initialise variables.

e.g., LOAD 11111001 . Loads a two's complement value in an 8-bit address field. When stored, it is padded to word or address size.

This mode is not very common due to capacity limitations

The operand holds the effective address. EA = A.

This means there is one memory reference per operand, however there is still limited address space and for this reason it is not used much.

Operand points to a memory location, which points to EA. EA = (A).

The operand is smaller than a memory word - but the possible addresses are still limited. The memory location is a full word, and any address is possible. This method of addressing is used in virtual memories.

The address directly refers to a CPU register.

The address is in a register, not main memory, otherwise it's the same as indirect.

This combines direct and register indirect.

EA = A + (R)

There are three common variants to this:

• relative addressing - program counter is the displacement
• base-register addressing - the register is implicit
• indexing - the reverse of base-register. This is fast for iteration.

Wikipedia

Reverse Polish Notation is useful when coding for a 1 operand instruction set. The format always gives correct precedence and it is most easily envisaged as a graph.