Eksamen høsten 2000 Datamaskinarkitektur

Les nøye gjennom oppgavene før du begynner og pass på å besvare alle spørsmålene. Alle hjelpemidler er tillatt. Oppgavene vil ikke bli vektlagt likt ved sensur. En sannsynlig fordeling er at oppgave 5 teller 25%, oppgavene 2-4 teller 15% hver og de resterende teller 10% hver. Innenfor hver oppgave vil deloppgavene telle omtrent likt.

Oppgave 1
Finn $x$, $y$, $z$ og $u$ slik at de fire likhetene under holder.

(a)

$(11011)_2 \times (100)_2 = (x)_2$

(b)

$(ACDC)_{16} \times (100)_{16} = (y)_{16}$

(c)

$(A)_{16} \times (A)_{16} = (z)_{16}$

(d)

$(A)_{16} \times (A)_{16} = (u)_{BCD}$

Oppgave 2
Under finner du 17 grunnleggende boolske lover. De er hentet fra læreboka (Mano & Kime).

$$\begin{array}{llcll} 1. & x + 0 = x & \;\;\;\;\;\;\;\;\; & 2... .... & \overline{x\cdot y}= \overline{x}+ \overline{y} \end{array}$$

Lovene over kan brukes til å vise at to boolske uttrykk er like. Vi kan for eksempel vise at $xu = (x ((zu+ \overline{zu})+yz))u$. Det kan gjøres slik:

$$x u \;\stackrel{\mbox{{\tiny 2}}}{=}\; (x\cdot 1)u \;\stackre... ...ackrel{\mbox{{\tiny 10}}}{=}\; (x ((zu+ \overline{zu})+yz))u\;.$$

Legg merke til at vi bruker én, og bare én, lov for hver likhet, og at vi av og til benytter at $\cdot$ binder sterkere enn $+$ til å sløyfe paranteser. Noen av de fem følgende booleske ligninger holder. Noen av dem holder ikke.

(1)

$x = y(x+y)$

(2)

$x = x(x+y)$

(3)

$x \; \overline{(y+z)} = \overline{(xy+xz)}$

(4)

$(x+y)z = xz+yz$

(5)

$(z+x)(z+y)+\overline{xy}=1$

(a)

Identifiser de ligningene som holder.

(b)

Vis etter mønster av eksempelet over at de ligningene du oppgav under punkt (a) holder. (NB! Du får ikke benytte andre lover enn de 17 grunnleggende lovene som er oppgitt i starten av denne oppgaven.)

Oppgave 3
Du skal designe en sekvensiell krets som styrer en primitiv heis. Heisen går mellom etasje A og B, og den styres ved å trykke på én knapp. Står heisen i etasje A, skal den gå til etasje B når noen trykker på knappen. Står heisen i etasje B, skal den gå til etasje A når noen trykker på knappen. Knappen det trykkes på blir stående inne og spretter først ut igjen når heisen har stanset i en ny etasje. Det er altså fysisk umulig å trykke på knappen mens heisen er på vei fra en etasje til en annen. (Vi kan for eksempel tenke oss en vareheis som brukes av enkelte restauranter som har kjøkken i kjelleren. De ansatte i restauranten kan bruke heisen til å sende oppvask, bestillinger, råvarer og lignende til og fra fra kjøkkenet.) Figur 1 skisserer hvordan kretsen skal virke sammen med resten av mekanikken som styrer heisen (heretter kalt ``heismekanikken'').

Figur: Heis-system

Vi ser av figuren at kretsen har én inputinngang $X$. Når inputsensoren har gjenkjent et trykk på knappen settes $X$ til logisk 1 i én, og bare én, klokkesyklus. Under alle andre klokkesykler har $X$ verdien logisk 0. Videre viser figuren at kretsen har to outpututganger $Y$ og $Z$. Hver gang $Y$ skifter fra logisk 0 til logisk 1 vil heismekanikken sørge for at heisen beveger seg fra etasje A til etasje B. Hver gang $Z$ skifter fra logisk 0 til logisk 1 vil heismekanikken sørge for at heisen beveger seg fra etasje B til etasje A.

