home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / drdobbs / 1990 / 08 / ellis.lst < prev    next >
File List  |  1990-06-20  |  14KB  |  415 lines
  1. _PARALLEL EXTENSIONS TO C_
  2. by Graham K. Ellis
  3.  
  4. [LISTING ONE]
  5.  
  6. /**** File: proto.h -- Contains the function protocols ****/
  7. /* include mytypes.h first....I don't do any checking */
  8.  
  9. source(Process *, Channel *, UBYTE *);
  10. output(Process *, Channel *);
  11. pipe(Process *, Channel *, Channel *);
  12.  
  13. /* end proto.h */
  14.  
  15.  
  16. [LISTING TWO] 
  17.  
  18. /**** mytypes.h ****/
  19.  
  20. #define BUFF_SIZE    256       /* the max. char buffer size */
  21. #define NUM_PIPES    BUFF_SIZE  /* the number of sorting processes */
  22. #define PIPE_STACK    128        /* stack space for the processes*/
  23. #define INPUT_STACK     4096
  24. #define OUTPUT_STACK     4096
  25.  
  26. #define TRUE        1       /* some simple defines */
  27. #define FALSE        0
  28.  
  29. typedef int                BOOL;
  30. typedef unsigned char    UBYTE;
  31.  
  32.  
  33.  
  34. [LISTING THREE]
  35.  
  36. ;  multisort.nif -- This is the file the transputer uses to load the network.
  37. ;  The parameters are:
  38. ;----------------------------------------------------------------------
  39. ; node number   |   processor reset | link 0 | link1 | link 2| link 3 |
  40. ;               |   from processor  |---------------------------------|
  41. ;               |   number Rxx      | The number here is the processor|
  42. ;               |                   | number we connect to.           |
  43. ;----------------------------------------------------------------------
  44. ;
  45. 1, multisort, R0, 0, , , 2;
  46. 2, multisort, R1,  , ,1,  ;
  47.  
  48.  
  49.  
  50. [LISTING FOUR]
  51.  
  52. /**** File: buffers.c -- Contains the funtions: 
  53. **      source(Process *, Channel *, UBYTE *)
  54. **    output(Process *, Channel *)
  55. **    pipe(Process *, Channel *, Channel *)
  56. ****/
  57.  
  58. #include <stdio.h>
  59. #include <conc.h>
  60. #include "mytypes.h"        /* include in this order...    */
  61. #include "proto.h"
  62.  
  63. /**** source(Process *p, Channel *out, UBYTE *ch)
  64. **    Output a single character at a time from the buffer pointed to by ch
  65. **    on the channel out.  Terminate when '\0' or whole buffer is sent.
  66. **    Process *p is used by the ProcAlloc() routine. You must have this
  67. **    in the parameter list for a parallel process.
  68. ****/
  69. source(Process *p, Channel *out, UBYTE *ch)
  70. {
  71.     BOOL inline = TRUE;
  72.     int i;
  73.     for(i=0; i<BUFF_SIZE; i++) {
  74.         if(inline)
  75.             switch(ch[i]) {
  76.                 case '\0':   /* this is the EOL for us */
  77.                     ChanOutChar(out, ch[i]);
  78.                     inline = FALSE;
  79.                     break;
  80.                 default:
  81.                     ChanOutChar(out, ch[i]);
  82.             }
  83.     }
  84. }    
  85.  
  86. /**** output(Process *p, Channel *in)
  87. **   Read a single character at at time on channel in and send it to stdout.
  88. **   Terminate when '\0' is received. Process *p is used by the ProcAlloc() 
  89. **   routine. You must have this in the parameter list for a parallel process.
  90. ****/
  91. output(Process *p, Channel *in)
  92. {
  93.     UBYTE ch;
  94.     BOOL running = TRUE;
  95.     
  96.     while(running) {
  97.         ch = ChanInChar(in);
  98.         switch(ch) {
  99.             case '\0':
  100.                 putchar('\n'); 
  101.                 running = FALSE;
  102.                 break;
  103.             case '\n':
  104.                 break;
  105.             default:
  106.                 putchar(ch);
  107.         }
  108.     }
  109. }
  110.  
  111. /**** pipe(Process *p, Channel *in, Channel *out)
  112. **  Reads a single character on channel in and falls into a loop where next 
  113. **  character is read and compared in an ASCII sense to the current charater. 
  114. **  Character with the lowest ASCII value is forwarded on channel out. Loop 
  115. **  terminates on a '\0' character.  The "stored" character is sent before the
  116. **  '\0' is propagated. Process *p is used by the ProcAlloc() routine. 
  117. **  You must have this in the parameter list for a parallel process.
  118. ****/
  119. pipe(Process *p, Channel *in, Channel *out)
  120. {
  121.     UBYTE highest, next;
  122.     BOOL running;
  123.     BOOL ns_node;
  124.  
  125.     if(_node_number == 1)     /* If we are the root node only do the */
  126.         ns_node = FALSE; /* main loop once.  If we are a non-   */
  127.     else             /* root node, loop forever.            */
  128.         ns_node = TRUE;
  129.     do {
  130.         running = TRUE;
  131.         highest = ChanInChar(in);
  132.         while(running) {
  133.             next = ChanInChar(in);
  134.             switch(next) {
  135.                 case '\0' :
  136.                     ChanOutChar(out, highest);
  137.                     running = FALSE;
  138.                     break;
  139.                 default :
  140.                     if(next > highest) {
  141.                         ChanOutChar(out, highest);
  142.                         highest = next;
  143.                     }
  144.                     else
  145.                     {
  146.                         ChanOutChar(out, next);
  147.                     }
  148.             }
  149.         }
  150.         ChanOutChar(out, '\0');
  151.     } while(ns_node);
  152. }
  153.  
  154.  
  155.  
  156. [LISTING FIVE]
  157.  
  158. /***************************************************************************
  159. **  sort.c -- Compiles under Logical Systems Transputer C compiler Versions 
  160. **  88.4, 89.1. A single transputer, multi-process ASCII sorting routine. This
  161. **  shows how to allocate and deallocate parallel (multi-tasking) processes on
  162. **  a single transputer. This algorithm is modelled after the sorting example 
  163. **  in the INMOS occam Transputer Development System (TDS). The algorithm 
  164. **  relies on having as many parallel processes as the maximum character 
  165. **  buffer size. Data is sent to a FIFO-like array of input-ouput buffers. If
  166. **  the next letter read in is less than (in an ASCII sense) the current letter
  167. **  in the buffer, it is forwarded to the next buffer, otherwise the current
  168. **  data is forwarded. The program will shut down when a ~ is the first 
  169. **  character in any input line.
  170. **  Must link in file buffers.c (after compilation of course..)
  171. **  Programed by: G.K.Ellis, Smart Materials and Structures Laboratory,
  172. **  Mechanical Engineering Department, Virginia Tech, Blacksburg, VA 24061
  173. *****************************************************************************/
  174.  
  175. #include <stdio.h>
  176. #include <conc.h>        /* the LSC defines are here */
  177. #include "mytypes.h"            /* include in this order... */
  178. #include "proto.h"
  179.  
  180. /**** MAIN PROGRAM  ****/
  181. void main()
  182. {
  183.     UBYTE ch[BUFF_SIZE];     /* string buffer */
  184.     BOOL active = TRUE;
  185.     int i; 
  186.     Channel *thru[NUM_PIPES + 1];    /* internal channels */
  187.     Process *p[NUM_PIPES + 3];      /* process pointers */
  188.     while(active) {
  189.         fgets(ch, BUFF_SIZE-1, stdin);     /* get the input line */
  190.         /* stop char is ~ as first letter */
  191.         if(ch[0] == '~') active = 0;
  192.         /* allocate the channels, NULL is returned if no memory    */
  193.         for(i = 0; i< NUM_PIPES + 1; i++) {
  194.             if((thru[i] = ChanAlloc()) == NULL)
  195.                 printf("No memory for Channel thru[%d]\n", i);
  196.         }
  197.                 
  198.     /* allocate the processes, NULL is returned if no memory */
  199.     p[0] = ProcAlloc(source, INPUT_STACK, 2, thru[0], ch);
  200.     for(i = 1; i < NUM_PIPES+1; i++) 
  201.         p[i] = ProcAlloc(pipe, PIPE_STACK, 2, thru[i-1], thru[i]);
  202.     p[NUM_PIPES+1] = ProcAlloc(output, OUTPUT_STACK, 1,  thru[NUM_PIPES]);
  203.         p[NUM_PIPES+2] = NULL;
  204.     /* check to see if all processes were allocated successfully    */
  205.         for(i = 0; i < NUM_PIPES + 2; i++)
  206.             if(!p[i])
  207.                 printf("No memory for Process p[%d]\n", i);
  208.        ProcParList(p);       /* Run a NULL terminated list of pointers */
  209.                  /* to processes. These are all low-pri    */
  210.         /* Since we allocate these each time through the loop, we needto 
  211.         ** deallocate them here otherwise, we will run out of memory */
  212.         for(i = 0; i < NUM_PIPES + 1; i++)
  213.             ChanFree(thru[i]);
  214.         for(i = 0; i < NUM_PIPES + 2; i++)    
  215.              ProcFree(p[i]);
  216.      }
  217.      printf("done!\n");        /* all done...    */
  218. }
  219.  
  220.  
  221.  
  222.  
  223. [LISTING SIX]
  224.  
  225. /*************************************************************************
  226. ** multisort.c -- A two transputer version of a simple parallel ASCII sorting 
  227. ** routine. This program will work on either node. Developed for Logical
  228. ** Systems Transputer C compiler (LSC) versions 88.4 or 89.1. Must link with 
  229. ** buffers.c. Programmed by: G.K.Ellis, Smart Materials and Structures 
  230. ** Laboratory, Mechanical Engineering Department, Virginia Tech,
  231. ** Blacksburg, VA 24061
  232. **************************************************************************/
  233.  
  234. #include <stdio.h>
  235. #include <conc.h>
  236. #include "mytypes.h"
  237. #include "proto.h"
  238.  
  239. /**** MAIN PROGRAM ****/
  240. void main()
  241. {
  242.     UBYTE ch[BUFF_SIZE];    /* string buffer */
  243.     BOOL active = TRUE;
  244.     int i; 
  245.     Channel *in, *out;        /* link channels */
  246.     Process *feeder, *sink;        /* hi-priority processes */
  247.     Channel *thru[NUM_PIPES - 1];     /* internal soft channels */
  248.     Process *p[NUM_PIPES - 2];     /* low-priority processes */
  249.     if(_node_number == 1) {        /* We are the root node */
  250.         in  = LINK3IN;        /* these are our links */
  251.         out = LINK3OUT;
  252.         while(active) {
  253.            fgets(ch, BUFF_SIZE-1, stdin);   /* get the input line */
  254.             /* stop char is ~ as first letter */
  255.             if(ch[0] == '~') active = 0;
  256.             /* set up the processes    */
  257.             feeder = ProcAlloc(source, INPUT_STACK, 2, out, ch);
  258.             sink   = ProcAlloc(output, OUTPUT_STACK, 1,  in);
  259.             /* Check that ProcAlloc() doesn't return a NULL, but 
  260.                         ** since we KNOW from the example sort.c this is ok */
  261.  
  262.             /* run the feeder and sink processes in parallel */
  263.              ProcPar(feeder, sink, NULL);
  264.  
  265.              /* free the previously allocated processes */
  266.              /* note we do this each time through the loop */
  267.              /* hey, it's only an example */
  268.              ProcFree(feeder);
  269.              ProcFree(sink);
  270.          }
  271.          printf("done!\n");
  272.          exit(0);            /* finis! */
  273.      } else {                /* if we are the non-root */
  274.         in = LINK2IN;            /* node, run this as main() */
  275.         out = LINK2OUT;            /* these are our links */
  276.         for(i = 0; i < NUM_PIPES - 1; i ++) { /* allocate soft channels */
  277.              thru[i] = ChanAlloc();
  278.          }
  279.             /* allocate soft channel pipe processes */
  280.            for(i = 0; i < NUM_PIPES - 2; i++) 
  281.              p[i] = ProcAlloc(pipe, PIPE_STACK, 2, thru[i], thru[i+1]);
  282.             /* allocate the processes with the links */
  283.             feeder = ProcAlloc(pipe, PIPE_STACK, 2, in, thru[0]);
  284.                sink   = ProcAlloc(pipe, PIPE_STACK, 2, thru[NUM_PIPES-2], out);
  285.          /* If we want to check the pointer returned from ProcAlloc(),
  286.          ** that is extra programming on a non-root node. Therefore, 
  287.          ** don't try to printf() from a non-root node.  There is a
  288.          ** non-server node _ns_printf() that does simple ASCII
  289.          ** transfers out a channel (link), but this generally requires
  290.          ** extra effort to communicate back to the server */
  291.  
  292.          /* Let's allocate these asynchronously */
  293.          ProcRunHigh(sink);   /* run the hardware links at high pri */
  294.          ProcRunHigh(feeder);
  295.          for(i = 0; i < NUM_PIPES - 2; i++) 
  296.              ProcRunLow(p[i]); /* and soft channels at low pri */
  297.          _ns_exit();    /* we must exit like this on non-server*/
  298.                 /* node or we will exit from the */
  299.                 /* main() program */
  300.           /* ProcRunHigh() and ProcRunLow() spawn new processes asyncronously 
  301.           ** from main().  The _ns_exit() does a STOPP on the main process
  302.           ** leaving the two spawned processes. The exit() routine trys
  303.           ** to send a message back to the server running on the PC.  If it
  304.           ** isn't there, i.e. you're not the root, you've got problems.
  305.           ** Note also, if we are not the root node, we never terminate
  306.           ** and restart the pipe processes... we just run the processes ! */
  307.      }
  308. }
  309.  
  310.  
  311. [Example 1: Actions performed by the single-processor
  312. implementation of the sorting routine]
  313.  
  314.  
  315.      Root Transputer:
  316.  
  317.      SEQUENTIAL
  318.         - Read in line of text and store in character buffer.
  319.         - Allocate channels and processes.
  320.         PARALLEL
  321.             - Send out a character at a time to the first pipe process.
  322.             - In 256 parallel pipe processes: read in a character then
  323.                 read a new character, forward the character with the
  324.                 lowest ASCII value.
  325.             - Read in one character at a time from last pipe buffer
  326.               and write it to the screen.
  327.         - Deallocate channels and processes.
  328.  
  329.  
  330.  
  331. [Example 2: A rectangle represents a transputer and the
  332. circles represent concurrent processes]
  333.  
  334.  
  335.     Root Transputer:
  336.     
  337.     SEQUENTIAL
  338.         - Read in line of text and store in character buffer.
  339.         - Allocate channels and processes.
  340.         PARALLEL
  341.             - Send out a character at a time to the first buffer.
  342.             - Read in a character at a time and write it to the screen.
  343.         - Deallocate channels and processes.
  344.  
  345.     Transputer Node 1:
  346.  
  347.     SEQUENTIAL
  348.         - Allocate channels and processes.
  349.         PARALLEL
  350.             - Read in data from link a character at a time, sort, forward to
  351.                 next pipe process.
  352.             - In 254 parallel pipe processes: read in a character then
  353.                 read a new character, forward the character with the
  354.                 lowest ASCII value.
  355.             - Read in data from pipe process sort, forward data to
  356.                root transputer.
  357.  
  358.  
  359.  
  360.  
  361. [Figure 1: Channel Communication  ]
  362.  
  363.     buffer(Process *p, Channel *in, *out)  /* the Procees *p is used by */
  364.     {                                      /* ProcAlloc()               */
  365.       int data;
  366.  
  367.       while(1) {
  368.         data = ChanInInt(in);
  369.         ChanOutInt(out, data);
  370.       }
  371.     }
  372.  
  373.  
  374.  
  375.  
  376. [Figure 2: Multiplexer using the channel alternative]
  377.  
  378.     mux(Process *p, Channel *in1, *in2, *out)
  379.     {
  380.       int data, index;
  381.  
  382.       while(1) {
  383.         index = ProcAlt(in1, in2, NULL); /* return offset into chan list */
  384.         switch(index) {
  385.           case 0:                        /* channel in1 */
  386.             data = ChanInInt(in1);
  387.             ChanOutInt(out, data);
  388.             break;
  389.           case 1:                        /* channel in2 */
  390.             data = ChanInInt(in2);
  391.             ChanOutInt(out, data);
  392.             break;
  393.         }
  394.       }
  395.     }
  396.  
  397.  
  398. [Figure 3: Two parallel processes code fragment]
  399.  
  400.  
  401.     Process *p1, *p2;            /* Process and Channel are defined in     */
  402.     Channel *in, *thru, *out;    /* conc.h                                 */
  403.  
  404.     in = ChanAlloc();   /* internal channel allocation                     */
  405.     out = ChanAlloc();  /* we should check the return values here          */
  406.     thru = ChanAlloc(); /* NULL returned if allocation unsuccessful        */
  407.     
  408.     p1 = ProcAlloc(buffer, STACK, 2, in, thru);  /* allocate space for the */
  409.     p2 = ProcAlloc(buffer, STACK, 2, thru, out); /* processes p1, p2       */
  410.     ProcPar(p1, p2, NULL);                       /* run them in parallel   */
  411.  
  412.  
  413.  
  414.  
  415.