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


    На фото: Blue Gene / P в Аргоннской национальной лаборатории

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

    В IBM (а как вы думали) заняты поиском решения этой задачи (один мой знакомый с юмором охарактеризовал ее как «узники блокировки»), так как голубой гигант остается самым крупным проектировщиком, изготовителем и поставщиком суперкомпьютерных кластеров, где синхронизированный доступ к памяти — камень преткновения.

    Есть и хорошие новости: в процессорах следующей модели Blue Gene / Q, которые будут питать 20-петафлопсный суперкомпьютер Sequoia, строящийся компанией в настоящее время для Ливерморской национальной лаборатории, реализована поддержка транзакционной памяти не на программном, а аппаратном, уровне. При успешных испытаниях эта технология докажет, что масштабируемое параллельное программирование может быть простой задачей (и в отсутствии параллельных алгоритмов) — это, в свою очередь, изменит ландшафт вычислений. Так как большинство исследований до сегодняшнего дня проводились именно в области реализации STM на уровне ПО, чипы BlueGene/Q позволят реально оценить разницу в скорости работы двух принципиально разных архитектур: HTM (hardware transactional memory) и традиционной STM.


    BlueGene/Q — это мультиядерная, 64-битная система на чипе, построенная по технологии PowerPC (если быть абсолютно конкретным, то это четырехтактная архитектура PowerPC A2). Каждый из чипов содержит 18 ядер, вместе набирающих вес в почти полтора миллиарда (1,47) транзисторов. 16 ядер используются для, собственно, вычислений, на одном работает операционная система, и, наконец последнее ядро отвечает за надежность вычислений всей системы. На частоте в 1,6 Ггц, каждый чип способен выдать 204,8 Гфлопс под напряжением в 55 Ватт. Естественно, частью чипа является и контроллеры памяти и операций ввода-вывода. Blue Gene/Q содержит 4 устройства вычислений над числами с плавающей запятой, что дает нам 4 выполненных операции за один такт на каждом ядре.

    Почему 18 ядер? Ответ: безопасность в избытке. Если на одном из ядер процессора был зафиксирован сбой, оно может быть отключено и переведено на скамейку «запасных». Собственно, обнаружение и изменение конфигурации «ошибочного» ядра может быть проведено на любом этапе производства или сборки системы — не только когда чип уже тестируется, но и на ранних этапах, например, инсталляции чипа в вычислительный кластер. В случае с Sequoia будет использоваться около 100 000 чипов, для того чтобы достичь заветных 20 петафлопс. Огромное количество процессоров делает задачу переназначения ядер очень важной: в компании IBM подсчитали, что при данном (100к) количестве чипов в суперкомпьютере каждые 3 недели в среднем будет выходить из строя 1 процессорный блок.

    Традиционная многопоточность: локи и дедлоки


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

    Стандартное решение этой проблемы: использование локов, или транзакционных блокировок. Каждый раз, когда потоку необходимо обновить какое-то общее значение, он ставит на него блокировку. Ни один другой поток не может получить доступ к заблокированному значению пока текущий поток не закончит процедуру — приходится курить и ждать. Поток, заблокировавший значение, может изменить его (в этом случае на сцену выходят товарищи «сложные вычисления» и «подождите я работаю»), после чего снять блокировку. Наконец, другие потоки, находящиеся в состоянии ожидания разблокировки, могут продолжить вычисления после того как значение было обновлено или освобождено. Эта модель работает и на практике, но у нее есть ряд проблем: если обращения к общему значению редки и непостоянны, то модель работает эффективно. В противном случае, когда доступ к общему значению или его обновления происходят регулярно, а не дай Бог — постоянно, потоки проводят много времени в ожидании и не могут производить вычисления, что в итоге ведет к падению производительности всей системы, которая, казалось бы, параллельна донельзя.

    К тому же, блокировки достаточно сложны в обращении. И если с единственным общим значением справится просто, то реальные программы как правило гораздо сложнее. Программа с двумя блокировками, условно: А и Б, может войти в положение которое называют «deadlock» — смертельная блокировка (в дальнейшем: дедлок). Если двум потокам нужны две блокировки, то у них есть следующий выбор: они могут либо поочередно заблокировать А, а потом Б, или наоборот. До тех пор, пока потоки совершают блокировки в одинаковом порядке — проблем не возникнет. Но если один из потоков заблокирует А первым, а второй следом заблокирует Б, они оба могут застрять навсегда — первый поток будет ожидать, пока с Б будет снята блокировка, а второй ожидает того же с А.

    На бумаге кажется, что этого легко избежать — это действительно так, если у программы есть только две блокировки. Но как только функционал начинает усложняться, придется быть крайне внимательным к тому, чтобы каждая часть ПО делала свое дело «как надо». Добавьте еще пару блокировок — и вся схема усложнится в разы, добавьте их 10 — и вы сами попали в дедлок.

    Настоящая транзакционная память — конец блокировок


    В общем и целом — аппаратная транзакционная память, разрабатываемая IBM в настоящее время, призвана решить вышеперечисленные сложности. Разработчик должен всего лишь разметить части ПО, которые производят манипуляции над общими значениями, как «атомарные». Каждый атомарный блок выполняется внутри транзакции либо целиком, либо никак. Внутри атомарного блока программа может считывать общие значения без блокировки, производя необходимые вычисления и записывая результат. В конце блок просто завершает транзакцию. Здесь и находится «хитрая» часть всей этой вычислительной кухни: при совершении операции транзакционная память проверяет были ли изменены общие значения с момента начала атомарной операции. Если да — транзакция отменяется и вся выполненная работа просто откатывается на начальный этап. Для нас это означает простой повтор операции с измененными значениями.

    Транзакционная память, потенциально, способна немало облегчить жизнь программистам, предложив несколько улучшений традиционной схемы блокировок. Во-первых — она «оптимистична»: вместо того, чтобы каждый поток блокировал значения просто потому, что оно может потребоваться конкурентной операции (пессимистичный подход), предполагается, что каждая операция в каждом потоке будет завершена успешно (оптимистичный подход). Если такая ситуация действительно происходит, то единственное, что нужно выполнить потоку — это повтор вычисления. Во-вторых, отсутствует сценарий дедлока, так как блокировки отсутствуют в принципе. В-третьих, модель программирования с использованием аппаратной транзакционной памяти, в широком смысле слова, уже известна большинству разработчиков. Транзакции сами по себе, да и операции отката вычислений, известны большинству программистов, сталкивавшихся с реляционными базами данных. В-четвертых, атомарные блоки, теоретически, упрощают задачу построения больших и сложных программ: атомарный блок с вложенными атомарными блоками все-равно будет выполнять поставленную задачу, что не является истиной в случае программ, построенных на принципах блокировки.

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

    Железные преимущества


    Итак, до сегодняшнего дня исследования в области транзакционной памяти фокусировались на софтовых реализациях технологии. Настоящие (кремниевые) процессоры до сих пор реально не поддерживают ее, лишь эмулируя. Некоторые схемы заставляют работать виртуальные машины в режиме транзакционной памяти (модификации STM для .NET и Java), другие используют нативный код и обучают разработчиков специальным функциям для доступа к общим данным. Зачем же тогда вообще нужна аппаратная реализация? Дело в том, что любая программная реализация транзакционной памяти медленна, подчас — чудовищно медлительна, а ведь это не совсем то, чего ждут от параллельных вычислений.

    BlueGene/Q отличается от других процессоров тем, что несет на борту модуль транзакционной памяти. Это первый подобный коммерческий процессор (хотя был еще Rock от компании Sun — его отменили когда Oracle выкупила первую компанию, там тоже предполагалось внедрение модуля транзакционной памяти). И хотя мы еще не готовы предоставить полную информацию по чипу, некоторые детали все же раскроем.

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

    Также в обиход вводится понятие «спекулятивной операции»: вместо того чтобы ждать последних версий всех значений (на практике для этого может потребоваться окончание работы над числами в одном из ядер), поток будет пытаться выполнить операцию с имеющимися данными, «спекулятивно» выполняя полезную работу и не зная, что произойдет в будущем. Как только работа выполнена система проверяет версии значений, если они были последними (то есть никаких изменений над общими значениями во время выполнения операции не происходило) — результат записывается в память. Это призвано повысить производительность, так как полезные вычисления будут производится до того, как будет получено финальное значение (из области фантастики). Если окажется, что общие значения в потоке устарели, то такая работа будет отменена и переделана с обновленными значениями.

    Логическая эволюция


    В принципе, поддержка транзакционной памяти процессором — это логическое расширение функции, которая давно наличествовала в процессорах PowerPC: «load-link/store-conditional» или LL/SC. Это примитивная операция, которая может быть использована как блок для строительства безопасных многопоточных конструкций. LL/SC включает в себя и известные механизмы, такие как блокировки, и куда более экзотические структуры данных, вроде таблицы, которая может быть изменяема несколькими потоками одновременно без необходимости блокировать значения. STM (софтовая реализация памяти) может быть сделана на базе LL/SC.

    LL/SC состоит из двух частей, где первая это «load-link». Программа использует LL для получения значения из памяти, после чего она может произвести требуемые манипуляции над извлеченным значением. После того как операция закончена и результат необходимо записать обратно в память используется вторая часть — «store-conditional». SC будет выполнена только в том случае, если значение в памяти не было изменено с момента окончания LL. Если значение было изменено, все начинается с начала.

    LL/SC можно найти на многих современных процессорах: PowerPC, MIPS, ARM и Alpha — все четыре используют эту функцию. Архитектура х86 имеет свою альтернативу под названием «compare and swap». Однако большинство LL/SC систем ограничивают ваши возможности — например, они не могут считывать изменения отдельных байтов памяти, но только линии кэша. Это означает, что SC операция вообще может не выполнится, хотя значение на самом деле и не было изменено.

    Тот модуль транзакционной памяти, которые будет встроен в BlueGene/Q представляет собой аппаратную реализацию функции LL/SC после курса стероидов: каждый поток в транзакции может совершать LL-часть операции из нескольких мест одновременно, точно так же как и SC может записывать результат в несколько локаций. Это не лишает поток шанса на ошибку, но снижает вероятность ее появления.

    Дайте две!


    В общем и целом все, что касается реализации аппаратной транзакционной памяти — это непростая история. Рууд Харинг (Ruud Haring), который представлял разработку IBM на последней конференции Hot Chips, сказал что: «потребовалось реализовать много хитроумных ходов» для того чтобы заставить работать такую систему, и что это «результат работы гения». После того как была закончена предварительная работа по составлению схемы чипа, система была построена на базе FPGA (процессоры которые реконфигурируются через ПО) и, как это ни удивительно, все работало нормально. Но насколько сложна эта система, столько в ней и ограничений — как это ни забавно, но пока прототип транзакционной памяти не дает поддержку мультипроцессорных транзакций (все вышеописанное в квадрате). Это не проблема для Sequoia, которая будет обрабатывать специфические задачи, но однозначно станет препятствием на пути популяризации HTM для традиционных многопроцессорных машин: потоки работающие на разных процессорах будут вносить изменения в общие значения, а транзакционная память не сможет это «увидеть».

    Все-таки главная фишка BlueGene/Q и его аппаратной поддержки транзакционной памяти заключается в том, что реализуя эту технологию в IBM смогли добиться минимальных, или нулевых, потерь производительности. Именно это заставляет меня верить в то, что однажды HTM может быть использована в процессорах, которые работают в компьютере каждого из нас и эффективно работать в приложениях, которые мы запускаем каждый день. До тех пор у нас не будет шанса узнать, действительно ли подобное распараллеливание способно улучшить жизнь как разработчиков, так и пользователей.

    Подведу итог. Hardware Transactional Memory — ни в коем случае не панацея и не механизм увеличения производительности процессора. Скорее это инструмент, призванный улучшить жизнь программистам, пишущим программы для параллельных вычислений любой сложности. И первый тест на ее жизнеспособность в кластере Sequoia — это хороший тест, который покажет, насколько реально использование транзакционной памяти в реальной жизни, а не только при прогнозировании атомных или метеорологических взаимосвязей. Если тест будет пройдет, можно не сомневаться, что эта разработка найдет свое место и в коммерческих устройствах самого широкого профиля, благо многоядерные системы уже присутствуют даже в телефонах. Если нет — то меня уже никто не убедит в том, что мультиядерность, недавно считавшаяся «лекарством» от проблем наращивания производительности и естественных ограничений в попытках догнать закон Мура, может получить смертельный удар в спину.

    IBM

    126,00

    Компания

    Поделиться публикацией
    Комментарии 23
      0
      Полезные статьи, как минимум для общего развития, спасибо! Жаль только, что их читает мало людей, сам однажды писал статью о System P — очень мало заинтересованных :(

      Интересно, а какие разработки и научные исследования проходят в России, да и вообще в СНГ? Я долго искал с кем бы поработать в процессе написания диссертации, в конце концов забил и ушел сопровождать сервера оператора мобильной связи))
        0
        К сожалению я не в курсе, какие современные разработки идут в наших университетах и научных институтах — если кто-то владеет подобной информацией, я бы сам с удовольствием узнал подробности.
          +1
          Там все покрыто мраком, адреса электронной почты сотрудников исследовательских центров не активны, сотрудники тоже ничего определенного сказать не могут. Хотя полезно было бы сотрудничать с молодыми учеными, для обоих сторон.
            0
            Однозначно. То же самое я могу сказать и про тему топика — идея STM, равно как и HTM, пришла из западных университетов и уже впоследствии была подхвачена компаниями.
          0
          У нас есть работы над системой RIDE и суперкомпьютер K-100. Есть разработки специализированных процессорных архитектур для обработки сигналов, но там параллельность всегда специфичная.
            0
            Вспомнилось ещё Intel TBB — многие его части делают у нас, в Нижнем Новгороде. У них может быть в университете нечто такое этакое.
              0
              Не знаю как с заинтересованными людьми. Но системы такого уровня в России строятся.
              habrahabr.ru/blogs/hi/135384/

              А раз строят, да еще, как пишут, на своих разработках… специалисты и научная база должны быть в наличии.
              +2
              под напряжением в 55 Ватт как то не логично? не?
                0
                Почему нелогично?
                  +1
                  как с трудо полагаю как напряжение в ватах измерять? в вольтах да, а в ватах потребление-выделение? оазве не так в законах физики у нас?
                    0
                    Возможно это моя ошибка, исправляюсь.
                      0
                      Вообщето «потреблять 55 Ватт» )))

                      55 вольт для передовой цифровой техники — это нонсенс
                  0
                  Так в результате транзакционная память не работает в многопоточном режиме на этом самом BlueGene/Q?
                    0
                    Как это выглядит с точки зрения кодинга?
                      0
                      Не думаю, что в ближайшее время компания IBM раскроет софтверные аспекты работы HTM, но в будущем это однозначно возможно.
                      +6
                      Вопросы возникают такие тут на самом деле.

                      1. А собственно, чем ситуация с бесконечным откладыванием (всегда успевает изменится версия данных) лучше взаимоблокировок? Ну будет livelock. С ними ещё сложнее бороться, чем с deadlock-ами. В последних хоть можно восстановить граф зависимостей, который приводит к останову, а тут?

                      2. Не понятно, что будет, если счётчики версий переполнятся. И хранятся ли они в RAM? Если хранятся, то это же будет дополнительное требование к ПСП, которого и так вечно не хватает. Если не хранятся, то это вообще как? Программист наделал ошибок — забил весь кэш транзакциями, и всё? Работа прекратилась?

                      3. Вообще-то уже достаточно давно показано, что общая память с изменяемыми извне состояниями — это тихий ужас для программирования. Тут дело совсем не в возможных блокировках или ошибках при синхронизации, дело в том, что очень сложно в таком случае формулировать инварианты алгоритма. Логическое время в программе мало того, что начинает течь нелинейно, оно вообще пропадает, невозможно сформулировать концепцию события. TM не помогает с этим никак совладать: появляется, конечно, событие: транзакция выполнена, но как его связать с общей системой событий в приложении? Не понятно, за счёт чего здесь облегчение будет достигнуто в программировании.

                      4. Sun же уже давно пыталась это сделать… Не выстрелило. И дело совсем не в том, что программная реализация неэффективна, а в том что сама абстракция неудобная для программирования. Вот если бы futures-ы получили аппаратную поддержку…
                        0
                        Попытаюсь ответить на ваши вопросы в ближайшее время после консультации с сотрудниками IBM.
                          +1
                          > 1. А собственно, чем ситуация с бесконечным откладыванием (всегда успевает изменится версия данных) лучше взаимоблокировок? Ну будет livelock. С ними ещё сложнее бороться, чем с deadlock-ами. В последних хоть можно восстановить граф зависимостей, который приводит к останову, а тут?

                          Можно делать несколько попыток и после n-ой неудачной, пойти по классической схеме и залочить необходимые ячейки. Но тогда уже нет гарантии от deadlock-а :).

                          > 3. Вообще-то уже достаточно давно показано, что общая память с изменяемыми извне состояниями — это тихий ужас для программирования. Не понятно, за счёт чего здесь облегчение будет достигнуто в программировании.

                          STM/HTM эмулирует нешаримую память. В идеале все выглядит так, будто бы ты единолично работаешь с памятью. Вариант share-nothing хорош, но у него есть свои недостатки — постоянные накладные расходы на копирование.

                          > 4. Sun же уже давно пыталась это сделать… Не выстрелило. И дело совсем не в том, что программная реализация неэффективна, а в том что сама абстракция неудобная для программирования. Вот если бы futures-ы получили аппаратную поддержку…

                          Почему неудобная? В Haskell и Clojure вроде как отлично работает. Даже Джо Армстронг(автор Erlang) сказал что из всех вариантов(кроме message-passing), STM самый многообещающий.

                          А у futures-ов есть свои проблемы с глобальным состоянием: calculist.org/blog/2011/12/14/why-coroutines-wont-work-on-the-web/
                            +1
                            Эмс. Сопрограммы и фьючерсы — это всё же разные вещи.

                            Можно делать несколько попыток и после n-ой неудачной, пойти по классической схеме и залочить необходимые ячейки. Но тогда уже нет гарантии от deadlock-а :).

                            А есть оценка вероятностей (с этим всегда плохо) с которой мы будем попадать на локи? Тут, ведь, как… Если вероятности маленькие, значит, взаимодействие не особо интенсивное, значит, какая выгода от TM? Вроде, это всё можно посчитать, но я не встречал почему-то количественных оценок, только качественные.

                            STM/HTM эмулирует нешаримую память. В идеале все выглядит так, будто бы ты единолично работаешь с памятью. Вариант share-nothing хорош, но у него есть свои недостатки — постоянные накладные расходы на копирование.

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

                            Кроме share-nothing есть ещё множество промежуточных вариантов: потоковые парадигмы, агенты, process calculus.

                            Почему неудобная? В Haskell и Clojure вроде как отлично работает. Даже Джо Армстронг(автор Erlang) сказал что из всех вариантов(кроме message-passing), STM самый многообещающий.

                            «Отлично» в каком смысле? Про Haskell я не знаю, наверное, там есть какая-нибудь библиотека (они вообще всё без разбора в библиотеки тянут), но насчёт качества её работы у меня сомнения, как и вообще по поводу всего, сделанного на Haskell.

                            В Clojure же, насколько я могу судить, то, что называется транзакционной памятью — это совсем не то, что обычно понимается под STM. Их вариант с синхронными ссылками более такой, эмс… ну, для него более на уровне интуиции ясно, почему он может быть удобнее и эффективнее критических секций обновляющих общую память.

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

                            Поэтому толку от того, что для каждой нити в критической секции обеспечивается консистентное состояние «мира» почти никакого нет, потому что главная-то сложность не в получении этого состояния (давно уже известно, как надо правильно локи лочить, чтобы взаимоблокировок не было, и давно известно как эти локи лочить эффективно), а в согласованном переходе между ними. И в возможности изменять независимо части этого мира, а потом собирать его в единое целое. Облегчает ли TM эти задачи? Лично мне кажется — совсем нет. Не даёт она механизма для организации потока событий.

                            В этом плане сообщения Erlang (которые, кстати, совсем не share-nothing: данные в них неизменяемые, и их можно не копировать) гораздо удобнее, потому что для них поток событий вполне себе формально определяем, виден из программы, его можно контроллировать и им можно пользоваться (часты Лампорта и всё такое прочее). Про futures-ы (promises, в терминологии Haskell) можно сказать то же самое.

                            IMHO, есть в TM какой-то элемент PR-а и рыночной технологии. Все знают про базы данных и про транзакционную модель, и на это можно опираться в маркетинговой компании: у Вас ещё нет процессора с поддержкой TM? — Тогда мы идём к Вам!
                          0
                          А есть ли какие-нибудь бенчмарки, показывающие, насколько аппаратная реализация превосходит софтварную в производительности?
                            0
                            Вы не первый, кто этим интересуется — к сожалению мне такие данные не были предоставлены, возможно в 2012 бенчмарки появятся в открытом доступе, для того чтобы визуально оценить разницу в скорости работы.
                            0
                            К такой транзакционной памяти применим термин уровень изоляции транзакций, если да, то какой он или каковы его свойства?
                              0
                              >Ни один другой поток не может получить доступ к заблокированному значению пока текущий >поток не закончит процедуру — приходится курить и ждать.

                              Так есть модели локов, когда можно читать заблокированное значение, например в Java для этого даже отдельные типы данных сделали.

                              А если нужно постоянно их изменять, то транзакции здесь также не помогут, будут только зря процессор грузить и отменять транзакции…

                              В общем, не впечатляет. Актеры в Scala или на Java (Akka) меня больше впечатлили…

                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                              Самое читаемое