Manawatu Campus

1001/159.233Sc

MAN

Internal

MASSEYUNIVERSITY

MANAWATU CAMPUS

EXAMINATION FOR

159.233 COMPUTER SYSTEMS

Semester One - 2010

Time allowed: THREE (3) hours

THIS IS A CLOSED BOOK EXAMINATION

ANSWER ALL QUESTIONS

SECTION A

Fourteenmulti-choice questions – each worth 2 marks28 marks

Record your answers to the questions in Section A on the Scantron Card provided.

SECTION B

Three questions – each worth 24 marks72 marks

Write your answers to the questions in Section B in the Blue Answer Booklet provided.

Total: 100 marks

Marks for each question are shown in brackets after the question, like this [8 marks]

Note that in some of the questions in this exam, the abbreviations hi and lo may have been used tosignify logic high (usually 5V) and logic low (0V) signals respectively.

Page 1 of 17

SECTION A

14 Multi-choice Questions – each worth 2 marks

1Registers in the MIPS computer ISA

(a)are used for the temporary storage of intermediate results in calculations.

(b)are 64bits wide to allow for the 64-bit result of multiplying two 32-bit numbers.

(c)are used for cache buffering.

(d)contain data that is always interpreted as a 2's complement number.

[2 marks]

2In measurements of computer performance, the terms throughput and performance have the following meanings

(a)throughput = total work accomplished in a given time,

performance = 1/cycles-per-second.

(b)throughput = access time

performance = 1/time for a given job.

(d) throughput = access time

performance = 1/cycles per second.

[2 marks]

3IC fabrication

(a)is a single-step process in which the layers of a chip are deposited simultaneously using patterns that are recorded photographically.

(b) is a multistep process in which the chip layers are grown on the surface of an epitaxial Silicon crystal in a furnace.

(c) is a single-step process in which all the chips layers are grown on the surface of an epitaxial Silicon crystal in a furnace.

(d) is a multistep process in which the layers of a chip are deposited one at a time using patterns that are recorded photographically.

[2 marks]

4Main memory in computers

(a)has a large address space and thus it is a large circuit, with long communication paths that make memory accesses slow.

(b) has longer access times than modern high speed disks.

(d) cannot be used by the processor for storing anything other than data for the current process. That is, it stores the values of the process's variables, but intermediate results have no addresses, so they must be kept in registers.

[2 marks]

5A barrel shift circuit for 32-bit numbers

(a)uses a separate subcircuit for each bit of the 5-bit shift-amount.Each subcircuit constitutes one stage in a larger multi-stage device, and it applies a shift by a power-of-two bits depending on whether the appropriate bit of the shift-amount is a 1 or zero.

(b) has a set of subcircuits that shifts the data in "chunks" of up eight bits at a time, and those subcircuits operate on (up to) four successive clock cycles to achieve the maximum shift of 32 bits. As most shifts are single-bit shifts, this does not cause significant delay.

(c)uses a simple (though very large) combinatorial circuit that calculates the result of the shift as a Boolean function of the input data and the 5-bit shift amount.

(d)shifts the data a bit at a time on successive clock cycles.

[2 marks]

6In an Algorithmic State Machine

(a)the state numbers are external inputs, and in the general case, the next state is determined by feeding the external inputs (or simple Boolean functions of the external inputs) into multiplexors.

(b) the state numbers are stored in a register and, in the general case, the next state is determined by feeding the external inputs (or simple Boolean functions of the external inputs) into multiplexors.

(c) the state numbers are stored in a register and, in the general case, the next state is a function of the value in the register and any external inputs to the ASM.

(d) the state numbers are external inputs, and in the general case, the next state is a function of other (internal) data.

[2 marks]

7During clock cycle 2 of a MIPS instruction

(a)the instruction has been fetched from memory, but it is not possible to perform actions that depend on its identity.

(b) the instruction has not been fetched from memory, but it is possible to perform actions that depend on its identity.

(c)the instruction has been fetched from memory, so it is possible to perform actions that depend on its identity.

(d) the instruction has not been fetched from memory and it is therefore not possible to perform actions that depend on its identity.

[2 marks]

8In a pipelined computer architecture,

