Спекулятивная многопоточность

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

Описание

TLS извлекает потоки из последовательного кода и спекулятивно выполняет их параллельно с безопасным потоком. Спекулятивный поток необходимо будет отбросить или запустить повторно, если его предположения о состоянии ввода окажутся недействительными. Это метод динамического распараллеливания (время выполнения) , который может выявить параллелизм, который методы статического распараллеливания (время компиляции) могут не использовать, поскольку во время компиляции независимость потоков не может быть гарантирована. Чтобы метод достиг цели сокращения общего времени выполнения, должен быть доступный ресурс ЦП, который может эффективно выполняться параллельно с основным безопасным потоком.

TLS оптимистично предполагает, что данная часть кода (обычно циклы) может безопасно выполняться параллельно. Для этого он делит пространство итераций на фрагменты, которые выполняются параллельно разными потоками. Аппаратный или программный монитор гарантирует сохранение последовательной семантики (другими словами, выполнение выполняется так, как если бы цикл выполнялся последовательно). Если появляется нарушение зависимости, спекулятивная среда может остановить все параллельное выполнение и перезапустить его; останавливать и перезапускать нарушающие потоки и всех их преемников, чтобы получать правильные данные; или остановить исключительно поток-нарушитель и его преемников, которые использовали из него неверные данные.

Дальнейшее чтение

• Япанис, Параскевас; Браун, Гэвин; Лухан, Микель (2016). «Рассуждения о программном обеспечении, управляемом компилятором, для параллелизма на уровне потоков» . Транзакции ACM в языках и системах программирования . 38 (2): 1–45. дои : 10.1145/2821505 .

