Читать онлайн «Распараллеливание алгоритмов и программ. Структурный подход»

В. А. Вальковский РАСПАРАЛЛЕЛИВАНИЕ АЛГОРИТМОВ И ПРОГРАММ СТРУКТУРНЫЙ ПОДХОД МОСКВА «РАДИО И СВЯЗЬ» 1989 УДК 519. 681. 5 Вальковский В. А. Распараллеливание алгоритмов и программ. Структурный подход. —М. : Радио и связь, 1989. — 176 с, ил. — ISBN 5-256-00195-7. Посвящается проблеме автоматического распараллеливания алгоритмов и программ для последующего их исполнения на многопроцессорных вычислительных комплексах. Вводятся и изучаются с математических позиций параллельные вычислительные процессы над общей памятью. Рассматриваются вопросы максимального распараллеливания операторных схем для различных отношений эквивалентности. Предлагаются методы организации динамического распараллеливания программ. Доказывается ряд теорем, дающих необходимые и достаточные условия максимальной распараллеливаемости схем программ заданного класса в динамическом режиме. Приводятся некоторые важные следствия из этих теорем. Построены конкретные алгоритмы распараллеливания. Отдельно рассматриваются вопросы параллельной реализации циклических участков программ. Вводятся и обосновываются два метода распараллеливания — параллелепипедов и пирамид, ориентированные на различные типы вычислителей. Изложение сопровождается подробными примерами. Приводится обзор действующих векторизаторов и распараллеливающих программ. Для научных работников. Рекомендуется инженерам, занимающимся вопросами параллельного программирования, микропрограммирования, разработкой многопроцессорных ЭВМ и математического обеспечения для них. Табл. 12. Ил. 40. Библиогр. 56 назв. Рецензент доктор техн. наук, проф. Б. А. Головкин Редакция литературы по вычислительной технике 2404010000-018 В 58-89 046(01)-89 ISBN 5-256-00195-7 © Издательство «Радио и связь», 1989 ПРЕДИСЛОВИЕ Прогресс в вычислительной технике, в частности разработка вычислительных средств перспективных поколений, вызвал интенсивное развитие соответствующего математического обеспечения. Образовалась специальная область науки, изучающая возникающие при этом проблемы, — параллельное программирование. Одной из проблем параллельного программирования является задача десеквенции, т. е. распараллеливания алгоритмов, программ или непосредственно вычислений. Первоначально под распараллеливанием понималось преобразование последовательной программы в эквивалентную параллельную, обрабатываемую одновременно на нескольких процессорах. В настоящее время в этот термин вкладывается более широкий смысл. Распараллеливанием называют комплексную процедуру «подгонки» алгоритма, программы или даже вычислительного метода к архитектуре конкретного или гипотетического вычислительного комплекса. Общая проблема «подгонки» структуры программы под архитектуру ЭВМ не является новой. Известны различные методы реструктуризации программ в целях оптимального использования памяти, быстродействующих регистров, каналов связи, устройств ввода-вывода и т. д. Специфика обработки, связанная с многопроцессорностью, также оказала влияние на эту проблему. Разные типы архитектур обусловили разные «оттенки» постановки задачи распараллеливания.