Алгоритм Томасуло
Алгоритм Томасуло — алгоритм, який використовується в комп'ютерній архітектурі апаратного забезпечення, для динамічного планування команд, яке передбачає позачергове виконання, з метою ефективного використання функціональних блоків процесора. Алгоритм був розроблений Робертом Томасуло у 1967 році, коли він працював в IBM, і вперше реалізований в IBM System/360 Model 91 в блоці операцій з рухомою комою.
Головними нововведеннями алгоритму Томасуло є перейменування регістрів в апаратних засобах, блоки резервування[en] для всіх функціональних блоків, і спільна шина даних (СШД), по якій обчислені значення синхронно передаються в усі блоки резервування, які можуть мати потребу в них. Ці зміни підвищили ефективність паралельного виконання інструкцій, виконання яких, при використанні методу scoreboarding[en] або більш ранніх алгоритмів, призводили до зупинки.
У 1997 році Роберт Томасуло отримав нагороду Еккерта-Моклі за розробку алгоритму.[1]
Концепції реалізації ред.
Нижче наведені поняття, необхідні для реалізації алгоритму Томасуло:
Загальна шина даних ред.
Загальна шина даних (ЗШД) з'єднує блок резервування безпосередньо з функціональними блоками. На думку Томасуло це «зберігає пріоритет при одночасному стимулюванні паралелізму».[2] Це має два важливих наслідки:
- Функціональні одиниці можуть отримати доступ до результату будь-якої операції, без участі регістра з рухомою комою, що дозволяє кільком пристроям, які очікують на результат, продовжити роботу не чекаючи вирішення неузгодженості для доступу до регістрового файлу порту читання.
- Виявлення небезпек і контроль виконання розподілення. Блоки резервування контролюють такі ситуації, коли команда може виконатись швидше, ніж виділиться хоча б один блок небезпеки.
Порядок інструкції ред.
Інструкції видаються послідовно, так що ефекти послідовності інструкцій, такі як виключення, викликані цими інструкціями, виникають в тому ж порядку, як і на послідовному процесорі, незалежно від того, що вони виконуються позачергово (тобто не послідовно).
Перейменування регістрів ред.
Алгоритм Томасуло використовує перейменування регістрів, щоб правильно зробити паралельне виконання. Всі регістри загального призначення і блоки резервування містять або реальне значення, або значення заповнювача. Якщо реальне значення недоступно в регістрі призначення на стадії випуску, спочатку використовуються значення заповнювача. Значення заповнювача — це тег, який вказує блок резервування, який буде виробляти реальне значення. Коли пристрій завершує і передає результат на ЗШД, заповнювач буде замінений реальним значенням.
Кожен функціональний блок має один блок резервування. Блок резервування містить інформацію, необхідну для виконання однієї команди, в тому числі операції і операндів. Функціональний блок починає обробку, коли він вільний, і коли всі вихідні операнди, необхідні для навчання, реальні.
Винятки ред.
З практичної точки зору, можуть бути такі винятки, для яких не вистачає інформації про статус виключення, і в цьому випадку процесор може виклакати спеціальне виключення, яке називається «неточне» виключення. Неточні виключення не можуть відбуватися у не позачерговому виконанні реалізації, так як стан процесора змінюється тільки в програмному порядку (див Конвеєр команд).
Програми, які виявляють «точний» виняток, де може бути визначена конкретна команда, яка спонукає виняток, можуть бути перезавантаженими або повторно виконаними в точці виключення. Проте, ті, які виявляють «неточні» винятки, як правило, не можуть бути перезавантаженими або повторно виконаними, так як система не може визначити конкретні інструкції, які мали виняток.
Життєвий цикл інструкції ред.
Три етапи, які перераховані нижче — це етапи, через які проходить кожна інструкція з моменту видачі до її успішного виконання.
Позначення ред.
- Op — представляє операцію, яка виконується над операндами
- Qj, Qk -блок резервування, який буде виробляти відповідний операнд-джерело (0 вказує, що значення знаходиться в Vj, Vk)
- Vj, Vk — значення початкових операндів
- A — використовується для зберігання інформації про адресу пам'яті для завантаження або зберігання
- Busy — 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[rs].Qi;
}
else {
RS[r].Vk ← Regs[rt];
RS[r].Qk ← 0
};
|
Етап 2: Виконання ред.
У стадії виконання, операції інструкцій виконуються. Інструкції затримуються на цьому етапі, доки всі їхні операндів не будуть доступні, виключаючи RAW небезпеки. Правильність програми підтримується за рахунок ефективного обчислення адреси для запобігання небезпеки через пам'ять.
- Якщо один або кілька операндів ще не доступні, то: чекати, доки операнд стане доступним на ЗШД.
- Коли всі операнди доступні, то: якщо команда є завантаженням або зберіганням
- Обчислити ефективну адресу, коли базовий регістр доступний, і помістіть його в буфері завантаження / зберігання
- Якщо команда завантаження, то: виконати, як тільки блок пам'яті доступний
- В іншому випадку, якщо інструкція зберігання, то: чекати значення, яке буде зберігатися, перед відправкою його в блок пам'яті
- Обчислити ефективну адресу, коли базовий регістр доступний, і помістіть його в буфері завантаження / зберігання
- В іншому випадку, команда представляє собою операцію арифметико-логічного блока (АЛП): виконати команду у відповідному функціональному блоці.
Псевдо-код ред.
| Стан інструкції | Зачекайте доки | Дія |
|---|---|---|
| FP операція | (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 виконаний | Читати з Mem[RS[r].A]
|
Стадія 3: Записати результат ред.
На стадії запису результату, результати операції АЛУ записуються назад в регістри і операції зберігання записуються назад в пам'ять.
- Якщо команда була операція АЛУ
- Якщо результат доступний, то: записати його на ЗШД і звідти в регістри і блоки резервування які чекають на цей результат
- В іншому випадку, якщо це була команда зберігання, то: записати дані в пам'ять.
Псевдо-код ред.
| Стан інструкції | Зачекайте доки | Дія |
|---|---|---|
| FP операція або завантаження | Виконання завершується при доступних 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 | Mem[RS[r].A] ← RS[r].Vk;
RS[r].Busy ← no;
|
Покращення алгоритмів ред.
Поняття резервування, перейменування регістрів, та загальної шини даних в алгоритмі Томасуло становить значний прогрес у проектуванні високопродуктивних комп'ютерів.
Блоки резервування беруть на себе відповідальність очікування операндів в присутності залежностей даних і інших невідповідностей, таких як зміни часу доступу до пам'яті і швидкості ланцюга, тим самим звільняючи функціональні блоки. Це поліпшення долає довгі затримки з рухомою комою і доступом до пам'яті. Зокрема, алгоритм більш терпимо ставиться до помилок кешу. Крім того, програмісти звільняються від реалізації оптимізованого коду. Це є результатом того, що загальна шина даних і блоки резервування працюють разом, щоб зберегти залежності, а також заохочення паралелізму[2].
Відстежуючи операнди для інструкцій в резервуванні і перейменовуючи регістри в апаратних засобах алгоритм зводить до мінімуму небезпеки (читання після запису (RAW) і усуває запис після запису (WAW) і запис після читання (WAR)) комп'ютерної архітектури. Це підвищує продуктивність за рахунок скорочення втрат часу, які могли б бути викликані зупинками. [2]
Не менш важливе поліпшення алгоритму це те, що проектування не обмежується певною структурою комунікаційних ліній. Це поліпшення дозволяє алгоритму бути більш широко використовуваним процесорами багатьох випусків. Крім того, алгоритм легко розширюється, щоб включити додаткові галузі.[3]
Сучасне застосування ред.
За межами IBM алгоритм Томасуло не використовувався протягом декількох років після його впровадження в System/360 Model 91. Проте, починаючи з 1990-х років, застосування суттєво зростає, з наступних причин:
- Після того, як кеш став звичайною справою, здатність алгоритму Томасуло підтримувати паралельність під час непередбачуваних навантажень, викликаних кеш-промахами, стала цінною в процесорах.
- Динамічне планування і спекулятивне розгалуження дозволило суттєво підняти швидкодію процесорів.
- Поширення програмного забезпечення для масового ринку, що розповсюджується у вигляді двійкового коду: випуск різних версій ПЗ під процесори, що відрізняються структурою конвеєра, був недоцільним (в тому числі через складність для користувачів, що інсталюють програму) чи економічно невигідним. Реалізація позачергового виконання команд безпосередньо у процесорі дозволяє значною мірою уніфікувати бінарний код (тонкі архітектурні оптимізації, як правило, робляться лише у найбільш критичних до швидкодії місцях програми).[3]
Багато сучасних процесорів реалізують динамічні схеми планування, які є похідними від оригінального алгоритму Томасуло, в тому числі популярні процесори архітектури x86.[5][6]
Примітки ред.
- ↑ Robert Tomasulo – Award Winner. ACM Awards. ACM. Архів оригіналу за 14 грудня 2014. Процитовано 8 грудня 2014.
- ↑ а б в Tomasulo, Robert M. (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.
- ↑ а б в г д 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. Архів оригіналу (PDF) за 8 лютого 2016. Процитовано 8 грудня 2014.
- ↑ Intel® 64 and IA-32 Architectures Software Developer’s Manual (Звіт). Intel. September 2014. Архів оригіналу за 9 грудня 2014. Процитовано 8 грудня 2014.
- ↑ Yoga, Adarsh. Differences between Tomasulo's algorithm and dynamic scheduling in Intel Core microarchitecture. The boozier. Архів оригіналу за 17 квітня 2016. Процитовано 4 квітня 2016.
Див. також ред.
Посилання ред.
- Динамічне планування — Алгоритм Томасуло [Архівовано 10 березня 2014 у Wayback Machine.]
- HASE Java аплет моделювання алгоритму Томасуло [Архівовано 11 вересня 2013 у Wayback Machine.]