8. More on Sigma 16
Boolean Operations
• There are a number of general well-known operations on the Boolean data set {F, T} (equivalently {L,H} or {0,1}).
• We’ve already seen the NOT (INV) operation. This takes only 1 operand: it is what is called a unary operation.
• There are three important binary Boolean operations (with 2 operands). They are AND, OR and exclusive-OR. Each can be defined by a so-called truth table, as follows.
AND
F
T
F
F
F
T
F
T
OR
F
T
F
F
T
T
T
T
XOR
F
T
F
F
T
T
T
F
– In each table, the row is the first operand and the column the second.
– Note that all the operations are symmetrical (or commutative): e.g. x AND y = y AND x etc.
• In summary:
– AND is true if and only if both operands are true;
– OR is false if and only if both operands are false;
– XOR is true if and only if both operands are different.
• Note: There are no simple Sigma16 Boolean operations to operate directly on the Boolean values generated by the CMP instructions. But there are bitwise Boolean operations for use on any codewords (see next slide).
Systems and Networks 8. More on Sigma 16 2
Bitwise operations and masks
• A bitwise Boolean operation is applied separately to every bit of a binary codeword (NOT) or corresponding bits of two codewords words (AND, OR, XOR).
– E.g. Bitwise XOR of 8-bit words $A0 and $37
$A0 = 1010 0000
$37 = 0011 0111
Bitwise-XOR = 1001 0111
• Performing a bitwise AND of a given word with a carefully chosen second word is very useful if we want to isolate or extract a certain group of bits.
– Suppose we want a program to isolate the 4 most significant bits of a word such as $7D
– In binary this word is 0111 1101. If we bitwise-AND the word with $F0 = 1111 0000 (notice only the 4 bits we want to keep are set)
– Notice that ANDing any bit with 0 gives 0 and ANDing any bit with 1 leaves that bit unchanged.
– So, the result will be
$7D = 0111 1101
$F0 = 1111 0000
Bitwise-AND = 0111 0000
– The second word ($F0) is called a mask because it zeroes or masks (hides) the bits of no interest.
– This can be used to “extract” any group of bits from an existing word.
– Note that this can be done with a word from any code, if the need is there.
Systems and Networks 8. More on Sigma 16 3
Some other RRR instructions
• The Sigma16 instructions: shiftl Ra,Rb,Rc and shiftr Ra,Rb,Rc shift Rb left (or right) by Rc places, with the result Ra.
– In shiftl the result is formed by feeding new 0s in to the right and dropping all bits shifted out on the left.
– In shiftr the result is formed by feeding new 0s in to the left and dropping all bits shifted out on the right.
– If you shift by 16 or more places the result will always be 0
• Arithmetic instructions are code-specific
– MUL, DIV, CMPGT and CMPLT will only work correctly with two’s complement numbers.
– ADD and SUB will work with unsigned or two’s complement.
– CMPEQ will work with any codewords, including non-numeric ones.
• The DIV instruction is unique in producing two output values: a quotient and a remainder. The remainder always goes into R15, regardless of which registers are named in the instruction.
– So for DIV R1,R2,R3 the quotient of the division R2/R3 goes into R1, but the remainder goes into R15.
– This means that R15, like R0 has a special feature.
– WARNING: Bear in mind, if you ever use DIV, that R15 will be overwritten.
Systems and Networks 8. More on Sigma 16 4
Instruction and memory cycles
• The fetch and execution of a machine code instruction by a CPU is called an instruction cycle.
• The reading or writing of one word to one memory location (over the data bus) is a memory cycle.
• A memory cycle will take a fixed amount of time depending on the speed of the CPU and its memory.
– In general a memory cycle is much slower than a CPU internal operation like accessing a register.
• An instruction cycle may involve several memory cycles.
– To fetch a machine code word takes a memory cycle.
– To read or write a data word takes a memory cycle.
• In Sigma16, RRR instruction uses 1 memory cycle (to fetch the operation word).
– How many memory cycles does a LOAD take?
– How many memory cycles does a JUMP take?
Systems and Networks 8. More on Sigma 16 5
Hardware Registers for Instructions
• The computer needs information about the current and next instruction
• This information is maintained automatically by hardware, via several special registers associated with the Control Unit. All CPUs have
– The IR (Instruction Register) contains operation word of the instruction being executed
– The PC (Program Counter) contains address of the next instruction that will be executed.
• There are also machine specific control registers. E.g. in Sigma16:
– The Address Register (ADR) contains the target address specified in an RX or X instruction.
– The Data Register (DAT) holds temporary data
• The IR, ADR and DAT are not part of the programmer’s model since they do not carry information between instruction cycles.
– They are sometimes referred to as temporary registers.
– However, they are exposed in the Sigma16 emulator to help with debugging.
Systems and Networks 8. More on Sigma 16 6
Example: executing a JUMP
• When the Sigma16 instruction JUMP x[R1] is executed, the following events occur:
– First word of instruction is fetched, PC increased by 1 IR:=Memory[PC]; PC:=PC+1;
– CPU discovers this is a JUMP, and fetches second word.
ADR:= Memory[PC]; PC:=PC+1; (The result: ADR:= x)
– Effective address computation: ADR:= ADR+ R1;
– Execution of the instruction: PC:= ADR
• The next instruction will be fetched from the modified PC value: IR:= Memory[PC]
• Notice how instruction execution can be described by means of assignment statements to CPU registers.
• Summary: a JUMP is really just an assignment to the PC register. Systems and Networks 8. More on Sigma 16 7
Instruction types
• Different CPU designs have different approaches to machine code design.
• Examine a machine code (assembly) instruction from new CPU with these questions:
1. How many memory cycles are needed to fetch the whole instruction?
2. How many memory cycles are needed to fetch or store data?
3. How many independent memory locations can the instruction access?
• Memory cycles are relatively slow so multi-word instructions and instructions requiring many memory cycles for operands or results will take relatively longer.
• One could design a Sigma16-like machine with an instruction like – ADD x[R1],y[R2],z[R3].
• This is what is called a 3-address instruction, but:
– How long would such an instruction be?
– How many memory cycles would it need to fetch or store data?
– To perform this operation in Sigma16 how many instructions are needed?
– Which would be faster?
– Is this an argument against Sigma16?
Systems and Networks 8. More on Sigma 16 8
RISC and CISC
• Why not have instructions of multiple types in a CPU?
– Problem is that many complex instructions mean a long operation word and a complex control unit.
– Complex control unit with many instruction types is slower than a simple one with few types.
– Yet by the 1970s this was the way most CPUs were evolving.
• As a counter to this, in the 1980s to the idea of a reduced instruction set computer (RISC)
– eliminate complex instructions by preventing most instructions accessing memory.
– All memory access via LOAD and STORE instructions (c.f. Sigma16)
– Sometimes called a LOAD-STORE architecture.
– Use internal registers for all arithmetic and logical operations. Make these as fast as possible.
– Need lots of internal registers.
– Simple fast control unit
• Conventional machines with complex instructions were called CISC.
• CISC vs RISC was a matter of great contention in the 1980s and 1990s.
• Outcome was a compromise. Most successful architecture, Intel’s x86 (aka Pentium), started as CISC but was modified to include RISC ideas.
Systems and Networks 8. More on Sigma 16 9
•
Virtual Machines
A virtual machine (VM) is a software model of a machine that may or may not exist as hardware.
– VM itself is called the guest and the machine it runs on the host.
– Examples of virtual machines are Sigma16 and the Java Virtual Machine (JVM).
– In general use, software called a hypervisor is often run on the host to create and manage new guests that can be complete copies of real machines like PCs. Examples of hypervisors are: Microsoft Hyper V, Virtual Box, VMware, Parallels.
Machine code allows a machine to do anything:
– Without safeguards this can be very dangerous: code can hijack other code, crash a
computer, destroy data. Such behaviour may be accidental (bugs) or malicious (malware).
– An operating system will block an application program from doing something that looks dangerous but sometimes it is desirable to modify or disable parts of the OS which removes this protection. Also malware may try to circumvent any safety measures.
– If this happens on a host it can be very serious but on a VM problems can be confined to that VM. If the VM crashes, the host will be fine as will any hypervisor that may be present and a new instance of the VM can quickly be started.
– On a system like Sigma 16 programming is in machine code directly and there is no OS protection. Fortunately Sigma 16 is a VM: if it crashes the host is OK.
– VMs can be used to isolate activities that are best kept apart from others because they are either risky (e.g. code that may have malware) or sensitive (e.g. banking).
•
Systems and Networks 8. More on Sigma 16 10
Subroutines
• Often the same sequence of instructions comes up repeatedly in a program.
• A powerful technique provided by most instruction sets is to allow the programmer to write this sequence once, then allow the CPU to jump to the sequence in such a way that control can always be transferred back to the instruction after the one that jumped to it.
• A fundamental programming technique is to write this sequence, called a subroutine, one time somewhere out of main flow of instructions and give it a label (name).
• The mechanism that jumps to or calls the subroutine must somehow allow the program counter to be returned to the instruction after the call.
• To do this, address of this instruction, the return address, must be stored somewhere while the subroutine executes.
• This is a fundamental machine programming technique and is the basis of many HLL constructs including procedures, functions, methods, and coroutines.
Systems and Networks 8. More on Sigma 16 11
The Jumps Needed for Subroutines
• The subroutine can be called from several places! It must return to the instruction after the one that called it.
Ordinary
JUMP
instructions won’t work for this!!!
first call second call
instr instr call work instr instr call work instr
work instr instr instr instr
return
• a subroutine must return to different addresses at different times
• It needs to jump to a location that’s a variable, not a constant!
Systems and Networks 8. More on Sigma 16 12
Calls and returns in Sigma16
• The S16 instruction set provides the JAL (Jump and Link) instruction to call subroutines
JAL Rf,work[R0]
• Here JAL
– Stores the return address in Rf
– Jumps to work.
• At the end of the subroutine a return is executed simply by executing
JUMP 0[Rf]
• This JUMP will go to a different destination depending on content of Rf.
• 0[Rf] is an example of a variable address.
Systems and Networks 8. More on Sigma 16 13
Subroutines and stacks
• A JAL instruction saves return address for subroutine call in an internal reg.
• But one subroutine can call another and so on (nested calls). When there are many calls, the register file may not have space for all return addresses.
• Instead return addresses are usually stored in a data structure called a stack
– Stack is setup and maintained by the programmer
– Unlike an array a stack can grow and shrink.
– First address is called the stack bottom and the last one is the stack top.
– In Sigma 16 the stack bottom is set by the programmer via a DATA statement. It must be placed after all other DATA statements as the stack can grow upwards and overwrite anything above it.
– The stack top is tracked by a register, the stack pointer (SP), which contains its current address. In Sigma 16 programmer uses one of the R registers to do this.
– Initially the stack top and bottom are the same so SP is set to the address of stack bottom. At this point the stack is empty.
Stack after 3 nested subroutine calls…
SP
Stack bottom
Ret addr1
Ret addr 2
Ret addr 3
And after first subroutine returns…
Ret addr1
Ret addr 2
– After subroutine call, store return address on stack & increment SP.
– After a return the address at the stack top is retrieved and the SP is decremented
Stack bottom
SP
Systems and Networks 8. More on Sigma 16
14
More on Stacks
• A stack is a last in first out (LIFO) data structure.
• Storing an item at the stack top is called a PUSH operation (e.g. save return address)
• Retrieving an item from the stack top is called a POP or PULL operation (e.g. retrieve return address)
• The item popped is always the last one pushed.
• Stack can be used to push and pop items other than return addresses but must be done with
care by any program doing so.
• In Sigma 16 the stack is programmer-maintained and grows upwards.
• Many CPUs help maintain the stack by providing e.g.
– A dedicated register for the SP which auto-increments/decrements when subroutine calls are made
– Special PUSH and POP instructions for manually storing and retrieving data items on the stack
• Note that in many CPU designs the stack grows downwards in memory so the stack top is at a lower address than the stack bottom.
• Programmer is responsible for making sure maximum stack size does not overwrite other data or code or try to use unpopulated addresses. Failure is stack overflow.
Systems and Networks 8. More on Sigma 16 15