fork download
copy 
  1. // LICENSE : GPL 3, see file LICENSE_GPL-3.txt
  2.  
  3. #include <stdlib.h>
  4. #include <stdio.h>
  5. #include <omp.h>
  6.  
  7. #ifndef N
  8. #define N 5
  9. #endif
  10. #ifndef FS
  11. #define FS 37 
  12. #endif
  13. #define MULTCOUNT 10000000
  14.  
  15. //  The goal of this lab is to demonstrate that unbounded loops such as while
  16. //  loops can be parallelized with the omp task clause
  17. //  There is overhead associated with omp task scheduler and so it is better for 
  18. //  performance for each thread to have significant amount of calculation to perform
  19. //  relative to the overhead of having a mastrer thread running thru the while loop
  20. //  assigning threads
  21. //
  22. //  By varying the #define parameters FS & N
  23. //  we can vary the amount of computation each thread performs
  24.  
  25. //  under the covers, process_work() calculates fibonacci numbers
  26. //  fibonacci was chosen because the amount of time it takes to compute fib(38) 
  27. //  is orders of magintude higher than the time is takes to compute fib(3) for example
  28.  
  29. //  this allows us to simply change a few parameters and quickly see the effect of 
  30. //  omp task scheduling for the linked list exmaple
  31.  
  32. //  small values of FS mean we are computing small fib numbers and this takes little time
  33. //  small values of N mean we are comuting fewer in a sequence of fib numbers
  34. //  this also means that process_work() takes little time
  35. //  small values such as FS=3, N=2 take so little time to compute, that the 
  36. //  overhead of omp task scheduling dominates the execution time
  37. //  so the parallel version runs slower
  38. //
  39. //  larger values for FS & N means that each thread is doing signicicant work
  40. //  and the cost of the omp task scheduler if not as significant
  41. //  in such cases, the parallel version of the code runs several times faster 
  42. //  than the serial version
  43.  
  44. //  to experiment with this overhead, modify the values for FS & N 
  45. //  in the ll.h inlcude file
  46.  
  47.  
  48. struct node {
  49.    int data;
  50.    int fibdata;
  51.    struct node* next;
  52. };
  53.  
  54.  
  55. struct node* init_list(struct node* p);
  56. void processwork(struct node* p); 
  57. int fib(int n); 
  58.  
  59. int fib(int n) 
  60. {
  61.    int x, y;
  62.    if (n < 2) {
  63.       return (n);
  64.    } else {
  65.       x = fib(n - 1);
  66.       y = fib(n - 2);
  67.       return (x + y);
  68.    }
  69. }
  70.  
  71.  
  72. int fibiter(int n)
  73. {
  74.   int u = 0;
  75.   int v = 1;
  76.   int i, t;
  77.   int j;
  78.  
  79.   for (j=0;j<MULTCOUNT;j++) {
  80.     u=0;
  81.     v=1;
  82.     for(i = 2; i <= n; i++)
  83.     {
  84.       t = u + v;
  85.       u = v;
  86.       v = t;
  87.     }
  88.   }
  89.   return v;
  90. }
  91.  
  92. void processwork(struct node* p) 
  93. {
  94.    int n;
  95.    n = p->data;
  96.    p->fibdata = fib(n);
  97. }
  98.  
  99.  
  100. struct node* init_list(struct node* p) {
  101.     int i;
  102.     struct node* head = NULL;
  103.     struct node* temp = NULL;
  104.  
  105.     head = malloc(sizeof(struct node));
  106.     p = head;
  107.     p->data = FS;
  108.     p->fibdata = 0;
  109.     for (i=0; i< N; i++) {
  110.        temp  = malloc(sizeof(struct node));
  111.        p->next = temp;
  112.        p = temp;
  113.        p->data = FS + i + 1;
  114.        p->fibdata = i+1;
  115.     }
  116.     p->next = NULL;
  117.     return head;
  118. }
  119.  
  120.  
  121. int main(int argc, char *argv[]) {
  122.      struct node *q=NULL;
  123.      struct node *temp=NULL;
  124.      struct node *head=NULL;
  125. 	 struct node *p;
  126.  
  127.      printf("Process linked list\n");
  128.  
  129.      q = init_list(q);
  130.      head = q;
  131. 	 p=head;
  132.  
  133. 	 while (p != NULL) {
  134. 		processwork(p);
  135. 		p = p->next;
  136. 	 }
  137.  
  138.      q = head;   //print the values after the computation for validation check
  139.      while (q != NULL) {
  140.         printf("%d : %d\n",q->data, q->fibdata);
  141.         temp = q->next;
  142.         free (q);
  143.         q = temp;
  144.      }  
  145.      free (q);
  146.  
  147.      return 0;
  148. }
  149.  
  150.  
Success #stdin #stdout 2.28s 9432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Process linked list
37 : 24157817
38 : 39088169
39 : 63245986
40 : 102334155
41 : 165580141
42 : 267914296
https://ideone.com/7NphyH
language:
C (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!