(a)it is easy to handle instructions of different lengths, and the architectural approach makes it simple to deal with operands in differing locations in the instruction word.

(b) the instructions should ideally have a fixed size, and operands should be in consistent locations in the instruction word.

(c) it is easy to handle instructions of different lengths,, but operands should be in consistent locations in the instruction word.

(d) the instructions should ideally have a fixed size, and the architectural approach makes it simple to deal with operands in differing locations in the instruction word.

[2 marks]

9In a pipelined computer architecture,

(a)structural hazards occur when two instructions need the same hardware resource, and data hazards occur when a later instruction needs data before an earlier instruction has finished producing it.

(b) structural hazards occur when two instructions need the same hardware resource, and data hazards occur when two instructions need the same resource.

(c) structural hazards occur when a control decision depends on the result of an incomplete instruction, and data hazards occur when a later instruction needs data before an earlier instruction has finished producing it.

(d) structural hazards occur when a control decision depends on the result of an incomplete instruction, and data hazards occur when two instructions need the same resource.

[2 marks]

10Memory management

(a)is designed to make memories seem faster and ensure that memory accesses are evenly distributed in time.

(b) is designed to reduce the complexity of memory addressing and ensure that memory accesses are evenly distributed in time.

(c) is designed to reduce the complexity of memory addressing and ensure that memory accesses are evenly distributed in time.

(d) is designed to make memories seem faster and appear to have a larger capacity than they really do.

[2 marks]

11 What is wrong with the 8051 assembly language instructionmov a,#$29F7 ?

(a) $29F7 is not a valid hexadecimal value.

(b) $29F7 won't fit in the accumulator.

(d)There should be a comma between the $29 and the 7F.

[2 marks]

12 The effect of the DJNZ Rn,labelinstruction in 8051 assembly language is to

(a) delete the value in register Rn, and negate (if not zero) the value at the label.

(b)decrement register Rn, and if the resulting value is not zero, jump to the label.

(c)decrement the register Rn, and if the label is not zero, jump to it.

(d)delete the label if the value in register Rn is not zero.

[2 marks]

13If X and Y are unsigned eight bit numbers, the following 8051 code will

movA,X

clrc

subbA,Y

jz kkk

jc kkk

(a) jump to the label kkk if X <= Y.

(b) jump to the label kkk if X >= Y.

(d)never jump to label kkk as the "clr c" instruction has cleared the carry bit.

[2 marks]

14After the following 8051 code has executed, what value is in the accumulator?

mov40h,#$F8

movr0,#$40

mova,@r0

anl a,#$1C

orl a,#1

(a) $18

(b)$20

(d)$19

[2 marks]

SECTION B (long answers)

Three questions – each worth 24 marks

Answer questions 15 to 17 in the Blue Answer Booklet provided.

Write the numbers of the questions you have answered from this Section on the front cover of your blue answer booklet.

Do NOT tie the Scantron Card into your Blue Answer Booklet.

15(a)Draw a table with two columns, one labelled Present, and the other labelled Absent. In the columnlabelled Present, write down three aspectsof a computer architecture that are present in an Instruction Set Architecture. In the column marked Absent, write down three properties of a computer architecture that are absent from an Instruction Set Architecture.

[6 marks]

(b)

The diagram above shows two types of field layout for MIPS instructions.

Name the two type of instruction that the diagram illustrates, making it clear which name applies to the top field layout, and which name applies to the bottom field layout.

Describe the general purpose of each of the two types of instruction.

Copy the diagram into your answer booklet and fill in the names of the fields.

[6 marks]

(c)Write down a high-level language (C, Delphi, Java or similar) equivalent of the following piece of MIPS assembly language code:

jedmult$7, $15, $10

lw$6, start($7)

bne$6, $21, ted

add$15, $15, $20

jjed

ted:

where

$10 contains the value 4

$15 contains the value of variable A

$20 contains the value of variable B

$21 contains the value of variable C

start is a memory address

[6 marks]

(d)Assuming the availability of digital logic building blocks such as the one pictured below, which contains a full adder, configured to perform addition and 2's-complement subtraction, draw a bit-slice architecture for a four-bit processor that includes overflow detection and support for the MIPS SLT instruction (C equivalent: result = b < a? 1 : 0) and explain the operation of the components of the circuit that are designed to support overflow detection and the SLT instruction.

