Covalue

Shavit, [2011] "Data structures in the multicore age"

Относительно известная научно-популярная статья десятилетней давности одного из корифеев конкаренси о будущем многопоточного (библиотечного) программирования.

Начинается с мотивации законом Амдала о ботлнеке параллельных вычислений. Упоминает, что корректность в многопоточном сеттинге распадается на два аспекта: safety (относительно модели согласованности, например линеаризуемости) и liveness (условия прогресса - lock-free/wait-free и более экзотические). Также изменяются инструменты работы с complexity - добавляется модель stalls, нужно внимательно следить за contention. Делается предсказание, что развитие алгоритмов и структур данных пойдет по пути ослабления гарантий (кажется, спустя 10+ лет это до сих пор довольно нишевые вещи).

Основное время статья описывает в качестве примера процесс "ослабления" многопоточного стека на жаве, проходя несколько фаз:

1. стек под спинлоком - линеаризуем, не параллелен (deadlock-free), забивает шину из-за бесконтрольных спинов (обычно решается backoff-схемами)
2. lock-free стек - специализирует лок до CASа на голове стека
3. elimination backoff stack - убирает последовательный ботлнек, получая т.н. "дуальную" структуру - т.е. позволяя тредам оставлять "антиданные" (заявки) и передавать элементы напрямую без записи в стек, по прежнему линеаризуем
4. elimination tree - дуальность плохо работает в случае пакетов однотипных операций, поэтому можно ослабить согласованность до quiescent модели (иллюзия линейности только в периоды бездействия), разбив стек на несколько параллельных и прикрыв их балансировщиками
5. stack pool - в конечном счете проблемой является сама последовательная логика стека, поэтому дальнейшего роста быстродействия можно добиться, убрав балансирующую машинерию и превратив стек в тщательно подогнанную под архитектуру слабоупорядоченную структуру, которой, по мнению автора, должно хватать для большинства приложений

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

#concurrency

www.tgoop.com/covalue/56

1.2K viewsedited  Jun 21, 2022 at 10:44

Shavit, [2011] "Data structures in the multicore age"

Относительно известная научно-популярная статья десятилетней давности одного из корифеев конкаренси о будущем многопоточного (библиотечного) программирования.

Начинается с мотивации законом Амдала о ботлнеке параллельных вычислений. Упоминает, что корректность в многопоточном сеттинге распадается на два аспекта: safety (относительно модели согласованности, например линеаризуемости) и liveness (условия прогресса - lock-free/wait-free и более экзотические). Также изменяются инструменты работы с complexity - добавляется модель stalls, нужно внимательно следить за contention. Делается предсказание, что развитие алгоритмов и структур данных пойдет по пути ослабления гарантий (кажется, спустя 10+ лет это до сих пор довольно нишевые вещи).

Основное время статья описывает в качестве примера процесс "ослабления" многопоточного стека на жаве, проходя несколько фаз:

1. стек под спинлоком - линеаризуем, не параллелен (deadlock-free), забивает шину из-за бесконтрольных спинов (обычно решается backoff-схемами)
2. lock-free стек - специализирует лок до CASа на голове стека
3. elimination backoff stack - убирает последовательный ботлнек, получая т.н. "дуальную" структуру - т.е. позволяя тредам оставлять "антиданные" (заявки) и передавать элементы напрямую без записи в стек, по прежнему линеаризуем
4. elimination tree - дуальность плохо работает в случае пакетов однотипных операций, поэтому можно ослабить согласованность до quiescent модели (иллюзия линейности только в периоды бездействия), разбив стек на несколько параллельных и прикрыв их балансировщиками
5. stack pool - в конечном счете проблемой является сама последовательная логика стека, поэтому дальнейшего роста быстродействия можно добиться, убрав балансирующую машинерию и превратив стек в тщательно подогнанную под архитектуру слабоупорядоченную структуру, которой, по мнению автора, должно хватать для большинства приложений

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

#concurrency

BY Covalue