Каковы внутренние характеристики процессора при конфликте CAS?

Я пытаюсь понять низкоуровневую механику CAS на x86 / x64, и я очень признателен за помощь /insight.

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

Release 7 Lock-Free Freelist Benchmark #1

   M
   N
   S
  L3U
L2U L2U
L1D L1D
L1I L1I
 P   P
L L L L total ops,mean ops/sec per thread,standard deviation,scalability
0 0 0 1 310134488,31013449,0,1.00
0 1 0 1 136313300,6815665,38365,0.22

0 1 0 1 136401284,6820064,50706,0.22
1 1 1 1 111134328,2778358,23851,0.09

0 0 1 1 334747444,16737372,2421,0.54
1 1 1 1 111105898,2777647,40399,0.09

Как мы знаем, может произойти блокировка в реальном времени, где каждый поток предотвращает развитие других.

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

Это «очевидно» объясняет результаты - все эти инструкции CAS, работающие одновременно, очень немногие имеют шанс полностью выполнить, прежде чем они будут разрушительно прерваны.

Подумав еще немного, я считаю, что теперь этого не может быть. Инструкция CAS на самом деле НЕ ИМЕЕТ режима отказа. Он сообщит вам, что пункт назначения равен или не равен сопоставимому. Вот и все. Он не возвращается и не говорит: «Ой, извините, столкнулся с кем-то другим».

Деструктивная помеха имеет место, но это происходит на более высоком уровне, в самом алгоритме структуры данных. Когда мы нажимаем или выталкиваем из / в список фрилансеров, мы на самом деле ПЫТАЕМСЯ поменяться местами. Нам нужно, чтобы адресат был стабильным достаточно долго, чтобы мы могли его читать, выполнять любую работу, которая нам нужна, а затем находить его неизменным, чтобы мы могли завершить наш push / pop.

Если другие потоки сохраняют CASing, пункт назначения не t стабильный - он постоянно меняется - и нам постоянно приходится повторять нашу операцию.

Но теперь я запутался.

Мы видим, что один поток выполняет около 30 миллионов операций push / pop. Назначение должно быть стабильным на протяжении одной из этих операций, чтобы операция была успешной, поэтому мы видим, что существует 30 миллионов «слотов». Если у нас есть два потока, тогда максимальная теоретическая производительность, которую мы можем получить, составляет 15 миллионов операций на поток; каждый поток использует половину слотов.

Теперь вернемся к CAS. CAS не имеет режима отказа. Итак, что происходит, когда второй поток пытается подключиться к CAS, когда другой поток уже находится в CAS? ну, второй поток завершится ошибкой на уровне структуры данных, так как обмен не может произойти, поэтому он попытается повторить обмен.

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

Но как только первый поток завершится, следующий поток, который считывает новое значение назначения, получит успешный CAS (и все остальные потоки, все еще выполняющие свои CAS или начинающие новые CAS, потерпят неудачу).

Так почему мы не видим идеального масштабирования? потому что должен использоваться каждый «слот»!

Я думаю, что поэтому я не понимаю CAS должным образом.

Читая Руководство разработчика программного обеспечения для архитектуры Intel, я обнаружил, что если все данные присутствуют в кеше (в какой ситуации я

Дреппер в своем техническом документе описывает LL / SC и то, как он работает с использованием MESI.

Мне кажется разумным, чтобы CAS работала аналогичным образом.

12256] Рассмотрим случай с двумя потоками. Первый поток начинает свой CAS. Строка кэша с адресатом находится в его кэше и помечена как эксклюзивная.

Второй поток начинает CAS. Первое ядро ​​отправляет свою строку кэша второму ядру, и у обоих ядер эта строка кэша помечена как общая.

Первый поток завершает CAS и записывает в строку кеша (запись всегда происходит на x86 / x64, даже если сравнение было ложным; он просто записывает исходное значение).

Запись отмечает строку кэша как измененную; происходит RFO, в результате чего второе ядро ​​отмечает свою строку кэша как недопустимую.

Второй поток приходит для завершения своего CAS и замечает, что его строка кэша недействительна ... и что потом? Мне трудно поверить, что инструкция находится внутри ЦП в цикле до тех пор, пока она не завершится успешно - хотя мне интересно, потому что LL / SC на ARM требует вас в вашей сборке для выполнения этого цикла. Но инструкция CAS знает, что значение назначения изменилось, поэтому результаты ее сравнения недействительны. Но есть' s ошибка невозможна с CAS; он всегда возвращает true или false для сравнения. Но даже если инструкции будут повторяться до завершения, я все равно буду ожидать идеального масштабирования. Каждый «слот» по-прежнему должен использоваться.

Так что же происходит? Что происходит с CAS?

Я действительно вижу, что по мере увеличения количества потоков выполняется все меньше и меньше работы - все доступные «слоты» определенно не используются. Что-то вызывает это. Это деструктивное вмешательство в инструкции CAS? Или это большое количество RFO, загружающих шину CPU-> Northbridge?

Я с большим интересом обращаю внимание на то, что два потока на одном физическом ядре идеально масштабируются. В этом случае происходит что-то особенное и иное - два потока на отдельных физических ядрах также масштабируются наполовину. Но это' недостаточно ключа, чтобы все это объяснить.