"Разпоточить" рекурсию

[Igors]

Добрый день

Навеяно этим http://www.prog.org.ru/topic_26946_0.html, но там мои попытки завязать содержательный разговор не имели успеха   Типа "ну вот есть средства (Concurrent, QThread) - вот ими и пользуйся". Наверное подразумевается что если уж выучил средства по букварю, то все самой получится. Но вот чего-то у меня не выходит Псевдокод задачи

Код

C++ (Qt)
void Merge(int *A, int first, int last)
{
  // что-то делаем с массивом
}
 
void MergeSort(int *A, int first, int last)
{
  MergeSort(A, first, (first+last)/2); //сортировка левой части
  MergeSort(A, (first+last)/2+1, last); //сортировка правой части
  Merge(A, first, last); //слияние двух частей
}
 
void main()
{
  ...
  MergeSort(A, 1, n); 
  ...
}
 

Как же будем "разпоточивать"? Да, и давайте по-взрослому: число созданных потоков не должно превышать число ядер

Спасибо

[Old]

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

[Igors]

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

Ну четыре надо сначала получить. А две - это всего 2 ядра, а сейчас 8 - пройденный этап, да и 16 никого не удивить. Да и даже 2 - как запускать-то? (в смысле куда встроить код запуска).

По поводу смысла: начиная так метров со 100 данных - он появляется очень быстро 

[Old]

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

Раскидать это можно и на 8 ядер. Например, в запускаемый создаём две нитки, внутри себя они создают ещё две рабочих.

[Old]

Добрался до компьютера:

Код

C++ (Qt)
int main()
{
    ...
 
    std::thread th1( std::bind( &MergeSort, A, first, (first+last)/2 ) );
    std::thread th2( std::bind( &MergeSort, A, (first+last)/2+1, last ) );
    th1.join();
    th2.join();
    Merge( A, first, last );
}
 

[Igors]

Да, красиво с bind. Но все-таки это hard-coded для 2 ниток. Да, можно для 4, но все равно решение остается hard-coded. И предлагаю не частить, а послушать что люди скажут. Поэтому беру паузу 

[Old]

Такое легко можно сделать для любого количества ниток. Главное требование, что это количество делилось на 2, но для этого алгоритма это вполне адекватное требование.
Реальных ниток будет больше, на каждую пару +1

[m_ax]

Как же будем "разпоточивать"? Да, и давайте по-взрослому: число созданных потоков не должно превышать число ядер

Спасибо

Эта задача аналогична распараллеливанию transform из этой темы http://www.prog.org.ru/topic_25963_15.html
Где вместо std::transform нужно поставить MergeSort)

[Igors]

Эта задача аналогична распараллеливанию transform из этой темы http://www.prog.org.ru/topic_25963_15.html
Где вместо std::transform нужно поставить MergeSort)

В том-то и дело что нет, в данном случае число задач неизвестно заранее.

Такое легко можно сделать ..

Вам это ничего (никого) не напоминает? "Прошу исполнить"

[Old]

Вам это ничего (никого) не напоминает?

А вы про что/кого?

"Прошу исполнить"

Не вопрос.

[Old]

Ловите:

Код

C++ (Qt)
void sort( int *A, int first, int last, unsigned int numthread )
{
        assert( A );
        assert( first < last );
 
        if( numthread )
        {
                thread th1( bind( &sort, A, first, (first+last)/2, numthread - 1 ) );
                thread th2( bind( &sort, A, (first+last)/2+1, last, numthread - 1 ) );
                th1.join();
                th2.join();
        }
        else
        {
                thread th1( bind( &mergeSort, A, first, (first+last)/2 ) );
                thread th2( bind( &mergeSort, A, (first+last)/2+1, last ) );
                th1.join();
                th2.join();
        }
        merge( A, first, last );
}
 

numthread - это необходимое количество квадратов пар потоков.

Можно сделать красивей, но мне пока лень.

[m_ax]

В том-то и дело что нет, в данном случае число задач неизвестно заранее.

Ааа.. понятненько)

Ну так old уже предложил вариант)
Думаю, что ещё можно эту рекурсию в компил тайме раскрутить.. (через мета шаблонную магию)

[Igors]

Ловите:

Это (может быть) помогло бы девушке сдать лабу, но не более того. Формально да, все нитки запущены, но ведь они толкаются и ждут друг друга. Производительность/КПД такой реализации ужасна.

Да, и UI кто-то всегда должен сопли подтирать, нечего там всем рассиживаться на join.

[Old]

Что за глупости? Никто там не толкается. Опять вас понесло в голословные утверждения про производительность и КПД?
Всю основную работу делает заданное количество ниток рекурсивно. Дополнительные нити ждут их и процессор не едят. Если начнете думать, то и с UI все будет в порядке.

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

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