Теория проблемно-ориентированных типовых алгоритмических структур с массивным параллелизмом

• Автор: Берзигияров, Парваз Куламович
• Шифр специальности: 05.13.11
• Научная степень: Докторская
• Год защиты: 2001
• Место защиты: Москва
• Количество страниц: 241 с. : ил

1.1. Крупномасштабные вычисления н параллельная обработка данных.

1.2. Программирование параллельных вычислительных систем.

1.2.1. Введение

1.2.2. Свойства систем параллельного профаммирования.

1.2.3. Классификация систем параллельного программирования.

1.2.4. Абстрактные системы с неявным параллелизмом.

1.2.4.1. Декларативные языки спецификации с элементами синтеза параллельных профамм

1.2.4.2. Функциональные языки с неявным параллелизмом.

1.2.4.3. Логическое программирование с неявным параллелизмом.

1.2.4.4. Распараллеливающие компиляторы.

1.2.5. Языки высокого уровня с явным параллелизмом.

1.2.5.1. Параллелизм по данным I
1.2.5.2. Расширения императивных языков
1.2.5.3. Языки скелетонов 3I.
1.2.6. Языки низкого уровня с явным параллелизмом
1.2.6.1. Обмен сообщениями I.
1.2.6.2. Мультитредовыс системы I.
1.2.7. Сравнительный анализ систем параллельного программирования .
1.3. Заключение
Глава 2. ТЕХНОЛОГИЧЕСКИЕ АСПЕКТЫ РАЗРАБОТКИ КРУПНОМАСШТАБНЫХ ВЫЧИСЛИТЕЛЬНЫХ ЗАДАЧ С МАССИВНЫМ ПАРАЛЛЕЛИЗМОМ НИЗКОУРОВНЕВЫЙ ПОДХОД
2.1. Основные технологические этапы разработки.
2.2. Параллельная реализация СIметода для крупномасштабного моделирования гидродинамических неустойчивостей и струйных течений
2.2.1. Введение
2.2.2. Постановка задачи.
2.2.3. Параллелизм.
2.2.4. Декомпозиция данных.
2.2.5. Организация взаимодействий
2.2.6. Ускорение и масштабируемость
2.2.7. Модель программы
2.2.8. Схема вычислений
2.2.9. Вычислительный эксперимент анализ производительности
2.2 Вычислительный эксперимент моделирование РелэйТейлоровских неустойчивостей и струйных течений.
2.3. Параллельная реализация модифицированного мегода для крупномасштабных квантовохимических расчетов полуэмпирическими методами.
2.3.1. Введение
2.3.2. Основные вычислительные аспекты комплекса С2
2.3.3. Приближение .
2.3.4. Основные алгоритмы последовательного комплекса 2.
2.3.5. Параллельная реализация приближения в программе V.
2.3.5.1. Параллельная реализация модуля диагонализации
2.3.5.2. Параллельная реализация вычислений матрицы электронной плотности.
2.3.5.3. Параллельная реализация ССПвычислений и процедур построения матрицы Фока , остовного гамильтониана и вычисления градиентов полной энергии по декартовым координатам атомов
2.3.6. Ускорение и эффективность программы V.
2.3.7. Вычислительный эксперимент
2.3.8. Развитие программы V
2.4. Заключение.
Глава 3. ПРОГРАММИРОВАНИЕ НА ТИПОВЫХ АЛГОРИТМИЧЕСКИХ СТРУКТУРАХ С МАССИВНЫМ ПАРАЛЛЕЛИЗМОМ
3.1. Введение.
3.2. Базовые алг оритмические структуры.
3.3. Проблемноориентированные алгоритмические структуры
3.4. Управляющие алгоритмические структуры композиция и вложенность
3.4.1. Композиция последовательных модулей с помощью единичных
3.4.2. Иерархическая композиция ГАС вложенность
3.5.Горизонтальная композиция алгоритмических структур
3.6. Идентификация ТАС в Iметоде.
3.7. Оптимизирующие преобразования .
3.7.1. Оптимизация горизонтальных композиций ТАС
3.7.2. Оптимизация вложенных композиций ТАС.
3.7.3. Взаимные преобразования статическая конвейеризация структур
3.7.3.1. Введение
3.7.3.2. Постановка задачи.
3.7.3.3. Статическая конвейеризация алгоритмов.
3.8. Особенности реализации типовых алгоритмических структур
3.8.1. Модель параллельной программы
3.8.2. Промежуточная абстрактная машина обеспечение мобильности и эффективности ТАС.
3.8.3. Объектная ориентированность механизмы повторного использования и специализации ТАС.
3.9. Заключение
Глава 4. ФОРМАЛЬНЫЕ МЕТОДЫ ПОСТРОЕНИЯ И ОПТИМИЗАЦИИ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ И ПРОГ РАММ.
4.1. Формальный вывод эффективных параллельных алгоритмов и программ
из абстрактных спецификаций
4.2. Дедуктивный вывод параллельных вычислительных алгоритмов.
4.2.1. Введение.
4.2.2. Описание подхода Логические спецификации свободных параллельных алгоритмов.
4.2.3. Логическая спецификация прямых методов решения систем линейных уравнений в рамках стратегии исключения
4.2.4. Вывод параллельной формы алгоритма Гаусса.
4.2.5. Учет архитектурного аспекта и вывод других алгоритмов.
4.2.6. Заключение
4.3. Вывод эффективных вычислительных алгоритмов методом переписывания термов.
4.3.1. Введение
4.3.2. Постановка задачи конструирование оптимальных алгоритмов
4.3.3. Постановка задачи конструирование эффективных алгоритмов посредством улучшающих преобразований
4.3.4. Система переписывания термов
4.3.5. Оптимизирующие преобразования.
4.3.6. Пример вывод алгоритма Штрассена.
4.3.7. Программная реализация системы
4.3.8. Заключение
4.4. Логические методы синтеза параллельных программ из непроцедурных спецификаций.
4.4.1. Введение
4.4.2. Внешние спецификации Формальная система .
4.4.3. Синтаксис и семантика языка программирования .
4.4.3.1. Синтаксис языка
4.4.3.2. Операционная семантика языка I
4.4.4. Внутренние спецификации Формальная система для спецификации и вывода алгоритмов и параллельных программ
4.4.5. Корректность системы .
4.4.6. Особенности реализации системы
4.4.7. Применение системы
4.4.8. Заключение
ЗАКЛЮЧЕНИЕ.
СПИСОК ЛИТЕРАТУРЫ


