Please refer to this page for information on how to work on your assignment.
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 arrange comparators such that they form a sorting network. An example of such an 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 neighbouring 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.
Each level is described by a certain code. This code consists of commands
about 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 takes 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 which is a multiple of 3. Here is 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 incoming data of a comparator or move command is just determined by the
position in the level description, the outgoing 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, the move instructions
also 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.
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.
If you find a network with 9 levels, you can hand in the assignment by showing it to the lecturer.