Eksamen våren 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 4 teller 25% og oppgave 5 teller 35%, mens de 4 andre oppgavene teller 10% hver. Innenfor hver oppgave vil deloppgavene telle omtrent likt.

Oppgave 1

(a)
Finn x, y, z og u slik at de fire likhetene under holder.
1.
(1111)2 + (1111)2 = (x)2
2.
(1111)8 + (1111)8 = (y)8
3.
(1111)16 + (1111)16 = (z)16
4.
(9)10 + (9)10 = (u)16
(b)
Skriv ned tallene 29, 30, 31 og 32 med heksadesimal notasjon.
(c)
Skriv ned tallene 29, 30, 31 og 32 med BCD-notasjon.
(d)
Finn et heltall n og $x_0,x_1,\ldots,x_n$ slik at

\begin{displaymath}41 \; = \; x_n2^n + x_{n-1}2^{n-1} + \cdots + x_1 2^1 + x_02^0\;. \end{displaymath}

hvor $x_0,x_1,\ldots,x_n$ har verdien 0 eller 1.
(e)
Finn to heltall n og m og heltall $x_0,x_1,\ldots,x_n$ og $y_1,y_2,\ldots,y_m$ slik at

\begin{displaymath}33.125\; = \; x_n2^n + x_{n-1}2^{n-1} + \cdots + x_1 2^1 + x_...
...ac{1}{2^1} +y_2 \frac{1}{ 2^2} + \cdots +y_m \frac{1}{ 2^m}\;. \end{displaymath}

og x'ene og y'ene har verdien 0 eller 1.
Oppgave 2
I denne oppgaven skal du lage en kombinatorisk krets som er ekvivalent til kretsen i Fig. 1.


  
Figure: Kombinatorisk krets
\begin{figure}
\begin{center}
\mbox{
\epsfxsize=10cm
\epsffile{lf1.ps}
}
\end{center}\end{figure}

Figuren viser at kretsen består av syv porter, at den tar tre input A, B og C, og at den gir en output F. Vi kan markere at F er en funksjon av A, B og C ved å bruke notasjonen F(A,B,C). Du skal tegne en ekvivalent krets, dvs. en krets som også implementerer funksjonen F(A,B,C), men den skal bestå av kun to logiske porter.

Oppgave 3
Denne oppgaven dreier seg om likheter mellom boolske uttrykk. Likheten $\overline{x}\; + \;\overline{y}= \overline{xy}$ er et eksempel på en likhet som holder. Det betyr at uansett hvilke boolske verdier vi setter inn for x og y i likheten, så får uttrykket på den høyre siden av likhetstegnet den samme verdi som utrykket på venstre side av likhetstegnet. Likheten $\overline{x}\; + \;\overline{y}= xy$ er et eksempel på en likhet som ikke holder. Her er det mulig å finne verdier for x og y slik at utrykket på høyre side av likhetstegnet får en annen verdi enn uttrykket på den venstre siden. Et eksempel på slike verdier er x=0 og y=1. Et annet eksempel er x=1 og y=0.

Under finner du en rekke boolske uttrykk med likhet mellom. Noen av likhetene holder. Andre holder ikke. Du skal plukke ut de likhetene som ikke holder. For hver likhet du plukker ut skal du fordele verdier til de aktuelle variablene slik at utrykket på den ene siden av likhetstegnet får forskjellig verdi fra utrykket på den andre siden. (Dersom det finnes flere slike fordelinger av verdier, så er det nok å gi én.)

(a)
$x\;(y\; + \;z)\;\; = \;\; x\;y \; + \;z\;x$
(b)
$\overline{x\;y}\; + \;z\;\; = \;\; \overline{x} \; + \;z \; + \;\overline{y}$
(c)
$x \; + \;\overline{x} \;\; = \;\; 1$
(d)
$x \;\overline{x} \;\; = \;\; 1$
(e)
$x \; + \;\overline{x} \;\; = \;\; 0$
(f)
$x \;\overline{x} \;\; = \;\; 0$
(g)
$x\; + \;y\; + \;z\;\; = \;\; x\;z\; + \;y\;x \; + \;z\;y \; + \;
x \;\overline{z} \; + \;y \;\overline{x} \; + \;z \;\overline{y}$
(h)
$x\; + \;y\; + \;z\;\;
= \;\; x\;z\; + \;y\;x \; + \;z\;y \; + \;x\;\overline{z} \; + \;y \;\overline{x} \; + \;z \;\overline{y} \; + \;\overline{z}$
(i)
$y\; + \;\overline{x}\;\overline{y} \; + \;x\;u
\; + \;z\;\overline{u} \; + \;x \;\overline{y} \;\overline{z} \;\overline{u}\;\; = \;\; 1$
(j)
$y\; + \;\overline{x}\;\overline{y} \; + \;x\;u
\; + \;z\;\overline{u} \; + \;x \;\overline{y}\;\overline{z}\;\overline{u}\;\; = \;\; x\; + \;y\; + \;z\; + \;u$

