Оцінювання ефективності паралельної вибірки мікрокоманд

Швидкодія керуючого автомата характеризується часом, що витрачається на формування одного набору керуючих сигналів. Ця величина складається з трьох складових: 1) часу формування адреси наступної мікрокоманди; 2) часу звернення до постійного запам’ятовуючого пристрою (ПЗП); 3) часу дешифрування мікрокоманди.

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

Розглянемо більш детально 2-й спосіб. Довжину слова ПЗП можна призначити рівній сумарній довжині К мікрокоманд. В такому випадку за одне звернення до ПЗП вибирається слово, що містить К мікрокоманд. Ці мікрокоманди будуть оброблятися послідовно в порядку, що диктує мікропрограма. Очевидно, що з К вибраних мікрокоманд реалізується в середньому мікрокоманд, в результаті чого витрати часу на вибірку з ПЗП однієї мікрокоманди зменшуються в N раз, тобто ефективна швидкодія ПЗП збільшується в N раз.

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

Паралельна вибірка використовується винятково з метою збільшення швидкодії.

Оцінимо ефективність способу паралельної вибірки мікрокоманд.

Нехай слово ПЗП містить К мікрокоманд. Будемо говорити, що у разі звертання до мікрокоманди процес виконання мікропрограми знаходиться в стані відповідно і при виконанні будь-якої іншої мікрокоманди, що не належить даному слову, — в стані 0. Приймемо, що процес з стану 0 переходить в будь-який стан з однаковою імовірністю . Після переходу в стан i процес переходить або в стан , зумовлений природним порядком слідування мікрокоманд, або в деякий стан j, що задається мікрокомандами умовного або безумовного переходу. Процес розвивається в межах станів до тих пір, доки деяка мікрокоманда не передасть управління мікрокоманді, що належить іншому слову ПЗП, тобто до тих пір, доки процес не перейде в стан 0. Імовірнісною моделлю означеного процесу є марковський ланцюг з станом [5], в кожному з яких процес перебуває одиницю часу і переходить з стану i в стан j з імовірністю, причому

. (1)

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

Щоб оцінити ефективність паралельної вибірки мікрокоманд, необхідно визначити час перебування процесу в станах за умови, що процес попадає в ці стани, виходячи з стану 0, тільки один раз. Позначимо через число перебувань процесу в станах , причому . Тоді сумарний час перебування процесу в станах складе

(2)

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

, (3)

котра встановлює, що кількість перебувань процесу в i-му стані дорівнює сумарному числу перебувань в станах , помноженому на імовірність переходів зі станів j в стани i. Таким чином, при заданих імовірностях переходів визначення значень зводиться до рішення системи лінійних алгебраїчних рівнянь (3) K-го порядку.

Імовірності переходів визначаються таким чином. Нехай мікрокоманди, що представляють функціональні оператори, виконуються з імовірністю q, тоді мікрокоманди, що реалізують оператори переходу, виконуються з імовірністю

. (4)

Отже, мікрокоманди породжують природний порядок слідування з імовірністю q і цей порядок порушується з імовірністю .

Якщо слідом за мікрокомандою з адресою виконується мікрокоманда з адресою , то говорять, що різниця

(5)

визначає довжину переходу, причому . Звичайно можна прийняти, що довжини переходів розподілені за геометричним законом, так що імовірність переходу з довжиною l дорівнює

, (6)

де

, (7)

L — середня довжина переходу. Позначимо імовірність переходу вперед, в сторону мікрокоманд з більшими адресами, через r і імовірність переходу назад через

. (8)

Розглянутому марковському ланцюгу відповідає наступна матриця перехідних імовірностей:

(9)

Тут – імовірність звернення до i-ї мікрокоманди

, (10)

a – імовірність переходу вперед на одну мікрокоманду, що виконується в природньому порядку або шляхом передачі управління наступній мікрокоманді

, (11)

b_l – імовірність переходу вперед на мікрокоманд

, (12)

c_l – імовірність переходу назад на мікрокоманд

, (13)

p_i – імовірність того, що мікрокоманда i передасть управління мікрокоманді, яка не міститься у вибраному слові

, (14)

(15)

Використовуючи визначені значення перехідних імовірностей, систему (3) можна записати таким чином:

. (16)

В даних рівняннях перша сума не існує (відсутня) при i=1 і i=2, другий член не існує при i=1 і остання сума — при i=К. Корені системи лінійних алгебраїчних рівнянь (16) визначають значення , підстановка яких в (2) дозволяє визначити кількість мікрокоманд N, що виконуються за одне звернення до ПЗП.

Рис. 2.

Графіки рис. 2 використовуються для визначення числа К мікрокоманд, що вибираються паралельно, необхідного для забезпечення потрібної швидкодії керуючого автомата. Якщо – гранично допустимий час вибірки однієї мікрокоманди і Т – тривалість циклу звернення до ПЗП, то

(17)

і величина К вибирається з рис. 2 як значення функції.

На pиc. 2 представлені значення k, що визначають число звернень до ПЗП, що приходиться на одну виконувану мікрокоманду, причому кривим 1, 2, 3, 4 відповідають значення L=3, 5, 7, 11. Значення k залежать від кількості К мікрокоманд, що вибираються паралельно, і характеристик q і L мікропрограми. Графіки побудовані в припущенні прo однакову імовірність переходів вперед і назад. Експеримент дозволяє зробити висновок про слабкий вплив значення r на величину k: при відхилення k від значень, що визначаються pис. 2, не перевищує 6%.