Даже более быстрый недорогой потокобезопасный счетчик?

Question

Я читал эту тему: C# Thread safe fast(est) counter и реализовал эту функцию в своем параллельном коде. Насколько я вижу, все работает нормально, однако оно значительно увеличило время обработки, как и 10% или около того.

Это немного подслушивало меня, и я думаю, что проблема заключается в том, что я делаю огромное количество относительно дешевых (< 1 квантовых) задач на небольших фрагментах данных, которые хорошо дополняются и, вероятно, хорошо используют локализации кэша, таким образом, работающая оптимально. Мое лучшее предположение, основанное на том, что мало что известно о MESI, заключается в том, что префикс x86 LOCK в Interlocked.Increment выталкивает кешью в эксклюзивный режим и заставляет пропустить кеш на других ядрах и заставляет перезагружать кеш на каждом параллельном проходе только ради увеличения этого счетчика , С задержкой в ​​100 нс для промаха в кэше и моей рабочей нагрузкой он, похоже, складывается. (Опять же, я мог ошибаться)

Теперь я не вижу способа обойти это, но, возможно, мне не хватает чего-то очевидного. Я даже думал об использовании n счетчиков (соответствующих степени распараллеливания), а затем увеличивал каждый на конкретном ядре, однако он кажется неосуществимым (обнаружение того ядра, на котором я работаю, вероятно, будет более дорогостоящим, не говоря уже о разработке, если/then/else структуру и испортить конвейер выполнения). Любые идеи о том, как разбить этого зверя? :)

Answer 1

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

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

Для этого вы можете использовать и class Holder { public int I; }. ThreadLocal поддерживает перечисление всех экземпляров, которые были созданы, чтобы вы могли их суммировать. Вы также можете использовать структуру, которая дополняется размером строки кеша. Это безопаснее.

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

Более быстрый вариант заключается в использовании Holder[]. Каждый поток обращается к индексу случайного массива один раз, а затем обращается к этому объекту-держателю. Индексирование массива происходит быстрее, чем локальный доступ к потоку. Если количество экземпляров держателей, которые вы используете, намного больше (10x), чем количество потоков, будет мало споров. Большинство писем будут идти в том же кэшированном виде.

Вместо случайного индекса вы можете использовать List<Holder> и добавлять элементы, поскольку к процессу присоединяется больше потоков.

Answer 2

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

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

Что префикс LOCK ограничивает объем спекулятивной работы, которую может выполнять процессор в ожидании завершения завершенной команды. Раздел 8.1.2 Руководства Intel 64 и IA-32 архитектуры программного обеспечения разработчика говорит:

заблокированные операции являются атомарными в отношении всех других памятей операций и всех видимых внешних события. Только команда fetch и обращения к таблицам страниц могут передавать заблокированные инструкции. Заблокированные инструкции могут быть использованы для синхронизации данных, написанных одним процессором и считанных другим процессором.

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