CPU architecture, assembly language and bit manipulation

The von Neumann model and the stored program concept

Almost every computer you will use is built on the von Neumann model, set out by John von Neumann in 1945. In this model the computer has three main parts: a central processing unit (CPU), main memory, and input and output devices. The CPU itself contains three things: the arithmetic and logic unit (ALU), the control unit (CU) and a set of registers. Everything the computer does is done by moving values between these parts and changing them in the ALU.

The idea that makes the model work is the stored program concept: the instructions of a program and the data it works on are held in the same main memory, in the same binary form, and are fetched one at a time and executed in sequence. Because an instruction is just a pattern of bits in memory, the machine does not have to be rebuilt for a new job - you load a different program and it does a different job. The CPU cannot tell an instruction from a data value by looking at it; it treats a value as an instruction only because the program counter pointed at it during a fetch.

The immediate access store (IAS) is the part of the computer that holds the programs and data currently in use. It is directly accessible by the CPU without any slow transfer from backing store, which is why it is measured in gigabytes and why its contents are lost when the power is switched off. The ALU carries out all the arithmetic (add, subtract, increment, decrement) and all the logical operations (AND, OR, XOR, shifts, comparisons). The control unit directs and coordinates everything: it decodes each instruction, then sends control signals along the control bus to the other components so that the right data is moved at the right time. The system clock produces a continuous series of pulses that synchronise every operation; each stage of the fetch-execute cycle takes a whole number of clock cycles, and the clock speed in gigahertz tells you how many cycles happen each second.

Registers: general purpose and special purpose

A register is a small, very fast storage location inside the CPU, built from flip-flops and holding a fixed number of bits, usually the word length of the processor. Registers are far faster than main memory, which is exactly why the values being used at that instant are held in them rather than being fetched from memory every time they are needed.

The difference the syllabus asks for is between general purpose and special purpose registers. A general purpose register holds data or an address while the processor is working on it, and it can be used for any purpose the programmer chooses. A special purpose register has one fixed job given to it by the design of the processor, and you cannot use it for anything else. The syllabus names seven special purpose registers: the program counter (PC), the memory data register (MDR), the memory address register (MAR), the accumulator (ACC), the index register (IX), the current instruction register (CIR) and the status register. In the assembly language of section 4.2 you are told to assume that only one general purpose register is available, the accumulator.

The program counter holds the address of the next instruction to be fetched. During the fetch stage it is incremented so that it always points at the following instruction, and an instruction that jumps (such as JMP) works by loading a new value into it. The memory address register holds the address of the memory location that is about to be read from or written to, and it is connected directly to the address bus. The memory data register holds the data or instruction that has just been read from that location, or the data that is about to be written there, and it is connected directly to the data bus. Since main memory is separate from the CPU, every item that goes in or out passes through the MDR.

The current instruction register holds the instruction that is currently being decoded and executed, split into its opcode (what to do) and its operand (what to do it to). The accumulator holds the data being processed and the result of the operation, so in this instruction set the answer always ends up in the ACC. The index register holds a number used in indexed addressing, where it is added to the operand to form the address to be used. The status register holds the flags set by the last operation in the ALU - for example whether the result was zero, whether it was negative, whether it carried out of the top bit, or whether it overflowed - and those flags are what conditional instructions test.

The three buses and the fetch-execute cycle

A bus is a set of parallel wires that carries signals between the components of a computer. There are three, and they all connect the CPU to main memory and to the input and output devices. The address bus is unidirectional - the address travels from the CPU out to memory and never the other way - and it carries the address of the location that is being read or written. Its width sets the maximum amount of memory that can be addressed: n address lines give 2^n locations, so 32 lines allow 4 GiB of memory. The data bus is bidirectional and carries the data and the instructions themselves; its width decides how many bits move in one transfer. The control bus carries the individual control signals, such as memory read, memory write, the clock pulses, an interrupt request from a device and a reset signal.

The fetch-execute cycle is the sequence the CPU repeats for every instruction. It has two main stages, fetch and execute, with a decode step in between; some descriptions add a store or write-back stage when a value is written to memory. Examiners ask for the fetch stage in register transfer notation, where square brackets mean 'the contents of' and a statement is read left to right as 'this receives that'.

The fetch stage in register transfer notation is short enough to learn by heart. The address in the program counter is copied to the memory address register, the program counter is incremented so that it points to the next instruction, the instruction is read from memory into the memory data register, and it is then copied into the current instruction register: MAR <- [PC], then PC <- [PC] + 1, then MDR <- [[MAR]], then CIR <- [MDR]. The double brackets mean 'the contents of the location whose address is in the MAR'.

