Транзакционная память

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

Мотивация

Атомарность между двумя параллельными транзакциями с конфликтом

В параллельном программировании синхронизация требуется, когда параллельные потоки пытаются получить доступ к общему ресурсу. Низкоуровневые конструкции синхронизации потоков, такие как блокировки, пессимистичны и запрещают потокам, находящимся за пределами критической секции , запускать код, защищенный критической секцией. Процесс применения и снятия блокировок часто функционирует как дополнительные накладные расходы в рабочих нагрузках с небольшим количеством конфликтов между потоками. Транзакционная память обеспечивает оптимистичное управление параллелизмом , позволяя потокам работать параллельно с минимальным вмешательством. ^[2] Цель систем транзакционной памяти — прозрачно поддерживать области кода, отмеченные как транзакции, путем обеспечения атомарности , согласованности и изоляции .

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

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

def  transfer_money ( from_account ,  to_account ,  amount ): """Перевести деньги с одного счета на другой.""" с транзакцией (): from_account . balance -= amount to_account . balance += amount         

В коде блок, определенный как «транзакция», гарантированно атомарен, согласован и изолирован базовым внедрением транзакционной памяти и прозрачен для программиста. Переменные внутри транзакции защищены от внешних конфликтов, что гарантирует, что либо передается правильная сумма, либо не выполняется никаких действий вообще. Обратите внимание, что ошибки, связанные с параллелизмом, все еще возможны в программах, которые используют большое количество транзакций, особенно в программных реализациях, где библиотека, предоставляемая языком, не может обеспечить правильное использование. Ошибки, внесенные через транзакции, часто бывает трудно отладить, поскольку точки останова не могут быть размещены внутри транзакции. ^[2]

Транзакционная память ограничена тем, что требует абстракции разделяемой памяти. Хотя программы транзакционной памяти не могут создавать тупик, программы все равно могут страдать от динамической блокировки или нехватки ресурсов . Например, более длинные транзакции могут многократно возвращаться в ответ на несколько более мелких транзакций, тратя время и энергию. ^[2]

Аппаратное обеспечение против программного обеспечения

Аппаратная транзакционная память с использованием битов чтения и записи

Абстракция атомарности в транзакционной памяти требует аппаратного механизма для обнаружения конфликтов и отмены любых изменений, внесенных в общие данные. ^[3] Аппаратные транзакционные системы памяти могут включать модификации процессоров, кэша и протокола шины для поддержки транзакций. ^{[4] [5] [6] [7] [8]} Спекулятивные значения в транзакции должны быть буферизированы и оставаться невидимыми для других потоков до времени фиксации. Большие буферы используются для хранения спекулятивных значений, избегая распространения записи через базовый протокол когерентности кэша . Традиционно буферы были реализованы с использованием различных структур в иерархии памяти, таких как очереди хранения или кэши. Буферы, расположенные дальше от процессора, такие как кэш L2, могут содержать больше спекулятивных значений (до нескольких мегабайт). Оптимальный размер буфера все еще является предметом споров из-за ограниченного использования транзакций в коммерческих программах. ^[3] В реализации кэша строки кэша обычно дополняются битами чтения и записи. Когда контроллер оборудования получает запрос, контроллер использует эти биты для обнаружения конфликта. Если из параллельной транзакции обнаружен конфликт сериализуемости, то спекулятивные значения отбрасываются. При использовании кэшей система может ввести риск ложных конфликтов из-за использования гранулярности строк кэша. ^[3] Load-link/store-conditional (LL/SC), предлагаемый многими RISC- процессорами, можно рассматривать как самую базовую поддержку транзакционной памяти; однако LL/SC обычно работает с данными, которые имеют размер собственного машинного слова, поэтому поддерживаются только транзакции с одним словом. ^[4] Хотя аппаратная транзакционная память обеспечивает максимальную производительность по сравнению с программными альтернативами, в настоящее время наблюдается ограниченное использование.

Программная транзакционная память обеспечивает семантику транзакционной памяти в программной библиотеке времени выполнения или языке программирования ^[9] и требует минимальной аппаратной поддержки (обычно атомарной операции сравнения и обмена или эквивалента). Как недостаток, программные реализации обычно имеют потерю производительности по сравнению с аппаратными решениями. Аппаратное ускорение может снизить некоторые из накладных расходов, связанных с программной транзакционной памятью.

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

История

Одной из самых ранних реализаций транзакционной памяти был буфер хранения gated, используемый в процессорах Crusoe и Efficeon компании Transmeta . Однако он использовался только для облегчения спекулятивных оптимизаций для двоичной трансляции, а не для какой-либо формы спекулятивной многопоточности или предоставления ее напрямую программистам. Azul Systems также реализовала аппаратную транзакционную память для ускорения своих Java -приложений, но это также было скрыто от посторонних. ^[11]

Sun Microsystems реализовала аппаратную транзакционную память и ограниченную форму спекулятивной многопоточности в своем высокопроизводительном процессоре Rock . Эта реализация доказала, что ее можно использовать для обхода блокировок и более сложных гибридных систем транзакционной памяти, где транзакции обрабатываются с помощью комбинации аппаратного и программного обеспечения. Процессор Rock был отменен в 2009 году, как раз перед приобретением Oracle ; хотя фактические продукты так и не были выпущены, ряд прототипов систем был доступен исследователям. ^[11]

В 2009 году AMD предложила Advanced Synchronization Facility (ASF), набор расширений x86 , которые обеспечивают очень ограниченную форму поддержки аппаратной транзакционной памяти. Цель состояла в том, чтобы предоставить аппаратные примитивы, которые можно было бы использовать для высокоуровневой синхронизации, такие как программная транзакционная память или алгоритмы без блокировок. Однако AMD не объявила, будет ли ASF использоваться в продуктах, и если да, то в какие сроки. ^[11]

Совсем недавно, в 2011 году, IBM объявила, что Blue Gene/Q имеет аппаратную поддержку как транзакционной памяти, так и спекулятивной многопоточности. Транзакционная память может быть сконфигурирована в двух режимах; первый — неупорядоченный и одноверсионный режим, в котором запись из одной транзакции вызывает конфликт с любыми транзакциями, читающими тот же адрес памяти. Второй режим предназначен для спекулятивной многопоточности, обеспечивая упорядоченную многоверсионную транзакционную память. Спекулятивные потоки могут иметь разные версии одного и того же адреса памяти, а аппаратная реализация отслеживает возраст каждого потока. Младшие потоки могут получать доступ к данным из более старых потоков (но не наоборот), а записи по тому же адресу основаны на порядке потоков. В некоторых случаях зависимости между потоками могут привести к прерыванию работы младших версий. ^[11]

Расширения транзакционной синхронизации Intel ( TSX) доступны в некоторых процессорах Skylake . Ранее они также были реализованы в процессорах Haswell и Broadwell , но оба раза реализации оказывались дефектными, и поддержка TSX была отключена. Спецификация TSX описывает API транзакционной памяти для использования разработчиками программного обеспечения, но не содержит подробностей о технической реализации. ^[11] Архитектура ARM имеет похожее расширение. ^[12]

Начиная с GCC 4.7 доступна экспериментальная библиотека для транзакционной памяти, которая использует гибридную реализацию. Вариант Python PyPy также вводит транзакционную память в язык.

Доступные реализации

• Аппаратное обеспечение:
  • Расширение транзакционной памяти Arm (TME) ^[13]
  • Процессор Blue Gene/Q от IBM (суперкомпьютер Sequoia) ^[14]
  • IBM zEnterprise EC12 , первый коммерческий сервер, включающий инструкции процессора транзакционной памяти
  • Расширения транзакционной синхронизации Intel (TSX), доступные в некоторых процессорах на базе Haswell и более новых, пока не будут удалены в Comet Lake
  • IBM POWER8 и 9 , удалены в Power10 ( Power ISA v.3.1 ) ^{[15] [16] [17]}
  • Процессор Rock (отменен Oracle )
• Программное обеспечение:
  • Вега 2 от Azul Systems ^[18]
  • Монада STM в компиляторе Glasgow Haskell ^[19]
  • STMX в Common Lisp ^[20]
  • Ссылки в Clojure
  • gcc 4.7+ для C/C++ ^{[21] [22] [23] [24]}
  • PyPy ^[25]
  • Часть picotm Transaction Framework для C ^[26]
  • TVar в concurrent-ruby, библиотеке параллельной обработки для Ruby ^[27]
  • Стих ^[28]

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

• Семантика памяти
• Автоматическое взаимное исключение

Ссылки

1. Харрис, Тим; Ларус, Джеймс; Раджвар, Рави (2010-06-02). «Транзакционная память, 2-е издание». Synthesis Lectures on Computer Architecture . 5 (1): 1–263. doi :10.2200/S00272ED1V01Y201006CAC011. ISSN  1935-3235.
2. "Транзакционная память: история и развитие". Kukuruku Hub . Получено 2016-11-16 .
3. Солихин, Ян (2016). Основы параллельной многоядерной архитектуры . Беркли, Калифорния: Chapman & Hall. С. 287–292. ISBN 978-1-4822-1118-4.
4. Herlihy, Maurice; Moss, J. Eliot B. (1993). "Транзакционная память: Архитектурная поддержка структур данных без блокировок" (PDF) . Труды 20-го Международного симпозиума по архитектуре компьютеров (ISCA) . стр. 289–300.
5. Стоун, Дж. М.; Стоун, Х. С.; Хайдельбергер, П.; Турек, Дж. (1993). «Множественные бронирования и обновление Оклахомы». IEEE Параллельная и распределенная технология: системы и приложения . 1 (4): 58–71. doi :10.1109/88.260295. S2CID  11017196.
6. Хаммонд, Л.; Вонг, В.; Чен, М.; Карлстром, Б.Д.; Дэвис, Дж.Д.; Герцберг, Б.; Прабху, МК; Хонгго Виджая; Козиракис, К.; Олукотун, К. (2004). «Когерентность и согласованность транзакционной памяти». Труды 31-го ежегодного Международного симпозиума по архитектуре компьютеров (ISCA) . стр. 102–13. doi :10.1109/ISCA.2004.1310767.
7. Ananian, CS; Asanovic, K.; Kuszmaul, BC; Leiserson, CE; Lie, S. (2005). "Неограниченная транзакционная память". 11-й Международный симпозиум по архитектуре высокопроизводительных компьютеров . стр. 316–327. doi :10.1109/HPCA.2005.41. ISBN 0-7695-2275-0.
8. "LogTM: Транзакционная память на основе журналов" (PDF) . WISC.
9. "The ATOMOΣ Transactional Programming Language" (PDF) . Стэнфорд. Архивировано из оригинала (PDF) 2008-05-21 . Получено 2009-06-15 .
10. Одайра, Р.; Кастанос, Дж. Г.; Накаике, Т. (2013). «Масштабируются ли программы на C и Java по-разному в аппаратной транзакционной памяти?». Международный симпозиум IEEE 2013 года по характеристике рабочей нагрузки (IISWC) . стр. 34. doi :10.1109/IISWC.2013.6704668. ISBN 978-1-4799-0555-3.
11. Дэвид Кантер (2012-08-21). "Анализ транзакционной памяти Haswell". Real World Technologies . Получено 2013-11-19 .
12. "Arm выпускает SVE2 и TME для архитектуры A-profile - Блог процессоров - Процессоры - Сообщество Arm". community.arm.com . 18 апреля 2019 г. Получено 25.05.2019 .
13. "Внутренние функции расширения транзакционной памяти (TME)" . Получено 2020-05-05 .
14. «IBM внедряет транзакционную память в процессор». EE Times.
15. Брайан Холл; Райан Арнольд; Питер Бергнер; Вайнер душ Сантос Мошетта; Роберт Эненкель; Пэт Хауген; Майкл Р. Мейснер; Алекс Мерикас; Филипп Олер; Берни Шифер; Брайан Ф. Вил; Суреш Уорриер; Дэниел Забава; Адхемерваль Занелла (2014). Методы оптимизации и настройки производительности процессоров IBM, включая IBM POWER8 (PDF) . Красные книги IBM. стр. 37–40. ISBN 978-0-7384-3972-3.
16. Вэй Ли, встроенные функции аппаратной транзакционной памяти компилятора IBM XL для IBM AIX в системах на базе процессора IBM POWER8
17. "Power ISA Version 3.1". openpowerfoundation.org. 2020-05-01 . Получено 2020-10-10 .
18. Java на 1000 ядер – Рассказы о совместном проектировании оборудования и программного обеспечения на YouTube
19. "Control.Monad.STM". hackage.haskell.org . Получено 2020-02-06 .
20. "Домашняя страница STMX".
21. Вонг, Майкл. "Конструкции транзакционного языка для C++" (PDF) . Получено 12 января 2011 г.
22. «Краткое руководство по транзакционной памяти GCC».
23. «Параметры диалекта C — использование коллекции компиляторов GNU (GCC)».
24. «Транзакционная память — GCC Wiki».
25. Риго, Армин. «Использование всех этих ядер: транзакционная память в PyPy». europython.eu . Получено 7 апреля 2015 г. .
26. "picotm - Портативный интегрированный настраиваемый и открытый менеджер транзакций".
27. "Конкурентный::TVar".
28. Pizlo, Phil (2024-03-15). "Перенос семантики транзакционной памяти Verse на C++" . Получено 2024-08-18 .

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

• Харрис, Тим; Ларус, Джеймс Р.; Раджвар, Рави (декабрь 2010 г.), Транзакционная память, 2-е издание , Лекции по синтезу компьютерной архитектуры, т. 5, Морган и Клейпул, стр. 1–263, doi :10.2200/S00272ED1V01Y201006CAC011
• Маккенни, Пол Э.; Майкл, Магед М.; Триплетт, Джош; Уолпол, Джонатан (июль 2010 г.). «Почему трава не может быть зеленее на другой стороне: сравнение блокировки и транзакционной памяти». SIGOPS Oper. Syst. Rev. 44 ( 3). Нью-Йорк, штат Нью-Йорк, США: ACM : 93–101. doi : 10.1145/1842733.1842749. ISSN  0163-5980. S2CID  1917393.

• Дейв Дайс, Йосси Лев, Марк Мойр, Дэн Нуссбаум и Марек Ольшевски. (2009) "Ранний опыт коммерческой аппаратной реализации транзакционной памяти". Технический отчет Sun Microsystems (60 стр.) SMLI TR-2009-180. Краткая версия появилась на ASPLOS'09 doi :10.1145/1508244.1508263
• Эми Ванг, Мэтью Годе, Пэн Ву, Хосе Нельсон Амарал, Мартин Омахт, Кристофер Бартон, Рауль Сильвера и Магед Майкл. «Оценка аппаратной поддержки Blue Gene/Q для транзакционной памяти. Архивировано 27 июня 2013 г. в Wayback Machine ». В трудах 21-й международной конференции по параллельным архитектурам и методам компиляции, стр. 127–136. ACM, 2012.
• Jacobi, C., Slegel, T. и Greiner, D. (2012, декабрь). "Архитектура транзакционной памяти и ее реализация для IBM System z. Архивировано 4 марта 2016 г. в Wayback Machine ". В Microarchitecture (MICRO), 45-й ежегодный международный симпозиум IEEE/ACM 2012 г. (стр. 25–36). IEEE.
• Гарольд В. Кейн, Магед М. Майкл, Брэд Фрей, Кэти Мэй, Дерек Уильямс и Хунг Ле. «Надежная архитектурная поддержка транзакционной памяти в архитектуре Power». В ISCA '13 Proceedings of the 40th Annual International Symposium on Computer Architecture, стр. 225–236, ACM, 2013. doi :10.1145/2485922.2485942

Внешние ссылки

• Майкл Нойлинг (IBM), «Что происходит с аппаратной транзакционной памятью!?!» вступительный доклад на linux.conf.au 2014
• Transactional Memory Online: Категоризированная библиография о транзакционной памяти