home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / parallel / 2050 < prev    next >
Encoding:
Text File  |  1992-09-03  |  6.8 KB  |  140 lines
  1. Newsgroups: comp.parallel
  2. Path: sparky!uunet!gatech!hubcap!fpst
  3. From: Parallel Performance Group <strand@ppg.strand.com>
  4. Subject: Strand88 Newsletter
  5. Message-ID: <1992Sep4.121507.18337@hubcap.clemson.edu>
  6. Sender: fpst@hubcap.clemson.edu (Steve Stevenson)
  7. Organization: Clemson University
  8. Date: Fri, 4 Sep 92 04:10:31 PDT
  9. Approved: parallel@hubcap.clemson.edu
  10. Lines: 128
  11.  
  12.  
  13.  
  14.                    STRAND88 NEWSLETTER VOLUME 1, ISSUE 3
  15.  
  16.                                  July, 1992
  17.  
  18.            THIS ISSUE'S TOPIC - THE VIRTUAL TOPOLOGIES FACILITY
  19.  
  20.  
  21. Strand88's Virtual Topologies Library enables Strand programmers to treat a
  22. distributed memory parallel machine with some given physical connection
  23. topology as though it actually had an alternative virtual connection topology.
  24. This virtual connection topology is mapped onto the real topology transparently
  25. by the Strand Virtual Topologies Library, with effectively no communications
  26. overhead.  If the Strand application is then moved to a new machine with a
  27. different real connection topology, the virtual connection topology will be
  28. mapped onto the new real connection topology automatically, when the applica-
  29. tion is compiled on the new machine.
  30.  
  31. Since Strand applications are completely portable among all machines to which
  32. Strand has been ported(i.e., without changes to the applications programs them-
  33. selves), this facility couples this portability with topology communications
  34. portability and optimality.  Thus the intermediate virtual topology enables the
  35. programmer to maintain the communications efficiency he has programmed into his
  36. Strand application on one architecture, when he moves his Strand application to
  37. another architecture, with no changes to the programs.  The topologies library
  38. frees the programmer from having to consider the physical connectivity of the
  39. machine in distributing an application.  Distribution schemes may be developed
  40. which employ a convenient connection topology, and this topology is then mapped
  41. onto the actual topology by the library.  Furthermore, users may develop dis-
  42. tributed applications to function as black boxes, establishing their own topo-
  43. logy as appropriate.  Other programs may invoke these applications without
  44. regard to their distribution requirements.
  45.  
  46. The topology library supports three different connection schemes: fully
  47. connected, ring, and twisted torus (a 2-dimensional mesh with wrapped-around
  48. rows and columns).  Example machine declarations are:
  49.  
  50.             -machine(ring).
  51.             -machine(connected(10)).
  52.             -machine(torus(4,6)).
  53.  
  54. Programmers may explicity construct topolgies and locate computations within
  55. them.  This functionality is made available by means of external procedure
  56. calls to procedures exported by the virtual topology library modules.  The use
  57. of external procedure calls allows topology dimensions to be calculated
  58. dynamically rather than be statically declared in the module.
  59.  
  60. The library procedures may also be employed by programmers to partition a
  61. machine into independent sets of nodes for use by separate subcomputations
  62. employing different distribution strategies.  Since these subcomputations may
  63. not redistribute themselves outside their original node allocation, they cannot
  64. compete with each other for CPU resources.
  65.  
  66. An example program using an explicitly created topology is given below; the
  67. torus procedure resides in and is exported from the Strand module torboot:
  68.  
  69.     -compile(free).
  70.     -exports([rotate_point/3,vector_mult/5,vector_product/5]).
  71.  
  72.     % rotate N-element point in N-space by multiplication with N x N matrix.
  73.     % Point, NewPoint are N-element tuples.
  74.     % Matrix is an N-element tuple of N-element tuples.
  75.  
  76.     rotate_point(Point,Matrix,NewPoint) :-
  77.        arity(Point,N)               % determine the dimension of Point.
  78.        make_tuple(N,NewPoint)       % create a length-N empty output vector.
  79.        torboot:torus(N,N,[matrix:vector_mult(N,N,Point,Matrix,NewPoint)]).
  80.  
  81.  
  82. In the above, vector_mult is a procedure from the module matrix; in a torus
  83. topology, each node has four links which are identified by "compass bearings"
  84. north, south, east, and west:
  85.  
  86.     vector_mult(Col,Rows,RowVector,Matrix,NewVector) :-
  87.       Col == 1 |
  88.          get_arg(Col,Matrix,ColVector),              % use next matrix row.
  89.          vector_product(Col,Rows,RowVector,ColVector,
  90.                         NewEntry),                   % calculate new entry.
  91.          put_arg(Col,NewVector,NewEntry).            % assign it.
  92.     vector_mult(Col,Rows,RowVector,Matrix,NewVector) :-
  93.       otherwise |                                     % still rows to multiply.
  94.          NewCol is Col - 1,
  95.          get_arg(Col,Matrix,ColVector),              % use next row.
  96.          vector_product(Col,Rows,RowVector,ColVector,
  97.                         NewEntry),                   % calculate new entry.
  98.          put_arg(Col,NewVector,NewEntry),            % assign it.
  99.          vector_mult(NewCol,Rows,RowVector,Matrix,
  100.                      NewVector)@east.                % get rest of vector.
  101.  
  102.     vector_product(Col,Rows,Vector1,Vector2,Product) :-
  103.       Col == 1 |
  104.          get_arg(Col,Vector1,NewEntry1),             % get next 2 next entries,
  105.          get_arg(Col,Vector2,NewEntry2),             
  106.          Product is NewEntry1 * NewEntry2.           % and multiply them.
  107.     vector_product(Col,Rows,Vector1,Vector2,Product) :-
  108.       Col = Rows | true.
  109.     vector_product(Col,Rows,Vector1,Vector2,Product) :-
  110.       otherwise |
  111.          NewCol is Col + 1,
  112.          get_arg(Col,Vector1,NewEntry1),                  % get next 2 entries, 
  113.          get_arg(Col,Vector2,NewEntry2),                  % and multiply them.
  114.          NewProduct is Product + (NewEntry1 * NewEntry2), % add product to rest
  115.                                                           %  of sum.
  116.          vector_product(NewCol,Rows,Vector1,Vector2,
  117.                         NewProduct)@south.                % get a new product.
  118.  
  119. Our next issue will cover single assignment and updating of shared variables.
  120.  
  121. **********************************************************************
  122.  
  123. Strand88 is a highly portable and scalable parallel programming language
  124. designed for efficient execution on many hardware platforms: shared-memory
  125. multiprocessors, distributed-memory multiprocessors, and networks of
  126. workstations.
  127.  
  128. Strand88 is currently ported to the following platforms:
  129.  
  130.      iPSC/860, iPSC2/386, Sequent Balance/Symmetry, Sun SparcStation, 
  131.      Sun 600MP Multiprocessing Workstation, Solbourne, Transputer/Helios,
  132.      Alliant FX/2800, Meiko Computing Surface, MIPS RISCstation, nCube2,
  133.      Pyramid, Encore Multimax and System 9x, Cogent XTM Workstation,
  134.      Mac II, IBM PS/2, NeXT, and TI TMS320C40 Digital Signal Processor.
  135.  
  136. Stuart Bar-On of Parallel Performance Group, at (619) 634-0882,
  137. E-Mail: 4956839@mcimail.com or strand@ppg.strand.com, will send
  138. information and answer any questions you may have about Strand88.
  139.  
  140.