Exercise #1: The Fetch-Decode-Execute Cycle The purpose of this exercise is to test the understanding of the Fetch-Decode-Execute cycle. Consider a fictitious and very simplified Von-Neumann architecture with: 5-bit addresses/9-bit values memory 2 9-bit registers for computation named A and B; 1 5-bit Program Counter register; 1 9-bit Current Instruction register; 1 1-bit error register (set at the end of the cycle) when the execution of an instruction creates an "error" condition. 6 instructions: LOAD, STORE, SUBTRACT, JE (Jump on Error), and STOP (detailed in the table below) Each instruction is encoded using 9 bits: the first 3 bits give the mnemonics (or operation code) identifying the instruction (see table below); the next bit gives the id of the register that the instruction operates on: 0 identifying A, 1 identifying B; and the last 5 bits are an operand which can be anything (e.g. an integer number, an address, or even ignored) depending on the instruction. CPU Instruction LOAD STORE SUB E STOP Opcode Description 010 011 101 110 111 Load register value with value from address (operand) Example: 010110101 = 010110101 is executed as 010 = LOAD, 1 = B, with the value at address (10101, i.e. LOAD B, [10101]. For instance, if the memory content at address 10101 is 11, then, at the end of the fetch-decode-execute cycle, the register B will contain the value 11. The value of the error register is not used. It is set to 0 when this instruction has completed its execution. Store register value to address (operand) Example: 011010101010 011010101 is executed as 011 = STORE, 0 = A, with the value at address (10101, i.e. STORE A, [10101]. For instance, if the content of the register A is 25d, then, at the end of the fetch-decode-execute cycle, the memory location at address 10101 will contain the value 25. The value of the error register is not used. It is set to 0 when this instruction has completed its execution. Subtract register B contents from register A contents. The result is written in A. The error register is set if an underflow happens. 101000101: SUB A, B. Note that 6 bits are ignored If initially A contains the value 7 and B 5, then, at the end of the fetch-decode-execute cycle, A will contain 2 (=7-5), i.e. b00010. The error register is set to 0 (no error). If initially A contains the value 3 and B 5, then, at the end of the fetch-decode-execute cycle, A will contain 0 (while it should be "-2" (=3-5)), and the error register will be set to 1 (signaling the underflow error) The value of the error register is not used for the execution of this instruction. If the error register value is set to 1, set the Program Counter (PC) value to (operand) Otherwise, nothing happens (i.e. increment the PC by 1). In any case the error register value is set to 0 at the end of the fetch-decode-execute cycle For instance: 110000101 translates to JE 00101 Case 1: If initially the error register is 0 and the PC value is 11110, then at the end of the fetch-decode-execute cycle, the PC value will be set to 11111 Case 2: If initially the error register is 1 and the PC value is 11110, then at the end of the fetch-decode-execute cycle, the PC value will be set to 00101 The value of the error register is used for the execution of this instruction. Terminates program For instance: 11100101 translates to STOP. Note that all bits after the first three ones (00101 in this example) are ignored. The value of the error register is not used for the execution of this instruction. Part 1: Warm-up Question 1.1 [2 points] What does the instruction encoded by 110010001 do? Show your work. Question 1.2 [2 points] Translate "LOAD A, [10110]" to binary. Show your Question 1.3 [2 point] Among the instruction encodings below, which one is invalid? Give an explanation. 1.11010110 2. 10011011 3. 01111010 work. Part 2: Case study Assume that initially: The Program Counter value is set to 12d=01100b; The values of the other registers are undefined. The memory has the following contents: Address Contents Address Contents Address Contents Address Contents 00000 101110110 01000 10011000110000 01001011111000 001001011 101101001 000001011 000000000 00001 110101001||01001 110010000 10001 00010 00111101101010 01010101010010 00011 10011011001011 010000001 10011 001011010 11011 00100 10100011001100 01001011010100 010001100 11100 00101 01001111001101 01011011110101 010100000 11101 00110 10001100101110 10110000010110 00111 00011101101111 110010001 10111 100010111 000000100 111101101 100100000 011010110 11001 11100000011010 00100000111110 010111100 11111 Question 2.1 [2 points] What is the address and the first instruction executed by the program? Explain. Question 2.2 [18 points] Detail the program execution instruction by instruction (the program stops after executing the first STOP). Detail what each stage of the Fetch-Decode-Execute cycle does for each instruction. Make sure to describe thoroughly how the system (CPU and memory) is or is not modified by each stage. Detail the program execution in the following way: for each instruction, give the assembly-like code of the instructions (e.g., "LOAD A, [0101]"), and state what register and or memory values change. For instance, here is a sample answer (which has nothing to do with the real answer): PRINT [0100] LOAD A, [0101] STORE B, [0000] JE [1111] STOP ; print 'R' ; set the value of A to 01010101 (85d) ; set the value in RAM at address 0000 to 77d ; do not jump to instruction at address 1111 ; terminate Hint: The program executes 6 instructions, counting the last STOP instruction. Question 2.3 [2 points] What is the content at address 10010? What is the content at address 10110? Question 2.4 [2 points] The last STORE instruction writes to memory the output of the program. What does this program compute? Also consider other cases with different input values. Explain. Hints: Rewrite the CPU mnemonics into a higher level pseudo-language (e.g. pseudo-C, or English). Swap the two initial input values in memory. Play around with other values. Execute and conclude.