Синхронизация

C# и .NET Framework --- Оптимизация приложений .NET Framework --- Синхронизация

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

Прежде чем приступить к исследованиям, давайте обсудим саму необходимость синхронизации при работе с данными маленького объема. Современные процессоры способны выполнять атомарные операции чтения и записи содержимого в памяти. Например, запись 32-разрядного целого числа всегда выполняется атомарно. Это означает, что если процессор записывает в ячейку памяти значение 0xDE178AAC, прежде инициализированную нулем, другой процессор никогда не получит частично измененное значение в этой ячейке, такое как 0xDE170000 или 0x00008AAC. К сожалению, то же самое нельзя сказать о более объемных данных; например, даже на 64-разрядном процессоре операция записи 20 байт не является атомарной и не может быть атомарной.

Всякий раз, когда для выполнения операции с областью памяти требуется выполнить несколько инструкций, немедленно возникает проблема синхронизации. Например, операция ++i (где i является переменной на стеке типа int) обычно транслируется в последовательность из трех машинных инструкций:

mov eax, dword ptr [ebp-64]   ; скопировать со стека в регистр
inc eax                       ; увеличить значение в регистре
mov dword ptr [ebp-64], eax   ; скопировать из регистра на стек

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

Процессор #1                        Процессор #2

mov eax, dword ptr [ebp-64]
                                    mov eax, dword ptr [ebp-64]
                                    inc eax
									
inc eax
mov dword ptr [ebp-64], eax
                                    mov dword ptr [ebp-64], eax

В этом случае переменная получит значение 101, даже при том, что операция инкремента была выполнена двумя процессорами и переменная должна была получить значение 102. Это состояние гонки за ресурсами (race condition) - мы надеемся, очевидно и легко обнаруживается, - является наглядным примером ситуаций, требующих синхронизации.

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

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

• Языки программирования, основанные на использовании модели агентов, интегрируют модель конкурентного доступа глубоко в язык и требуют организации явных взаимодействий между агентами (объектами) в терминах обмена сообщениями, а не операций с совместно используемой памятью.

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

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

Код без блокировок

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

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

Все семейства процессоров, на которых Windows может выполняться, поддерживают аппаратный примитив синхронизации с названием «Сравнить-и-Заменить» (Compare-And-Swap, CAS). Примитив CAS выполняет операцию атомарно и имеет следующую семантику (в псевдокоде):

WORD CAS(WORD* location, WORD value, WORD comparand) 
{
    WORD old = *location;
	
    if (old == comparand) {
        *location = value;
    }
	
    return old;
}

Проще говоря, примитив CAS сравнивает содержимое памяти по адресу location с указанным значением comparand. Если в памяти хранится это значение, оно заменяется другим значением value; в противном случае значение в памяти не изменяется. В любом случае возвращается прежнее содержимое памяти, хранившееся до операции.

В процессорах Intel x86 этот примитив реализован в виде инструкции LOCK CMPXCHG. Трансляция вызова CAS(&a, b, с) в инструкцию LOCK CMPXCHG - это чисто механическая процедура, именно поэтому мы будем использовать аббревиатуру CAS. В .NET Framework примитив CAS реализован в виде множества перегруженных методов Interlocked.CompareExchange():

int n = 1;

// заменить 0 на 1
if (Interlocked.CompareExchange(ref n, 1, 0) == 0)
{ 
    // ... выполнить какие-нибудь операции
}

// инструкции на языке ассемблера x86:
mov eax, 0                            ; значение для сравнения
mov edx, 1                            ; новое значение
lock cmpxchg dword ptr [ebp-64], edx  ; предполагается, что n в [ebp-64]
test eax, eax                         ; if eax = 0, проверка возможности замены
jnz not_taken
; ... выполнить некоторые операции not taken:
not_taken:

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

