Assignment 19 - Parallel Sorting
You can download this homework and set the permissions
with the commands
cd ~/public_html
wget http://www.comp.nus.edu.sg/~gem1501/assignment19.html
chmod 755 *.html
Outline
Comparators are small devices which have two inputs and two outputs.
The first output is the minimum and the second the maximum of the
two numbers at the input. So a comparator sorts two numbers two
a list. One can arragne comparators such that they form a sorting
network. An example of such a architecture are the odd-even sorting
networks on pages 264-265 in Chapter 10 of Harel's book.
The goal is to have several comparators in parallel in order to
sort with as few levels as possible.
Each level has 10 inputs and 10 outputs. Some neightbouring inputs
might be sent into a comparator with the results then sent to some output
fields and other inputs are without being compared directly moved to
some output. There are at most 5 comparators per level and every input
is dealt with exactly once. More details are given in next section.
The syntax for describing a level
Each level is described by a certain code. This code consists of
commands what to do in the level. The command consists of a sequence
of move commands like "m9-" which moves the current input to the
place "9" for the next level and comparators like "c34" which
take two current inputs and assign their minimum to the place "3"
and their maximum to the place "4". The combined command consists
of several 3-digit-codes and has therefore a length with is a multiple
of 3. Here an example.
Complete code: "m9-c12c34c87m6-c50", inputs are determined
by positions of subcodes in code, outputs are explicitly stated.
"m9-": input at "0" is Moved to "9";
"c12": inputs at "1" and "2" are sent into a Comparator
and the results are sent to "1" and "2";
"c34": inputs at "3" and "4" are sent into a Comparator
and the results are sent to "3" and "4";
"c87": inputs at "5" and "6" are sent into a Comparator
and the results are sent to "8" and "7";
"m6-": input at "7" is Moved to "6";
"c50": inputs at "8" and "9" are sent into a Comparator
and the results are sent to "5" and "0".
Sample Execution of level:
Position "0" "1" "2" "3" "4" "5" "6" "7" "8" "9"
Before 10 90 80 70 77 66 55 88 39 28
Command m9- c12 c34 c87 m6- c50
After 28 80 90 70 77 39 88 66 55 10
The incomming data of a comparator or move command are just determined
by the position in the level-description, the outcomming positions are
explicitly declared by digits. The coded operation should address all
positions and cover all inputs of the next level. Therefore every digit
has to appear exactly once in the code. For easier interpretation, also
the move instructions have three digits with a "-" filling the third
useless character. "m" stands for moving an input, "c" stands for
comparing two inputs in a comparator. Note that even if the input moves
to the same position in the output, a moving command must be placed.
A command like "c87" places the larger output first and the smaller
one second; this is legal but does not give any advantage, therefore
it is recommended not to do that. The goal is to have the resulting
list be ordered in an ascending way.
What has to be done
Implemented is a sorting network consisting of 11 levels. This is
not optimal at all. So the goal is to find an architecture which does it
with 9 or less levels. The architecture of each level
is loaded with a push-operation onto the network. To edit the levels,
one has to change the codes describing what is done in each level
and to delete some of the push-operations, if less levels are
required.
Handing in and Programming Competition
If you find a network with 9 levels, you can hand in the assignment
by showing it to the lecturer.
Java Script starts here.
Java Script ends here.