🚀 go-pugleaf

                   STRAND88 NEWSLETTER VOLUME 1, ISSUE 3

                                 July, 1992

           THIS ISSUE'S TOPIC - THE VIRTUAL TOPOLOGIES FACILITY


Strand88's Virtual Topologies Library enables Strand programmers to treat a
distributed memory parallel machine with some given physical connection
topology as though it actually had an alternative virtual connection topology.
This virtual connection topology is mapped onto the real topology transparently
by the Strand Virtual Topologies Library, with effectively no communications
overhead.  If the Strand application is then moved to a new machine with a
different real connection topology, the virtual connection topology will be
mapped onto the new real connection topology automatically, when the applica-
tion is compiled on the new machine.

Since Strand applications are completely portable among all machines to which
Strand has been ported(i.e., without changes to the applications programs them-
selves), this facility couples this portability with topology communications
portability and optimality.  Thus the intermediate virtual topology enables the
programmer to maintain the communications efficiency he has programmed into his
Strand application on one architecture, when he moves his Strand application to
another architecture, with no changes to the programs.  The topologies library
frees the programmer from having to consider the physical connectivity of the
machine in distributing an application.  Distribution schemes may be developed
which employ a convenient connection topology, and this topology is then mapped
onto the actual topology by the library.  Furthermore, users may develop dis-
tributed applications to function as black boxes, establishing their own topo-
logy as appropriate.  Other programs may invoke these applications without
regard to their distribution requirements.

The topology library supports three different connection schemes: fully
connected, ring, and twisted torus (a 2-dimensional mesh with wrapped-around
rows and columns).  Example machine declarations are:

            -machine(ring).
            -machine(connected(10)).
            -machine(torus(4,6)).

Programmers may explicity construct topolgies and locate computations within
them.  This functionality is made available by means of external procedure
calls to procedures exported by the virtual topology library modules.  The use
of external procedure calls allows topology dimensions to be calculated
dynamically rather than be statically declared in the module.

The library procedures may also be employed by programmers to partition a
machine into independent sets of nodes for use by separate subcomputations
employing different distribution strategies.  Since these subcomputations may
not redistribute themselves outside their original node allocation, they cannot
compete with each other for CPU resources.

An example program using an explicitly created topology is given below; the
torus procedure resides in and is exported from the Strand module torboot:

    -compile(free).
    -exports([rotate_point/3,vector_mult/5,vector_product/5]).

    % rotate N-element point in N-space by multiplication with N x N matrix.
    % Point, NewPoint are N-element tuples.
    % Matrix is an N-element tuple of N-element tuples.

    rotate_point(Point,Matrix,NewPoint) :-
       arity(Point,N)               % determine the dimension of Point.
       make_tuple(N,NewPoint)       % create a length-N empty output vector.
       torboot:torus(N,N,[matrix:vector_mult(N,N,Point,Matrix,NewPoint)]).


In the above, vector_mult is a procedure from the module matrix; in a torus
topology, each node has four links which are identified by "compass bearings"
north, south, east, and west:

    vector_mult(Col,Rows,RowVector,Matrix,NewVector) :-
      Col == 1 |
         get_arg(Col,Matrix,ColVector),              % use next matrix row.
         vector_product(Col,Rows,RowVector,ColVector,
                        NewEntry),                   % calculate new entry.
         put_arg(Col,NewVector,NewEntry).            % assign it.
    vector_mult(Col,Rows,RowVector,Matrix,NewVector) :-
      otherwise |                                     % still rows to multiply.
         NewCol is Col - 1,
         get_arg(Col,Matrix,ColVector),              % use next row.
         vector_product(Col,Rows,RowVector,ColVector,
                        NewEntry),                   % calculate new entry.
         put_arg(Col,NewVector,NewEntry),            % assign it.
         vector_mult(NewCol,Rows,RowVector,Matrix,
                     NewVector)@east.                % get rest of vector.

    vector_product(Col,Rows,Vector1,Vector2,Product) :-
      Col == 1 |
         get_arg(Col,Vector1,NewEntry1),             % get next 2 next entries,
         get_arg(Col,Vector2,NewEntry2),             
         Product is NewEntry1 * NewEntry2.           % and multiply them.
    vector_product(Col,Rows,Vector1,Vector2,Product) :-
      Col = Rows | true.
    vector_product(Col,Rows,Vector1,Vector2,Product) :-
      otherwise |
         NewCol is Col + 1,
         get_arg(Col,Vector1,NewEntry1),                  % get next 2 entries, 
         get_arg(Col,Vector2,NewEntry2),                  % and multiply them.
         NewProduct is Product + (NewEntry1 * NewEntry2), % add product to rest
                                                          %  of sum.
         vector_product(NewCol,Rows,Vector1,Vector2,
                        NewProduct)@south.                % get a new product.

Our next issue will cover single assignment and updating of shared variables.

**********************************************************************

Strand88 is a highly portable and scalable parallel programming language
designed for efficient execution on many hardware platforms: shared-memory
multiprocessors, distributed-memory multiprocessors, and networks of
workstations.

Strand88 is currently ported to the following platforms:

     iPSC/860, iPSC2/386, Sequent Balance/Symmetry, Sun SparcStation, 
     Sun 600MP Multiprocessing Workstation, Solbourne, Transputer/Helios,
     Alliant FX/2800, Meiko Computing Surface, MIPS RISCstation, nCube2,
     Pyramid, Encore Multimax and System 9x, Cogent XTM Workstation,
     Mac II, IBM PS/2, NeXT, and TI TMS320C40 Digital Signal Processor.

Stuart Bar-On of Parallel Performance Group, at (619) 634-0882,
E-Mail: 4956839@mcimail.com or strand@ppg.strand.com, will send
information and answer any questions you may have about Strand88.