(a)

Tegn et tilstandsdiagram for kretsen.

(b)

Kretsen skal konstrueres ved hjelp av en D-vippe. Tegn den ferdige kretsen. Du trenger ikke forklare hvordan du har tenkt for å komme fram til kretsen du tegner.

Oppgave 4
Kretsene som lages i denne oppgaven skal senere brukes i oppgave 5. Figur 2 viser hvordan de blir brukt.

(a)

Konstruer ved hjelp av logiske porter en kombinatorisk krets som tar to input $P_1$ og $P_0$ og har 4 output $P_1^+, P_0^+, P_1^-$ og $P_0^-$. Kombinasjonen $P_1 P_0$ skal tolkes som et 2-bits binært tall $P$, og $P^+$ og $P^-$ skal tilsvarende tolkes som 2-bits binære tall. Kretsen skal konstrueres slik at $P^+ = P + 1$ og $P^- = P -1$. Hvis f. eks. $P = 10$ skal kretsen altså gi output $P^- = 01$ og $P^+ = 11$. I det spesielle tilfellet at $P = 11$ skal $P^+ = 00$ og tilsvarende for $P = 00$ skal $P^- = 11$.

I resten av oppgaven skal en 2-bits teller konstrueres som tar to input $C_1$ og $C_0$. Output fra telleren er tallet $P = P_1 P_0$. Telleren skal kunne telle både oppover og nedover og kunne resettes. Operasjonen skal avhenge av input etter følgende tabell:

$C_1$	$C_0$	operasjon
0	0	reset (P = 0)
0	1	P endres ikke
1	0	$P = P -1$
1	1	$P = P +1$

$P$ skal følge sekvensen 00, 01, 10, 11, 00, 01, ... etc. når det telles oppover og sekvensen 00, 11, 10, 01, 00, 11, .... etc. når det telles nedover.

(b)

Kretsen skal designes med JK-vipper. Skriv ned en tilstandstabell der vippeinngangene er med.

(c)

Bruk Karnaugh-diagram til å finne forenklede Boolske uttrykk for vippeinngangene.

(d)

Tegn kretsen.

Oppgave 5
Mange datamaskiner bruker prinsippet med en stack som data kan push'es til og pop'es fra. I denne oppgaven skal vi konstruere hardware som kan gjøre raske stackoperasjoner ved å bruke et sett av registere som stack. Telleren som ble konstruert i oppgave 4 skal brukes som stack-peker. Vi skal også bruke den kombinatoriske kretsen fra oppgave 4(a). Man trenger ikke å ha fått til konstruksjonen av kretsene i forrige oppgave for å gjøre denne oppgaven, men man må forstå hvordan disse kretsene virker.

Figur: Datapath

Figur 2 viser hvordan kretsene fra oppgave 4 inngår i en datapath som bruker en 4x4 registerfil som stack. Registerfilen består av fire 4-bits registere og har en inngående D-buss og to utgående busser A og B. Registerfilen styres av følgende styringsbit og adresser:

RW	Det skrives til registerfilen hvis dette bitet er 1
DA	2-bits adresse til registeret det skrives til når RW = 1
AA	Innholdet til registeret med denne 2-bits adressen sendes til A-bussen
AB	Innholdet til registeret med denne 2-bits adressen sendes til B-bussen

