581365-8 Tietokoneen rakenne, erilliskoe 10.10.2003  

Kirjoita jokaiseen vastauspaperiin: oma nimi, henkilötunnus, kurssin nimi, nimikirjoitus ja sivunumero.

1. [15 p] Yhdistelmäpiiriä (combinatorial circuit) käytetään kontrolloimaan 7-segmenttistä näyttöä (ks. Figure A.34, kääntöpuolella). Piirillä on neljä sisäänmenoa, joiden avulla on koodattu desimaalinumero käyttäen pakattua desimaaliesitystä. Tässä esityksessä numerot 0, 1, 2,..., 9 ovat koodattuna siis biteiksi 0000, 0001, 0010, ..., 1001. Sisäänmenobitit ovat vasemmalta oikealle järjestyksessä X₁, X₂, X₃, X₄. (Jos haluat, voit nimetä ne uudelleen biteiksi A, B, C ja D)

   Sisäänmenojen avulla piiri valitsee, mitkä näytön segmenteistä on kulloinkin aktivoitu (valaistu). Tarkastelemme jatkossa vain näyttösegmenttiä Z₄ (vaakaviiva keskellä) ja sitä kontrolloivaa vastaavaa piirin ulostuloa Z₄. Ulostulon Z₄ arvo on siis yksi (1) kun kyseinen segmentti on valaistu.

   1. [4 p] Anna Z₄ totuustaulukkona.
   2. [4 p] Anna Z₄ Boolean lausekkeena SOP (sum of products) muodossa.
   3. [4 p] Anna Z₄:n SOP-muotoa vastaava Karnaugh-kartta (Karnaugh Map) ja sen avulla muodostettu mahdollisimman yksinkertainen SOP-muotoinen Z₄:n Boolean lauseke. Näytä, miten yksinkertaistaminen tapahtui Karnaugh-kartan avulla.
   4. [3 p] Anna Z₄ Boolean lausekkeena POS (product of sums) muodossa.
   
    
2. [15 p] Boothin algoritmi kokonaislukujen kertolaskuun. Minkä ongelman Boothin algoritmi ratkaisee? Miten Boothin algoritmi toimii? Miksi Boothin algoritmi on parempi kuin perinteinen ratkaisu? Onko tilanteita, joissa perinteinen ratkaisu olisi parempi tai yhtä hyvä kuin Boothin algoritmiin perustuva ratkaisu? Anna kuvaava esimerkki.
   
   (Vastauksesi saa olla korkeintaan 2 sivua pitkä, kuvat mukaanluettuna)
    
3. [15 p] IA-64 ja Itanium.
   1. Selitä käsite "predikoitu suoritus (predicated execution)". Anna esimerkki.
   2. Selitä käsite "spekulatiivinen lataus tai kontrollispekulointi (speculative loading or control speculation)". Anna esimerkki.
   3. Selitä käsite "data spekulointi (data speculation)". Anna esimerkki.
   4. Selitä käsite "ohjelmisto liukuhihnoitus (software pipelining)". Anna esimerkki.
   5. Selitä käsite "haarautumisrekisteri (branch register)". Anna esimerkki.
   
    
4. [15 p] Riippuvuudet. Oletetaan, että RISC-arkkitehtuurin konekielen ALU-käskyissä on kolme rekisterioperandia ja että tulos menee aina ensiksi mainittuun (vasemmanpuoliseen) rekisteriin. Arkkitehtuuri on toteutettu (tavanomaisesti, ei superskalaarina) liukuhihnoitettuna siten, että parhaimmassa tapauksessa joka syklillä (cycle) saadaan yksi konekäsky valmiiksi.

   Tarkastellaan seuraavaa kääntäjän generoimaa käskysarjaa:

   	Load	R2, VarX	; Regs(R2) <- Mem(VarX)
   	Add	R5, R5, R2	; Regs(R5) <- Regs (R5) + Regs(R2)  
   	Move	R2, R6	; Regs(R2) <- Regs (R6)
   	Add	R3, R3, R2
   	Move	R7, R3
   	Mul	R3, R2, R5 
   	Jnzer	R2, Loop
    	Move	R1, R3
   	Add	R3, R2, R5 

   Useat seikat edellämainitussa koodisegmentissä voivat hidastaa suorittimen toimintaa maksiminopeudesta.
   1. [10 p] Kuvaile täsmällisesti allamainitut ongelmatyypit ja merkitse selkeällä tavalla kaikki kyseisen ongelmatyypin esiintymät em. käskysarjassa:
      • data-riippuvuudet (data dependencies)
      • rakenteelliset riippuvuudet (structural dependencies)
      • kontrolliriippuvuudet (control dependencies)
      Miten kustakin ongelmatyypistä aiheutuvaa ongelmia voidaan välttää tai niiden aiheuttamia suorituskykyä heikentäviä vaikutuksia vähentää?
       
   2. [5 p] Oletetaan nyt, että arkkitehtuuri toteutetaankin superskalaarina (superscalar). Kuvaile täsmällisesti allamainitut uudet ongelmatyypit ja merkitse selkeällä tavalla kaikki kyseisen ongelmatyypin esiintymät em. käskysarjassa.
      • kirjoitusriippuvuus (output dependencies)
      • antiriippuvuus (antidependencies)
      Miten kustakin uudesta ongelmatyypistä aiheutuvaa ongelmia voidaan välttää tai niiden aiheuttamia suorituskykyä heikentäviä vaikutuksia vähentää?
       

   Tee tarvittavat lisäoletukset ja kirjaa ne näkyviin.