CS152 Computer Architecture and Engineering Assigned February 5 ISAs Microprogramming and Pipelining Problem Set 1 February 5 2003 Due February 12 http inst eecs berkeley edu cs152 sp08 The problem sets are intended to help you learn the material and we encourage you to collaborate with other students and to ask questions in discussion sections and office hours to understand the problems However each student must turn in their own solutions to the problems The problem sets also provide essential background material for the quizzes The problem sets will be graded primarily on an effort basis but if you do not work through the problem sets you are unlikely to succeed at the quizzes We will distribute solutions to the problem sets on the day the problem sets are due to give you feedback Homework assignments are due at the beginning of class on the due date Homework will not be accepted once solutions are handed out Problem 1 CISC RISC and Stack Comparing ISAs In this problem your task is to compare three different ISAs x86 is an extended accumulator CISC architecture with variable length instructions MIPS64 is a load store RISC architecture with fixed length instructions We will also look at a simple stack based ISA Problem 1 A CISC Let us begin by considering the following C code int b a global variable void multiplyByB int a int i result for i 0 i b i result result a Using gcc and objdump on a Pentium III we see that the above loop compiles to the following x86 instruction sequence On entry to this code register ecx contains i and register edx contains result and register eax contains a b is stored in memory at location 0x8049580 loop xor xor cmp jl jmp add inc jmp L1 done edx edx ecx ecx 0x8049580 ecx L1 done eax edx ecx loop The meanings and instruction lengths of the instructions used above are given in the following table Registers are denoted with RSUBSCRIPT register contents with RSUBSCRIPT Instruction Operation add RDEST RSRC cmp imm32 RSRC2 inc RDEST jmp label jl label RSRC RSRC RDST Temp RSRC2 MEM imm32 RDEST RDEST 1 xor RDEST RSRC RDEST RDEST RSRC jump to the address specified by label if SF OF jump to the address specified by label Length 2 bytes 6 bytes 1 byte 2 bytes 2 bytes 2 bytes Notice that the jump instruction jl jump if less than depends on SF and OF which are status flags Status flags also known as condition codes are analogous to the condition register used in the MIPS architecture Status flags are set by the instruction preceding the jump based on the result of the computation Some instructions like the cmp instruction perform a computation and set status flags but do not return any result The meanings of the status flags are given in the following table Name OF SF Purpose Overflow Sign Condition Reported Result exceeds positive or negative limit of number range Result is negative less than zero How many bytes is the program For the above x86 assembly code how many bytes of instructions need to be fetched if b 10 Assuming 32 bit data values how many bytes of data memory need to be fetched Stored Problem 1 B RISC Translate each of the x86 instructions in the following table into one or more MIPS64 instructions Place the L1 and loop labels where appropriate You should use the minimum number of instructions needed to translate each x86 instruction Assume that upon entry R1 contains b R2 contains a R3 contains i R4 should receive result If needed use R5 as a condition register and R6 R7 etc for temporaries You should not need to use any floating point registers or instructions in your code A description of the MIPS64 instruction set architecture can be found in Appendix B of Hennessy Patterson The authoritative source would be http www mips com products resource library product materials mips architecture x86 instruction label MIPS64 instruction sequence xor edx edx xor ecx ecx cmp 0x8049580 ecx jl L1 jmp done add eax edx inc ecx jmp loop done How many bytes is the MIPS64 program using your direct translation How many bytes of MIPS64 instructions need to be fetched for b 10 using your direct translation Assuming 32 bit data values how many bytes of data memory need to be fetched Stored Problem 1 C Stack In a stack architecture all operations occur on top of the stack Only push and pop access memory and all other instructions remove their operands from the stack and replace them with the result The hardware implementation we will assume for this problem set uses stack registers for the top two entries accesses that involve other stack positions e g pushing or popping something when the stack has more than two entries use an extra memory reference The table below gives a subset of a simple stack style instruction set Assume each opcode is a single byte Labels constants and addresses require two bytes Example instruction PUSH A POP A ADD SUB ZERO INC BEQZ label BNEZ label GOTO label Meaning push M A onto stack pop stack and place popped value in M A pop two values from the stack ADD them push result onto stack pop two values from the stack SUBtract top value from the 2nd push result onto stack zeroes out the value at top of stack pop value from top of stack increments value by one push new value back on the stack pop value from stack if it s zero continue at label else continue with next instruction pop value from stack if it s not zero continue at label else continue with next instruction continue execution at location label Translate the multiplyByB loop to the stack ISA For uniformity please use the same control flow as in parts a and b Assume that when we reach the loop a is the only thing on the stack Assume b is still at address 0x8000 to fit within a 2 byte address specifier How many bytes is your program Using your stack translations from part c how many bytes of stack instructions need to be fetched for b 10 Assuming 32 bit data values how many bytes of data memory need to be fetched Stored If you could push and pop to from a four entry register file rather than memory the Java virtual machine does this what would be the resulting number of bytes fetched and stored Problem 1 D Conclusions In just a few sentences compare the three ISAs you have studied with respect to code size number of instructions fetched and data memory traffic Problem 1 E Optimization To get more practice with MIPS64 optimize the code from part B so that it can be expressed in fewer instructions There are solutions more efficient than simply translating each individual x86 instruction
View Full Document
Unlocking...