并行算法
P-FIB(n)
if n ≤ 1
return n
else x = spawn P-FIB(n-1)
y = P-FIB(n-2)
sync
return x+y
Linux C的简单实现
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
void* P_FIB(void* arg){
int n = (int)arg;
int* p = malloc(sizeof(int));
if(n<=1){
*p = n;
return p;
}else{
pthread_t pid;
pthread_create(&pid,NULL,P_FIB,(void*)n-1);
int* y = P_FIB((void*)n-2);
int* x = 0;
int err;
if((err = pthread_join(pid,&x)) != 0){
printf("%s\n",strerror(err));
}
*p = *x + *y;
free(x);
free(y);
return p;
}
}
int main(){
int i;
for(i=0;i<10;i++){
int* res = P_FIB((void*)i);
printf("%d\n",*res);
free(res);
}
}
C++11的简单实现
#include <iostream>
#include <thread>
using namespace std;
void P_FIB(int* res,int n){
if(n <= 1){
*res = n;
}else{
int x(0),y(0);
thread t(P_FIB,&x,n-1);
P_FIB(&y,n-2);
t.join();
*res = x+y;
}
}
int main(){
int i;
for(i=0;i<10;i++){
int res(0);
P_FIB(&res,i);
printf("%d\n",res);
}
}
以上，做法只是对并行算法的实现，实际上对于Fibonacci并不具备可行性，最有效的方式是使用DP。