Oppgave 4
Du skal designe en sekvensiell krets som styrer en primitiv vekslingsautomat. En bruker kan putte en tikronemynt i automaten. Deretter kan han1 trykke på en av to knapper på automaten. Trykker han på den ene knappen skal automaten gi fra seg ti enkronemynter. Trykker han på den andre knappen skal automaten gi fra seg to femkronemynter. Dersom bruker legger på to tikroner i rad uten å trykke på en av knappene i mellomtiden, skal automaten gi en tikrone ut. (Det er ikke vårt problem om automaten går tom for penger.) Fig. 2 skisserer hvordan kretsen skal virke sammen med resten av automaten.

  
Figure: Vekslingsautomat
\begin{figure}
\begin{center}
\mbox{
\epsfxsize=16cm
\epsffile{lf2.ps}
}
\end{center}\end{figure}

Vi ser av figuren at kretsen har tre inputinnganger A, B og C. Når inputsensoren har gjenkjent en tikrone settes A til logisk 1 i én, og bare én, klokkesyklus. Under alle andre klokkesykler har A verdien logisk 0. Når inputsensoren har gjenkjent et knappetrykk som tilkjennegir at brukeren ønsker kronestykker, settes B til logisk 1 i én, og bare én, klokkesyklus. Under alle andre klokkesykler har B verdien logisk 0. Når inputsensoren har gjenkjent et knappetrykk som tilkjennegir at brukeren ønsker femkronemynter, settes C til logisk 1 i én, og bare én, klokkesyklus. Under alle andre klokkesykler har C verdien logisk 0. Maksimalt én av inputvariablene vil ha verdien logisk 1 under en og samme klokkesyklus. Det kan ikke skje at f.eks. både B og C har verdien 1 samtidig. Vi har dermed fire mulige konfigurasjoner av input ABC: 000 (intet har skjedd), 100 (tikrone lagt på), 010 (trykk for kronestykker), 001 (trykk for femkroner). Videre viser figuren at kretsen har tre outpututganger E, F og T. Hver gang E skifter fra logisk 0 til logisk 1 vil utløsermekanismen sørge for at automaten gir fra seg kronestykker. Hver gang F skifter fra logisk 0 til logisk 1 vil utløsermekanismen sørge for at automaten gir fra seg femkroner. Hver gang T skifter fra logisk 0 til logisk 1 vil utløsermekanismen sørge for at automaten gir fra seg en tikrone.

(a)
Tegn et tilstandsdiagram for kretsen. Diagrammet skal inneholde to tilstander.
(b)
Kretsen skal konstrueres ved hjelp av en D-vippe. (Det holder med én vippe når diagrammet har to tilstander.) Lag en tilstandstabell for diagrammet i punkt (a).
(c)
Finn (så enkle som mulig) boolske utrykk for vippeinngangen og outpututgangene E, F og T.
(d)
Tegn kretsen.

Oppgave 5
Vi skal i denne oppgaven se på en forenklet modell for en prosessor, en single-cycle maskin. Først skal du designe en forenklet registerfil med bare to 4-bits registere, R0 og R1.

(a)
Lag en tegning på portnivå av en 1 til 2 linjers dekoder uten enable.


(b)
Lag en detaljert tegning av en registerfil med to 4-bits registere, R0 og R1. De skal kunne lastes parallelt og kan i tegningen symboliseres med REG 4 registeret i figuren til høyre. Det skal komme en 4-bits buss D inn og dekoderen fra oppgave a) skal brukes til å velge hvilke registere som det eventuelt skal skrives til via D-bussen. Et input DA styrer dekoderen; DA = 0 velger at R0 lastes, mens DA = 1 velger at R1 lastes. Et input RW til registerfilen avgjør om det i det hele tatt skal skrives til registerene; RW = 0 velger at det ikke skal skrives, RW = 1 at det skal skrives. Utgangene fra registerne R0 og R1 skal kobles direkte til utgang A og B. Det som leses av på utgang A er med andre ord alltid det som er lagret i R0. Du skal bare tegne dekoderen og registerene som bokser med inn og utganger, tegn ikke portene som disse objektene inneholder.





\includegraphics[width=3.5cm]{r4.ps}






  
Figure: Datapath
\begin{figure}
\begin{center}
\mbox{
\epsfxsize=9cm
\epsffile{machine.ps}
}
\end{center}\end{figure}



