Томасуло алгоритам

Томасуло алгоритам је хардверски алгоритам којег је 1967. развио Роберт Томасуло у IBM. Овај алгоритам омогућава секвенцијалне инструкције које би иначе биле заустављене због одређених зависности. Прва имплементација је била у јединици покретног зареза у систему IBM Систем/360 – Модел 91.

Овај алгоритам се разликује од scoreboarding-а зато што користи преименовање регистара. Тамо где scoreboarding решава опасности писања након писања, читања након писања и писања након читања стопирањем, преименовање регистара омогућава континуирано издавање инструкција. Томасуло алгоритам такође користи заједнички бус података на ком су израчунате вредности пребачене свим станицама резервације где су потребне. Ово омогућава боље паралелно извршавање инструкција које би иначе биле заустављене приликом коришћења scoreboarding-а.

Роберт Томасуло је добио Екерт-Мучли награду 1997. за овај алгоритам.

Концепти имплементације

Следећи концепти су обавезни за имплементацију Томасуло алгоритма:

Инструкције се издају секвенцијално тако да ефекти секвенце инструкција као што су изузеци подугнути од стране ових инструкција се дешавају у истом реду као што би и у нормалном процесору, без обзира на то што се извршавају ванредно.
Сви обични и регистри резервације станице држе или реалну или виртуелну вредност. Ако ре јеална вредност недоступна дестинацијском регистру током фазе издавања, виртуелна вредност је користи у почетку. Функционална јединица која рачуна реалне вредности је постављена за виртуелну вредност. Вредности виртуелног регистра су конвертовани у реалне вредности чим функционална јединица заврши своје рачунање.
Функционалне јединице користе резервационе станице са више слотова. Сваки слот садржи информацију која је потребна за извршавање једне инструкције, укључујући операцију и операнде. Функционална јединица почиње са обрадом када је слободна и када су сви изворни операнди потребни за инстуркцију реални.

Животни циклус инструкције

Следе фазе кроз које мора да прође свака инструкција од времена кад је издата до завршетка.

Фаза 1: издавање

У овој фази, инструкције се издају за извршавање ако су сви операнци и резервационе станице спремне или ако су заустављене. Регистри су преименовани у овом кораку, елиминишући WAR и WAW опасности.

Врати следећу инструкцију из почетка инструкционог реда. Ако су операнди инструкције тренутно у регистрима, онда
- Ако је одговарајућа функционална јединица доступна, издај инструкцију.
- У супротном случају, заустави инструкцију док станица или бафер не буду слободни.
У супротном случају, можемо претпоставити да операнди нису у регистрима, зато користимо виртуелне врености. Функционална јединица мора израчунати реалну вреност, како би чувала функционалне јединице које ће направравити операнд.

Фаза 2: извршавање

У овој фази операнди инструкције се износе. Инструкције се одлажу у овом кораку док сви њихови операнди не постану доступни, што елиминише RAW опасност. Тачност програма је одржана кроз ефективну калкулацију адресе да би се спречиле опасности кроз меморију.

Ако један или више операнада није доступан сачекај да операнд постане доступан.
Када су сви операнди доступни, онда ако је инструкције читање или писање
- израчунај ефективну адресу када је базни регистар доступан, и постави га у бафер за чување и вађење
  - Ако је инстукција увезена, изврши је чим меморијска јединица постане доступна
  - Ако није, сачекај да вредност буде постављена пре него што је пошаљеш у меморијску јединицу
У супротном случају, инструкција је АЛУ операција и изврши је на одговарајућој функционалној јединици.

Фаза 3: исписивање резултата

У овој фази, резултати АЛУ операција се исписују назад у регистре и операције чувања се исписују назад у меморију.

Ако је инструкција била АЛУ операција
- Ако је резултат доступан, напиши га у ЦДБ и одатле у регистре и било коју резервациону станицу која чека овај резултат.
У супротном случају, пиши податке у меморију.

Литература

An Efficient Algorithm for Exploiting Multiple Arithmetic Units Архивирано на сајту Wayback Machine (19. јул 2013), IBM Journal of Research and Development, 11(1):25-33, January 1967.
WebHASE: Tomasulo's Algorithm: HASE Java applet simulation of the Tomasulo's Algorithm Архивирано на сајту Wayback Machine (11. септембар 2013), Institute for Computing Systems Architecture, Edinburgh University.
TOMASULO'S ALGORITHM FOR DYNAMIC SCHEDULING
Computer Architecture: A Quantitative Approach, John L. Hennessy & David A. Patterson

Спољашње везе

Dynamic Scheduling - Tomasulo's Algorithm Архивирано на сајту Wayback Machine (10. март 2014)
Web based Java demo of Tomasulo's algorithm