Разделение итераций цикла между потоками

Question

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

for (int i1 = 0; i1 < N; i1++)
  for (int i2 = 0; i2 < N; i2++)
    for (int i3 = 0; i3 < N; i3++)
      for (int i4 = 0; i4 < N; i4++)
        histogram[bin_index(i1, i2, i3, i4)] += 1; // see bottom of question

Это работало нормально, Ядда Ядда Ядда, получились прекрасные графики ;-) Но потом я подумал, у меня на компьютере 2 ядра, почему бы не сделать эту программу многопоточной, чтобы я мог запустить ее вдвое быстрее?

Теперь, мои циклы, скажем, около миллиарда вычислений, и мне нужно как-то разделить их между потоками. Я полагаю, что должен сгруппировать вычисления в «задачи» - скажем, каждая итерация самого внешнего цикла - задача - и передать задачи потокам. Я рассмотрел

• просто дает потоку #n все итерации самого внешнего цикла, где i1 % nthreads == n - по существу, предопределяя, какие задачи и в какие потоки идут
• пытается установить некоторую переменную, защищенную мьютексом, которая содержит параметр (ы) (в данном случае i1) следующей задачи, которая должна быть выполнена - динамическое назначение задач потокам

Какие есть причины выбирать один подход перед другим? Или другой подход, о котором я не думал? Это вообще имеет значение?

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

EDIT : в этом случае bin_index - это детерминированная функция, которая ничего не меняет, кроме своих собственных локальных переменных. Примерно так:

int bin_index(int i1, int i2, int i3, int i4) {
    // w, d, h are constant floats
    float x1 = i1 * w / N,  x2 = i2 * w / N, y1 = i3 * d / N, y2 = i4 * d / N;
    float l = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) + h * h);
    float th = acos(h / l);
    // th_max is a constant float (previously computed as a function of w, d, h)
    return (int)(th / th_max);
}

(хотя я ценю все комментарии, даже те, которые не относятся к детерминированному bin_index)

Answer 1

Если вы никогда не кодировали многопоточное приложение, я начну с OpenMP:

• библиотека теперь включена в gcc по умолчанию
• это очень легко использовать

В вашем примере вам просто нужно добавить эту прагму:

#pragma omp parallel shared(histogram)
{
for (int i1 = 0; i1 < N; i1++)
  for (int i2 = 0; i2 < N; i2++)
    for (int i3 = 0; i3 < N; i3++)
      for (int i4 = 0; i4 < N; i4++)
        histogram[bin_index(i1, i2, i3, i4)] += 1;
}

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

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

Answer 2

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

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

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

Кроме того, «гистограмма [bin_index (i1, i2, i3, i4)] + = 1» может быть прервана другим потоком, что приведет к неверному результату (если присвоение извлекает значение, увеличивает его и сохраняет полученный значение в массиве). Вы можете ввести локальную гистограмму для каждого потока и объединить результаты в одну гистограмму после завершения всех потоков. Вы также можете убедиться, что только один поток изменяет гистограмму одновременно, но это может привести к тому, что потоки будут блокировать друг друга большую часть времени.

Answer 3

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

Возможно, вы также можете использовать библиотеку Intel Thread Building Blocks .

Answer 4

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

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

Answer 5

Я бы сделал что-то вроде этого:

void HistogramThread(int i1, Action<int[]> HandleResults)
{
    int[] histogram = new int[HistogramSize];

    for (int i2 = 0; i2 < N; i2++)
       for (int i3 = 0; i3 < N; i3++)
          for (int i4 = 0; i4 < N; i4++)
             histogram[bin_index(i1, i2, i3, i4)] += 1;

    HandleResults(histogram);
}

int[] CalculateHistogram()
{
    int[] histogram = new int[HistogramSize];

    ThreadPool pool; // I don't know syntax off the top of my head
    for (int i1=0; i1<N; i1++)
    {
       pool.AddNewThread(HistogramThread, i1, delegate(int[] h)
       {
           lock (histogram)
           {
               for (int i=0; i<HistogramSize; i++)
                   histogram[i] += h[i];
           }
       });
    }
    pool.WaitForAllThreadsToFinish();

    return histogram;
}

Таким образом, вам не нужно делиться памятью до конца.

Answer 6

Я согласен с Sharptooth, что ваш первый подход кажется единственно вероятным.

Ваше однопоточное приложение постоянно присваивается памяти. Чтобы получить какое-либо ускорение, ваши несколько потоков должны также постоянно назначаться памяти. Если за один раз назначается только один поток, вы вообще не получите ускорения. Так что, если ваши задания будут защищены, все упражнение будет провалено.

Это был бы опасный подход, поскольку вы назначаете общую память без охраны. Но, похоже, опасность того стоит (если имеет значение ускорение х2). Если вы можете быть уверены, что все значения bin_index (i1, i2, i3, i4) отличаются в вашем подразделении цикла, то это должно работать, так как назначение массива будет в разных местах в вашей общей памяти. Тем не менее, всегда нужно внимательно смотреть на такие подходы.

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

Edit:

Глядя на ваш bin_index (i1, i2, i3, i4), я подозреваю, что ваш процесс не может быть распараллелен без значительных усилий.

Единственный способ разделить работу вычислений в вашем цикле, опять же, быть уверенным, что ваши потоки получат доступ к тем же областям в памяти. Однако, похоже, что bin_index (i1, i2, i3, i4), скорее всего, будет часто повторять значения. Вы можете разделить итерацию на условия, где bin_index выше, чем отсечка, и где она ниже, чем отсечение. Или вы можете разделить его произвольно и посмотреть, будет ли инкремент реализован атомарно. Но любой сложный подход к многопоточности вряд ли обеспечит улучшение, если у вас есть только два ядра для работы с ними.

Answer 7

Если вы хотите написать многопоточный код обработки чисел (и вы собираетесь делать его в будущем), я бы посоветовал вам взглянуть на использование функционального языка, такого как OCaml или Haskell.

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

Answer 8

Если вы когда-либо делаете это в .NET, используйте Параллельные расширения .