stringtranslate.com

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

Спекулятивное выполнение — это метод оптимизации , при котором компьютерная система выполняет некоторую задачу, которая может быть не нужна. Работа выполняется до того, как станет известно, нужна ли она на самом деле, чтобы предотвратить задержку, которая могла бы возникнуть при выполнении работы после того, как станет известно, что она нужна. Если выясняется, что работа все-таки не нужна, большинство изменений, внесенных работой, отменяются, а результаты игнорируются.

Цель состоит в том, чтобы обеспечить больше параллелизма , если доступны дополнительные ресурсы . Этот подход используется в различных областях, включая прогнозирование ветвлений в конвейерных процессорах , прогнозирование значений для использования локальности значений, предварительную выборку памяти и файлов , а также оптимистическое управление параллелизмом в системах баз данных . [1] [2] [3]

Спекулятивная многопоточность — это частный случай спекулятивного выполнения.

Обзор

Современные конвейерные микропроцессоры используют спекулятивное выполнение для снижения стоимости инструкций условного перехода с помощью схем, которые предсказывают путь выполнения программы на основе истории выполнения переходов. [2] Для повышения производительности и использования ресурсов компьютера инструкции можно планировать на время, когда еще не определено, что инструкции необходимо будет выполнить, до перехода . [ 4]

Варианты

Спекулятивные вычисления были родственной более ранней концепцией. [5]

Жадное исполнение

Eager execution — это форма спекулятивного выполнения, при которой выполняются обе стороны условного перехода; однако результаты фиксируются только в том случае, если предикат истинен. При неограниченных ресурсах Eager execution (также известное как Oracle execution ) теоретически обеспечивает ту же производительность, что и Perfect Branch predicting . При ограниченных ресурсах Eager execution следует использовать осторожно, поскольку количество необходимых ресурсов растет экспоненциально с каждым уровнем перехода, выполняемым Eager. [6]

Предиктивное исполнение

Предиктивное выполнение — это форма спекулятивного выполнения, при которой предсказывается некоторый результат, и выполнение продолжается по предсказанному пути до тех пор, пока не станет известен фактический результат. Если предсказание верно, предсказанное выполнение допускается для фиксации; однако, если предсказание неверно, выполнение должно быть развернуто и выполнено повторно. Распространенные формы этого включают предикторы ветвлений и предсказание зависимости памяти . Обобщенная форма иногда называется предсказанием значения. [7]

Бегущий впереди

Runahead — это метод, позволяющий процессору компьютера спекулятивно предварительно обрабатывать инструкции во время циклов промахов кэша . Предварительно обработанные инструкции используются для генерации предварительных выборок инструкций и потоков данных путем выполнения инструкций, приводящих к промахам кэша (обычно называемым загрузками с большой задержкой ) до того, как они обычно происходят, эффективно скрывая задержку памяти . В runahead процессор использует ресурсы бездействующего выполнения для вычисления адресов инструкций и потоков данных с использованием доступной информации, которая не зависит от промаха кэша. После того, как процессор разрешил начальный промах кэша, все результаты runahead отбрасываются, и процессор возобновляет выполнение в обычном режиме. Основной вариант использования метода — смягчение эффектов стены памяти . Метод также может использоваться для других целей, таких как предварительное вычисление результатов ветвления для достижения высокоточного предсказания ветвления . [8]

Связанные концепции

Ленивое исполнение

Ленивое выполнение является противоположностью жадного выполнения и не подразумевает спекуляций. Включение спекулятивного выполнения в реализации языка программирования Haskell , ленивого языка, является актуальной темой исследований. Eager Haskell , вариант языка, разработан вокруг идеи спекулятивного выполнения. Кандидатская диссертация 2003 года заставила GHC поддерживать своего рода спекулятивное выполнение с механизмом прерывания для отмены в случае плохого выбора, называемого оптимистичным выполнением . [9] Это было сочтено слишком сложным. [10]

Уязвимости безопасности

Начиная с 2017 года в реализациях спекулятивного выполнения на распространенных архитектурах процессоров был обнаружен ряд уязвимостей безопасности , которые фактически позволяли повышать привилегии .

К ним относятся:

Смотрите также

Ссылки

  1. ^ Лампсон, Батлер (2006). «Ленивое и спекулятивное выполнение в компьютерных системах». В Момензаде, Мариам; Шварцман, Александр А. (ред.). Принципы распределенных систем . 10-я международная конференция по принципам распределенных систем. Конспект лекций по информатике. Том 4305. Бордо, Франция: Springer. стр. 1–2. doi :10.1007/11945529_1. ISBN 978-3-540-49991-6.
  2. ^ ab Raghavan, Prabhakar; Shachnai, Hadas; Yaniv, Mira (1998). "Динамические схемы для спекулятивного выполнения кода". Труды Шестого международного симпозиума по моделированию, анализу и имитации компьютерных и телекоммуникационных систем . IEEE. стр. 309–314. doi :10.1109/MASCOT.1998.693711 . Получено 18 января 2011 г.
  3. ^ Кунг, Х. Т .; Джон Т. Робинсон (июнь 1981 г.). «Об оптимистических методах управления параллелизмом» (PDF) . ACM Trans. Database Syst . Vol. 6. Архивировано (PDF) из оригинала 31 августа 2019 г.
  4. ^ Бернд Криг-Брюкнер (1992). ESOP '92: 4-й Европейский симпозиум по программированию, Ренн, Франция, 26-28 февраля 1992 г.: материалы. Спрингер. стр. 56–57. ISBN 978-3-540-55253-6. Получено 18 января 2011 г.
  5. ^ Рэнди Б. Осборн (1990-03-21). "Спекулятивные вычисления в Multilisp". Parallel Lisp: Languages ​​and Systems ( PS ). Lecture Notes in Computer Science. Vol. 441. Digital Equipment Corporation Research Lab . pp. 103–137. doi :10.1007/BFb0024152. ISBN 3-540-52782-6. Архивировано из оригинала 2017-02-07 . Получено 2018-01-26 .
  6. ^ Юрий Шилц; Борут Робич; Тео Унгерер (1999). Архитектура процессора: от потока данных к суперскаляру и далее . Спрингер. стр. 148–150. ISBN 978-3-540-64798-0. Получено 21 января 2011 г.
  7. ^ Марк Д., Хилл; Норман П., Джуппи ; Гуриндар С., Сохи (2000). Чтения по компьютерной архитектуре. Морган Кауфман. ISBN 9781558605398. Получено 5 января 2018 г.
  8. ^ Pruett, Stephen; Patt, Yale (октябрь 2021 г.). «Branch Runahead: альтернатива предсказанию ветвей для невозможных для предсказания ветвей». MICRO-54: 54-й ежегодный международный симпозиум IEEE/ACM по микроархитектуре . MICRO '21. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 804–815. doi :10.1145/3466752.3480053. ISBN 978-1-4503-8557-2. S2CID  239011545.
  9. ^ Джонс, Саймон Пейтон; Энналс, Роберт (1 августа 2003 г.). «Оптимистическая оценка: быстрая стратегия оценки для нестрогих программ» . Получено 15 мая 2019 г. – через www.microsoft.com. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  10. ^ «[Haskell] Оптимистическая оценка?». 31 августа 2006 г.