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

1. Яке визначення точного переривання у конвеєрі?

2. Чи є підтримка точних переривань обов’язковою вимогою і у яких випадках?

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

4. Які особливості виявлення конфліктів і організації прискореного пересилання даних у довгих конвеєрах?

5. Які існують підходи до забезпечення точних переривань при конвеєрній обробці в умовах позачергового завершення команд?

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

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

Лекція 8. Паралелелізм на рівні виконання команд, планування завантаження конвеєра та методика розгортання циклів

План лекції

1. Паралелізм на рівні виконання команд, планування завантаження конвеєра та методика розгортання циклів.

2. Паралелізм рівня команд: залежності й конфлікти за даними.

3. Паралелізм рівня циклу: концепції та методи.

4. Основи планування завантаження конвеєра й розгортання циклів.

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

1. Паралелізм на рівні виконання команд, планування завантаження конвеєра та методика розгортання циклів

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

Для початку запишемо вираження, що визначає середню кількість тактів для виконання команди в конвеєрі:

CPI конвеєра = CPI ідеального конвеєра +

+ Припинення через структурні конфлікти +

+ Припинення через конфлікти типу RAW +

+ Припинення через конфлікти типу WAR +

+ Припинення через конфлікти типу WAW +

+ Припинення через конфлікти по керуванню

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

Перш, ніж почати розгляд цих методів, необхідно визначити концепції, на яких ці методи побудовані.

2. Паралелізм рівня команд: залежності й конфлікти за даними

Всі розглянуті тут методи використовують паралелізм, закладений у послідовності команд. Як ми встановили вище цей тип паралелізму називається паралелізмом рівня команд. Ступінь паралелізму, доступна усередині базового блоку (лінійної послідовності команд, переходи із зовні якої дозволені тільки на її вхід, а переходи усередині якої дозволені тільки на її вихід) досить мала. Наприклад, середня частота переходів у цілочисельних програмах становить близько 16%. Це означає, що в середньому між двома переходами виконуються приблизно п'ять команд. Оскільки ці п'ять команд можливо взаємозалежні, то ступінь перекриття, що ми можемо використати усередині базового блоку, можливо буде менше ніж п'ять. Щоб одержати істотне поліпшення продуктивності, ми повинні використати паралелізм рівня команд одночасно для декількох базових блоків.

Метод	Знижує
Розгортання циклів	Припинення по керуванню
Базове планування конвеєра	Припинення RAW
Динамічне планування із централізованою схемою керування	Припинення RAW
Динамічне планування з перейменуванням регістрів	Припинення WAR і WAW
Динамічне прогнозування переходів	Припинення по керуванню
Видача декількох команд в одному такті	Ідеальний CPI
Аналіз залежностей компілятором	Ідеальний CPI і припинення за даними
Програмна конвеєризація й планування трас	Ідеальний CPI і припинення за даними
Виконання по припущенню	Всі припинення за даними й керуванню
Динамічне усунення неоднозначності пам'яті	Припинення RAW, пов'язані з пам'яттю

Рис. 1.

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

for (i = 1; i <= 1000; i = i + 1)

x[i] = x[i] + y[i];

Кожна ітерація циклу може перекриватися з будь-якою іншою ітерацією, хоча усередині кожної ітерації циклу практична можливість перекриття невелика.

Є кілька методів для перетворення такого паралелізму рівня циклу в паралелізм рівня команд. Ці методи засновані головним чином на розгортанні циклу або статично, використовуючи компілятор, або динамічно за допомогою апаратури. Нижче в цьому розділі ми розглянемо докладний приклад розгортання циклу.

Важливим альтернативним методом використання паралелізму рівня команд є використання векторних команд. По суті векторна команда оперує з послідовністю елементів даних. Наприклад, наведена вище послідовність на типовій векторній машині може бути виконана за допомогою чотирьох команд: двох команд завантаження векторів x і y з пам'яті, однієї команди додавання двох векторів і однієї команди запису вектора-результату. Звичайно, ці команди можуть бути конвеєризованими й мати відносно більші затримки виконання, але ці затримки можуть перекриватися. Векторні команди й векторні машини заслуговують окремого розгляду, що виходить за рамки даного курсу. Хоча розробка ідей векторної обробки передувала появі більшості методів використання паралелізму, які тут розглядаються, машини, що використовують паралелізм рівня команд поступово заміняють машини, що базуються на векторній обробці. Причини цього зрушення технології обговорюються більш детально пізніше в даному курсі.