Possible answers to the test are below the test. CSc 262 Test 1 Friday, 19 September 1997 Each question worth 20 points. 1. You are designing a pseudo-code for a machine with 512 words of data memory, 512 words of a separate program memory, where each memory location stores an unsigned 22-bit word. What form would an instruction take? Design a single arithemetic instruction, e.g., +, and a single logical instruction, and explain, in detail, what they would do. 2. Explain the principles of Regularity and Simplicity. For both FORTRAN and pseudocode give examples illustrating each of the two principles. 3. Suppose two differnt FORTRAN subprograms, say SUBA and SUBB, respectively, have the following COMMON declarations: COMMON /COM1/ A(3,4), B(4,20) COMMON /COM1/ B(4,20), A(3,4) and both subprograms have the same DIMENSION statement: DIMENSION A(3,4), B(4,20) Which variable in the second subprogram corresponds to the variable A(2,2) in the first subprogram? Which variable in the first subprogram corresponds to the variable A(1,1) in the second subprogram? 4. In FORTRAN the assigned GOTO and the computed GOTO are redundant. Choose one of the two to eliminate and explain how to implement the one eliminated in terms of the one remaining. Then explain how to eliminate the one remaining in terms of the remaining instructions for control flow (the IF statements, GOTO, etc.) 5. Below is a table for the pseudo-code from the book. Suppose you wrote a FORTRAN compiler in this pseudo-code. Write the code for implementing the following FORTRAN instruction: IF(N)10,20,30 Explain any assumptions that you need to make. + - --------------------------- 0 MOVE NO-OP 1 + - 2 - * 3 SQUARE SQUARE ROOT 4 = NOT = 5 >= < 6 Z<--X(Y) X-->Y(Z) 7 INC + TEST NO-OP 8 READ WRITE 9 STOP NO-OP ------------------------------------------ ANSWERS 1. To count from address 0 to 511 in binary requires 9 bits, and we have 22 bits available. Thus, an instruction could consiss of two addresses (9 bits each), leaving 4 bits for the instruction. Four bits would give us room for 16 different instructions. We could number the + instruction 0001, and it would look like 0001xxxxxxxxxyyyyyyyyy, which could mean "add the contents of the memory location numbered xxxxxxxxx to the content of the memory location nubmered yyyyyyyyy." A logical instruction representing <0 could be number, say, (in binary) 0100, and the instruction 0100xxxxxxxxxyyyyyyyyy could mean "if the contents of the memory numbered xxxxxxxxx is less than 0, then go to the instruction numbered yyyyyyyyy." 2. Regular rules, rules that are simple to apply and have no exceptions are easier to learn and remember - that is the principle of regularity. In pseudocode, the three address fields of the instruction always correspond to the order "third field gets the result of having the first field operate (left to right) with the second field." This is an example of regularity. FORTRAN violates the principle in the way it allows indexing of arrays. Only certain forms (var, const, const*var, etc) are allowed. Also, its rules for forming IF statements and GOTOs are difficult to remember. Simplicity - a language should be as simple as possible, with few rules to remember. Pseudocode is simple, because the language is so small and there are so few rules to remember. FORTRAN has a simple set of rules for naming variables, and the variables need not be declared (of course this leads to other problems). 3. To simplify the argument, suppose that the address of A(1,1) in SUBA is 100 ==> the address of B(1,1) in SUBB is 100. The address of A(2,2) in SUBA is 100+(2-1)3+(2-1)=104. Now we want to choose i and j so that the address of B(i,j) in SUBB is 104. That is, 100+(j-1)4+i-1=104 ==> j=2, i=1 ==> B(2,1). The address of A(1,1) in SUBB is 100 + (room for B) = 100 + 80 = 180. In SUBA, A(3,4) occupies 100...111 ==> in SUBA B starts at 112. We seek i and j such that the address of B(i,j) = 180. But address of B(i,j) = address of B(1,1) + (i-1)4 +(j-1) = 180 ==> 112 + (i-1)4 +j-1 = 180 ==> (i-1)4 +j-1=68 ==> j=18, i=1 ==> the variable is B(1,18) 4. The choice of which to eliminate first is arbitrary, so you do not need to remember which one is which. Let us eliminate the one the reads GOTO (A1, A2, A3, ..., AN),J (the computed GOTO), where we go to the statement with the number Am if J=m. In place of that we can write the code IF (J.EQ.1) ASSIGN A1 TO N IF (J.EQ.2) ASSIGN A2 TO N . . . ... . . IF (J.EQ.1) ASSIGN AN TO N GOTO N,(A1, A2, ..., AN) then to eliminate the assigned GOTO replace GOTO N,(A1, A2, ..., AN) with IF (N.EQ.A1) GOTO A1 IF (N.EQ.A2) GOTO A1, etc. then we can eliminate the ASSIGN statement as well, replacing ASSIGN x TO N with N = x. 5. To recode IF (N) 10, 20, 30 assume that location 100 stores the value of N and that the addresses (labels) 10, 20, and 30 stand for the instructions numbered 10, 20, and 30. Also, assume location 000 if fee to be used. I separate the fields to make reading the instructions easier -1 000 000 000 store 0 in 000 -5 100 000 010 if N<0 goto 10 +4 100 000 020 if N=0 goto 20 +4 000 000 030 otherwise, goto 30