Assignment 15 - Parallel Sorting

  1. Getting Started

    Please refer to this page for information on how to work on your assignment.

  2. 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 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.

  3. The syntax for describing a level

    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.

  4. Task of the exercise

    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.

  5. 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.

JavaScript Starts Here.
JavaScript Ends Here.