In the decode step the control unit splits the instruction in the CIR into opcode and operand and works out what has to be done. In the execute step the work depends on the instruction: for LDD 200 the address in the operand is copied to the MAR, the data is read into the MDR, and then copied to the ACC; for STO 300 the ACC is copied into the MDR and written to the address in the MAR; for ADD #5 the ALU adds 5 to the ACC; for JMP 40 the value 40 is copied into the PC, which is why the next fetch takes the instruction from a different place.

Interrupts: causes, applications and handling

An interrupt is a signal sent to the processor, from hardware or from software, that tells it something needs attention. The processor suspends the program it is running, saves where it had got to, runs a short routine to deal with whatever caused the interrupt, and then carries on as if nothing had happened. Without interrupts the processor would either have to stop and check every device constantly (polling) or ignore the devices until the program finished.

The causes are best grouped as hardware and software. Hardware causes include a key being pressed or a mouse being clicked, a printer running out of paper or its buffer becoming full, a transfer to or from a disk finishing, a pulse from the system clock (the timer interrupt that lets an operating system share the processor between programs), a power failure and a hardware fault. Software causes include a program attempting to divide by zero, an attempt to execute an instruction that does not exist, and a program asking the operating system to do something for it.

The applications follow from those causes. Interrupts let the processor respond to input immediately without wasting time checking devices. They make multitasking possible, because the timer interrupt takes control away from one program and gives it to the next. They allow real-time systems, such as a car's engine management or a hospital monitor, to react within a guaranteed time. They also let errors and hardware failures be handled by the operating system instead of crashing the program that happened to be running.

An interrupt is detected at the end of the execute stage of the fetch-execute cycle, before the next instruction is fetched - never in the middle of an instruction. When one is detected, the processor finishes the instruction it is on, saves the contents of its registers including the PC on the stack, checks the priority of the interrupt (a higher-priority interrupt can interrupt the routine already running), loads the start address of the interrupt service routine (ISR) into the PC, and executes it. The ISR is the short routine written to service that particular device or event. When it finishes, the saved register values and the PC are restored from the stack, so the interrupted program continues from exactly where it stopped.

Factors affecting performance, and ports for peripherals

Clock speed is the number of cycles the system clock produces each second, measured in gigahertz. Every stage of the fetch-execute cycle takes a number of cycles, so a higher clock speed means more cycles per second and therefore more instructions completed per second. The gain is not unlimited: a faster processor still has to wait for slower main memory, and different instructions take different numbers of cycles.

The number of cores matters because each core is effectively a complete processor with its own control unit, ALU and registers. Two cores can be executing two different sets of instructions at the same time, so a program that can be split into parallel threads will finish sooner. The gain depends on the software - a program written as a single sequence of instructions uses one core however many are available - and more cores mean more heat, more power and more competition for the memory and the buses. The processor type covers the rest of the design: the word length it works with, the instruction set, and the size of its caches.

Bus width sets how much can move at once. A wider data bus carries more bits in each transfer, so fewer transfers are needed to move a block of data. A wider address bus means more address lines, and since n lines address 2^n locations, it allows more memory to be fitted. Cache memory is a small amount of very fast memory on or next to the CPU that holds recently used and frequently used instructions and data. Before going to main memory the processor checks the cache; if the value is there - a cache hit - it is obtained far more quickly than a fetch from RAM. Cache is expensive, so it is small compared with main memory, and it is usually organised in levels, with level 1 the smallest and fastest.

• USB (universal serial bus): a general purpose serial port that connects keyboards, mice, printers, cameras and storage devices, is plug and play, can supply power to the device, and can connect several devices through a hub.
• HDMI (high definition multimedia interface): carries high definition digital video and audio to a monitor, projector or television through a single cable.
• VGA (video graphics array): an older port that carries analogue video only, with no audio, to a monitor or projector; it is gradually being replaced by digital connections such as HDMI.
• All three are ports: they provide the physical connection and the agreed set of rules by which a peripheral device exchanges data with the computer.

Assembly language, machine code and the two-pass assembler

