Спекулятивне виконання

Спекулятивне виконання — (від лат. specio - погляд) це метод прискорення обчислень, коли комп'ютер маючи виконує обчислення, не чекаючи чи буде виконана умова при яких ці обчислення будуть необхідні. Якщо виявиться що робота не була потрібна то зміни скасовуються та результати ігноруються. Такий підхід використовується в різних областях, у тому числі прогнозування розгалуження в конвеєрах процесорів, упереджувальна вибірка з пам'яті та файлів, і оптимістичне керування паралелізмом у системах баз даних.

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

Огляд

Під терміном «динамічне (спекулятивне) виконання» мається на увазі наступна сукупність можливостей:^[]

• Глибоке передбачення розгалужень (з ймовірністю> 90 % можна передбачити 10-15 найближчих переходів).
• Аналіз потоку даних (на 20-30 кроків вперед переглянути програму і визначити залежність команд за даними або ресурсів).
• Випереджувальне виконання команд (процесор може виконувати команди в порядку, відмінному від їх проходження в програмі).

Сучасні конвеєрні мікропроцесори використовують спекулятивне виконання, щоб знизити вартість команд умовного переходу з використанням схем, що передбачають шлях виконання програми. З метою підвищення ефективності та використання ресурсів комп'ютера, інструкції можуть бути заплановані в той час, коли ще не була визначено, що інструкції повинні бути виконані. У оптимізації компіляторів для декількох систем обробки, спекулятивне виконання передбачає дозвільний процесор, що виконує код в наступному блоці процесора, якщо немає залежності від коду, який може бути запущений на інших процесорах. Перевага цієї схеми є скорочення часу відгуку для окремих процесорів і системи в цілому. Компілятор обмежується видачею спекулятивної команди виконання, так як вона вимагає апаратного забезпечення за для буферизації. Без апаратної підтримки, компілятор може видати тільки спекулятивні інструкції, які не мають ніяких побічних ефектів у разі неправильної спекуляції^:16.

Нетерпляче обчислення

(Нетерпляче обчислення) (англ. eager evaluation) являє собою форму спекулятивного виконання, де виконуються обидві сторони умовної гілки; проте, залишається лише результат тієї гілки, чий предикат стає вірним.

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

З необмеженими ресурсами, нетерпляче обчислення (також відоме як пророкування виконання) могло б забезпечити таку ж продуктивність що і передбачення переходів. З обмеженими ресурсами нетерпляче обчислення слід використовувати обережно, тому що кількість необхідних ресурсів зростає з кожним етапом.^:148—150

Передбачуване виконання

Докладніше: Конвеєр (інформатика)

Передбачуване виконання це різновид спекулятивного виконання, за якого процесор прогнозує результат певної операції та починає виконувати інструкції на основі цього прогнозу. Якщо прогноз виявляється вірним, виконані інструкції зберігаються. Але якщо прогноз виявиться помилковий, процесору доведеться скасовувати виконані інструкції та починати все знову. В загальній формі це називається передбачення значень, та використовується в модулі передбачення переходів та ^[en].

Ліниві обчислення

Докладніше: Ліниві обчислення

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

Уразливості

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

• Spectre
• Meltdown
• ^[en]
• ^[en]
• ^[en]

Примітки

1. https://www.bbc.com/news/magazine-35933859 Speculation comes from the Latin word specio, meaning look, which fathered a great tribe of words ranging from "spectacular" to "despicable".
2. Butler Lampson (12 грудня 2006). (PDF). OPODIS. Bordeaux, France: Microsoft Research. Архів оригіналу (PDF) за 4 березня 2016. Процитовано 2 грудня 2016.
3. Prabhakar Raghavan; Hadas Schachnai; Mira Yaniv (1998). (англ.). IBM, Research Division. Архів оригіналу за 27 листопада 2020. Процитовано 18 січня 2011.
4. Kung, H. T.; Robinson, John T. (June 1981). On optimistic methods for concurrency control. ACM Trans. Database Syst. Т. 6, № 2.
5. Bernd Krieg-Brückner (1992). . Springer. с. 56—57. ISBN . Архів оригіналу за 12 червня 2014. Процитовано 18 січня 2011.
6. Laplante, Phillip A. (2004). Real-Time Systems Design and Analysis (англ.) (вид. 3rd). Wiley-IEEE Press. с. 391. ISBN . {{}}: |access-date= вимагає |url= ()
7. Lilja, David J.; Bird, Peter L. (31 травня 1994). The Interaction of Compilation Technology and Computer Architecture (англ.). Springer Science & Business Media. ISBN .
8. Šilc, Jurij; Robic, Borut; Ungerer, Theo (8 червня 1999). Processor Architecture: From Dataflow to Superscalar and Beyond (англ.). Springer Science & Business Media. ISBN .

Посилання

• «Speculative computation in Multilisp.» [ 7 лютого 2017 у Wayback Machine.]
• Проект спільноти програмістів з документації виявлених уразливостей CPU security bugs caused by speculative execution [ 9 січня 2018 у Wayback Machine.] (Meltdown та Spectre)