Параллельная структура и избежание ложного обмена

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

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

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

Для кода ниже горизонтального правила a Bytes:

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 как limits[0] был ленивым выбором с моей стороны - мой компьютер имеет 6 ядер.

Блок с одним потоком Среднее время выполнения: 10 с0059мс

  var data = new List<Bytes>();
  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
    });

Параллельная, плохая реализация. Среднее время выполнения: 81s729ms, ~ 8700.

  var data = new ConcurrentStack<Bytes>();
  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
      });
  });

Параллельно,?? реализация Среднее время выполнения: 5s833ms, 92 утверждения

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

  Parallel.For (0, limits[0], () => new List<Bytes>(), 
    (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 секунды, но это, вероятно, наивное ожидание.

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

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

Ответы

Ответ 1

Во-первых, мое первоначальное предположение относительно Parallel.For() и Parallel.ForEach() было неправильным.

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

При использовании Parallel.For() и Parallel.ForEach() вы не можете просто вставить строку в строку for или foreach. Это не означает, что это не может быть слепым улучшением, но, не рассматривая проблему и не применяя ее, использование их бросает многопоточность на проблему, потому что это может ускорить ее работу.

** Parallel.For() и Parallel.ForEach() имеют перегрузки, которые позволяют создавать локальное состояние для Task, которое они в конечном итоге создают, и запускать выражение до и после каждого выполнения итерации.

Если у вас есть операция, которую вы распараллеливаете с помощью Parallel.For() или Parallel.ForEach(), вероятно, рекомендуется использовать эту перегрузку:

public static ParallelLoopResult For<TLocal>(
    int fromInclusive,
    int toExclusive,
    Func<TLocal> localInit,
    Func<int, ParallelLoopState, TLocal, TLocal> body,
    Action<TLocal> localFinally
)

Например, вызывая For() для суммирования всех целых чисел от 1 до 100,

var total = 0;

Parallel.For(0, 101, () => 0,  // <-- localInit
(i, state, localTotal) => { // <-- body
  localTotal += i;
  return localTotal;
}, localTotal => { <-- localFinally
  Interlocked.Add(ref total, localTotal);
});

Console.WriteLine(total);

localInit должен быть lambda, который инициализирует тип локального состояния, который передается в body и localFinally lambdas. Обратите внимание, что я не рекомендую выполнять суммирование с 1 по 100 с использованием распараллеливания, но просто попробуйте простой пример, чтобы сделать пример коротким.