ПРОРОКУВАННЯ РОЗГАЛУЖЕНЬ

Раніше після вибірки команди умовного розгалуження (переходу) робота конвеєра завжди припинялася для перевірки умови переходу:

  • • при невиконанні умови програма виконувалася по основної гілки;
  • • виконанні умови переходу відбувалася очистка всіх попередніх ступенів і вибірка команди з нової гілки програми, тобто перезавантаження конвеєра.

Передбачення переходу (Branch Prediction) дозволяє безупинно (без перевірки умови розгалуження) вибрати напрямок подальшого виконання програми. Відомі два методу передбачення:

  • • статичний, згідно з яким заздалегідь віддається перевага одному з умов розгалуження. Його алгоритм закладається програмістом в текст програми і реалізується при її виконанні;
  • • динамічний, заснований на передісторії виконання програми і що передбачається на підставі статистичних даних, отриманих для обох гілок.

В процесорах Pentium для прогнозування використовуються такі засоби:

  • • 512 адрес раніше виконаних переходів, що зберігаються в буфері адрес розгалужень (Branch Target Buffer - ВТВ);
  • • 4 біта передісторії розгалуження, які вказують, виконувався перехід при чотирьох попередніх вибірках даної команди. Біти зберігаються в буфері історії переходів (Branch History Buffer - ВНВ).

При надходженні чергової команди умовного переходу вказаний в ній адресу АКУП порівнюється з адресою АВТВ буфера:

  • • якщо раніше за адресою АКУП не відбувались переходи, то ця адреса не міститься в буфері ВТВ і передбачається відсутність розгалуження, тому триває вибірка і декодування команд, що настають за командою переходу;
  • • якщо в буфері ВТВ відшукується адреса АВТВ = АКУП, то проводиться аналіз передісторії, в результаті чого визначається напрямок розгалуження, для якого найчастіше виконувалося умова розгалуження, а також виявляються чергуються переходи.

Обрана по передбаченого адресою команда умовного переходу зберігається (завантажується в конвеєр). Одночасно з нею вибирається, декодируется і зберігається наступна команда. Якщо після аналізу умови розгалуження з'ясовується, що пророкування було неправильним, то в виконавчий пристрій надходить наступна команда. Таким чином, скорочуються втрати часу на перезавантаження конвеєра. Даний алгоритм забезпечує ймовірність правильного передбачення розгалужень до 90%.

ВИПЕРЕДЖАЮЧЕ ВИКОНАННЯ

Спосіб обробки даних, при якому процесор заздалегідь (до виявлення умов переходу) виконує команди розгалуження, називається випереджувальним виконанням, виконанням за припущенням або спекулятивним виконанням (Speculative Execution). Цей спосіб, по суті, дозволяє процесору завершувати команди заздалегідь, а потім використовувати вже обчислені результати в міру необхідності. В його основі лежить випереджаюче перегляд лічильника команд. Процесор на підставі аналізу вибирає команди з накопичувача (кеш-пам'яті, реєстрового файлу, пулу), виконує їх і зберігає результати у тимчасових регістрах.

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

При спекулятивному виконанні використовуються такі механізми, як просування даних (Data Forwarding) і виконання зі зміною порядку проходження команд (out-of-order execution - нестандартне виконання) [18].

 
< Попер   ЗМІСТ   Наст >