StackThreads/MP: version 0.77 User's Guide

2.1: An Example

The following program illustrates the use of StackThreads/MP using the "Fibonacci" function.

@ 1  
@ 2  #include <st.h>
@ 3
@ 4  
@ 5  int fib(int n)
@ 6  {
@ 7    if (n < 2) {
@ 8   
@ 9      return 1;
10    } else {
11      int a, b;
12  
13  
14  
15  
16      a = fib(n - 1);
17      b = fib(n - 2);
18      
19      return a + b;
20  
21  
22    }
23  }
24  
25  void pfib(int n, int * r, st_join_counter_t *c)
26  {
27    if (n < 2) {
28      *r = 1;                     /* write the result */
29      st_join_counter_finish(c, 1);/* say I have done */
30    } else {
31      int a, b;
32      st_join_counter_t cc[1];
33      ST_POLLING();               /* check if somebody is asking work 
34                                     and free stack */
35      st_join_counter_init(cc, 2);/* initialize join counter */
36      ST_THREAD_CREATE(pfib(n - 1, &a, cc)); /* fork fib(n-1, ...) */
37      pfib(n - 2, &b, cc);        /* fork fib(n-2, ...) */
38      st_join_counter_wait(cc);   /* wait for child's completion */
39      *r = a + b;                 /* write the result */
40      st_join_counter_finish(c);  /* say I have done */
41      ST_POLLING();               /* check if somebody is asking work 
42                                     and free stack */
43    }
44  }
45  
46  int st_main()
47  {
48    
49    int n = 33;
50    long pfib_time, sfib_time;
51    
52    {
53      long t0, t1, t2, t3;
54      int pr, sr;
55      st_join_counter_t c[1];
56  
57      /* do parallel fib */
58      t0 = st_current_time_ms();
59      st_join_counter_init(c, 1);
60      pfib(n, &pr, c);
61      st_join_counter_wait(c);
62      t1 = st_current_time_ms(); 
63      pfib_time = t1 - t0;
64  
65      /* do sequential fib */
66      t0 = st_current_time_ms();
67      sr = fib(n);
68      t1 = st_current_time_ms();
69      sfib_time = t1 - t0;
70  
71      if (sr != pr) {
72        fprintf(st_errout, "wrong\n");
73        st_stack_trace_and_die();
74      }
75    }
76  
77    printf("pfib: %d ms on %d processors, sfib: %d ms\n", 
78           pfib_time, st_n_toplevel_workers(), sfib_time);
79    return 0;
80  }
81  

fib is a sequential function that computes Nth Fibonacci number. pfib is a parallel version. The algorithm is just to create a thread for the first recursive call (line 36). Before going into details of the program, we summarize some practical points.

1. Any file that uses StackThreads/MP primitives should include <st.h> (line 2).
2. A simple way to build a StackThreads/MP program is to define st_main instead of main. The main function defined in the library processes some command-line arguments that are common to all StackThreads/MP programs (such as -nw), performs necessary setup, and invokes st_main, passing unrecognized command-line arguments in argc, argv, and envp. The return value of st_main becomes the exit status of the program. There is a way to use StackThreads/MP from your own main (see Calling StackThreads/MP Procedure from Sequential Procedure).
3. If you want to maintain a single source which is sometimes compiled with StackThreads/MP and sometimes without it, use STHREADS predefined macro. It is defined iff the program is compiled for StackThreads/MP. (see STGCC and STGPP A Wrapper for GCC for more details).