Аппаратная поддержка транзакционной памяти

Усилия программистов, необходимые для использования параллелизма, оправдываются, если новый код выполняется лучше или обеспечивает более быструю реактивность, чем последовательный код. Хотя современные системы STM масштабируются при возрастании числа процессоров на многоядерном кристалле, накладные расходы программных систем являются существенными. Даже при использовании оптимизирующих компиляторов STM-поток может выполняться в 2-7 раз медленнее последовательного кода [22, 26].

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

Аппаратное ускорение STM. Основным источником накладных расходов STM является поддержка и проверка наборов прочитанных объектов. Для поддержки такого набора в системе STM обычно вызывается специальная подпрограмма при каждом чтении из совместно используемой памяти. Эта подпрограмма регистрирует адрес соответствующего объекта и, возможно, выполняет раннее обнаружение конфликта путем проверки версии объекта или наличия блокировки. Для валидации транзакции система STM должна проверить весь набор прочитанных объектов и убедиться в том, что ни для одного из них нет конфликта. Выполнение этих инструментальных действий может стать большим накладным расходом, если транзакция после каждого обращения к памяти не производит большой объем вычислений.

Система STM с аппаратным ускорением (hardware-accelerated STM, HASTM), предложенная Саха (Saha) и др. [26], была первой системой, где для снижения накладных расходов инструментария STM использовалась аппаратная поддержка. Вспомогательная аппаратура позволяет программному обеспечению построить быстрые фильтры, которые могут ускорить действия, требуемые для поддержки наборов прочитанных объектов. HASTM обеспечивает для STM две возможности на основе поддержки битов пометки потоков управления на уровне блоков кэша. Во-первых, программное обеспечение может проверить, не был бы ранее установлен бит пометки для данного блока памяти, и не производилась ли запись в этот блок в другом потоке после того, как он был помечен (выявление конфликта). Во-вторых, программное обеспечение может узнать, производилась ли запись в других потоках управления в какой-нибудь из блоков памяти, помеченных данным потоком (валидация).

В HASTM предлагалось реализовывать биты пометки за счет использования дополнительных метаданных для каждого блока процессорных кэшей многоядерного кристалла. Аппаратура отслеживает, не стал ли недействительным какой-либо помеченный блок кэша по причине выталкивания из кэша или записи, произведенной в него из другого потока управления. STM использует биты пометки следующим образом. При вызове подпрограммы чтения проверяется и устанавливается бит пометки для блока памяти, содержащего заголовок соответствующего объекта. Если бит пометки уже установлен, т.е. данная транзакция ранее уже обращалась к объекту, то этот объект не добавляется к набору прочитанных объектов. Для валидации транзакции STM выясняет с помощью аппаратуры, стал ли недействительным какой-либо помеченный блок кэша. Если это не произошло, то значит все объекты, к которым производился доступ через инструментарий STM, являлись частными для данного потока управления в течение всего выполнения транзакции, и никакая дальнейшая валидация не требуется. Если некоторые помеченные блоки стали недействительными, система STM должна производить программную валидацию, проверяя номера версий или наличие блокировок для всех объектов из набора прочитанных объектов. На этом дорогостоящем шаге валидации определяется, был ли помеченный блок вытолкнут из кэша из-за его ограниченной емкости или из-за наличия реального конфликта между одновременно выполняемыми транзакциями.

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

Ускорить выявление конфликтов в STM можно и без модификации аппаратных кэшей. Кэши первого уровня обычно располагаются в критическом контуре процессора и взаимодействуют со сложными подсистемами, такими как подсистема поддержки протокола согласованности кэшей. Даже незначительные изменения в аппаратуре кэша могут повлиять на тактовую частоту процессора и повысить сложность его разработки и верификации. Као Минь (Cao Minh) и др. [22] предложили подход к ускорению систем STM на основе сигнатур (SigTM). При этом подходе для пессимистического кодирования множеств прочитанных и измененных объектов программных транзакций используются аппаратные сигнатуры. Сигнатуры вычисляются вне кэшей с применением аппаратного фильтра Блюма. (Фильтр Блюма (Bloom filter) позволяет эффективно представлять надмножество элементов множества и быстро устанавливать, входит ли в это множество заданный элемент. Использование фильтров Блюма для обнаружения зависимостей при управлении выполнением нитей и транзакций было впервые предложено Сезом (Ceze) и др. [6].) Программный инструментарий обеспечивает фильтрам адреса объектов, читаемых или изменяемых внутри транзакции. Для распознавания конфликтов аппаратура компьютера отслеживает трафик протокола поддержки согласованности кэшей, обнаруживая в нем запросы монопольного доступа к блокам кэша, что означает изменение памяти. Анализируя сигнатуры транзакции, аппаратура проверяет, не может ли относиться адрес, содержащийся в запросе, к наборам прочитанных или измененных объектов этой транзакции. Если да, то считается, что обнаружен потенциальный конфликт, и система STM может либо аварийно завершить транзакцию, либо прибегнуть к программной валидации.

