Я пытаюсь понять низкоуровневую механику CAS на x86/x64, и я очень благодарен за помощь/понимание.
Причина, по которой я думал об этом, заключается в том, что я пытаюсь рассуждать об экспоненциальном отсрочке и в принципе понимаю, какой должна быть правильная единица задержки отсрочки.
Если я посмотрю на свободную свободную таблицу сравнения, без экспоненциального отсрочки, я вижу, что число потоков увеличивается, производительность быстро выравнивается.
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, если они будут происходить одновременно. Оба потерпят неудачу. (Prolly, потому что я был в глубине души, думая о ethernet).
Это "очевидно" объясняет результаты - все эти инструкции CAS работают одновременно, очень немногие имеют возможность полностью выполнить, прежде чем будут разрушены.
Подумав об этом еще, я считаю, что теперь этого не может быть. В инструкции CAS нет режима сбоя. Он скажет вам, что пункт назначения равен или не равен сравнению. Все это. Он не возвращается и говорит: "О, извините, натолкнулся на кого-то другого".
Разрушительная помеха IS возникает, но она возникает на более высоком уровне, в самом алгоритме структуры данных. Когда мы нажимаем или поп из/в freelist, мы на самом деле пытаемся поменяться местами. Нам нужно, чтобы место назначения было стабильным достаточно долго, чтобы мы могли его прочитать, выполнить любую работу, которую нам нужно сделать, а затем найти ее без изменений, чтобы мы могли завершить наш push/pop.
Если другие потоки сохраняют CASing, назначение нестабильно - оно продолжает меняться - и нам остается повторить нашу операцию.
Но теперь я в замешательстве.
Мы видим, что один поток выполняет около 30 миллионов операций push/pop. Назначение должно быть стабильным на протяжении одной из этих операций, чтобы операция преуспела, поэтому мы видим, что есть 30 миллионов слотов. Если у нас есть два потока, то максимальная теоретическая производительность, которую мы можем иметь, составляет 15 миллионов операций на поток; каждый поток использует половину слотов.
Теперь вернемся к CAS. CAS не имеет режима отказа. Итак, что происходит, когда второй поток пытается использовать CAS, когда другой поток уже является CASing? ну, второй поток потерпит неудачу на уровне структуры данных, так как обмен не может произойти, поэтому он повторит обмен.
Но теперь представьте, что у нас есть много потоков. Первый поток, начинающийся с CAS, будет успешным (если предположить, что каждый CAS принимает ровно одно и то же время - не верно, но это предположение не меняет ничего фундаментального, так что хорошо рассуждать). Все остальные потерпят неудачу.
Но как только первый поток будет завершен, следующий поток, который прочитает новое значение назначения, получит успешное выполнение CAS (и все остальные потоки, все еще выполняющие свои CAS или начинающие новые CAS, будут терпеть неудачу).
Итак, почему мы не видим идеального масштабирования? потому что каждый слот должен использоваться!
Я думаю, поэтому я не понимаю CAS должным образом.
Чтение руководства по разработке программного обеспечения для архитектуры Intel, я нахожу, что если все данные присутствуют в кеше (в какой ситуации меня интересует), протокол когерентности кэша выполняет CAS.
Drepper в своем белом документе описывает LL/SC и как он работает с использованием MESI.
Мне кажется разумным, чтобы CAS работал аналогичным образом.
Рассмотрим два случая потока. Первая нить начинается с CAS. Линия кэша с пунктом назначения находится в кеше и помечена как эксклюзивная.
Вторая нить начинается с CAS. Первое ядро отправляет свою линию кэша во второе ядро, и оба ядра имеют выделенную строку кэша.
Первый поток завершает CAS и записывает в строку кэша (запись всегда происходит на x86/x64, даже если сравнение было ложным, оно просто записывает исходное значение).
Акт записи маркирует строку кэша как измененную; возникает RFO, в результате чего второе ядро помечает свою строку кэша как недопустимую.
Второй поток приходит для завершения CAS и замечает, что его строка кеша недействительна... и затем, что? Мне трудно поверить, что инструкция находится в ЦП, внутренне зацикленной до тех пор, пока это не удастся - хотя мне интересно, потому что LL/SC на ARM требует, чтобы вы в своей сборке выполняли этот цикл. Но инструкция CAS знает, что значение адресата изменилось, поэтому результаты его сравнения недействительны. Но с CAS нет ошибки; он всегда возвращает true или false для сравнения. Но даже если инструкции выполняются до завершения, я все равно ожидаю отличного масштабирования. Каждый слот должен использоваться.
Так что же происходит? что происходит с CAS?
Что я вижу, так это то, что по мере увеличения количества потоков все меньше и меньше делается - все доступные слоты, конечно, не используются. Что-то вызывает это. Является ли это разрушительным вмешательством между инструкциями CAS? или это большое количество RFO, поддерживающих CPU- > северную шину?
Что я замечаю с большим интересом, так это то, что два потока на одном и том же физическом ядре отлично. В этом случае происходит нечто особенное и другое - два потока на отдельных физических ядрах также равны половине. Но этого недостаточно, чтобы объяснить все это.
