Распараллеливание программ для суперкомпьютеров с параллельной памятью и открытая распараллеливающая система

• Автор: Штейнберг, Борис Яковлевич
• Шифр специальности: 05.13.11
• Научная степень: Докторская
• Год защиты: 2004
• Место защиты: Ростов-на-Дону
• Количество страниц: 343 с. : ил.

ГЛАВА 1. РАСПАРАЛЛЕЛИВАЩИЕОПТИМИЗИРУЮЩИЕ ПРЕОБРАЗОВАНИЯ ПРОГРАММ. ОБ ИССЛЕДОВАНИЯХ РАСПАРАЛЛЕЛИВАНИЯ ПРОГРАММ. КОРРЕКТНОСТЬ ПРЕОБРАЗОВАНИЙ. ПРЕОБРАЗОВАНИЯ ПРОГРАММ. Перестановка фрагментов. Канонизация циклов. Раскрутка цикла. Расщепление одномерного цикла. Развертка цикла. Разбиение цикла. Слияние циклов. Приведение цикла к разбиваемому виду. Информационная зависимость в многомерных циклах. Подстановка. Переименование переменных. ГЛАВА 2. РАСПАРАЛЛЕЛИВАНИЕ РЕКУРРЕНТНЫХ ЦИКЛОВ. РАСПАРАЛЛЕЛИВАНИЕ ЛИНЕЙНЫХ РЕКУРРЕНТНЫХ ЦИКЛОВ И РЕШЕНИЕ СЛАУ С ТРЕУГОЛЬНЫМИ ЛЕНТОЧНЫМИ МАТРИЦАМИ. ЦИКЛЫ С НЕЛИНЕЙНОЙ РЕКУРРЕНТНОЙ ЗАВИСИМОСТЬЮ. ПОСТОЯННЫЕ ЛИНЕЙНЫЕ РЕКУРРЕНТНЫЕ ЗАВИСИМОСТИ. ПРИНЦИП СДВАИВАНИЯ ДЛЯ ВЫЧИСЛЕНИЯ РЕКУРРЕНТНЫХ ЦИКЛОВ
2. Обобщение вычисления минимального элемента массива. ГЛАВА 3. ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ. ОБ ОПТИМАЛЬНОМ КОЛИЧЕСТВЕ ПРОЦЕССОРОВ ПРИ ПАРАЛЛЕЛЬНОМ ВЫЧИСЛЕНИИ ПРОГРАММНЫХ ЦИКЛОВ. Устройства для обменов данными. Рекуррентное вычисление массивов данных5

3. Вычисление скалярных переменных.

Поэтому, такая проверка не подходит для построения графа информационных связей, но вполне годится для проверки входных зависимостей, которые нужны при размещении данных в параллельной памяти. Одной из простых моделей информационной зависимости во фрагментах программы со скалярными переменными являются цепочки 5. Эти цепочки эффективны при таких скалярных оптимизационных преобразованиях, как протягивание констант или удаление мертвого кода, включая и мертвые ветки условных операторов. При описании конвейеризации будет использоваться граф вычислений. Граф вычислений это помеченный граф. Вершинами этого графа являются операции программы, метка тип операции. Дуга соединяет операцию а с операцией Ь, если результат операции а используется операцией Ь. Для текстов программ, не содержащих условных операторов, это определение не требует дополнительных оговорок. Напомним, что две программы называются эквивалентными, если на одних и тех же входных данных они дают одинаковые выходные данные. Очевидно, если графы вычислений двух программ изоморфны, как помеченные графы, то рассматриваемые программы эквивалентны. Заметим, что если в графе информационных связей есть дуга истинной информационной зависимости, то этой дуге соответствует дуга в графе вычислений. В цикле скалярные переменные, которые не являются счетчиком этого цикла, называются внешними. Существуют специальные методы определения информационной зависимости в случаях, когда в индексных выражениях присутствуют индуктивные переменные 8 или иные внешние переменные 0. В работе 8 рассмотрено определение информационной зависимости для нелинейных билинейных индексных выражений.