Загрузка ссылки/сохранение при условии

В информатике , с привязкой к нагрузке/условием хранения. ^[1] ( LL/SC ), иногда называемый зарезервированным по нагрузке/условным сохранением ^[2] ( LR/SC ) — пара инструкций, используемых в многопоточности для достижения синхронизации . Load-link возвращает текущее значение ячейки памяти , в то время как последующее условие сохранения в той же ячейке памяти сохранит новое значение только в том случае, если с момента загрузки ссылки в этой ячейке не произошло никаких обновлений. Вместе это реализует безблокировочную , атомарную операцию чтения - изменения-записи .

«Связь с нагрузкой» также известна как связь с загрузкой . ^[3] нагрузка зарезервирована , ^[2] и с блокировкой нагрузки . ^{[ нужна ссылка ]}

LL/SC изначально был ^[4] предложено Йенсеном, Хагенсеном и Бротоном для мультипроцессора S-1 AAP. ^[1] в Ливерморской национальной лаборатории имени Лоуренса .

Сравнение LL/SC и сравнения и замены

Если произошли какие-либо обновления, условие сохранения гарантированно завершится неудачно, даже если значение, прочитанное ссылкой загрузки, с тех пор было восстановлено. Таким образом, пара LL/SC более надежна, чем чтение с последующим сравнением и заменой (CAS), которое не обнаружит обновления, если старое значение было восстановлено (см. проблему ABA ).

Реальные реализации LL/SC не всегда успешны, даже если в рассматриваемой области памяти нет одновременных обновлений. Любые исключительные события между двумя операциями, такие как переключение контекста , другая ссылка загрузки или даже (на многих платформах) другая операция загрузки или сохранения, приведут к ложному сбою условия сохранения. будут транслироваться какие-либо Старые реализации потерпят неудачу, если по шине памяти называют это слабым LL/SC, поскольку оно нарушает многие теоретические алгоритмы LL/SC. обновления. Исследователи ^[5] Слабость относительна, и для некоторых алгоритмов можно использовать некоторые слабые реализации.

LL/SC сложнее имитировать, чем CAS. Кроме того, остановка выполнения кода между парными инструкциями LL/SC, например, при пошаговом выполнении кода, может помешать продвижению вперед, что усложняет отладку. ^[6]

Тем не менее, LL/SC эквивалентен CAS в том смысле, что любой примитив может быть реализован в терминах другого, за O(1) и без ожидания . ^[7]

Реализации

Инструкции LL/SC поддерживаются:

Альфа : ldl_l ^[8]/stl_c ^[9] и ldq_l ^[8]/stq_c ^[9]
PowerPC / Power ISA : lwarx/stwcx и ldarx/stdcx ^[10]^[11]
MIPS : ll/sc ^[12] и ллд/скд ^[13]
ARM : ldrex/strex (ARMv6, ^[14] v7 и v8-М ^[15]) и ldxr/stxr (ARMv8-A ^[16])
RISC-V : lr/sc ^[2]
АРК : LLOCK/СКОНД

Некоторые процессоры ^{[ который? ]} требуют, чтобы адрес, к которому осуществляется доступ, был настроен исключительно в режиме сквозной записи.

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

Все эти платформы обеспечивают слабую ^{[ нужны разъяснения ]} LL/SC. Реализация PowerPC позволяет паре LL/SC переносить загрузки и даже сохранения в другие строки кэша (хотя этот подход уязвим для ложного совместного использования строк кэша). Это позволяет реализовать, например, подсчет ссылок без блокировок при изменении графов объектов с произвольным повторным использованием счетчика (что в противном случае требует двойного сравнения и замены , DCAS). RISC-V обеспечивает архитектурную гарантию возможного прогресса для последовательностей LL/SC ограниченной длины.

Некоторые реализации ARM определяют зависящие от платформы блоки размером от 8 до 2048 байт, и попытка LL/SC в любом заданном блоке завершается неудачей, если между LL и SC существует нормальный доступ к памяти внутри одного и того же блока. Другие реализации ARM терпят неудачу, если где-то во всем адресном пространстве происходят изменения. Первая реализация является более сильной и практичной.

