Составители:
II барьер: старые значения используются, и потому должны
быть сохранены;
III барьер: перед переходом на следующий уровень нужно про-
вести все необходимые вычисления.
Замечания. 1) Алгоритм может быть изменен для любой ассо-
циативной бинарной операции (коммутативность не обязательна).
2) Программа может быть адаптирована к числу процессов
меньше n; при этом каждому процессу придется поручить больше
работы.
§14 Операции со связанными списками
Рассмотрим задачу об отыскании конца связанного списка с n эле-
ментами, у которого связи хран ятся в массиве link[n], а данные
списка хранятся в массиве data[n].
Пусть на начало списка указывает переменная head, а конец
списка характеризуется указ ателем null (см. рис. 5).
Рис. 5. Иллютрация связей в списке
Задач а состоит в организации систематической перестройки
указател ей так, чтобы все они указывали в null.
Последовательное решение этой задачи требует n тактов, а при
параллельном решении потребуется dlog
2
ne тактов (здесь dae озна-
чает наименьшее целое k, для которого k ≥ a).
Пусть end[n] — разделяемый массив типа integer. Для просто-
ты будем считать, что link[i] — также целочислен ный массив, что
пус той указатель null интерпретируется числом −1, и при i < n−1
элемент link[i] содержит индекс следующего элемента списка, т.е.
число i + 1; кроме того, пусть link[n − 1] == null.
Первоначально каждый процесс присваивает элементу end[i]
значение link[i] (т.е. индекс следующего элемента списка). Процес-
сы выполняют несколько этапов, на каждом из которых элементу
end[i] присваивается значение end[end[i]], если такое вычисление
имеет смысл и дает индекс элемента, имеющегося в списке data[n],
или null — в противном случае.
71
Страницы
- « первая
- ‹ предыдущая
- …
- 68
- 69
- 70
- 71
- 72
- …
- следующая ›
- последняя »