Machine code is the set of binary patterns that the processor can execute directly: an opcode that says what to do and an operand that says what to do it to. Assembly language is a low-level language in which each of those instructions is written with a mnemonic (such as LDD or JMP) instead of a binary opcode, and with a symbolic address (such as total) instead of a number. There is essentially a one-to-one relationship between the two: one assembly language instruction is translated into one machine code instruction, which is what makes assembly language different from a high-level language. Because the mnemonics and the instruction set belong to one family of processors, assembly language is machine dependent - a program written for one processor will not run on another without being rewritten - and it must be translated by an assembler before the computer can run it.

The assembler reads the source program twice, which is why it is called a two-pass assembler. The reason is the forward reference: a program frequently jumps to a label that is defined further down the listing, and when the assembler reaches the jump it has not yet met the label and does not know its address. Reading the program twice solves this - the first pass finds out where everything is, and the second pass fills the addresses in.

In pass 1 the assembler sets a location counter to the address where the object code will start, then reads the source line by line. Comments are ignored. Each time it meets a label it adds the label and the current value of the location counter to the symbol table, and it reports an error if a label is defined twice. It then adds the length of the instruction or data item to the location counter and moves on. Data lines, which give a symbolic address to a location holding a constant, are recorded in the same way. Pass 1 produces no machine code at all - its only output is the symbol table.

In pass 2 the assembler reads the source again. For each instruction it looks the mnemonic up in the opcode table to get the binary opcode, takes the operand, and if the operand is a label it looks the label up in the symbol table and substitutes the absolute address it finds there. It then assembles the complete binary instruction and writes it out. Data lines are turned into the binary value they define, and an operand that is not in the symbol table is reported as an undefined label. The output of pass 2 is the object code, which can be loaded and run.

Instruction groups and addressing modes

The instruction set you are given is small, and every question uses it, so learn it as groups rather than as a list. Data movement instructions move values between memory, the accumulator and the index register: LDM, LDD, LDI, LDX, LDR and MOV load, and STO stores. Input and output instructions are IN, which reads a character from the keyboard and stores its ASCII value in the ACC, and OUT, which displays the character whose ASCII value is in the ACC. Arithmetic instructions are ADD, SUB, INC and DEC. On top of those there are the unconditional jump JMP, the conditional jumps JPE and JPN, and the compare instructions CMP and CMI, which set the flags that the conditional jumps test.

The operand is written in a way that tells you what kind of value it is: a # means a denary number, so ADD #12 adds twelve; a B means binary, so AND B00101000 uses that bit pattern; a &amp; means hexadecimal, so LDM &amp;4A loads the value 74. An operand in angle brackets is an address, and it can be written as an absolute address such as 200 or as a symbolic address such as total, which the assembler replaces with a number.

The addressing mode is the rule for working out where the operand comes from, and it is the part of this section that loses the most marks. In immediate addressing the operand is the value: LDM #5 puts 5 in the accumulator. In direct addressing the operand is the address of the location holding the value: LDD 200 reads the contents of address 200. In indirect addressing the operand is the address of a location that itself holds the address to use: LDI 300 looks in address 300, finds an address there, and reads the contents of that second address. In indexed addressing the operand is added to the contents of the index register to form the address: LDX 200 with IX holding 4 reads address 204. In relative addressing the operand is an offset from the address of the current instruction, which the processor adds to the program counter, so the code can be moved in memory without changing the instruction.

• Data movement: LDM #n, LDD address, LDI address, LDX address, LDR #n, MOV register, STO address.
• Input and output: IN reads a character and stores its ASCII value in ACC; OUT displays the character whose ASCII value is in ACC - so OUT prints characters, not the number itself.
• Arithmetic: ADD address or ADD #n, SUB address or SUB #n, INC register, DEC register.
• Unconditional jump: JMP address - always goes there.
• Conditional jumps: JPE address jumps if the preceding compare was true (equal), JPN address jumps if it was false (not equal).
• Compare: CMP address, CMP #n and CMI address compare the ACC with a value and set the flags; they do not change the ACC.
• Only the accumulator and the index register can be named directly, so almost every instruction involves the ACC.

Tracing a simple assembly language program

A trace question gives you a program and asks for the contents of the registers and named memory locations after each instruction, or after the program has finished. The method is always the same: draw a table with a column for the ACC, a column for the IX, and a column for every memory location the program writes to. Work down the program one instruction per row, and after each one ask yourself what actually changed - INC IX, for example, changes only the index register, not the accumulator.

Here is a program that adds three numbers stored at addresses 200, 201 and 202 and stores the total in a memory location named total. The two symbolic addresses, total and count, are given absolute addresses by the assembler, and both locations have to be set to zero before the loop starts.

