BU/CLA CS-551

Parallel Computing: Models, Languages, and Architectures

Finding Prime Numbers using C-LINDA

The following program is proposed to compute prime numbers. Explain how it works by describing the various processes involved and how they communicate and synchronize through the tupple space. Suggest an optimized version of this program. 


#include  
#include "sr_linda.h" 
 
#define MAXVAL 1000

/* In the following program the "linda_eval_functions" is a special 
   data structure that is used by the Linda compiler to identify the
   various processes that may be invoked using the "eval" operation. 
   In this program there is only one such function "primes".

   The function call "linda_init()" is used to initialize the tuple
   space and the necessary Linda mechanisms. 

   Notice that the first argument to the "in", "out" and "eval"
   operations is a template (similar to that used with C printf() and
   scanf()). This is slightly different from the notation introduced
   in class. 
*/

main(argc,argv) 
int argc; 
char **argv; 
{ 
    int primes(); 
    int last,i,ok;
    struct linda_eval_table linda_eval_functions[2];
 
    linda_eval_functions[0].ptr = primes;
    strcpy(linda_eval_functions[0].name,"primes");
    linda_eval_functions[1].ptr = NULL;

    linda_init(&argc,argv,linda_eval_functions);

    for (i=2; i < MAXVAL; i++) 
    { 
       out("%s%d","primeargs",i); 
       eval("%s","primes"); 
    } 
 
    for (i=2; i < MAXVAL; i++) 
    { 
        rd("%s%d?d","primes",i,&ok); 
        if (ok == 1)  
            last = i; 
    } 

    printf("greatest prime is %d\n",last); 

    linda_end(); 
} 


int primes() 
{ 
    int me,i,limit,ok; 
    double sqrt(); 
    in("%s?d","primeargs",&me); 
    limit = sqrt((double) me) + 1; 
    for (i=2; i < limit; i++) 
    { 
        rd("%s%d?d","primes",i,&ok); 
        if (ok && (me%i == 0)) 
        { 
           out("%s%d%d","primes",me,0); 
           return(0); 
        } 
     } 
   
     p4_dprintf("slave found prime = %d\n",me); 
     out("%s%d%d","primes",me,1); 
     return(0); 
}
This document has been prepared by Professor Azer Bestavros <best@cs.bu.edu> as the WWW Home Page for CS-551, which is part of the NSF-funded undergraduate curriculum on parallel computing at BU.

Date of last update: May 22, 1994.