581365-8 Tietokoneen rakenne, kurssikuulustelu 1.11.2002                    [ Other side in English]

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

1. [12 p] Boothin algorithmi kokonaislukujen kertolaskuun.
   1. [6 p] Mikä on Boothin algoritmin perusidea?
   2. [2 p] Näytä esimerkkinä, miten algoritmi toimii kertolaskun 27*27 yhteydessä.
   3. [2 p] Milloin Boothin algoritmi on nopeampi kuin tavanomainen ratkaisu? Anna esimerkki.
   4. [2 p] Milloin Boothin algoritmi on hitaampi kuin tavanomainen ratkaisu? Anna esimerkki.
       
2. [12 p] Välimuisti (cache) ja TLB
   1. [2 p] Mitä yhteistä on välimuistilla ja TLB:llä? Mitkä ovat suurimmat erot?
   2. [2 p] Miten paikallisuusominaisuudet vaikuttavat välimuistin ja TLB:n toteutukseen? Onko niissä jotain eroja?
   3. [2 p] Mitä hyötyä on siitä, että välimuistin lohkon (rivin) pituus on iso?
   4. [2 p] Mitä hyötyä on siitä, että joukkoassosiatiivisen TLB:n joukon koko on iso?
   5. [2 p] Mitä hyötyä on siitä, että välimuisteja olisi useampaa tasoa?
   6. [2 p] Mitä tarkoittaa käsite "erillinen välimuisti" (split cache)? Miten TLB suhtautuu siihen?
       
3. [12 p] Langoitettu ja mikro-ohjelmoitu kontrolli (hardwired and microprogrammed control)
1. [3 p] Minkä ongelman kontrolli ratkaisee?
2. [3 p] Mitä yhteistä on langoitetussa ja mikro-ohjelmoidussa kontrollissa?
3. [2 p] Mitä haittoja langoitetussa kontrollissa on verrattuna mikro-ohjelmoituun kontrolliin?
4. [2 p] Mitä etuja langoitetussa kontrollissa on verrattuna mikro-ohjelmoituun kontrolliin?
5. [2 p] Mikro-ohjelmoidussa kontrollissa on käsitteet vaakasuora (horizontal) ja pystysuora (vertical) mikrokoodi. Sopivatko vastaavat käsitteet myös langoitettuun kontrolliin? Jos sopivat, niin mitä ne kuvaavat. Jos eivät sovi, niin miksi ei?
    
4. [12 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
   	Mul	R3, R2, R5 
   	Jnzer	R2, Loop
   	Add	R3, R2, R5 

   Useat seikat edellämainitussa koodisegmentissä voivat hidastaa suorittimen toimintaa maksiminopeudesta.
   1. [6 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. [3 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ää?
       
   3. [3 p] Oletetaan nyt, että kyseiselle arkkitehtuurille on toteutettu funktionaalisesti oikein toimiva emulaattori. Emulaattori on toteutettu tavanomaisen von Neumann -arkkitehtuurin mukaisesti, joten siinä suoritetaan annettua konekielistä koodia yksi konekäsky kerrallaan. Mitkä kohtien (a) ja (b) käskyjen välisistä riippuvuuksista tulee emuloinnissa ottaa huomioon ja millä tavoin? Perustele vastauksesi.

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