Category : Files from Magazines
Archive   : DDJ-9008.ZIP
Filename : ELLIS.LST

 
Output of file : ELLIS.LST contained in archive : DDJ-9008.ZIP
_PARALLEL EXTENSIONS TO C_
by Graham K. Ellis

[LISTING ONE]

/**** File: proto.h -- Contains the function protocols ****/
/* include mytypes.h first....I don't do any checking */

source(Process *, Channel *, UBYTE *);
output(Process *, Channel *);
pipe(Process *, Channel *, Channel *);

/* end proto.h */


[LISTING TWO]

/**** mytypes.h ****/

#define BUFF_SIZE 256 /* the max. char buffer size */
#define NUM_PIPES BUFF_SIZE /* the number of sorting processes */
#define PIPE_STACK 128 /* stack space for the processes*/
#define INPUT_STACK 4096
#define OUTPUT_STACK 4096

#define TRUE 1 /* some simple defines */
#define FALSE 0

typedef int BOOL;
typedef unsigned char UBYTE;



[LISTING THREE]

; multisort.nif -- This is the file the transputer uses to load the network.
; The parameters are:
;----------------------------------------------------------------------
; node number | processor reset | link 0 | link1 | link 2| link 3 |
; | from processor |---------------------------------|
; | number Rxx | The number here is the processor|
; | | number we connect to. |
;----------------------------------------------------------------------
;
1, multisort, R0, 0, , , 2;
2, multisort, R1, , ,1, ;



[LISTING FOUR]

/**** File: buffers.c -- Contains the funtions:
** source(Process *, Channel *, UBYTE *)
** output(Process *, Channel *)
** pipe(Process *, Channel *, Channel *)
****/

#include
#include
#include "mytypes.h" /* include in this order... */
#include "proto.h"

/**** source(Process *p, Channel *out, UBYTE *ch)
** Output a single character at a time from the buffer pointed to by ch
** on the channel out. Terminate when '\0' or whole buffer is sent.
** Process *p is used by the ProcAlloc() routine. You must have this
** in the parameter list for a parallel process.
****/
source(Process *p, Channel *out, UBYTE *ch)
{
BOOL inline = TRUE;
int i;
for(i=0; i if(inline)
switch(ch[i]) {
case '\0': /* this is the EOL for us */
ChanOutChar(out, ch[i]);
inline = FALSE;
break;
default:
ChanOutChar(out, ch[i]);
}
}
}

/**** output(Process *p, Channel *in)
** Read a single character at at time on channel in and send it to stdout.
** Terminate when '\0' is received. Process *p is used by the ProcAlloc()
** routine. You must have this in the parameter list for a parallel process.
****/
output(Process *p, Channel *in)
{
UBYTE ch;
BOOL running = TRUE;

while(running) {
ch = ChanInChar(in);
switch(ch) {
case '\0':
putchar('\n');
running = FALSE;
break;
case '\n':
break;
default:
putchar(ch);
}
}
}

/**** pipe(Process *p, Channel *in, Channel *out)
** Reads a single character on channel in and falls into a loop where next
** character is read and compared in an ASCII sense to the current charater.
** Character with the lowest ASCII value is forwarded on channel out. Loop
** terminates on a '\0' character. The "stored" character is sent before the
** '\0' is propagated. Process *p is used by the ProcAlloc() routine.
** You must have this in the parameter list for a parallel process.
****/
pipe(Process *p, Channel *in, Channel *out)
{
UBYTE highest, next;
BOOL running;
BOOL ns_node;

if(_node_number == 1) /* If we are the root node only do the */
ns_node = FALSE; /* main loop once. If we are a non- */
else /* root node, loop forever. */
ns_node = TRUE;
do {
running = TRUE;
highest = ChanInChar(in);
while(running) {
next = ChanInChar(in);
switch(next) {
case '\0' :
ChanOutChar(out, highest);
running = FALSE;
break;
default :
if(next > highest) {
ChanOutChar(out, highest);
highest = next;
}
else
{
ChanOutChar(out, next);
}
}
}
ChanOutChar(out, '\0');
} while(ns_node);
}



[LISTING FIVE]