Для начала рассмотрим простой пример умножения на месте. Нам требуется атомарно выполнить операцию x* = y, где x является совместно используемой переменной, запись в которую может выполняться одновременно несколькими потоками, а y - это константа, недоступная для изменения. Ниже приводится метод на языке C#, решающий поставленную задачу с применением примитива CAS:

public static void InterlockedMultiplyInPlace(ref int x, int y)
{
    int temp, mult;
    do
    {
        temp = x;
        mult = temp * y;
    } 
    while (Interlocked.CompareExchange(ref x, mult, temp) != temp);
}

Каждая итерация начинается с чтения значения x во временную переменную на стеке, которая недоступна другим потокам. Затем вычисляется результат умножения для записи в переменную х. И, наконец, цикл завершается, если compareExchange сообщит, что замена прежнего значения x результатом умножения произведена успешно, вернув оригинальное значение. Мы не можем гарантировать, что цикл завершится за некоторое ограниченное число итераций; однако весьма маловероятно, даже при наличии других процессоров, цикл будет выполнен более чем несколько раз. Но, как бы то ни было, цикл готов к такой ситуации.

Взгляните на следующую историю выполнения цикла двумя процессорами со значениями x = 3, y = 5:

Процессор #1                        Процессор #2

temp = x; (3)
                                    temp = x; (3)
mult = temp * y; (15)
                                    mult = temp * y; (15)
                                    CAS(ref x, mult, temp) == 3 (== temp)
									
CAS(ref x, mult, temp) == 15 (!= temp)

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

public static void InterlockedMultiplyInPlace(ref int x, int y)
{
    int temp, mult;
    do
    {
        temp = x;
        mult = x * y;
    } 
    while (Interlocked.CompareExchange(ref x, mult, temp) != temp);
}

Почему? Двукратное чтение значения x, даже в такой быстрой последовательности, не гарантирует, что будет получено одно и то же значение! Следующая история выполнения показывает, как могут быть получены неправильные результаты на двух процессорах и начальных значениях x = 3, y = 5 - в конце выполнения получится результата x = 60!

Процессор #1                        Процессор #2

temp = x; (3)
                                    x = 12;
mult = x * y; (60!)
                                    x = 3;
									
CAS(ref x, mult, temp) == 3 (== temp)

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

public static void DoWithCAS<T>(ref T location, Func<T, T> generator) 
   where T : class
{
    T temp, replace;
    do
    {
        temp = location;
        replace = generator(temp);
    } 
    while (Interlocked.CompareExchange(ref location, replace, temp) != temp);
}

Операция умножения достаточно легко выражается в терминах обобщенной версии:

public static void InterlockedMultiplyInPlace(ref int x, int y)
{
    DoWithCAS(ref x, t => t * y);
}

С помощью примитива CAS можно реализовать простой механизм синхронизации, который называется циклической блокировкой (spin-lock). Идея состоит в следующем: как только блокировка приобретается каким-то одним потоком, все другие потоки должны терпеть неудачу при попытке захватить ее, и повторять попытки. Циклическая блокировка может быть приобретена единственным потоком, а все остальные потоки должны будут «крутиться» (spin) в ожидании ее освобождения (понапрасну тратя процессорное время):

public class SpinLock
{
        private volatile int locked;

        public void Acquire()
        {
            while (Interlocked.CompareExchange(ref locked, 1, 0) != 0) ;
        }

        public void Release()
        {
            locked = 0;
        }
}

Модели памяти и изменчивые переменные

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

Вообще говоря, модель памяти для конкретного языка/окружения описывает, как компилятор и процессор могут переупорядочивать операции, выполняемые разными потоками, влияющими на взаимодействие потоков посредством совместно используемой памяти. Хотя в большинстве моделей принимается, что операции чтения и записи с одной и той же областью памяти не могут переупорядочиваться, существует редко встречающееся соглашение о семантике операций чтения и записи, выполняемых с разными участками памяти. Например, следующая программа может вывести 13 при начальных значениях f = 0, x = 13:

