Как распараллелить маленькую чистую функцию? - PullRequest
Новая
       20

Как распараллелить маленькую чистую функцию?

5 голосов
/ 24 февраля 2009

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

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

Ответы [ 8 ]

3 голосов
/ 24 февраля 2009

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

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

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

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

Возможно, вам потребуется поместить достаточно данных в «предметы», которые вы обрабатываете, чтобы иметь возможность сказать, что с ними делать после того, как вы закончите. Они почти наверняка должны быть объектами, и вы можете захотеть, чтобы они содержали информацию о состоянии.

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

Редактировать: Также посмотрите на некоторые параллельные библиотеки, такие как ThreadPoolExecutor . Легко забыть параллельную библиотеку (как я только что сделал), это, вероятно, именно то, что вы искали (отсюда и акцент)

3 голосов
/ 24 февраля 2009

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

2 голосов
/ 24 февраля 2009

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

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

Я думаю, что следующая самая сложная часть - это описание параллелизма, в частности, вы упоминаете, что эта функция вызывается много раз. Можете ли вы передать это и отделить планирование функции от ее работы? Если вы не можете передать это по конвейеру, это похоже на параллельный цикл, обход дерева или оно более неструктурировано, чем это. В частности, подчиняется Amdahl , если вы не можете перекрыть работу и убедиться, что одновременно запущено несколько экземпляров или что-то еще, вы фактически последовательны, даже если вы чисты. Все, что вы можете сделать, чтобы реорганизовать работу в конвейер, рекурсивный обход дерева (или параллельный цикл) или, если вам нужно более неструктурированную работу с зависимостями explicity между задачами, здесь поможет независимо от используемой библиотеки.

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

Извините, если это не было супер конкретным, но я надеюсь, что это было полезно.

2 голосов
/ 24 февраля 2009

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

void OuterFunction( Thingy inputData[N] )
{
  for ( int i = 0 ; i < N ; ++i )
    InnerFunction( inputData[i] );
}

Мы разрешим вашу проблему (при условии наличия системы очереди заданий): 

void JobFunc( Thingy inputData[], int start, int stop )
{
  for ( int i = start ; i < stop ; ++i )
    InnerFunction( inputData[i] );  
}
void OuterFunction( Thingy inputData[N], int numCores )
{
   int perCore = N / numCores; // assuming N%numCores=0 
                               // (omitting edge case for clarity)
   for ( int c = 0 ; c < numCores ; ++c )
     QueueJob( JobFunc, inputData, c * perCore, (c + 1) * perCore );
}

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

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

Затем рассмотрите возможность SIMD, вы можете векторизовать его для запуска четырех входных точек через один регистр одновременно. С четырьмя ядрами и четырьмя SIMD вы можете теоретически получить ускорение в 16 раз, но это предполагает, что работа, выполняемая InnerFunction, в основном является фиксированной математической функцией, поскольку ветвление имеет тенденцию уничтожать прирост производительности SSE / VMX. 1015 *

1 голос
/ 24 февраля 2009

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

1 голос
/ 24 февраля 2009

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

0 голосов
/ 26 июня 2009

Между вызовами нет зависимости от данных, т.е. ни один вызов не использует результат любого другого вызова.

Это поможет с распараллеливанием, но будьте абсолютно уверены, что функция вообще не имеет побочных эффектов. Если функция обновляет структуру данных, является ли она поточно-ориентированной? Если он выполняет IO, будет ли IO узким местом, если вам удастся распараллелить выполнение функции?

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

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

0 голосов
/ 24 февраля 2009

вы можете вывернуть цикл наизнанку, используя Compare-and-Swap, чтобы получить шаг без атомарной блокировки: 

void OuterFunction()
{
  for(int i = 0; i < N; i++)
    InnerFunction(i);
}

идет к: 

void OuterFunction()
{
   int i = 0, j = 0;

   void Go()
   {
      int k;
      while((k = atomicInc(*i)) < N)
      {
         InnerFunction(k);

         atomicInc(*j);
      }
   }

   for(int t = 0; t < ThreadCount - 1; t++) Thread.Start(&Go);

   Go(); // join in

   while(j < N) Wait(); // let everyone else catch up.
}

Редактировать: мои потоки ржавые, поэтому не компилируются, потому что все имена неверны

...