розріджена модель базових блоків для оптимізації потоків команд

Довгалюк П.М., Праці Інституту системного програмування РАН

Анотація

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

Аналіз існуючих математичних моделей обчислювальних процесів в базових блоках

Існує ряд моделей обчислювальних процесів в базових блоках. Найбільш Найпоширеніші з них використовують для представлення базового блоку спрямовані ациклічні графи [3], [4], [5].

Під всіх поширених Графова моделях базових блоків безліч вершин відповідає безлічі команд, а наявність дуги між двома вершинами відповідає наявності залежності між відповідними командами (дуга (v, u) показує, що команда v повинна бути виконана раніше команди u).

Для того щоб задати протяжність затримки між командами, в найбільш популярної моделі, описаної в [3] і [5], використовуються числові позначки ребер графа, відповідні тривалість затримок - D ((v, u)).

На Рис. 1 і 2 представлений приклад вмісту базового блоку і його традиційне подання за допомогою графа.

mov a, b

add c, 1

mul a, c

mov d, c

mul a, d

Рис. 1. Приклад вмісту базового блоку

Рис. 2. Традиційне уявлення базового блоку у вигляді графа

Коректним розкладом S для систем з одним конвеєром називається функція S: (V