И HASTM, и SigTM ускоряют поддержку наборов прочитанных объектов и валидацию в системах STM. Тем не менее, между этими подходами имеются архитектурные различия. SigTM кодирует наборы прочитанных и измененных объектов, размеры которых превышают размеры частных кэшей. Ограниченная емкость кэша и промахи при обнаружении конфликтов не приводят к потребности программной валидации, как при использовании HASTM. С другой стороны, в SigTM используются вероятностные сигнатуры, в результате чего истинные конфликты никогда не упускаются, но из-за наложения адресов в фильтрах Блюма могут выявляться ложные конфликты. Кроме того, аппаратные сигнатуры относительно компактны, и их легко обрабатывать, так что их можно сохранять и восстанавливать при переключении контекста и обработке прерываний. В HASTM биты пометки могут быть утрачены, если процессор используется для выполнения другой задачи. С другой стороны, в сигнатурах SigTM отражаются физические адреса, и содержимое сигнатуры становится недействительным при изменении отображения виртуальных страниц.

Показано, что аппаратное ускорение управления наборами прочитанных объектов в два раза повышает производительность систем STM, основанных на блокировках, с непосредственным обновлением и отложенными изменениями [22, 26]. Возможны дополнительные усовершенствования с использованием аппаратных механизмов, которые поддерживают управление версиями объектов, изменяемых STM [31]. Однако, поскольку в большинстве программ читается гораздо больше объектов, чем изменяется, получаемое повышение производительности является незначительным.

Аппаратная транзакционная память. Интерес к полностью аппаратной реализации TM (HTM) появился после публикации двух первых статей про TM: статей Найта (Knight) [16] и Херлихи и Мосса [13]. В системах HTM не требуется программный инструментарий для обработки адресов памяти внутри кода транзакции. Аппаратура управляет версиями данных и отслеживает конфликты прозрачным образом при выполнении программами обычных операций чтения и записи. Устранение инструментария позволяет сократить накладные расходы прикладной программы и снимает потребность в специализированных телах функций, так что их можно вызывать и внутри, и вне транзакции.

В системах HTM для реализации управления версиями и выявления конфликтов используются иерархия кэшей и протокол согласования кэшей. Через кэши проходят все операции чтения и записи, задаваемые процессором, в них может буферизоваться значительный объем данных, и их ассоциативная организация позволяет производить эффективный поиск. Во всех HTM модифицируются кэши первого уровня, но этот подход может быть распространен на кэши более высокого уровня, как частные, так и совместно используемые. Для иллюстрации организации и функционирования систем HTM ниже сравнительно подробно описывается архитектура TCC, и кратко упоминаются ключевые особенности альтернативных разработок.

TCC (Transactional Coherence and Consistency) – это система HTM с откладываемыми изменениями, в которой выявление конфликтов производится на стадии фиксации транзакций [21]. Для отслеживания наборов прочитанных и измененных объектов каждый блок кэша помечается служебными битами R и W, которые устанавливаются при первом доступе к блоку внутри транзакции по чтению или записи соответственно. Блоки кэша, входящие в набор измененных объектов, действуют как буфера записи и не выталкиваются в память до фиксации транзакции.

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

Выявление конфликтов происходит, когда другие процессоры получают сообщения о согласовании кэшей от фиксируемой транзакции. Аппаратура проверяет, не содержится ли блок с указанным адресом в локальных кэшах. Если этот блок содержится в кэше, и для него установлены биты R или W, то это значит, что между фиксируемой и локальной транзакциями имеется конфликт «read-write» или «write-write» соответственно. Аппаратура генерирует сигнал программному обработчику, который аварийно завершает локальную транзакцию и потенциально повторяет ее с некоторой задержкой.

Аналогичные аппаратные методы могут применяться для поддержки систем HTM с непосредственным обновлением памяти и ранним обнаружением конфликтов [23]. Для систем с непосредственным обновлением аппаратура прозрачным образом журнализует исходное значение блока памяти до его первой модификации транзакцией. Если транзакция завершается аварийно, этот журнал используется для обратного выполнения операций обновления. Для раннего обнаружения конфликтов аппаратура получает монопольный доступ к блоку кэша при первой записи и удерживает этот режим доступа до фиксации транзакции. При наличии небольшого числа конфликтов почти все системы HTM ведут себя схожим образом. Если конфликтов много, то подход с откладываемыми изменениями и обнаружением конфликтов приводит к меньшему числу патологических сценариев, с которыми можно легко справиться с применением политики задержек [3].

