Lecture 17 Todays Lecture Instruction formats Little versus big endian Internal storage in the CPU: stacks vs. registers Number of operands and instruction length Expanding opcodes 1 Instruction sets Instruction sets are differentiated by the following:

Number of bits per instruction. Instruction length: 16, 32 and 64 bits are the most common. Stack-based or register-based. Operand storage: register or stack? Number of explicit operands per instruction. Zero, one, two, and three are the most common. Operand location. Combinations of operands allowed per instruction: register-to-regis ter, register-to-memory, or memory-to-memory? Types of operations Arithmetic, data transfer, floating pointing operation, logic operation, etc. Type and size of operands.

Operands can be addresses, numbers, or characters. 2 Byte Ordering Little endian machines store the most significant byte at the least significant byte. Big endian machines store the most significant byte fir st (at the lower address). As an example, suppose we have the hexadecimal nu mber 0x12345678. 3 Instruction Formats Exercise A larger example: A computer uses 32-bit integers. The values 0xA BCD1234, 0x00FE4321, and 0x10 would be stored sequentially in memory, starting at address 0x200 as below.

4 Internal Storage in CPU Stack architecture A stack is used to execute instructions, and the operands ar e found on top of the stack. A stack can not be access randomly. A stack is a bottleneck during execution. Accumulator architecture

One operand implicitly in the accumulator One operand is in memory, creating lots of bus traffic. General purpose register (GPR) architecture Faster than accumulator architecture. Results in longer instructions. 5 General Purpose Architecture Most systems today are GPR systems. There are three types depending on where the operands a re located. Memory-memory where two or three operands may be in memory.

Register-memory where at least one operand must be in a registe r. Load-store architectures require data to be moved into registers be fore any operations on these data are performed. Most architectures today. SPARC, MIPS, Alpha, PowerPC The number of operands and the number of available regis ters has a direct affect on instruction length. 6 Number of Operands & Instruction Length Instruction length Fixed length: waste space but is fast and results in better performan ce when instruction-level pipelining is used. Variable length: more complex to decode but saves storage space.

Number of operands: most common instruction formats incl ude zero, one, two, or three operands. Zero: OPCODE only One: OPCODE + 1 address (usually a memory address) Two: OPCODE + 2 addresses (usually registers, or one register and one memory address) Three: OPCODE+3 addresses (usually registers, or combinations of registers and memory) Note: all architectures have a limit on the maximum number of operands allowed per instruction. 7 Number of Operands & Instruction Length More on stack-based architectures: Most instructions consist of opcodes only Some special instructions have one or two operand.

LOAD and STORE instructions require a single memory a ddress operand. PUSH and POP operations involve only the stacks top el ement. Push X: place the data value found at memory location X onto the stack. Pop X: removes the top element in the stack and stores it at location X. Binary instructions (e.g., ADD, MULT) use the top two ite ms on the stack. ADD: the CPU adds the top two elements of the stack, popping them bot h and then pushing the sum onto the top of the stack. 8 Stack Arithmetic Expression Infix notation, such as: Z = X + Y. Stack arithmetic uses postfix notation: Z = XY+.

This is also called reverse Polish notation, in honor of its Polish inventor, Jan Lukasiewicz (1878 - 1956). The principal advantage of postfix notation is that paren theses are not used. For example, the infix expression, Z = (X Y) + (W U), becomes: Z = X Y W U + in postfix notation. 9

Infix & Postfix Expressions Exercise 1 Convert the infix expression (2+3) - 6/3 to postfix: 2 3+ - 6/3 The sum 2 + 3 in parentheses takes precedence; we replace the term with 2 3 +. 2 3+ - 6 3 / The division operator takes next precedence; we replace 6/3 with 6 3 /. 2 3+ 6 3 / - The quotient 6/3 is subtracted from the sum of 2 + 3, so we move the - operator to the end. 10

Infix & Postfix Expressions Exercise 2 Example: Use a stack to evaluate the postfix expre ssion 2 3 + 6 3 / - : Scanning the expression from left to right, push operands onto the stack, until an operator is found 2 3 + 6 3 3 2 / Stack top 11

Infix & Postfix Expressions Exercise 2 Example: Use a stack to evaluate the postfix expre ssion 2 3 + 6 3 / - : Pop the two operands and carry out the operation indicated by the operator. Push the result back on the stack. 2 3 + 6 3 3 2 5

/ - Stack top 12 Infix & Postfix Expressions Exercise 2 Example: Use a stack to evaluate the postfix expre ssion 2 3 + 6 3 / - : Push operands until another operator is found. 2 3 + 6 3 3