Процессор #1               Процессор #2

while (f == 0);            x = 42;
print(x);                  f = 1;

Причина такого, казалось бы, неожиданного результата состоит в том, что компилятор и процессор могут изменить порядок выполнения инструкций процессором 2 так, что запись в переменную f будет выполнена до записи в переменную x, а порядок выполнения инструкций процессором 1 так, что чтение переменной x будет выполнено перед чтением переменной f. Неправильное понимание конкретной модели памяти может приводить к чрезвычайно тяжело выявляемым ошибкам.

В C# имеется несколько средств, которые можно использовать для предупреждения проблем, связанных с переупорядочением операций. Первое из них - ключевое слово volatile, которое препятствует переупорядочению операций с конкретной переменной компилятором и большинством процессоров.

Второе - множество методов класса Interlocked и метод Thread.MemoryBarrier(), устанавливающие барьер, который не может быть преодолен в каком-то одном или в обоих направлениях при попытке переупорядочить инструкции. К счастью, механизмы синхронизации ОС Windows (вовлекающие системные вызовы), а также примитивы синхронизации без блокировок (lock-free) в TPL, автоматически устанавливают барьеры, когда это необходимо. Однако, если вы собираетесь заняться реализацией собственного механизма синхронизации, вам придется потратить немало времени, чтобы разобраться в модели памяти целевой среды выполнения.

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

Итак, вернемся к классу SpinLock. В нашей реализации циклической блокировки значение 0 соответствует свободной блокировке, а 1 - занятой. Наша реализация пытается заменить внутреннее значение единицей, передавая значение 0 для сравнения - то есть, блокировка может быть приобретена, только когда она свободна. Поскольку нет никаких гарантий, что поток, получивший блокировку, быстро освободит ее, использование циклической блокировки означает, что множество других потоков могут «крутиться» на месте, в ожидании освобождения блокировки, и напрасно расходовать процессорное время.

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

В действительности, циклические блокировки широко используются в ядре Windows для реализации внутренних механизмов синхронизации. Структуры данных в ядре, такие как база данных планировщика, список блоков в кеше файловой системы, база данных номеров страниц памяти и другие, защищаются одной или несколькими циклическими блокировками. Кроме того, в ядре Windows используется дополнительная оптимизация простой реализации циклической блокировки, описанной выше и страдающей двумя проблемами:

1. Циклическая блокировка не справедлива в терминах семантики FIFO. Процессор может быть последним из десяти процессоров, вызвавших метод Acquire(), но получить блокировку первым.

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

Ядро Windows использует циклические блокировки с очередью (in-stack queued spinlocks); циклическая блокировка с очередью поддерживает очередь процессоров, ожидающих ее освобождения, и каждый процессор, ожидающий на блокировке, «вращается» вокруг отдельной ячейки памяти, которая не кешируется другими процессорами. Когда процессор, владевший блокировкой, освобождает ее, он находит первый процессор в очереди и устанавливает бит, появление которого ожидает данный процессор. Это гарантирует семантику FIFO очереди и предотвращает принудительную актуализацию кешей всех процессоров, кроме того, который благополучно приобрел блокировку.

Реализации циклических блокировок промышленного уровня могут быть еще более надежными, предусматривать возможность определения предельного времени ожидания (за счет преобразования цикла в блокирующее ожидание), следить за потоком-владельцем, чтобы обеспечить корректное приобретение и освобождение, позволять рекурсивное приобретение блокировок и поддерживать дополнительные удобства. Одной из рекомендуемых реализаций является тип SpinLock из библиотеки Task Parallel Library.

Имея на вооружении примитив синхронизации CAS, мы можем реализовать чудо инженерной мысли - стек без блокировок. При обсуждении коллекций мы уже познакомились с некоторыми параллельными коллекциями, поэтому не будем повторять обсуждение, а реализуем тип ConcurrentStack<T>, оставшийся для нас тайной. Как по волшебству, стек типа ConcurrentStack<T> позволяет нескольким потокам вталкивать и выталкивать элементы, не требуя использовать механизмы синхронизации (которые мы рассмотрим далее).

