aem@mthvax.cs.miami.edu (a.e.mossberg) (10/15/90)
Posting-number: Volume 15, Issue 81
Submitted-by: "a.e.mossberg" <aem@mthvax.cs.miami.edu>
Archive-name: mpsim/part01
This is Felix Quevedo's Multiprocessor simultator package which he wrote
here at the University of Miami. I've provided a nroff'ed version of his
documentation, for those without the ms macros, or perhaps without *roff
itself.
The package was developed on a Sun 3 running SunOS 3.5 and has been
tested on Sun 4 running SunOS 4.0.3, a vax running Ultrix 3.0, and
a mac running A/UX 1.1 The Makefile needs to be changed for non-SunOS
systems.
Felix can be reached at fqs@mthvax.cs.miami.edu, but he can not provide
any support.
aem
-------------------------------cut here ------------------------------
#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create the files:
# mpsim
# This archive created: Sat Oct 6 17:05:05 1990
export PATH; PATH=/bin:$PATH
if test ! -d 'mpsim'
then
echo shar: creating directory "'mpsim'"
mkdir 'mpsim'
fi
echo shar: entering directory "'mpsim'"
cd 'mpsim'
echo shar: extracting "'doc.ms'" '(5126 characters)'
if test -f 'doc.ms'
then
echo shar: will not over-write existing file "'doc.ms'"
else
cat << \SHAR_EOF > 'doc.ms'
.nr PO 1.5i
.sp 2i
.ft B
.ce 2
The MultiProcessor Simulator\(co / Experimental Version 1.0
.sp 2
.ft R
by F\*'elix E. Quevedo Stuva
.sp 4
.ad b
.fi
.ls 2
.NH 1
Introduction
.NH 2
Why a Simulator
.PP
There are several reasons that justifies a Multiprocessor
Simulator, instead of purshising the actual hardware. The first reason
would be cost, since we assume that a Multiprocessor Computer is expensive.
Well, it is, but not much more than a commercial "Supercomputer". Another
reason would be the availability of CPU time, but we forget that the
hardware must be running some kind of multiprogramming operating system, that
allows time sharing. So then, what is the need of a simulator if the reasons
for not having a parallel computer are trivial? Well, we must not forget the
great diversity of proposed arquitectures and the fact that we do not have
at this moment a standard hardware and implementation software.
.PP
The spirit for the simulator design, was to have a tool for designing
algorithms without having a parallel computer, regardless of the model or
arquitecture used. This meant a design flexible enough to support the most
important features of most of the parallel computer models: shared memory
and interprocessor networks. From an academic point of view, these two
features must be handy to test algorithms that requires them.
.NH 2
Outline of the Simulator
.PP
The simulator allows the user to define an environment where to
test parallel algorithms. The user has access to the multiprocessor facilities through user
functions and an interactive environment where to execute the programs.
The user can define a number of pseudoprocessors, each one with one message
queue, and access to a single shared memory segment.
.PP
The message queue defined for a processor can contain any type of data,
including structures.
The creation of shared memory segments is a special feacture reserved for
a host programs. The access is public and with concurrent read and concurrent
write. It is the user the encharged to control the access to the SMS.
By using a layered approach, the user can design the its own parallel
computer model. As observed the simulator tries not to constrait the application
of the user.
.PP
The simulator runs in an UNIX environment with IPC facilities. This is any
UNIX release with System V support.
The number of processors that a user can define depends on the value of the
UNIX system parameter MAXUPRC, on the system program /sys/param.c.
.PP
The simulator has been implemented with all the self controls
considered at that moment. This does not guarantee that a bug could eventually pop.
The only way to avoid such inconvinience is the use of the system.
.NH 2
Unix IPC Facilities
.PP
The Interprocess Communication Facilities of UNIX System V, is the
Simulator's lower layer. The two described feature of a processor, are
actually IPC facilities with a nice user friendly presentation.
.PP
The message queue facility operates with more options than available with
the simulator. It is important to mention a constrain in the number of bytes
that the message queue together can support is defined on the value ot the
UNIX system parameters MSGPOOL, MSGSIZ, MSGNMI, etc; on /sys/h/msg.h.
.NH 2
Suggested Further Implementations
.PP
There are many upgrades that can be made in this first experimental version:
.IP a)
improve the setup and execution (mpload, mprun) functions,
.IP b)
extend the user library with a set of prefixed intercommunication networks;
.IP c)
extend the user library with a interprocess synchronization function;
.IP d)
improve the interactive module, even with windows and graphic support;
.IP e)
research in a programming language interface layer; etc.
.NH 1
Installation
.PP
The Makefile has all the setups necessary to install the simulator, just
type:
.sp
make
.PP
The final product are two file:
.IP mpsim
: Interactive Multiprocessor Simulator Manager;
.IP libmp.a
: user loading library.
.PP
To compile a user library just do:
.sp
cc myfile.c libmp.a [-o myfile] [-lm] ...
.NH 1
Implementation
.PP
The simulator has been implemented on UNIX C. It is transportability
has been proved between a SUN 3/60 and a VaxStation II. In both cases
the main modules were working, but with no guarantee of full feature
capacity.
.PP
The implementation consist of the following files:
.IP a)
mpsim.c: the interactive module. Contains the
.I main()
and the
.I _stop_handler()
functions.
.IP b)
mplib.c: the common function library. Contains the
.I
mpopen(), mptime(), mpprint(), mperro(), mehost(), _mplnode()
.R
functions.
.IP c)
mpsys.c: the system function library. Contains the
.I
_handler_req(), _handler_chl(), _handler_sys(), _mpinit(), _mpkill(),
_mplhost(), _mprun(), _mpstart(), _mpstatus(), _mpterm(),
.R and
_mpwait()
.R
functions.
.IP d)
mpusr.c: the user function library. Contains the
.I
_pause_handler()*, _getpt(), _trchd(), _imhost(), mprnd(), mpdim(),
mynode(), load(), _mvstr(), _rcvm(), recv(), trcv()*, send(),
probe(), crtshm(), attshm(), detshm()
.R and
slpmsq()*
.R
functions. The ones marked with a * are still on experimental phase.
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'Makefile'" '(635 characters)'
if test -f 'Makefile'
then
echo shar: will not over-write existing file "'Makefile'"
else
cat << \SHAR_EOF > 'Makefile'
#
# Multiprocessor Simulator MAKEFILE
#
COMP = cc -O
LDIR = scrs
SPRG = $(LDIR)/mpsim
CLIB = $(LDIR)/mplib.o
ULIB = $(LDIR)/mpusr.o
SLIB = $(CLIB) $(LDIR)/mpsys.o
SDEF = $(LDIR)/mpdef.h
UDEF = $(SDEF) $(LDIR)/mpuser.h
DFLG = -DMULTIPROCLIB
all:
make sim
make use
make clean
sim:
make $(SPRG)
mv $(SPRG) .
use:
make $(ULIB)
rm -f libmp.a
ar cr libmp.a $(ULIB) $(CLIB)
ranlib libmp.a
$(SPRG): $(SDEF) $(SLIB)
$(COMP) -o $@ $@.c $(SLIB)
$(SLIB): $(SDEF)
$(COMP) -c $(@:.o=.c) -o $(@)
$(ULIB): $(UDEF) $(CLIB)
$(COMP) -c $(@:.o=.c) -o $(@)
new:
rm mpsim libmp.a
prt:
ptroff -ms -h README
clean:
rm $(SLIB) $(ULIB)
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'doc.txt'" '(6912 characters)'
if test -f 'doc.txt'
then
echo shar: will not over-write existing file "'doc.txt'"
else
cat << \SHAR_EOF > 'doc.txt'
The MultiProcessor Simulator / Experimental Version 1.0
by Fe'lix E. Quevedo Stuva
1. Introduction
1.1. Why a Simulator
There are several reasons that justifies a Multiproces-
sor Simulator, instead of purshising the actual hardware.
The first reason would be cost, since we assume that a Mul-
tiprocessor Computer is expensive. Well, it is, but not
much more than a commercial "Supercomputer". Another reason
would be the availability of CPU time, but we forget that
the hardware must be running some kind of multiprogramming
operating system, that allows time sharing. So then, what is
the need of a simulator if the reasons for not having a
parallel computer are trivial? Well, we must not forget the
great diversity of proposed arquitectures and the fact that
we do not have at this moment a standard hardware and imple-
mentation software.
The spirit for the simulator design, was to have a tool
for designing algorithms without having a parallel computer,
regardless of the model or arquitecture used. This meant a
design flexible enough to support the most important
features of most of the parallel computer models: shared
memory and interprocessor networks. From an academic point
of view, these two features must be handy to test algorithms
that requires them.
1.2. Outline of the Simulator
The simulator allows the user to define an environment
where to test parallel algorithms. The user has access to
the multiprocessor facilities through user functions and an
interactive environment where to execute the programs. The
user can define a number of pseudoprocessors, each one with
one message queue, and access to a single shared memory seg-
ment.
The message queue defined for a processor can contain
any type of data, including structures. The creation of
shared memory segments is a special feacture reserved for a
host programs. The access is public and with concurrent read
and concurrent write. It is the user the encharged to con-
trol the access to the SMS. By using a layered approach,
the user can design the its own parallel computer model. As
observed the simulator tries not to constrait the applica-
tion of the user.
The simulator runs in an UNIX environment with IPC
facilities. This is any UNIX release with System V support.
The number of processors that a user can define depends on
the value of the UNIX system parameter MAXUPRC, on the sys-
tem program /sys/param.c.
The simulator has been implemented with all the self
controls considered at that moment. This does not guarantee
that a bug could eventually pop. The only way to avoid such
inconvinience is the use of the system.
1.3. Unix IPC Facilities
The Interprocess Communication Facilities of UNIX Sys-
tem V, is the Simulator's lower layer. The two described
feature of a processor, are actually IPC facilities with a
nice user friendly presentation.
The message queue facility operates with more options
than available with the simulator. It is important to men-
tion a constrain in the number of bytes that the message
queue together can support is defined on the value ot the
UNIX system parameters MSGPOOL, MSGSIZ, MSGNMI, etc; on
/sys/h/msg.h.
1.4. Suggested Further Implementations
There are many upgrades that can be made in this first
experimental version:
a) improve the setup and execution (mpload, mprun) func-
tions,
b) extend the user library with a set of prefixed inter-
communication networks;
c) extend the user library with a interprocess synchroni-
zation function;
d) improve the interactive module, even with windows and
graphic support;
e) research in a programming language interface layer;
etc.
2. Installation
The Makefile has all the setups necessary to install
the simulator, just type:
make
The final product are two file:
mpsim: Interactive Multiprocessor Simulator Manager;
libmp.a: user loading library.
To compile a user library just do:
cc myfile.c libmp.a [-o myfile] [-lm] ...
3. Implementation
The simulator has been implemented on UNIX C. It is
transportability has been proved between a SUN 3/60 and a
VaxStation II. In both cases the main modules were working,
but with no guarantee of full feature capacity.
The implementation consist of the following files:
a) mpsim.c: the interactive module. Contains the main()
and the stop handler() functions.
b) mplib.c: the common function library. Contains the mpo-
pen(), mptime(), mpprint(), mperro(), mehost(),
mplnode() functions.
c) mpsys.c: the system function library. Contains the
handler req(), handler chl(), handler sys(),
mpinit(), mpkill(), mplhost(), mprun(), mpstart(),
mpstatus(), mpterm(), mpwait() functions.
d) mpusr.c: the user function library. Contains the
pause handler()*, getpt(), trchd(), imhost(),
mprnd(), mpdim(), mynode(), load(), mvstr(), rcvm(),
recv(), trcv()*, send(), probe(), crtshm(), attshm(),
detshm() slpmsq()* functions. The ones marked with a *
are still on experimental phase.
SHAR_EOF
fi # end of overwriting check
if test ! -d 'scrs'
then
echo shar: creating directory "'scrs'"
mkdir 'scrs'
fi
echo shar: entering directory "'scrs'"
cd 'scrs'
echo shar: extracting "'mpdef.h'" '(3184 characters)'
if test -f 'mpdef.h'
then
echo shar: will not over-write existing file "'mpdef.h'"
else
cat << \SHAR_EOF > 'mpdef.h'
/* FQSystems -------------------------------------------------------------------
File : mpd.h
Header file for all system files.
Title : MultiProcessor Macro Library.
Author: Felix E. Quevedo Stuva.
Date : May 12, 1989.
----------------------------------------------------------------------------- */
/* -----------------------------------------------------------------------------
* System Macro Includes
*/
#include <sys/types.h>
#include <sys/time.h>
#include <sys/ipc.h>
#include <sys/msg.h>
#include <sys/shm.h>
#include <sys/wait.h>
#include <sys/resource.h>
#include <sys/file.h>
#include <errno.h>
#include <signal.h>
#include <stdio.h>
/* -----------------------------------------------------------------------------
* Global Macro Defines
*/
#define MAX_PRC 32
#define MIN_PRC 1
#define MSG_LEN 512
#define MAX_WAITC 80000
#define PEMPTY 0x0000
#define PREADY 0x0001
#define PRUNNING 0x0002
#define PBLOCKED 0x0003
#define NIL -1
/* -----------------------------------------------------------------------------
* Global Data Type Definition
*/
typedef struct {
short pno, /* processor number: 0..MAX_PRC */
ppw, /* pause wait flag: 0 pause, 1 continue */
pst; /* processor status:
* 0: empty,
* 1: ready,
* 2: running,
* 3: blocked */
int pid, /* processor UNIX PID */
msnd,
mrcv;
char cdp[50]; /* command string pointers */
long cmi; /* Msg queue ID */
struct rusage rsg; /* processor resource usage */
} MP_NODE;
typedef struct /* MP SHM table */
{
int mpn, /* number of active processors */
mpr, /* number of running processors */
mpq, /* processor starting request from host */
mpm, /* multiprocessor shared memory id */
mpf, /* logfile file descriptor */
mpt; /* logfile tracer indicator */
short mps; /* multiprocessor status:
* 0: empty,
* 1: ready,
* 2: running */
char mpl[50]; /* system log file */
/* the following two lines MUST always be together! */
MP_NODE mph; /* HOST node */
MP_NODE prc[MAX_PRC]; /* Processor nodes */
} MP_TBL;
typedef struct
{
long mtype;
char mtext[MSG_LEN];
} MSG_FORM;
typedef struct
{
int mwho; /* Who send the message */
int mlen; /* length of the message */
char *mtxt; /* message text */
} MSG_TXT;
/* -----------------------------------------------------------------------------
* Global external Functions
*/
extern char *shmat(), *mptime(), *ctime();
extern MP_TBL *getpt();
/* -----------------------------------------------------------------------------
* Global Variables
*/
#ifndef _MPLIB_
extern MSG_FORM Smsg, /* sending message */
Rmsg; /* receiving message */
extern MSG_TXT *Tmsg; /* general message text */
extern MP_TBL *Ptbl; /* proccesors table */
extern int MsgKey, MsgId, ShmId, _tout, jmp, mpfd, simpid, simsq;
#else
MSG_FORM Smsg, /* sending message */
Rmsg; /* receiving message */
MSG_TXT *Tmsg; /* general message text */
MP_TBL *Ptbl; /* proccesors table */
int MsgKey, MsgId, ShmId, _tout, jmp, mpfd, simpid, simsq;
#endif
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'mplib.c'" '(2459 characters)'
if test -f 'mplib.c'
then
echo shar: will not over-write existing file "'mplib.c'"
else
cat << \SHAR_EOF > 'mplib.c'
/* FQSystems -------------------------------------------------------------------
File : mplib.c
Title : MultiProcessor Functions Libraries
Author: Felix E. Quevedo Stuva.
Date : May 12, 1989
----------------------------------------------------------------------------- */
#define _MPLIB_
#include <varargs.h>
#include "mpdef.h"
long MPclk[1]; /* current time of the day */
mpopen(flg)
int flg;
{
return open((*Ptbl).mpl, flg, 00644);
}
char *mptime()
{
int i=0;
char *s, *c;
time(MPclk);
c = s = ctime(MPclk)+4;
for(; *c!='\n'; c++);
*(c-4) = '\0';
return s;
}
void mpprint(va_alist)
va_dcl
{
if(Ptbl && (*Ptbl).mpt) {
va_list args;
char *fmt, *whr;
int l;
va_start(args);
whr=Smsg.mtext;
strcpy(whr, mptime());
fmt = va_arg(args, char *);
(void)vsprintf(whr+16, fmt, args);
va_end(args);
write((*Ptbl).mpf, whr, strlen(whr));
}
}
mperror(n, wh)
int n; /* error number */
char *wh; /* who am I */
{
(*Ptbl).mpt=1;
switch(n) {
case 1:
mpprint("%s, MP not Active!!\n", wh);
printf("%s, MP not Active!!\n", wh);
break;
case 2:
mpprint("%s, MP already active!!\n", wh);
printf("%s, MP already active!!\n", wh);
break;
case 3:
mpprint("%s, MP could not attach the SHM segment!!\n", wh);
printf("%s, MP could not attach the SHM segment!!\n", wh);
break;
case 4:
mpprint("%s, MP could not assign a SHM segment!!\n", wh);
printf("%s, MP could not assign a SHM segment!!\n", wh);
break;
case 5:
mpprint("%s, BAD parameter list!!\n", wh);
printf("%s, BAD parameter list!!\n", wh);
break;
case 6:
mpprint("%s, Illegal command for node process!\n", wh);
printf("%s, Illegal command for node process!\n", wh);
break;
default:
mpprint("%s", wh);
printf("%s", wh);
break;
}
exit(n);
}
mehost()
{
if ((*Ptbl).mph.pid==getpid())
return 1;
return 0;
}
_mplnode(cmd, prcn)
char *cmd;
int prcn;
{
int i, j;
if(!cmd) return mperror(5, "Sim: lnode");
i=(prcn<0)?0:prcn;
j=(prcn<0)?(*Ptbl).mpn-1:i;
for(;i<=j;
strcpy((*Ptbl).prc[i].cdp, cmd),
(*Ptbl).prc[i].pst = PREADY,
mpprint("Sim: NODE %2d, Command %s loaded!\n", i, (*Ptbl).prc[i].cdp),
i++);
(*Ptbl).mps=PREADY;
}
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'mpsim.c'" '(5692 characters)'
if test -f 'mpsim.c'
then
echo shar: will not over-write existing file "'mpsim.c'"
else
cat << \SHAR_EOF > 'mpsim.c'
/* FQSystems -------------------------------------------------------------------
File : mpsim.c
Title : MultiProcessor Simulator Interactive Entry.
Author: Felix E. Quevedo Stuva.
Date : May 31, 1989.
----------------------------------------------------------------------------- */
#include "mpdef.h"
#include <sys/stat.h>
#include <setjmp.h>
struct stat stype[1];
int jmp;
jmp_buf env;
static _stop_handler()
{
if(!jmp) longjmp(env, 1);
}
#define MPLNODE 1
#define MPLHOST 2
#define MPSTART 3
#define MPLSTART 4
#define MPSTATUS 5
#define MPKILL 6
#define MPLOG 7
#define BADCOM 999
main(ac, ar)
int ac;
char *ar[];
{
int i=MAX_PRC;
int nr, j, tc;
char buf[BUFSIZ], *cmd, *par, *opc, fn[50], *mptime();
if(ac>1) i = atoi(ar[1]);
_mpinit(i);
signal(SIGINT, _stop_handler);
printf("University of Miami\n");
printf("Department of Mathematics and Computer Science\n");
printf("MultiProccessor Simulator - Experimental Ver 1.0\n");
if (((*Ptbl).mpf=mpopen(O_CREAT | O_WRONLY | O_APPEND))==NIL) {
printf("Sim: WARNING, NOT able to open default logfile %s!!\n",
(*Ptbl).mpl);
}
setjmp(env);
jmp=1;
for(;;)
{
for(;;) {
printf("\nMPSim\/%d >> ", (*Ptbl).mpn);
nr=(int)fgets(buf, BUFSIZ, stdin);
if(nr==NULL) _mpterm();
for(i=0; buf[i]==' ' && i<BUFSIZ; i++);
if(buf[i]!='\n') break;
}
for(i=i, cmd=buf+i, opc=par=0;
i<BUFSIZ && buf[i]!=' ' && buf[i]!='\n'; i++);
if(buf[i]==' ' || buf[i]=='\n') {
buf[i] = 0;
par = &buf[i]+1;
for(; *par==' ' && i<BUFSIZ; par++, i++);
if(*par=='\n')
*par=0;
else {
if(*par=='-') {
opc = par+1;
for(j=0; i<BUFSIZ && opc[j]!='\n' && opc[j]!=' '; i++, j++);
if(opc[j]!='\n') par=opc+j+1;
opc[j]=0;
}
for(j=0; i<BUFSIZ && par[j]!='\n'; i++, j++);
if(par[j] =='\n') par[j]=0;
}
}
/*printf("cmd %s, par %s, opc %s\n", cmd, par, opc);*/
tc=NIL;
if (!strcmp("lhost", cmd)) tc=MPLHOST;
else
if (!strcmp("lh", cmd)) tc=MPLHOST;
else
if (!strcmp("lnode", cmd)) tc=MPLNODE;
else
if (!strcmp("ln", cmd)) tc=MPLNODE;
else
if (!strcmp("start", cmd)) tc=MPSTART;
else
if (!strcmp("s", cmd)) tc=MPSTART;
else
if (!strcmp("lstart", cmd)) tc=MPLSTART;
else
if (!strcmp("ls", cmd)) tc=MPLSTART;
else
if (!strcmp("kill", cmd)) tc=MPKILL;
else
if (!strcmp("status", cmd)) tc=MPSTATUS;
else
if (!strcmp("st", cmd)) tc=MPSTATUS;
else
if (!strcmp("log", cmd)) tc=MPLOG;
else
if (!strcmp("quit", cmd)) _mpterm();
else
if (!strcmp("q", cmd)) _mpterm();
else
if (!strcmp("trace", cmd) || !strcmp("t", cmd)) {
(*Ptbl).mpt=(*Ptbl).mpt?0:1;
printf((*Ptbl).mpt?"Sim: trace ON\n":"Sim: trace OFF\n");
}
else tc=BADCOM;
switch(tc) {
case MPLNODE:
if(*par)
if((i=stat(par, stype))==-1)
printf("Sim: File %s, does NOT exist!\n", par);
else
if ((*stype).st_mode & S_IEXEC) {
i=opc?atoi(opc):-1;
if (i>-2 && i<MAX_PRC)
_mplnode(par, i);
else
printf("Sim: Option %s, is invalid\n", opc);
}
else
printf("Sim: File %s, is NOT executable\n", par);
else
printf("Sim: Sintax error, ln <-node_index> file_name\n");
break;
case MPLHOST:
if(*par)
if((i=stat(par, stype))==-1)
printf("Sim: File %s, does NOT exist!\n", par);
else
if ((*stype).st_mode & S_IEXEC)
_mplhost(par);
else
printf("Sim: File %s, is NOT executable\n", par);
else
printf("Sim: Sintax error, lh file_name\n");
break;
case MPSTART:
if((*Ptbl).mps==PREADY) {
(*Ptbl).mps=PBLOCKED;
_mprun(-1);
(*Ptbl).mps=PRUNNING;
}
_mpwait();
break;
case MPLSTART:
if((*Ptbl).mps==PREADY) _mpstart(-1);
_mpwait();
break;
case MPKILL:
_mpkill(SIGKILL);
break;
case MPSTATUS:
_mpstatus();
break;
case MPLOG:
if(*par) {
strcpy((*Ptbl).mpl, par);
strcat((*Ptbl).mpl, ".LOG");
}
close((*Ptbl).mpf);
if (((*Ptbl).mpf=mpopen(O_CREAT | O_WRONLY | O_TRUNC))==NIL) {
printf("Sim: NOT able to open log file %s!!\n", (*Ptbl).mpl);
perror("Sim");
}
else {
j=(*Ptbl).mpt;
(*Ptbl).mpt=1;
mpprint("Sim: Log file %s, initiated\n", (*Ptbl).mpl);
(*Ptbl).mpt=j;
printf("Sim: Log file %s, initiated\n", (*Ptbl).mpl);
}
break;
case BADCOM:
printf("Sim: Unknown command %s\n", cmd);
break;
default:
break;
}
}
}
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'mpsys.c'" '(8549 characters)'
if test -f 'mpsys.c'
then
echo shar: will not over-write existing file "'mpsys.c'"
else
cat << \SHAR_EOF > 'mpsys.c'
/* FQSystems -------------------------------------------------------------------
File : mpsys.c
Title : MultiProcessor Simulator System File
Author: Felix E. Quevedo Stuva.
Date : May 12, 1989.
----------------------------------------------------------------------------- */
#include "mpdef.h"
static _handler_req()
{
if((*Ptbl).mpq>=0) {
_mprun((*Ptbl).mpq);
(*Ptbl).mps=PRUNNING;
}
else {
(*Ptbl).mps=PREADY;
_mpstart(0);
}
}
static _handler_chl()
{
int p, i, r, j, (*oh)();
union wait stts[1];
struct rusage rsg[1];
char wht[20];
while((p=wait3(stts, WNOHANG, rsg))>0) {
r=(*stts).w_retcode;
for(i=j=0, i--; (*Ptbl).prc[i].pid!=p && (*Ptbl).mpn>i; i++);
if WIFEXITED(*stts) {
strcpy(wht, "EXITED\n");
(*Ptbl).prc[i].pid = 0;
(*Ptbl).prc[i].pst = PREADY;
if(r) {
mpprint("Warning, NODE %d has exited with RC=%d\n", i, r);
}
if(i == NIL) _mpkill(9);
}
else
if WIFSIGNALED(*stts) {
strcpy(wht, "SIGNALED\n");
(*Ptbl).prc[i].pid = 0;
(*Ptbl).prc[i].pst = PREADY;
mpprint("Warning, NODE %d signaled SIG=%d\n", i, (*stts).w_stopval);
}
else
if WIFSTOPPED(*stts) {
strcpy(wht, "STOPPED\n");
(*Ptbl).prc[i].pst = PBLOCKED;
}
j=(*Ptbl).mpt;
(*Ptbl).mpt=1;
mpprint("NODE %2d: RC %2d CPU%6d SYS%6d MSND%4d MRCV%4d %s", i, r,
(*rsg).ru_utime.tv_usec/1000, (*rsg).ru_stime.tv_usec/1000,
(*Ptbl).prc[i].msnd, (*Ptbl).prc[i].mrcv, wht);
(*Ptbl).mpt=j;
if((*Ptbl).mpr>0) (*Ptbl).mpr--;
}
if(!(*Ptbl).mpr) (*Ptbl).mps=PREADY;
}
static _handler_sys()
{
int i, j, k;
struct itimerval val[1];
struct itimerval oval[1];
if(Ptbl) {
for(i=0, i--; i<(*Ptbl).mpn; i++) {
if((*Ptbl).prc[i].pid)
kill((*Ptbl).prc[i].pid, SIGKILL);
msgctl((*Ptbl).prc[i].cmi, IPC_RMID, 0);
}
shmctl((*Ptbl).mpm, IPC_RMID, 0);
shmctl(shmget(geteuid(), sizeof(MP_TBL), 0777), IPC_RMID, 0);
}
(*val).it_interval.tv_usec=(*val).it_value.tv_usec=0;
setitimer(ITIMER_REAL, val, oval);
exit(0);
}
_mpinit(n)
int n; /* number of starting processors */
{
int i, j, k;
if(n < MIN_PRC)
printf("Minimum # of Nodes (%d) NOT REACHED!\n", MIN_PRC);
else
if (n > MAX_PRC)
printf("Maximum # of Nodes (%d) EXCEEDED!\n", MAX_PRC);
else {
signal(SIGCHLD, _handler_chl);
signal(SIGUSR1, _handler_req);
signal(SIGUSR2, SIG_IGN);
for(i=1; i<17; signal(i++, _handler_sys));
ShmId = shmget(geteuid(), sizeof(MP_TBL), 0777|IPC_CREAT);
if (ShmId > NIL) {
Ptbl = (MP_TBL *)shmat(ShmId, 0, 0);
if (Ptbl > 0) {
(*Ptbl).mpn = n;
(*Ptbl).mpm = 0;
(*Ptbl).mpt = 0;
(*Ptbl).mps = PEMPTY;
strcpy((*Ptbl).mpl, "MPSYSLOG");
for(i=0, i--; i<n; i++) {
(*Ptbl).prc[i].pid = 0;
(*Ptbl).prc[i].ppw = 0;
(*Ptbl).prc[i].pno = i;
(*Ptbl).prc[i].pst = PEMPTY;
(*Ptbl).prc[i].cmi = 0;
(*Ptbl).prc[i].msnd= 0;
(*Ptbl).prc[i].mrcv= 0;
(*Ptbl).prc[i].cdp[0] = 0;
}
}
else mperror(3, "Sim: init");
}
else mperror(4, "Sim: init");
return;
}
mperror(999, "Sim, init");
}
_mpkill(sig)
int sig;
{
int i;
if(Ptbl)
{
for(i=0, i--;i<(*Ptbl).mpn;i++)
if((*Ptbl).prc[i].pid)
kill((*Ptbl).prc[i].pid, sig);
}
else mperror(1, "Sim: kill");
}
_mplhost(cmd)
char *cmd;
{
if(!cmd) return mperror(5, "Sim: lhost");
strcpy((*Ptbl).mph.cdp, cmd);
mpprint("HOST, Command %s loaded!\n", (*Ptbl).mph.cdp);
(*Ptbl).mps=(*Ptbl).mph.pst=PREADY;
}
_mprun(j)
int j;
{
int n, i, k;
if (Ptbl > 0) { /* if Mp is setup */
i=fork(); /* create child process */
if(i>0) { /* I'm still daddy. */
(*Ptbl).prc[j].pid = i; /* save Unix pid */
(*Ptbl).mpr++; /* more running successful */
msgctl((*Ptbl).prc[j].cmi, IPC_RMID, 0);
(*Ptbl).prc[j].cmi = msgget(geteuid()+i, 0777|IPC_CREAT);
(*Ptbl).prc[j].msnd = 0; /* initiate msg snd counter */
(*Ptbl).prc[j].mrcv = 0; /* initiate msg rcv counter */
} else
if(!i) { /* I'm child */
signal(SIGINT, SIG_IGN); /* setup ignore INT signal */
signal(SIGUSR2,SIG_IGN); /* setup ignore USR2 signal */
(*Ptbl).prc[j].pst=PBLOCKED; /* status child blocked */
for(;(*Ptbl).mps!=PRUNNING;);/* wait for MP setup */
(*Ptbl).prc[j].pst=PRUNNING; /* status child running */
/* exec user process */
i=execl((*Ptbl).prc[j].cdp, (char *)0);
if(mehost()) { /* inform system error */
printf("HOST, SYSTEM ERROR! Couldn't EXECL\n");
mpprint("HOST, Couldn't EXECL %s, RC %d\n",
(*Ptbl).prc[j].cdp, i);
}
else {
printf("NODE %2d, SYSTEM ERROR! Couldn't EXECL\n",j);
mpprint("NODE %2d, Couldn't EXECL %s, RC %d\n",
j, (*Ptbl).prc[j].cdp, i);
}
exit(999);
}
else { /* SYSTEM ERROR!, terminate simulator now! */
printf("NODE %2d, SYSTEM ERROR! Couldn't fork \n",j);
mpprint("NODE %2d, SYSTEM ERROR! Couldn't fork \n",j);
_mpterm();
}
}
return 0;
}
_mpstart(b)
int b; /* initial node to start MP simulation */
{
int n, i, j, k;
if (Ptbl > 0) {
switch ((*Ptbl).mps) {
case PEMPTY:
printf("MPStart, MP Simulator is not ready! MPLoad first!\n",j);
break;
case PREADY:
n=(*Ptbl).mpn;
for(j=b; j < n;j++) {
switch ((*Ptbl).prc[j].pst) {
case PEMPTY:
break;
case PREADY:
_mprun(j);
break;
case PRUNNING:
printf("NODE %2d, USER ERROR! Node is running\n",j);
break;
case PBLOCKED:
printf("NODE %2d, USER ERROR! Node is blocked\n",j);
break;
default:
printf("NODE %2d, STATUS ERROR! Unknown type %d\n", j,
(*Ptbl).prc[j].pst);
mpprint("NODE %2d, STATUS ERROR! Unknown type %d\n", j,
(*Ptbl).prc[j].pst);
_mpterm();
break;
}
}
(*Ptbl).mps=PRUNNING;
break;
default:
printf("MPStart, USER ERROR!... MP simulator is running\n");
break;
}
}
else mperror(3, "Sim: starter");
}
_mpstatus()
{
int i, j;
if(Ptbl)
{
printf("Nodes : %5d Logfile : %s\n", (*Ptbl).mpn, (*Ptbl).mpl);
printf("Status: %5d #Running: %5d\n", (*Ptbl).mps, (*Ptbl).mpr);
printf("Node UNIXId MsgId Command MsgSnd MsgRcv Status\n");
printf("---- ------ ------ ---------- ------ ------ -------\n");
for(i=0, i--; i<(*Ptbl).mpn; i++)
{
if ((*Ptbl).prc[i].pst!=PEMPTY) {
printf("%4d %6d %6d %10s %6d %6d ",
(*Ptbl).prc[i].pno, (*Ptbl).prc[i].pid,
(*Ptbl).prc[i].cmi, (*Ptbl).prc[i].cdp,
(*Ptbl).prc[i].msnd, (*Ptbl).prc[i].mrcv);
switch ((*Ptbl).prc[i].pst) {
case PREADY: printf("ready");
break;
case PRUNNING: printf("running");
break;
case PBLOCKED: printf("blocked");
break;
}
printf("\n");
}
}
}
else mperror(1, "Sim: status");
}
_mpterm()
{
kill(getpid(), SIGTERM);
pause();
}
_mpwait()
{
if(Ptbl)
{
jmp=0;
for(;(*Ptbl).mpr;);
(*Ptbl).mps=PREADY;
}
else mperror(1, "Sim: wait");
}
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'mpuser.h'" '(115 characters)'
if test -f 'mpuser.h'
then
echo shar: will not over-write existing file "'mpuser.h'"
else
cat << \SHAR_EOF > 'mpuser.h'
#include <math.h>
#define lg2(X) X!=8?log((double)X)/log(2.):3.;
#define pw2(X) pow(2.,(double)X);
#define NIL -1
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'mpusr.c'" '(6179 characters)'
if test -f 'mpusr.c'
then
echo shar: will not over-write existing file "'mpusr.c'"
else
cat << \SHAR_EOF > 'mpusr.c'
/* FQSystems -------------------------------------------------------------------
File : mpusr.c
Title : User library
Author: Felix E. Quevedo Stuva.
Date : May 12, 1989
----------------------------------------------------------------------------- */
#define _MPLIB_
#include "mpdef.h"
#include <varargs.h>
#include <sys/stat.h>
struct stat stype[1];
char tmpbf[80];
char tbuf[20];
int bft=0; /* indicate that buffer has been touch */
static _pause_handler()
{
(*Ptbl).prc[mynode()].ppw = 1;
}
_getpt() /* asure that MP is setup */
{
int i;
if(Ptbl<=0)
if((i=shmget(geteuid(), sizeof(MP_TBL), 0777))>NIL)
Ptbl=(MP_TBL *)shmat(i, 0, 0);
if(Ptbl>0) return;
mperror(1, "User: _getpt");
}
char *_trchd()
{
_getpt();
if(!bft) {
tbuf[0]=0;
bft=1;
if(mehost())
sprintf(tbuf, "User: HOST ,");
else
sprintf(tbuf, "User: NODE %2d,", mynode());
}
return tbuf;
}
_imhost() /* security gateguard for host commands */
{
_getpt();
if (mehost()) return;
mperror(6, "User: _imhost");
}
mprnd() /* return number of nodes running */
{
_getpt();
return (*Ptbl).mpr;
}
mpdim() /* return maximum number of nodes available */
{
_getpt();
return (*Ptbl).mpn;
}
mynode() /* return current node number */
{
int i, j;
_getpt();
j = getpid();
for(i=NIL; i<(*Ptbl).mpn && (*Ptbl).prc[i].pid != j; i++);
if (i<(*Ptbl).mpn && (*Ptbl).prc[i].pid == j)
return (*Ptbl).prc[i].pno;
sprintf(tmpbf, "UNIX PID: %d is NOT a MP node!\n", getpid());
mperror(999, tmpbf );
}
load(fn, nd) /* load node command and execute */
char *fn;
int nd;
{
int i, j;
mpprint("%s loading node comand\n", _trchd());
_imhost(); /* be sure that I'm the host */
if((i=stat(fn, stype))==-1) { /* is the node exec exists? */
sprintf(tmpbf, "%s load, file %s does NOT exist!\n", _trchd(), fn);
mperror(999, tmpbf );
}
else
if ((*stype).st_mode & S_IEXEC) { /* is the node exec executable */
if (nd>-2 && nd<MAX_PRC) { /* is the node a legal one? */
_mplnode(fn, nd); /* load nodes */
(*Ptbl).mpq=nd; /* start request */
kill(getppid(), SIGUSR1); /* ask simulator to start request */
for(;(*Ptbl).mps!=PRUNNING;); /* wait for MPStart to setup */
}
else {
sprintf(tmpbf, "%s load, illegal node %d\n", _trchd(), nd);
mperror(999, tmpbf);
}
}
else {
sprintf(tmpbf, "%s load, file %s is NOT executable\n", _trchd(), fn);
mperror(999, tmpbf);
}
}
_mvstr(from, to, len)
int len;
char *from, *to;
{
int i;
for(i=0; i<len; to[i]=from[i], i++);
}
_rcvm(prcn, txt, len, type, wtyp, mode) /* receive from the msg queue */
int len, *type, *prcn, wtyp, mode;
char *txt;
{
int i, j;
_getpt();
i = mynode();
(*Ptbl).prc[i].pst = PBLOCKED;
mpprint("%s waiting for msg type %d\n", _trchd(), wtyp);
if((j=msgrcv((*Ptbl).prc[i].cmi, &Rmsg, MSG_LEN, wtyp, mode))>NIL) {
*type= Rmsg.mtype;
Tmsg = (MSG_TXT *)Rmsg.mtext; /* this command FIRST */
*prcn= (*Tmsg).mwho;
if(len != (*Tmsg).mlen) { /* if expected len != recv len then abort */
sprintf(tmpbf, "%s recv, msg len snd %d and rcv %d does NOT match!\n",
_trchd(), len, (*Tmsg).mlen);
mperror(999, tmpbf);
}
_mvstr(&(*Tmsg).mtxt, txt, len);
/* NO mpprint before this line!!!! */
mpprint("%s recv from %d, len %d, type %d\n", _trchd(), *prcn, len, *type);
(*Ptbl).prc[i].mrcv++;
}
if(j==NIL) mpprint("%s UNSUCCESSFUL recv len %d, type %d\n", _trchd(), len, wtyp);
(*Ptbl).prc[i].pst = PRUNNING;
return j;
}
recv(prcn, txt, len, type, wtyp) /* receive from the msg queue */
int len, *type, *prcn, wtyp;
char *txt;
{
return _rcvm(prcn, txt, len, type, wtyp, 0); /* receive from the msg queue */
}
trcv(prcn, txt, len, type, wtyp) /* test and receive from the msg queue */
int len, *type, *prcn, wtyp;
char *txt;
{
return _rcvm(prcn, txt, len, type, wtyp, IPC_NOWAIT); /* receive from the msg queue */
}
send(prcn, txt, len, type) /* send a msg */
int prcn, len, type;
char *txt;
{
int i;
_getpt();
Smsg.mtype=type;
Tmsg = (MSG_TXT *)Smsg.mtext; /* this command FIRST */
_mvstr(txt,&(*Tmsg).mtxt, len);
i=(*Tmsg).mwho = mynode();
(*Tmsg).mlen = len;
if(msgsnd((*Ptbl).prc[prcn].cmi, &Smsg, 2*sizeof(int) + len, 0)==0) {
/* NO mpprint before this line!!!! */
kill((*Ptbl).prc[prcn].pid, SIGUSR2);
mpprint("%s sent to %d, len %d, type %d\n", _trchd(), prcn, len, type);
(*Ptbl).prc[i].msnd++;
return 0;
}
mpprint("%s UNSUCCESSFUL send to %d, len %d, type %d\n", _trchd(), prcn, len, type);
return NIL;
}
probe(i)
int i;
{
struct msqid_ds buf[1];
_getpt();
if(!i)mpprint("%s testing msg queue\n", _trchd());
if(msgctl((*Ptbl).prc[mynode()].cmi, IPC_STAT, buf) != NIL)
return (*buf).msg_qnum;
return 0;
}
crtshm(sz)
int sz;
{
_imhost(); /* be sure that I'm the host */
mpprint("%s creating shared memory segment\n", _trchd());
(*Ptbl).mpm = shmget(geteuid()+1, sz, 0777|IPC_CREAT);
if((*Ptbl).mpm > 0) {
return attshm();
}
else
mperror(3, _trchd());
}
attshm()
{
int i;
_getpt();
mpprint("%s attaching share memory segment\n", _trchd());
i=(int)shmat((*Ptbl).mpm, 0, 0);
if(i>0)
return i;
mperror(4, _trchd());
}
detshm()
{
_getpt();
mpprint("%s dettaching share memory segment\n", _trchd());
return shmdt(shmat((*Ptbl).mpm, 0, 0));
}
slpmsq() /* sleep until new message is queued */
{
int i=mynode();
mpprint("%s sleeping until new message, current %d\n", _trchd(), probe());
signal(SIGUSR2, _pause_handler);
if(!(*Ptbl).prc[i].ppw) {
pause();
}
(*Ptbl).prc[i].ppw=0;
}
SHAR_EOF
fi # end of overwriting check
echo shar: done with directory "'scrs'"
cd ..
if test ! -d 'tsts'
then
echo shar: creating directory "'tsts'"
mkdir 'tsts'
fi
echo shar: entering directory "'tsts'"
cd 'tsts'
if test ! -d 'hi'
then
echo shar: creating directory "'hi'"
mkdir 'hi'
fi
echo shar: entering directory "'hi'"
cd 'hi'
echo shar: extracting "'hi.c'" '(892 characters)'
if test -f 'hi.c'
then
echo shar: will not over-write existing file "'hi.c'"
else
cat << \SHAR_EOF > 'hi.c'
/* ------------------------------------------------------------------------------
* hi.c
* Nice test program
* Uses SHM segment and sends messages to processor i+1.
* Felix E. Quevedo Stuva
* Oct 11, 1989
* --------------------------------------------------------------------------- */
main()
{
int i,j, l, t, f;
char txt[50];
double *mt;
i=mynode();
j=mpdim();
printf("Hi there!, I'm NODE %d\n",i);
recv(&f, txt, 7, &t, 0);
printf("NODE %d: recv %s, len %d, type %d, from %d\n", i, txt, l, t, f);
mt=(double*)attshm();
mt[i]=i;
printf("NODE %d: attached shm seg and update index %d\n",i, i);
if((i+1)%j) {
printf("NODE %d: sending to %d\n",i, (i+1)%j);
send((i+1)%j, txt, 7, t+1);
}
printf("NODE %d: sending to the host!\n", i);
if(send(-1, txt, 7, t+1)<0)
printf("NODE %d, Message not delivered!\n", i);
else
printf("NODE %d, Message delivered!\n", i);
}
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'hih.c'" '(752 characters)'
if test -f 'hih.c'
then
echo shar: will not over-write existing file "'hih.c'"
else
cat << \SHAR_EOF > 'hih.c'
/* ------------------------------------------------------------------------------
* hih.c
* Nice test program
* Allocates SHM segment and sends messages to processors.
* Felix E. Quevedo Stuva
* Oct 11, 1989
* --------------------------------------------------------------------------- */
main()
{
int i,j, l, t, f;
char txt[10];
double *mt;
printf("HOST: running\n");
load("hi",-1);
mt = (double*)crtshm(20*sizeof(double));
printf("HOST: send message to 0\n");
send(0, "Howdy!", 7, 1);
j=mpdim()+1;
printf("HOST: waiting message type %d\n", j);
recv(&f, txt, 7, &t, j);
printf("HOST: received msg type %d from %d\n", t, f);
printf("Shared Memory content:\n");
for(i=0; i<t-1; printf("%f ", mt[i++]));
printf("\n");
}
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'Makefile'" '(226 characters)'
if test -f 'Makefile'
then
echo shar: will not over-write existing file "'Makefile'"
else
cat << \SHAR_EOF > 'Makefile'
#
# Multiprocessor Simulator MAKEFILE
#
COMP = cc -O
MLIB = ../../libmp.a
all:
$(COMP) -o hih hih.c $(MLIB)
$(COMP) -o hi hi.c $(MLIB)
go:
../../mpsim 8 < go.file
prt:
ptroff -ms -h README
clean:
rm hih hi MPSYSLOG
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'README'" '(1000 characters)'
if test -f 'README'
then
echo shar: will not over-write existing file "'README'"
else
cat << \SHAR_EOF > 'README'
The MultiProcessor Simulator / Experimental Version 1.0
by Fe'lix E. Quevedo Stuva
Nice test program
This example does not other objective to just test the communication
and share memory features of the simulator. In general allocates
share memory segment and sends a round ribbon greeting message.
The host program (hih), loads the processor program (hi)
to the available processors. Then creates the share memory segment
and saves the pointer. Finally sends a greeting message to processor 0
of type 1, and waits for a message of type number of proecessors plus 1.
Once the message is received it displays the content of the share memory
segment.
The processor programs, waits for a message of any type. Once received
it attaches the shere memory segment and updates an area of index equal
to the processor number with the processor number. Finally sends a message to
the next processor after incrementing the previous type received in 1.
If the processor is the last it send it to the host.
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'go.file'" '(15 characters)'
if test -f 'go.file'
then
echo shar: will not over-write existing file "'go.file'"
else
cat << \SHAR_EOF > 'go.file'
lh hih
ls
st
q
SHAR_EOF
fi # end of overwriting check
echo shar: done with directory "'hi'"
cd ..
if test ! -d 'max'
then
echo shar: creating directory "'max'"
mkdir 'max'
fi
echo shar: entering directory "'max'"
cd 'max'
echo shar: extracting "'max.h'" '(393 characters)'
if test -f 'max.h'
then
echo shar: will not over-write existing file "'max.h'"
else
cat << \SHAR_EOF > 'max.h'
/* max.h
* CRCW Parallel Algorithm for Finding Maximum of a set of numbers.
* Header file for source codes
* Felix E. Quevedo
* November 10, 1989.
*/
typedef
struct {
short flg, /* sinchronization semaphore */
ij[15][2], /* compare indexes */
lst[6]; /* lost vector */
int vec[6], /* data vector */
max; /* maximum value */
} SMSeg;
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'README'" '(1084 characters)'
if test -f 'README'
then
echo shar: will not over-write existing file "'README'"
else
cat << \SHAR_EOF > 'README'
The MultiProcessor Simulator / Experimental Version 1.0
by Fe'lix E. Quevedo Stuva
Maximum Finding Algorithm CRWR SM MIMD.
This example uses the share memory feature of the MPsim. It also intends
to show how to make a user semaphore and simulate a SIMD machine.
This algorithm is known to be the fastest.
The host program creates the share segment, prepares data, and loads the
processor program one at a time. Once all the processors are loaded, the
host wiats for all the processors to complete the first step. Once all the
processors has completed the first step, it resets the step flag and
waits for the second step. Finally displays the results on the
corresponding share memory area.
The processor program in the first step obtains the maximum of the two
assigned values, marking the looser vector. Then increments the flag a
and if its a second step processor, waits for the host to reset the flag.
Once the processor resets the flag verifies if the assigned looser index
value is winner (not looser) to save the maximum value on the correspponding
share memory area.
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'max_hst.c'" '(1207 characters)'
if test -f 'max_hst.c'
then
echo shar: will not over-write existing file "'max_hst.c'"
else
cat << \SHAR_EOF > 'max_hst.c'
/* max_hst.c
*
* CRCW Parallel Algorithm for Finding Maximum of a set of numbers.
*
* Host source code
* Felix E. Quevedo
* November 10, 1989.
*/
#include "max.h"
main()
{
int i, j, k, l;
SMSeg *seg;
seg = (SMSeg*)crtshm(sizeof(SMSeg)); /* create share memory segment */
/* prepare data and parameter for execution */
srandom(l = time() / 100); /* seed of random generator */
for(i=k=0; i < 6; i++) { /* for all vector number */
seg->vec[i] = random() / l; /* generate random integer */
seg->lst[i] = 0; /* nobody lost */
for(j=i+1; j < 6; j++) { /* prepare Pi,j -> Pk*/
seg->ij[k][0] = i;
seg->ij[k][1] = j;
k++;
}
}
printf("Shared Memory Input Vector:\n");
for(i=0; i < 6; printf("%d ", seg->vec[i++]));
printf("\n");
printf("HOST: First Step\n");
seg->flg = 0; /* start 1st step */
for(i=0; i < 15; load("max_prc",i++)); /* load processors */
while(seg->flg-i); /* wait complete 1st step */
printf("HOST: Second Step\n");
seg->flg = 0; /* start 2nd step */
while(seg->flg+6); /* wait complete 2nd step */
printf("Shared Memory content:\n");
for(i=0; i<6; printf("%d ", seg->lst[i++]));
printf("\n");
printf("Max: %d\n", seg->max);
}
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'max_prc.c'" '(870 characters)'
if test -f 'max_prc.c'
then
echo shar: will not over-write existing file "'max_prc.c'"
else
cat << \SHAR_EOF > 'max_prc.c'
/* max_prc.c
*
* CRCW Parallel Algorithm for Finding Maximum of a set of numbers.
*
* Processor source code
* Felix E. Quevedo
* November 10, 1989.
*/
#include "max.h"
main()
{
int i, j, k, l;
SMSeg *seg;
seg = (SMSeg*)attshm(sizeof(SMSeg)); /* attach share memory segment */
i = mynode(); /* get node number */
j = seg->ij[i][0]; /* get compare index */
k = seg->ij[i][1]; /* get compare index */
l = (seg->vec[j] < seg->vec[k])? j : k; /* compare */
seg->lst[l] = 1; /* mark looser / minimum */
seg->flg++; /* increment semaphore */
printf("Prc: %2d selects index %d from %d, %d\n", i, l, j, k);
if ( i < 6) {
while(seg->flg>0); /* wait for 2nd step go! */
if (!seg->lst[i]) /* if I'm the looser */
seg->max = seg->vec[i]; /* I'm the maximum */
seg->flg--; /* decrement semaphore */
}
}
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'Makefile'" '(252 characters)'
if test -f 'Makefile'
then
echo shar: will not over-write existing file "'Makefile'"
else
cat << \SHAR_EOF > 'Makefile'
#
# Multiprocessor Simulator MAKEFILE
#
COMP = cc -O
MLIB = ../../libmp.a
all:
$(COMP) -o max_hst max_hst.c $(MLIB)
$(COMP) -o max_prc max_prc.c $(MLIB)
go:
../../mpsim 16 < go.file
prt:
ptroff -ms -h README
clean:
rm max_hst max_prc MPSYSLOG
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'go.file'" '(19 characters)'
if test -f 'go.file'
then
echo shar: will not over-write existing file "'go.file'"
else
cat << \SHAR_EOF > 'go.file'
lh max_hst
ls
st
q
SHAR_EOF
fi # end of overwriting check
echo shar: done with directory "'max'"
cd ..
if test ! -d 'mmlt'
then
echo shar: creating directory "'mmlt'"
mkdir 'mmlt'
fi
echo shar: entering directory "'mmlt'"
cd 'mmlt'
echo shar: extracting "'Makefile'" '(258 characters)'
if test -f 'Makefile'
then
echo shar: will not over-write existing file "'Makefile'"
else
cat << \SHAR_EOF > 'Makefile'
#
# Multiprocessor Simulator MAKEFILE
#
COMP = cc -O
MLIB = ../../libmp.a
all:
$(COMP) -o mmlt_hst mmlt_hst.c $(MLIB)
$(COMP) -o mmlt_prc mmlt_prc.c $(MLIB)
go:
../../mpsim 16 < go.file
prt:
ptroff -ms -h README
clean:
rm mmlt_hst mmlt_prc MPSYSLOG
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'README'" '(858 characters)'
if test -f 'README'
then
echo shar: will not over-write existing file "'README'"
else
cat << \SHAR_EOF > 'README'
The MultiProcessor Simulator / Experimental Version 1.0
by Fe'lix E. Quevedo Stuva
Mesh Matrix Multiplication
This example uses the interprocess communication feature, simulating a Mesh
network. The basic algorithm was taken from Alk [1989] page 179.
The host program setups by loading the processor program and sending the
matrix dimension as messages. Then prepares data and sends the elements as
describe in the algorithm as messages of type 1 (horizontal) and type 2
(vertical). Finally it waits for the results at each processor.
The processor program after setup, waits for messages type 1 and 2. Once
received it operates the multiplication. After the given number of
operations, it sends to the host as a message of type 3.
The output attached shows the results of multiplying two matrices and
status of the processor after the execution.
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'mmlt_hst.c'" '(2092 characters)'
if test -f 'mmlt_hst.c'
then
echo shar: will not over-write existing file "'mmlt_hst.c'"
else
cat << \SHAR_EOF > 'mmlt_hst.c'
/* mmlt_hst.c
*
* Mesh Matrix Multiplication
*
* Host source code
* Felix E. Quevedo
* November 24, 1989.
*/
#define M 4
#define N 6
#define O 4
P(i, j)
int i, j;
{
return i*O+j;
}
main()
{
int i, j, k, l, f, t, max;
int mA[M][N]; /* data matrix */
int mB[N][O]; /* data matrix */
int mC[M][O]; /* output matrix */
if (mpdim()<M*O) {
printf("Requires a MPSim of size %d\n", M*O);
exit(); /* save # of processors */
}
for(i=0; i < M; i++) { /* for all ith matrix number */
for(j=0; j < O; j++) { /* for all jth matrix number */
l = P(i, j);
load("mmlt_prc",l); /* load processor */
k = M;
send(l, &k, sizeof(int), 11); /* send matrix */
k = N;
send(l, &k, sizeof(int), 12); /* send matrix */
k = O;
send(l, &k, sizeof(int), 13); /* send matrix */
}
}
/* prepare data and parameter for execution */
srandom(k = time() / 10); /* seed of random generator */
printf("Matrix A:\n");
for(i=0; i < M; i++) { /* for all ith matrix number */
for(j=0; j < N; j++) { /* for all jth matrix number */
mA[i][j] = random() / k; /* generate random integer */
printf("%3d ", mA[i][j]);
}
printf("\n");
}
printf("Matrix B:\n");
for(i=0; i < N; i++) { /* for all ith matrix number */
for(j=0; j < O; j++) { /* for all jth matrix number */
mB[i][j] = random() / k; /* generate random integer */
printf("%3d ", mB[i][j]);
send(P(0,j), &mB[i][j], sizeof(int), 2); /* send matrix */
}
printf("\n");
}
for(j=0; j < N; j++) { /* for all jth matrix number */
for(i=0; i < M; i++) { /* for all ith matrix number */
send(P(i,0), &mA[i][j], sizeof(int), 1); /* send matrix */
}
}
for(i=0; i<M*O; i++) {
recv(&f, &j, sizeof(int), &t, 3); /* wait for result */
mC[f/O][f%O] = j;
}
printf("Matrix C: A * B\n");
for(i=0; i < M; i++) { /* for all ith matrix number */
for(j=0; j < O; j++) { /* for all jth matrix number */
printf("%4d ", mC[i][j]);
}
printf("\n");
}
}
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'mmlt_prc.c'" '(843 characters)'
if test -f 'mmlt_prc.c'
then
echo shar: will not over-write existing file "'mmlt_prc.c'"
else
cat << \SHAR_EOF > 'mmlt_prc.c'
/* mmlt_prc.c
*
* Mesh Matrix Multiplication
*
* Processor source code
* Felix E. Quevedo
* November 24, 1989.
*/
int M, N, O;
P(i, j)
int i, j;
{
return i*O+j;
}
main()
{
int i, j, f, t;
int a, b, c;
int pi, ni, nj;
pi = mynode(); /* save processor index */
recv(&f, &M, sizeof(int), &t, 11); /* recv # of elements */
recv(&f, &N, sizeof(int), &t, 12); /* recv # of elements */
recv(&f, &O, sizeof(int), &t, 13); /* recv # of elements */
ni = pi / O;
nj = pi % O;
for(i = c = 0; i < N; i++) {
recv(&f, &b, sizeof(int), &t, 2); /* recv partition */
recv(&f, &a, sizeof(int), &t, 1); /* recv partition */
c += a*b;
if(ni < M) send(P(ni+1,nj), &b, sizeof(int), 2);
if(nj < O) send(P(ni,nj+1), &a, sizeof(int), 1);
}
send(-1, &c, sizeof(int), 3); /* send to host the result */
}
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'go.file'" '(20 characters)'
if test -f 'go.file'
then
echo shar: will not over-write existing file "'go.file'"
else
cat << \SHAR_EOF > 'go.file'
lh mmlt_hst
ls
st
q
SHAR_EOF
fi # end of overwriting check
echo shar: done with directory "'mmlt'"
cd ..
if test ! -d 'prim'
then
echo shar: creating directory "'prim'"
mkdir 'prim'
fi
echo shar: entering directory "'prim'"
cd 'prim'
echo shar: extracting "'prim.h'" '(635 characters)'
if test -f 'prim.h'
then
echo shar: will not over-write existing file "'prim.h'"
else
cat << \SHAR_EOF > 'prim.h'
/*------------------------------------------------------------------------------
Title: Prim's MST Algorithm for INTEL Hybercube Simulator
File: prim.h
Dscrp: Header file for Cube Simulator program.
Author: Felix E. Quevedo
Date: Oct. 1989
------------------------------------------------------------------------------*/
#include <math.h>
#define HPID 1
#define NPID 2
#define HNODE -1
#define HTYPE 10
#define NTYPE 20
#define NHTYPE 30
#define INF 0x7fffffff
#define NN 32
#define min(X,Y) X<Y?X:Y
lg2(x)
int x;
{
int i, j;
if(!x) return 0;
for(i=x, j=0; i!=1; i=i>>1, j++);
return j;
}
pw2(x)
int x;
{
return 1<<x;
}
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'README'" '(835 characters)'
if test -f 'README'
then
echo shar: will not over-write existing file "'README'"
else
cat << \SHAR_EOF > 'README'
The MultiProcessor Simulator / Experimental Version 1.0
by Fe'lix E. Quevedo Stuva
Prim's MST Algorithm for a Hypercube machine.
This example uses the interprocess communication feacture, simulating a
Hypercube machine.
The host setups by loading the processor program and sending the dimension
and partition of the graph. Then it waits for the node 0 to send the paths
of the MST.
The process program finds the minimum at each entry level and sends to its
parents. A parent receives from its childs their results and compares to
the one they obtained. The parent selects the smallest, after receiving from
all childs, the smallest one, and send to its parent the results, and so on.
If it is the node 0, it sends the new MST path to the host and the new entry
to its child, and its child to its child, up to the the leaf nodes.
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'prim_cm.c'" '(2095 characters)'
if test -f 'prim_cm.c'
then
echo shar: will not over-write existing file "'prim_cm.c'"
else
cat << \SHAR_EOF > 'prim_cm.c'
/*------------------------------------------------------------------------------
Title: Prim's MST Algorithm for MPSim Simulator
File: prim_cm.c
Dscrp: Cube manager program, generate random weighted graph, loads node
program to the simulator and waits for edges of the MST given by the
node 0.
Author: Felix E. Quevedo
Date: Oct. 1989
------------------------------------------------------------------------------*/
#include "prim.h"
main()
{
/* Cube system variables */
int type, cnt, node, pid, numnodes;
/* Application variables */
int wgt[NN][2], wgf[NN][NN], v[3];
int i, j, k, mx, n, cn;
numnodes = mpdim(); /* obtain nodes available */
printf("Parallelized Prim's MST Algorithm\n");
printf("By Felix E. Quevedo\n");
n = 16;
if(n<2||n>numnodes*2) exit(0);
cn = pw2(i=lg2(n-1)); /* cube nodes requiered */
printf("nodes:%d, cube nodes:%d\n", n, cn);
/* create random weighted graph and load cube nodes */
printf("\nWeighted graph:\n");
mx = random(); /* initial random number */
for(i=0; i<n; i++) { /* random weighted graph */
wgf[i][i]=INF;
for(j=i+1; j<n; j++) { /* random weigth creation */
k=(random()%mx)/10000000;
wgf[i][j]=k>1?k:INF;
wgf[j][i]=wgf[i][j];
}
for(; j<2*cn; j++) wgf[i][j]=INF; /* complete weighted graph */
for(j=0; j<n; /* pretty output */
printf((wgf[i][j]==INF?"*** ":"%3d "), wgf[i][j]),j++);
printf("\n");
wgf[i][0]=INF; /* initial entry node */
}
/* load cube nodes, prepare and send partition to cube nodes */
for(i=k=0; i<2*cn; i+=2) {
load("prim_node", k=i/2); /* load program to cube node */
/* send size of partition */
send(k, &n, sizeof(int), HTYPE);
for(j=0; j<n; j++) { /* prepare partition */
wgt[j][0]=wgf[j][i];
wgt[j][1]=wgf[j][i+1];
} /* send partition */
send(k, wgt, NN*2*sizeof(int), HTYPE);
}
/* wait for node to solve MST */
printf("\nMinimum Spanning Tree:\n");
for(i=0; i<n-1; i++) {
recv(&node, v, sizeof(int)*3, &type, NHTYPE);
printf("HOST path:%2d-%2d wgt:%3d\n", v[0],v[1],v[2]);
}
printf("Bye, bye...\n");
}
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'prim_node.c'" '(2540 characters)'
if test -f 'prim_node.c'
then
echo shar: will not over-write existing file "'prim_node.c'"
else
cat << \SHAR_EOF > 'prim_node.c'
/*------------------------------------------------------------------------------
Title: Prim's MST Algorithm for MPSim Simulator
File: prim_node.c
Dscrp: Cube node program, obtain from manager the partition of the grap to
process with the Prim's MST algorithm.
Author: Felix E. Quevedo
Date: Oct. 1989
------------------------------------------------------------------------------*/
#include "prim.h"
main()
{
/* Cube System Variables */
int node;
int type, rcnt, rnode, rpid;
int numnodes;
/* Application Variables */
int i, j, k, n;
int from, to, dad, mlen;
int vec[3], rvc[3], wgt[NN][2], bs[2];
/* SetUp system variables */
node = mynode();
numnodes = mpdim();
/* receive from Host size of graph */
recv(&rpid, &n, sizeof(int), &type, HTYPE);
/* SetUp application variables */
mlen=3*sizeof(int); /* message length */
from=node?lg2(pw2(lg2(node)+1)):0; /* initial child node index */
to=from+lg2(n/2)-lg2(2*node); /* final child node index */
dad=(node)?node-pw2(i=lg2(node)):HNODE; /* parent node index */
bs[0]=bs[1]=0; /* initial base */
/*printf("NODE %d: from %d, to %d, dad %d\n", node, from, to);*/
/* receive from Host graph partition */
recv(&rpid, wgt, sizeof(int)*2*NN, &type, HTYPE);
/* Loop For until all graph nodes have been on base */
for(i=0; i<n-1; i++) {
/*printf("%d:%d processing...\n", node, getpid());*/
/* local minimum */
k=(wgt[bs[1]][1]<wgt[bs[0]][0])?1:0;
vec[0]=bs[k]; /* save minimum index from */
vec[1]=2*node+k; /* save minimum index to */
vec[2]=wgt[bs[k]][k]; /* save minimum weight */
for(j=from; j<to; j++) { /* receive from child their minimum */
recv(&rpid, rvc, mlen, &type, NTYPE);
if(rvc[2]<vec[2]) /* child has minimum: save it */
for(k=0; k<3; vec[k]=rvc[k++]);
}
/* send and receive from parent */
if(node){ /* if not first cube node */
send(dad, vec, mlen, NTYPE);
recv(&rpid, vec, mlen, &type, NTYPE);
/* if parent has minimum: change base */
if(wgt[vec[0]][0]<wgt[bs[0]][0]) bs[0]=vec[0];
if(wgt[vec[0]][1]<wgt[bs[1]][1]) bs[1]=vec[0];
}
else { /* if first cube node: send to HOST */
send(HNODE, vec, mlen, NHTYPE);
vec[0]=vec[1]; /* save new base! */
}
k=vec[0]-2*node; /* if I have base: fill with INF */
if(k==1||k==0) for(j=0; j<n*2; wgt[j++][k]=INF);
for(j=from;j<to; /* send to childs new base */
/*printf("%d: send to %d\n", node, node+pw2(j)),*/
send(node+pw2(j++), vec, mlen, NTYPE));
}
}
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'Makefile'" '(261 characters)'
if test -f 'Makefile'
then
echo shar: will not over-write existing file "'Makefile'"
else
cat << \SHAR_EOF > 'Makefile'
#
# Multiprocessor Simulator MAKEFILE
#
COMP = cc -O
MLIB = ../../libmp.a -lm
all:
$(COMP) -o prim_cm prim_cm.c $(MLIB)
$(COMP) -o prim_node prim_node.c $(MLIB)
go:
../../mpsim 8 < go.file
prt:
ptroff -ms -h README
clean:
rm prim_cm prim_node MPSYSLOG
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'go.file'" '(13 characters)'
if test -f 'go.file'
then
echo shar: will not over-write existing file "'go.file'"
else
cat << \SHAR_EOF > 'go.file'
lh prim_cm
s
SHAR_EOF
fi # end of overwriting check
echo shar: done with directory "'prim'"
cd ..
if test ! -d 'tmx'
then
echo shar: creating directory "'tmx'"
mkdir 'tmx'
fi
echo shar: entering directory "'tmx'"
cd 'tmx'
echo shar: extracting "'present'" '(5900 characters)'
if test -f 'present'
then
echo shar: will not over-write existing file "'present'"
else
cat << \SHAR_EOF > 'present'
.nr PO 1.5i
.sp 2i
.ft B
.ce 2
The MultiProcessor Simulator\(co / Experimental Version 1.0
.sp 2
.ft R
by F\*'elix E. Quevedo Stuva
.sp 4
.ad b
.fi
.ls 2
.NH 1
Nice test program
.PP
This example does not other objective to just test the communication
and share memory features of the simulator. In general allocates
share memory segment and sends a round ribbon greeting message.
.PP
The host program (hih), loads the processor program (hi)
to the available processors. Then creates the share memory segment
and saves the pointer. Finally sends a greeting message to processor 0
of type 1, and waits for a message of type number of proecessors plus 1.
Once the message is received it displays the content of the share memory
segment.
.PP
The processor programs, waits for a message of any type. Once received
it attaches the shere memory segment and updates an area of index equal
to the processor number with the processor number. Finally sends a message to
the next processor after incrementing the previous type received in 1.
If the processor is the last it send it to the host.
.bp
.sp 5
.NH 2
Maximum Finding Algorithm CRWR SM MIMD.
.PP
This example uses the share memory feature of the MPsim. It also intends
to show how to make a user semaphore and simulate a SIMD machine.
This algorithm is known to be the fastest.
.PP
The host program creates the share segment, prepares data, and loads the
processor program one at a time. Once all the processors are loaded, the
host wiats for all the processors to complete the first step. Once all the
processors has completed the first step, it resets the step flag and
waits for the second step. Finally displays the results on the
corresponding share memory area.
.PP
The processor program in the first step obtains the maximum of the two
assigned values, marking the looser vector. Then increments the flag a
and if its a second step processor, waits for the host to reset the flag.
Once the processor resets the flag verifies if the assigned looser index
value is winner (not looser) to save the maximum value on the correspponding
share memory area.
.bp
.sp 5
.NH 2
Maximum Finding Algorithm for a Binary Tree machine, mapped on a
Linear Array Computer.
.PP
This example uses the interprocess communication feature. It also simulates
the mapping of a Binary Tree Machine on a simulated Linear Array Computer.
The algorithm is known to be Cost Optimal.
.PP
The host program prepares data, load to all the processor available the
processor program and send to each one the assigned partition. Finally
waits for the result as a messages from the root processor.
.PP
The processor program receives the partition, finds the maximum and send
the result to its parent. At this moment the mapping of a binary tree
machine on a linear array computer, proposed by Sarkar and Deo [1988], enters
in effect. Depending on the stage algorithm it will receive, process and
send; or will receive and send. Finally if the processor is the mapped root
of the binary tree, send the result to the host process.
.PP
The output attached to the implementation, shows step by step how the
communication is performed. Observe how the execution of the processors (nodes)
are completely asynchronical at the begining.
.bp
.sp 5
.NH 2
Mesh Matrix Multiplication
.PP
This example uses the interprocess communication feature, simulating a Mesh
network. The basic algorithm was taken from Alk [1989] page 179.
.PP
The host program setups by loading the processor program and sending
the matrix dimension as messages. Then prepares data and sends the elements as
describe in the algorithm as messages of type 1 (horizontal) and type 2
(vertical). Finally it waits for the results at each processor.
.PP
The processor program after setup, waits for messages type 1 and 2. Once received
it operates the multiplication. After the given number of operations, it sends
to the host as a message of type 3.
.PP
The output attached shows the results of multiplying two matrices and
status of the processor after the execution.
.bp
.sp 5
.NH 2
Prim's MST Algorithm for a Hypercube machine.
.PP
This example uses the interprocess communication feacture, simulating a
Hypercube machine.
.PP
The host setups by loading the processor program and sending the dimension
and partition of the graph. Then it waits for the node 0 to send the paths
of the MST.
.PP
The process program finds the minimum at each entry level and sends to its
parents. A parent receives from its childs their results and compares to
the one they obtained. The parent selects the smallest, after receiving from
all childs, the smallest one, and send to its parent the results, and so on.
If it is the node 0, it sends the new MST path to the host and the new entry
to its child, and its child to its child, up to the the leaf nodes.
.bp
.sp 5
.NH 1
Implementation
.PP
The simulator has been implemented on UNIX C. It is transportability
has been proved between a SUN 3/60 and a VaxStation II. In both cases
the main modules were working, but with no guarantee of full feature
capacity.
.PP
The implementation consist of the following files:
.IP a)
mpsim.c: the interactive module. Contains the
.I main()
and the
.I _stop_handler()
functions.
.IP b)
mplib.c: the common function library. Contains the
.I
mpopen(), mptime(), mpprint(), mperro(), mehost(), _mplnode()
.R
functions.
.IP c)
mpsys.c: the system function library. Contains the
.I
_handler_req(), _handler_chl(), _handler_sys(), _mpinit(), _mpkill(),
_mplhost(), _mprun(), _mpstart(), _mpstatus(), _mpterm(),
.R and
_mpwait()
.R
functions.
.IP d)
mpusr.c: the user function library. Contains the
.I
_pause_handler()*, _getpt(), _trchd(), _imhost(), mprnd(), mpdim(),
mynode(), load(), _mvstr(), _rcvm(), recv(), trcv()*, send(),
probe(), crtshm(), attshm(), detshm()
.R and
slpmsq()*
.R
functions. The ones marked with a * are still on experimental phase.
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'README'" '(1199 characters)'
if test -f 'README'
then
echo shar: will not over-write existing file "'README'"
else
cat << \SHAR_EOF > 'README'
The MultiProcessor Simulator / Experimental Version 1.0
by Fe'lix E. Quevedo Stuva
Maximum Finding Algorithm for a Binary Tree machine, mapped on a
Linear Array Computer.
This example uses the interprocess communication feature. It also simulates
the mapping of a Binary Tree Machine on a simulated Linear Array Computer.
The algorithm is known to be Cost Optimal.
The host program prepares data, load to all the processor available the
processor program and send to each one the assigned partition. Finally
waits for the result as a messages from the root processor.
The processor program receives the partition, finds the maximum and send
the result to its parent. At this moment the mapping of a binary tree
machine on a linear array computer, proposed by Sarkar and Deo [1988], enters
in effect. Depending on the stage algorithm it will receive, process and
send; or will receive and send. Finally if the processor is the mapped root
of the binary tree, send the result to the host process.
The output attached to the implementation, shows step by step how the
communication is performed. Observe how the execution of the processors (nodes)
are completely asynchronical at the begining.
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'tmx_hst.c'" '(1205 characters)'
if test -f 'tmx_hst.c'
then
echo shar: will not over-write existing file "'tmx_hst.c'"
else
cat << \SHAR_EOF > 'tmx_hst.c'
/* tmx_hst.c
*
* Cost Optimal algorithm for find maximum with
* Mapping of Binary-Tree Machine to Linear Array.
*
* Host source code
* Felix E. Quevedo
* November 17, 1989.
*/
#define NN 256
main()
{
int i, j, k, l, f, t, max;
int vec[NN]; /* data vector */
if ((f = mpdim())<32) exit(); /* save # of processors */
/* prepare data and parameter for execution */
srandom(l = time() / 100); /* seed of random generator */
for(i=k=0; i < NN; i++) { /* for all vector number */
vec[i] = random() / l; /* generate random integer */
}
printf("Input Vector:\n");
for(i=0; i < NN-14;) {
for(j=0; j < 22; printf("%3d ", vec[i++]), j++);
printf("\n");
}
for(j=0; j < 14; printf("%3d ", vec[i++]), j++);
printf("\n");
load("tmx_prc",-1); /* load processor */
k = NN / f;
printf("HOST: send partition of size %d to %d processors\n", k, f);
for(i=0; i < f;
send(i, &k, sizeof(int), 1), /* send # of elements */
send(i, &vec[k*i], k*sizeof(int), 2), /* send vector */
i++
); /* send messages to processors */
printf("HOST: wait for result\n");
recv(&f, &max, sizeof(int), &t, 0); /* wait for result */
printf("HOST: Maximum %d\n", max);
}
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'tmx_prc.c'" '(1700 characters)'
if test -f 'tmx_prc.c'
then
echo shar: will not over-write existing file "'tmx_prc.c'"
else
cat << \SHAR_EOF > 'tmx_prc.c'
/* tmx_prc.c
*
* Cost Optimal algorithm for find maximum with
* Mapping of Binary-Tree Machine to Linear Array.
*
* Processor source code
* Felix E. Quevedo
* November 17, 1989.
*/
#define pw2(X) (1<<X)
lg2(x) /* simple function for log base 2 */
int x;
{
int i;
if(x) for(i=0; x>>i+1; i++);
return i;
}
main()
{
int i, j, k, l, f, t;
int ni, ne, np, mx, xm;
int vec[20];
ni = mynode(); /* save processor index */
np = mpdim(); /* save number of processors */
recv(&f, &ne, sizeof(int) , &t, 1); /* recv # of elements */
recv(&f, vec, sizeof(int)*ne, &t, 2); /* recv partition */
printf("NODE %d: received vector ", ni);
for(i = mx = 0; i < ne;
mx = mx > vec[i]? mx : vec[i], /* find partition maximum */
printf("%3d ", vec[i]),
i++);
printf("\n");
j = lg2(np); /* compute # of max steps */
for(i = 0; i < j; i++) {
k = (ni+1) / pw2(i); /* compute x = (j mod 2^i-1) */
l = k * pw2(i); /* compute y = x * 2^i-1 */
if( (ni+1) == l && k % 2) {
printf("NODE %d: send max %d to %d\n", ni, mx, ni+1);
send(ni+1, &mx, sizeof(int), 3);
}
else {
if( (ni+1) != l) {
printf("NODE %d: waiting to communicate\n", ni);
recv(&f, &xm, sizeof(int), &t, 3);
printf("NODE %d: send max %d to %d\n", ni, xm, ni+1);
send(ni+1, &xm, sizeof(int), t);
}
else {
printf("NODE %d: waiting to process\n", ni);
recv(&f, &xm, sizeof(int), &t, 3);
mx = mx > xm? mx : xm;
}
}
}
if(ni == mpdim()-1) /* if I'm the last processor */
send(-1, &mx, sizeof(int), t); /* send to host the result */
}
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'Makefile'" '(249 characters)'
if test -f 'Makefile'
then
echo shar: will not over-write existing file "'Makefile'"
else
cat << \SHAR_EOF > 'Makefile'
#
# Multiprocessor Simulator MAKEFILE
#
COMP = cc -O
MLIB = ../../libmp.a
all:
$(COMP) -o tmx_hst tmx_hst.c $(MLIB)
$(COMP) -o tmx_prc tmx_prc.c $(MLIB)
go:
../../mpsim < go.file
prt:
ptroff -ms -h README
clean:
rm tmx_hst tmx_prc MPSYSLOG
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'go.file'" '(18 characters)'
if test -f 'go.file'
then
echo shar: will not over-write existing file "'go.file'"
else
cat << \SHAR_EOF > 'go.file'
lh tmx_hst
s
st
q
SHAR_EOF
fi # end of overwriting check
echo shar: done with directory "'tmx'"
cd ..
echo shar: extracting "'Makefile'" '(593 characters)'
if test -f 'Makefile'
then
echo shar: will not over-write existing file "'Makefile'"
else
cat << \SHAR_EOF > 'Makefile'
#
# Multiprocessor Simulator MAKEFILE
#
all:
cd hi ; make; cd ..
cd max ; make; cd ..
cd mmlt; make; cd ..
cd prim; make; cd ..
cd tmx ; make; cd ..
go:
cd hi ; make go; cd ..
cd max ; make go; cd ..
cd mmlt; make go; cd ..
cd prim; make go; cd ..
cd tmx ; make go; cd ..
prt:
ptroff -ms -h README
cd hi ; make prt; cd ..
cd max ; make prt; cd ..
cd mmlt; make prt; cd ..
cd prim; make prt; cd ..
cd tmx ; make prt; cd ..
clean:
cd hi ; make clean; cd ..
cd max ; make clean; cd ..
cd mmlt; make clean; cd ..
cd prim; make clean; cd ..
cd tmx ; make clean; cd ..
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'README'" '(481 characters)'
if test -f 'README'
then
echo shar: will not over-write existing file "'README'"
else
cat << \SHAR_EOF > 'README'
The MultiProcessor Simulator / Experimental Version 1.0
by Fe'lix E. Quevedo Stuva
TEST PROGRAMS
It is not the purpose of the programs to explain an algorithm, just
the implementation method in a very general way.
CONTENTS
hi - Nice test program
max - Maximum Finding Algorithm CRWR SM MIMD.
mmlt - Mesh Matrix Multiplication
prim - Prim's MST Algorithm for a Hypercube machine.
tmx - Maximum Finding Algorithm for a Binary Tree machine,
mapped on a Linear Array Computer.
SHAR_EOF
fi # end of overwriting check
echo shar: done with directory "'tsts'"
cd ..
echo shar: extracting "'README'" '(538 characters)'
if test -f 'README'
then
echo shar: will not over-write existing file "'README'"
else
cat << \SHAR_EOF > 'README'
This is Felix Quevedo's Multiprocessor simultator package which he wrote
here at the University of Miami. I've provided a nroff'ed version of his
documentation, for those without the ms macros, or perhaps without *roff
itself.
The package was developed on a Sun 3 running SunOS 3.5 and has been
tested on Sun 4 running SunOS 4.0.3, a vax running Ultrix 3.0, and
a mac running A/UX 1.1 The Makefile needs to be changed for non-SunOS
systems.
Felix can be reached at fqs@mthvax.cs.miami.edu, but he can not provide
any support.
aem
SHAR_EOF
fi # end of overwriting check
echo shar: done with directory "'mpsim'"
cd ..
# End of shell archive
exit 0