Parallel Framework и предотвращение ложного обмена ⇐ C#

[Anonymous]

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


Это почти гарантированно приведет к ложному обмену данными и, вероятно, будет во много раз медленнее. (благодарность gjvdkamp)


и они были правы, это была смертельная медленная скорость. Тем не менее, я исследовал эту тему и нашел несколько интересных материалов и предложений (только в архиве журнала MSDN, .NET Matters: False Sharing) по борьбе с ней. Если я правильно понимаю, когда потоки обращаются к непрерывной памяти (скажем, к массиву, который, вероятно, поддерживает этот ConcurrentStack), вероятно, происходит ложное совместное использование.



Для кода ниже горизонтальной линейки байты:

Код: Выделить всё

struct Bytes {
public byte A; public byte B; public byte C; public byte D;
public byte E; public byte F; public byte G; public byte H;
}

Для собственного тестирования я хотел получить параллельную версию, работающую по-настоящему быстрее, поэтому я создал простой пример на основе исходного кода. 6 в качестве ограничений[0] был ленивым выбором с моей стороны — у моего компьютера 6 ядер.

Блок одного потока Среднее время выполнения: 10s0059ms

Код: Выделить всё

  var data = new List();
var limits = new byte[] { 6, 16, 16, 16, 32, 8, 8, 8 };

for (byte a = 0; a < limits[0]; a++)
for (byte b = 0; b < limits[1]; b++)
for (byte c = 0; c < limits[2]; c++)
for (byte d = 0; d < limits[3]; d++)
for (byte e = 0; e < limits[4]; e++)
for (byte f = 0; f < limits[5]; f++)
for (byte g = 0; g < limits[6]; g++)
for (byte h = 0; h < limits[7]; h++)
data.Add(new Bytes {
A = a, B = b, C = c, D = d,
E = e, F = f, G = g, H = h
});

Параллелизованный, плохая реализация Среднее время выполнения: 81 с729 мс, ~ 8700 конфликтов

Код: Выделить всё

  var data = new ConcurrentStack();
var limits = new byte[] { 6, 16, 16, 16, 32, 8, 8, 8 };

Parallel.For(0, limits[0], (a) => {
for (byte b = 0; b < limits[1]; b++)
for (byte c = 0; c < limits[2]; c++)
for (byte d = 0; d < limits[3]; d++)
for (byte e = 0; e < limits[4]; e++)
for (byte f = 0; f < limits[5]; f++)
for (byte g = 0; g < limits[6]; g++)
for (byte h = 0; h < limits[7]; h++)
data.Push(new Bytes {
A = (byte)a,B = b,C = c,D = d,
E = e,F = f,G = g,H = h
});
});

Параллелизованный, ?? реализация Среднее время выполнения: 5 с833 мс, 92 конфликта

Код: Выделить всё

  var data = new ConcurrentStack[*]>();
var limits = new byte[] { 6, 16, 16, 16, 32, 8, 8, 8 };

Parallel.For (0, limits[0], () => new List(),
(a, loop, localList) => {
for (byte b = 0; b < limits[1]; b++)
for (byte c = 0; c < limits[2]; c++)
for (byte d = 0; d < limits[3]; d++)
for (byte e = 0; e < limits[4]; e++)
for (byte f = 0; f < limits[5]; f++)
for (byte g = 0; g < limits[6]; g++)
for (byte h = 0; h < limits[7]; h++)
localList.Add(new Bytes {
A = (byte)a, B = b, C = c, D = d,
E = e, F = f, G = g, H = h
});
return localList;
}, x => {
data.Push(x);
});

Я рад, что получил реализацию, которая быстрее однопоточной версии. Я ожидал результата ближе к 10 с/6 или около 1,6 секунды, но это, вероятно, наивное ожидание.

Мой вопрос: для параллельной реализации, которая на самом деле быстрее, чем однопоточная версия, существуют ли дополнительные оптимизации, которые можно было бы применить к этой операции?< /strong> Меня интересуют оптимизации, связанные с распараллеливанием, а не улучшения алгоритма, используемого для вычисления значений. В частности:

• Я знаю об оптимизации для хранения и заполнения в виде структуры вместо byte[], но это не связано с распараллеливанием (или нет?)
• Я знаю, что желаемое значение может быть лениво вычислено с помощью сумматора с пульсирующим переносом, но то же самое, что и оптимизация структуры .

Подробнее здесь: https://stackoverflow.com/questions/298 ... se-sharing