Параллельное программирование



     аренда спецтехники объявления. | для собак интернет магазин |          

Нахождение последнего элемента списка


Одним из наиболее часто используемых способов организации информации в памяти ЭВМ является ее представление в виде списков, которые позволяют оперировать не с самими величинами, а с их адресами, что облегчает программирование, экономит память и сокращает затраты на пересылку информации. С помощью списков удобно отображать данные самой разнообразной структуры: множества, деревья, графы, строки и т.д.

Основными операциями над списками являются: получение доступа к произвольному элементу списка; включение нового элемента в заданное место списка и исключение его оттуда; сортировка элементов списка; поиск элемента с заданными свойствами и другие. Простота их реализации является одним из наиболее привлекательных свойств списковой организации данных. Однако традиционное представление списков на основе ссылок предполагает последовательную обработку их элементов. Все известные алгоритмы, реализующие операции над списками, являются последовательными и ориентированы на однопроцессорные ЭВМ фон-неймановской архитектуры.

Эффективная реализация операций над списками для параллельных вычислительных систем представляет непростую (а для некоторых архитектур — например, векторно-конвейерной — и неразрешимую) задачу. Особый интерес представляла бы разработка таких алгоритмов для ВС с большим числом процессорных элементов.

Под списком L будем понимать совокупность объектов вида In =(V, C), где V — ссылка на данные, C — ссылка на некоторый (следующий) элемент этого же списка. Последний элемент списка имеет своим значением nil, т.е. пустую ссылку.

Пусть элементы каждой двойки (V, C) расположены в памяти так, что их адреса определяются сложением фиксированного смещения с некоторым базовым адресом. Тогда совокупность всех двоек можно рассматривать как массив R — образ списка, в котором места расположения каждого элемента могут быть рассчитаны.

Интуиция подсказывает, что параллельная обработка списка невозможна, поскольку в общем случае необходимо вычислить адреса k предыдущих элементов списка, прежде чем станет доступен (k+1)-й элемент.


Содержание  Назад  Вперед