Algorithms: Sequential, Parallel and Distributed 1-18
master.c
*/
#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>
#include “nqueens.h”
int message[MSG_LEN];
void change_worker_state(int worker, int new_state)
}
void Master(int p)
{
int i;
int *task;
int num_tasks;
MPI_Status status;
Algorithms: Sequential, Parallel and Distributed 1-19
worker_state = (int*)calloc(p, sizeof(int));
for(i=1; i < p; i++)
worker_state[i] = W;
{
int SourceWorker = 0;
MPI_Recv(message, MSG_LEN, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG,
MPI_COMM_WORLD, &status);
SourceWorker = status.MPI_SOURCE;
// extract next unsent initial task tasknext
change_worker_state(SourceWorker, W);
MPI_Bsend((void*)(task+cur_task*MSG_LEN), MSG_LEN, MPI_INT,
SourceWorker, T, MPI_COMM_WORLD);
cur_task++;
}
else
{
{
j++;
}
*message = SourceWorker;
change_worker_state(SourceWorker, S);
MPI_Bsend(message, MSG_LEN, MPI_INT, j, H, MPI_COMM_WORLD);
}
else
{
change_worker_state(SourceWorker, I);
}
}
break;
Algorithms: Sequential, Parallel and Distributed 1-20
j++;
}
*message = Helper;
MPI_Bsend(message, MSG_LEN, MPI_INT, j, H, MPI_COMM_WORLD);
}
else
{
change_worker_state(Helper, I);
}
}
break;
{
j++;
}
change_worker_state(j, S);
*message = j;
MPI_Bsend(message, MSG_LEN, MPI_INT, SourceWorker, H,
MPI_COMM_WORLD);
}
break;
case S: // informs the master about a solution found
{
// message
int *update_message;
Algorithms: Sequential, Parallel and Distributed 1-21
}
}
};
break;
} // switch
worker.c
/*
* nQueens problem
* worker.c
* – general framework
*
* MPI Version – Master/Worker paradigm
*
void Worker(int myid, int p)
{
int j = myid, flag;
bool idle, finished, completed;
MPI_Status status;
int message[MSG_LEN];
Algorithms: Sequential, Parallel and Distributed 1-22
{
if ( ! idle )
{
ComputeCycle(&completed, &solution_found, solution);
if (completed)
{
idle = true;
MPI_Bsend(nullmessage, MSG_LEN, MPI_INT, 0, I, MPI_COMM_WORLD);
//report idle
}
if (solution_found)
{
MPI_Bsend(solution, MSG_LEN, MPI_INT, 0, S, MPI_COMM_WORLD); //report
Algorithms: Sequential, Parallel and Distributed 1-23
}
}
break;
case U: //global information
{
int *updatemessage = message;
Update(updatemessage); //use global update info
if (2*j < p)
{
MPI_Bsend(updatemessage, MSG_LEN, MPI_INT, 2*j+1, U,
MPI_COMM_WORLD); //broadcast update
}
}
break;
case F: //the finished message
finished = true;
if (2*j < p)
}
if (j == p-1)
{
MPI_Bsend(NULL, 0, MPI_INT, 0, F, MPI_COMM_WORLD); //broadcast of
finished message
}
break;
Algorithms: Sequential, Parallel and Distributed 1-24
nqueens.h
/*
* nQueens problem
* nqueens.c
*
* MPI Version – Master/Worker paradigm
*
*/
#define n 8
#define MSG_LEN (n*n+n)
#ifndef bool
#define bool int
#define false 0
#define true 1
enum {
W = 0,
T = 1,
I = 2,
S = 3,
Algorithms: Sequential, Parallel and Distributed 1-25
nqueens.c
/*
* nQueens problem
* nqueens.c
*
* MPI Version – Master/Worker paradigm
*
*/
int k = 0;
int btLevel = 0;
int btLevelShift = 0;
int X[n]; // current path
int _H[MSG_LEN]; // for helper
int Board[n][n];
int Diag1[2*n – 2];
int Diag2[2*n – 2];
int Vert[n]; //integer arrays initialized to 0s
int solutions=0;
Algorithms: Sequential, Parallel and Distributed 1-26
int IsSafePos(int x, int y)
{
if (Board[x][y] == 0 ← Vert[y] == 0 ← Diag1[x – y + n – 2] == 0
← Diag2[x + y – 1] == 0) //place queen
return 1;
else
return 0;
}
int PathLen = *message;
int *P = message+1;
int i;
backtrack=0;
for(i = 0; i<PathLen; i++)
}
}
X[PathLen] = 0;
btLevel = PathLen;
int *SplitWork()
{
int i;
int *H;
Algorithms: Sequential, Parallel and Distributed 1-27
while ((X[i] == n-1 || (i==btLevel ← btLevelShift == n-1))
← i < k)
{
H[i] = X[i];
i = i + 1;
} //endwhile
if (n-i < rt)
{
if (btLevelShift == n-1) {
assert(i==k);
// if we are forced to go one beyond the current position
// i==k => need to go further one level with k
if (IsSafePos(k, X[k])) {
}
};
btLevelShift++;
H[i] = btLevelShift;
Algorithms: Sequential, Parallel and Distributed 1-28
H—;
H[0] = btLevel+1;
return H;
}
// setup work found a conflict
if (backtrack) {
*completed = true; //finished assigned work
return;
}
{
iterations = iterations + 1;
do
{
if (X[k] == n) // backtrack
{
X[k] = 0;
k = k – 1;
if (k < btLevel) break;
SetPos(k, X[k], 0);
assert(k>btLevel || X[k] <= btLevelShift);
Algorithms: Sequential, Parallel and Distributed 1-29
if (k==btLevel) {
btLevelShift++;
X[k] = btLevelShift;
} else {
X[k] = X[k] + 1;
}
}
else // not in last row
{
k = k + 1; // go to next row in board
}
}
else // continue looking for place for queen in row k
{
assert(k>btLevel || X[k] <= btLevelShift);
exit(1);
}
int cur_tasks=1;
(*tasks)[0*MSG_LEN]=0;
while(cur_tasks < p) {
// extend all tasks by n
}
}
*num_tasks = cur_tasks;
}
void PrintBoard(int *Board, int nn)
{
int i,j;
Algorithms: Sequential, Parallel and Distributed 1-31
fprintf(stderr, “+”);
for(j=0;j<nn;j++)
{
fprintf(stderr, “-+”);
}
fprintf(stderr, “\n”);
}
fprintf(stderr, “%d: -^^^ Solution number %d ^^^-“, id, ++solutions);
for(i=0;i<nn;i++) {
}
18.25
/*
* Sieves of Eratosthenes
*
* MPI Version
*
* non-optimized
*
Algorithms: Sequential, Parallel and Distributed 1-32
*/
{
previous_prime++;
while(X[previous_prime]==1) previous_prime++;
if (X[previous_prime]==2) return 0; // no more primes here
return range_start+previous_prime;
}
void flag_multiples(int prime)
{
int active_p;
ret = MPI_Init (&argc, &argv);
if (ret)
{
printf (“Error: %d\n”, ret);
Algorithms: Sequential, Parallel and Distributed 1-33
range_start = myid*n/p;
range_len = n/p;
if (range_start+previous_prime+1==0) previous_prime++; // skip 0
if (range_start+previous_prime+1==1) previous_prime++; // skip 1
X = calloc(n/p+2, sizeof(unsigned char));
active_p = active_p + 1;
MPI_Bcast(&active_p, 1, MPI_INT, active_p-1, MPI_COMM_WORLD);
} else {
int next_prime;
Algorithms: Sequential, Parallel and Distributed 1-34
}