Наши партнеры

Книги по Linux (с отзывами читателей)

Библиотека сайта rus-linux.net

На главную -> MyLDP -> Тематический каталог -> Аппаратное обеспечение

Что каждый программист должен знать о памяти. Часть 8. Технологии будущего

Оригинал: Memory part 8: Future technologies
Автор: Ulrich Drepper
Дата публикации: ноябрь 2007 г.
Перевод: М.Ульянов
Дата перевода: май 2010 г.

8. Грядущие технологии: что нас ждет?

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

8.1. Проблемы с атомарными операциями

Традиционно, синхронизация доступа к разделяемым структурам данных реализуется двумя способами:

применением взаимных исключений (мьютексов), для чего обычно используются возможности системной среды исполнения;
применением безблокировочных (lock-free) структур данных.

Недостаток второго варианта: от процессора требуется поддержка примитивов, способных выполнить полностью всю операцию атомарно. Не все процессоры поддерживают такие примитивы. На большинстве архитектур поддержка сводится к атомарным операциям чтения и записи одного [машинного] слова. Есть два основных способа их реализации (см. раздел 6.4.2):

использование атомарной операции "сравнение и замена" (CAS);
использование пары инструкций load lock/store conditional (LL/SC).

Нетрудно заметить, что операция CAS может быть реализована с применением инструкций LL/SC. И поэтому именно она применяется в качестве основы большинства атомарных операций и безблокировочных структур данных.

Некоторые процессоры, в особенности архитектуры x86 и x86-64, поддерживают куда более широкий набор атомарных инструкций. Многие из которых представляют собой версии CAS, оптимизированные под отдельные задачи. Например, атомарный инкремент хранящегося в памяти значения может быть реализован с помощью инструкций CAS и LL/SC, но родная, "нативная" поддержка атомарного инкрементирования на процессорах x86/x86-64 работает быстрее. Важно, чтобы программисты при работе знали об этих инструкциях и о том, как их применять. Хотя в этом нет ничего нового.

Но что действительно выделяет эти две архитектуры, так это поддержка операций CAS с двойными словами (DCAS). Это значительный плюс для некоторых (но не для всех, см. [dcas]) приложений . В качестве примера использования DCAS давайте попробуем написать безблокировочную структуру данных стека LIFO, основанную на массиве. Первая попытка, с применением встроенных средств gcc, показана на рисунке 8.1.

  struct elem {
    data_t d;
    struct elem *c;
  };
  struct elem *top;
  void push(struct elem *n) {
    n->c = top;
    top = n;
  }
  struct elem *pop(void) {
    struct elem *res = top;
    if (res != NULL)
      top = res->c;
    return res;
  }

Рисунок 8.1: Стек LIFO, не ориентированный на многопоточность

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

Для начала попытаемся решить проблему, применив CAS при вставке и удалении элементов списка. В итоге получим код, показанный на рисунке 8.2.

  #define CAS __sync_bool_compare_and_swap
  struct elem {
    data_t d;
    struct elem *c;
  };
  struct elem *top;
  void push(struct elem *n) {
    do
      n->c = top;
    while (!CAS(&top, n->c, n));
  }
  struct elem *pop(void) {
    struct elem *res;
    while ((res = top) != NULL)
      if (CAS(&top, res, res->c))
        break;
    return res;
  }

Рисунок 8.2: Стек LIFO, организованный с применением CAS

На первый взгляд, должно работать. Переменная top не изменяется до тех пор, пока не совпадет с элементом, который находился на вершине стека при начале операции. Но нужно принимать во внимание параллельность на всех уровнях. Другой поток, работающий с этой же структурой, может вступить в дело в самый неподходящий момент. Один из таких случаев - так называемая проблема ABA. Представьте, что произойдет, если второй поток запланирован прямо перед инструкцией CAS в pop и он выполняет следующие действия:

l = pop()
push(newelem)
push(l)

