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

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

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

ОглядРедагувати

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

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

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

Енергійне обчисленняРедагувати

Енергійне обчислення[en]

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

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

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

Ліниві обчисленняРедагувати

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

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

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

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

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

ПриміткиРедагувати

  1. Butler Lampson (12 December 2006). Lazy and Speculative Execution OPODIS. Bordeaux, France: Microsoft Research. 
  2. Prabhakar Raghavan; Hadas Schachnai; Mira Yaniv (1998). Dynamic schemes for speculative execution of code (en). IBM, Research Division. Процитовано 18 January 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. Процитовано 18 January 2011. 
  5. Laplante, Phillip A. (2004). Real-Time Systems Design and Analysis (en) (вид. 3rd). Wiley-IEEE Press. с. 391. ISBN 978-0-471-22855-4. 
  6. Lilja, David J.; Bird, Peter L. (31 May 1994). The Interaction of Compilation Technology and Computer Architecture (en). Springer Science & Business Media. ISBN 978-0-7923-9451-8. 
  7. Šilc, Jurij; Robic, Borut; Ungerer, Theo (8 June 1999). Processor Architecture: From Dataflow to Superscalar and Beyond (en). Springer Science & Business Media. ISBN 978-3-540-64798-0. 

Див. такожРедагувати

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

ПосиланняРедагувати