/ - Stack top 6 5 13 Infix & Postfix Expressions Exercise 2 Example: Use a stack to evaluate the postfix expre ssion 2 3 + 6 3 / - : Carry out the operation and push the result. 3 6

5 2 3 + 6 3 2 5 / - Stack top 14 Infix & Postfix Expressions Exercise 2 Example: Use a stack to evaluate the postfix expre ssion 2 3 + 6 3 / - :

Finding another operator, carry out the operation and push the result. The answer is at the top of the stack. 2 3 + 6 3 2 5 3 / - Stack top

15 Infix & Postfix Expressions Exercise 3 Let's see how to evaluate an infix expression using diff erent instruction formats. With three-address instructions, the infix expression, Z = X Y + W U might look like this: MULT R1,X,Y MULT R2,W,U ADD Z,R1,R2 16 Infix & Postfix Expressions Exercise 3 With two-address instructions, the infix expressi

on, Z = X Y + W U might look like this: LOAD R1,X MULT R1,Y LOAD R2,W MULT R2,U ADD R1,R2 STORE Z,R1 17 Infix & Postfix Expressions Exercise 3 With one-address instructions (as in MARIE), th e infix expression,

Z = X Y + W U looks like this: LOAD X MULT Y STORE TEMP LOAD W MULT U ADD TEMP STORE Z Note: Must assume that a register is implied as the destination for the result of the instruction. 18 Infix & Postfix Expressions Exercise 3 In a stack ISA (no operand), the postfix expression, Z = X Y W U +

might look like this: PUSH PUSH MULT PUSH PUSH MULT ADD PUSH X Y W U Z Would this program require more execution time than the

corresponding (shorter) program that we saw in the 319 address ISA? # of Operands and # of Instructions The number of instructions required to execute the desired code in this example Thee-address operands: 3 instructions Two-address operands: 6 instructions One-address operands: 7 instructions Zero-address operand: 8 instructions Reduce the number of operands allowed per instru

ction, the number of instructions required to execut e the desired code increase. 20 Expanding Opcodes In any instruction set, not all instructions require the s ame number of operands. Operations that require no operands, such as HALT, n ecessarily waste some space when fixed-length instru ctions are used. One way to recover some of this space is to use expa nding opcodes. 21 Expanding Opcodes A system has 16 registers and 4K of memory.

We need 4 bits to access one of the registers. We als o need 12 bits for a memory address. If the system is to have 16-bit instructions, we have t wo choices for our instructions: 22 Expanding Opcodes & Escape Opcodes If the length of the opcode is allowed to vary, we could create a very rich instruction set. How to determine when the instruction should be interpreted as having a 4-bit, 8-bit, 12-bit or 16-bit opcode? Escape opcode to indicate which format should be use. Suppose we wish to encode the following instructions:

15 instructions with three addresses 14 instructions with two addresses 31 instructions with one addresses 16 instructions with zero addresses 23 Expanding Opcodes & Escape Opcodes 24 Expanding Opcodes & Escape Opcodes If ( leftmost four bits != 1111 ) { Execute appropriate three-address instruction } else if ( leftmost seven bits != 1111 111 ) {

Execute appropriate two-address instruction } else if ( leftmost twelve bits != 1111 1111 1111 ) { Execute appropriate one-address instruction } else { Execute appropriate zero-address instruction } 25 Expanding Opcodes & Escape Opcodes Question: how do we know if the instruction set we want is p ossible when using expanding opcode? Determine if we have enough bits to create the desired n umber of bit patterns. Once we determine it is possible, we can create the appr opriate escape opcodes for the instruction set.

26 Expanding Opcodes & Escape Opcode s Example 1 12-bit instruction and 3-bit register operand 4 instructions with three registers: 255 instructions with one register: 16 instructions with zero registers: 16 bit patterns In total: 2048 + 2040 + 16 = 4194 > An expanding opcode instruction set can be designed to meet th

e specified requirement. 27 Expanding Opcodes & Escape Op codes Example 2 Example: Given 8-bit instructions, is it possible to allo w the following to be encoded? 3 instructions with two 3-bit operands. 2 instructions with one 4-bit operand. 4 instructions with one 3-bit operand. We need: = 192 bit patterns for the 3-bit operands = 32 bit patterns for the 4-bit operands = 32 bit patterns for the 3-bit operands.

Total: 256 bits = bits. We have an exact match . 28 Expanding Opcodes & Escape O pcodes Example 2 29