В результате этих действий элемент, находящийся на вершине стека, возвращается на своё место, но второй элемент изменился. При этом в первом потоке, поскольку верхний элемент остался прежним, операция CAS выполнится успешно. Но значение res->c уже не верно. Это указатель на второй элемент первоначального стека, а не на newelem. И что в итоге? Новый элемент потерян.

В литературе [см. lockfree] можно найти предложения по решению этой проблемы, основанные на особенностях некоторых процессоров. А именно, имеются в виду процессоры x86 и x86-64 и их способность выполнять инструкции DCAS. На рисунке 8.3 показана третья версия кода, на этот раз с применением DCAS.

  #define CAS __sync_bool_compare_and_swap
  struct elem {
    data_t d;
    struct elem *c;
  };
  struct lifo {
    struct elem *top;
    size_t gen;
  } l;
  void push(struct elem *n) {
    struct lifo old, new;
    do {
      old = l;
      new.top = n->c = old.top;
      new.gen = old.gen + 1;
    } while (!CAS(&l, old, new));
  }
  struct elem *pop(void) {
    struct lifo old, new;
    do {
      old = l;
      if (old.top == NULL) return NULL;
      new.top = old.top->c;
      new.gen = old.gen + 1;
    } while (!CAS(&l, old, new));
    return old.top;
  }

Рисунок 8.3: Стек LIFO, основанный на CAS с двойными словами

В отличие от предыдущей пары примеров, это лишь псевдокод (на данный момент), поскольку gcc пока "не понимает" передачу структур в качестве параметров CAS. Тем не менее, такого примера должно быть достаточно для понимания принципов подхода. К указателю на вершину стека добавляется счетчик обращений. Так как он изменяется при любой операции, будь то push или pop, описанная выше проблема ABA решается сама собой. К тому времени как первый поток возобновит работу, пытаясь обновить указатель top, счетчик обращений уже будет увеличен трижды. Следовательно, инструкция CAS завершится неудачей, и на следующей итерации цикла будут определены верные значения первого и второго элементов стека. Мы избежали ошибки. Проблема решена!

Но решена ли она на самом деле? Авторы данного труда [lockfree] убеждены, что да - и надо отдать им должное, такой подход стоит упоминания. Действительно, вполне возможно создать структуры данных для стека LIFO, позволяющие использовать вышеприведенный код. Но в общем случае, этот подход не лучше предыдущего. Проблемы с параллельностью не исчезли - они лишь переместились в другое место. Предположим, поток выполняет pop и затем прерывается сразу после проверки old.top == NULL. Тут второй поток использует pop и завладевает бывшим первым элементом стека. Поток может сделать с ним что угодно - поменять все значения, к примеру, или (в случае динамически выделяемых элементов) освободить память.

Затем первый поток возобновляет работу. В переменной old все еще хранится предыдущее значение вершины стека. А если точнее, указатель top ссылается на элемент, только что обработанный вторым потоком. Оператором new.top = old.top->c первый поток обращается к значению элемента через указатель. Но элемент, на который ссылается указатель, возможно, уже освобожден. А часть адресного пространства, где он находился, возможно, недоступна - происходит сбой. В случае работы с данными родового типа подобные ситуации недопустимы. Любое решение этой проблемы обходится чрезвычайно дорого: память нельзя освобождать, ну или необходимо получить подтверждение того, что ни один поток более не ссылается на нее, прежде чем выполнить освобождение. Учитывая, что безблокировочные структуры данных по определению должны работать быстрее других и лучше поддерживать параллельность, видим, что эти дополнительные требования попросту сводят на нет все преимущества. Решить проблему может так называемая "сборка мусора" при работе с памятью, но она поддерживается не всеми языками. А где поддерживается - имеет свою цену.

