_PARALLEL C EXTENSIONS_
by Barr E. Bauer

[LISTING ONE]

/* Loop parallelism sum reduction critical block within loop nest
 * B. E. Bauer 1992 -- compiled using the following on the IRIS:
 *     parallel: cc -O2 -o example1p -mp example1.c
 *     serial: cc -O2 -o example1 example1.c  */
#include <stdio.h>
#define MAX 1536
double a[MAX][MAX], b[MAX][MAX];
main()
{
    int i, j, k, k1;
    double sum=0.0, temp;
    /* shared arrays filled; values not important, just order */
    for (i=0; i<MAX; i++) { 
        for (j=0; j<MAX; j++) {
            a[i][j] = (double)i;
            b[i][j] = (double)j;
        }
    }     
    k1 = 256; /* inner loop delay factor */
    /* start of parallel region */
    #pragma parallel shared(a,b,sum) local(i,j,k,temp) byvalue(k1)
    {
        /* pfor block */
        #pragma pfor iterate(i=0; MAX; 1)
            for (i=0; i<MAX; i++) {
                for (j=0; j<MAX; j++) {
                    temp = a[i][j]-b[i][j];
                    for (k=0; k<k1; k++) /* lengthen execution time */
                        temp += 0.01;
                    #pragma critical
                    {
                        sum += temp;  /* summation in inner loop */
                    }
                }
            } 
    }
    printf("\nDone! sum = %24.15f\n", sum);
}


[LISTING TWO]

/* Loop parallelism sum reduction critical block moved into local code
 * B. E. Bauer 1992 -- compiled using the following on the IRIS:
 *     parallel: cc -O2 -o example2p -mp example2.c
 *     serial: cc -O2 -o example2 example2.c  */

#include <stdio.h>
#define MAX 1536
double a[MAX][MAX], b[MAX][MAX];
main()
{
    int i, j, k, k1;
    double sum=0.0, temp, st;   /* st = local code subtotal */
    /* shared arrays filled; values not important, just order */
    for (i=0; i<MAX; i++) { 
        for (j=0; j<MAX; j++) {
            a[i][j] = (double)i;
            b[i][j] = (double)j;
        }
    }     
    k1 = 256; /* inner loop delay factor */
    /* start of parallel region */
    #pragma parallel shared(a,b,sum) local(i,j,k,temp,st) byvalue(k1)
    {
        st = 0.0;   /* st initialized in each thread */
        /* pfor block */
        #pragma pfor iterate(i=0; MAX; 1)
            for (i=0; i<MAX; i++) {
                for (j=0; j<MAX; j++) {
                    temp = a[i][j]-b[i][j];
                    for (k=0; k<k1; k++) /* lengthens execution time */
                        temp += 0.01;
                    st += temp;
                }
            } 
        /* local code grand summation */
        #pragma critical
        {
            sum += st;
        }
    }
    printf("\nDone! sum = %24.15f\n", sum);
}


[LISTING THREE]

/* Block parallelism, producer-consumer problem
 * B. E. Bauer 1992 -- Taken from "Practical Parallel Programming" pp 214-225
 * (C) 1992 Academic Press, Inc. All Rights Reserved. Used with permission. */
 
