c - segmentation fault while using pthread library -
i newbie threading , trying change sequential program of travelling salesman problem (dynamic programming) parallel program using threading in c.
#include <stdio.h> #include <limits.h> #define size 10 //maximum 10 cities #define min(a,b) (a > b ? b : a) #define sizepow 1024 // 2^10 //space complexity: o(n * 2^n) //time complexity: o(n^2 * 2^n) int n; npow; int g[size][sizepow]; int p[size][sizepow]; int adj[size][size]; int compute(int start, int set) { int masked, mask, temp, i; int result = int_max; //result stores minimum if (g[start][set] != -1) //memoization dp top-down,check repeated subproblem return g[start][set]; (i = 0; < n; i++) { //npow-1 because exclude "home" vertex our set mask = (npow - 1) - (1 << i); //remove ith vertex set masked = set & mask; if (masked != set) { //in case same set generated(because ith vertex not present in set hence same set on removal) eg 12&13=12 temp = adj[start][i] + compute(i, masked); //compute removed set if (temp < result) result = temp, p[start][set] = i; //removing ith vertex gave minimum } } return g[start][set] = result; //return minimum } void getpath(int start, int set) { if (p[start][set] == -1) return; //reached null set int x = p[start][set]; int mask = (npow - 1) - (1 << x); int masked = set & mask; //remove p set printf("%d ", x); getpath(x, masked); } void tsp() { int i, j; //g(i,s) length of shortest path starting @ visiting vertices in s , ending @ 1 (i = 0; < n; i++) (j = 0; j < npow; j++) g[i][j] = p[i][j] = -1; (i = 0; < n; i++) g[i][0] = adj[i][0]; //g(i,nullset)= direct edge between (i,1) int result = compute(0, npow - 2);//npow-2 exclude our "home" vertex printf("tour cost:%d\n", result); printf("tour path:\n0 "); getpath(0, npow - 2); printf("0\n"); } int main(void) { int i, j; printf("enter number of cities\n"); scanf("%d",&n); npow=(int)pow(2, n);//bit number required represent possible sets printf("enter adjacency matrix\n"); for(i = 0; < n; i++) for(j = 0; j < n; j++) scanf("%d", &adj[i][j]); tsp(); return 0; } this sequential program ideone code. here parallel code this
#include <stdio.h> #include <math.h> #include <pthread.h> #include <signal.h> #include <errno.h> #include <unistd.h> #include<limits.h> #define size 10 //maximum 10 cities #define min(a,b) > b ? b:a #define sizepow 1024 // 2^10 struct threadargs { int a, b; int *c; }; //space complexity: o(n * 2^n) //time complexity: o(n^2 * 2^n) int n, npow; int g[size][sizepow]; int p[size][sizepow]; int adj[size][size]; void printmatrix() { int i, j; (i = 0; < 4; i++) { (j = 0; j < 16; j++) { printf("%d ",g[i][j]); printf("\n"); } printf("\n\n"); } void *compute(void *args) { int masked, mask, i, start, set; int result = int_max; //result stores minimum struct threadargs *recvargs = (struct threadargs *) args; start = recvargs->a; set = recvargs->b; int *retval = recvargs->c; if (g[start][set] != -1) { //memoization dp top-down,check repeated subproblem *retval += g[start][set]; return; } printmatrix(); //sleep(1); int temp[n]; (i = 0; < n; i++) temp[i] = int_max; pthread_t threads[n]; struct threadargs arguments[n]; int running_thread_count = 0; (i = 0; < n; i++) threads[i] == -1; (i = 0; < n; i++) { //npow-1 because exclude "home" vertex our set mask= (npow - 1) - (1 << i); //remove ith vertex set masked = set & mask; //printf("hello world"); if (masked != set)//in case same set generated(because ith vertex not present in set hence same set on removal) eg 12&13=12 { temp[i] = adj[start][i]; arguments[i].a = i; arguments[i].b = masked; arguments[i].c = &temp[i]; pthread_create(&threads[i], null, compute, (void *)&arguments[i] ); running_thread_count++; } } (i = 0; < n; i++) { if (pthread_kill(threads[i], 0) != esrch) pthread_join(threads[i], null); } int ith = 0; result = temp[0]; (i = 1; < n; i++) { if(temp[i] < result) { result = temp[i]; ith = i; } } p[start][set] = ith; if (result != int_max) g[start][set] = result; //return minimum *retval += g[start][set]; } void getpath(int start,int set) { if (p[start][set] == -1) return; //reached null set int x = p[start][set]; int mask= (npow - 1) - (1 << x); int masked = set & mask;//remove p set printf("%d ",x); getpath(x, masked); } void tsp() { int i, j; //g(i,s) length of shortest path starting @ visiting vertices in s , ending @ 1 for(i=0; < n; i++) for( j = 0; j < npow; j++) g[i][j] = p[i][j] = -1; (i = 0; < n; i++) g[i][0] = adj[i][0]; //g(i,nullset)= direct edge between (i,1) int result; struct threadargs arguments; arguments.a = 0; arguments.b = npow-2; arguments.c = &result; compute((void *) &arguments);//npow-2 exclude our "home" vertex printf("tour cost:%d\n",result); printf("tour path:\n0 "); getpath(0,npow-2); printf("0\n"); } int main(void) { int i, j; printf("enter number of cities\n"); scanf("%d", &n); npow=(int)pow(2, n);//bit number required represent possible sets printf("enter adjacency matrix\n"); (i = 0; < n; i++) (j = 0; j < n; j++) scanf("%d", &adj[i][j]); tsp(); return 0; } but getting segmentation fault while trying execute code. following output of gdb
program received signal sigsegv, segmentation fault. 0x00007ffff78bf63e in pthread_join (threadid=4196128, thread_return=0x0) @ pthread_join.c:85 85 pthread_join.c: no such file or directory. (gdb) backtrace #0 0x00007ffff78bf63e in pthread_join (threadid=4196128, thread_return=0x0) @ pthread_join.c:85 #1 0x0000000000400b36 in compute (args=0x7fffffffde90) @ tsp3.c:69 #2 0x0000000000400db2 in tsp () @ tsp3.c:107 #3 0x0000000000400ec8 in main () @ tsp3.c:120 (gdb) i know not give noticeable performance gain want try this. in advance.
**edit : ** have rectified errors facing new errors.i getting correct answer when program runs if delete line `printmatrix() , segmentation fault. gdb log follows
(gdb) backtrace #0 __pthread_kill (threadid=0, signo=0) @ ../nptl/sysdeps/unix/sysv/linux/pthread_kill.c:42 #1 0x0000000000400c85 in compute (args=0x7ffff74eede0) @ tsp3.c:79 #2 0x00007ffff78be182 in start_thread (arg=0x7ffff64ed700) @ pthread_create.c:312 #3 0x00007ffff75eaefd in clone () @ ../sysdeps/unix/sysv/linux/x86_64/clone.s:111 (gdb) why happening. please explain. in advance.
you creating threads in compare function, , pass compare thread function, that's chaos. maybe exceed available number of threads.
Comments
Post a Comment