• Япанис, Параскевас; Росас-Хам, Демиан; Браун, Гэвин; Лухан, Микель (2013). «Оптимизация систем выполнения программного обеспечения для спекулятивного распараллеливания» . Транзакции ACM по оптимизации архитектуры и кода . 9 (4): 1–27. дои : 10.1145/2400682.2400698 .
• Льянос, Диего Р. (2007). «Новые стратегии планирования для рандомизированных инкрементных алгоритмов в контексте спекулятивного распараллеливания» . Транзакции IEEE на компьютерах . 56 (6): 839–852. CiteSeerX   10.1.1.77.5496 . дои : 10.1109/TC.2007.1030 . S2CID   3181243 .
• Джонсон, Ник П.; Ким, Ханджун; Прабху, Пракаш; Закс, Аял; Август, Дэвид И. (2012). «Спекулятивное разделение на приватизацию и сокращения» (PDF) . Материалы 33-й конференции ACM SIGPLAN по проектированию и реализации языков программирования . ПЛДИ '12. стр. 359–370. дои : 10.1145/2254064.2254107 .
• Бхоумик, Анасуа; Франклин, Манодж (2002). «Общая структура компилятора для спекулятивной многопоточности». Материалы четырнадцатого ежегодного симпозиума ACM по параллельным алгоритмам и архитектурам . СПАА '02. стр. 99–108. дои : 10.1145/564870.564885 .
• Брюнинг, Дерек; Девабхактуни, Шрикришна; Амарасингхе, Саман (2000). Softspec: Программный спекулятивный параллелизм (PDF) . ФДДО-3. стр. 1–10.
• Чен, Майкл К.; Олукотун, Кунле (1998). «Использование параллелизма на уровне методов в однопоточных программах Java». Международная конференция по параллельным архитектурам и методам компиляции . ПАКТ 1998. стр. 176–184. дои : 10.1109/PACT.1998.727190 .
• Чен, Майкл К.; Олукотун, Кунле (2003). «Система Jrpm для динамического распараллеливания Java-программ». Материалы 30-го ежегодного международного симпозиума по архитектуре компьютеров . ИСКА '03. стр. 434–446. дои : 10.1145/859618.859668 .
• Синтра, Марсело; Льянос, Диего Р. (2003). «На пути к эффективному и надежному спекулятивному распараллеливанию программного обеспечения на мультипроцессорах». Материалы девятого симпозиума ACM SIGPLAN «Принципы и практика параллельного программирования» . ППоПП '03. стр. 13–24. дои : 10.1145/781498.781501 .
• Кук, Джонатан Дж. (2002). «Обратное выполнение байт-кода Java». Компьютерный журнал . 45 (6): 608–619. CiteSeerX   10.1.1.20.4765 . дои : 10.1093/comjnl/45.6.608 .
• Хиноны, Карлос Гарсия; Мадрилес, Карлос; Санчес, Хесус; Маркуэльо, Педро; Гонсалес, Антонио; Таллсен, Дин М. (2005). «Компилятор митоза: инфраструктура для спекулятивного распараллеливания на основе срезов предварительного вычисления». Материалы конференции ACM SIGPLAN 2005 года по проектированию и реализации языков программирования . ПЛДИ '05. стр. 269–279. дои : 10.1145/1065010.1065043 .
• Ху, Шивэнь; Бхаргава, Рави; Джон, Лизи Куриан (2003). «Роль прогнозирования возвращаемого значения в использовании спекулятивного параллелизма на уровне методов» (PDF) . ДЖИЛП . 5 : 1–21.
• Кази, Иффат Х. (2000). Динамически адаптивная модель распараллеливания на основе спекулятивной многопоточности (кандидатская диссертация). Университет Миннесоты. стр. 1–188.
• Пикетт, Кристофер Дж. Ф.; Вербрюгге, Кларк (2005). «SableSpMT: программная платформа для анализа спекулятивной многопоточности в Java». Материалы 6-го семинара ACM SIGPLAN-SIGSOFT по программному анализу для программных средств и инженерии . ПАСТА '05. стр. 59–66. дои : 10.1145/1108792.1108809 .
• Пикетт, Кристофер Дж. Ф.; Вербрюгге, Кларк (2005). «Предположение на уровне потоков программного обеспечения для языка Java и среды виртуальных машин» (PDF) . Материалы 18-й международной конференции «Языки и компиляторы для параллельных вычислений» . ЛКПК '05. ЛНКС. Том. 4339. стр. 304–318. дои : 10.1007/978-3-540-69330-7_21 .
• Портер, Лео; Чхве, Бумён; Таллсен, Дин М. (2009). «Отображение пути от аппаратной транзакционной памяти к спекулятивной многопоточности». 18-я Международная конференция по параллельным архитектурам и методам компиляции . ПАКТ '09. стр. 313–324. CiteSeerX   10.1.1.153.2503 . дои : 10.1109/PACT.2009.37 .
• Рундберг, Питер; Стенстрем, Пер (2001). «Полнопрограммная система предположений о зависимости данных на уровне потоков для мультипроцессоров» (PDF) . ДЖИЛП . 3 : 1–28.
• Стеффан, Дж. Грегори; Колохан, Кристофер; Чжай, Антония; Моури, Тодд К. (2005). «Подход STAMPede к спекуляциям на уровне потоков». Транзакции ACM в компьютерных системах . 23 (3): 253–300. CiteSeerX   10.1.1.79.4317 . дои : 10.1145/1082469.1082471 . S2CID   10499545 ​​.
• Уэйли, Джон; Козыракис, Христос (2005). «Эвристика для спекулятивного распараллеливания на уровне методов на основе профилей». Международная конференция по параллельной обработке . ICPP 2005. стр. 147–156. CiteSeerX   10.1.1.77.3989 . дои : 10.1109/ICPP.2005.44 .
• Ренау, Хосе; Штраус, Карин ; Сезе, Луис; Лю, Вэй; Саранги, Смрути; Так, Джеймс; Торреллас, Хосеп (2006). «Рассуждения об энергоэффективности на уровне потоков» (PDF) . IEEE микро . 26 (1): 80–91. дои : 10.1109/MM.2006.11 . S2CID   206472480 .
• Ёсидзоэ, Кадзуки; Мацумото, Такаши; Хираки, Кей (1998). «Спекулятивное параллельное выполнение на JVM» . Британский семинар по HPNC . стр. 1–20.
• Оанча, Космин Э.; Майкрофт, Алан; Харрис, Тим (2009). «Облегченная реализация на месте для спекуляций на уровне потоков программного обеспечения» (PDF) . Материалы двадцать первого ежегодного симпозиума по параллелизму в алгоритмах и архитектурах . СПАА '09. стр. 1–10. дои : 10.1145/1583991.1584050 .