Томасулов алгоритам
Томасулов алгоритам — алгоритам за сметачка архитектура наменет за динамичко распоредување на наредби што овозможува нивно нередоследно извршување и овозможува поефикасно користење на повеќе единици за извршување. Алгоритмот е развиен од страна на Роберт Томасуло во IBM во 1967 година и за првпат бил имплементиран во единицата со подвижна запирка, IBM System / 360 Model 91 .
Главните иновации на Томасуловиот алгоритам вклучуваат преименување на регистри во машинската опрема, резервирани станици за сите единици за извршување и заедничка магистрала за податоци (CDB) на која пресметаните вредности се емитуваат до сите резервирани станици кои можеби имаат потреба од истите. Овие случувања овозможуваат подобрено паралелно извршување на упатства кои инаку ќе одолговлекуваат при употреба на табела за резултат или други претходни алгоритми.
Роберт Томасуло, за неговата работа на алгоритмот, ја добил наградата Екерт-Моши во 1997 година.[1]
Концепти за имплементација
уреди
Следниве се концепти неопходни за имплементација на Томасуловиот алгоритам:
Заедничка податочна магистрала
уредиЗаедничката податочна магистрала ги поврзува резервираните станици директно со функционалните единици. Според Томасуло „таа го задржува првенството додека поттикнува конкурентност“.[2] :33 Ова има два важни ефекти:
- Функционалните единици можат да пристапат до резултатот од која било операција без вклучување на регистар со подвижна запирка, дозволувајќи им на повеќе единици што чекаат на резултат да продолжат без да чекаат да го решат спорот за пристап до регистрите за читање на податотеки.
- Распределувањето на опасностите и контролното извршување се дистрибуираат. Станиците за резервација контролираат кога наредбата може да се изврши, наместо една посветена единица за опасност.
Редослед на наредби
уредиНаредбите се издаваат последователно, така што ефектите од низа наредби, како што се исклучоците произлезени од овие наредби, се појавуваат во ист редослед каков што би го имале при извршување по ред, без оглед на фактот дека тие се извршуваат надвор од редослед, (пример: непоследователно).
Преименување на регистри
уредиТомасуловиот алгоритам го користи преименувањето на регистрите за правилно извршување вон редослед. Сите регистри за општа намена и резервација имаат или вистинска вредност или заменска вредност. Ако вистинската вредност не е достапна до регистарот на одредишта за време на фазата на издавање, првично се користи заменската вредност. Вредноста на заменувачот е ознака која означува која резерна станица ќе ја произведе вистинската вредност. Кога единицата завршува и го емитува резултатот на заедничката податочна магистрала, заменската вредност ќе биде заменета со вистинската вредност.
Секоја функционална единица има станица за резервација. Резервираните станици ги содржат информациите потребни за извршување на една наредба, вклучувајќи ја и операцијата и операндите. Функционалната единица започнува со обработка кога е слободна и кога сите извори на операнди потребни за наредбата се реални.
Исклучоци
уредиПрактично кажано, може да има исклучоци за кои не се достапни доволно информации за статусот на исклучокот, во тој случај обработувачот може да покрене посебен исклучок, наречен „непрецизен“ исклучок. Непредвидливите исклучоци не можат да се појават при имплементацијата на OoOE , бидејќи состојбата на обработувачот се менува само во редот на програмата (видете RISC Pipeline Exceptions).
Програми кои доживуваат „прецизни“ исклучоци, каде што може да се одреди конкретната наредба што го презела исклучувањето, може да се рестартира или повторно да се изврши од точката на исклучувањето. Сепак, оние што доживуваат „непрецизни“ исклучоци генерално не можат да се рестартираат или повторно да се извршат, бидејќи системот не може да ја одреди специфичната наредба што го презела исклучокот.
Упатство животен циклус
уредиТрите фази наведени подолу се фазите преку кои секоја наредба ги поминува од времето кога е издадена до времето кога нејзиното извршување е завршено.
Легенда
уреди- Ор - ја претставува операцијата што се изведува на операнди
- Qj, Qk - резервираната станица која ќе го произведе соодветниот извор на операнд (0 укажува дека вредноста е во Vj, Vk)
- Vj, Vk - вредноста на изворните операнди
- A - се користат за чување на информации за мемориската адреса за товар или продавница
- Зафатено - 1 ако е окупирано, 0 ако не е окупирано
- Qi - (само регистрирајте единица) резервација станица чиј резултат треба да се чуваат во овој регистар (ако празно или 0, нема вредности кои се наменети за овој регистар)
Фаза 1: издавање
уредиВо фазата на издавање, наредбите се издаваат за извршување, ако сите операнди и резервираните станици се подготвени, или пак тие се заглавени. Регистрите се преименувани во овој чекор, со што се елиминираат опасностите од WAR и WAW.
- Повратете ја следната наредба од главата на редот за наредби. Ако операндите со наредби во моментот се во регистрите, тогаш:
- Ако е достапна соодветна функционална единица, издадете ја наредбата.
- Инаку, бидејќи нема функционална единица, ја задржуваме наредбата сè додека станицата или бафер не се ослободи.
- Инаку, можеме да претпоставиме дека операндите не се во регистрите, и затоа се користат виртуелни вредности. Функционалната единица мора да ја пресмета вистинската вредност за да ги следи функционалните единици кои ги произведуваат операндите.
| Наставна состојба | Почекајте додека | Акција или книговодство |
|---|---|---|
| Проблем | Станица r | if (RegisterStat[rs].Qi¦0) {
RS[r].Qj ← RegisterStat[rs].Qi
}
else {
RS[r].Vj ← Regs[rs];
RS[r].Qj ← 0;
}
if (RegisterStat[rt].Qi¦0) {
RS[r].Qk ← RegisterStat[rt].Qi;
}
else {
RS[r].Vk ← Regs[rt]; RS[r].Qk ← 0;
}
RS[r].Busy ← yes;
RegisterStat[rd].Q ← r;
|
| Вчитај или чувај | Бафер r празен | if (RegisterStat[rs].Qi¦0) {
RS[r].Qj ← RegisterStat[rs].Qi;
}
else {
RS[r].Vj ← Regs[rs];
RS[r].Qj ← 0;
}
RS[r].A ← imm;
RS[r].Busy ← yes;
|
| Вчитај само | RegisterStat[rt].Qi ← r;
| |
| Само чувајте | if (RegisterStat[rt].Qi¦0) {
RS[r].Qk ← RegisterStat[rt].Qi;
}
else {
RS[r].Vk ← Regs[rt];
RS[r].Qk ← 0
};
|
Фаза 2: изврши
уредиВо фазата на извршување, операциите за наредбите се спроведуваат. Наредбите се одложуваат во овој чекор сè додека не се достапни сите операнди, со што се елиминираат опасностите од RAW. Коректноста на програмата се одржува преку делотворна пресметка на адреси за да се спречат опасностите преку меморијата.
- Ако еден или повеќе операнди сè уште не се достапни тогаш: почекајте операндот да стане достапен на заедничката податочна магистрала.
- Кога сите операнди се достапни, тогаш: ако наредбата е вчитување или чување
- Пресметајте ја делотворната адреса кога е достапен базниот регистар и ставете го во баферот за оптоварување / складирање
- Ако наредбата е вчитување тогаш: изврши веднаш штом мемориската единица е достапна
- Од друга страна, ако наредбата е чување тогаш: почекајте вредноста да се складира пред да ја испратите во мемориската единица
- Пресметајте ја делотворната адреса кога е достапен базниот регистар и ставете го во баферот за оптоварување / складирање
- Доколку, наредбата е операција со аритметичка логичка единица (АЛЕ) тогаш: извршете ја наредбата на соодветната функционална единица
| Наставна состојба | Почекајте додека | Акција или книговодство |
|---|---|---|
| ФП операција | (RS[r].Qj = 0) and (RS[r].Qk = 0)
|
Пресметај резултат: операндите се во Vj и Vk |
| Ставете / складирајте чекор 1 | RS[r]. Qj = 0 & r е на чело на редот за чување на оптоварување
|
RS[r].A ← RS[r].Vj + RS[r].A;
|
| Вчитај чекор 2 | Вчитај го чекор 1 целосно | Read from Mem[RS[r]. A]
|
Фаза 3: запишете резултат
уредиВо фазата на запишување на резултатите, резултатите од операциите на АЛЕ се запишуваат во регистрите, а операциите на складирање се запишуваат во меморијата.
- Ако наредбата е операција со АЛЕ
- Ако резултатот е достапен, тогаш: запишете го на заедничката податочна магистрала и од таму во регистрите и во која било резервирана станица која чека на овој резултат
- Инаку, ако наредбата е сочувување тогаш: запишете ги податоците во меморијата за време на овој чекор
| Состојба на наредбата | Почекајте додека | Акција или книговодство |
|---|---|---|
| ФП операција или вчитување | Извршувањето е завршено r & ЗМП на располагање | ∀x(if (RegisterStat[x].Qi = r) {
regs[x] ← result;
RegisterStat[x].Qi = 0
});
∀x(if (RS[x].Qj = r) {
RS[x].Vj ← result;
RS[x].Qj ← 0;
});
∀x(if (RS[x].Qk = r) {
RS[x].Vk ← result;
RS[x].Qk ← 0;
});
RS[r].Busy ← no;
|
| Сочувај | Извршувањето е завршено r & RS[r].Qk = 0 Qk = 0 | Mem[RS[r].A] ← RS[r].Vk;
RS[r].Busy ← no;
|
Подобрувања на алгоритмот
уредиКонцептите на резервирани станици, преименувањето на регистри и заедничката податочна магистрала во Томасуловиот алгоритам претставуваат значајни достигнувања во дизајнот на сметачите со голема моќ.
Резервираните станици ја преземаат одговорноста за чекање на операнди во присуство на зависности од податоци и други недоследности, како што се различно време за пристап до складирани податоци и брзини на ел. кола, со што се ослободуваат функционалните единици. Ова подобрување ги надминува одложувањата добиени од долги подвижни точки и пристапот до меморија. Особено алгоритмот е потолерантен за пропуштањата на кешот. Дополнително, програмерите се ослободуваат од спроведување на оптимизиран код. Ова е резултат на заедничката податочна магистрала и резервираната станица кои работат заедно за да се зачуваат зависности, како и поттикнување на конкурентноста.[2] :33
Со следење на операнди за наредби во резервацијата станици и регистрирајте се преименува во машински алгоритам минимизира читање по-запишување(RAW) и ја елиминира запишување-по-запишување (WAW) и Прати-по-Прочитај (војна) сметачка архитектура опасности . Ова ја подобрува ефикасноста со намалување на потрошеното време кое инаку би било потребно за боксови.[2] :33
Подеднакво важно подобрување во алгоритмот е и тоа што дизајнот не е ограничен на одредена структура на линијата. Ова подобрување овозможува алгоритмот да биде пошироко прифатен од обработувачи со повеќе проблеми. Дополнително, алгоритмот лесно се проширува за да овозможи шпекулација на гранки.[3] :182
Апликации и наследство
уредиТомасуловиот алгоритам, надвор од IBM, не бил користен неколку години по нејзината имплементација во архитектурата на System / 360 Model 91. Сепак, во текот на 1990-тите имало значително зголемување на употребата заради три причини:
- Откако кеширањето станало вообичаено, способноста на Томасуло за одржување на конкурентноста за време на непредвидливи времиња на оптоварување предизвикана од пропуштање на кеш станала важна во обработувачите.
- Динамичкиот распоред и шпекулациите на гранките овозоможил алгоритмот да помогне на обработнатувачката моќ, бидејќи обработувачите издале сè повеќе и повеќе наредби.
- Проширувањето на софтверот за масовен пазар значеше дека програмерите не би сакале да компајлираат за одредена структура на линијата. Алгоритмот може да функционира со која било архитектура на линијата и затоа софтверот бара неколку модификации специфични за архитектурата.[3] :183
Многу модерни обработувачи имплементираат шеми на динамичко распоредување кои се извод на оригиналниот алгоритам на Томасуло, вклучувајќи ги и популарните чипови Intel x86-64 .[5] [6]
Поврзано
уреди- Враќач за повторно нарачување (ROB)
- Паралелизам на ниво на наредби (ILP)
Наводи
уреди- ↑ „Robert Tomasulo – Award Winner“. ACM Awards. ACM. Посетено на 8 December 2014.
- ↑ 2,0 2,1 2,2 Tomasulo, Robert Marco (Jan 1967). „An Efficient Algorithm for Exploiting Multiple Arithmetic Units“. IBM Journal of Research and Development. IBM. 11 (1): 25–33. doi:10.1147/rd.111.0025. ISSN 0018-8646.
- ↑ 3,0 3,1 3,2 3,3 3,4 Hennessy, John L.; Patterson, David A. (2012). Computer Architecture: A Quantitative Approach. Waltham, MA: Elsevier. ISBN 978-0123838728.
- ↑ „CSE P548 - Tomasulo“ (PDF). washington.edu. Washington University. 2006. Посетено на 8 December 2014.
- ↑ (Report). Отсутно или празно
|title=(help) - ↑ Yoga, Adarsh. „Differences between Tomasulo's algorithm and dynamic scheduling in Intel Core microarchitecture“. The boozier. Посетено на 4 April 2016.
Дополнителна литература
уреди- Savard, John J. G. (2018) [2014]. „Pipelined and Out-of-Order Execution“. quadibloc. Архивирано од изворникот на 2018-07-03. Посетено на 2018-07-16.
Надворешни врски
уреди- Динамичкo распоредедување - Алгоритам на Томасуло Архивирано на 10 март 2014 г.
- HASE Јава аплет симулација на алгоритам Томасуло Архивирано на 11 септември 2013 г.