Мгу им. М. В. Ломоносова. Для студентов, аспирантов, научных работников, программистов и всех, кто хочет научиться разрабатывать программы для парал­лельных ЭВМ




НазваниеМгу им. М. В. Ломоносова. Для студентов, аспирантов, научных работников, программистов и всех, кто хочет научиться разрабатывать программы для парал­лельных ЭВМ
страница1/27
Дата публикации04.11.2013
Размер2.99 Mb.
ТипДокументы
uchebilka.ru > Информатика > Документы
  1   2   3   4   5   6   7   8   9   ...   27



&L.
основы параллельного граммирования


"t эг .тгс?

~1--— i

Ч-


»?

;^. .,

^* ~-

*"■*

Л'

-.Н

Ire





x-VAL х = х + 1 VAL = X

f
y=VAL

у=у+1

VAL=y


К"'.J

J«£a-

VAL


] . t.


TUJU N Е ( К И И УНИВЕРСИТЕТ

| гЩ_ КЮ.Богачев

ОСНОВЫ

параллельного программирования

%.

Москва

БИНОМ. Лаборатория знаний

2003

NIK 001.(if)

i;i;k :\\>.ш

НогачёвК. Ю.

IJ.'IO Основы параллельного программирования / К. Ю. Бо­гаче».—M.: БИНОМ. Лаборатория знаний, 2003.-342 с, ил л.

ISBN 5-94774-037-0

Данная книга представляет собой введение в методы програм­мирования для параллельных ЭВМ. Основной ее целью является научить читателя самостоятельно разрабатывать максимально эф­фективные программы для таких компьютеров. Вопросы распарал­леливания конкретных алгоритмов рассмотрены на многочисленных примерах программ на языке С. В основу книги положен курс лек­ций для студентов механико-математического факультета МГУ им. М. В. Ломоносова.

Для студентов, аспирантов, научных работников, программистов и всех, кто хочет научиться разрабатывать программы для парал­лельных ЭВМ.

УДК 004.65 ББК 32.073

© Богачёв К.Ю., 2001, 2003
© БИНОМ. Лаборатория
ISBN 5-94774-037-0 знаний, 2003

Оглавление

Предисловие 7

Порядок чтения 9

Глава 1. Для нетерпеливого читателя 10

  1. Последовательная программа 10.

  2. Ускорение работы за счет параллелизма 12

  3. Параллельная программа, использующая процессы . 13

  4. Параллельная программа, использующая задачи 18

  5. Параллельная программа, использующая MPI 21

Глава 2. Пути повышения производительности процессоров ... 24

  1. CISC- и RISC-процессоры 24

  2. Основные черты RISC-архитектуры 25

  3. Конвейеризация 26

  4. Кэш-иамять 34

  5. Многопроцессорные архитектуры 39




  1. Основные архитектуры 39

  2. Комбинированные архитектуры 40

  3. Обанкротившиеся архитектуры 43




  1. Поддержка многозадачности и многопроцессорности 44

  1. Использование параллелизма процессора для повыше­ния эффективности программ 45

Глава 3. Пути повышения производительности оперативной па­
мяти 61


Глава 4. Организация данных во внешней памяти 64

4 Оглавление

Глава 5. Oi мойные положения 66

  1. < ><шишиг определения 66

  2. Им м.i ресурсов 72

  3. Г I it шммодействия процессов 73

5.1. ('<»« inviимя процесса 77

Глава 6. ('г.тд;фТ1,1 на операционные системы UNIX 79

  1. ('........p. BSD 4.3 79

  2. ('та.. .;,рт UNIX System V Release 1 79

  3. ('.;... ...|»г POSIX 1003 80

  4. (:..... .,,pr UNIX X/Open 80

^ Глава 7. Упр.иимиио процессами 81

  1. Футмшя fork 81

  2. Функции excel, execv 84

  3. Функция waitpid 84

  4. Функция kill 87

  5. Функция signal 88

Глава 8. Синхронизация и взаимодействие процессов 96

8.1. Разделяемая память 97

8.1.1. Функция shmget 98

8Л/2. Функция shmat 99

8Л.'Л. Функция shmctl 99

8.2. Семафоры 100

  1. Функция semget 103

  2. Функция semop 103

  3. Функция semctl 104

8.2.1. Пример использования семафорои и разделяе­
мой памяти 104

66

  1. События 120

  2. Очереди сообщений (почтовые ящики) 122




  1. Функция msgget 124

  2. Функция msgsnd 124

  3. Функция msgrcv 125

  4. Функция msgctl 126

  5. Пример использования очереден 126

  6. Функция pipe 133

8.5. Пример многопроцессной программы, ш.гшеляющей
произведение матрицы на вектор 135

Оглавление

5

^ Глава 9. Управление задачами (threads) 156

  1. Функция pthread_create 156

  2. Функция pthread_Join 157

  3. Функция sched_yield 157

Глава 10. Синхронизация и взаимодействие задач 158

10.1. Объекты синхронизации типа mutex 158

  1. Функция pthread_mutex_init 161

  2. Функция pthread_mutex_lock 162

  3. Функция pthread_mutex_trylock 162

  4. Функция pthread_mutex_unlock 162

  5. Функция pthread_mutex_destroy 163

  6. Пример использования mutex 163




  1. Пример multithread-программы, вычисляющей опреде­ленный интеграл 168

  2. Объекты синхронизации типа condvar 168




  1. Функция pthread_cond_init 170

  2. Функция pthread_cond_signal 171

  3. Функция pthread_cond_broadcast 171

  4. Функция pthread_cond_wait 172

  5. Функция pthread_cond_destroy 172

  6. Пример использования condvar 172




  1. Пример multithread-программы, вычисляющей произ­ведение матрицы на вектор 178

  2. Влияние дисциплины доступа к памяти на эффектив­ность параллельной программы 192

  3. Пример multithread-программы, решающей задачу Ди­рихле для уравнения Пуассона 202

^ Глава 11. Интерфейс MPI (Message Passing Interface) 232

  1. Общее устройство MPI-программы 232

  2. Сообщения 234

  3. Коммуникаторы 237

  4. Попарный обмен сообщениями 238

  5. Операции ввода-вывода в MPI-программах 240

  6. Пример простейшей MPI-программы 242

  7. Дополнительные функции для попарного обмена сооб­щениями 243

  8. Коллективный обмен сообщениями 250

6 Оглавление

11.9. Пример MPI-ирограммы, вычисляющей определен­
ный интеграл 256

  1. Работа с временем 259

  1. Пример MPI-программы, вычисляющей произведение матрицы на вектор 261

  2. Дополнительные функции коллективного обмена со­общениями для работы с массивами 273

  1. Пересылка структур данных 277




  1. Пересылка локализованных разнородных дан­ных 277

  2. Пересылка распределенных однородных дан­ных 288




  1. Ограничение коллективного обмена на подмножество процессов 290

  1. Пример MPI-ирограммы, решающей задачу Дирихле

для уравнения Пуассона 292

^ Источники дополнительной информации 323

Программа курса 325

Список задач 329

Указатель русских терминов 334

Указатель английских терминов 336

Список иллюстраций 339

Список таблиц 340

Список примеров 341

Предисловие

Параллельные ЭВМ, возникшие преимущественно для высоко­производительных научных вычислений, получают все более широкое распространение: их можно встретить в небольших научных подразделениях и офисах. Этому способствуют как непрерывное падение цен на них, так и постоянное усложнение решаемых задач. Можно без преувеличения сказать, что парал­лельные компьютеры сейчас используются или планируются к использованию всеми, кто работает на передовых рубежах на­уки и техники:

  • научными работниками, применяющими ЭВМ для решения реальных задач физики, химии, биологии, медицины и дру­гих наук, поскольку упрощенные модельные задачи уже рас­считаны на «обычных» ЭВМ, а переход к реальным задачам сопряжен с качественным ростом объема вычислений;

  • программистами, разрабатывающими системы управления базами данных (СУБД), разнообразные Internet-серверы за­просов (WWW, FTP, DNS и др.) и совместного использова­ния данных (NFS, SMB и др.)? автоматизированные систе­мы управления производством (АСУП) и технологическими процессами (АСУТП), поскольку требуется обеспечить об­служивание максимального количества запросов в единицу времени, а сложность самого запроса постоянно растет.

В настоящий момент практически все крупные разрабатыва­емые программные проекты как научной, так и коммерческой

8

Предисловие

направленности либо уже содержат поддержку параллельной работы на компьютерах разных типов, либо эта поддержка за­планирована на ближайшее время (причем промедление здесь часто вызывает поражение проекта в конкурентной борьбе).

Настоящая книга представляет собой введение в методы про­граммирования параллельных ЭВМ. Основной ее целью являет­ся научить читателя самостоятельно разрабатывать максималь­но эффективные программы для таких компьютеров. Вопросы распараллеливания конкретных алгоритмов рассматриваются на многочисленных примерах. В качестве языка программиро­вания использован язык С, как наиболее распространенный (и, заметим, единственный (не считая своего расширения C++), на котором можно реализовать все приведенные примеры). Про­граммы, посвященные использованию параллелизма процесса и MPI, могут быть легко переписаны на языке FORTRAN-77. Для иллюстрации подпрограмма умножения двух матриц, дающая почти 14-кратное ускорение на одном процессоре, приведена на двух языках: С и FORTRAN-77.

Изложение начинается с изучения параллелизма в работе процессора, оперативной памяти и методов его использования. Затем приводится описание архитектур параллельных ЭВМ и базовых понятий межпроцессного взаимодействия. Для систем с общей памятью подробно рассматриваются два метода програм­мирования: с использованием процессов и использованием задач (threads). Для систем с распределенной памятью рассматрива­ется ставший фактическим стандартом интерфейс MPI. Для указанных систем приведены описания основных функций и примеры их применения. В описаниях намеренно выброшены редко используемые детали, чтобы не пугать читателя большим объемом информации (чем страдают большинство руководств пользователя).

Книга используется в качестве учебного пособия в основном курсе «Практикум на ЭВМ» на механико-математическом фа­культете МГУ им. М.В.Ломоносова по инициативе и при под­держке академика РАН Н. С.Бахвалова.

^ Порядок чтения

9

Порядок чтения

Книгу можно разделить на 5 достаточно независимых частей:

  1. В главах 2, 3, 4 описан параллелизм в работе процессора и оперативной памяти, а также разнообразные приемы, ис­пользуемые для повышения эффективности их работы. Эту информацию можно использовать для достижения значи­тельного ускорения работы программы даже на однопро­цессорном компьютере.

  2. В главах 5 и б изложены основные понятия, используемые при рассмотрении параллельных программ, а также стан­дарты на операционные системы UNIX, установленные на подавляющем большинстве параллельных ЭВМ.

  3. В главах 7 и 8 описаны основные функции для управле­ния процессами и осуществления межпроцессного взаимо­действия. Эти функции можно использовать для запуска многих совместно работающих процессов в системах с общей памятью, а также для разработки параллельного приложе­ния для систем, не поддерживающих задачи (threads).

  4. В главах 9 и 10 описаны основные функции для управления задачами (threads) и осуществления межзадачного взаимо­действия. Эти функции можно использовать для разработки параллельного приложения в системах с общей памятью.

  5. В главе 11 описаны основные функции Message Passing Interface (MPI). Эти функции можно использовать для раз­работки параллельного приложения в системах как с общей, так и с распределенной памятью.

Части расположены в рекомендуемом порядке чтения. По­следние три независимы друг от друга и могут изучаться в про­извольной последовательности. Главу 1, адресованную нетерпе­ливому читателю, при систематическом изучении рекоменду­ется разбирать по мере ознакомления с материалом основных частей книги.

Книгой можно воспользоваться и в качестве учебника. Для этого в конце приведены программа курса и список типовых экзаменационных задач. Эти материалы будут полезны и для самостоятельной подготовки.

^ 1

Для нетерпеливого читателя

Для нетерпеливого читателя, желающего как можно быстрее научиться писать параллельные приложения, сразу же приве­дем пример превращения последовательной программы в парал-лельнз'ю. Для простоты рассмотрим задачу вычисления опреде­ленного интеграла от заданной функции и будем считать, что все входные параметры (концы отрезка интегрирования и ко­личество точек, в которых вычисляется функция) заданы кон­стантами. Все использованные функции будут описаны в после­дующих главах.

^ 1.1. Последовательная программа

Для вычисления приближения к определенному интегралу от функции / по отрезку [а, Ь] используем составную формулу тра­пеций:

/ /(*) dx « h(f(a)/2 + J2 /(« + 3h) + №/2),
{ J=i

где h= (b — a)/n, а параметр n задает точность вычислений.

Вначале — файл integral.с с текстом последовательной программы, вычисляющей определенный интеграл этим спосо­бом:

#include "integral.h"

1.1. Последовательная программа

11

/* Интегрируемая функция */

double f (double х)

{

return х; }

/* Вычислить интеграл по отрезку [а, Ь] с числом точек

разбиения п методом трапеций. */ double integrate (double a, double b, int n) {

double res; /* результат */

double h; /* шаг интегрирования */

int i;

h = (b - a) / n;

res = 0.5 * (f (a) + f (b)) * h;

for (i = 1; i < n; i++)

res += f (a + i * h) * h; return res; }

Соответствующий заголовочный файл integral.h:

double integrate (double a, double b, int n);

Файл sequential.с с текстом последовательной программы:

#include #include "integral.h"

/* Все параметры для простоты задаются константами */ static double а = 0.; /* левый конец интервала */ static double b = 1.; /* правый конец интервала */ static int n = 100000000; /* число точек разбиения */

int main () {

12

  1   2   3   4   5   6   7   8   9   ...   27

Добавить документ в свой блог или на сайт

Похожие:

Мгу им. М. В. Ломоносова. Для студентов, аспирантов, научных работников, программистов и всех, кто хочет научиться разрабатывать программы для парал­лельных ЭВМ iconМгу им. М. В. Ломоносова и Гуманитарном институте. Для студентов,...
Ш95 Основы нейрофизиологии: Учебное пособие для студентов вузов. М.: Аспект Пресс, 2000. с. 277

Мгу им. М. В. Ломоносова. Для студентов, аспирантов, научных работников, программистов и всех, кто хочет научиться разрабатывать программы для парал­лельных ЭВМ iconПеревод с английского Н. Г. Гуревич под редакцией канд физ мат наук...
Книга предназначена для научных работников, специализирующихся в области информатики и вычислительной техники, разработчиков автоматизированных...

Мгу им. М. В. Ломоносова. Для студентов, аспирантов, научных работников, программистов и всех, кто хочет научиться разрабатывать программы для парал­лельных ЭВМ iconУчебно-методическое пособие по написанию и оформлению научных работ...
Хгаэп в качестве учебно-методического пособия для студентов, магистрантов, аспирантов и соискателей учёных степеней

Мгу им. М. В. Ломоносова. Для студентов, аспирантов, научных работников, программистов и всех, кто хочет научиться разрабатывать программы для парал­лельных ЭВМ iconСправочников на cd «Металлические конструкции» (Справочник проектировщика)
Справочник предназначен для работников научных и проектных организаций, работников экспертных базовых центров, конструкторских бюро,...

Мгу им. М. В. Ломоносова. Для студентов, аспирантов, научных работников, программистов и всех, кто хочет научиться разрабатывать программы для парал­лельных ЭВМ iconДанное пособие предназначено для всех, кто хочет улучшить свои коммуникативные...
М. Е. Новичихина, доцент кафедры теории и практики коммуникации Воронежского института повышения квалификации и переподготовки работников...

Мгу им. М. В. Ломоносова. Для студентов, аспирантов, научных работников, программистов и всех, кто хочет научиться разрабатывать программы для парал­лельных ЭВМ iconРуководитель программы развития частного и малого предпринимательства канд экон наук
Справочник предназначен для работников экономических служб и руководителей предприятий, предпринимателей, научных работников в области...

Мгу им. М. В. Ломоносова. Для студентов, аспирантов, научных работников, программистов и всех, кто хочет научиться разрабатывать программы для парал­лельных ЭВМ iconПаралельне програмування
Разработана методика применения системы переписывания правил для преобразования конструкций координации вычислений в многопоточных...

Мгу им. М. В. Ломоносова. Для студентов, аспирантов, научных работников, программистов и всех, кто хочет научиться разрабатывать программы для парал­лельных ЭВМ iconNota bene
Книга предназначена для студентов, аспирантов, научных работников. В ней рассматриваются основные положения и понятия современной...

Мгу им. М. В. Ломоносова. Для студентов, аспирантов, научных работников, программистов и всех, кто хочет научиться разрабатывать программы для парал­лельных ЭВМ iconКонтрольные вопросы Рекомендуемая литература
Учебник предназначен для преподавателей, аспирантов и студентов факультетов психоанализа, психологии, философии, социо^ логин, педагогики,...

Мгу им. М. В. Ломоносова. Для студентов, аспирантов, научных работников, программистов и всех, кто хочет научиться разрабатывать программы для парал­лельных ЭВМ iconГлобальные теленовости: общая характеристика
Книга предназначена для студентов, аспирантов и преподавателей факультетов журналистики и всех, кто интересуется вопросами международного...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
uchebilka.ru
Главная страница


<