CS152 Computer Architecture and Engineering ISAs, Microprogramming and Pipelining January 29, 2009 Assigned January 30 Problem Set #1 Due February 10 http://inst.eecs.berkeley.edu/~cs152/sp09 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) xor %edx,%edx xor %ecx,%ecx loop: cmp 0x8049580,%ecx jl L1 jmp done L1: add %eax,%edx inc %ecx jmp loop done: ... 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 Length add RDEST, RSRC RSRC ! <RSRC> + <RDST> 2 bytes cmp imm32, RSRC2 Temp ! <RSRC2> - MEM[imm32] 6 bytes inc RDEST RDEST ! <RDEST> + 1 1 byte jmp label jump to the address specified by label 2 bytes jl label if (SF"OF) jump to the address specified by label 2 bytes xor RDEST, RSRC RDEST ! RDEST # RSRC 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 andset status flags, but do not return any result. The meanings of the status flags are given in the following table: Name Purpose Condition Reported OF Overflow Result exceeds positive or negative limit of number range SF Sign 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. 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 Meaning PUSH A push M[A] onto stack POP A pop stack and place popped value in M[A] ADD pop two values from the stack; ADD them; push result onto stack SUB pop two values from the stack; SUBtract top value from the 2nd; push result onto stack ZERO zeroes out the value at top of stack INC pop value from top of stack; increments value by one push new value back on the stack BEQZ label pop value from stack; if it’s zero, continue at label; else, continue with next instruction BNEZ label pop value from stack; if it’s not zero, continue at label; else, continue with next instruction GOTO label 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
View Full Document
Unlocking...