Прангишвили И. В. и др.
Параллельные вычислительные системы с общим управлением/ И. В. Прангишвили, С. Я. Ви-ленкин, И. Л. Медведев. — М.: Энергоатомиздат, 1983. —312 с., ил.
Изложены основы организации, возможные применения и сравнительный анализ различных типов параллельных многопроцессорных систем, обеспечивающих быстродействие до сотен миллионов операций в секунду. Всесторонне рассмотрены вопросы технического и программного обеспечения таких систем.
Для специалистов, работающих в области разработки и применения высокопроизводительных средств вычислительной техники. Будет полезна аспирантам и студентам вузов, специализирующимся в области вычислительной техники и программирования.
В первых четырех главах рассматриваются различные способы организации вычислительного процесса, варианты структур- вычислительных систем и их элементов, подходы к оценке их производительности и пути ее повышения. Дано краткое описание наиболее известных в наше время ПВС с ОУ.
В остальных главах описываются языки программирования и особенности вычислительных методов решения задач, в том числе методы преобразования последовательных алгоритмов в параллельные. Особое внимание уделяется задачам линейной алгебры и математической физики.
В заключительной главе исследуются вопросы организации асинхронных вычислений, обеспечивающие написание машинонезависимых параллельных программ. В приложении излагаются алгебраические основы параллельных вычислений.
Главы ] и 4 написаны И. Л. Медведевым, гл. 2 и 3— И. В. Прангишвили, гл. 5, 6, 9 и приложение — С. Я. Ви-ленкиным, гл. 7 и 8 по просьбе авторов написал Е. Г. Сухов, гл. 10 написана Ю. С. Затуливетром и И. Л. Медведевым.
Книга написана в основном по результатам работы авторов при создании параллельной вычислительной системы с общим управлением ПС-2000, выполненной в Институте проблем управления совместно с Научно-исследовательским институтом управляющих вычислительных машин (г. Северодонецк).
Естественно, что в небольшой монографии не могли найти полного отражения все аспекты рассматриваемых вопросов. Более подробные сведения по некоторым из них можно найти в соответствующей литературе.
Авторы сознают, что не на все поставленные вопросы они дали исчерпывающие ответы. Они будут весьма признательны за все критические замечания, которые просят направлять в адрес издательства: 113114, Москва, М-114, Шлюзовая наб., 10.
Авторы
ОГЛАВЛЕНИЕ
Предисловие............. 3
Глава 1. Вопросы оценки и выбора структур параллельных
ЭВМ.......,....... 5
1.1. Постановка задачи.......... 5
1.2. Оценка основных характеристик параллельной ЭВМ . . 7
1.3. Основные, типы устройств обработки данных ... 11
1.4. Оценка возможностей типовых устройств обработки данных..............1Г>
1.5. Увеличение пропускной способности и производительности решающих полей многопроцессорных машин . . 1!)
1.6. Совмещение операций..........22
1.7. Методы увеличения пропускной способности памяти .
1.8. Увеличение пропускной способности устройства обработки данных.............27
1.9. Основные способы организации вычислительного процесса в решающем поле..........27
1.10. Структуры машин.......... 32
1.11. Некоторые рекомендации по выбору структур машин 42
1.12. Типы параллельных ЭВМ с общим управлением . . 4:1
1.13. Базовая структура параллельной ЭВМ с общим управлением .............. 45
1.14. Организация управления параллельной ЭВМ ... 49
1.15. Организация ввода-вывода......... .г>(>
Глава 2. Некоторые особенности структурной организации многопроцессорных вычислительных систем......(id
2.1. Тенденции развития многопроцессорных вычислительных систем..............(ill
2.2. Способы связи устройств обработки данных с памятью данных..............ОН
2.3. Способы организации внутрисистемных связей ... ПК
2.4. Структура агрегатно-модульной многопроцессорной вычислительной системы . .......72
328
2.5. Способы повышения производительности вычислительных систем.............. 77
2.6. Оценка системной производительности и эффективности многопроцессорных вычислительных систем ... 86
Глава 3. Краткий обзор зарубежных параллельных многопроцессорных вычислительных систем с общим управлением
3.1. Системы для обработки векторной информации ... 93
3.2. Параллельная система ILLIAC IV......
3.3. Распределенный параллельный процессор DAP
3.4. Параллельная система Propal 2....... 101
3.4.1. Структура системы......... 101
3.4.2. Память обмена данных........ 102
3.4.3. Параллельная память данных . . . . . . ЮЗ
3.4.4. Параллельный ввод-вывод....... 103
3.4.5. Устройство обработки данных..... .104
3.4.6. Арифметические операции....... 105
3.4.7. Блок управления......... 105
3.4.8. Три конфигурации и режимы работы системы Pro-pal 2 .............. 107
3.4.9. Программирование......... ПО
3.5. Параллельные вычислительные системы с комбинированной структурой........... 112
. Глава 4. Параллельная система 2000 (ПС-2000) . . .114
4.1. Назначение............ 114
4.2. Особенности и состав.......... 114
4.3. Параллельный процессор ППС-2000...... 116
4.3.1. Процессорный элемент........ 116
4.3.2. Устройство управления........ 124
4.4. Структура управления ППС-2000...... 128
4.5. Мнемокод параллельного процессора ППС-2000 . . 129
4.6. Программный интерфейс параллельного процессора . . 130
4.7. Канал данных............ 131
4.8. Команды программного интерфейса для управления каналом денных............ 132
4.9. Основные характеристики ППС-2000...... 134
4.10. Субкомплекс внешней памяти....... 134
4.11. Структура вычислительных процессов в ПС-2000 . . 135
4.12. Программное обеспечение ПС-2000...... 136
4.13. Сравнение архитектурных особенностей ПС-2000 с параллельными системами......... 140
Глава 5. Языки программирования для параллельных вычислительных систем с общим управлением . . .... 143
5.1. Общие замечания........... 143
5.2. IVTRAN — язык программирования для ILLIAC IV . . И4
5.3. Операторы описания размещения массивов . . . . М8
5.4. Операторы перекрытия и переопределения , . . . 154
5.5. GLYPNIR и TRANQUIL — алголоподобные языки для многопроцессорных систем с общим управлением . • . . 155
5.6. Язык ВЕКТОР............ 100
Глава 6. Выбор вычислительных методов для параллельных
вычислительных систем.......... ПИ
6.1. Критерии выбора алгоритма реализации вычислительного метода.............. НИ
6.2. Выбор алгоритма по критерию точности результата . . 109
6.3. Методы преобразования последовательных алгоритмов
в параллельные....... ... 173
6.4. Организация вычислений при наличии разнотипных операций .............. 182
6.5. Организация размещения в памяти промежуточных результатов вычислений . . ....... IHN
6.6. Оптимизация структур данных при последовательном выполнении цепочки алгоритмов . . ..... I'-'l
Глава 7. Решение задач линейной алгебры . . . . . 195
7.1. Параллельные вычисления........ 1!>5
7.2. Вычислительная модель......... 1!И'
7.3. Выполнение арифметических операций..... 1!»Н
7.4. О решении задач линейной алгебры...... '.'<>"
7.5. Клеточные операции...........202
7.5.1. Умножение строки на клетку...... 202
7.5.2. Скошенная форма хранения клетки . . . , 203
7.5.3. Обращение WX^'-клетки методом Жордана . . '.'().',
7.5.4. Обращение треугольной матрицы-клетки . . . 204
7.5.5. Метод квадратного корня....... 205
7.5.6. Решение линейной системы с треугольной невырожденной матрицей . ......... 205
7.5.7. LU-разложение с перестановкой строк . . . 200
7.6. Решение задач большой размерности..... 207
7.7. Итерационные методы решения линейных систем . . '.'пч
7.8. Нелинейные задачи.......... "им
7.9. Алгебраическая проблема собственных значений' . . 21
7.10. Организация процесса решения задач..... '.'IS
Глава 8. Параллельные численные методы..... :>|<>
8.1. Быстрые алгоритмы.......... 216
8.2. Численное решение уравнений в частных производных 310
Глава 9. Реализация невычислительных задач на параллельных вычислительных системах с " общим управлением
9.1. Сортировка на параллельной ЭВМ с регулярным каналом ..............
9.2. Идеальный тасовщик на логарифмическом коммутаторе 243
9.3. Реализация параллельной сортировки Бэтчера N элементов на параллельной ЭВМ, состоящей из N ПЭ
9.4. Сортировка со слиянием массивов размером rN на N параллельных процессорах . . .- . .
9.5. Поиск в упорядоченном по ключу массиве
9.6. Обобщенные числа Фибоначи.....' 251
9.7. Организация и ведение поискового дерева на параллельной ЭВМ.......... 255
Глава 10. Организация вычислений* с управлением потоками данных в параллельных системах с общим управлением . 101. Особенности вычислений с управлением потоками данных ....., .".......'259
10.2. Информационно-потоковые графы — модель описания вычислительных процессов........261
10.3. Машинное представление информационно-потоковых графов.............273
10.4. Принципы машинной реализации и информационно-потоковая схема многопроцессорной вычислительной системы............* . . 280
10.5. Особенности вычислительных процессов Приложение. Алгебраические основы структур данных .
П.1. Структуры данных.....
П.2. Алгоритмы над индексными множествами .... 293 П.З. Отношения между операторами как источник параллелизма ........•.....
П.4. Структуры индексных множеств, порождаемые операторами ..............299
Список основных сокращений . . . .'..'•'.....300
Список литературы.............302