#include <stdio.h> 
#define MAXCONSUMERS 3
#define MAXPRODUCTS 10000
#define STOP_TOKEN -1
#define NULL_ITEM (node_t *)NULL 
/* the product is defined here */ 
struct node  
{ 
    int productid; 
    struct node *next; 
}; 
typedef struct node node_t;  /* the typedef is convenient */ 
node_t *root = NULL_ITEM;  /* linked list root */ 
int max_depth = 0; 
/* ----- create a new "product" -------------------------------- */ 
node_t *make_product(node_t *item, int prodid) 
{ 
    item = (node_t *)malloc(sizeof(node_t)); 
    if (item != NULL_ITEM) { 
        item->productid = prodid;
      item->next = NULL_ITEM; 
    } 
    else  
      printf("problems with production, boss...\n"); 
      return (item); 
} 
/* ----- add a "product" to the end of the list ---------------- */ 
node_t *ship_product(node_t *new) 
{
    int cur_depth = 0;
    node_t *list = root;
 
    if (root == NULL_ITEM) 
        root = new;
    else 
    {
        while (list->next != NULL_ITEM)
        {
            list = list->next;
            cur_depth++;
        }
        cur_depth++;
        list->next = new;
    }
    if (cur_depth > max_depth)
        max_depth = cur_depth;
} 
/* ----- pop the product off the beginning of the list --------- */
node_t *receive_product()
{
    node_t *item = root;
    if (root != NULL_ITEM)
        root = root->next;
    return(item);
}
/* ----- consume the product by freeing its memory ------------- */
void consume_product(node_t *item)
{
    if (item != NULL_ITEM)
        free (item);
}
/* ----- the producer ------------------------------------------ */ 
void producer(int cnt) 
{ 
    node_t *temp; 
    int i;
    /* make "products" cnt times (limits simulation) */ 
    for (i=0; i<=cnt; i++)
    { 
        if ((temp = make_product(temp,i)) == NULL_ITEM) 
            break; 
        #pragma critical 
        {
            ship_product(temp); 
        }    
    } 
    /* load on stop tokens */ 
    for (i=0; i<MAXCONSUMERS; i++) 
    { 
        if ((temp = make_product(temp, STOP_TOKEN)) == NULL_ITEM) 
            break; 
        #pragma critical 
        {
            ship_product(temp); 
        }         
    } 
    printf("producer calls it quits\n"); 
} 
/* ----- the consumer (created 3 times) ------------------------ */ 
long consumer(int myid) 
{ 
    /* local variables */ 
    int consuming = 1, j;
    long consumed = 0;    /* count of "products" */ 
    node_t *item;
    double temp;
    printf("consumer %d starts the shopping day\n", myid);
    while (consuming)     /* loop until stop token seen */ 
    { 
        for (j=0; j<32000; j++)
            temp *= (double)j;

        #pragma critical 
        {
            item = receive_product();
        }
        if (item != NULL_ITEM)
        {
            if (item->productid != STOP_TOKEN) 
            {
                if (item->productid)
                    ++consumed;
                printf("consumer %d consuming product %d\n", 
                                                     myid, item->productid);
            }
            else
            {
                consuming = 0;
                printf("consumer %d ran out of products\n", myid);
            }
            consume_product(item);
        }
    }
    printf("consumer %d consumed %d products\n", myid, consumed);
    return(consumed); 
} 
main() 
{ 
    long total, sum[MAXCONSUMERS]; 
    int i; 
    printf("business starts with %d products\n",MAXPRODUCTS); 
    #pragma parallel shared(sum)
    { 
        #pragma independent 
        {
            producer(MAXPRODUCTS); /* start producer */
        }
        #pragma independent 
        {
            sum[0] = consumer(1);  /* start consumer 1 */ 
        }     
        #pragma independent 
        {
            sum[1] = consumer(2);  /* start consumer 2 */ 
        }     
        #pragma independent 
        {
            sum[2] = consumer(3);  /* start consumer 3 */ 
        }
    } 
    for (i=0, total = 0L; i<MAXCONSUMERS; i++) 
        total += sum[i];  /* sum up the products consumed by each */ 
    printf("business over, %d products exchanged\n", total); 
    printf("maximum products in list = %d\n", max_depth-MAXCONSUMERS);
} 


Example 1:

(a)

for (sum=i=0; i<max; i++)
    sum += a[i];

(b)


for (i=1; i<max; i++)
    a[i] = b[i] * a[i-1];


Example  2:

(a)

Code Block becomes

#pragma parallel
#pragma shared (arrayvar1, arrayvar2..., grandtotal)
#pragma local (index1, index2, subtotal1,...)
#pragma byvalue(shared_constant1,...)
{
    Code Block
}

or, the equivalent

#pragma parallel shared(list) local(list) byvalue(list)
{
    Code Block
}


(b)

/* strictly local code */
#pragma parallel
#pragma local(i, j)
{
    for (i=sum=0; i<1000; i++)
        sum += i;
    printf("sum = %d\n", sum);
}


Example 3:

for (i=0; i<max; i++)
        b[i] = const*a[i];

becomes

#pragma parallel shared(a,b) local(i) byvalue(max,const)
{
    #pragma pfor iterate(i=0; max; 1)
        for (i=0; i<max; i++)
            b[i] = const*a[i];
}




Example 4:


code block 1
code block 2

becomes

#pragma parallel shared(list) local(list) byvalue(list)
{
    #pragma independent
    {
        code block 1
    }
    #pragma independent
    {
        code block 2
    }
}


Example 5:

(a)

sum = 0.0;
#pragma parallel shared (sum, a) local(i) byvalue(max)
{
    #pragma pfor iterate (i=0; max; 1)
        for (i=0; i<max; i++)
            sum +=  a[i];
}

(b)

sum = 0.0;
#pragma parallel shared (sum, a) local(i) byvalue(max)
{
    #pragma pfor iterate (i=0; max; 1)
        for (i=0; i<max; i++)
            #pragma critical
        {
        sum += a[i];
        }
}