Переупорядочение зависимых нагрузок в процессоре

Question

Переупорядочение зависимых нагрузок в процессоре

Я читал очень популярную статью Пола МакКенни (Paul E. McKenney), " Память барьеров: взгляд на оборудование для хакеров".

В статье подчеркивается, что очень слабо упорядоченные процессоры, такие как Alpha, могут переупорядочивать зависимые нагрузки, что является побочным эффектом многораздельного кэша.

Отрывок из бумаги:

1 struct el *insert(long key, long data)
2 {
3     struct el *p;
4     p = kmalloc(sizeof(*p), GPF_ATOMIC);
5     spin_lock(&mutex);
6     p->next = head.next;
7     p->key = key;
8     p->data = data; 
9     smp_wmb();
10    head.next = p;
11    spin_unlock(&mutex);
12 }
13
14 struct el *search(long key)
15 {
16     struct el *p;
17     p = head.next;
18     while (p != &head) {
19         /* BUG ON ALPHA!!! */
20         if (p->key == key) {
21             return (p);
22         }
23         p = p->next;
24     };
25     return (NULL);
26 }

Есть 2 процессора CPU0 и CPU1.
Каждый процессор имеет 2 банка кеша CB0(нечетный адрес), CB1(четный адрес).
Голова в CB0 и P в CB1.
У insert() есть барьер записи, который гарантирует, что недействительность для строки 6-8 - это сначала входная шина, за которой следует недействительность в строке 10.
Однако другой процессор, выполняющий поиск, может иметь слегка загруженную CB0 и сильно загруженную CB1.
Это означает, что процессор выводит последнее значение head, но старое значение p (потому что запрос на аннулирование для p еще не обработан CB1.)

Вопрос: Похоже, что все архитектуры ожидают альфа-чести зависимых нагрузок. Например: IA64 может изменить порядок следования, кроме переупорядочения зависимых нагрузок.

Загрузка переупорядочена после загрузки
Загрузка переупорядочена после магазина
Магазины переупорядочены после магазинов
Магазины переупорядочены после загрузки
Атомная инструкция переупорядочена с нагрузками.
Атомные Инструкции переупорядочены с магазинами.

Это заставляет меня задуматься, какая аппаратная поддержка требуется для предотвращения переупорядочения зависимой нагрузки.

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

Есть идеи?

7

synchronization locking cpu-architecture memory-barriers lock-free

Источник

user978524 31 янв '16 в 15:35

1 ответ

Другие вопросы по тегам synchronization locking cpu-architecture memory-barriers lock-free

user937324 03 фев '16 в 08:42 2016-02-03 08:42 · Answer 1 · 2016-02-03 08:42

Короткий ответ:

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

Длинный ответ:

Фон по отслеживанию зависимости

Это, вероятно, лучше всего объяснить на примере. Представьте, что у вас есть следующая последовательность инструкций (для простоты используются инструкции псевдокода):

ST R1, A       // store value in register R1 to memory at address A
LD B, R2       // load value from memory at address B to register R2
ADD R2, 1, R2  // add immediate value 1 to R2 and save result in R2

В этом примере есть зависимость между LD и ADD инструкция. ADD читает значение R2 и поэтому он не может выполняться, пока LD делает это значение доступным. Эта зависимость определяется регистром и может отслеживаться логикой проблемы процессора.

Однако может также существовать зависимость между ST и LD, если адрес A а также B мы одинаковы. Но в отличие от зависимости между LD и ADDвозможная зависимость между ST и LD неизвестно на момент выдачи инструкции (начинается исполнение).

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

Возвращаясь к примеру с псевдокодом, вы можете представить себе ситуацию, когда LD выполняется до ST (возможно, значение, необходимое в R1, по какой-то причине не было готово). Но когда ST выполняет это видит этот адрес A а также B подобные. Итак LD действительно должен был прочитать значение, которое было произведено ST, а не устаревшее значение, которое уже было в кэше. В результате LD необходимо будет выполнить заново вместе с любыми инструкциями, которые пришли после LD, Существуют различные варианты оптимизации, позволяющие уменьшить некоторые из этих издержек, но основная идея верна.

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

Правила упорядочения памяти

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

Альфа-пример

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

Initially: p = & x, x = 1, y = 0

    Thread 1         Thread 2
--------------------------------
  y = 1         |    
  memoryBarrier |    i = *p
  p = & y       |
--------------------------------
Can result in: i = 0

Аномальное поведение в настоящее время возможно только в системе на базе 21264. И, очевидно, вы должны использовать один из наших многопроцессорных серверов. Наконец, шансы, что вы на самом деле видите его, очень низки, но это возможно.
Вот что должно произойти, чтобы это поведение проявилось. Предположим, что T1 работает на P1 и T2 на P2. P2 должен быть местом кэширования y со значением 0. P1 делает y=1, что приводит к отправке "аннулировать y" в P2. Этот недействительный вводится во входящую "очередь тестов" P2; как вы увидите, проблема возникает из-за того, что этот недействительный объект теоретически может находиться в очереди тестов, не занимая МБ на P2. Аннулирование сразу же подтверждается на этом этапе (т. Е. Вы не ждете, пока он фактически сделает недействительной копию в кэше P2, прежде чем отправлять подтверждение). Следовательно, P1 может пройти через свой MB. И он продолжает делать запись в р. Теперь P2 переходит к чтению p. Ответу на чтение p разрешено обходить очередь тестов на P2 по входящему пути (это позволяет ответам / данным быстро возвращаться к 21264 без необходимости ожидания обслуживания предыдущих входящих тестов). Теперь P2 может разыменовывать P, чтобы прочитать старое значение y, которое находится в его кэше (там находится значение y в очереди тестов P2).
Как это может исправить MB на P2? 21264 сбрасывает свою входящую очередь проверки (т. Е. Обслуживает любые ожидающие сообщения там) на каждом МБ. Следовательно, после прочтения P вы создаете MB, который наверняка передаст инвалидности y. И вы больше не можете видеть старое кэшированное значение для y.
Несмотря на то, что приведенный выше сценарий теоретически возможен, шансы увидеть проблему из-за него чрезвычайно малы. Причина в том, что даже если вы правильно настроите кэширование, P2, скорее всего, будет иметь достаточную возможность обслуживать сообщения (т.е. недействительные) в своей очереди проверки, прежде чем он получит ответ данных для "чтения p". Тем не менее, если вы попадаете в ситуацию, когда вы помещаете много вещей в очередь тестов P2 перед инвалидом для y, то вполне возможно, что ответ на p вернется и обойдет это инвалидность. Хотя вам будет сложно настроить сценарий и реально наблюдать аномалию.
Выше указано, как нынешние Альфы могут нарушать то, что вы показали. Альфа будущего может нарушить его из-за других оптимизаций. Одна интересная оптимизация - это прогнозирование стоимости.

Резюме

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