ALU'en har bare to funksjoner. For $S=1$ adderer den A+B og for $S=0$ subtraherer den A-B. Multiplekseren K sender resultatet fra ALU til registerfilen om styringsbit MK = 1, for MK = 0 sendes en konstant verdi. Registerene R0, R1, R2 og R3 (som adresseres med henholdsvis 00, 01, 10 og 11) betraktes som en stack der 4-bits tall kan lagres. Telleren P, som ble konstruert i deloppgave 4(b), skal til enhver tid peke på det øverste tallet på stacken. Når et nytt tall pushes på stack, skal P økes med 1. Av Figur 2 ser man at de to øverste tallene på stacken alltid sendes til A og B-bussen. Hvilket register som det skrives til, avgjøres av styringsbitet MP til MUX P. For MP = 0 skrives det til R[$P+1$] og for MP = 1 skrives det til R[$P-1$]. Utgangene $P^+$ og $P^-$ kommer fra kretsen som ble konstruert i 4(a). Denne sammensetningen gjør det mulig å lage hurtige stackoperasjoner som utføres i løpet av en klokkesyklus.

En maskininstruksjon er gitt ved 3 bit på formen [Opcode 2, Opcode 1, Opcode 0]. Instruksjonssettet for maskinen skal bestå av følgende fem instruksjoner:

Opcode	Symbol	Funksjon
000	RESET	P $\leftarrow$ 0
001	POP	P $\leftarrow$ P - 1
010	ADD	R[P-1] $\leftarrow$ R[P] + R[P-1], deretter P $\leftarrow$ P - 1
011	SUB	R[P-1] $\leftarrow$ R[P] - R[P-1], deretter P $\leftarrow$ P - 1
1XX	PUSH	R[P+1] $\leftarrow$ tallet XX, deretter P $\leftarrow$ P + 1

Instruksjonen POP flytter stack-pekeren P ett hakk ned på stacken. Etter en addisjon av de to øverste tallene på stacken skal pekeren flyttes ett hakk ned til dit resultatet ligger. Instruksjonen PUSH legger tallet som Opcode 1 og Opcode 0 tilsammen utgjør (0-3) øverst på stacken og flytter stack-pekeren til å peke på dette tallet. Figur 3 viser et eksempel på hvordan stack-pekeren og verdiene på stacken endrer seg ved instruksjonen ADD.

Figur: Slik endres stacken ved instruksjonen ADD.

(a)

Tegn en tabell som for hver av de fem instruksjonene viser hvilke verdier inngangene $C_1$, $C_0$, RW, MK, MP og S til datapath må ha for at instruksjonen skal bli utført. Sett kryss hvis verdien ikke spiller noen rolle.

(b)

Konstruer og tegn i detalj (på portnivå) den tilsvarende instruksjonsdekoderen. Bruk Karnaugh-diagram eller andre metoder til å forenkle kretsen mest mulig.

Figur: Stack-maskin

Figur 4 viser hvordan telleren PC (Program Counter) og en ROM er koblet til instrukssjonsdekoderen og datapath, slik at man kan skrive programmer og legge dem i ROM. I boksen "zero fill" legges det 0 i de to mest signifikante bitene av konstanten, slik at Opcode 1 og Opcode 0 tilsammen utgjør kostanten som sendes til datapath.

(c)

Skriv ved hjelp av symbolnavn for instruksjonene et program som manipulerer stacken slik at tallet 2 blir liggende i R0 og tallet 6 blir liggende øverst på stacken i R1

(d)

Skriv programmet i forrige deloppgave med binær kode slik det må legges i ROM.

Oppgave 6
Finn først ASCII-verdien til de tre bokstavene 'v', 'i' og 'r'.
Lag deretter en assembler-prosedyre med navn "virussjekk" som avgjør om strengen "vir" forekommer i datasegmentet, når bytene der tolkes som ASCII-tegn. Du kan anta at datasegmentet begynner med ds:[0] og avsluttes med ds:[65535]. Når prosedyren returnerer skal verdien 1 ligge i ax hvis strengen "vir" ble funnet, ellers skal verdien 0 ligge i ax. Prosedyren må bevare verdiene i bx, cx og dx.

Oppgave 7

Figur: 2-til-4 dekoder

Sett sammen fem 2-til-4 dekodere med Enable som den vist i Figur 5, til en 4-til-16 dekoder med Enable. Du skal ikke bruke noen eksterne porter, kun fem dekodere.

-SLUTT-