Таким образом, мы получаем доступ
Таким образом, мы получаем доступ к последнему элементу списка за log2N шагов. Аналогичные алгоритмы, также использующие информационную избыточность, могут быть построены и для других операций над списками.
Реализация операций над списками для локально-асинхронной ВС, каковой является ВС SPMD-архитектуры, допускает использование принципа монопрограммирования, т.е. составления единственной программы, запускаемой на всех процессорах одновременно. Здесь мы приведем монопрограмму нахождения последнего элемента списка и проследим процесс ее выполнения. Она выбрана потому, что нахождение последнего элемента является частью многих операций над списками. Например, для объединения списков L1 и L2 достаточно найти последний элемент списка L1 и заменить в его поле C пустую ссылку ссылкой на первый элемент списка L2.
Как говорилось выше, для организации параллельной обработки целесообразно использовать образ R списка — массив информации об элементах списка, содержащий сведения о его структуре и преемственности элементов. Отметим, что упорядоченность элементов массива R в памяти в общем случае может не совпадать с логической упорядоченностью элементов списка, задаваемой ссылками. Это позволяет достаточно просто интерпретировать выполнение операций над списками. Например, при добавлении новых элементов в список L нет необходимости вставлять новый элемент массива R в какую-либо конкретную позицию - можно просто добавить его в конец массива. Аналогично, при исключении элемента из L вместо уплотнения массива R на освободившееся место можно записать его последний элемент.
Обработку списка, таким образом, мы сводим к обработке массива, представляющего его образ. Этот массив, в свою очередь, может описываться дескриптором.
Дескриптор DR массива R={V,C,D}1^N в полной комплектации, как рассматривалось ранее, состоит из восьми элементов: DR={DRO , ..., DR7}. Дескрипторный элемент DRO содержит адрес a0 первого элемента массива, DR1 — шаг h = 3 переадресации, DR2 — количество N элементов массива, в DR3 находится адрес последнего элемента массива.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий