## 4.6

Write a parallel variant of Kernighan and Ritchie's classic "hello, world" program [61]. Each process should print a message of the form

hello, world, from process <i> 

where \<i\> is its rank.

## 4.7
Write a parallel program that computes the sum 1 + 2 + ... + p in the
following manner: Each process i assigns the value i + 1 to an integer,
and then the processes perform a sum reduction of these values. Process 0
should print the result of the reduction. As a way of double-checking the
result, process 0 should also compute and print the value p(p + l)/2 .

## 4.8

A prime number is a positive integer evenly divisible by exactly two positive integers: itself and 1. The first five prime numbers are 2, 3, 5, 7, and 11. Sometimes two consecutive odd numbers are both prime. For example, the odd integers following 3, 5, and 11 are all prime numbers. However, the odd integer following 7 is not a prime number. Write a parallel program to determine, for all integers less than 1,000,000, the number of times that two consecutive odd integers are both prime.

### 4.9

The gap between consecutive prime numbers 2 and 3 is only 1, while the gap between consecutive primes 7 and 11 is 4. Write a parallel program to determine, for all integers less than 1,000,000, the largest gap between a pair of consecutive prime numbers.

## 4.12

Simpson's Rule is a better numerical integration algorithm than the rectangle rule because it converges more quickly. Suppose we want to compute $\int_a^bf(x)dx$. We divide the interval $[a. b]$ into $n$ subintervals, where $n$ is even. Let $x$, denote the end of the $i$-th interval, for $1 \leq i \leq n$, and let $x_0$ denote the beginning of the first interval. According to Simpson's Rule:
$$
\int_a^bf(x)dx\approx\frac{1}{3n}\left[f(x_0)-f(x_n)+\sum_{i=1}^{n/2}(4f(x_{2i-1})+2f(x_{2i}))\right]
$$
A C program that uses Simpson's Rule to compute $\pi$ appears in Figure 4.9.

* (a)

Write a parallel program to compute the value of TT using Simpson's Rule: /(.r) =4/( 1 +x-),a = 0,/; = l,and/; = 50.

* (b)

Benchmark your program on various numbers of processors.

**Figure 4.8** A C program to compute the value of $\pi$ using the rectangle rule.

/* This program computes p i using the rectangle rule . */
#define INTERVALS 1000000
int main (int argc, char *argv[] ) {
    double area; /* Area under curve */
    double ysum; /* Sum of rectangl e height s */
    double xi ; /* Midpoint of interva l */
    int i ;
    ysum = 0.0 ;
    for(1=0 ; i < INTERVALS; i++) {
        x i = (1.0/INTERVALS)*(i+0.5);
        ysum += 4.0/(1.0+xi*xi) ;
        )
        area = ysum * (1.0 / INTERVALS);
        print f ("Area i s %13.11f\n", area) ;
        return 0;
    }
}

**Figure 4.9** A C program to compute the value of $\pi$ using Simpson's Rule..

/* This program uses Simpson's Rule t o compute pi . */
#define n 50
double f (int i ) {
    double x;
    x = (double) i / (double) n;
    retur n 4.0 / (1.0 + x * x) ;
}
int main (int argc, char *argv[] ) {
    double area;
    int i ;
    area = f(0 ) - f(n) ;
    f o r ( i = 1; i <= n/2; i++)
    area += 4.0*f(2*i-l ) + 2*f(2*i) ;
    area /= (3.0 * n) ;
    print f ("Approximation of pi : %13.11f\n", area) ;
    return 0;
}

## 5.11

The simplest harmonic progression is
$$
\frac{1}{1}, \frac{1}{2}, \frac{1}{3}, \cdots
$$
Let $S_n=\sum_{i=1}^n 1/i$

* (a) Write a parallel program that computes these sums to arbitrary precision after the decimal point. For example, $S_7$= 2.592857142857, to 12 digits of precision after the decimal point. Process 0 should query the user for the two parameters, n and d, and broadcast these parameters to the other processes. Processes should work together to compute $S_n$ to d digits of precision after the decimal point. After $S_n$, has been computed, process 0 should print its value.
* (b) Benchmark the program computing $S_{1,000,000}$ to $100$ digits of precision, using various numbers of processors.

## 6.8

Assume that the time needed to send an n-byte message is $\lambda+n/\beta$. Write a program implementing the "ping pong" test to determine $\lambda$ (latency) and $\beta$ (bandwidth) on your parallel computer. Design the program to run on exactly two processes. Process 0 records the time and then sends a message to process 1. After process 1 receives the message, it immediately sends it back to process 0. Process 0 receives the message and records the time. The elapsed time divided by 2 is the average message-passing time. Try sending messages multiple times, and experiment with messages of different lengths, to generate enough data points that you can estimate $\lambda$ and $\beta$.

## 6.13

In 1970, Princeton mathematician John Conway invented the game of Life. Life is an example of a cellular automaton. It consists of a rectangular grid of cells. Each cell is in one of two states: alive or dead. The game consists of a number of iterations. During each iteration a dead cell with exactly three neighbors becomes a live cell. A live cell with two or three neighbors stays alive. A live cell with less than two
neighbors or more than three neighbors becomes a dead cell. All cells are updated simultaneously. Figure 6.12 illustrates three iterations of Life for a small grid of cells.


**Figure 6.12 An initial state and three iterations of Conway's game of Life.**

Write a parallel program that reads from a hie an $m \times n$ matrix containing the initial state of the game. It should play the game of Life for $j$ iterations, printing the state of the game once every $k$ iterations, where $j$ and $k$ are command-line arguments.