Реализацию стека без блокировки мы выполним на основе односвязного списка. Вершиной стека будет голова списка; операции вталкивания элемента в стек и выталкивания со стека будут реализованы как замена головы списка. Для синхронизации этих операций мы используем примитив CAS; фактически мы можем использовать вспомогательный метод DoWithCAS<T>, представленный выше:

public class LockFreeStack<T>
{
    private class Node
    {
        public T Data;
        public Node Next;
    }

    private Node head;

    public void Push(T element)
    {
        Node node = new Node { Data = element };

        DoWithCAS(ref head, h =>
        {
            node.Next = h;
            return node;
        });
    }

    public bool TryPop(out T element)
    {
        // метод DoWithCAS здесь не подходит, потому что нам 
        // нужна семантика раннего завершения Node 
        Node node;
        do
        {
            node = head;
            if (node == null)
            {
                element = default(T);
                return false; // срочный выход - здесь нечего возвращать
            }
        } 
        while (Interlocked.CompareExchange(ref head, node.Next, node) != node);

        element = node.Data;
        return true;
    }

    public static void DoWithCAS<T>(ref T location, Func<T, T> generator) where T : class
    {
         // ...
    }
}

Метод Push() пытается заменить голову списка новым узлом, чей указатель Next будет указывать на текущую голову списка. Аналогично метод TryPop() пытается заменить голову списка узлом, на который ссылается указатель Next текущей головы, как показано на рисунке ниже:

Кому-то может показаться, что с помощью CAS и похожих примитивов синхронизации можно реализовать любую структуру данных, и действительно, мы можем привести примеры коллекций без блокировок, широко используемых в настоящее время:

• двусвязный список без блокировки;

• очередь без блокировки (с головой и хвостом);

• простая очередь с поддержкой приоритетов.

Однако существует множество разнообразных коллекций, которые не могут быть реализованы без блокировок и вынуждающих использовать блокирующие механизмы синхронизации. Кроме того, существует масса ситуаций, требующих использовать синхронизацию, но не позволяющих применять примитив CAS, потому что приходится выполнять продолжительные операции под защитой блокировки. Теперь обратимся к «настоящим» механизмам синхронизации, реализуемым операционной системой.

Механизмы синхронизации Windows

ОС Windows предлагает множество механизмов синхронизации для использования в программах, выполняющихся в пользовательском режиме, таких как события, семафоры, мьютексы и переменные условий (condition variables). Все эти механизмы доступны программам посредством дескрипторов и функций Win32 API, которые обращаются к системным вызовам от нашего имени.

Платформа .NET Framework обертывает большинство механизмов синхронизации Windows тонкими объектно-ориентированными обертками, такими как классы ManualResetEvent, Mutex, Semaphore и другими. Поверх имеющихся механизмов синхронизации .NET Framework предлагает несколько новых, таких как ReaderWriterLockSlim и Monitor. Мы не будем подробно исследовать каждый из механизмов синхронизации, более подробно они описаны в разделе "Потоки и файлы", а далее займемся более важным для нас делом - изучением характеристик производительности.

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

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

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

Механизмы синхронизации ОС Windows и .NET доступны приложениям в первую очередь в терминах семантики приобретения и освобождения, также известной как семантика сигнального состояния (signal state). Когда механизм синхронизации взводится в сигнальное состояние, он пробуждает поток (или группу потоков), ожидающих освобождения блокировки. В таблице ниже описывается семантика состояния сигнала для некоторых из механизмов синхронизации, доступных в настоящее время приложениям для .NET:

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

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

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

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

Вопросы оптимального использования кеша

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

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

