funnel : helping move applications to multiple processors 
Author Message
 funnel : helping move applications to multiple processors

        funnel : Easy Distributed Processing for Existing Applications
        --------------------------------------------------------------

Introduction:
-------------

funnel should allow a fair-sized class of applications, written with a
single processor in mind, to be easily run, without modification, on multiple
machines/processors.

funnel manages the main input/output data stream of an application so that it
may be run in parallel on many processors.

funnel can help applications which satisfy the following criteria:

i)
The application produces sequential output which can be divided into events.
The events must be independent entities and their ordering must be irrelevant.

ii) [Optional]
The application produces the output events by 'converting' an input event. The
input events must also be independent entities with an irrelevant ordering and
each input event must lead to exactly one output event.

I'm posting this to:
 - Demonstrate that some applications, without modification but using
   utilities like those presented here, can run in parallel on many machines.
 - Receive net wisdom:
   . Does funnel already exist under another name?
      i.e. Have we just recreated the sneeble_dist utility.
   . Names of utilities similar to funnel would be much appreciated.
   . Is there a need for funnel? If yes, it could made public.
   . Comments on the methods presented below would be appreciated.

A working example:
------------------

funnel has been created in order to run, on multiple unix machines,
the 'ZEUS Detector Simulation Monte Carlo', a.k.a. Mozart.

Mozart in a nutshell:

     while input
       read input event
       use input event as a 'seed' to generate the output event
       write the output event
     endwhile

In greater detail:
input event  - a set of particles coming out of a high energy collision
               between an electron and a proton.
generate     - simulate the particles' behavior in the detectors observing the
               collision.
output event - the collection of simulated signals in the detectors.

Introducing the notation:     I   = Input Events
                              O   = Ouput Events
                              []  = A file
                              >   = flow of data
                              ()  = A process

Mozart was written to be used as follows:

                           [I] > (MOZART) > [O]            (1)

i.e. just a regular program reading a sequential input file and writing to a
sequential output file.

Now if one wants to quickly create a lot of output events, by running on
N processors, one is of course free to divide up the input into N parts,
start up Mozart on each of the N processors and when they're all finished
go back and catenate all the output files together. This is what funnel does
in an easier and more elegant fashion. i.e. funnel allows:

                          |-->-- (MOZART) -->--|
                          :         :          :
                          |-->-- (MOZART) -->--|
                          |-->-- (MOZART) -->--|
                 [I] -->--|-->-- (MOZART) -->--|-->-- [O]      (2)
                          |-->-- (MOZART) -->--|
                          |-->-- (MOZART) -->--|
                          :         :          :
                          |-->-- (MOZART) -->--|

Where each input event from [I] is passed to one of the (MOZART). In our case
each (MOZART) is running parasitically in the background, nice 19, on one of 40
DECstations. (The DECstations are workstations for regular users.) funnel is
usually started up with a sequence of input files, and the matching output
files are written straight to Exabyte tape.                    

funnel has been developped on a mix of DECstations and Silicon Graphics
machines and should be fairly portable to other unix machines supporting
rexec(3).

In addition to the explicit application requirements listed in the
introduction, the implicit limit of data transfer rates have to be met.

The maximum number of processors that can be supported in a single system is
simply:
                    bandwidth between processors
  max_processors =  -------------------------------------------
                    i/o of a single instance of the application

I/O Feasability in our case:
 . Data tranfer, -->--,  is across ethernet, conservatively: 400Kbyte/sec.
 . Exabyte writes at:                                        400Kbyte/sec.
 . Output event size:  (input event is negligible)           100Kbyte.
 . Processing time for 1 event:                              60sec/event.

Therefore up to 4 events/sec can be transferred, i.e. one could suppport up to
240 machines in a single system.

Recall, funnel promised that (MOZART) could be completely standard in
diagram (2), i.e. (MOZART) still thinks it's reading from and writing to a
file. Here's how it's done:

The following system is started from a single script which has:
 - 2 lines per processor: . one to start (MOZART) via rsh
                          . one to inform (funnel) about the processor
 - 1 line for each ouput file or process.
 - 1 line for each input file.

The script is automagically generated from a list of processors and a list of
input files.

        __unix1_________________          __unix40________________
        | (MOZARTMOZARTMOZART) |          | (MOZARTMOZARTMOZART) |
        |    C    I       O    |    38    |    C    I       O    |
        |    C  named   named  |   more   |    C  named   named  |
        |    C   pipe    pipe  | machines |    C   pipe    pipe  |
        |    C    I       O    |   here   |    C    I       O    |
        |    C (block) (evcat) |          |    C (block) (evcat) |
        |____C____I_______O____|          |____C____I_______O____|
_____________C____I_______O_____ . . . . . ____C____I_______O_______________
|            C    I       O                    C    I       O              |
|           [C]   I       O                   [C]   I       O              |
|                 I       O                         I       O              |
| [I]II(evcat)II(FUNNELFUNNELFUN . . . . . FUNNELFUNNELFUNNEL)OO(dd)OO[O]  |
|                                                                          |
|__unixMASTER___________________ . . . . . ________________________________|

MACHINES:
unix1      - any unix machine running (MOZART) in the background.
             Same for unix2, .., unix40.
             (FUNNEL) requires that the machine support rexecd(1M|8c)
unixMASTER - the unix machine controlling the whole show.
             (FUNNEL) requires that the machine support rexec(3) and select(2).

DATA:
CC..CC - the flow of the ASCII log and error messages from (MOZART) which is
         recorded in a file on unixMASTER.
       - the control cards used to steer (MOZART).
         [(MOZART) is written in fortran, where one still talks about cards.]
II..II - the flow of input events from a file through (FUNNEL) which forwards
         each event to one of the (MOZART). (FUNNEL) sends an input event after
         receiving an output event.
OO..OO - the flow of output events from (MOZART) through (FUNNEL) to an output
         process or file.

PROCESSES:
(block)  - (MOZART) does a Fortran open with a given record length on the input
           file. The named pipe has to be filled with blocks of this length.
           block receives the input data from (FUNNEL), and writes it out with
           the correct blocksize into the named pipe.
(evcat)  - evcat reads the named pipe filled by (MOZART) and recognizes when it
           has read in a complete event. At that point it forwards the event to
           (FUNNEL).
(dd)     - (FUNNEL) can write each output 'file' to either a file or a process.
           For (MOZART), we popen(3) dd(1) and write straight to Exabyte.
(MOZART) - the standard single processor application.
(FUNNEL) - Something like:

              Read in the startup script
              rexec(3) gets (evcat) and (block) going
              fopen(3) | popen(3) the output file | process.
              fill input event queue of each (MOZART).
              while don't have all output events
                wait for select(2)
                read(2) the event from unixN and write to output file | process
                write(2) an event to unixN
              endwhile

          Add the following features:
          - multiple input/output files.
          - add processors, input/output files on the fly.
          - a user interface.
          - a toplike window to display the state of the system.
          - broadcast a header from the input file to all (MOZART).
          - start each output file with a header output from (MOZART).
          - send a final trailer to each (MOZART).
          - add a final trailer to each output file | process.
          - handle exceptions for everything that can and will go wrong.

          And you've got a 2000 line program. The current version won't win any
          beauty contests, but it works and we don't know of any holes that
          aren't plugged.

MISCELLANY:
input event queue - (MOZART) buffers up to two output events. To prevent the
                    system from blocking, (MOZART) needs access to 3 events.
                    Therefore (FUNNEL) can keep track of an input event queue
                    which is held in (block).
protocol - (evcat) sends events to (FUNNEL) by preceding each event with 4 bytes
           specifying the event length, and following the event by a 4 byte
           checksum.
           (FUNNEL) allows events to be lost, but won't forward bad data to
           the output. Therefore (FUNNEL) reads in the entire event and
           verifies the checksum before forwarding the data.
killmozart - is a simple program that allows any user on one of the
             workstations to 'kill -9' the (MOZART) if it interferes with the
             user's work.
...

read more »



Mon, 28 Nov 1994 22:39:40 GMT  
 funnel : helping move applications to multiple processors
Burkhard, we have a number of computational chemistry programs that could
benefit from what you have done with 'funnel'.  We are just now starting to
experiment with network parallel computing and are interested in giving
'funnel' a try if that can be arranged.

PS:  I tried to respond directly to you but the mail bounced.



Rohm and Haas Company - Research Division - PO Box 219 - Bristol, PA 19007 USA



Mon, 28 Nov 1994 22:40:45 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. PC with Multiple processors

2. Threads and multiple processors

3. Looking for Funnel Sort algorithm

4. DVF & Multiple Processors (newbie)

5. Python on multiple processor machines

6. MS PS 4.0 and Multiple Processors

7. FORTRAN compliers for multiple processors.

8. Shared mem(Sparc FORTRAN): multiple processors

9. Problem with Dos application hoging the processor

10. Fixing Clipper applications (without source) to new Processors

11. how to move the source code to the application

12. Clipper Summer 87 Application moved from 286 to Pentium Causing Errors

 

 
Powered by phpBB® Forum Software