LL/SC имеет два преимущества перед CAS при проектировании архитектуры загрузки-хранения : чтение и запись представляют собой отдельные инструкции, как того требует философия проектирования (и архитектура конвейера ); и обе инструкции могут выполняться с использованием только двух регистров (адреса и значения), что естественно соответствует обычным ISA с двумя операндами . CAS, с другой стороны, требует трех регистров (адрес, старое значение, новое значение) и зависимости между считанным и записанным значением. x86 , будучи архитектурой CISC , не имеет этого ограничения; хотя современные чипы вполне могут внутренне преобразовать инструкцию CAS в отдельные микрооперации LL/SC .

Расширения

Аппаратные реализации LL/SC обычно не допускают вложения пар LL/SC. ^[17] Механизм вложения LL/SC может использоваться для предоставления примитива MCAS (многословный CAS, где слова могут быть разбросаны). ^[18] В 2013 году Тревор Браун, Фейт Эллен и Эрик Рупперт реализовали в программном обеспечении многоадресное расширение LL/SC (которое они называют LLX/SCX), основанное на автоматизированной генерации кода; ^[19] они использовали его для реализации одного из наиболее эффективных параллельных двоичных деревьев поиска (на самом деле хроматического дерева ), немного обойдя на основе JDK CAS реализацию списка пропуска . ^[20]

См. также

Ссылки

^ Jump up to: ^а ^б «Проект С-1» . Стэнфордская вики по информатике . 2018-11-30.
^ Jump up to: ^а ^б ^с Эндрю Уотерман; Крсте Асанович , ред. (07.05.2017). «7.2 Инструкции, зарезервированные для загрузки/сохранения». Руководство по набору команд RISC-V, Том 1: ISA уровня пользователя, версия 2.2 (PDF) .
^ US20030217115A1 , Роулендс, Джозеф, «Условный механизм загрузки/сохранения в системе CC-NUMA», выпущено 20 ноября 2003 г.
^ Херлихи, Морис (1 ноября 1993 г.). «Методология реализации высококонкурентных объектов данных» . Транзакции ACM в языках и системах программирования . 15 (5): 745–770. дои : 10.1145/161468.161469 . ISSN 0164-0925 .
^ Бекманн, Натан. «Синхронизация» (PDF) . 15-740: Компьютерная архитектура, осень 2018 г. Университет Карнеги-Меллон . Проверено 23 апреля 2021 г.
^ Кено Фишер (02 мая 2020 г.). «Предварительный обзор функций Julia 1.5: отчеты об ошибках путешествий во времени (Linux)» . Проверено 14 мая 2020 г.
^ Джеймс Х. Андерсон; Марк Мойр (1995). «Универсальные конструкции для многообъектных операций». PODC '95 Материалы четырнадцатого ежегодного симпозиума ACM по принципам распределенных вычислений . АКМ. стр. 184–193. дои : 10.1145/224964.224985 . ISBN 0-89791-710-3 . S2CID 8204331 . См. их таблицу 1, рисунки 1 и 2 и, в частности, раздел 2.
^ Jump up to: ^а ^б «Справочное руководство по архитектуре Alpha» (PDF) . стр. 4–9~4–12 . Проверено 26 января 2024 г.
^ Jump up to: ^а ^б «Справочное руководство по архитектуре Alpha» (PDF) . стр. 4–13~4–15 . Проверено 26 января 2024 г.
^ Мэй, Кэти; Силха, Эд; Симпсон, Эйк; Уоррен, Хэнк (1993). Архитектура PowerPC: СПЕЦИФИКАЦИЯ НОВОГО СЕМЕЙСТВА RISC-ПРОЦЕССОРОВ . Morgan Kaufmann PUblishers, Inc., стр. 336–338, 465. ISBN. 1-55860-316-6 .
^ Качмарчик, Кэри (1995). Оптимизация кода PowerPC . Издательство Аддисон-Уэсли. стр. 71–72. ISBN 0-201-40839-2 .
^ «УКАЗАНИЯ ПО ПРИМЕНЕНИЮ Примитивы синхронизации MIPS R4000» (PDF) . п. 9 . Проверено 27 декабря 2023 г.
^ «УКАЗАНИЯ ПО ПРИМЕНЕНИЮ Примитивы синхронизации MIPS R4000» (PDF) . п. 5 . Проверено 27 декабря 2023 г.
^ «Версия процессора ARM11 MPCore™: Техническое справочное руководство r2p0» . п. 301-302(8-7,8-8) . Проверено 14 декабря 2023 г.
^ «Справочное руководство по архитектуре Arm®v8-M» . п. 278 . Проверено 14 декабря 2023 г.
^ «Примитивы синхронизации ARMv8-A» . п. 6 . Проверено 14 декабря 2023 г.
^ Джеймс Р. Ларус; Рави Раджвар (2007). Транзакционная память . Морган и Клейпул. п. 55. ИСБН 978-1-59829-124-7 .
^ Кейр Фрейзер (февраль 2004 г.). Практическая свобода блокировки (PDF) (Технический отчет). Компьютерная лаборатория Кембриджского университета. п. 20. UCAM-CL-TR-579.
^ Браун, Тревор; Эллен, Фейт; Руперт, Эрик (2013). «Прагматические примитивы для неблокирующих структур данных» (PDF) . PODC '13 Материалы симпозиума ACM 2013 года по принципам распределенных вычислений . АКМ. стр. 13–22. arXiv : 1712.06688 . дои : 10.1145/2484239.2484273 . ISBN 978-1-4503-2065-8 . S2CID 6537417 . См. также слайды
^ Тревор Браун; Фейт Эллен; Эрик Рупперт (2014). «Общий метод создания неблокирующих деревьев» (PDF) . PPoPP '14 Симпозиум ACM SIGPLAN по принципам и практике параллельного программирования . АКМ. стр. 329–342. arXiv : 1712.06687 . дои : 10.1145/2555243.2555267 . ISBN 978-1-4503-2656-8 . S2CID 9442380 .