БЭР 9, 0, 9, 3, 8, 9, 0, 4, модели потоков данных 1, функциональные и логические модели . САТ 7, всевозможные теории процессов СЯРХСЭ, рисчисление . Каждая из этих моделей обеспечивает эффективный стиль программирования только для конкретною класса вычислительных систем. Ни одна из моделей не обеспечивает не только эффективность программы на другой системе, но даже и возможность простого переноса кода на новую систему. Ситуация изменилась в лучшую сторону только в последние несколько лет, в связи с усилиями но стандартизации систем параллельного программирования 2 и некоторыми тенденциями по конвергенции архитектурных принципов , 9. Ответ на второй вопрос кроется с одной стороны, в силе традиции, а с другой стороны, в прагматике. Сила традиции проявляется в стремлении использовать для программирования параллельных систем языки близкие к последовательным аналогам. Даже в тех случаях, когда предлагаются языки по выразительной силе и стилю очень близкие к традиционной математической практике, как это имеет место в случае с функциональными языками , 7, 8, 9. ФОРТРАН или Си. Прагматика же проявляется в стремлении перенести на параллельные системы огромный фонд последовательных программ, написанных, как правило, на различных диалектах языка ФОРТРАН, т. Кроме того, нрисутствует естественное стремление как можно меньше иметь дело с параллелизмом в явном виде. Резюмируя, можно сказать, что большое многообразие языковых средств параллельного программирования, отражает ситуацию, хараюеризующуюся отсутствием языков, обеспечивающих переносимость программного кода и его эффективность при переходе с одной параллельной системы на другую 9, 1, 4. Существует и ряд других факторов, препятствующих широкому применению параллельных вычислительных систем. Остановимся теперь на некоторых желательных свойствах, которым должны удовлетворять параллельные системы программирования. Список сформирован, на основе анализа работ различных авторов 2, 8, 4, , а также с учетом собственного опыта. Удобство и легкость программирования. В эту группу входят свойства полезные программистам. Пор тируемое гь одна из наиболее важных групп свойств, ввиду большого разнообразия используемых архитектурных принципов и трудностей в прогнозе путей развития параллельных вычислений. В силу этого модели нс должны опираться на какуюто конкретную архитектуру с тем. Эффективность модель должна допускать эффективную реализацию на различных архитектурах. Меры сложности должны обеспечивать правдоподобные оценки эффективности программ на различных архитектурах. Общепринятой является классификация языков параллельного программирования по уровням абстракции 4, 1. В процессе разработки параллельной программы можно выделить следующие три сталии 1. Декомпозиция iii на этой фазе определяется потенциальный параллелизм и осуществляется декомпозиция задачи на параллельные подзадачи. Отображение i на этом этапе осуществляется отображение процессов на физические процессоры. Чем больше из этих этапов перекладывается с программиста на систему, тем более абстрактной считается система. Эта идея положена в основу классификации, используемой в работах ряда авторов 4. Абстрактные системы с неявным параллелизмом. В эту группу входят подходы, в рамках которых программист полностью изолирован от каких бы то ни было вопросов, связанных с параллелизмом. Высокоуровневые системы с явным параллелизмом. Низкоуровневые системы с явным параллелизмом. В последнюю группу входят языки и системы параллельного программирования, в которых реализация всех трех этапов возлагается на программиста. В таблице 1. Таблица 1. V, I. Как уже отмечалось выше, в эту группу входят системы, полностью освобождающие программиста от выявления, спецификации и управления параллелизмом. Распараллеливающие компиляторы. В первых трех случаях программист опирается на потенциальный параллелизм соответствующей модели вычислений. В последнем случае, компилятор осуществляет анализ последовательной программы с целью организации параллельных вычислений. Как правило, эго относиться к регулярным вычислениям, сосредоточенным в циклах.