Расщепление рекурсии в более мелких зернах рекурсии

Question

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

Чтобы прояснить, что я имею в виду, небольшой пример (сортировка слиянием):

Вместо выполнения:

...
merge_sort(b, m);
merge_sort(m, e);
merge(b, m, e);  
...

делаем что-то вроде этого:

...
merge_sort_quad(b, m1);
merge_sort_quad(m1 + 1, m2);
merge_sort_quad(m2 + 1, m3);
merge_sort_quad(m3 + 1, e);
merge_quad(b, m1, m2, m3, e);
...

Сравнивая параллельный пример, я не вижу принципиальной разницы в обоих подходах, поскольку они, вероятно, приведут к одному и тому же:

void foo (..) {
    ...
    //using tbb::prallel_invoke() to call functions in parallel
    tbb::parallel_invoke(foo(..), foo(..)); 
    ...
}

void foo_parallel (..) {
    ...
    tbb::parallel_invoke(foo(..), foo(..), foo(..), foo(..));
    ...
}

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

Answer 1

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

Первая рекурсия. Существует логическая рекурсия, где мы разбиваем проблему на повторяющиеся версии, пока они не достигнут некоторой точки, где они становятся тривиальными (классически, факториальными, умножая текущее число на факториал на единицу меньше, пока мы не достигнем 1), и есть функциональная рекурсия, где мы смоделируйте это с помощью вызова самой функции.

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

Теперь, в конкретном виде рекурсии, который мы имеем с сортировкой слиянием, мы увеличиваем число более простых задач, когда разбиваем проблему. Это вместо того, чтобы n! становиться единственной задачей n × (n - 1)!, сортировка слиянием становится двумя задачами слияния двух половин последовательности для слияния, за которыми следует задача объединения результатов.

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

Сортировка, вероятно, будет привязана только к процессору и памяти, и вряд ли будет что-то выиграть после 1 потока на ядро ​​или не более 1 потока на виртуальный процессор, если используется многопоточность.

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

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

Answer 2

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

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