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


              

Далее следует переход на начало


Далее следует переход на начало третьего цикла обработки ссылок (такт 16), но, обнаружив ненулевое значение модификатора K (такт 17), в следующем такте процессор П1 также завершает свою работу. Результатом совместной работы трех процессоров является адрес ссылки на последний элемент списка, записанный в модификаторе K.

Заметим, что детерминированный — при синхронной работе процессорных элементов — процесс выполнения алгоритма при реализации на локально-асинхронной ВС приобретает некоторую неопределенность. Дело в том, что мы не можем быть уверены в порядке выполнения процессорами операций замены значений ссылок (команда 6), поскольку в принципе не исключены обращения к одним и тем же модулям общей памяти. В результате какой-либо процессор может "подхватить" уже обновленную ссылку. Однако очевидно, что это только приблизит окончание работы алгоритма, который в таком случае как бы "перескакивает" через некоторые шаги. Например, элемент A, обрабатываемый процессором П0, после первого выполнения процессором команды 6 должен содержать ссылку на элемент E. Но если процессор П1 успел по какой-либо причине выполнить свою аналогичную операцию раньше, элемент A будет содержать ссылку на более "удаленный" от него элемент F. Поэтому появляется возможность более раннего достижения условия окончания работы программы.

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


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