231 Fall 2008 -- Exam 1 (with answers) Name:________________________ Word Bank - questions 1-10. Place the appropriate term by its description below. (2 pts. each) accumulator machine direct addressing immediate value load/store machine indexed addressing memory location stack machine indirect addressing register ALU load address instruction location counter (loc) CPU store label pseudo-op program counter (PC) 1. __instruction________ the basic unit of work in a program, which is composed of an opcode and possibly one or more operands 2. __address____________ a number used as the name of a memory location 3. __direct_addressing__ addressing mode in which the instruction holds the address of a memory word which contains the data which is to be accessed 4. __store______________ an instruction that will make a copy of the value in the accumulator (or in a specified general register) and place it in a specified memory word. 5. __stack_machine______ machine design in which an add instruction only has an opcode (the source operands are fetched from, and the result is stored in, a structure within the CPU) 6. __ALU________________ unit within a computer that performs arithmetic and logical computations (it has no registers) 7. __program_counter____ a register in the CPU that contains the address of the memory word from which the next instruction will be fetched 8. __label______________ a symbolic name in an assembly language program that is used to access data or as a branch target 9. __pseudo-op__________ an assembly language statement that doesn't generate a machine instruction but instead acts as a directive to the assembler 10. _location_counter___ a variable in the assembler program that contains the address at which the next instruction or data word will be placed Give the power of ten that corresponds to these prefixes. (3 pts. each) 11. tera __10**(+12)__ 12. mega __10**(+6)___ 13. nano __10**(-9)___ 14. micro __10**(-6)___ 15. (a) Why do assemblers use two passes? ____________forward references____ (Hint: two words.) (2 pts.) (b) What does the first pass do? increment the __location_counter______ (Hint: two words each.) and (2 pts. each) build the ______symbol_table__________ 16. On the right hand side, give the symbol table produced by the first pass of the assembler for the following accumulator machine program. (9 pts.) --- ANSWERS --- label(start) start 0 load(ten) ten 5 store(value) value 6 halt word(ten,10) word(value,ten) end(start) 17. The opcodes for the halt, load, and store instructions are 0, 50, and 60, respectively. On the right hand side give the executable file produced by the second pass of the assembler for the following accumulator machine program. (12 pts.) --- ANSWERS --- label(start) load(ten) 50 5 store(value) 60 6 halt 0 word(ten,10) 10 word(value,ten) 5 end(start) 0 18. Give the output and explain what the following m4 macro does when called as "test(a,2)". (5 pts.) define(a,1) define(test,`ifelse($1,$2,eval($1+$2),eval($1*$2))') --- ANSWER --- prints 2 test(a,2) --> ifelse(a,2,eval(a+2),eval(a*2)) `a' is replaced with 1 --> ifelse(1,2,eval(1+2),eval(1*2)) since 1!=2 ifelse() returns 4th argument --> eval(1*2) --> 2 Extra Credit 1. (up to 2 points) Suppose we want to increment the accumulator on the accumulator machine. Since we do not have an increment instruction, a friend suggests the following macro. Does the macro work correctly to provide the assembly language programmer the equivalent function of an increment instruction? Explain your answer. define(inc,`add(1)') --- ANSWER --- no, add(1) will add the value contained in memory location 1 to the accumulator, and memory location 1 could contain anything 19. For the accumulator machine, we used the following m4 definitions for assembling an add instruction. [first pass] define(add, `define(`loc', eval(loc + 2))dnl') [second pass] define(`add', ` 40 $1') Suppose that an increment accumulator instruction (opcode 41 with no operands) is added to the accumulator machine and we want to add it to the assembler. An "inc" instruction is defined as a one-word instruction with an opcode value of 41. Show the first and second pass assembler macro definitions for inc. (10 pts.) [first pass] define(inc, [second pass] define(`inc', --- ANSWER --- [first pass] define(inc, `define(`loc', eval(loc + 1))dnl') [second pass] define(`ins', ` 41') 20. For the accumulator and load/store machines, we used the pseudo-op macro named word() to generate a single memory word and define a label for that word. Thus, word(x,1) will add the label x to the symbol table in the first pass and generate a memory word with the value 1 in the second pass. The m4 definitions for word() are: [first pass] define(word,``define($1,'eval(loc)`)' define(`loc', eval(loc + 1))') [second pass] define(`word',` $2') We would like to add a new pseudo-op macro named data() that will generate a single memory word without defining a label. That is, using data(), we could perform the actions of word(x,1) in this manner: label(x) data(1) We also want data() to be able to evaluate arithmetic expressions involving decimal constants and even symbolic names. Thus data(5+4) would generate a memory word containing a 9, data(a) would generate a memory word containing the numeric address for a, and data(a+4) would generate a memory word containing the numeric address for the fourth memory word beyond the memory location a. Fill in the two m4 definitions needed for data(). (10 pts.) [first pass] define(data, [second pass] define(`data', --- ANSWER --- [first pass] define(data, `define(`loc', eval(loc + 1))') [second pass] define(`data', `eval($1)') accumulator machine instruction set opcode address operation name machine action ------ ------- -------------- -------------- halt ---- halt stop execution div addr divide acc = acc/memory[addr] mul addr multiply acc = acc*memory[addr] sub addr subtract acc = acc-memory[addr] add addr add acc = acc+memory[addr] load addr load acc = memory[addr] store addr store memory[addr] = acc ba addr branch always pc = addr blt0 addr branch on less than if acc<0 then pc = addr ble0 addr branch on less than or equal if acc<=0 then pc = addr beq0 addr branch on equal if acc==0 then pc = addr bne0 addr branch on not equal if acc/=0 then pc = addr bge0 addr branch on greater than or equal if acc>=0 then pc = addr bgt0 addr branch on greater than if acc>0 then pc = addr print addr print display contents of memory[addr] 21. Write a section of code in the assembly language for the accumulator machine that examines values in memory locations x and y and stores the smaller of the two values in memory location z. If they are equal, it doesn't matter which one you store in z. (16 pts.) --- commented version for study --- (comments are not needed when you are answering on the exam) comment(` if( x < y ) ') comment(` z = x ') comment(` else ') comment(` z = y ') load(x) comment(` if ( x - y < 0 ) ') sub(y) comment(` that is, if x < y ') blt0(storex) comment(` then go to code for z = x ') comment(` else fall through to z = y ') load(y) comment(` else z = y ') store(z) ba(done) comment(` skip over `then' section ') label(storex) load(x) comment(` then z = x ') store(z) label(done) comment(` join point for then and else parts ') Extra credit 2. (up to 8 pts.) Write a section of code in the assembly language for the accumulator machine that implements the following loop. for( i = 1; i <= 5; i++ ) print(i); --- commented version for study --- (comments are not needed when you are answering on the exam) load(one) comment(` i = 1 ') store(i) label(loop) comment(` translated as a while loop ') load(i) comment(` if ( i - 5 > 0 ) ') sub(five) comment(` that is, if i > 5 ') bgt0(done) comment(` then exit loop ') comment(` else fall into body of loop ') comment(` (falls through when i <= 5) ') print(i) load(i) comment(` i++ ') add(one) store(i) ba(loop) label(done) ... word(one,1) word(five,5)