Для более сложных структур данных обычно всё еще хуже. В вышеупомянутом документе также описана реализация FIFO, с некоторыми уточнениями в последующих материалах. Но и там всё те же проблемы. Поскольку на существующем оборудовании (x86, x86-64) инструкции CAS могут изменять только пару последовательно расположенных в памяти слов, то в других часто встречающихся ситуациях они вообще бывают бесполезны. К примеру, невозможно атомарное добавление либо удаление элементов в любом месте двусвязного списка. {Для справки: разработчики IA-64 также не реализовали эту возможность. Они позволяют сравнивать два слова, но заменять - только одно.}

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

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 уже будет недостаточно.

8.3. Увеличение латентности

Относительно дальнейшего развития технологий памяти можно быть уверенным в одном: латентность продолжит расти. В разделе 2.2.4 мы уже говорили о том, что задержки памяти DDR3 будут превышать таковые у DDR2. Память FB-DRAM также имеет теоретически более высокие задержки, особенно при последовательном подключении модулей. Ведь проход по всем модулям запросов и ответов на них чего-то, да стоит.

Второй источник задержек - всё более широкое распространение NUMA. AMD Opteron в версии с несколькими ядрами (процессорами) как раз представляет собой систему NUMA. ЦПУ имеют свою локальную память с собственным контроллером, но к остальной части памяти доступ на материнских платах SMP осуществляется через шину HyperTransport. Технология Intel CSI будет использовать почти тот же принцип. В связи с ограничениями пропускной способности на каждый процессор и требованием (к примеру) постоянного использования множества 10-гигабитных Ethernet-портов, многосокетовые материнские платы никуда не исчезнут, даже учитывая увеличение числа ядер на каждом сокете.

Третий источник задержек - сопроцессоры. Мы думали, что избавились от них в начале 1990-х, когда исчезла необходимость в математических сопроцессорах на ЦП потребительского уровня, но теперь они возвращаются. Intel Geneseo и AMD Torrenza - расширения платформ, позволяющие сторонним разработчикам оборудования интегрировать свои продукты в материнские платы. То есть выходит, что сопроцессоры будут размещаться не на PCIe платах, а гораздо ближе к ЦПУ. Благодаря чему увеличится доступная им пропускная способность.

В IBM пошли по другому пути (хотя расширения по типу Intel и AMD всё ещё возможны) с процессором Cell. Данный процессор состоит, помимо ядра PowerPC, из восьми синергических вычислительных элементов (Synergistic Processing Units, SPU), которые по сути являются специализированными процессорами для (по большей части) вычислений с плавающей запятой.

Сопроцессоры и SPU объединяет то, что в них, скорее всего, будет использоваться еще более медленный набор логики памяти, чем в современных реальных процессорах. Частично это обусловлено необходимостью упрощения: все эти тонкости работы с кэшем, предвыборка и прочее - сложно, правда? Особенно когда в дополнение ко всему необходима поддержка когерентности кэша. Высокопроизводительные программы будут все больше полагаться на сопроцессоры, поскольку разница в производительности может быть огромна. Теоретическая пиковая производительность процессора Cell - 210 Гфлопс. Сравните с 50-60 Гфлопс для "обычного" хай-энд ЦПУ. Современные графические процессоры (Graphics Processing Units, GPU) достигают и более высоких результатов (до 500 Гфлопс), и их без особых проблем, пожалуй, можно интегрировать в системы Geneseo/Torrenza.

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

8.4. Векторные операции

Мультимедийные расширения современных процессоров, по сути, реализуют векторные операции в некоторой, очень ограниченной форме. Векторные инструкции характеризуются большим числом операций, выполняемых вместе. Ну, большим - если говорить о мультимедиа инструкциях и сравнивать со скалярными операциями. Это тем не менее очень и очень далеко от векторных компьютеров вроде Cray-1 или векторных блоков комплекса IBM 3090.

Для компенсации ограниченного числа операций, выполняемых за одну инструкцию (на большинстве машин это четыре операции с типом float или две с double), необходимо увеличение количества итераций внешних циклов. Пример в разделе 9.1 ясно это показывает: на каждую кэш-строку приходится по SM итераций.