/***************************************************************************
** sort.c -- Compiles under Logical Systems Transputer C compiler Versions
** 88.4, 89.1. A single transputer, multi-process ASCII sorting routine. This
** shows how to allocate and deallocate parallel (multi-tasking) processes on
** a single transputer. This algorithm is modelled after the sorting example
** in the INMOS occam Transputer Development System (TDS). The algorithm
** relies on having as many parallel processes as the maximum character
** buffer size. Data is sent to a FIFO-like array of input-ouput buffers. If
** the next letter read in is less than (in an ASCII sense) the current letter
** in the buffer, it is forwarded to the next buffer, otherwise the current
** data is forwarded. The program will shut down when a ~ is the first
** character in any input line.
** Must link in file buffers.c (after compilation of course..)
** Programed by: G.K.Ellis, Smart Materials and Structures Laboratory,
** Mechanical Engineering Department, Virginia Tech, Blacksburg, VA 24061
*****************************************************************************/

#include
#include /* the LSC defines are here */
#include "mytypes.h" /* include in this order... */
#include "proto.h"

/**** MAIN PROGRAM ****/
void main()
{
UBYTE ch[BUFF_SIZE]; /* string buffer */
BOOL active = TRUE;
int i;
Channel *thru[NUM_PIPES + 1]; /* internal channels */
Process *p[NUM_PIPES + 3]; /* process pointers */
while(active) {
fgets(ch, BUFF_SIZE-1, stdin); /* get the input line */
/* stop char is ~ as first letter */
if(ch[0] == '~') active = 0;
/* allocate the channels, NULL is returned if no memory */
for(i = 0; i< NUM_PIPES + 1; i++) {
if((thru[i] = ChanAlloc()) == NULL)
printf("No memory for Channel thru[%d]\n", i);
}

/* allocate the processes, NULL is returned if no memory */
p[0] = ProcAlloc(source, INPUT_STACK, 2, thru[0], ch);
for(i = 1; i < NUM_PIPES+1; i++)
p[i] = ProcAlloc(pipe, PIPE_STACK, 2, thru[i-1], thru[i]);
p[NUM_PIPES+1] = ProcAlloc(output, OUTPUT_STACK, 1, thru[NUM_PIPES]);
p[NUM_PIPES+2] = NULL;
/* check to see if all processes were allocated successfully */
for(i = 0; i < NUM_PIPES + 2; i++)
if(!p[i])
printf("No memory for Process p[%d]\n", i);
ProcParList(p); /* Run a NULL terminated list of pointers */
/* to processes. These are all low-pri */
/* Since we allocate these each time through the loop, we needto
** deallocate them here otherwise, we will run out of memory */
for(i = 0; i < NUM_PIPES + 1; i++)
ChanFree(thru[i]);
for(i = 0; i < NUM_PIPES + 2; i++)
ProcFree(p[i]);
}
printf("done!\n"); /* all done... */
}




[LISTING SIX]

/*************************************************************************
** multisort.c -- A two transputer version of a simple parallel ASCII sorting
** routine. This program will work on either node. Developed for Logical
** Systems Transputer C compiler (LSC) versions 88.4 or 89.1. Must link with
** buffers.c. Programmed by: G.K.Ellis, Smart Materials and Structures
** Laboratory, Mechanical Engineering Department, Virginia Tech,
** Blacksburg, VA 24061
**************************************************************************/

#include
#include
#include "mytypes.h"
#include "proto.h"