public static int MatrixSumSequential(int[,] matrix)
{
    int sum = 0;
    int rows = matrix.GetUpperBound(0);
    int cols = matrix.GetUpperBound(1);

    for (int i = 0; i < rows; ++i)
    {
        for (int j = 0; j < cols; ++j)
        {
            sum += matrix[i, j];
        }
    }

    return sum;
}

Мы знаем немало способов распараллеливания программ такого рода. Но представьте на мгновение, что y нас нет библиотеки TPL, и нам остается только работать с потоками выполнения напрямую. Ниже приводится попытка реализовать параллельное выполнение, которая, на первый взгляд, позволяет получить выгоды от выполнения в многопроцессорной системе, и даже использует прием агрегирования, чтобы избежать необходимости синхронизировать доступ к общей переменной sum:

public static int MatrixSumParallel(int[,] matrix)
{
    int sum = 0;
    int rows = matrix.GetUpperBound(0);
    int cols = matrix.GetUpperBound(1);

    const int THREADS = 4;
    int chunk = rows / THREADS; // должно делиться нацело

    int[] localSums = new int[THREADS];
    Thread[] threads = new Thread[THREADS];

    for (int i = 0; i < THREADS; ++i)
    {
        int start = chunk * i;
        int end = chunk * (i + 1);

        // воспрепятствовать "подъему" переменной компилятором в lambda-захвате
        int threadNum = i; 

        threads[i] = new Thread(() =>
        {
            for (int row = start; row < end; ++row)
            {
                for (int col = 0; col < cols; ++col)
                {
                    localSums[threadNum] += matrix[row, col];
                }
            }
        });

        threads[i].Start();
    }
	
    foreach (Thread thread in threads)
    {
        thread.Join();
    }

    sum = localSums.Sum();
    return sum;
}

Выполнив каждый из методов 25 раз в системе с процессором Intel Core i7, мы получили следующие результаты для матрицы а 2000 x 2000: среднее время выполнения последовательного метода составило 325 мсек, а параллельного метода 935 мсек, в три раза медленнее последовательной версии!

Понятно, что это совершенно неприемлемо, но почему так получилось? Эта ситуация не может служить еще одним примером слишком мелкого дробления задачи, потому что было запущено всего 4 потока. Если предположить, что проблема имеет некоторое отношение к кешу процессора (хотя бы потому, что пример приводится в разделе с названием «Вопросы оптимального использования кеша»), имеет смысл исследовать количество промахов кеша в каждом из двух методов. Профилировщик Visual Studio (с частотой срабатывания 2000 раз в секунду) сообщил о 963 промахах в параллельной версии и только о 659 промахах в последовательной; подавляющее большинство промахов было обнаружено в теле внутреннего цикла, выполняющем чтение элемента матрицы.

И снова, почему? Почему запись в массив localSums порождает промахов больше, чем запись в локальную переменную? Ответ прост: дело в том, что запись в совместно используемый массив вызывает необходимость актуализации строк кеша в других процессорах, что в каждой операции += приводит к промаху кеша.

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

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

На рисунке видно, что процессор 1 записывает значение в localSums[1], а процессор 2 записывает значение в localSums[2]. Так как оба элемента массива находятся в смежных ячейках памяти и попадают в одну строку кеша в кешах обоих процессоров, каждая операция записи вызывает необходимость актуализации кеша другого процессора.

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

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

Я столкнулся с похожей ситуацией в промышленном приложении, которое распределяло задания между двумя потоками, выполняющимися на двух процессорах, с применением общей очереди. После внесения незначительных изменений во внутреннюю структуру полей класса очереди обнаружилось существенное падение производительности (примерно 20%). В ходе скрупулезных исследований выяснилось, что падение производительности было вызвано переупорядочением полей в классе очереди; два поля, запись в которые выполняются разными потоками, оказались слишком близко друг к другу и попали в одну строку кеша. После разнесения полей, производительность очереди восстановилась до приемлемого уровня.