Огляд методів оптимізації коду для процесорів з підтримкою паралелізму на рівні команд

Шумаков С.М.

Вступ

Процесори, здатні одночасно і незалежно виконувати кілька команд, мають виключно високим потенціалом продуктивності і знаходять все більше широке застосування. Про процесорах такого типу кажуть, що вони підтримують паралелізм на рівні команд (Instruction Level Parallelism, ILP). Далі, щоб стислості вони будуть називатися ILP-процесорами. Клас ILP-процесорів включає суперскалярні процесори і процесори з дуже довгим командним словом (Very Large Instruction Word, VLIW), до числа яких належать, зокрема, багато моделі цифрових процесорів обробки сигналів (ЦПОСІ).

Важливе перевага ILP в порівнянні з паралелізмом багатопроцесорних архітектур полягає в тому, що програмний паралелізм на рівні команд витягується (апаратурою або компілятором) автоматично, без додаткових зусиль з боку прикладних програмістів, у той час як використання паралелізму багатопроцесорних архітектур на увазі переписування програм.

Для реального використання високої продуктивності ILP-процесорів необхідні компілятори з мов високого рівня, здатні генерувати ефективний код. Застосування одних лише традиційних методів оптимізації коду виявляється абсолютно недостатнім. Наприклад, згідно з [3] або [41], типовий компілятор для ЦПОСІ (що підтримує тільки традиційні оптимізації) генерує код, який за часом виконання може поступатися оптимальному в 5-10 і більше разів.

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

В розділі 2 дається короткий огляд ILP-процесорів та їх основних характеристик. Розділ 3 присвячений критеріям оптимізації коду для ILP-процесорів. У розділі 4 представлена зразкова схема роботи компілятора, характеризуються основні завдання, пов'язані з оптимізацією коду для ILP-процесорів. У розділі 5 дається огляд способів формування областей (фрагментів модульна програми), в рамках яких можливе ефективне розпаралелювання. У розділі 6 описуються методи оптимізації, спрямовані на посилення внутрішнього програмного паралелізму в рамках виділених областей. У розділі 7 розглядаються методи розпаралелювання коду в попередньо виділених областях. Розділ 8 присвячено специфіки оптимізації коду для ЦПОСІ. У розділі 9 наводиться інформація про мовних розширеннях та їх ролі у збільшенні ефективності процесорів. У укладанні (розділ 10) представлені деякі з актуальних невирішених цього час проблем оптимізації коду для ILP-процесорів.

ILP-платформи

Загальні властивості ILP-процесорів - здатність одночасно і незалежно виконувати кілька операцій і наявність декількох функціональних пристроїв різних типів, таких як, наприклад, пристрій обміну з пам'яттю, арифметичне пристрій та ін У виконанні кожної команди бере участь певний набір функціональних пристроїв. Процесор може виконувати команди c1, ..., cn одночасно, якщо:

процесор має досить функціональних пристроїв для їх спільного виконання.

ні одна з команд ci не використовує в якості вхідних операндів результати інших команд c1, ..., cn;

ILP-процесори можуть відрізнятися багатьма характеристиками, які істотні з точки зору застосування і ефективності розглянутих далі методів оптимізації. Даний розділ містить короткий огляд типів ILP-процесорів і їх властивостей.

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

Нехай виконання команди складається з 3-х етапів

по 1 процесорного такту на кожен:

1) читання команди з пам'яті (Ч);

2) декодування (Д);

3) виконання (І).        

Послідовне виконання команд             

Етапи         

Ч1         

Д1         

И1         

Ч2         

Д2         

И2         

Ч3         

Д3         

і3             

Такт