Передбачення переходів

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

Існує два базових методи передбачення переходів: статичний і динамічний.

Статичне передбачення

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

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

Динамічне передбачення

Динамічні методи, які широко використовують в сучасних процесах, використовують аналіз історії розгалужень. Прикладом динамічного передбачення є дворівневий адаптивний історичний алгоритм (англ. Bimodal branch prediction), який використовувався процесорами архітектури Intel P6 (аналізується таблиця історії переходів, що містить молодші значущі біти адреси інструкції і відповідну імовірність умовного переходу: «скоріш за все, буде виконаний», «можливо, буде виконаний», «можливо, не буде виконаний», «скоріш за все, не буде виконаний» та оновлюється після кожного переходу).

Посилання

• Dan Luu, Branch Prediction