Потери производительности HTM-нити обычно составляет от 2-х до 10-ти процентов по сравнению с производительностью не транзакционного кода. Система HTM может превосходить по производительности систему STM, основанную на блокировках, в четыре раза, а систему STM с аппаратным ускорением – в два раза [22]. Тем не менее, системам HTM свойственно несколько проблем, которые отсутствуют в реализациях STM. Кэши, используемые для поддержки наборов прочитанных и измененных объектов, а также версий данных, обладают конечной емкостью и при выполнении длинной транзакции могут переполниться. Состояние транзакции, сохраняемое в кэше, имеет большой объем, и его трудно сохранять и восстанавливать при обработке прерываний, переключении контекста и подкачке. Длинные транзакции могут быть редкими, но их все равно необходимо выполнять с сохранением свойств атомарности и изолированности. С точки зрения программистов недопустимо устанавливать зависящие от реализации ограничения на размеры транзакций.

Простой механизм обработки переполнения кэша или системных событий заключается в том, чтобы в любом случае обеспечить возможность выполнения транзакции до конца [21]. При возникновении одного из упомянутых выше событий система HTM может начать обновлять память напрямую, без поддержки наборов прочитанных и измененных объектов и старых версий данных. Однако в это время не могут выполняться другие транзакции, поскольку более невозможно выявление конфликтов. Кроме того, непосредственные обновления памяти без журнализации препятствуют использованию в транзакции явных операторов аварийного завершения или повторного выполнения.

Райвар (Rajwar) и др. предложили альтернативный подход VTM (Virtualized TM), который позволяет поддерживать атомарность и изолированность даже в тех случаях, когда транзакция прерывается событиями переполнения кэша или прерываниями [25]. VTM отображает ключевые структуры данных, описывающие выполнение транзакции (наборы прочитанных и измененных данных, буфера записи или журнал откатов), в виртуальную память, которая является практически неограниченной, и на которую не влияют системные прерывания. В аппаратных кэшах сохраняется рабочий набор этих структур данных. Разработчики VTM также предлагали использовать аппаратные сигнатуры для устранения избыточного поиска в структурах в виртуальной памяти.

Наконец, для решения проблемы ограниченности аппаратных ресурсов можно использовать гибридную систему HTM–STM [7, 17]. Выполнение транзакции начинается в режиме HTM с использованием аппаратных механизмов выявления конфликтов и поддержки версий данных. Если ресурсы HTM исчерпываются, то транзакция откатывается и запускается заново в режиме STM с применением дополнительного инструментария. Для использования этого подхода требуется наличие двух вариантов каждой функции, но обеспечивается хорошая производительность для коротких транзакций. Проблемой гибридных систем является выявление конфликтов между одновременно выполняемыми HTM- и STM-транзакциями.

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

Безотносительно к объему аппаратуры, используемой для поддержки TM, важно то, что системы HTM обеспечивают функциональные возможности, полезные при разработке практических программных моделей и сред выполнения. Значительная часть исследований в области HTM посвящена аппаратно-программному интерфейсу, который может поддерживать развитые программные средства. Макдональд (McDonald) и др. предложили четыре интерфейсных механизма для систем HTM [20]. Первый механизм – это двухфазный протокол фиксации, который на архитектурном уровне разделяет вилидацию транзакции и фиксацию выполненных ею изменений в памяти. Второй механизм представляет собой транзакционные обработчики, позволяющие программному обеспечению реагировать на существенные события, такие как обнаружение конфликта, фиксация или аварийное завершение. Шрираман (Shriraman) и другие предлагают аналогичный механизм «alert-on-update», который вызывает программный обработчик, когда аппаратура HTM обнаруживает конфликт, или в ней возникает переполнение [31]. Третий механизм заключается в поддержке замкнутых и открыто-вложенных транзакций. Открытая вкладываемость позволяет программному обеспечение прерывать выполняемую транзакцию и исполнять некоторый служебный код (например, системный вызов) с независимыми гарантиями атомарности и изолированности. Другие исследователи полагают, что для обслуживания системных вызовов и операций ввода-вывода достаточно приостанавливать HTM-транзакции [24, 32]. Тем не менее, если в служебном коде для доступа к совместно используемым данным используются транзакции, требования задержки выполнения транзакции не существенно отличаются от требований открыто-вложенных транзакций. Наконец, и Макдональд, и Шрираман предлагают несколько типов инструкций чтения и записи, позволяющих компиляторам отличать доступ к частным данным потока управления, неизменяемым и идемпотентным данным от доступа к истинно разделяемым данным. При наличии таких механизмов системы HTM могут поддерживать широкий диапазон программных средств, от средств традиционной синхронизации и ограниченного ввода-вывода внутри транзакций [5,32] до высокоуровневых моделей параллелизма, позволяющих избегать аварийного завершения транзакций при конфликтах по памяти, если не нарушается семантика уровня приложений [4].