home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / dcom / cellrel / 737 < prev    next >
Encoding:
Text File  |  1992-11-18  |  2.6 KB  |  79 lines
  1. Newsgroups: comp.dcom.cell-relay
  2. Path: sparky!uunet!stanford.edu!kronos.arc.nasa.gov!iscnvx!news
  3. From: myoung@force.ssd.lmsc.lockheed.com
  4. Subject: Sorting
  5. Message-ID: <1992Nov18.153610.2671@iscnvx.lmsc.lockheed.com>
  6. Sender: news@iscnvx.lmsc.lockheed.com (News)
  7. Reply-To: myoung@force.ssd.lmsc.lockheed.com
  8. Organization: LMSC, Sunnyvale, California
  9. Date: Wed, 18 Nov 92 15:36:10 GMT
  10. Lines: 67
  11.  
  12. In this application an arbitrary group of processors have been
  13. already been allocated and their wave interpreters connected
  14. in an arbitrary mesh network using virtual paths.  A list of data 
  15. made available to one processor, and using the following simple
  16. wave sort algorithm, the list is immmediately spread over a
  17. binary sort tree, imposed upon the arbitrary mesh network.
  18. As the tree is formed, processors are chosen from the list
  19. of connections in an arbitrary order, some processors being
  20. used to manage more than one node of the sort tree.  All synchronization
  21. is automatic with the wave syntax.
  22.  
  23. WAVE Sort:
  24.  
  25. The tree node divides list of objects according to whether the upstream
  26. list of items according if an object is greater than or less than the first 
  27. item on the list.  A tree is created with the sorted items at the leaves of 
  28. the tree.  The wave process is  ongoing, continuing to sort items as long as 
  29. items are available in the upstream nodes.  That is as new records arrive
  30. they are automatically sorted and distributed, new nodes formming as
  31. required.
  32.  
  33.   At any given time, a secondary wave can be launched to collect
  34. the items from the tree leaves in a sorted manner.
  35.  
  36.  
  37.   Written in pseudo wave:
  38.  
  39.  
  40. WAVE SORT:
  41.  
  42.    Frontal Storage:
  43.          First Item
  44.          List Pointer (either left or right)
  45.  
  46.    Nodal Storage:
  47.          Left List, Left list index
  48.          Right list, right list index
  49.  
  50.   WAVE GET NEXT ITEM
  51.    Frontal Item:
  52.         Obtained Item
  53.  
  54.    Propagate upstream
  55.       Wait for next item in left or right list 
  56.        according to list pointer
  57.  
  58.       Increment List pointer
  59.       return
  60.  
  61.    If obtained item is less than first item then
  62.       if obtained item is first object obtained that is
  63.       less/equal than first item then
  64.           Propagate WAVE SORT to a new down stream node, 
  65.             obtained item is new first item and list pointer is left
  66.            not wait for echo
  67.       else
  68.           add it to left list, increment index
  69.       endif
  70.  
  71.       if obtained item is first object obtained that is
  72.       more than first item then
  73.           Propagate WAVE SORT to a new down stream node, 
  74.             obtained item is new first item and list pointer is right
  75.            not wait for echo
  76.       else
  77.           add it to right list, increment index
  78.       endif
  79.