Уменьшить это число можно, расширив векторные регистры и операции. Это дает нам нечто большее, чем просто улучшение декодирования инструкций и т.п.; мы сейчас более заинтересованы во влиянии на память. Если одной инструкцией можно считывать или записывать больше данных, то процессору лучше видно, как приложение использует память, и не приходится собирать информацию по кусочкам, исследуя поведение множества отдельных инструкций. Далее, полезнее становятся инструкции "сквозного" чтения или записи, т.е. которые не трогают кэш. С размером SSE регистра в 16 байт (в процессоре x86), использование "сквозного" чтения - не лучшая идея, поскольку тогда последующие запросы к той же строке будут вынуждены по новой загружать данные из памяти (в случае промахов кэша). С другой стороны, если векторные регистры будут достаточного размера для хранения одной и более строк кэша, операции сквозного чтения/записи станут не так страшны. На практике растет необходимость работать с наборами данных, не помещающимися в кэш-память.

Наличие больших векторных регистров не обязательно означает увеличение латентности, ведь векторным инструкциям не нужно ждать, пока прочитаются/запишутся все данные. Векторные процессорные блоки могут начать работу с теми данными, которые уже успели загрузиться, если получится распознать кодовую последовательность. Это значит, например, что если нужно загрузить векторный регистр и затем все элементы умножить на некое число, то процессор может начать операцию перемножения как только первая часть вектора будет загружена, не дожидаясь загрузки остальных. Всё это лишь вопрос сложности векторного блока. Рассмотренные факты показывают, что теоретически векторные регистры могут распространиться очень широко и уже сегодня программы можно разрабатывать, учитывая данную возможность. Практически же, процессоры используются в многопроцессных и многопоточных операционных системах, что накладывает ограничения на размер векторных регистров. А именно, важно время контекстного переключения, куда входит сохранение/загрузка значений регистров.

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

Векторные блоки прошлого имели различные режимы для обеспечения типичных, наиболее используемых запросов доступа:

используя striding, он же интервальный режим, можно указать величину промежутка между двумя соседними векторными элементами. Интервалы между всеми элементами должны быть одинаковыми, но это, к примеру, легко позволяет считать столбец матрицы в векторный регистр за одну инструкцию, а не использовать по инструкции на каждую строку.
используя косвенную адресацию памяти, можно создавать шаблоны произвольного доступа. Инструкция чтения/записи получает указатель на массив с адресами или смещениями от адресов памяти, и по ним работает.

Сейчас еще не ясно, увидим ли мы возрождение настоящих векторных операций в процессорах будущего. Быть может, эта задача будет возложена на сопроцессоры. В любом случае, если мы получим доступ к векторным операциям, будет важно корректно организовывать код, выполняющий подобные операции. Код должен быть самодостаточным и заменяемым, с интерфейсом, позволяющим эффективно применять векторные операции. Например, интерфейсы должны обеспечивать добавление матриц целиком, вместо того чтобы ограничиваться строками, столбцами или даже группами элементов. Чем больше "строительные блоки", тем выше шанс использования векторных операций.

В [vectorops] авторы призывают к возрождению векторных операций. Они выделяют множество преимуществ и пытаются развеять некоторые мифы. Но по правде говоря, они рисуют слишком упрощенную картину. Выше упомянуто, что большие наборы регистров означают увеличение времени контекстных переключений, чего следует избегать в операционных системах общего назначения. Почитайте о проблемах процессора IA-64, возникающих при операциях, интенсивно применяющих контекстные переключения. Долгое время выполнения векторных операций также становится проблемой, если задействуются прерывания. При возникновении прерывания, процессор должен остановить текущую работу и обработать его. После этого можно возобновлять прерванную работу. А в целом, прервать выполнение инструкции где-то в середине достаточно сложно; не то чтобы совсем невозможно, но сложно. Если время выполнения инструкции велико, то в ней должна быть реализована возможность приостановки, либо перезапуска. Иначе время реагирования на прерывание станет слишком большим. Последнее - недопустимо.

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