Библиотека сайта rus-linux.net
Что каждый программист должен знать о памяти. Часть 8. Технологии будущего
Оригинал: Memory part 8: Future technologiesАвтор: Ulrich Drepper
Дата публикации: ноябрь 2007 г.
Перевод: М.Ульянов
Дата перевода: май 2010 г.
8. Грядущие технологии: что нас ждет?
8.2. Транзакционная память
Херлих и Мосс в своем новаторском исследовании 1993 года [transactmem] предложили применить аппаратный транзакционный подход к организации операций с памятью, поскольку исключительно средствами ПО эффективно решить проблему не удавалось. В то время в Digital Equipment Corporation уже столкнулись с проблемами масштабируемости на топовом многопроцессорном оборудовании (имеющем пару десятков процессоров). Принцип тот же, что и с транзакциями в базах данных: либо результат транзакции виден сразу и полностью, либо она отменяется и все значения остаются неизменными.
Вот это и предложили применить к памяти, и именно этого в предыдущем разделе мы пытались добиться, разрабатывая алгоритмы с применением атомарных операций. Транзакционная память рассматривается как замена (или расширение) атомарных операций в различных ситуациях, и особенно в случае безблокировочных структур данных. Интеграция системы транзакций в процессор может показаться ужасно сложной затеей, но на самом деле в большинстве процессоров уже реализовано нечто подобное.
Например, в некоторых ЦП реализация операций LL/SC представляет собой ничто иное, как транзакцию. Инструкция SC отменяет или подтверждает транзакцию на основе того, были обращения к области памяти или нет. Транзакционная память расширяет эту концепцию. А именно, подразумевается, что в транзакции теперь принимают участие не две простые инструкции, а множество их. Чтобы разобраться в том, как оно работает, давайте сначала посмотрим, каким образом можно реализовать пару LL/SC. {Но это не означает, что на деле инструкции реализуются именно так.}
8.2.1. Реализация Load Lock/Store Conditional
При выполнении инструкции LL значение, хранящееся в области памяти, загружается в регистр. В процессе данное значение загружается и в кэш данных первого уровня (L1d). В дальнейшем инструкция SC завершится успешно только в случае, если значение останется нетронутым. Как процессор может это проконтролировать? Ответ приходит сам собой, если вернуться к описанию протокола MESI, рисунок 3.18. Когда другой процессор меняет значение в памяти, копия в кэше L1d первого процессора должна быть помечена как недействительная. При выполнении инструкции SC на первом процессоре ей придется загружать значение в L1d заново. А это процессор уже должен отследить.
Есть и другие моменты, которые следует уладить, которые касаются контекстных переключений (возможная модификация данных на том же процессоре) и случайных перезагрузок строки кэша после записи на другом процессоре. Но это всё решаемо - политикой (очистка кэша при контекстном переключении) и дополнительными флагами, либо отдельными строками кэша для инструкций LL/SC. В целом, реализация LL/SC обеспечивается фактически по умолчанию при использовании протокола согласования кэша вроде MESI.
8.2.2. Операции с транзакционной памятью
Чтобы транзакционная память была действительно полезной, транзакции не должны завершаться с первой же инструкцией сохранения. Вместо этого должна быть реализована возможность выполнения нужного числа операций загрузки и сохранения. Следовательно, необходимы отдельные инструкции завершения (подтверждения) и отмены. Вскоре увидим, что нужна еще одна, третья инструкция, позволяющая запрашивать текущее состояние транзакции и проверять, была она отменена или нет.
Всего должны быть реализованы три операции с памятью:
- Чтение из памяти
- Чтение с последующей записью
- Запись в память
Для чего нужен второй, особый тип операции чтения, можно понять, взглянув внимательнее на протокол MESI. Для "нормального" чтения подходят строки кэша, находящиеся в состояниях `E' и `S'. А операция чтения второго типа может быть выполнена только над строкой, имеющей статус `E'. В каких именно случаях нужно применять второй тип, будет вскользь упомянуто ниже. А для детального изучения вопроса заинтересованный читатель может обратиться к литературе о транзакционной памяти, для начала можно порекомендовать [transactmem].
Также, помимо только что указанных трех операций, нам нужна возможность управления транзакциями, которое в основном состоит из операций завершения и отмены (commit и abort соответственно) - они нам уже знакомы по работе с транзакциями в базах данных. Хотя есть и еще одна операция, в теории необязательная, но на практике, для написания серьезных программ с применением транзакционной памяти - попросту необходимая. Имеется в виду инструкция, позволяющая потоку проверить, выполняется ли еще транзакция и может ли она быть успешно завершена в дальнейшем, либо она уже потерпела неудачу и в любом случае будет отменена.
Далее обсудим, как на деле эти операции взаимодействуют с кэшами ЦПУ и шиной. Но сначала давайте взглянем на примеры кода, использующего транзакционную память. Это должно облегчить понимание раздела в дальнейшем.
8.2.3. Пример кода, использующего транзакционную память
Для примера вернемся к уже известному нам коду и продемонстрируем реализацию стека LIFO с применением транзакционной памяти.
struct elem { data_t d; struct elem *c; }; struct elem *top; void push(struct elem *n) { while (1) { n->c = LTX(top); ST(&top, n); if (COMMIT()) return; ... delay ... } } struct elem *pop(void) { while (1) { struct elem *res = LTX(top); if (VALIDATE()) { if (res != NULL) ST(&top, res->c); if (COMMIT()) return res; } ... delay ... } }Рисунок 8.4: Стек LIFO, организованный с применением транзакционной памяти
Данный листинг напоминает самый первый, вообще не ориентированный на многопоточность, - и это дополнительный плюс: писать код, использующий транзакционную память, проще. Чем он отличается от того, первого, так это операциями LTX, ST, COMMIT и VALIDATE. С помощью них организуется доступ к транзакционной памяти. На деле есть еще одна операция, LT, которую в данном случае мы не использовали. LT представляет собой неисключающее (non-exclusive) чтение, LTX - исключающее (exclusive) чтение, а ST - запись в транзакционную память. Операция VALIDATE проверяет, выполняется ли еще транзакция и может ли она быть завершена успешно. Возвращается true, если с транзакцией все в порядке. Если же транзакция уже помечена как отмененная, то она окончательно отменяется и следующая инструкция начинает новую транзакцию. Специально для этого в коде имеется новый блок if, на случай, если транзакция все еще выполняется.
Операция COMMIT завершает транзакцию; если завершение проходит успешно, возвращается true. Это значит, что данная часть программы завершена и поток может двигаться дальше. Если вернулось false, значит, вся кодовая последовательность должна быть выполнена заново. Для этого введен внешний цикл while. Хотя стоит отметить, это не всегда так уж необходимо - иногда лучшим выбором будет просто продолжить работу.
Особенность операций LT, LTX и ST в том, что они могут окончиться неудачей, и никак об этой неудаче не сообщить. Проверить это программа может только через VALIDATE или COMMIT. То есть в случае операции загрузки (чтения) может оказаться, что загруженное в регистр значение - ошибочно, недействительно; и вот поэтому в вышеприведенном примере необходимо использовать VALIDATE, прежде чем разыменовывать указатель. В следующем разделе увидим, почему следует использовать именно такую реализацию. Хотя возможно, что с широким распространением транзакционной памяти в процессорах будет реализовано нечто иное. Но тем не менее, авторы [transactmem] пришли именно к тому, что мы сейчас описываем.
Функцию push можно описать так: транзакция начинается с чтения указателя на вершину стека. Чтение запрашивает исключительное владение, ибо далее в эту переменную будет производиться запись. Если ранее другой поток уже начал транзакцию, чтение завершится неудачей и транзакция - всё еще выполняющаяся - будет помечена как отмененная; загруженное при этом значение может являться просто мусором. Это значение, независимо от статуса, сохраняется в поле next нового элемента списка. Всё нормально, ведь данный элемент пока нигде не используется, и доступ к нему имеет только один поток. Затем указатель на вершину стека заменяется указателем на новый элемент. Если транзакция еще не была помечена как отмененная, то данная замена указателя пройдет успешно. Так всё происходит в общем случае. Неудача может произойти, только если поток использует для доступа к указателю код, отличающийся от представленного в функциях push и pop. Если на момент вызова ST транзакция уже отменена, то не выполнится вообще ничего. Ну и в конце концов, поток пытается завершить транзакцию. Если завершение проходит успешно, всё готово - и другие потоки могут начинать свои транзакции. Если транзакция была отменена на каком-либо из этапов, ее необходимо выполнить с самого начала. Но перед этим лучше всего вставить некоторую задержку (delay). Если упустить данный момент, поток может войти в непрерывно повторяющийся цикл, тратя ресурсы и перегревая процессор.
Функция pop чуть более сложная. Она начинается так же - чтением вершины стека с запросом на исключительное владение. Затем немедленно происходит проверка, успешно ли выполнилась операция LTX. Если нет - далее ничего не происходит, кроме задержки перед следующей итерацией. Если указатель top считался успешно, значит, он находится в нужном нам состоянии и мы можем разыменовать указатель. Вспомните, именно здесь была проблема с использованием атомарных операций; а с применением транзакционной памяти всё проходит гладко. Последующая операция, ST, выполняется только если стек не пуст, так же как и в первоначальном коде, не поддерживающем многопоточность. И наконец, транзакция завершается. Если завершение успешно, функция возвращает старый указатель на вершину, иначе ставим задержку и пытаемся заново. Важный нюанс: следует помнить, что операция VALIDATE отменяет транзакцию, если та помечена соответствующим образом. Следующая операция транзакционной памяти начнет новую транзакцию, следовательно, мы должны пропустить весь оставшийся код в функции.
Как именно работают задержки, увидим, когда транзакционная память будет реализована аппаратно. Если реализация окажется неудачной, то производительность системы серьезно пострадает.
8.2.4. Протокол шины для транзакционной памяти
Рассмотрев основные принципы работы с транзакционной памятью, теперь можем углубиться в подробности ее реализации. Обратите внимание, что реализация основана не на используемом оборудовании. Вместо этого, она отталкивается от первоначального описания принципов транзакционной памяти и знаний о протоколах согласования кэша. Кое-какие подробности опущены, но это не должно помешать разобраться в рабочих характеристиках.
На деле транзакционная память не является какой-то отдельной памятью - это было бы глупо и бессмысленно, ведь нам необходима возможность проведения транзакций в любом месте адресного пространства потока. Вместо этого, она реализуется на первом уровне кэша. В теории, можно было б ее разместить прямо в обычном кэше L1d, но в [transactmem] показано, что это не самая лучшая идея. Скорее, мы увидим кэш транзакций, параллельный кэшу данных первого уровня. Все запросы доступа будут использовать кэши верхних уровней точно так же, как они используют L1d. По идее, кэш транзакций должен быть гораздо меньше кэша данных первого уровня. Если он будет полностью ассоциативен, то размер такого кэша должен определяться количеством операций, которое может содержать транзакция. Различные реализации, скорее всего, будут ограничены архитектурой и/или конкретной версией процессора. Легко представить кэш транзакций, состоящий из 16 элементов, а то и меньше. Выше, в примере, нам нужна была только одна единственная область памяти; алгоритмы с транзакционными рабочими множествами большего размера будут ну очень сложными. Вполне возможно появление процессоров, поддерживающих несколько активных транзакций одновременно. В таком случае число элементов кэша увеличивается, но остается достаточно небольшим для того, чтобы сохранить полную ассоциативность.
Кэши транзакций и L1d - эксклюзивны, то есть раздельны. Это значит, что строка кэша может содержаться в одном из кэшей, но никогда - в обоих сразу. Каждый слот в кэше транзакций в любой момент времени находится в одном из четырех состояний, поддерживаемых протоколом MESI. Дополнительно, каждый слот (строка) хранит некоторое состояние транзакции. Данные состояния перечислены ниже (названия приведены в соответствии с [transactmem]):
EMPTY
слот не содержит никаких данных. Статус MESI всегда 'I'.
NORMAL
слот содержит подтвержденные данные. Они также могут находиться и в кэше L1d. Статусы MESI могут быть 'M', 'E' и 'S'. Поддержка состояния 'M' означает, что при подтверждении (завершении) транзакции данные не обязаны записываться в основную память (ну если только данная область не объявлена как некэшируемая или со сквозной записью). Это может значительно повысить производительность.
XABORT
слот содержит данные, отбрасываемые при отмене. Явная противоположность XCOMMIT. Все данные, созданные во время транзакции, содержатся в кэше транзакций, ничего не записывается в основную память до завершения транзакции. Это ограничивает максимальный размер транзакции, но зато при этом означает, что никакая другая память, кроме кэша транзакций, не должна следить за состояниями XCOMMIT/XABORT конкретной области. Возможные статусы MESI: 'M', 'E' и 'S'.
XCOMMIT
слот содержит данные, отбрасываемые при подтверждении. Полезная оптимизация для реализации в процессорах. Если в процессе выполнения транзакции значение, хранящееся в области памяти, изменяется, то старое значение нельзя сразу отбрасывать - если транзакция будет отменена, его нужно будет восстановить. Статусы MESI те же, что и для XABORT. Заметное отличие от XABORT состоит в том, что если кэш транзакций заполняется, все XCOMMIT-элементы (во всех состояниях) сбрасываются, при этом элементы, находящиеся в состоянии 'M', должны быть сначала записаны обратно в основную память.
При вызове операции LT, процессор сначала выделяет две строки кэша. При этом в первую очередь ищутся NORMAL-слоты по адресу операции, т.е. кэш-попадания. Если такой элемент найден, то ищется второй и значение копируется. Один элемент помечается как XABORT, второй как XCOMMIT.
В случае когда кэш-попадания отсутствуют, т.е. данного адреса в кэше нет, ищутся слоты с пометкой EMPTY. Если таковых не обнаружено, то ищутся слоты NORMAL. Старое содержимое затем сбрасывается в память, если слот находится в состоянии 'M'. Ну а если не выходит найти даже NORMAL-слотов, то придется пожертвовать элементами XCOMMIT. Хотя, всё это - нюансы конкретной реализации. Максимальный размер транзакции определяется размером кэша транзакций, и поскольку количество слотов, необходимое для каждой операции в транзакции, фиксировано, количество транзакций можно ограничить таким образом, чтоб не приходилось сбрасывать XCOMMIT-элементы.
Если адрес не найден в кэше транзакций, на шину передается запрос T_READ. Использование именно его указывает системе, что это запрос для кэша транзакций. В остальном он практически не отличается от обычного запроса шины READ. Как и в случае с обычным READ-запросом, сначала опрашиваются кэши других процессоров. Если в них ничего не обнаружено, искомое значение считывается из основной памяти.
Протоколом MESI определяется состояние новой строки - 'E' либо 'S'. Разница между T_READ и READ проявляется, если строка кэша в момент запроса используется активной транзакцией другого процессора или ядра. В таком случае операция T_READ завершается неудачей, никаких данных не передается. Транзакция, отправившая запрос, помечается как отмененная, а значение, в ней используемое (обычно полученное простым чтением регистра), освобождается. Вернувшись к нашему примеру, видим, что такое поведение не создает проблем, если правильно применять операции с транзакционной памятью. А именно, прежде чем использовать загруженное значение, его необходимо верифицировать с помощью VALIDATE. В большинстве случаев это ничего не стоит и лишним не будет. При попытке реализовать структуру FIFO с помощью атомарных операций мы увидели, что именно такой проверки и не хватает, чтобы наш безблокировочный код заработал как надо.
Операция LTX почти не отличается от LT. Но именно что "почти". Отличие в том, что для взаимодействия с шиной применяется операция T_RFO, а не T_READ. T_RFO, как и стандартный запрос шины RFO, содержит требование исключительного владения строкой кэша. В результате строка кэша будет находиться в состоянии 'E'. Как и T_READ, запрос T_RFO может завершиться неудачей, и при этом значение так же отбрасывается. Если строка кэша уже находится в локальном кэше транзакций со статусом 'M' или 'E', ничего делать не требуется. Если же строка в локальном кэше имеет статус 'S', то необходим запрос шины для аннулирования всех остальных копий.
Операция ST подобна LTX. Сначала значение переводится в исключительное владение локального кэша транзакций. Затем операция ST копирует значение во вторую строку (слот) кэша и помечает элемент как XCOMMIT. Другой слот помечается как XABORT и туда записывается новое значение. Если транзакция уже была отменена ранее, либо отменяется при неудаче последних действий (являющихся аналогом LTX), записи не происходит.
Ни VALIDATE, ни COMMIT не могут автоматически скрытно обратиться к шине для записи в основную память. И это огромный плюс по сравнению с атомарными операциями. В случае атомарных операций параллельность обеспечивается благодаря записи измененных значений обратно в основную память. И если вы дочитали до этого места, то уже должны понимать, насколько это дорого. С применением же транзакционной памяти, запись в основную память не навязывается. Если в кэше нет EMPTY-слотов, придется пожертвовать текущим содержимым, при этом только содержимое строк со статусом 'M' должно быть записано в основную память. Подход не отличается от используемого в обычной кэш-памяти, и обратную запись можно выполнять без особых гарантий атомарности. Если размер кэша достаточно велик, его содержимое может храниться долгое время. Если транзакции снова и снова работают с одной и той же областью памяти, прирост скорости может быть попросту огромен, поскольку в отличие от "обычного" подхода, когда на каждой итерации имеем одну или две записи в основную память, при подходе с применением транзакционной памяти все запросы обрабатываются кэшем транзакций, который так же быстр, как L1d.
Всё, что операции VALIDATE и COMMIT делают в случае отмены транзакции, это помечают XABORT-слоты как пустые, а XCOMMIT-слоты - как NORMAL. Соответственно, когда операцией COMMIT транзакция успешно завершается, слоты XCOMMIT помечаются как пустые, а XABORT - как NORMAL. Все эти операции крайне быстры, и выполняются в пределах кэша транзакций. Никакой дополнительной информации другим процессорам, желающим произвести транзакцию, не передается; они просто пробуют свою удачу опять и опять. Как это организовать эффективно - другой вопрос. В примере выше мы просто ставили ...delay... в соответствующих местах. Возможно, в будущих процессорах появится аппаратная реализация нужного нам алгоритма задержек.
Подведем итоги. Операции с транзакционной памятью обращаются к шине только при начале новой транзакции либо когда в выполняющуюся транзакцию нужно загрузить новую строку, которую не удалось найти в кэше транзакций. Операции в транзакциях, помеченных как отмененные, никогда не обратятся к шине. Не будет никакого "пинг-понга" со строками кэшей, обычно получающегося при попытке нескольких потоков использовать одну и ту же область памяти.
8.2.5. О чем еще стоит сказать
В разделе 6.4.2 мы уже обсудили, как можно использовать префикс lock (доступен на x86 и x86-64) во избежание применения атомарных операций в некоторых случаях. Однако, предложенные приемы не работают в случае множества потоков, которые при этом не борются за одну и ту же область памяти. В таком случае применение атомарных операций не обязательно. А с транзакционной памятью проблема исчезает сама собой. Ресурсоемкие запросы RFO выполняются только когда разные процессоры обращаются к одной и той же области одновременно, либо сразу друг за другом. Только тогда они и используются. Как-то еще оптимизировать выполнение уже практически невозможно.
Внимательный читатель наверняка уже задался вопросом, как же быть с задержками. Давайте представим, что может произойти в самом худшем случае? Что, если поток с активной транзакцией внезапно выходит из очереди, либо получает сигнал и, возможно, завершается, либо решает использовать siglongjmp для перехода в другое состояние? Ответ один: транзакция будет отменена. Ее можно отменить в любой момент: и когда поток выполняет системный вызов, и когда он получает сигнал (т.е. происходит смена уровня кольца). Так же может оказаться, что отмена транзакции - часть работы операционной системы при обработке системных вызовов или сигналов. Как бы то ни было, нам придется подождать, чтобы увидеть, как это всё будет реализовано на деле.
Но и прямо сейчас есть над чем поразмыслить. Рассмотрим последний в этом разделе нюанс относительно транзакционной памяти. Кэш транзакций, как и другие кэши, работает с кэш-строками. Поскольку он представляет собой эксклюзивный кэш, то одновременное использование одной и той же строки транзакциями и нетранзакционной операцией затруднительно. Следовательно, важно
- убирать данные, не используемые транзакцией, из кэш-строки
- данные разных транзакций хранить в разных строках кэша
Первый подход далеко не нов - сегодня он окупает себя сполна и при использовании атомарных операций. Со вторым сложнее: в наше время объекты почти никогда не выравниваются по строкам кэша в связи с высокой стоимостью. Если используемые данные, а с ними и слова, измененные с помощью атомарных операций, хранить в одной кэш-строке, то этим уменьшается количество затраченных строк. Это не относится к взаимным исключениям (где мьютекс всегда привязан к отдельной строке кэша), но в остальных случаях вполне реально расположить данные атомарных операций вместе с другими данными. В случае же транзакционной памяти, такое применение строки кэша для двух целей разом, скорее всего окажется фатальным. Любая обычная попытка доступа к данным {К данным рассматриваемой строки, конечно же. Доступ к другим случайным строкам не влияет на ход выполнения транзакции.} приведет к удалению кэш-строки из кэша транзакций, отменяя тем самым выполняемую транзакцию. Выравнивание объектов по строкам кэша в будущем станет вопросом не только производительности, но также корректности и точности.
Хотя возможно, транзакционная память будет по умолчанию реализована с более точным учетом данных, и в результате мы избежим проблем с обычным доступом к информации, находящейся в строках кэша, используемых транзакциями. Вот только такая реализация потребует гораздо больше усилий, поскольку тогда информации протокола MESI уже будет недостаточно.
| Назад | Оглавление | Вперед |