Рекурсивный Фиб с нитями, ошибка сегментации?
Любые идеи, почему он отлично работает для значений, таких как 0, 1, 2, 3, 4... и ошибки сегмента для значений, таких как>15? #include #include #include
void *fib(void *fibToFind);
main(){
pthread_t mainthread;
long fibToFind = 15;
long finalFib;
pthread_create(&mainthread,NULL,fib,(void*) fibToFind);
pthread_join(mainthread,(void*)&finalFib);
printf("The number is: %d\n",finalFib);
}
void *fib(void *fibToFind){
long retval;
long newFibToFind = ((long)fibToFind);
long returnMinusOne;
long returnMinustwo;
pthread_t minusone;
pthread_t minustwo;
if(newFibToFind == 0 || newFibToFind == 1)
return newFibToFind;
else{
long newFibToFind1 = ((long)fibToFind) - 1;
long newFibToFind2 = ((long)fibToFind) - 2;
pthread_create(&minusone,NULL,fib,(void*) newFibToFind1);
pthread_create(&minustwo,NULL,fib,(void*) newFibToFind2);
pthread_join(minusone,(void*)&returnMinusOne);
pthread_join(minustwo,(void*)&returnMinustwo);
return returnMinusOne + returnMinustwo;
}
}
3 ответа
Недостаточно памяти (недостаточно места для стеков) или допустимые дескрипторы потоков?
Вы просите очень много потоков, которые требуют много стека / контекста. Windows (и Linux) имеют глупую идею "большого [смежного] стека".
Из документации по pthreads_create: "В Linux/x86-32 размер стека по умолчанию для нового потока составляет 2 мегабайта". Если вы производите 10000 потоков, вам нужно 20 ГБ ОЗУ. Я собрал версию программы OP, и она взорвалась с помощью 3500 (p) потоков в Windows XP64.
Посмотрите эту SO-ветку, чтобы узнать больше о том, почему большие стеки - действительно плохая идея: почему переполнение стека все еще остается проблемой?
Если вы отказываетесь от больших стеков и внедряете параллельный язык с выделением кучи для записей активации (наш PARLANSE - один из них), проблема исчезнет.
Вот первая (последовательная) программа, которую мы написали на PARLANSE:
(define fibonacci_argument 45)
(define fibonacci
(lambda(function natural natural )function
`Given n, computes nth fibonacci number'
(ifthenelse (<= ? 1)
?
(+ (fibonacci (-- ?))
(fibonacci (- ? 2))
)+
)ifthenelse
)lambda
)define
Вот запуск выполнения на i7:
C:\DMS\Domains\PARLANSE\Tools\PerformanceTest>run fibonaccisequential
Starting Sequential Fibonacci(45)...Runtime: 33.752067 seconds
Result: 1134903170
Вот второе, параллельное:
(define coarse_grain_threshold 30) ; technology constant: tune to amortize fork overhead across lots of work
(define parallel_fibonacci
(lambda (function natural natural )function
`Given n, computes nth fibonacci number'
(ifthenelse (<= ? coarse_grain_threshold)
(fibonacci ?)
(let (;; [n natural ] [m natural ] )
(value (|| (= m (parallel_fibonacci (-- ?)) )=
(= n (parallel_fibonacci (- ? 2)) )=
)||
(+ m n)
)value
)let
)ifthenelse
)lambda
)define
Явный параллелизм делает программы намного проще для написания.
Параллельную версию мы тестируем с помощью вызова (parallel_fibonacci 45). Вот выполнение, выполняемое на том же i7 (который, возможно, имеет 8 процессоров, но на самом деле это четыре многопоточных процессора, поэтому на самом деле это не совсем 8 эквивалентных процессоров):
C:\DMS\Domains\PARLANSE\Tools\PerformanceTest>run fibonacciparallelcoarse
Parallel Coarse-grain Fibonacci(45) with cutoff 30...Runtime: 5.511126 seconds
Result: 1134903170
Ускорение около 6+, неплохо для не совсем 8 процессоров. Один из других ответов на этот вопрос - версия pthreads; вычисление Fib(18) заняло "несколько секунд", а для Fib(45) - 5,5 секунды. Это говорит о том, что pthreads - это принципиально плохой способ сделать много мелкого параллелизма, потому что он имеет очень, очень большие накладные расходы. (PARLANSE предназначен для минимизации разветвления).
Вот что произойдет, если вы установите технологическую константу равной нулю (разветвления при каждом вызове fib):
C:\DMS\Domains\PARLANSE\Tools\PerformanceTest>run fibonacciparallel
Starting Parallel Fibonacci(45)...Runtime: 15.578779 seconds
Result: 1134903170
Вы можете видеть, что амортизационная вилка над головой - хорошая идея, даже если у вас есть быстрые вилки.
Fib(45) производит много зерна. Распределение кучи записей активации решает проблему первого порядка OP (тысячи pthreads каждый со стеком 1Mb записывают гигабайты оперативной памяти).
Но есть проблема второго порядка: 2^45 "зерна" PARLANSE сожгут всю вашу память, просто отслеживая зерна, даже если ваш блок управления зерном крошечный. Так что это помогает иметь планировщик, который душит вилы, когда у вас есть "много" (для некоторого определения "много" значительно меньше, чем 2^45) зерен, чтобы предотвратить взрыв параллелизма, затопляющий машину данными отслеживания "зерна" структур. Он должен отвязывать вилки, когда число зерен падает ниже порогового значения, чтобы физические процессоры всегда выполняли много логической параллельной работы.
Я попытался запустить ваш код и натолкнулся на несколько неожиданностей:
printf("The number is: %d\n", finalFib);
В этой строке есть небольшая ошибка: %d средства printf ожидает int, но передается long int, На большинстве платформ это одно и то же или в любом случае будет иметь одинаковое поведение, но педантично говоря (или если вы просто хотите остановить появление предупреждения, что также является очень благородным идеалом), вы должны использовать %ld вместо этого, который будет ожидать long int,
Ваш fib функция, с другой стороны, кажется нефункциональной. Тестируя его на моей машине, он не падает, но дает 1047, который не является числом Фибоначчи. Если присмотреться, кажется, что ваша программа неверна по нескольким аспектам:
void *fib(void *fibToFind)
{
long retval; // retval is never used
long newFibToFind = ((long)fibToFind);
long returnMinusOne; // variable is read but never initialized
long returnMinustwo; // variable is read but never initialized
pthread_t minusone; // variable is never used (?)
pthread_t minustwo; // variable is never used
if(newFibToFind == 0 || newFibToFind == 1)
// you miss a cast here (but you really shouldn't do it this way)
return newFibToFind;
else{
long newFibToFind1 = ((long)fibToFind) - 1; // variable is never used
long newFibToFind2 = ((long)fibToFind) - 2; // variable is never used
// reading undefined variables (and missing a cast)
return returnMinusOne + returnMinustwo;
}
}
Всегда заботьтесь о предупреждениях компилятора: обычно, когда вы его получаете, вы действительно делаете что-то подозрительное.
Возможно, вам следует немного пересмотреть алгоритм: сейчас ваша функция возвращает сумму двух неопределенных значений, следовательно, 1047, которое я получил ранее.
Реализация набора Фибоначчи с использованием рекурсивного алгоритма означает, что вам нужно снова вызвать функцию. Как отмечали другие, это довольно неэффективный способ сделать это, но это легко, поэтому я предполагаю, что все учителя информатики используют его в качестве примера.
Обычный рекурсивный алгоритм выглядит так:
int fibonacci(int iteration)
{
if (iteration == 0 || iteration == 1)
return 1;
return fibonacci(iteration - 1) + fibonacci(iteration - 2);
}
Я не знаю, в какой степени вы должны были использовать потоки - просто запустить алгоритм во вторичном потоке или создать новые потоки для каждого вызова? Давайте предположим, что первое пока что, так как это намного проще.
Приведение целых к указателям и наоборот - плохая практика, потому что если вы попытаетесь взглянуть на вещи на более высоком уровне, они должны сильно отличаться. Целые числа выполняют математические операции, а указатели разрешают адреса памяти. Это работает, потому что они представлены одинаково, но на самом деле, вы не должны этого делать. Вместо этого вы можете заметить, что функция, вызываемая для запуска нового потока, принимает void* Аргумент: мы можем использовать его для передачи как того, где находится ввод, так и того, где будет вывод.
Итак, опираясь на мой предыдущий fibonacci функция, вы можете использовать этот код в качестве основной процедуры потока:
void* fibonacci_offshored(void* pointer)
{
int* pointer_to_number = pointer;
int input = *pointer_to_number;
*pointer_to_number = fibonacci(input);
return NULL;
}
Он ожидает указатель на целое число и получает от него свой ввод, а затем записывает его там. 1 Затем вы бы создали такую тему:
int main()
{
int value = 15;
pthread_t thread;
// on input, value should contain the number of iterations;
// after the end of the function, it will contain the result of
// the fibonacci function
int result = pthread_create(&thread, NULL, fibonacci_offshored, &value);
// error checking is important! try to crash gracefully at the very least
if (result != 0)
{
perror("pthread_create");
return 1;
}
if (pthread_join(thread, NULL)
{
perror("pthread_join");
return 1;
}
// now, value contains the output of the fibonacci function
// (note that value is an int, so just %d is fine)
printf("The value is %d\n", value);
return 0;
}
Если вам нужно вызвать функцию Фибоначчи из новых отдельных потоков (обратите внимание: это не то, что я бы посоветовал, и другие, похоже, со мной согласятся; это просто взорвется за достаточно большое количество итераций), вы сначала нужно объединить fibonacci функция с fibonacci_offshored функция. Это значительно увеличит объем, потому что работать с потоками тяжелее, чем с обычными функциями.
void* threaded_fibonacci(void* pointer)
{
int* pointer_to_number = pointer;
int input = *pointer_to_number;
if (input == 0 || input == 1)
{
*pointer_to_number = 1;
return NULL;
}
// we need one argument per thread
int minus_one_number = input - 1;
int minus_two_number = input - 2;
pthread_t minus_one;
pthread_t minus_two;
// don't forget to check! especially that in a recursive function where the
// recursion set actually grows instead of shrinking, you're bound to fail
// at some point
if (pthread_create(&minus_one, NULL, threaded_fibonacci, &minus_one_number) != 0)
{
perror("pthread_create");
*pointer_to_number = 0;
return NULL;
}
if (pthread_create(&minus_two, NULL, threaded_fibonacci, &minus_two_number) != 0)
{
perror("pthread_create");
*pointer_to_number = 0;
return NULL;
}
if (pthread_join(minus_one, NULL) != 0)
{
perror("pthread_join");
*pointer_to_number = 0;
return NULL;
}
if (pthread_join(minus_two, NULL) != 0)
{
perror("pthread_join");
*pointer_to_number = 0;
return NULL;
}
*pointer_to_number = minus_one_number + minus_two_number;
return NULL;
}
Теперь, когда у вас есть эта громоздкая функция, настройки вашего main Функция будет довольно простой: просто измените ссылку на fibonacci_offshored в threaded_fibonacci,
int main()
{
int value = 15;
pthread_t thread;
int result = pthread_create(&thread, NULL, threaded_fibonacci, &value);
if (result != 0)
{
perror("pthread_create");
return 1;
}
pthread_join(thread, NULL);
printf("The value is %d\n", value);
return 0;
}
Возможно, вам сказали, что потоки ускоряют параллельные процессы, но где-то есть ограничение, когда установка потока обходится дороже, чем его содержимое. Это очень хороший пример такой ситуации: многопоточная версия программы работает намного, намного медленнее, чем непотоковая.
В образовательных целях эта программа исчерпывает потоки на моем компьютере, когда число требуемых итераций равно 18, и для ее запуска требуется несколько секунд. Для сравнения, используя итеративную реализацию, у нас никогда не заканчиваются потоки, и мы получаем наш ответ в течение нескольких миллисекунд. Это также значительно проще. Это было бы отличным примером того, как использование лучшего алгоритма решает многие проблемы.
Кроме того, из любопытства было бы интересно посмотреть, не сработает ли это на вашей машине, и где / как.
1. Обычно вам следует избегать изменения значения переменной между ее значением на входе и ее значением после возврата функции. Например, здесь, на входе, переменная - это количество итераций, которое мы хотим; на выходе это результат функции. Это два совершенно разных значения, и это не очень хорошая практика. Мне не хотелось использовать динамическое распределение для возврата значения через void* возвращаемое значение
Вы не проверяете ошибки - в частности, от pthread_create(), когда pthread_create() терпит неудачу, pthread_t переменная остается неопределенной, а последующая pthread_join() может разбиться
Если вы проверите на наличие ошибок, вы обнаружите, что pthread_create() терпит неудачу. Это потому, что вы пытаетесь сгенерировать почти 2000 потоков - с настройками по умолчанию для этого потребуется 16 ГБ стеков потоков, которые должны быть выделены в одиночку.
Вы должны пересмотреть свой алгоритм, чтобы он не генерировал так много потоков.