Составители:
Рубрика:
Пусть n является степенью двойки (n = 2
k
). Для построения
сортирующей сети упомянутый процесс GLUE скопируем в 2
k−1
вы-
числительных модулей, подав н а них по паре соседних элементов: в
результате они соединятся в цепочки из двух упорядоченных чисел.
Далее в 2
k−2
вычислительных модулей направим пары этих це-
почек, в результате получим 2
k−2
упорядоченных цепочек по че ты-
ре числа.
Продолжая процесс в конце концов получим дерево сортиру-
ющей сети, корень которого выдаст полностью отсортированный
поток (см. рис. 1). Высота дерева log
2
n, а ширина n/2.
В сети имеются каналы; входные и выходные каналы должны
быть разделяемыми.
Рис. 1. Распараллеливание процесса слияния
Пример 3. Фильтр для слияния двух входных потоков.
chan in1(int), in2(int), out(int);
process GLUE{
int v1, v2;
receive in1(v1);
receive in2(v2); # получены первые два входных числа
# меньшее из чисел отправить
# в выходной канал и повторить
while(v1!=EOS and v2!=EOS){
12
Страницы
- « первая
- ‹ предыдущая
- …
- 9
- 10
- 11
- 12
- 13
- …
- следующая ›
- последняя »