Дженсен, Эрик Х.; Хагенсен, Гэри В.; Бротон, Джеффри М. (ноябрь 1987 г.). Новый подход к монопольному доступу к данным в мультипроцессорах с общей памятью (PDF) (Технический отчет). Ливерморская национальная лаборатория Лоуренса. UCRL-97663. Архивировано из оригинала (PDF) 02 февраля 2017 г. Проверено 22 февраля 2012 г.
Брунер, Джон Д.; Хагенсен, Гэри В.; Дженсен, Эрик Х.; Паттин, Джей С.; Бротон, Джеффри М. (11 ноября 1987 г.). Когерентность кэша на S-1 AAP (PDF) (Технический отчет). Ливерморская национальная лаборатория Лоуренса. UCRL-97646. Архивировано из оригинала (PDF) 2 февраля 2017 года . Проверено 10 ноября 2013 г.
Детлефс, Д.; Мартин, П.; Мойр, М.; Стил-младший, Гай Л. (2001). «Блокировочный подсчет ссылок». PODC '01 Материалы двадцатого ежегодного симпозиума ACM по принципам распределенных вычислений . АКМ. стр. 190–9. CiteSeerX 10.1.1.92.8221 . дои : 10.1145/383962.384016 . ISBN 1-58113-383-9 .
Рейнхольц, Кирк (декабрь 2004 г.). «Указатели атомарного подсчета ссылок» . Журнал пользователей C/C++ .
Сайты, RL (февраль 1993 г.). «Архитектура Альфа AXP» . Комм. АКМ . 36 (2): 33–44. дои : 10.1145/151220.151226 . S2CID 5473184 .

[S-1-1] Jump up to: ^а ^б «Проект С-1» . Стэнфордская вики по информатике . 2018-11-30.

[RISCV-2] Jump up to: ^а ^б ^с Эндрю Уотерман; Крсте Асанович , ред. (07.05.2017). «7.2 Инструкции, зарезервированные для загрузки/сохранения». Руководство по набору команд RISC-V, Том 1: ISA уровня пользователя, версия 2.2 (PDF) .

[3] US20030217115A1 , Роулендс, Джозеф, «Условный механизм загрузки/сохранения в системе CC-NUMA», выпущено 20 ноября 2003 г.