The loop works like this. LDX 200 uses indexed addressing, so on the first pass it reads address 200, on the second pass 201 (because IX has been incremented) and on the third 202. The value read is added to whatever is already in total and stored back. The IX is then incremented, and a separate counter in memory is incremented and compared with 3 - as soon as the count reaches 3 the compare is true, JPN does not jump, and the program falls through to load the total into the ACC and stop.

• LDM #0 - put 0 in the ACC
• STO total - total = 0
• STO count - count = 0
• LDR #0 - put 0 in the IX
• loop: LDX 200 - ACC = contents of (200 + IX)
• ADD total - ACC = ACC + total
• STO total - total = ACC
• INC IX - IX = IX + 1
• LDD count - ACC = count
• INC ACC - ACC = ACC + 1
• STO count - count = ACC
• CMP #3 - compare the count with 3
• JPN loop - jump back if the compare was false
• LDD total - ACC = the total
• END - return control to the operating system

Bit manipulation: shifts and masking to test and set bits

A shift moves every bit in a register a given number of places to the left or the right. A logical shift moves the bits and fills the empty positions at the end it has moved away from with zeros; any bit shifted off the other end is lost. LSL #n shifts logically left, so zeros come in on the right, and LSR #n shifts logically right, so zeros come in on the left. Because each place is worth a power of two, a logical left shift multiplies the value by 2 for each place and a logical right shift divides by 2 for each place, throwing away the remainder: B00001010 (10) becomes B00010100 (20) after LSL #1, and B00000101 (5) after LSR #1.

An arithmetic shift is used for numbers held in two's complement, where the leftmost bit is the sign. An arithmetic right shift copies the sign bit into the positions vacated on the left, so the sign of the number is preserved while it is halved: B10010110, which is negative, still begins with 1s after the shift. An arithmetic left shift puts zeros on the right, exactly like a logical left shift, but the bit shifted out of the left-hand end is not just lost - if it was not the same as the new sign bit, the number has overflowed and the result is wrong.

A cyclic shift, also called a rotation, moves the bits that leave at one end back into the empty positions at the other end, so no bit is ever lost. A cyclic left shift moves the top bit round to the bottom, and a cyclic right shift moves the bottom bit round to the top. This matters when every bit carries information that must be preserved, as in serial data transmission and in some encryption and hashing techniques, where losing a bit would corrupt the whole pattern.

A bit mask is a bit pattern used with a logical operation to work on particular bits of a value while leaving the rest untouched. The three logical instructions do three different jobs, and mixing them up is the classic mistake. AND is used to test bits and to clear them, because AND with a 1 keeps a bit and AND with a 0 forces it to 0. OR is used to set bits, because OR with a 1 forces a bit to 1 and OR with a 0 leaves it alone. XOR is used to invert or toggle bits, because XOR with a 1 flips a bit and XOR with a 0 leaves it alone; XOR also gives zero when two patterns are identical, which makes it useful for testing whether a value has changed.

The reason this matters is that a single byte read from or written to a device usually carries several pieces of information at once. A status byte might use bit 0 to report that a door is open, bit 1 for a temperature alarm and bit 2 for a pressure fault; an output byte might use each bit to switch one device on or off. To find out about one sensor you must isolate its bit, and to switch one device you must change its bit without disturbing the others. That is exactly what a mask allows.

To test a bit, AND the value with a mask that has a 1 only in the position you are interested in. Every other bit becomes 0, so the result is either zero (the bit was 0) or the mask itself (the bit was 1). Compare the result with 0 and branch on the answer: JPE jumps when the compare was true, that is when the result was 0, and JPN jumps when it was false, that is when the bit was set. To set a bit, OR the value with a mask that has a 1 only in that position. To clear a bit, AND it with a mask that has a 0 only in that position and 1s everywhere else. To toggle a bit, XOR it with a mask that has a 1 only in that position.

• Test bit 2 of the status byte at address 500: LDD 500 then AND #B00000100 then CMP #0, then JPE if the bit was clear and JPN if it was set.
• Set bit 0 of the output byte, leaving the other seven bits alone: OR #B00000001.
• Clear bit 3, leaving the other seven bits alone: AND #B11110111.
• Toggle bit 5: XOR #B00100000.
• Mask for bit n is 2^n written in binary: bit 0 is B00000001, bit 1 is B00000010, bit 2 is B00000100, bit 3 is B00001000.
• The masking instruction is nearly always followed by CMP #0 when the purpose is to test a bit, because AND on its own does not change the flags in a useful way.