Re: Request for Comments : Distributed Ada Systems

[ian@LORAL.UUCP (Ian Kaplan)]

  Please post in the Ada news groups on USENET and ARPANet.
		    Thanks,
			    Ian Kaplan

  This note is in response to Jim Baldo's note regarding Ada on distributed
  systems.  I tried to mail this to Jim and I was unable to get my mail
  through.

  I am one of the developers working on a large grain data flow
  system.  Our data flow system, the LDF 100, is a distributed architecture
  in that it does not have any memory that is shared by all the processors.
  Instead, memory is distributed throughout the system and processors
  communicate over a message passing (token) bus.  There has been some 
  interest in Ada on our system.  I am not an Ada expert, but from my 
  reading of the Ada language spec. it is unclear what we have to do to 
  implement Ada on our system.

  The LDF 100 logically consists of two components (although they are
  physically packaged in the same chassis): a Berkeley UNIX development
  environment and the data flow engine.  All the processors in the system,
  including the data flow processing elements, are implemented with the
  National Semiconductor NS32016 microprocessor.  There is an Ada compiler
  for the 32000 from Verdix, so there should be no problem getting validated
  Ada on the UNIX system.  Our problem is that we do not know that we have 
  to do with Ada to get it validated on the data flow parallel processor.  

  We have designed our system so that it supports large scale parallelism.
  We can, for example, build a system with over one hundred Processing
  Elements, that has close to supercomputer performance.  The multiprocess
  model used by Ada was not designed for large scale parallel systems.  At
  best it was designed for systems with a few processors and shared
  memory.  In a large scale parallel system centralized control will not
  work, so the idea of a central scheduler can not be used.

  In data flow there is no central control.  A data flow  program is 
  organized in a data flow graph and graph nodes execute when they have 
  the necessary data.  This allows asynchronous processing through the 
  graph (i.e., pipelining).  We are unsure how to reconcile this model with
  Ada.  The Ada programming model seems to be based on
  the assumption that there is shared memory and a central program that
  controls everything.

  We would like to run Ada on our system in the same way that we run 
  C and FORTRAN.  A program for our system consists of two components, a
  graph that describes the parallel structure of the application and the
  code that implements the nodes of the graph.  This code is written in
  either C or FOTRAN.  One of the simplest examples is a sort-merge graph.

		  
			   data source
			    /  / \  \
                           /  /   \  \
                          S  S     S  S
			   \/       \/
			   Merge     Merge
			    \        /
			     \      /
			      \    /
				Merge
				 |

  
  We express this graph in a custom graph langauge

      
      Sort1 = "/usr/ian/sort"
      import{ stream DataInput1 }
      export{ stream SortResult1 }

      Sort2 = "/usr/ian/sort"
      import{ stream DataInput2 }
      export{ stream SortResult2 }

      Merge = "/usr/ian/merge"
      import{ stream SortResult1, SortResult2 }
      export{ stream Merge1 }

	  etc...

  The quoted string is the UNIX file name of the code file that 
  implements that particular node.  Each node is implemented by a fully
  linked program (i.e., UNIX code file).  A C langauge skeleton program
  for the sort is shown below:

  #define INPUT_ARC 1
  #define OUTPUT_ARC 1

    main()  /* sort an array of short integers */
    {
      int len;
      short *array_ptr;

      /* read in the data to be sorted */
      len = floread( INPUT_ARC, &array_ptr );

      /* sort the data */

      /* write out the sorted data */
      flowrite( OUTPUT_ARC, array_ptr, len);
    } /* end sort program */

  In data flow a node is not scheduled for execution until it has all the
  data it needs to execute.  For this reason there are no "waiting reads"
  in a data flow system.  The floread executed above will return
  immediately.  As I have mentioned abnove, data flow is an asynchronous 
  programming model.  Unlike a rendezvous the flowrite does not have to 
  synchronize with the reader.

  In addition to having C and FORTRAN nodes we would like to have Ada nodes.
  Our hope is that the data flow engine will be simply another target
  environment, just as an F-16 computer module would be.  This would allow
  us to certify the Ada compiler under our UNIX system and run Ada nodes on
  the data flow engine.  Whether this is a realistic expectation is still
  unclear.

  I appologize for the length of this posting, but I do not think that a
  shorter one would have made our problem clear.

		     Ian Kaplan
		     Loral Data Flow Group
		     Loral Instrumentation
		     (619) 560-5888 x4812
	     USENET: {ucbvax,decvax,ihnp4}!sdcsvax!sdcc6!loral!ian
	     ARPA:   sdcc6!loral!ian@UCSD
	     USPS:   8401 Aero Dr. San Diego, CA 92123