This should take no longer than 25 minutes and is simply intended to probe whether you have understood the material in the prac. Use your textbook if you think it will help. Answer on the question sheet (3 sides).)
1. I have a memory like my friend Eratosqenes and his sief and cannot remember - remind me of your name (surname) and student number [1]
Pat Terry 63T0844
2. In the prac you were invited to note that sequences like
LDA X and LDA Y
LDV <code>
STO
occurred so frequently that it was worth introducing special opcodes LDL X and STL Y instead. By now you will recognise something of the Terry perversity - maybe the PVM was originally defined to have LDA, LDV and STO opcodes rather than simply having only LDL and STL opcodes for no other reason than that it makes for lots of fun late at night to add these opcodes to the machine. But maybe not? If you have LDL and STL, could you completely remove LDA, LDV and STO from the opcode list, or would you still need to have them available? Justify your answer. [3]
If every LDV was preceded by an LDA one could get away with using LDL instead of LDA + LDV, and if every other use of LDA was followed by a STO one could get away without LDA. But this is not the case. Consider the following code:
read(i); list[i] = list[j];
which, even if we use every LDL and STL we can, translates to
LDA i
INPI ; read(i)
LDL list
LDL i
INXA ; address of list[i]
LDL list
LDL j
INXA ; address of list[j]
LDV ; value of list[j]
STO ; list[i = list[j]
3. The following algorithm is meant to read a list of numbers and then report on which was the greatest in magnitude. It is not quite right. Make the minimal change needed to correct it. [2]
void main () {
// Reads a list of non-zero numbers and reports on which had the
// greatest magnitude
// Example: for 1 45 -7 60 -7 0 should report 60
// Example: for 1 45 -7 60 -70 0 should report -70
// Ivan Idear, 2007
int n, max = 0;
repeat
read(n);
if (abs(n) > max) max = n;
until (n == 0);
write("largest number was ", max);
}
All we need is to change the if statement:
if (abs(n) > abs(max)) max = n;
4. Suppose that the PVM could be extended to incorporate a new opcode PVM.abs for dealing with the abs(n) function in the above code. What addition would be needed to the switch statement in the emulator (as it appears on pages 62 - 65 of the text) to support this new opcode? [3]
case PVM.abs:
Push(Math.abs(Pop());
break;
or even
case PVM.abs:
tos = Pop();
if (tos >= 0) Push(tos); else Push(-tos);
break;
or even
case PVM.abs:
mem[cpu.sp] = Math.abs(mem[cpu.sp]);
break;
or even
case PVM.abs:
if (mem[cpu.sp] < 0) mem[cpu.sp] = -mem[cpu.sp];
break;
5. Show how the corrected algorithm could be coded into PVM code, making use of PVM.abs. [9]
Hint: you will be able to write a shorter translation if you make use of the LDL N and STL N opcodes mentioned in question 2, so feel free to do so.
0 DSP 2 ; variable 0 is n, variable 1 is max 0 DSP 2 ; variable 0 is n, variable 1 is max
2 LDA 1 2 LDC 0
4 LDC 0 4 STL 1 ; max = 0;
6 STO ; max = 0; 6 LDA 0 ; repeat
7 LDA 0 ; repeat 8 INPI ; read(n);
9 INPI ; read(n); 9 LDL 0
10 LDA 0 11 ABS ; // abs(n)
12 LDV 12 LDL 1
13 ABS ; // abs(n) 14 ABS ; // abs(max)
14 LDA 1 15 CGT
16 LDV 16 BZE 22 ; if (abs(n) > abs(max)
17 ABS ; // abs(max) 18 LDL 0
18 CGT 20 STL 1 ; max = n;
19 BZE 27 ; if (abs(n) > abs(max) 22 LDL 0
21 LDA 1 24 LDC 0
23 LDA 0 26 CEQ
25 LDV 27 BZE 6 ; until (n == 0;
26 STO ; max = n; 29 PRNS "largest number was "
27 LDA 0 31 LDL 1
29 LDV 33 PRNI ; write(max)
30 LDC 0 34 HALT ; exit
32 CEQ
33 BZE 7 ; until (n == 0;
35 PRNS "largest number was "
37 LDA 1
39 LDV
40 PRNI ; write(max)
41 HALT ; exit
6. Briefly indicate where, if anywhere, you would have to make other changes to the PVM.java file to handle this new opcode [2].
We should have to add an internal value for abs to the "enumeration" at the start of the file, and we should have to add the corresponding initialisation of the element of the mnemonic look-up array (at the end of the file). Since this is a "zero address" instruction, it does not give rise to further changes in the parts of the file responsible for tracing or for listing code.
7. Suppose you could not introduce or use the PVM.abs opcode. How would you then code an algorithm like the following in PVM code, using only one PVM.prni opcode? [5]
void main () {
int i;
read(i);
write(abs(i));
}
0 DSP 1 ; variable 0 is i 0 DSP 1 ; variable 0 is i
2 LDA 0 2 LDA 0
4 INPI ; read(i) 4 INPI ; read(i)
5 LDA 0 5 LDL 0
7 LDV 7 LDC 0
8 LDC 0 9 CGT
10 CGT 10 BZE 16 ; if (i > 0)
11 BZE 18 ; if (i > 0) 12 LDL 0 ; i on tos
13 LDA 0 14 BRN 19
15 LDV ; i on tos 16 LDL 0 ; i on tos
16 BRN 22 18 NEG ; -i on tos
18 LDA 0 ; i on tos 19 PRNI ; write(abs(i));
20 LDV 20 HALT ; exit
21 NEG ; -i on tos
22 PRNI ; write(abs(i));
23 HALT ; exit
8. When doing the practical you should have noticed that the numeric values associated with the opcodes influence the performance of the interpreter. In developing a serious interpreter, one might "profile" the system, by computing a frequency count for each opcode using a set of test programs and then use this information to tweak the mnemonic to opcode mapping. Briefly suggest how and where one would modify the interpreter to perform such a frequency count as a program was interpreted and report it after execution was complete. [5]
Introduce an array in which to store the frequency counts for each instruction:
public static int[] freq = new int[PVM.nul + 1];
Modify the start of the interpreter and the fetch-execute cycle to clear the counts as the program commences and then increment the appropriate count for each opcode encountered:
for (int i = 0; i <= PVM.nul; i++) freq[i] = 0; // +++++++ prepare to gather statistics
ps = running; // prepare to execute
do {
pcNow = cpu.pc; // retain for tracing/postmortem
if (cpu.pc < 0 || cpu.pc >= codeLen) {
ps = badAdr;
break;
}
cpu.ir = next(); // fetch
if (tracing) trace(results, pcNow);
freq[cpu.ir]++; // +++++++ gather statistics
switch (cpu.ir) { // execute
...
When interpretation is complete, display the statistics for each valid opcode:
...
if (ps != finished) postMortem(results, pcNow);
for (int l = 0; l <= PVM.nul; l++) // +++++++ display statistics
if (!mnemonics[l].equals("")) {
results.write(mnemonics[l], -6);
results.writeLine(freq[l], 10);
}
A more sophisticated system might sort this array before displaying it, or perform further analysis. For the sample programs in the prac kit one will find that some opcodes are executed far more than others!