/*********************** Master source code
******************/
#include < sys/types.h>
#include < sys/ipc.h>
#include < stdio.h>
#include < stdlib.h>
#include < time.h>
#include "pvm3.h"
#define SLAVENAME "slave"
#define NO_TASK 1
#define NEW_TASK 2
#define SENDING_DATA 3
#define SLAVE_HUNGRY 4
#define SOLUTION 5
#define UPDATE_MIN_COST 6
#define ANY_SLAVE -1
#define ANY_MSG -1
char FileName[40];
int x[29];
int MinCostVector[29];
int costar[29][29];
int VNodes;
int prosize;
int n;
int size;
int mincost;
int BestSlave;
int Msg;
int Pos;
long STime;
long ETime;
time_t ltime;
struct pvmhostinfo *hostp[32];
int mytid; /* my task id */
int tids[32]; /* task ids */
int me, i, nproc, master, msgtype;
int numt, who, nhost, narch;
int NoOfSentTasks, NoOFSolvedTasks;
int vn[32];
float result[100];
FILE *Data;
/******************************/
void PrintTime(TotalTime)
int TotalTime;
{
int Days, Hours, Minutes, Seconds;
double fDays, fHours, fMinutes;
fDays = ((float)TotalTime /(24*60*60));
Days = (int) fDays;
fHours = (fDays - Days) * 24;
Hours = (int)fHours;
fMinutes = (fHours - Hours) * 60;
Minutes = (int)fMinutes;
Seconds = (int) ((fMinutes - Minutes) * 60) ;
printf("\n %d Days :%d Hours:%d Minutes:%d Seconds",Days, Hours, Minutes,Seconds);
}
void fPrintTime(TotalTime)
int TotalTime;
{
int Days, Hours, Minutes, Seconds;
double fDays, fHours, fMinutes;
fDays = ((float)TotalTime /(24*60*60));
Days = (int) fDays;
fHours = (fDays - Days) * 24;
Hours = (int)fHours;
fMinutes = (fHours - Hours) * 60;
Minutes = (int)fMinutes;
Seconds = (int) ((fMinutes - Minutes) * 60) ;
fprintf(Data,"\n %d Days :%d Hours:%d Minutes:%d Seconds",Days, Hours, Minutes,Seconds);
}
void Activate(SlaveId, PlaceNo)
int SlaveId, PlaceNo;
{
int MsgType;
MsgType = NEW_TASK;
pvm_initsend(PvmDataDefault);
pvm_pkint(&MsgType, 1, 1);
pvm_pkint(&PlaceNo, 1, 1);
pvm_pkint(&mincost, 1, 1);
pvm_send(SlaveId,NEW_TASK);
}
/******************************/
void SendSlaves(mincost)
int mincost;
{
int Msg;
Msg=UPDATE_MIN_COST;
pvm_initsend(PvmDataDefault);
pvm_pkint(&Msg, 1, 1);
pvm_pkint(&mincost, 1, 1);
pvm_mcast(tids,nproc,UPDATE_MIN_COST);
}
/******************************/
void ShutDownSlaves()
{
int MsgType;
MsgType = NO_TASK;
pvm_initsend(PvmDataDefault);
pvm_pkint(&MsgType, 1, 1);
pvm_mcast(tids,nproc,NO_TASK);
}
/******************************/
main()
{
int j;
int mcost;
NoOFSolvedTasks = 0;
NoOfSentTasks = 0;
/* enroll in pvm */
mytid = pvm_mytid();
/* Set number of slaves to start */
if( pvm_parent() == PvmNoParent ){
puts("How many slave programs (1-32)?");
scanf("%d", &nproc);
}
else{
pvm_config( &nhost, &narch, hostp );
nproc = nhost;
if( nproc > 32 ) nproc = 32 ;
}
pvm_config( &nhost, &narch, hostp );
printf("\nno of hosts =%d\n",nhost);
/* start up slave tasks */
/*pvm_catchout(stdout);*/
numt=pvm_spawn("/home/hashmawi/pvmproject/slave",(char**)0,0, 0, nproc, tids);
if( numt < nproc ){
printf("Trouble spawning slaves. Aborting. Error codes are:\n");
for( i=numt ; i \n");
STime=time(<ime);
while(NoOFSolvedTasks \n");
ShutDownSlaves();
printf("Data file name = %s\n", FileName);
printf("The chess board size = %d X %d.\n",n,n);
printf("\n# of physical machine(s) added = %d",nhost);
printf("\n# of spawned tasks = %d",nproc);
printf("\nThe minimum cost = %d from slave # %d\n",mincost,who);
printf("The solution vector = (%d",MinCostVector[1]);
for(i=2;i<=n;i++)
printf(", %d", MinCostVector[i]);
printf(" )\n");
printf("The solution took exactly (%d) seconds", ETime-STime);
PrintTime(ETime-STime);
Msg = 7;
i=0;
/*********************************/
Data = http://www.geocities.com/nmntoko/csci/fopen("result.dat","w");
fprintf(Data,"Data file name = %s\n", FileName);
fprintf(Data,"The chess board size = %d X %d.\n",n,n);
fprintf(Data,"\n# of physical machine(s) added = %d",nhost);
fprintf(Data,"\n# of spawned tasks = %d",nproc);
fprintf(Data,"\nThe minimum cost = %d from slave # %d\n",mincost,who);
fprintf(Data,"The solution vector = ( %d",MinCostVector[1]);
for(i=2;i<=n;i++)
fprintf(Data,", %d", MinCostVector[i]);
fprintf(Data," )\n");
fprintf(Data,"The solution took exactly (%d) seconds", ETime-STime);
fPrintTime(ETime-STime);
fclose(Data);
/* Program Finished exit PVM before stopping */
pvm_exit();
}
/*********************** Salve source code ******************/
#include "pvm3.h"
/*************************/
#include < stdio.h>
#include < stdlib.h>
#define NO_TASK 1
#define NEW_TASK 2
#define GETTING_DATA 3
#define SLAVE_HUNGRY 4
#define SOLUTION 5
#define UPDATE_MIN_COST 6
FILE *Data;
int x[29];
int MinVector[29];
int costar[29][29];
int n;
int mincost;
int Msg;
int Pos;
int mytid; /* my task id */
int tids[32]; /* task ids */
int me, i, nproc, master, msgtype;
int NoOfTasks, NoOfSolvedTasks;
int NoVNodes;
int SolNo;
int NoOfAsks;
int GetMinCost(c)
int c;
{
int Msg;
int minc;
if(pvm_nrecv(master, UPDATE_MIN_COST)) {
pvm_upkint(&Msg, 1, 1);
pvm_upkint(&minc, 1, 1);
}
else minc = c;
return minc;
}
int CheapPlace(k,i,c)
int k,i,c;
{
int j;
int lcost ;
lcost = c + costar[k][i];
for(j=1; j < k; j++)
if( (x[j] == i) ||
(abs(x[j]-i) == abs(j-k)))
return 0;
mincost = GetMinCost(mincost);
if (lcost < mincost) {
return 1;
}
return 0;
}
int NQueens(k, n, pos, c)
int k, n ,pos,c;
{
int i, j, s, lcost;
lcost = c;
++NoVNodes;
if(pos) {
x[k] = pos;
lcost = c + costar[k][pos];
lcost = NQueens(k+1, n, 0, lcost);
return lcost;
}
for(i=1; i<= n; i++) {
++NoVNodes;
if(CheapPlace(k, i, c)){
x[k] = i;
lcost = c + costar[k][i];
if(k == n) {
++SolNo;
mincost = lcost;
for (j = 1; j < 29; j++) {
MinVector[j]=x[j];
}
return lcost;
}
else lcost = NQueens(k+1, n, 0, lcost);
}
}
return lcost;
}
/************************/
void GetData()
{
/* Receive data from master */
pvm_recv( master, GETTING_DATA );
pvm_upkint(&nproc, 1, 1);
pvm_upkint(tids, nproc, 1);
pvm_upkint(&mincost, 1, 1);
pvm_upkint(&n, 1, 1);
pvm_upkint( &costar[0][0], 29*29 , 1);
}
/*************************/
int AskMasterForATask()
{
int Msg;
Msg = SLAVE_HUNGRY;
pvm_initsend( PvmDataDefault );
pvm_pkint( &Msg, 1, 1 );
pvm_pkint( &me, 1, 1 );
pvm_send( master, SLAVE_HUNGRY );
pvm_recv(master, -1);
pvm_upkint(&Msg, 1, 1);
while((Msg == UPDATE_MIN_COST)) {
pvm_upkint(&mincost, 1, 1);
pvm_recv(master, -1);
pvm_upkint(&Msg, 1, 1);
}
++NoOfAsks;
if(Msg == NEW_TASK) {
pvm_upkint(&Pos, 1, 1);
pvm_upkint(&mincost, 1, 1);
}
return Msg;
}
/*************************/
SendMaster(MinCost)
int MinCost;
{
int Msg;
Msg = SOLUTION;
pvm_initsend( PvmDataDefault );
pvm_pkint( &Msg, 1, 1 );
pvm_pkint( &me, 1, 1 );
pvm_pkint( &MinCost, 1, 1 );
pvm_pkint( &MinVector[0], 29 , 1 );
pvm_send( master, SOLUTION );
}
main()
{
int j;
int MinCost;
NoOfAsks = 0;
NoOfTasks = 0;
NoOfSolvedTasks = 0;
NoVNodes = 0;
/* enroll in pvm */
mytid = pvm_mytid();
master = pvm_parent();
GetData();
/* Determine which slave I am (0 -- nproc-1) */
for( i=0; i",me);
/*pvm_exit();*/
}
********Sample data output********
DATA FOR SIXTEEN BY SIXTEEN MATRIX
**********************************************
Data file name = sixteen.dat
The chess board size = 16 X 16.
# of physical machine(s) added = 2
# of spawned tasks = 1
The minimum cost = 328 from slave # 0
The solution vector = ( 7, 4, 6, 11, 14, 1, 3, 16, 13,
8, 2, 9, 12, 15, 5, 10 )
The solution took exactly (1768) seconds
0 Days :0 Hours:29 Minutes:28 Seconds
**********************************************
Data file name = sixteen.dat
The chess board size = 16 X 16.
# of physical machine(s) added = 2
# of spawned tasks = 2
The minimum cost = 328 from slave # 0
The solution vector = ( 7, 4, 6, 11, 14, 1, 3, 16, 13,
8, 2, 9, 12, 15, 5, 10 )
The solution took exactly (503) seconds
0 Days :0 Hours:8 Minutes:23 Seconds
**********************************************
Data file name = sixteen.dat
The chess board size = 16 X 16.
# of physical machine(s) added = 3
# of spawned tasks = 3
The minimum cost = 328 from slave # 0
The solution vector = ( 7, 4, 6, 11, 14, 1, 3, 16, 13,
8, 2, 9, 12, 15, 5, 10 )
The solution took exactly (405) seconds
0 Days :0 Hours:6 Minutes:45 Seconds
**********************************************
Data file name = sixteen.dat
The chess board size = 16 X 16.
# of physical machine(s) added = 4
# of spawned tasks = 2
The minimum cost = 328 from slave # 1
The solution vector = ( 7, 4, 6, 11, 14, 1, 3, 16, 13,
8, 2, 9, 12, 15, 5, 10 )
The solution took exactly (865) seconds
0 Days :0 Hours:14 Minutes:25 Seconds
**********************************************
Data file name = sixteen.dat
The chess board size = 16 X 16.
# of physical machine(s) added = 4
# of spawned tasks = 3
The minimum cost = 328 from slave # 1
The solution vector = ( 7, 4, 6, 11, 14, 1, 3, 16, 13,
8, 2, 9, 12, 15, 5, 10 )
The solution took exactly (338) seconds
0 Days :0 Hours:5 Minutes:38 Seconds
**********************************************
Data file name = sixteen.dat
The chess board size = 16 X 16.
# of physical machine(s) added = 4
# of spawned tasks = 4
The minimum cost = 328 from slave # 3
The solution vector = ( 7, 4, 6, 11, 14, 1, 3, 16, 13,
8, 2, 9, 12, 15, 5, 10 )
The solution took exactly (277) seconds
0 Days :0 Hours:4 Minutes:37 Seconds
**********************************************
Data file name = sixteen.dat
The chess board size = 16 X 16.
# of physical machine(s) added = 9
# of spawned tasks = 8
The minimum cost = 329 from slave # 3
The solution vector = ( 8, 4, 16, 14, 10, 15, 5, 3,
13, 7, 2, 11, 1, 6, 9, 12 )
The solution took exactly (488) seconds
0 Days :0 Hours:8 Minutes:8 Seconds
**********************************************
Data file name = sixteen.dat
The chess board size = 16 X 16.
# of physical machine(s) added = 9
# of spawned tasks = 9
The minimum cost = 328 from slave # 7
The solution vector = ( 7, 4, 6, 11, 14, 1, 3, 16, 13,
8, 2, 9, 12, 15, 5, 10 )
The solution took exactly (400) seconds
0 Days :0 Hours:6 Minutes:40 Seconds