Pull to refresh
89.54
Rating

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

IBM corporate blog

На фото: 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 — это хороший тест, который покажет, насколько реально использование транзакционной памяти в реальной жизни, а не только при прогнозировании атомных или метеорологических взаимосвязей. Если тест будет пройдет, можно не сомневаться, что эта разработка найдет свое место и в коммерческих устройствах самого широкого профиля, благо многоядерные системы уже присутствуют даже в телефонах. Если нет — то меня уже никто не убедит в том, что мультиядерность, недавно считавшаяся «лекарством» от проблем наращивания производительности и естественных ограничений в попытках догнать закон Мура, может получить смертельный удар в спину.
Tags: IBMSTMHTMBlueGeneQтранзакционная памятьсуперкомпьютерыпараллельные вычисления
Hubs: IBM corporate blog
Total votes 35: ↑34 and ↓1 +33
Comments 23
Comments Comments 23

Top of the last 24 hours

Information

Founded
Website
www.ibm.com
Employees
1,001–5,000 employees
Registered