Энтони Уильямс - Параллельное программирование на С++ в действии. Практика разработки многопоточных программ

В разделах 8.2.3 и 8.2.4 мы видели, что для улучшения использования кэша и предотвращения ложного разделения лучше, когда поток обращается к данным, находящимся в соседних ячейках, а не разбросанным но всей памяти. Если поток вычисляет множество столбцов, то читать ему придётся все значения из первой матрицы и соответственных столбцов второй матрицы, но писать только в назначенные ему столбцы результирующей матрицы. При том, что матрицы хранятся но строкам, это означает, что мы будем обращаться к N элементам первой строки результирующей матрицы, N элементам второй строки и т.д. ( N — количество обрабатываемых столбцов). Другие потоки будут обращаться к другим элементам строк, поэтому, чтобы минимизировать вероятность ложного разделения, столбцы, вычисляемые каждым потоком, должны быть соседними, тогда будут соседними и N записываемых элементов в каждой строке. Разумеется, если эти N элементов занимают в точности целое число строк кэша, то ложного разделения вообще не будет, потому что каждый поток работает со своим набором строк кэша.

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

А как насчет третьего варианта — вычисления прямоугольных блоков матрицы? Можно рассматривать его как комбинацию распределения но столбцам и по строкам. Поэтому шансы на ложное разделение такие же, как при распределении но столбцам. Если выбрать число столбцов так, чтобы минимизировать эту вероятность, то у распределения по блокам будет преимущество в части чтения — исходную матрицу придётся читать не целиком, а только те столбцы и строки, которые соответствуют назначенному потоку прямоугольному блоку. Рассмотрим конкретный пример умножения двух матриц размерностью 1000×1000. Всего в каждой матрице миллион элементов. При наличии 100 процессоров каждый из них сможет вычислить 10 строк, то есть 10 000 элементов. Однако для их вычисления процессору придётся прочитать всю правую матрицу (миллион элементов) плюс 10 000 элементов из соответственных строк левой матрицы, итого — 1 010 000 элементов. С другой стороны, если каждый процессор вычисляет блок 100×100 (те же 10 000 элементов), то нужно будет прочитать значения из 100 строк левой матрицы (100×1000 = 100 000 элементов) и 100 столбцов правой матрицы (еще 100 000). В итоге мы получаем только 200 000 прочитанных элементов, то есть в пять раз меньше по сравнению с первым случаем. Если читается меньше элементов, то сокращается вероятность отсутствия нужного значения в кэше, а, значит, производительность потенциально возрастает.

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

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

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

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

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

• Попытайтесь минимизировать объем данных, к которым обращается каждый поток.

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

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

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

Схожая проблема возникает для данных, защищенных мьютексом. Предположим, что имеется простой класс, содержащий какие-то элементы данных и защищающий их мьютекс. Для потока, захватывающего мьютекс, было бы идеально, чтобы мьютекс и данные были размещены в памяти рядом. Тогда необходимые ему данные уже находятся в кэше процессора, потому что были загружены вместе с мьютексом, когда поток модифицировал его для захвата. Но есть и оборотная сторона медали: другие потоки, пытающиеся захватить мьютекс, удерживаемый первым потоком, должны будут обратиться к той же памяти. Захват мьютекса обычно реализуется в виде атомарной операции чтения-модификации-записи ячейки памяти, принадлежащей мьютексу, с последующим вызовом ядра ОС, если мьютекс уже захвачен. Операция чтения-модификации-записи вполне может сделать недействительными хранящиеся в кэше данные. С точки зрения мьютекса, это несущественно, так как первый поток все равно не стал бы его трогать, пока не подойдёт время освобождения. Но если мьютекс находится в той же строке кэша, что и данные, которыми оперирует захвативший его поток, то получится, что производительность потока, владеющего мьютексом, надает только потому, что другой поток попытался захватить тот же мьютекс .