8/9/14

Comparing Net.

Concurrent algorithms use concurrent computation models.

One of such is Comparing Net, which has two qualities:

  1. Can perform only compare operations,
  2. Can perform many operations concurrently.

Comparing nets are made of wires & comparators only.




Comparator.



Comparator is a device with two inputs: x, y and with two outputs: x', y' that count following function:

  x' = min(x,y)
  y' = max(x,y)

Let's assume that each of comparators works in constant time O(1). That is, time between appearance of all input data and production of output is constant.




Comparator image using wires.


Comparing Net has n inputs: a1, a2, ..., an where values to be sorted are put, and n outputs: b1, b2, ..., bn where sorted values appear.

We can also say that we have input sequence: < a1, a2, ..., an > and output sequence: < b1, b2, ..., bn >.

Comparing Net with n inputs can be shown as n horizontal lines, wires with comparators. Single line does not have to represent one wire but sequence of wires that connect many comparators. Input data is on the left, output to the right.




Comparing Net with n = 4, that is also Sorting Net.



Source: [4], Sorting Nets.

No comments:

Post a Comment