ПРОГРАММНЫЕ ЗАВИСИМОСТИ И БАЗОВЫЕ ПРЕОБРАЗОВАНИЯ УпрАВлЯюЩий грАф прогрАммы Управляющий граф [8], [12] – это одна из основ преобразования программ. даже если в описании преобразования управляющий граф не упоминается, то он, как правило, подразумевается. в явном или неявном виде управляющий граф присутствует во внутренних представлениях оптимизирующих/распараллеливающих компиляторов. перед описанием преобразований и управляющего графа программ следует определиться, о каких программах будет идти речь. программы – это предложения языков программирования. в научной литературе высокоуровневые преобразования более всего описаны для программ языка Фортран. встречаются также описания преобразований для языков си и паскаль, реже – для других высокоуровневых языков. абстрагируемся от этих конкретных языков, чтобы преобразования носили как можно более общий характер. будем считать, что рассматриваемые программы содержат следующие операторы: операторы присваивания, циклы со счетчиком (параметром, считающим итерации), блочные условные операторы, операторы безусловного перехода на метку GOTO, пустые операторы, блочные операторы (операторные скобки), 7 операторы вызова подпрограммы (процедуры или функции). предполагается, что в рассматриваемом языке программирования допускается конкатенация операторов. данные описываются только константами, скалярными переменными и массивами. программы могут исполняться, изменяя этим самым состояние памяти компьютера. исполнение программы состоит в чтении единиц языка (операторов, линейных участков), сопоставлении переменных, входящих в выражения с их значениями и изменении значений переменных (соответствующих им состояний ячеек памяти). последовательность чтения единиц языка определяется семантикой языка программирования. если две единицы языка могут прочитаться при некотором исполнении программы одна после другой, то говорят, что они связаны <...>
Распараллеливание_программ.pdf
УДК 519.6+681.3.012
ББК 22.193+32.973.26–018.2
С 13
Печатается по решению редакционно-издательского совета
Южного федерального университета
Учебник подготовлен и издан
в рамках национального проекта
«Образование» по «Программе развития федерального
государственного образовательного учреждения
высшего профессионального образования
″Южный федеральный университет″ на 2007–2010 гг.»
Савельев В. А., Штейнберг Б. Я.
с 13
распараллеливание программ: учебник / в. а. савельев, б. Я. Штейнберг. –
ростов н/д: изд-во юФУ, 2008. – 192 с.
ISBN 978-5-9275-0547-0
Учебник посвящен параллельным вычислениям, которые сегодня занимают все
большее место в теории и практике программирования. рассматривается как теория
преобразований и распараллеливания программ, так и инструменты практического параллельного
программирования.
адресован студентам и аспирантам математических и естественнонаучных специальностей.
УДК
519.6+681.3.012
ISBN 978-5-9275-0547-0
ББК 22.193+32.973.26–018.2
© савельев в. а., 2008
© Штейнберг б. Я., 2008
© южный федеральный университет, 2008
© оформление. Макет. издательство
южного федерального университета, 2008
Стр.2
оглавление
введение .........................................................................................................................5
1. распараллеливаюЩие/оптиМизирУюЩие преобразованиЯ
програММ ....................................................................................................................7
програММнЫе зависиМости и базовЫе преобразованиЯ .................7
преобразованиЯ линейнЫХ УЧастков ......................................................19
преобразованиЯ циклов ...................................................................................34
реШетЧатЫй граФ как Модель инФорМационной
зависиМости в гнездаХ циклов ..................................................................61
распараллеливание ............................................................................................72
конвейернЫе вЫЧислениЯ ..............................................................................89
2. основнЫе средства параллельного програММированиЯ ..........103
использование OpenMP ......................................................................................103
основные понятия .................................................................................................104
директивы OpenMP API ........................................................................................106
Функции времени выполнения OpenMP ..............................................................116
комбинированные конструкции ...........................................................................117
простые примеры использования OpenMP .........................................................118
библиотека POSIX® thread ....................................................................................124
типы данных pthread .............................................................................................125
Управление нитями ................................................................................................126
простой пример .....................................................................................................132
синхронизация .......................................................................................................133
Частные данные нити ............................................................................................139
передаЧа сообЩений .......................................................................................143
обзор языков и систем .........................................................................................143
PVM ........................................................................................................................145
Erlang ......................................................................................................................148
Parallaxis III ............................................................................................................154
програММирование на MPI .............................................................................160
основные свойства ................................................................................................161
среда выполнения ..................................................................................................165
взаимодействия точка-точка .................................................................................166
коллективные взаимодействия .............................................................................175
коммуникаторы ......................................................................................................180
интеркоммуникаторы ............................................................................................183
топология ................................................................................................................184
пользовательские типы данных ...........................................................................184
прилоЖение. использование Pthreads-Win32 .........................................................188
список литератУрЫ ................................................................................................190
3
Стр.3