Блог

У меня проблема с высокой степенью распараллеливаемости. Сотни отдельных проблем должны быть решены с помощью одной и той же функции. Каждая проблема занимает в среднем, возможно, 120 мс (0,12 с) на одном ядре, но есть существенные различия, и некоторые экстремальные и редкие проблемы могут занимать в 10 раз больше времени. Для каждой проблемы требуется память, но она выделяется заранее. Проблемы не требуют дискового ввода-вывода, и они не передают туда и обратно какие-либо переменные после их запуска. Тем не менее, они получают доступ к разным частям (элементам массива) одной и той же глобальной структуры.

У меня есть код на C , основанный на чужом коде, который работает. (Глобальный массив структур не показан.) Он запускает 20 проблем (например), а затем возвращает. Я думаю, 20 достаточно, чтобы выровнять вариабельность на 4 ядрах. Я вижу, что время выполнения уже выравнивается примерно с 10.

Существуют версии Win32 и OpenMP, и они ведут себя почти одинаково с точки зрения времени выполнения. Я запускаю программу в 4-ядерной системе Windows. Я включаю некоторый код OpenMP ниже, поскольку он короче. (Я изменил имена и т.д., Чтобы сделать его более универсальным, и, возможно, я допустил ошибки — он не будет компилироваться автономно.)

Ускорение по сравнению с однопоточной версией выравнивается примерно в 2,3 раза. Таким образом, если для однопоточной обработки требуется 230 секунд, для многопоточной — 100 секунд. Я удивлен, что ускорение не намного ближе к 4, количеству ядер.

Правильно ли я разочарован?

Могу ли я что-нибудь сделать, чтобы приблизиться к моим теоретическим ожиданиям?

 int split_bigtask(Inputs  * inputs, Outputs * results)
{
  for (int k = 0; k < MAXNO; k  )
    results->solved[k].value = 0;

  int res;
  #pragma omp parallel shared(inputs, outputs)
  {
    #pragma omp for schedule(dynamic)
    for (int k = 0; k < inputs->no; k  )
    {
      res = bigtask(inputs->values[k], 
                    outputs->solved[k], 
                    omp_get_thread_num()
                   );
    }
  }
  return TRUE;
}
  

1. Я предполагаю, что внутри не выполняется синхронизация bigtask() (очевидно, но я все равно сначала проверил бы это).
2. Возможно, вы столкнулись с проблемой «грязного кэша»: если вы обрабатываете данные, которые находятся близко друг к другу (например, одну и ту же строку кэша!) из нескольких ядер, каждая манипуляция будет помечать строку кэша как грязную (что означает, что процессору необходимо сообщить об этом всем другим процессорам, что, в свою очередь, снова включает синхронизацию …).
3. вы создаете слишком много потоков (выделение потока — это довольно накладные расходы. Таким образом, создание одного потока для каждого ядра намного эффективнее, чем создание 5 потоков для каждого).

Лично я бы предположил, что у вас случай 2 («Большой глобальный массив»).

Решение проблемы (если это действительно случай 2):

• Запишите результаты в локальный массив, который объединяется в «Большой глобальный массив» основным потоком после окончания работы
• Разделите глобальный массив на несколько меньших массивов (и предоставьте каждому потоку один из этих массивов)
• Убедитесь, что записи в структуре выровнены по границам строк кэша (это немного халтурно, поскольку границы строк кэша могут измениться для будущих процессоров) Возможно, вы захотите попробовать создать локальную копию массива для каждого потока (по крайней мере, для результатов)