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

Question

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

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.

Answer 1

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

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

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

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

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

Answer 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);