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

Спекулятивне виконання — це метод оптимізації, коли комп'ютерна система виконує деякі завдання, які можуть бути насправді непотрібними. Основна ідея полягає в тому, щоб виконати роботу до того, як стане відомо, чи буде потрібна ця робота взагалі, з тим щоб запобігти затримці. Якщо зрештою з'ясовується, що робота була не потрібна, будь-які зміни скасовуються і результати ігноруються.

Мета полягає в тому, щоб забезпечити більше паралелізму за умови наявності додаткових ресурсів. Такий підхід використовується в різних областях, у тому числі прогнозування розгалуження в конвеєрах процесорів, упереджувальна вибірка з пам'яті та файлів, і оптимістичне керування паралелізмом[en] у системах баз даних.[1][2][3]

Огляд ред.

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

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

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

Енергійне обчислення ред.

Енергійне обчислення (англ. eager evaluation) являє собою форму спекулятивного виконання, де виконуються обидві сторони умовної гілки; проте, залишається лише результат тієї гілки, чий предикат стає вірним. З необмеженими ресурсами, енергійне обчислення (також відоме як пророкування виконання) могло б забезпечити таку ж продуктивність що і передбачення переходів. З обмеженими ресурсами енергійне обчислення слід використовувати обережно, тому що кількість необхідних ресурсів зростає з кожним етапом.[7]:148—150

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

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

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

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

Перевагами лінивих обчислень є:

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

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

Ліниві обчислення не спекулюють. Включення спекулятивного виконання в реалізації мови програмування Haskell є поточною темою дослідження. Haskell побудована навколо ідеї спекулятивного виконання.

Примітки ред.

  1. Butler Lampson (12 грудня 2006). Lazy and Speculative Execution OPODIS. Bordeaux, France: Microsoft Research. Архів оригіналу за 4 березня 2016. Процитовано 2 грудня 2016. 
  2. Prabhakar Raghavan; Hadas Schachnai; Mira Yaniv (1998). Dynamic schemes for speculative execution of code (англ.). IBM, Research Division. Архів оригіналу за 27 листопада 2020. Процитовано 18 січня 2011. 
  3. Kung, H. T.; Robinson, John T. (June 1981). On optimistic methods for concurrency control. ACM Trans. Database Syst. Т. 6, № 2. 
  4. Bernd Krieg-Brückner (1992). ESOP '92: 4th European Symposium on Programming, Rennes, France, February 26-28, 1992: proceedings. Springer. с. 56–57. ISBN 978-3-540-55253-6. Архів оригіналу за 12 червня 2014. Процитовано 18 січня 2011. 
  5. Laplante, Phillip A. (2004). Real-Time Systems Design and Analysis (англ.) (вид. 3rd). Wiley-IEEE Press. с. 391. ISBN 978-0-471-22855-4.  {{cite book}}: |access-date= вимагає |url= (довідка)
  6. Lilja, David J.; Bird, Peter L. (31 травня 1994). The Interaction of Compilation Technology and Computer Architecture (англ.). Springer Science & Business Media. ISBN 978-0-7923-9451-8. 
  7. Šilc, Jurij; Robic, Borut; Ungerer, Theo (8 червня 1999). Processor Architecture: From Dataflow to Superscalar and Beyond (англ.). Springer Science & Business Media. ISBN 978-3-540-64798-0. 

Див. також ред.

  • Meltdown та Spectre — оприлюднені на початку 2018 року уразливості в сучасних мікропроцесорах з технологією спекулятивного виконання команд

Посилання ред.