[4] Херлихи, Морис (1 ноября 1993 г.). «Методология реализации высококонкурентных объектов данных» . Транзакции ACM в языках и системах программирования . 15 (5): 745–770. дои : 10.1145/161468.161469 . ISSN 0164-0925 .

[5] Бекманн, Натан. «Синхронизация» (PDF) . 15-740: Компьютерная архитектура, осень 2018 г. Университет Карнеги-Меллон . Проверено 23 апреля 2021 г.

[Fischer2020-6] Кено Фишер (02 мая 2020 г.). «Предварительный обзор функций Julia 1.5: отчеты об ошибках путешествий во времени (Linux)» . Проверено 14 мая 2020 г.

[Anderson1995-7] Джеймс Х. Андерсон; Марк Мойр (1995). «Универсальные конструкции для многообъектных операций». PODC '95 Материалы четырнадцатого ежегодного симпозиума ACM по принципам распределенных вычислений . АКМ. стр. 184–193. дои : 10.1145/224964.224985 . ISBN 0-89791-710-3 . S2CID 8204331 . См. их таблицу 1, рисунки 1 и 2 и, в частности, раздел 2.

[alpha-ll-8] Jump up to: ^а ^б «Справочное руководство по архитектуре Alpha» (PDF) . стр. 4–9~4–12 . Проверено 26 января 2024 г.

[alpha-sc-9] Jump up to: ^а ^б «Справочное руководство по архитектуре Alpha» (PDF) . стр. 4–13~4–15 . Проверено 26 января 2024 г.

[10] Мэй, Кэти; Силха, Эд; Симпсон, Эйк; Уоррен, Хэнк (1993). Архитектура PowerPC: СПЕЦИФИКАЦИЯ НОВОГО СЕМЕЙСТВА RISC-ПРОЦЕССОРОВ . Morgan Kaufmann PUblishers, Inc., стр. 336–338, 465. ISBN. 1-55860-316-6 .

[11] Качмарчик, Кэри (1995). Оптимизация кода PowerPC . Издательство Аддисон-Уэсли. стр. 71–72. ISBN 0-201-40839-2 .

[12] «УКАЗАНИЯ ПО ПРИМЕНЕНИЮ Примитивы синхронизации MIPS R4000» (PDF) . п. 9 . Проверено 27 декабря 2023 г.

[13] «УКАЗАНИЯ ПО ПРИМЕНЕНИЮ Примитивы синхронизации MIPS R4000» (PDF) . п. 5 . Проверено 27 декабря 2023 г.

[14] «Версия процессора ARM11 MPCore™: Техническое справочное руководство r2p0» . п. 301-302(8-7,8-8) . Проверено 14 декабря 2023 г.

[15] «Справочное руководство по архитектуре Arm®v8-M» . п. 278 . Проверено 14 декабря 2023 г.

[16] «Примитивы синхронизации ARMv8-A» . п. 6 . Проверено 14 декабря 2023 г.

[LarusRajwar2007-17] Джеймс Р. Ларус; Рави Раджвар (2007). Транзакционная память . Морган и Клейпул. п. 55. ИСБН 978-1-59829-124-7 .

[Fraser2004-18] Кейр Фрейзер (февраль 2004 г.). Практическая свобода блокировки (PDF) (Технический отчет). Компьютерная лаборатория Кембриджского университета. п. 20. UCAM-CL-TR-579.

[Brown2013-19] Браун, Тревор; Эллен, Фейт; Руперт, Эрик (2013). «Прагматические примитивы для неблокирующих структур данных» (PDF) . PODC '13 Материалы симпозиума ACM 2013 года по принципам распределенных вычислений . АКМ. стр. 13–22. arXiv : 1712.06688 . дои : 10.1145/2484239.2484273 . ISBN 978-1-4503-2065-8 . S2CID 6537417 . См. также слайды

[Brown2014-20] Тревор Браун; Фейт Эллен; Эрик Рупперт (2014). «Общий метод создания неблокирующих деревьев» (PDF) . PPoPP '14 Симпозиум ACM SIGPLAN по принципам и практике параллельного программирования . АКМ. стр. 329–342. arXiv : 1712.06687 . дои : 10.1145/2555243.2555267 . ISBN 978-1-4503-2656-8 . S2CID 9442380 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]