S1 S0 D
0 0 0
0 1 A + B
1 0 $A+\overline{B}+1$
1 1 A+1








Datapath er designet ved at registerfilen er koblet til en ALU og RAM som vist i Fig. 3. Vi betrakter RAM som en del av datapath. For MW = 1 skrives data til RAM, for MW = 0 endres ikke innholdet i RAM. ALU'en består kun av en aritmetisk enhet med to styrings-bit S1 og S0. Den er satt sammen av fire komplette adderere (FA, Full Adder) og CO (Carry Out) er mente fra addereren som gir mest signifikante bit. ALU'ens funksjonstabell er gitt ved tabellen til venstre. Det er 5 bit som bestemmer hvilken operasjon datapath utfører og vi kan samle dem i et kontrollord: [DA, S1, S0, RW, MW].



(c)
Skriv ned et kontrollord som får datapath til å legge sammen tallet i R0 med tallet i R1 og legge resultatet i R1.
Vi skal nå lage en hardwired kontrollenhet til datapath og skjematisk ser maskinen ut som i Fig. 4.
  
Figure: Single-cycle maskin
\begin{figure}
\begin{center}
\mbox{
\epsfxsize=13cm
\epsffile{single.ps}
}
\end{center}\end{figure}

I tillegg til bitene som styrer datapath har instrukssjonsdekoderen utgangen PL som settes til logisk en for en jump-instruksjon. På grunnlag av PL og verdien CO har etter forrige regneoperasjon, vil branch-control avgjøre hvilket signal L som skal sendes til PC (Program Counter). PC er en 3-bits teller som fortløpende gir adressen til neste instruksjon i ROM som skal utføres. Sender branch-control L = 0, skal PC øke med én og lese neste instruksjon i ROM. Sender branch-control L = 1, skal PC laste inn de 3 minst signifikante bitene i nåværende instruksjon som neste kodeadresse. En maskininstruksjon er gitt ved 4 bit på formen [Opcode 2, Opcode 1, Opcode 0, DR]. Instruksjonssettet for maskinen skal bestå av følgende fem instruksjoner:

Opcode Symbol Funksjon
000 RESET R[DR] $\leftarrow$ 0
001 ADD R[DR] $\leftarrow$ R0 + R1
010 ST M[R0] $\leftarrow$ R1
011 INC R[DR] $\leftarrow$ R0 + 1
1XX JNC Jump if No Carry (CO = 0)



For instruksjonene RESET, ADD og INC er de 3 første bitene opcode mens det siste DR, Destination Register, avgjør om det skal skrives til R0 eller R1. Instruksjonen ST bruker ikke DR. For JNC er kun første bit opcode og de 3 siste adressen som det eventuelt skal hoppes til.
(d)
Tegn en tabell som for hver av de fem instruksjonene viser hvilke verdier utgangene S1, S0, RW, MW og PL må ha for at instruksjonen skal bli utført. Sett kryss hvis verdien ikke spiller noen rolle.
(e)
Konstruer og tegn i detalj (på portnivå) hele instruksjonsdekoderen. DR skal overføres direkte til DA. Bruk Karnaugh-diagram eller andre metoder til å forenkle kretsen mest mulig.
(f)
Tegn innholdet i "status-register"-boksen.
(g)
Tegn innholdet i "branch-control"-boksen.
Maskinen skal nå programmeres. Anta at tallene i R0 og R1 er ukjent når programmet starter.
(h)
Skriv et program i form av en løkke som legger følgende i RAM:
M[0] = 0
M[1] = 0 +1 = 1
M[2] = 0+1+2 =3
M[3] = 0+1+2+3=6
etc. helt til summen er så stor at den ikke kan lagres med 4 bit. Skriv koden som "assembler", altså med setninger som "INC R0". Prøv om mulig å få programmet til å gå inn i en uendelig løkke etter at det har utført oppgaven.
(i)
Oversett "assembler"-programmet i forrige delspørsmål til maskinkode; nuller og enere, slik den må skrives inn i ROM.

Oppgave 6
Lag et assemblerprogram som lagrer byte i minne slik at
ds:[0] = 0
ds:[1] = 0 +1 = 1
ds:[2] = 0+1+2 =3
ds:[3] = 0+1+2+3=6
etc. helt til summen er så stor at den ikke kan lagres med en byte (altså helt tilsvarende det som skulle bli lagt i minne i oppgave 5h).


-SLUTT-

About this document ...

This document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998)

Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -show_section_numbers -split 0 -no_navigation exV00.

The translation was initiated by Haarek Haugerud on 2000-06-15


Footnotes

... han1
Vi antar at kvinner ikke finnes.


Haarek Haugerud
2000-06-15