581365-8 Tietokoneen rakenne, erilliskoe 16.1.2004  

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

1. [14 p] Boothin algoritmi kokonaislukujen kertolaskuun.
   1. [2 p] Minkä ongelman Boothin algoritmi ratkaisee?
   2. [6 p] Miten Boothin algoritmi toimii?
   3. [2 p] Mitä Boothin algoritmissa tapahtuu kertolaskun 60*60 tapauksessa? (Lukujen desimaaliarvo on siis 60)
   4. [2 p] Miksi Boothin algoritmi on parempi kuin perinteinen ratkaisu? Anna kuvaava esimerkki.
   5. [2 p] Onko tilanteita, joissa perinteinen ratkaisu olisi parempi tai yhtä hyvä kuin Boothin algoritmiin perustuva ratkaisu? Anna kuvaava esimerkki.
   
    
2. [16 p] Ehdottomat hypyt ja ehdolliset haarautumiset aiheuttavat ongelmia liukuhihnoitetuissa suorittimissa. Näitä ongelmia on ratkottu usealla eri tavalla. Kerro kustakin allamainitusta ratkaisumenetelmästä, (i) minkä ongelman se ratkaisee, (ii) miten ratkaisu on toteutettu sekä (iii) ratkaisun hyvät/huonot puolet.
   1. [2 p] Viivästetty haarautuminen (delayed branch)
   2. [2 p] Silmukkapuskuri (loop buffer)
   3. [2 p] Ennakoiva käskyn nouto (prefetch branch target)
   4. [2 p] Haarautumisen ennustaminen (branch prediction)
   5. [2 p] Haarautumisen historiataulu (branch history table)
   6. [2 p] IA-64:n predikoitu suoritus (predicated execution)
   7. [2 p] IA-64:n data spekulointi (data speculation)
   8. [2 p] IA-64:n haarautumisrekisteri (branch register)
       
       
3. [15 p] Välimuisti. Oletetaan, että (epärealistisen pienessä välimuistiratkaisussa) 4-tavuisen sanan 8-bittinen tavuosoite on 0xB6 (heksadesimaali B6). Välimuistin koko on 128 tavua ja rivin pituus (cache line size) on 16 tavua. Tee (kuvallinen) esimerkki ja näytä miten viitattu muistipaikka löytyy välimuistista, kun käytössä on
   1. [5 p] Suoraa kuvausta (direct mapping) käyttävä kuvausfunktio (mapping function)?
   2. [5 p] Täysin assosiatiivista (associative or fully associative) kuvausta käyttävä kuvausfunktio.
   3. [5 p] Joukkoassosiatiivista kuvausta joukon koolla 2 (2-way set associative mapping) käyttävä kuvausfunktio?
   Voit olettaa esimerkissäsi, että viitattu muistipaikka löytyy välimuistista.
   Mitkä ovat eri osoitekenttien nimet/pituudet kunkin kuvaustyypin yhteydessä?
   Missä kaikkialla kyseinen muistipaikka voi välimuistissa sijaita kunkin kuvaustyypin yhteydessä?
   
   
4. [15 p] Langoitettu kontrolli (hardwired control)
   1. [2 p] Minkä ongelman (langoitettu) kontrolli ratkaisee?
   2. [7 p] Miten langoitettu kontrolli toimii? Anna (kuvallinen) esimerkki.
   3. [2 p] Mitä ongelmia langoitetussa kontrollissa on verrattuna mikro-ohjelmoituun (microprogrammed) kontrolliin?
   4. [2 p] Mitä etuja langoitetussa kontrollissa on verrattuna mikro-ohjelmoituun (microprogrammed) kontrolliin?
   5. [2 p] Kannattaisiko RISC suoritin toteuttaa langoitetulla vai mikro-ohjelmoidulla kontrollilla? Miksi?