Разреженная модель базових блоків для оптимізації потоків команд
Также в жодній з найпоширеніших моделей до уваги береться те що, що у більшості архітектур різні команди займають різну кількість тактів конвеєра. Наприклад, для RISC-процессоров, де всі команди кодуються одним машинним словом, деякі команди, які оперують великими константами, можуть кодуватимуть у двох словах. Традиционная графовая модель базових блоків використовують у ролі вузлів окремі… Читати ще >
Разреженная модель базових блоків для оптимізації потоків команд (реферат, курсова, диплом, контрольна)
Разреженная модель базових блоків для оптимізації потоків команд
Довгалюк П.М., Трудов института системного програмування РАН.
Аннотация
Предлагаемая модель призначається для описи потоків команд в базових блоках. Ця модель орієнтована на завдання оптимізації потоків команд за швидкістю їх виконання. Такі моделі застосовуються для одержання найкоротшого по часу розкладу команд, вступників на конвеєр процесора.
Анализ існуючих математичних моделей обчислювальних процесів в базових блоках Существует ряд моделей обчислювальних процесів в базових блоках. Найбільш поширені їх використовують із уявлення базового блоку спрямовані ациклические графи [3], [4], [5].
Во всіх поширених графовых моделях базових блоків безліч вершин відповідає безлічі команд, а наявність дуги між двома вершинами відповідає наявності залежності між відповідними командами (дуга (v, u) показує, що команда v має бути виконане раніше команди u).
Для здобуття права поставити протяжність затримки між командами, у найбільш популярної моделі, описаної в [3] і [5], використовуються числові позначки ребер графа, відповідні продолжительностям затримок — D ((v, u)).
На Рис. 1 і 2 представлений приклад вмісту базового блоки і його традиційне подання з допомогою графа.
mov a, b.
add з, 1.
mul a, c.
mov d, c.
mul a, d.
Рис. 1. Приклад вмісту базового блока.
.
Рис. 2. Традиційне уявлення базового блоку як графа.
Корректным розписом P. S для систем з однією конвеєром називається функція P. S: (V?N??(v, u)?E?S (u)-S (v)>D ((v, u))). Отже, S (v) — позиція вершини v в результуючому розкладі. У кожній позиції розкладу може знаходитися чи одна інструкція, або спеціальна команда NOP, яка виконує ніяких дій.
mov a, b.
add з, 1.
mul a, c.
nop.
mov d, c.
mul a, d.
Рис. 3. Приклад коректного розкладу для базового блока Существует безліч моделей, побудованих з урахуванням описаної вище, відмінних різними атрибутами вершин і дуг, залежно від особливостей архітектури цільових машин.
В деяких поширених архитектурах, наприклад Intel i860 [2], залежності між командами може бути обмежено за часом згори. Тобто друга (залежна) інструкція має бути виконане за певне кількість тактів після першої, інакше результат виконання першої команди буде втрачено. Хоча такі види залежностей і описуються існуючими моделями [1], [5], але ефективних алгоритмів побудови розкладу, створюють коректне розклад завжди, коли може бути, їм немає. Це тим, такі залежності уводять у модель з допомогою спеціального атрибута зв’язків. Дане розширення моделі Демшевського не дозволяє змогли ефективно використати алгоритми оптимізації, придатні моделей самотужки атрибута [4], [5]. Ці алгоритми в процесі роботи можуть заходити у безвихідь, генеруючи некоректне розклад.
Также в жодній з найпоширеніших моделей до уваги береться те що, що у більшості архітектур різні команди займають різну кількість тактів конвеєра. Наприклад, для RISC-процессоров, де всі команди кодуються одним машинним словом, деякі команди, які оперують великими константами, можуть кодуватимуть у двох словах.
Кроме цього у традиційних моделях базових блоків не враховуються команди переходу, мають неустранимые затримки. Такі затримки припустимо заповнювати корисними командами, якщо це призводить до конфліктів за даними. Оскільки таке обмеження погано вписується в існуючі моделі, то тут для вирішення цього завдання використовуються спеціальні алгоритми [3].
Таким чином, необхідно побудувати модель базових блоків, що дозволить оптимізувати обчислювальний процес й у випадках, коли є жорсткі обмеження згори на тривалість затримки між командами, і навіть, якщо команди кодуються неоднаковим кількістю слів. З іншого боку, нова модель повинна дозволяти враховувати залежності між командами з суміжних базових блоків для конвеєрної оптимізації команд переходу.
Разреженная модель обчислювальних процесів в базових блоках
Традиционная графовая модель базових блоків використовують у ролі вузлів окремі команди цільової машини, із яких складається базовий блок [5]. У такій моделі не відбиває завантаженості конвеєра непродуктивними обчисленнями не дозволяє оперувати командами, розмір яких набагато більше одного машинного слова.
Поэтому пропонується видозмінити модель базових блоків так: як вузлів використовувати операції, що їх конвеєром за такт. Такими операціями може бути вибірка коду команди або непродуктивна затримка, в протягом чим конвеєр не надходить нових команд. Зв’язувати ці операції в граф пропонується з допомогою зв’язків два види: котрі задають відносний чи абсолютний порядок операцій, вступників на конвеєр.
Добавление узлов-задержек між командами робить граф більш розрідженим, що стало джерелом назви модели.
Разреженную модель базових блоків можна математично описати з допомогою наступного ациклического графа:
G=(V; E; p. s; e), де.
V — безліч вузлів, відповідних конвеєрним операціям, формує базовий блок.
E?VxV — безліч зв’язків, визначальних порядок надходження узлов-операций (команд і затримок) на конвеєр процесора.
s?V — стартовий (кореневої) вузол.
e?V — останній вузол у кожному коректному розкладі, побудованому з урахуванням даного графа.
Узлы у тому графі мали бути зацікавленими позначені відповідно до їхніх призначенню — чи є вони вибірками коду команди з пам’яті, або непродуктивними затримками.
Для рішення поставлених завдань необхідно провести два виду перетинів поміж вершинами.
Введем такі визначення:
Определение 1: Зв’язок називається «жорсткої «, якщо дві операції, що вона з'єднує повинні надходити на конвеєр суворо друг за іншому (між ними має бути інших операцій).
Обозначим підмножина жорстких зв’язків як H.
Определение 2: Зв’язок називається «гнучкою », якщо вона ставить лише відносний порядок надходження операцій на конвеєр (з-поміж них на конвеєр можуть надходити інші операції).
Множество затримок введено для моделювання мінімального часу між інструкціями, що традиційно [3] представляється як числової позначки дуги. У запропонованої моделі паузи між інструкціями заповнюються з допомогою непродуктивних операцій.
.
Рис. 4. Уявлення базового блоку з допомогою розрідженій моделі.
Формальное опис графа наведене вище недостатньо точно описує модель. А аби розв’язувати завдання оптимізації потоку команд з допомогою даної моделі, граф повинен відповідати наступним умовам:
В графі є тільки одна коренева вершина — p.s.
В графі є тільки один лист — e.
Граф є слабко зв’язковим.
В графі немає циклів, бо можуть існувати циклічні залежності за даними між інструкціями щодо одного базовому блоці.
Моделирование особливостей архітектури цільової машины
Такая особливість цільової машини, як інструкції, які з кількох машинних слів, то, можливо описана з допомогою кількох послідовних узлов-операций, з'єднаних жорсткими зв’язками.
Команды, тривалість затримки між якими суворо фіксована (тобто. тривалість життя результату виконання перша з команд обмежена), пропонується моделювати з допомогою послідовності, складається з двох узлов-операций і знання кількох узлов-задержек з-поміж них. Дані вузли з'єднуються жорсткими зв’язками.
Аналогичным чином можуть описуватися команди переходів з неустранимыми затримками, лише у цьому випадку замість другий операції повинен використовуватися останній вузол графа.
Выводы В статті розглянутий традиційний, спосіб уявлення базових блоків із допомогою графовой моделі. За підсумками аналізу її недоліків введена розріджена модель базових блоків.
Предлагаемая модель відрізняється від традиційної спеціальними видами вузлів і зв’язків. На відміну від традиційних моделей, в розрідженій моделі у ролі вузлів використовуються однотактовые операції конвеєра цільової машини. Дані операції об'єднують у граф з допомогою ребер два види — для завдання відносного й абсолютної порядку операцій.
Разряженная модель дозволяє застосовувати єдиний підхід при оптимізації потоку команд в базових блоках за наявності команд з кількох машинних слів, інструкцій переходу з неустранимыми затримками, і навіть команд з обмеженою часом життя результату їх виконання. Ця її особливість дає можливість оптимізувати потоки команд в базових блоках у межах одного універсального алгоритму, що неможливо в традиційних моделях.
Список литературы.
Beaty, P. S. List scheduling: Alone, with foresight, and with lookahead. In Conference on Massively Parallel Computing Systems: the Challenges of General-Purpose and Special-Purpose Computing (Ischia, Italy, May 1994).
Intel. i860 64-bit microprocessor programmer «p.s reference manual, 1990.
S. Muchnick. Advanced compiler design and implementation, 1997.
Philip Schielke. Issues in Instruction Scheduling. Rice University, Department of Computer Science. Ph. D. Thesis Proposal.
Bjorn De Sutter. General-Purpose Architecture Instruction Scheduling Techniques. ELIS Technical Report DG 98−09, November 1998.
Для підготовки даної роботи було використані матеріали із російського сайту internet.