/**** MAIN PROGRAM ****/
void main()
{
UBYTE ch[BUFF_SIZE]; /* string buffer */
BOOL active = TRUE;
int i;
Channel *in, *out; /* link channels */
Process *feeder, *sink; /* hi-priority processes */
Channel *thru[NUM_PIPES - 1]; /* internal soft channels */
Process *p[NUM_PIPES - 2]; /* low-priority processes */
if(_node_number == 1) { /* We are the root node */
in = LINK3IN; /* these are our links */
out = LINK3OUT;
while(active) {
fgets(ch, BUFF_SIZE-1, stdin); /* get the input line */
/* stop char is ~ as first letter */
if(ch[0] == '~') active = 0;
/* set up the processes */
feeder = ProcAlloc(source, INPUT_STACK, 2, out, ch);
sink = ProcAlloc(output, OUTPUT_STACK, 1, in);
/* Check that ProcAlloc() doesn't return a NULL, but
** since we KNOW from the example sort.c this is ok */

/* run the feeder and sink processes in parallel */
ProcPar(feeder, sink, NULL);

/* free the previously allocated processes */
/* note we do this each time through the loop */
/* hey, it's only an example */
ProcFree(feeder);
ProcFree(sink);
}
printf("done!\n");
exit(0); /* finis! */
} else { /* if we are the non-root */
in = LINK2IN; /* node, run this as main() */
out = LINK2OUT; /* these are our links */
for(i = 0; i < NUM_PIPES - 1; i ++) { /* allocate soft channels */
thru[i] = ChanAlloc();
}
/* allocate soft channel pipe processes */
for(i = 0; i < NUM_PIPES - 2; i++)
p[i] = ProcAlloc(pipe, PIPE_STACK, 2, thru[i], thru[i+1]);
/* allocate the processes with the links */
feeder = ProcAlloc(pipe, PIPE_STACK, 2, in, thru[0]);
sink = ProcAlloc(pipe, PIPE_STACK, 2, thru[NUM_PIPES-2], out);
/* If we want to check the pointer returned from ProcAlloc(),
** that is extra programming on a non-root node. Therefore,
** don't try to printf() from a non-root node. There is a
** non-server node _ns_printf() that does simple ASCII
** transfers out a channel (link), but this generally requires
** extra effort to communicate back to the server */

/* Let's allocate these asynchronously */
ProcRunHigh(sink); /* run the hardware links at high pri */
ProcRunHigh(feeder);
for(i = 0; i < NUM_PIPES - 2; i++)
ProcRunLow(p[i]); /* and soft channels at low pri */
_ns_exit(); /* we must exit like this on non-server*/
/* node or we will exit from the */
/* main() program */
/* ProcRunHigh() and ProcRunLow() spawn new processes asyncronously
** from main(). The _ns_exit() does a STOPP on the main process
** leaving the two spawned processes. The exit() routine trys
** to send a message back to the server running on the PC. If it
** isn't there, i.e. you're not the root, you've got problems.
** Note also, if we are not the root node, we never terminate
** and restart the pipe processes... we just run the processes ! */
}
}


[Example 1: Actions performed by the single-processor
implementation of the sorting routine]


Root Transputer:

SEQUENTIAL
- Read in line of text and store in character buffer.
- Allocate channels and processes.
PARALLEL
- Send out a character at a time to the first pipe process.
- In 256 parallel pipe processes: read in a character then
read a new character, forward the character with the
lowest ASCII value.
- Read in one character at a time from last pipe buffer
and write it to the screen.
- Deallocate channels and processes.



[Example 2: A rectangle represents a transputer and the
circles represent concurrent processes]


Root Transputer:

SEQUENTIAL
- Read in line of text and store in character buffer.
- Allocate channels and processes.
PARALLEL
- Send out a character at a time to the first buffer.
- Read in a character at a time and write it to the screen.
- Deallocate channels and processes.

Transputer Node 1:

SEQUENTIAL
- Allocate channels and processes.
PARALLEL
- Read in data from link a character at a time, sort, forward to
next pipe process.
- In 254 parallel pipe processes: read in a character then
read a new character, forward the character with the
lowest ASCII value.
- Read in data from pipe process sort, forward data to
root transputer.




[Figure 1: Channel Communication ]

buffer(Process *p, Channel *in, *out) /* the Procees *p is used by */
{ /* ProcAlloc() */
int data;

while(1) {
data = ChanInInt(in);
ChanOutInt(out, data);
}
}




[Figure 2: Multiplexer using the channel alternative]

mux(Process *p, Channel *in1, *in2, *out)
{
int data, index;

while(1) {
index = ProcAlt(in1, in2, NULL); /* return offset into chan list */
switch(index) {
case 0: /* channel in1 */
data = ChanInInt(in1);
ChanOutInt(out, data);
break;
case 1: /* channel in2 */
data = ChanInInt(in2);
ChanOutInt(out, data);
break;
}
}
}


[Figure 3: Two parallel processes code fragment]


Process *p1, *p2; /* Process and Channel are defined in */
Channel *in, *thru, *out; /* conc.h */

in = ChanAlloc(); /* internal channel allocation */
out = ChanAlloc(); /* we should check the return values here */
thru = ChanAlloc(); /* NULL returned if allocation unsuccessful */

p1 = ProcAlloc(buffer, STACK, 2, in, thru); /* allocate space for the */
p2 = ProcAlloc(buffer, STACK, 2, thru, out); /* processes p1, p2 */
ProcPar(p1, p2, NULL); /* run them in parallel */






  3 Responses to “Category : Files from Magazines
Archive   : DDJ-9008.ZIP
Filename : ELLIS.LST

  1. Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!

  2. This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.

  3. But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/