Еще быстрее, недорогой, потокобезопасный счетчик?
Я прочитал эту тему: C# Thread Safe Fast(EST) счетчик и реализовал эту функцию в моем параллельном коде. Насколько я вижу, все это работает нормально, однако оно заметно увеличило время обработки, например, на 10% или около того.
Это немного беспокоит меня, и я думаю, что проблема заключается в том, что я выполняю огромное количество сравнительно дешевых (<1 квант) задач с небольшими фрагментами данных, которые хорошо разбиты и, вероятно, хорошо используют локальность кэша, Таким образом, работает оптимально. Насколько я знаю о MESI, я думаю, что x86 LOCK префикс в Interlocked.Increment переводит строку кэширования в эксклюзивный режим и вызывает ошибку кэширования на других ядрах и вызывает перезагрузку кэша на каждом параллельном проходе только для увеличения этого счетчика. С задержкой в 100 нс из-за отсутствия кэша и моей рабочей нагрузки, кажется, все складывается. (Опять же, я могу ошибаться)
Сейчас я не вижу выхода из этого, но, возможно, я упускаю что-то очевидное. Я даже думал об использовании n счетчиков (соответствующих степени распараллеливания) и последующем увеличении каждого из них на конкретном ядре, однако это кажется невозможным (определение того, на каком ядре я работаю, вероятно, будет более дорогим, не говоря уже о сложном if/then/else структура и испортить с конвейером исполнения). Есть идеи как сломать этого зверя?:)
2 ответа
Операции с несколькими ядрами в одной и той же строке кэша конкурируют на аппаратном уровне. Это верно для заблокированного и для регулярного доступа к памяти. Это настоящая проблема. Конкурирующий доступ вообще не масштабируется, когда добавляется больше ядер. Масштабирование, как правило, является жестким негативом.
Вам нужно использовать несколько строк кэша, причем каждое ядро большую часть времени использует свое собственное.
Вы могли бы использовать ThreadLocal<Holder> а также class Holder { public int I; } для этого. ThreadLocal поддерживает перечисление всех экземпляров, которые были созданы, чтобы вы могли их суммировать. Вы также можете использовать структуру, дополненную размером строки кэша. Это безопаснее.
Обратите внимание, что не важно использовать один счетчик на ядро. Каждый поток достаточно хорош, потому что кванты времени невероятно велики по сравнению с операциями приращения. Несколько неудачных обращений не являются проблемой производительности.
Более быстрый вариант будет использовать Holder[], Каждый поток рисует случайный индекс массива один раз, а затем обращается к этому объекту-держателю. Индексирование массива выполняется быстрее, чем локальный доступ к потокам. Если количество используемых вами экземпляров держателей будет намного больше (в 10 раз), чем количество потоков, возникнет небольшая конкуренция. Большинство записей будут идти в той же уже кэшированной строке.
Вместо случайного индекса вы можете использовать List<Holder> и добавьте элементы, поскольку больше потоков присоединяется к обработке.
Я думал, что я бы дал некоторые разъяснения о согласованности кэша и что LOCK префикс делает в архитектурах Intel. Поскольку это слишком долго для комментария, а также отвечает на некоторые вопросы, которые вы подняли, я думаю, что уместно опубликовать в качестве ответа.
В протоколе согласованности кэша MESI любая запись в строку кэша приведет к изменению состояния на эксклюзивное, независимо от того, используете ли вы LOCK префикс или нет. Таким образом, если два процессора одновременно обращаются к одной и той же строке кэша, и по крайней мере один из процессоров выполняет запись, тогда процессоры будут испытывать пропадание строки кэша при доступе к строке, которой они делятся. Принимая во внимание, что если бы они оба только читали из строки, то у них были бы попадания в строку кэша, потому что они могли бы держать строку в своем частном кэше L1 в общем состоянии.
Что за LOCK префикс ограничивает объем спекулятивной работы, которую процессор может выполнять, ожидая завершения выполнения заблокированной инструкции. Раздел 8.1.2 Руководства разработчика программного обеспечения для архитектуры Intel 64 и IA-32 гласит:
Заблокированные операции являются атомарными относительно всех других операций с памятью и всех видимых извне событий. Только выборка инструкций и доступ к таблице страниц могут передавать заблокированные инструкции. Заблокированные инструкции могут использоваться для синхронизации данных, записанных одним процессором и считанных другим процессором.
При нормальных обстоятельствах процессор может спекулятивно выполнять инструкции в ожидании устранения ошибки кэша. Но LOCK Префикс предотвращает это и по существу останавливает конвейер, пока заблокированная инструкция не завершит выполнение.