[6 marks]

16(a)Complete the following sentencesthat describe a virtual memory system, using words or phrases chosen from the list in bold below. You may "complete" the sentence simply by writing down the letters that precede the words and phrases in a clearly ordered list:

Program code and data are stored as ………………called pages: in the medium term (………………, rather than …………….), pages reside on ………………, and they have a……………… They are copied to ……………… when necessary. A ……………… has two components, ……………… and ……………… A device called the ………………converts a ……………… into the ……………… of the page in physical memory.

A: address translation unit

B: base address

C: cache

D: disk

E: disk address

F: fixed-sized units

G: hours and days

H: memory

I: memory address

J: page offset

K: seconds

L: virtual page no

Note that each word or phrase in the list may occur 0, 1, or more times in the resulting sentences.

[6 marks]

(b)Although the time-penalty of retrieving a page from disk is very great, it is possible to take advantage of the time delay. Identifyhow, and describe(don’t just give its name; describe what it does) a virtual memory technique that it makes viable.

[6 marks]

(d) Consider a machine with separate instruction and data caches. It has the following characteristics.

processor Cycles Per Instruction (without memory stalls):3

miss penalty (all misses)300 cycles

A particular program running on that machine has the following characteristics:

instructions executedI

loads and stores as % of total instructions50%

cache miss rate (data)6%

cache miss rate(instruction)3%

How much faster would the program be if cache misses were eliminated?

Note that the numbers have been chosen to make the calculation simple

[6 marks]

17(a) From the programmer's perspective, the8051 serial character I/O subsystem consists the serial buffer register sbuf and the status bits ri and tiin the scon register. Write afetch_charsubroutine that returns with a character received by the serial subsystem. If no character has been received, fetch_char should wait until one has arrived and then return with it.Assuming the serial subsystem has already been initialised, give an example of a call of your subroutine and the subsequent use of the returned value.

[4 marks]

(b)Show how the following fragmentsof pseudo-code could be translated into 8051 assembler.
A literal translation is not required, just code that implements the same functionality.

(i)The variables X, P & Q are one byte variables …

X = P / 29 – Q;

[2 marks]

(ii)If M represents internal data memory …

for i = 10 to 127
M[i] = i-1;

[3 marks]

(iii)The following is a pseudo-code fragment to build a string from characters entered by the user.
Assume:

- a getch() subroutine exists and returns a character in the accumulator.

-the character array myString starts at location $50 in data memory

byte i = 0;

byte ch = getch();

myString[i++] = ch;

ch = getch();

while(ch != $0D));

[5 marks]

(c)Describe what interrupts are, why they might be useful, and what (if any) setup
is necessary before they can be used.

[4 marks]

Question 17continued over…

Question 17continued…

(d) Write a subroutinein 8051 assembly language to subtract two multi-byte numbers (N1 and N2). On entry to the subroutine:

r0 contains the address of the first (the most significant) byte of N1

r1 contains the address of the first byte of the second number of N2

