Как лучше распараллелить задачу?

#c_sharp #многопоточность

Добрый день!
Есть задача, которую хотелось бы распараллелить.
Имеются функции

y1 = F1(x1, x2, ..., xn),  
y2 = F2(x1, x2, ..., xn)


xi, y1, y2 - вещественные числа;
ОДЗ (область допустимых значений) F1 явл. подмн. ОДЗ F2.  

Задача: перебрать всевозможные наборы (xi), вычислить y1 и y2, зафиксировать (записать
в файл) набор (xi), y1, y2, если |y1 - y2| < e (разница по модулю меньше заданного e).



Выделил следующие функции:
 1. Функция A производит перебор наборов (x1, x2, ..., xn) для y1, является рекурсивной,
не представляю как ее можно привести в другой вид;
Вычисление следующего набора занимает времени меньше чем 0.001 (обычно 0.0002) сек.;
 2. Функция B - вычисление y1, 0.100 - 0.300 сек.;
 3. Функция C - вычисление y2, может быть двух реализаций: 0.100 - 0.200 сек. или
~1-2 сек. - вторую реализацию скорее всего делать не будем.

Вышеописанные измерения только примерные (просто много раз вызывали методы, мерили
при помощи Stopwatch и записывали результат в файл), но описанные диапазоны выдерживают.
Измерения производились на Intel(R) Core(TM) i5 CPU 760  @ 2.80GHz.



Распараллеливание задачи представляю след. образом:
 1. главный поток - выполняет A, результаты складывает в общую для потоков очередь;
 2. функция P - берет очередной набор из очереди, вычисляет y1, y2, сравнивает разницу,
записывает в файл при необходимости;
 3. функцию P запустить в нескольких потоках.



Реализация функций A, B, C уже есть на C#.
С потоками знаком только на WinAPI, прочитал статью на RSDN Работа с потоками в C#.
Есть некоторые представления, про распараллеливание, но хотелось бы добиться максимальной
производительности, т.к. по нашим подсчетам количество всевозможных (xi) больше 10e+9.   

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

UPD
Опечатка: количество всевозможных (xi) больше 10e+9.
    

Ответы

Ответ 1

Почему бы не использовать producer-consumer pattern?

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

Можно сделать так:


Поток №1 (producer) вычисляет последовательность наборов x1, x2, ..., xn, используя
функцию A. Если вычисление можно распараллелить, вместо потока появляется группа потоков.
Результаты складываются в очередь, откуда...
Группа потоков №2 (consumer) получает задания из очереди, выполняет для этого набора
переменных функцию P, которая вычисляет B, C и сравнивает результаты. Если разность
достаточно мала, результат уходит в следующую очередь (для неё текущий поток — producer),
откуда...
Поток №3 читает данные из очереди и записывает их в файл.


Поскольку узким местом, по идее, является вычисление P, количество потоков в группе
№2 следует сделать равным количеству ядер в системе.


Ответ 2

Могу предложить следующий quick-and-dirty вариант с использованием Parallel LINQ.



  
  Вычисление Y1(arguments), Y2(arguments) и дельты между ними имеет смысл  синхронно
производить в конструкторе класса Result. Параллелить их выполнение для заданного набора
аргументов, а затем как-то reduc'ить результаты кажется мне нецелесообразным.
  Если реализация вашей функции A не укладывается в логику Range().Select(), то ее
стоит переписать с использованием yield return new Arguments(...) и подставить вместо
генератора, который приведен в моем примере.
  Обратите внимание на место, в котором вызывается AsParallel().
  



В production варианте, наверно, стоит отделить вычисление результатов от их форматирования
и записи в файл.

var results = Enumerable.Range(0, 1000)
                        .AsParallel()
                        .Select(i => new Arguments(i))
                        .Select(arguments => new Result(arguments))
                        .Where(result => result.Delta < Epsilon)
                        .Select(result => result.ToString());

File.WriteAllLines(path, results);