home *** CD-ROM | disk | FTP | other *** search
- Newsgroups: comp.dcom.cell-relay
- Path: sparky!uunet!stanford.edu!kronos.arc.nasa.gov!iscnvx!news
- From: myoung@force.ssd.lmsc.lockheed.com
- Subject: Sorting
- Message-ID: <1992Nov18.153610.2671@iscnvx.lmsc.lockheed.com>
- Sender: news@iscnvx.lmsc.lockheed.com (News)
- Reply-To: myoung@force.ssd.lmsc.lockheed.com
- Organization: LMSC, Sunnyvale, California
- Date: Wed, 18 Nov 92 15:36:10 GMT
- Lines: 67
-
- In this application an arbitrary group of processors have been
- already been allocated and their wave interpreters connected
- in an arbitrary mesh network using virtual paths. A list of data
- made available to one processor, and using the following simple
- wave sort algorithm, the list is immmediately spread over a
- binary sort tree, imposed upon the arbitrary mesh network.
- As the tree is formed, processors are chosen from the list
- of connections in an arbitrary order, some processors being
- used to manage more than one node of the sort tree. All synchronization
- is automatic with the wave syntax.
-
- WAVE Sort:
-
- The tree node divides list of objects according to whether the upstream
- list of items according if an object is greater than or less than the first
- item on the list. A tree is created with the sorted items at the leaves of
- the tree. The wave process is ongoing, continuing to sort items as long as
- items are available in the upstream nodes. That is as new records arrive
- they are automatically sorted and distributed, new nodes formming as
- required.
-
- At any given time, a secondary wave can be launched to collect
- the items from the tree leaves in a sorted manner.
-
-
- Written in pseudo wave:
-
-
- WAVE SORT:
-
- Frontal Storage:
- First Item
- List Pointer (either left or right)
-
- Nodal Storage:
- Left List, Left list index
- Right list, right list index
-
- WAVE GET NEXT ITEM
- Frontal Item:
- Obtained Item
-
- Propagate upstream
- Wait for next item in left or right list
- according to list pointer
-
- Increment List pointer
- return
-
- If obtained item is less than first item then
- if obtained item is first object obtained that is
- less/equal than first item then
- Propagate WAVE SORT to a new down stream node,
- obtained item is new first item and list pointer is left
- not wait for echo
- else
- add it to left list, increment index
- endif
-
- if obtained item is first object obtained that is
- more than first item then
- Propagate WAVE SORT to a new down stream node,
- obtained item is new first item and list pointer is right
- not wait for echo
- else
- add it to right list, increment index
- endif
-