CMPT 295 – Spring 2021 Assignment 7 Objectives: Designing and evaluating instruction sets (ISA) Submission: Submit your document called Assignment_7.pdf, which must include your answers to all of the questions in Assignment 7. o Add your full name and student number at the top of the first page of your document Assignment_7.pdf. Submit your assignment Assignment_7.pdf on CourSys. Due: Thursday, March 25 at 3pm. Late assignments will receive a grade of 0, but they will be marked in order to provide feedback to the student. Marking scheme: The marks assigned to each question is indicated in [ ]. This assignment will be marked for correctness. A solution will be posted after the due date. Note 1: Clarifying Memory Model. If any of these terms are unclear to you: o memory model o memory size o address resolution and o word size please, before starting this assignment and as part of your study, read the document found at this link: CMPT 295 – Spring 2021 https://www2.cs.sfu.ca/CourseCentral/295/alavergn/Lectures/Clarifying_Memory_Mod el.pdf This document has also been posted below our Assignment 7. Note 2: In our lectures, we designed and evaluated the instruction set called x295M. In this assignment, we shall design and evaluate three (3) other instruction sets: x295, x295+ and x295++. Be aware: All of these 4 instruction sets are different! Instruction Set 1 – x295 A. Description of x295 instruction set architecture (ISA) Data size : 16 bits Memory model o Size of memory: 212 × 16 m = 12 -> this means that each memory address has 12 bits. n = 16 -> this means that the address resolution, i.e., the smallest addressable memory “chunk”, is a memory “chunk” of 16 bits. Each memory “chunk” of 16 bits has a distinct memory address. This is not a byte-addressable computer o Word size: 16 bits -> this means that when the microprocessor reads from/writes to memory, it reads/writes 16 bits at a time. It is a coincidence that the address resolution and the word size have the same bit value. These two are independent from each other. o Number of registers: 0 Instruction set (assembly and machine instructions) o Maximum number of instructions: 16 This means that we need a maximum of 4 bits to distinctly represent each of these 16 instructions. Therefore, the size of the opcode field, in the machine instructions, will be 4 bits (24 = 16) o Operand Model: CMPT 295 – Spring 2021 Memory (only) – only memory locations are operands, no registers are used as operands except the register representing the stack pointer 3-operand model In the machine instructions, the order of these operands is: Dest, Src1, Src2 o Memory addressing mode: Direct, Base and Displacement and Indirect These may not all be used in the instructions found in this assignment. o Assembly instructions (defined so far) and their format and meaning: ADD a,b,c Meaning: M[c] <- M[a] + M[b] SUB a,b,c Meaning: M[c] <- M[a] - M[b] MUL a,b,c Meaning: M[c] <- M[a] * M[b] In these assembly instructions, the order of the operands is: Src1, Src2, Dest. o Machine code format: 4 bits 4 bits 4 bits This format is made of 3 words, each word is 16 bits in length (word size). This format must be used to form all three machine instructions corresponding to the three assembly instructions listed above. The bit patterns for the opcode are: Opcode (instruction) Bit pattern (4 bits) padding 0000 ADD 0001 SUB 0010 MUL 0011 … … B. Evaluation of x295 instruction set C program x295 assembly program x295 machine code z = (x + y) * (x – y); ADD x, y, tmp1 SUB x, y, tmp2 0001 0000 0000 0010 0000 opcode Dest (12 bits) padding padding Src1 (12 bits) Src2 (12 bits) CMPT 295 – Spring 2021 MUL tmp1, tmp2, z (where tmp1 and tmp2 are memory addresses holding temporary results) 0000 0011 0000 0000 Note: In the above machine code, we will not be using actual memory addresses in the memory address fields (fields in purple). 1. The first step in evaluating our x295 instruction set is to write an assembly program using the assembly instructions defined by our x295 instruction set. This step has been done for us and is displayed in the table above in column “x295 assembly program”. Note that as we are performing this step, we are verifying that our x295 instruction set contains sufficient instructions to allow us to write such program in x295 assembly code. (Nothing for us to do in this part of our x295 instruction set evaluation.) Once we have our x295 assembly program, we need to transform it into its x295 machine code equivalent. This step has been done for us and is displayed in the table above in column “x295 machine code”. Note that as we are performing this step, we are verifying that our x295 instruction set contains sufficient instructions to allow us to write such program in x295 machine code. (Again, nothing for us to do in this part of our x295 instruction set evaluation.) 2. The next step is evaluating our x295 instruction set is to execute (hand trace) our assembly program or its corresponding machine code and using the metric (criteria) called memory traffic, we count the number of memory accesses our program makes during its execution. In other words, we count how many time the execution of our program required a word (16 bits) to be read from or written to memory. Note that as we are performing this step, we are verifying that the meaning of the instructions contained in our x295 instruction set is such that hand tracing these instructions does indeed produce the result the software developer that wrote the above C program expected. This is to say that if we use the test case: x = 3, y = 2 when hand tracing our x295 assembly code (or its machine code equivalent), we would obtain the same (expected) result as if we were to hand trace the C program itself. As part of this step in the evaluation of our x295 instruction set, we are asked to evaluate the number of word size memory accesses made by the microprocessor when it is CMPT 295 – Spring 2021 fetching and executing each assembly code statement (or machine code statement) listed in the left column in the table below. Also we need to justify our count. Finally, let’s total our counts. [2 marks] x295 program (in assembly and machine code) Fetch (number of word size memory accesses) + Provide an explanation explaning the count Execute (number of word size memory accesses) + Provide an explanation explaning the count ADD x, y, tmp1 0001 0000 0000 Count: Explanation: Count: Explanation: SUB x, y, tmp2 0010 0000 0000 Count: Explanation: Count: Explanation: MUL tmp1, tmp2, z 0011 0000 0000 Count: Explanation: Count: Explanation: Grand Total: Total: Total: CMPT 295 – Spring 2021 3. We also evaluate our instruction set using the metric (criteria) called static code size: o The code size of our x295 program is 3 instructions. o And since each instruction is 3 word long, the code size of our x295 program is 9 words. (Nothing for us to do in this part of our x295 instruction set evaluation.) Instruction Set 2 – x295+ A. Description of x295+ instruction set architecture (ISA) Considering the results of our x295 instruction set evaluation, one possible improvement in order to reduce the number of memory accesses could be to reduce the size of the machine instructions. Since these are made of an opcode and a memory address, we could introduce registers which could hold these memory addresses and take less space (less number of bits) to identify in the machine code than to identify the memory addresses. With the idea of introducing registers, we specified a second instruction set architecture (ISA) with the same components as x295, but with the following modifications: Memory model o Number of registers: 8 x 16-bit registers This means that we need a maximum of 3 bits to distinctly represent each of these 8 (23) registers. Therefore, the size of any register field, in the machine instructions, will be 3 bits in length. Each register contains 16 bits. o The bit patterns for the registers are: Register Bit pattern (3 bits) r0 000 r1 001 r2 010 r3 011 r4 100 r5 101 r6 110 r7 111 CMPT 295 – Spring 2021 Instruction set (assembly and machine instructions) o Operand Model: Registers o Assembly instructions: ADD rA,rB,rC Meaning: rC <- rA + rB SUB rA,rB,rC Meaning: rC <- rA - rB MUL rA,rB,rC Meaning: rC <- rA * rB LOAD a,rC Meaning: rC <- M[a] STORE rA,c Meaning: M[c] <- rA o Machine code format: Format 1: This format is made of 16 bits (1 word) and it can be used to form the machine instructions corresponding to the ADD, SUB and MUL assembly instructions. XXX -> these X’s can be either 0’s or 1’s – they are not used by the microprocessor. Format 2: This format is made of 32 bits (2 words) and it can be used to form the machine instructions corresponding to the LOAD assembly instruction. XXX, XXXXXX and XXXX -> these X’s can be either 0’s or 1’s. – they are not used by the microprocessor. Format 3: This format is made of 32 bits (2 words) and it can be used to form the machine instructions corresponding to the STORE assembly instruction. XXX and XXXXXX -> these X’s can be either 0’s or 1’s– they are not used by the microprocessor. When the microprocessor decodes the opcode for a LOAD instruction, it will know where to find Dest and where to find Src (in the memory address located in the least significant 12 bits of the second word composing this instruction). It will also know to ignore all other bits (X’s) in the instruction. Opcode (4 bits) XXX padding XXXXXX Memory address of Src (12 bits) Dest (3 bits) Opcode (4 bits) Dest (3 bits) Src1 (3 bits) Src2 (3 bits) XXX Data manipulation type of instructions Data transfer type of instructions Opcode (4 bits) XXX padding XXXXXX Memory address of Dest (12 bits) Src (3 bits) CMPT 295 – Spring 2021 When the microprocessor decodes the opcode for a STORE instruction, it will know where to find Src and where to find Dest (in the memory address located in the least significant 12 bits of the second word composing this instruction). It will also know to ignore all other bits (X’s) in the instruction. Note: About ISA design principles: When creating formats to encode instruction set … As few of them as possible were created. The fields that have the same purpose (such as Opcode, Dest and Src) are placed in the same location in as many of the formats as possible. This helps simplify the design of the microprocessor (its datapath). The bit patterns for the opcode are: Opcode (instruction) Bit pattern (4 bits) padding 0000 ADD 0001 SUB 0010 MUL 0011 LOAD 1010 STORE 1011 … … B. Description of x295+ instruction set C program x295+ assembly program x295+ machine code z = (x + y) * (x – y); 1010 000 XXX XXXXXX 0000 1010 001 XXX XXXXXX 0000 0001 010 000 001 XXX 0010 011 000 001 XXX 0011 100 010 011 XXX CMPT 295 – Spring 2021 1011 XXX 100 XXXXXX 0000 1. The first step in evaluating our x295+ instruction set is to translate the C program into an assembly program using the assembly instructions defined by our x295+ instruction set and its corresponding machine code using the machine instructions defined by our x295+ instruction set. Our task is to complete the middle column (assembly code) in the table above. The machine code has already been given. [3 marks] 2. The next step is evaluating our x295+ instruction set is to execute (hand trace) our assembly program or its corresponding machine code and using the metric (criteria) called memory traffic, we count the number of memory accesses our program makes during its execution. In other words, we count how many time the execution of our program required a word (16 bits) to be read from or written to memory. As part of this step in the evaluation of our x295+ instruction set, complete the table below. [4 marks] x295+ program (in assembly and machine code) Fetch (number of word size memory accesses) + Provide an explanation explaning the count Execute (number of word size memory accesses) + Provide an explanation explaning the count Assembly code: Machine code: 1010 000 XXX XXXXXX 0000 Count: Explanation: Count: Explanation: CMPT 295 – Spring 2021 Assembly code: Machine code: 1010 001 XXX XXXXXX 0000 Count: Explanation: Count: Explanation: Assembly code: Machine code: 0001 010 000 001 XXX Count: Explanation: Count: Explanation: Assembly code: Machine code: 0010 011 000 001 XXX Count: Explanation: Count: Explanation: Assembly code: Machine code: 0011 100 010 011 XXX Count: Explanation: Count: Explanation: Assembly code: Machine code: 1011 XXX 100 XXXXXX 0000 Count: Explanation: Count: Explanation: CMPT 295 – Spring 2021 Grand Total: Total: Total: 3. We also evaluate our instruction set using the metric (criteria) called static code size. Fill in the blanks in the statement below: [0.5 marks] o The code size of our x295+ program is __________ instructions ( __________ words). Instruction Set 3 – x295++ A. Description of x295++ instruction set architecture (ISA) Would reducing the number of operands to the instructions in our instruction set decrease the number of memory accesses the microprocessor does when fetching and executing our program Would introducing another instruction, namely COPY, in our instruction set also decrease the number of memory accesses the microprocessor does when fetching and executing our program With the above two ideas in mind, we specified a third instruction set architecture (ISA) with the same components as x295 and x295+, but with the following modifications: Instruction set (assembly and machine instructions) o Operand Model: 2 operand model o Assembly instructions: ADD rA,rC Meaning: rC <- rA + rC SUB rA,rC Meaning: rC <- rA - rC MUL rA,rC Meaning: rC <- rA * rC COPY rA,rC Meaning: rC <- rA LOAD a,rC Meaning: rC <- M[a] STORE rA,c Meaning: M[c] <- rA o Machine code formats: Format 1: This format is made of 16 bits (1 word) and it can be used to form the machine instructions corresponding to the ADD, SUB, MUL and COPY assembly instructions. Opcode (4 bits) Dest (3 bits) Src (3 bits) XXXXXX CMPT 295 – Spring 2021 XXXXXX -> these X’s can be either 0’s or 1’s. The bit patterns for the opcode are: Opcode (instruction) Bit pattern (4 bits) padding 0000 ADD 0001 SUB 0010 MUL 0011 COPY 1001 LOAD 1010 STORE 1011 … … B. Evaluation of x295++ instruction set C program x295++ assembly program x295++ machine code z = (x + y) * (x – y); 1. The first step in evaluating our x295++ instruction set is to translate the C program into an assembly program using the assembly instructions defined by our x295++ instruction set and its corresponding machine code using the machine instructions defined by our x295++ instruction set. Our task is to complete the middle column (assembly code) and the right column (machine code) in the table above. [5 marks] 2. The next step is evaluating our x295++ instruction set is to execute (hand trace) our assembly program or its corresponding machine code and using the metric (criteria) called memory traffic, we count the number of memory accesses our program makes during its execution. In other words, we count how many time the execution of our program required a word (16 bits) to be read from or written to memory. As part of this step in the evaluation of our x295++ instruction set, complete the table below. [4 marks] x295++ program Fetch Execute CMPT 295 – Spring 2021 (in assembly and machine code) (number of word size memory accesses) + Provide an explanation explaning the count (number of word size memory accesses) + Provide an explanation explaning the count … expand the table by adding as many rows as needed using the row format seen in the tables above … Grand Total: Total: Total: 3. We also evaluate our instruction set using the metric (criteria) called static code size. Fill in the blanks in the statement below: [0.5 marks] o The code size of our x295++ program is _________ instructions ( _________ words). Conclusion Considering the memory traffic metric (number of memory accesses required by our test program), which instruction set (x295, x295+ or x295++) produces the most time efficient program [0.5 marks] Considering the static code size metric (number of instructions/words required to implement our test program), which instruction set (x295, x295+ or x295++) produces the smallest program [0.5 marks]
