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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Алгоритм Томасуло — це алгоритм, який використовується в комп'ютерній архітектурі апаратного забезпечення, для динамічного планування команд, яке передбачає позачергове виконання, з метою ефективного використання функціональних блоків процесора. Алгоритм був розроблений Робертом Томасуло у 1967 році, коли він працював в IBM, і вперше реалізований в IBM System/360 Model 91 в блоці операцій з рухомою комою.

Головними нововведеннями алгоритму Томасуло є перейменування регістрів в апаратних засобах, блоки резервування[en] для всіх функціональних блоків, і спільна шина даних (СШД), по якій обчислені значення синхронно передаються в усі блоки резервування, які можуть мати потребу в них. Ці зміни підвищили ефективність паралельного виконання інструкцій, виконання яких, при використанні методу scoreboarding[en] або більш ранніх алгоритмів, призводили до зупинки.

У 1997 році Роберт Томасуло отримав нагороду Еккерта-Моклі[en] за розробку алгоритму.[1]

Концепції реалізації[ред.ред. код]

Блок обчислень з рухомою комою Томасуло

Нижче наведені поняття, необхідні для реалізації алгоритму Томасуло:

Загальна шина даних[ред.ред. код]

Загальна шина даних (ЗШД) з'єднує блок резервування безпосередньо з функціональними блоками. На думку Томасуло це «зберігає пріоритет при одночасному стимулюванні паралелізму».[2]:33 Це має два важливих наслідки:

  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
};

[3]:180

Приклад Алгоритму Томасуло[4]

Етап 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] :180

Стадія 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;

[3] :180

Покращення алгоритмів[ред.ред. код]

Поняття резервування, перейменування регістрів, та загальної шини даних в алгоритмі Томасуло представляє значний прогрес в проектуванні високопродуктивних комп'ютерів.

Блоки резервування беруть на себе відповідальність очікування операндів в присутності залежностей даних і інших невідповідностей, таких як зміни часу доступу до пам'яті і швидкості ланцюга, тим самим звільняючи функціональні блоки. Це поліпшення долає довгі затримки з рухомою комою і доступом до пам'яті. Зокрема, алгоритм більш терпимо відноситься до помилок кеша. Крім того, програмісти звільняються від реалізації оптимізованого коду. Це є результатом того, що загальна шина даних і блоки резервування працюють разом, щоб зберегти залежності, а також заохочення паралелізму.[2]:33

Відстежуючи операнди для інструкцій в резервуванні і перейменовуючи регістри в апаратних засобах алгоритм зводить до мінімуму небезпеки (читання після запису (RAW) і усуває запис після запису (WAW) і запис після читання (WAR)) комп'ютерної архітектуриs. Це підвищує продуктивність за рахунок скорочення втрат часу, які могли б бути викиликані зупинками. [2]:33

Не менш важливе поліпшення алгоритму це те, що проектування не обмежується певною структурою комунікаційних ліній. Це поліпшення дозволяє алгоритму бути більш широко використовуваним процесорами багатьох випусків. Крім того, алгоритм легко розширюється, щоб включити додаткові галузі.[3] :182

Програми та спадщина[ред.ред. код]

Алгоритм Томасуло, за межами IBM, не використовувався протягом декількох років після його впровадження в системі / 360 Model 91 архітектури. Проте, він побачив величезне збільшення використання протягом 1990-х років згідно 3 причин:

  1. Після того, як кеш став звичайною справою, здатність алгоритму Томасуло підтримувати паралельність під час непередбачуваних навантажень, викликаних кеш-промахами стала цінною в процесорах.
  2. Динамічне планування і додаткові галузі, що алгоритм дозволяє, допомогли виконанню, адже процесори випускали більше і більше команд.
  3. Поширення програмного забезпечення для масового ринку означає, що програмісти не хотіли компілювати для конкретної структури комунікаційних ліній. Алгоритм може працювати з будь-якою архітектурою комунікаційних лінійі, таким чином, програмне забезпечення вимагає кілька архітектур конкретних модифікацій.[3] :183

Багато сучасних процесорів реалізують динамічні схеми планування, які є похідними від оригінального алгоритму Томасуло, в тому числі популярні Intel-64 чипи.[5] [6]

Див. також[ред.ред. код]

Додаткові посилання[ред.ред. код]

Посилання[ред.ред. код]

  1. Robert Tomasulo – Award Winner. ACM Awards. ACM. Процитовано 8 December 2014. 
  2. а б в Tomasulo, Robert M. (Jan 1967). An Efficient Algorithm for Exploiting Multiple Arithmetic Units. IBM Journal of Research and Development 11 (1) (IBM). с. 25–33. ISSN 0018-8646. doi:10.1147/rd.111.0025. 
  3. а б в г д Hennessy, John L.; Patterson, David A. (2012). Computer Architecture: A Quantitative Approach. Waltham, MA: Elsevier. ISBN 978-0123838728. 
  4. CSE P548 - Tomasulo. washington.edu. Washington University. 2006. Процитовано 8 December 2014. 
  5. Intel® 64 and IA-32 Architectures Software Developer’s Manual. Intel. September 2014. Процитовано 8 December 2014. 
  6. Yoga, Adarsh. Differences between Tomasulo's algorithm and dynamic scheduling in Intel Core microarchitecture. The boozier. Процитовано 4 April 2016. 
CC-logo.svg

Ця стаття містить текст, перекладений зі статті Будь ласка, вкажіть назву статті англійської Вікіпедії.

Icono de traducción.svg