Контрольні запитання

1. Які методи дозволяють знизити вплив конфліктів за даними та по керуванню при використанні можливостей процесора паралелізму, закладеного у програмах?

2. Які типи залежностей можуть існувати між командами?

3. Що означає „залежність по іменах” між командами програми?

4. Які існують різновиди залежності по іменах?

5. У чому полягає залежність по керуванню між командами програми?

6. На чому фокусується увага при аналізі паралелізму на рівні циклу?

7. У чому полягає алгоритм розгортання циклів?

Рекомендована література

1. Самофалов и др. Основы теории многоуровневых конвеерных вычислительных систем. – К.,”Техніка”, 1980.

Лекція 9. Усунення залежностей по даним і механізми динамічного планування

План лекції

1. Основна ідея динамічної оптимізації.

2. Динамічна оптимізація із централізованою схемою виявлення конфліктів.

Виклад лекції

1. Основна ідея динамічної оптимізації

Головним обмеженням методів конвеєрної обробки, які ми розглядали раніше, є видача для виконання команд строго в порядку, запропонованому програмою: якщо виконання якої-небудь команди в конвеєрі припинялося, то випливаючі за нею команди також припинялися. Таким чином, при наявності залежності між двома близько розташованими в конвеєрі командами виникало припинення обробки багатьох команд. Але якщо є кілька функціональних пристроїв, багато хто з них можуть виявитися незавантаженими. Якщо команда j залежить від довгої команди i, що виконується в конвеєрі, то всі команди, що випливають за командою j повинні призупинитися доти, поки команда i не завершиться й не почне виконуватися команда j. Наприклад, розглянемо наступну послідовність команд:

DIVD F0,F2,F4

ADDD F10,F0,F8

SUBD F8,F8,F14

Команда SUBD не може виконуватися через те, що залежність між командами DIVD і ADDD привела до призупинки конвеєра. Однак команда SUBD не має ніяких залежностей від команд у конвеєрі. Це обмеження продуктивності, що може бути усунуто зняттям вимоги про виконання команд у суворому порядку.

У розглянутому нами конвеєрі структурні конфлікти й конфлікти за даними перевірялися під час стадії декодування команди (ID). Якщо команда могла нормально виконуватися, вона видавалася із цього щабля конвеєра в наступні. Щоб дозволити почати виконання команди SUBD з попереднього приклада, необхідно розділити процес видачі на дві частини: перевірку наявності структурних конфліктів і очікування відсутності конфлікту за даними. Коли ми видаємо команду для виконання, ми можемо здійснювати перевірку наявності структурних конфліктів; таким чином, ми усе ще використовуємо впорядковану видачу команд. Однак ми хочемо почати виконання команди як тільки стануть доступними її операнди. Таким чином, конвеєр буде здійснювати неупорядковане виконання команд, що означає й неупорядковане завершення команд.

Неупорядковане завершення команд створює основні труднощі при обробці виняткових ситуацій. У розглянутих в даному дослідженні машинах з динамічним плануванням потоку команд переривання будуть неточними, оскільки команди можуть завершитися до того, як виконання більш ранньої виданої команди викличе виняткову ситуацію. Таким чином, дуже важко повторити запуск після переривання. Замість того, щоб розглядати ці проблеми негайно, ми обговоримо можливі рішення для реалізації точних переривань пізніше в контексті машин, що використають планування по припущенню.

Щоб реалізувати неупорядковане виконання команд, ми розщеплюємо щабель ID на два щаблі:

1. Видача - декодування команд, перевірка структурних конфліктів.

2. Читання операндів - очікування відсутності конфліктів за даними й наступне читання операндів.

Потім, як і в розглянутому нами конвеєрі, треба щабель EX. Оскільки для виконання команд ПК може знадобидись декілька тактів залежно від типу операції, ми повинні знати, коли команда починає виконуватися і коли закінчується. Це дозволяє декільком командам виконуватися в той самий момент часу. На додаток до цих змін структури конвеєра ми змінимо і структуру функціональних пристроїв, змінюючи кількість пристроїв, затримку операцій і ступінь конвеєризації функціональних пристроїв так, щоб краще використати ці методи конвеєризації.