r7 contains the number of bytes in each number (they're the same)

The numbers are stored with the most significant byteat the lowest memory address and the successively less significant bytes in the following (higher) memory locations.

The result of the multi-byte subtraction, itself a multi-byte number, is stored in the same memory as N2.

Show how your subroutine could be used by writing a small program that subtracts two 5-byte numbers stored in data memory, the first number starting at $60 and the second at $70.

[6 marks]

+ + + + + + + +

8051 Architecture Reference

Program Counter: 16 bit register restricted to 0000H -> 07FFFH

Special Function Registers (SFR) Space:

Byte address / Name / Description / Bits
("---"  NOT bit addressable)
80H / P0 / Port 0 / bit addressable: P0.7 -> P0.0
81H / SP / Stack Pointer / ---
82H / DPL / Low byte of DPTR / ---
83H / DPH / High byte of DPTR / ---
87H / PCON / Power control / -
88H / TCON / Timer control / TF1-TR1-TF0-TR0-IE1-IT1-IE0-IT0
89H / TMOD / Timer mode control / ---
8AH / TL0 / Timer 0 low byte / ---
8BH / TL1 / Timer 1 low byte / ---
8CH / TH0 / Timer 0 high byte / ---
8DH / TH1 / Timer 1 high byte / ---
90H / P1 / Parallel port 1 / Bit Addressable P1.7 -> P1.0
98H / SCON / Serial control / SM0-SM1-SM2-REN-TB8-RB8-TI -RI
99H / SBUF / Serial buffer / ---
A0H / P2 / Port 2 / Bit addressable: P2.7-P2.0
A8H / IE / Interrupt Enable / EA- - -ES-ET1-EX1-ET0-EX0
B0H / P3 / Parallel port 3 / Bit addressable: P3.7 -> P3.0
B8H / IP / Interrupt priority / - - -PS -PT1-PX1-PT0-PX0
D0H / PSW / Program Status Word / CY-AC-F0-RS1-RS0-OV -F1 -P
E0H / ACC / Accumulator / ACC.7-> ACC.0
F0H / B / B register / B.7 -> B.0

Interrupt control register

IE:EAGlobal bit to enable interrupts

ESSerial interrupt (either RI or TI)

ETxClock interrupt on overflow of timer x

Timer control and mode registers - 2 timers 0 and 1

TCON: TF0/TF1Timer overflow flag timers 0/1

TR0/TR1Timer run control bit. Set by software to switch timer ON

TMOD:mode0-mode12 x 4-bit nibbles. Timer 1 = high order nibble, Timer 0 = low order.

mode = 013 bit timer

mode = 116 bit timer

mode = 28 bit auto-reload timer. THx -> TLx on overflow. Used by Serial

I/O as bit rate (*32). 0FDH in Thx gives 9600bps for 11.059Mhz clock

Serial control register

SCON: SM0-SM1-SM2-REN should be set to 0111 for normal operation

TIset when the character has been transmitted

RIset when a character is received

Power control register

PCON: set to 2 will stop the processor

Addressing Modes:

RnRegister R0 - R7 of the currently selected register bank.

direct8-bit internal data location's address.

This could be an internal Data RAM location (0-127) or a SFR.

@Ri8-bit internal Data RAM location addressed indirectly via register R0 or R1

#data8-bit constant included in instruction.

#data1616-bit constant included in instruction.

addr1111-bit destination address. Used by ACALL and AJMP.

The branch will be within the same 2K byte page of Program Memory as the
first byte of the following instruction.

addr1616-bit destination address. Used by LCALL and LJMP.

A branch can be anywhere within the 2K byte Program Memory address space.

relSigned (two's complement) 8-bit offset byte. Used by SJMP and all conditional jumps. Range is -128 to +127 bytes relative to first byte of the next instruction.

bitDirect addressed bit in internal Data RAM or SFR.

Arithmetic operations: / Byte / Cycle / C OV AC
ADD A,Rn / Add register to Accumulator / 1 / 1 / X X X
ADD A,direct / Add direct byte to Accumulator / 2 / 1 / X X X
ADD A,@Ri / Add indirect RAM to Accumulator / 1 / 1 / X X X
ADD A,#data / Add immediate data to Accumulator / 2 / 1 / X X X
ADDC A,Rn / Add register to Acc. with Carry / 1 / 1 / X X X
ADDC A,direct / Add direct byte to Acc. with Carry / 2 / 1 / X X X
ADDC A,@Ri / Add indirect RAM to Acc. with Carry / 1 / 1 / X X X
ADDC A,#data / Add immediate data to Acc. / Carry / 2 / 1 / X X X
SUBB A,Rn / Subtract reg. from Acc. with borrow / 1 / 1 / X X X
SUBB A,direct / Sub. direct byte from Acc. / borrow / 2 / 1 / X X X
SUBB A,@Ri / Sub. indirect RAM from Acc./ borrow / 1 / 1 / X X X
SUBB A,#data / Sub. immed. data from Acc. / borrow / 2 / 1 / X X X
INC A / Increment Accumulator / 1 / 1
INC Rn / Increment register / 1 / 1
INC direct / Increment direct byte / 2 / 1
INC @Ri / Increment indirect RAM / 1 / 1
DEC A / Decrement Accumulator / 1 / 1
DEC Rn / Decrement register / 1 / 1
DEC direct / Decrement direct byte / 2 / 1
DEC @Ri / Decrement indirect RAM / 1 / 1
INC DPTR / Increment Data Pointer / 1 / 2
MUL AB / Multiply A and B / 1 / 4 / 0 X
DIV AB / Divide A by B / 1 / 4 / 0 X
DA A / Decimal adjust Accumulator / 1 / 1 / X
Logical operations: / Byte / Cycle / C OV AC
ANL A,Rn / AND register to Accumulator / 1 / 1
ANL A,direct / AND direct byte to Accumulator / 2 / 1
ANL A,@Ri / AND indirect RAM to Accumulator / 1 / 1
ANL A,#data / AND immediate data to Accumulator / 2 / 1
ANL direct,A / AND Accumulator to direct byte / 2 / 1
ANL direct,#data / AND immediate data to direct byte / 3 / 2
ORL A,Rn / OR register to Accumulator / 1 / 1
ORL A,direct / OR direct byte to Accumulator / 2 / 1
ORL A,@Ri / OR indirect RAM to Accumulator / 1 / 1
ORL A,#data / OR immediate data to Accumulator / 2 / 1
ORL direct,A / OR Accumulator to direct byte / 2 / 1
ORL direct,#data / OR immediate data to direct byte / 3 / 2
XRL A,Rn / Exc-OR register to Accumulator / 1 / 1
XRL A,direct / Exc-OR direct byte to Accumulator / 2 / 2
XRL A,@Ri / Exc-OR indirect RAM to Accumulator / 1 / 1
XRL A,#data / Exc-OR immediate data to Acc. / 2 / 1
XRL direct,A / Exc-OR Accumulator to direct byte / 2 / 1
XRL direct,#data / Exc-OR imm. data to direct byte / 3 / 2
CLR A / Clear Accumulator / 1 / 1
CPL A / Complement Accumulator / 1 / 1
RL A / Rotate Accumulator left / 1 / 1
RLC A / Rotate Acc. left through Carry / 1 / 1 / X
RR A / Rotate Accumulator right / 1 / 1
RRC A / Rotate Acc. right through Carry / 1 / 1 / X
SWAP A / Swap nibbles within the Accumulator / 1 / 1
Data transfer: / Byte / Cycle / C OV AC
MOV A,Rn / Move register to Accumulator / 1 / 1
MOV A,direct / Move direct byte to Accumulator / 2 / 1
MOV A,@Ri / Move indirect RAM to Accumulator / 1 / 1
MOV A,#data / Move immediate data to Accumulator / 2 / 1
MOV Rn,A / Move Accumulator to register / 1 / 1
MOV Rn,direct / Move direct byte to register / 2 / 2
MOV Rn,#data / Move immediate data to register / 2 / 1
MOV direct,A / Move Accumulator to direct byte / 2 / 1
MOV direct,Rn / Move register to direct byte / 2 / 2
MOV direct,direct / Move direct byte to direct byte / 3 / 2
MOV direct,@Ri / Move indirect RAM to direct byte / 2 / 2
MOV direct,#data / Move immediate data to direct byte / 3 / 2
MOV @Ri,A / Move Accumulator to indirect RAM / 1 / 1
MOV @Ri,direct / Move direct byte to indirect RAM / 2 / 2
MOV @Ri,#data / Move immediate data to indirect RAM / 2 / 1
MOV DPTR,#data16 / Load Data Pointer with 16-bit const / 3 / 2
MOVC A,@A+DPTR / Move Code byte rel. to DPTR to Acc. / 1 / 2
MOVC A,@A+PC / Move Code byte rel. to PC to Acc. / 1 / 2
PUSH direct / Push direct byte onto stack / 2 / 2
POP direct / Pop direct byte from stack / 2 / 2
XCH A,Rn / Exchange register with Accumulator / 1 / 1
XCH A,direct / Exchange direct byte with Acc. / 2 / 1
XCH A,@Ri / Exchange indirect RAM with Acc. / 1 / 1
XCHD A,@Ri / Exchange low order digit indirect RAM with Accumulator / 1 / 1

Number and String Formats: