Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Мотивация [ править ]

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

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

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

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

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

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

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

Аппаратное обеспечение и программное обеспечение [ править ]

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

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

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

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

История [ править ]

Одна из самых ранних реализаций транзакционной памяти был закрытый магазин буфер , используемый в Transmeta «s Крузо и Efficeon процессоров. Однако это использовалось только для облегчения умозрительных оптимизаций для двоичной трансляции, а не для любой формы умозрительной многопоточности или непосредственного раскрытия ее программистам. 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 «s транзакционных синхронизации расширений (TSX) в некоторых из Skylake процессоров. Ранее он также был реализован в процессорах Haswell и Broadwell , но оба раза реализации оказывались дефектными и поддержка TSX была отключена. Спецификация TSX описывает API транзакционной памяти для использования разработчиками программного обеспечения, но не раскрывает детали технической реализации. [11] Архитектура ARM имеет аналогичное расширение. [12]

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

Доступные реализации [ править ]

  • Аппаратное обеспечение:
    • Расширение транзакционной памяти Arm (TME) [13]
    • Рок-процессор (отменен Oracle )
    • Процессор Blue Gene / Q от IBM (суперкомпьютер Sequoia) [14]
    • IBM zEnterprise EC12 , первый коммерческий сервер, включающий инструкции процессора транзакционной памяти
    • Расширения Intel Transactional Synchronization Extensions (TSX) доступны в некоторых процессорах на базе Haswell и новее, пока не будут удалены в Comet Lake.
    • IBM POWER8 и 9 , удаленные в POWER10 ( Power ISA v.3.1 ) [15] [16] [17]
  • Програмное обеспечение:
    • Vega 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 для C [26]
    • TVar в concurrent-ruby, библиотека параллелизма для Ruby [27]

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ Харрис, Тим; Ларус, Джеймс; Раджвар, Рави (02.06.2010). «Транзакционная память, 2-е издание». Синтез лекций по компьютерной архитектуре . 5 (1): 1–263. DOI : 10.2200 / S00272ED1V01Y201006CAC011 . ISSN  1935-3235 .
  2. ^ a b c d «Транзакционная память: история и развитие» . Кукуруку Хаб . Проверено 16 ноября 2016 .
  3. ^ a b c Солихин, Ян (2016). Основы параллельной многоядерной архитектуры . Беркли, Калифорния: Chapman & Hall. С. 287–292. ISBN 978-1-4822-1118-4.
  4. ^ а б Херлихи, Морис; Мосс, Дж. Элиот Б. (1993). «Транзакционная память: Архитектурная поддержка структур данных без блокировок» (PDF) . Материалы 20-го Международного симпозиума по компьютерной архитектуре (ISCA) . С. 289–300.
  5. ^ Стоун, JM; Камень, HS; Heidelberger, P .; Турек, Дж. (1993). «Множественные резервации и обновление Оклахомы». Параллельные и распределенные технологии IEEE: системы и приложения . 1 (4): 58–71. DOI : 10.1109 / 88.260295 .
  6. ^ Хаммонд, L; Вонг, В .; Chen, M .; Карлстром, Б.Д .; Дэвис, JD; Hertzberg, B .; Прабху, МК; Хонгго Виджая; Козыракис, Ц .; Олюкотун, К. (2004). «Согласованность и согласованность транзакционной памяти». Материалы 31-го ежегодного Международного симпозиума по компьютерной архитектуре (ISCA) . С. 102–13. DOI : 10.1109 / ISCA.2004.1310767 .
  7. ^ Ананян, CS; Асанович, К .; Кузмаул, Британская Колумбия; Лейзерсон, CE; Ли, С. (2005). «Неограниченная транзакционная память». 11-й Международный симпозиум по архитектуре высокопроизводительных компьютеров . С. 316–327. DOI : 10.1109 / HPCA.2005.41 . ISBN 0-7695-2275-0.
  8. ^ «LogTM: транзакционная память на основе журналов» (PDF) . WISC.
  9. ^ "Транзакционный язык программирования ATOMOΣ" (PDF) . Стэнфорд.
  10. ^ Odaira, R .; Castanos, JG; Накаике, Т. (2013). «По-разному ли масштабируются программы C и Java на аппаратной транзакционной памяти?». 2013 Международный симпозиум IEEE по характеристике рабочей нагрузки (IISWC) . п. 34. DOI : 10,1109 / IISWC.2013.6704668 . ISBN 978-1-4799-0555-3.
  11. ^ a b c d e Дэвид Кантер (21 августа 2012 г.). «Анализ транзакционной памяти Haswell» . Технологии реального мира . Проверено 19 ноября 2013 .
  12. ^ «Arm выпускает SVE2 и TME для архитектуры A-профиля - Блог процессоров - Процессоры - Сообщество Arm» . community.arm.com . Проверено 25 мая 2019 .
  13. ^ «Внутренние функции Transactional Memory Extension (TME)» . Проверено 5 мая 2020 .
  14. ^ "IBM устанавливает транзакционную память в ЦП" . EE Times.
  15. ^ Брайан Холл; Райан Арнольд; Питер Бергнер; Вайнер душ Сантуш Москетта; Роберт Эненкель; Пэт Хауген; Майкл Р. Мейснер; Алекс Мерикас; Филипп Элер; Берни Шифер; Брайан Ф. Вил; Суреш Уорриер; Даниэль Забава; Адхемервал Занелла (2014). Методы оптимизации и настройки производительности для процессоров IBM, включая IBM POWER8 (PDF) . IBM Redbooks. С. 37–40. ISBN  978-0-7384-3972-3.
  16. ^ Вей Ли, аппаратный компилятор IBM XL, встроенные функции транзакционной памяти для IBM AIX в системах на базе процессоров IBM POWER8
  17. ^ "Power ISA версии 3.1" . openpowerfoundation.org. 2020-05-01 . Проверено 10 октября 2020 .
  18. ^ Java на 1000 ядер - Рассказы об аппаратном и программном обеспечении CoDesign на YouTube
  19. ^ "Control.Monad.STM" . hackage.haskell.org . Проверено 6 февраля 2020 .
  20. ^ "Домашняя страница STMX" .
  21. ^ Вонг, Майкл. «Транзакционные языковые конструкции для C ++» (PDF) . Проверено 12 января 2011 .
  22. ^ "Краткое руководство по транзакционной памяти GCC" .
  23. ^ «Параметры диалекта C - Использование коллекции компиляторов GNU (GCC)» .
  24. ^ "TransactionalMemory - GCC Wiki" .
  25. ↑ Риго, Армин. «Использование всех этих ядер: транзакционная память в PyPy» . europython.eu . Проверено 7 апреля 2015 года .
  26. ^ «picotm - Портативный интегрированный настраиваемый и открытый менеджер транзакций» .
  27. ^ "Параллельно :: TVar" .

Дальнейшее чтение [ править ]

  • Харрис, Тим; Larus, James R .; Rajwar, Рави (декабрь 2010), транзакционной памяти, 2 - е издание , Synthesis Лекции по компьютерной архитектуры, 5 , Morgan & Claypool, С. 1-263,. DOI : 10,2200 / S00272ED1V01Y201006CAC011
  • Маккенни, Пол Э .; Майкл, Магед М .; Триплет, Джош; Уолпол, Джонатан (июль 2010 г.). «Почему трава не может быть зеленее с другой стороны: сравнение блокировки и транзакционной памяти». SIGOPS Oper. Syst. Ред . Нью-Йорк, Нью-Йорк, США: ACM . 44 (3): 93–101. DOI : 10.1145 / 1842733.1842749 . ISSN  0163-5980 .
  • Дэйв Дайс, Йоси Лев, Марк Мойр, Дэн Нуссбаум и Марек Ольшевски. (2009) «Ранний опыт реализации коммерческой аппаратной транзакционной памяти». Технический отчет Sun Microsystems (60 стр.) SMLI TR-2009-180. Краткая версия появилась на ASPLOS'09 doi : 10.1145 / 1508244.1508263
  • Эми Ван, Мэтью Годе, Пэн Ву, Хосе Нельсон Амарал, Мартин Омахт, Кристофер Бартон, Рауль Сильвера и Магед Майкл. « Оценка аппаратной поддержки Blue Gene / Q для транзакционной памяти ». В материалах 21-й международной конференции по параллельным архитектурам и методам компиляции, стр. 127–136. ACM, 2012.
  • Якоби, К., Слегель, Т., и Грейнер, Д. (2012, декабрь). « Архитектура и реализация транзакционной памяти для IBM System z ». In 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
  • Транзакционная память онлайн : категоризированная библиография по транзакционной памяти