мых аппаратных контроллеров, позволявших центральному
Предисловие
Параллельное программирование возникло в 1962 г. с изобретением каналов — независи мых аппаратных контроллеров, позволявших центральному процессору выполнять новую прикладную программу одновременно с операциями ввода-вывода других (приостановленных) программ. Параллельное программирование (слово параллельное в данном случае означает "происходящее одновременно"') первоначально было уделом разработчиков операционных систем. В конце 60-х годов были созданы многопроцессорные машины. В результате не только были поставлены новые задачи разработчикам операционных систем, но и появились новые возможности у прикладных программистов.
Первой важной задачей параллельного программирования стало решение проблемы так называемой критической секции. Эта и сопутствующие ей задачи ("обедающих философов", "читателей и писателей" и т.д.) привели к появлению в 60-е годы огромного числа научных работ. Для решения данной проблемы и упрощения работы программиста были разработаны такие элементы синхронизации, как семафоры и мониторы. К середине 70-х годов стало ясно, что для преодоления сложности, присущей параллельным программам, необходимо использовать формальные методы.
На рубеже 70-х и 80-х годов появились компьютерные сети. Для глобальных сетей стандартом стал Arpanet, а для локальных— Ethernet. Сети привели к росту распределенного программирования, которое стало основной темой в 80-х и, особенно, в 90-х годах. Суть рас-пределенног9 программирования состоит во взаимодействии процессов путем передачи сообщений, а не записи и чтения разделяемых переменных.
Сейчас, на заре нового века, стала заметной необходимость обработки с массовым параллелизмом, при которой для решения одной задачи используются десятки, сотни и даже тысячи процессоров. Также видна потребность в технологии клиент-сервер, сети Internet и World Wide Web. Наконец, стали появляться многопроцессорные рабочие станции и ПК. Параллельное аппаратное обеспечение используется больше, чем когда-либо, а параллельное программирование становится необходимым.
Это моя третья книга, в которой предпринята попытка охватить часть истории параллельного программирования. Первая книга — Concurrent Programming: Principles and Practice, опубликованная в 1991 г., — дает достаточно полное описание периода между 1960 и 1990 годами. Основное внимание в ней уделяется новым задачам, механизмам программирования и формальным методам.
Вторая книга — The SR Programming Language: Concurrency in Practice, опубликованная в 1993 году, —-подводит итог моей работы с Роном Одеоном (Ron Olsson) в конце 80-х и начале 90-х годов над специальным языком программирования, который может использоваться при написании параллельных программ для систем как с разделяемой, так и с распределенной памятью. Книга о языке SR является скорее практическим руководством, чем формальным описанием языка, поскольку демонстрирует пути решения многих проблем с использованием одного языка программирования.
Данная книга выросла из предыдущих и является отражением моих мыслей о том, что важно сейчас и в будущем. Многое почерпнуто из книги Concurrent Programming, но полностью переработан каждый раздел, взятый из нее, и переписаны все примеры программ на псевдоС вместо языка SR. Все разделы дополнены новым материалом; особенно это каса-
1 Слово "параллельный" в большинстве случаев является переводом английского "concurrent". Применительно к программам, вычислениям и программированию его смысл, возможно, лучше передавался бы словом "многопроцессный", но этого термина в русскоязычной литературе нет. Перевод английского "parallel" связан с синхронным параллелизмом, и его смысл определяется в разделах 1.3 и 3.5 и уточняется в самом начале части 3. Отметим, что смысл слова "concurrent" шире, чем "parallel". — Прим. ред.
14 Предисловие
ется параллельного научного программирования.
Также добавлены учебные примеры по наиболее важным языкам программирования и библиотекам программ, содержащие завершенные учебные программы. И, наконец, я по-новому вижу использование этой книги — в аудиториях и личных библиотеках.
Новое видение и новая роль
Идеи параллельных и распределенных вычислений сегодня распространены повсеместно. Как обычно в вычислительной технике, прогресс исходит от разработчиков аппаратного обеспечения, которые создают все более быстрые, большие и мощные компьютеры и коммуникационные сети. Большей частью, они достигают успеха, и лучшее доказательство тому — фондовая биржа!
Новые компьютеры и сети создают новые проблемы и возможности, а разработчики программного обеспечения по-прежнему не отстают. Вспомните Web-броузеры, Internet-коммерцию, потоки Pthread, язык Java, MPI, и вновь доказательством служит фондовая биржа! Эти программные продукты разрабатываются специально для того, чтобы использовать все преимущества параллельности в аппаратной и программной части. Короче говоря, большая часть мира вычислительной техники сейчас параллельна!
Аспекты параллельных вычислений — многопоточных, параллельных или распределенных — теперь рассматриваются почти в каждом углубленном курсе по вычислительной технике. Отражая историю, курсы по операционным системам охватывают такие темы, как многопоточность, протоколы взаимодействия и распределенные файловые системы. Курсы по архитектуре вычислительной техники — многопроцессорность и сети, по компиляторам — вопросы компиляции для параллельных машин, а теоретические курсы — модели параллельной обработки данных. В курсах по алгоритмам изучаются параллельные алгоритмы, а по базам данных — блокировка и распределенные базы данных. В курсах по графике используется параллелизм при визуализации и трассировке лучей Этот список можно продолжить. Кроме того, параллельные вычисления стали фундаментальным инструментом в широкой области научных и инженерных дисциплин.
Главная цель книги, как видно из ее названия, — заложить основу для программирования многопоточных, параллельных и распределенных вычислений. Частная цель — создать текст, который можно использовать в углубленном курсе для студентов и магистров. Когда некоторая тема становится распространенной, как это произошло с параллелизмом, вводятся учебные курсы по ее основам. Аналогично, когда тема становится хорошо изученной, как сейчас параллелизм, она переносится в нормативный курс.
Я пытался охватить те вопросы параллельной и распределенной обработки данных, которые, по моему мнению, должен знать любой студент, изучающий вычислительную технику. Сюда включены основные принципы, методы программирования, наиболее важные приложения, реализации и вопросы производительности. Я добавил также материал по важнейшим языкам программирования и библиотекам программ — потоки Pthread (три главы), язык Java (три главы), CSP, Linda, MPI (две главы), языки Ада, SR и ОрепМР. В каждом примере сначала описаны соответствующие части языка программирования или библиотеки, а затем представлена полная программа. Исходные тексты программ доступны на Web-сайте этой книги. Кроме того, в главе 12 приведен обзор нескольких дополнительных языков, моделей и инструментов для научных расчетов.
С другой стороны, ни в одной книге нельзя охватить все, поэтому, возможно, студенты и преподаватели захотят дополнить данный текст. Исторические справки и списки литературы в конце каждой главы описывают дополнительные материалы и содержат указания для дальнейшего изучения. Информация для дальнейшего изучения и ссылки на соответствующие материалы представлены на Web-сайте этой книги.
Предисловие 15
Обзор содержания
Эта книга состоит из 12 глав. В главе 1 дается обзор основных идей параллелизма, аппаратной части и приложений. Затем рассматриваются пять типичных приложений: умножение матриц, адаптивная квадратура, каналы ОС Unix, файловые системы и распределенное умножение матриц.
Каждое приложение просто, но, тем не менее, полезно: вместе они иллюстрируют некоторый диапазон задач и пять стилей программирования многократных вычислений. В последнем разделе главы 1 резюмируется программная нотация, использованная в книге.
Оставшиеся главы разделены на три части. Часть 1 описывает механизмы параллельного программирования, которые используют разделяемые переменные и поэтому непосредственно применяются к машинам с разделяемой памятью. В главе 2 представлены базовые понятия процессов и синхронизации; основные моменты иллюстрируются рядом примеров. Заканчивается глава обсуждением формальной семантики параллелизма. Понимание семантических концепций поможет вам разобраться в некоторых разделах последующих глав. В главе 3 показано, как реализовать и использовать блокировки и барьеры, описаны алгоритмы, параллельные по данным, и метод параллельного программирования, называемый "портфель задач". В главе 4 представлены семафоры и многочисленные примеры их использования. Семафор был первым механизмом параллельного программирования высокого уровня и остается одним из важнейших. В главе 5 подробно описаны мониторы. Они появились в 1974г.; в 80-е и в начале 90-х годов внимание к ним несколько угасло, но появление языка Java возобновило интерес к ним. Наконец, в главе 6 представлена реализация процессов, семафоров и мониторов на одно- и многопроцессорных машинах.
Часть 2 посвящена распределенному программированию, в котором процессы взаимодействуют и синхронизируются, используя сообщения. В главе 7 описана передача сообщений с помощью элементарных операций send и receive. Демонстрируется, как использовать эти операции для программирования фильтров (программ с односторонней связью), клиентов и серверов (с двусторонней связью), а также взаимодействующих равных (с передачей в обоих направлениях). В главе 8 рассматриваются два дополнительных примитива взаимодействия: удаленный вызов процедуры (RPC) и рандеву.
Процесс- клиент инициирует связь, посылая сообщение call (неявно оно является последовательностью сообщений send и receive). Взаимодействие обслуживается или новым процессом (RPC), или с помощью рандеву с существующим процессом. В главе 9 описано несколько моделей взаимодействия процессов в распределенных программах. Три из них обычно используются в параллельных вычислениях— "управляющий-рабочие", алгоритм пульсации и конвейер. Еще четыре возникли в распределенных системах — зонд-эхо, оповещение (рассылка), передача маркера и дублируемые серверы. Наконец, в главе 10 описана реализация передачи сообщений, RPC и рандеву. Показано, как реализовать так называемую распределенную разделяемую память, которая поддерживает модель программирования с разделяемой памятью в распределенной среде.
Часть 3 посвящена синхронному параллельному программированию, особенно его применению к высокопроизводительным научным вычислениям. (Многие другие типы синхронных параллельных вычислений рассмотрены в предыдущих главах и в упражнениях к нескольким из них.) Цель параллельной программы — ускорение, т.е. более быстрое решение задачи с помощью большого числа процессоров. Синхронные параллельные программы пишутся с использованием разделяемых переменных или передачи сообщений, следовательно, в них применяется методика, описанная в частях 1 и 2. В главе 11 рассматриваются три основных класса приложений для научных вычислений: сеточные, точечные и матричные. Они возникают при моделировании физических и биологических систем; матричные вычисления используются и для таких задач, как экономическое прогнозирование. В главе 12 дан обзор наиболее важных инструментов для написания научных параллельных вычислительных программ: библиотеки (Pthread, MPI, OpenMP), распараллеливающие компиляторы, языки и модели, а также такие инструменты более высокого уровня, как метавычисления.
16 Предисловие
В конце каждой главы размещены историческая справка, ссылки на литературу и упражнения. В исторической справке резюмируются происхождение, развитие и связи каждой темы с другими темами, а также описываются статьи и книги из списка литературы. В упражнениях представлены вопросы, поднятые в главе, и дополнительные приложения.
Использование в учебном процессе
Я использую эту книгу каждой весной в университете штата Аризона, читая курс примерно для 60 студентов. Около половины из них — магистры; остальные — студенты старших курсов. В основном это студенты специальности "computer science". Данный курс для них не обязателен, но большинство студентов его изучают. Также каждый год курс проходят несколько аспирантов других отделений, интересующихся вычислительной техникой и параллельными вычислениями. Большинство студентов одновременно проходят и наш курс по операционным системам.
В наших курсах по ОС, как и везде, рассматриваются потребности ОС в синхронизации и изучается реализация синхронизации, процессов и других элементов ОС, в основном, на однопроцессорных машинах. Мой курс демонстрирует, как использовать параллельность в качестве общего инструмента программирования для широкого диапазона приложений. Я рассматриваю методы программирования, концепции высокого уровня, параллельную и распределенную обработку данных. По существу, мой курс относится к курсу по ОС примерно так же, как сравнительный курс языков программирования относится к курсу по компиляторам.
В первой половине моего курса я подробно излагаю главу 2, а затем быстро прохожу по остальным главам первой части, акцентируя внимание на темах, не рассматриваемых в курсе по ОС, — протокол "проверить-проверить-установить" (Test-and-Test-and-Set), алгоритм билета, барьеры, передача эстафеты для семафоров, некоторые способы программирования мониторов и многопроцессорное ядро. В дополнение к этому студенты самостоятельно изучают библиотеку Pthread, потоки языка Java и синхронизированные методы.
После лекций по барьерам они выполняют проект по синхронным параллельным вычислениям (на основе материала главы 11).
Во второй половине курса я использую многое из материала части 2 книги, касающегося распределенного программирования. Мы рассматриваем передачу сообщений и ее использование в программировании как распределенных систем, так и распределенных параллельных вычислений. Затем мы изучаем RPC и рандеву, их воплощение в языках Java и Ada и приложения в распределенных системах. Наконец, мы рассматриваем каждую парадигму из главы 9, вновь используя для иллюстрации и мотивировки приложения из области синхронных параллельных и распределенных систем. Самостоятельно студенты изучают библиотеку MPI и снова используют язык Java.
В течение семестра я даю четыре домашних задания, два аудиторных экзамена, проект по параллельным вычислениям и заключительный проект. (Примеры представлены на Web-сайте книги.) Каждое домашнее задание состоит из письменных упражнений и одной или двух задач по программированию. Магистры должны выполнить все упражнения, другие студенты — две трети задач (по своему выбору). Экзамены проводятся аналогично: магистры решают все задачи, а остальные выбирают вопросы, на которые хотят отвечать. В Аризонском университете начальные задачи по программированию мы решаем с помощью языка SR, который студенты могут использовать и в дальнейшем, но поощряется использование таких языков и библиотек, как Pthreads, Java и MPI.
Проект по синхронному параллельному программированию связан с задачами из главы 11 (обычно это сеточные вычисления). Студенты пишут программы и экспериментируют на небольшом мультипроцессоре с разделяемой памятью. Магистры реализуют более сложные алгоритмы и обязаны написать подробный отчет о своих опытах. Заключительный проект — это статья или программный проект по какому-либо вопросу распределенного программирования. Студенты выбирают тему, которую я утверждаю. Большинство студентов выполняют
Предисловие 17
проекты по реализации, многие из них работают парами. Студенты создают разнообразные интересные системы, в основном, с графическим интерфейсом.
Несмотря на то что студенты, изучающие мой курс, имеют различную подготовку, почти все оценивают его отлично. Студенты часто отмечают, насколько хорошо курс согласуется с их курсом по ОС; им нравится взгляд на параллельность с другой точки зрения, изучение многопроцессорных систем, им интересно рассматривать широкий спектр приложений и инструментов. Магистры отмечают, что курс связывает воедино разные вещи, о которых они уже что-то слышали, и вводит их в область параллельного программирования. Однако многим из них было бы интересно изучить параллельные вычисления более подробно Со временем мы надеемся сделать отдельные курсы для магистров и студентов. Я не буду значительно изменять курс для студентов, но в нем будет меньше углубленных тем. В курсе для магистров я буду тратить меньше времени на материал, с которым они уже знакомы (часть 1), и больше времени посвящать синхронным параллельным приложениям и инструментарию синхронных вычислений (часть 3).
Эта книга идеально подходит для курса, который охватывает область механизмов параллельного программирования, средств и приложений. Почти все студенты смогут использовать что-то из рассмотренного здесь, но не все будут заниматься только параллельной обработкой данных, только распределенными системами или программировать только на языке Java. Тем не менее книгу можно использовать и как пособие в более специализированных курсах, например, в курсе синхронных параллельных вычислений, вместе с книгами по параллельным алгоритмам и приложениям.
Информация в Internet
"Домашняя страничка" этой книги находится по адресу:
http://www.cs.arizona.edu/people/greg/mpdbook
На этом сайте есть исходные тексты программ из книги, ссылки на программное обеспечение и информацию о языках программирования и библиотеках, описанных в примерах; большое число других полезных ссылок.
Также сайт содержит обширную информацию о моем курсе в Аризонском университете, включая программу курса, конспекты лекций, копии домашних заданий, проектов и экзаменационных вопросов. Информация об этой книге также доступна по адресу:
http://www.awlonline.com/cs
Несмотря на мои усилия, книга, без сомнения, содержит ошибки, так что по этому адресу появится (уверен, что скоро) их список. Безусловно, в будущем добавятся и другие материалы.
Благодарности
Я получил множество полезных замечаний от читателей чернового варианта этой книги. Марте Тиенари (Martti Tienary) и его студенты из университета Хельсинки обнаружили несколько неочевидных ошибок. Мои последние аспиранты, Вине Фрих (Vince Freeh) и Дейв Ловентал (Dave Lowenthal), прокомментировали новые главы и за последние несколько лет помогли отладить если не мои программы, то мои мысли. Студенты, изучавшие мой курс весной 1999 г., служили "подопытными кроликами" и нашли несколько досадных ошибок. Энди Бернат (Andy Bernat) предоставил отзыв о своем курсе в университете в Эль-Пасо, Техас, который он провел весной 1999 г. Благодарю следующих рецензентов за их бесценные отзывы: Джаспал Субхлок (Jaspal Subhlok) из университета Carnegy Mellon, Болеслав Жимански (Boleslaw Szymansky) из политехнического института Rensselaer, Дж. С. Стайлс (G. S. Stiles) из Utah State University, Нарсингх Део (Narsingh Deo) из Central Florida University, Джанет Харт-ман (Janet Hartman) из Illinois State University, Нэн Шаллер (Nan С. Schaller) из Технологического института Рочестера и Марк Файнап (Mark Fineup) из университета Северной Айовы.
В течение многих лет организация National Science Foundation поддерживает мои исследования, в основном по грантам CCR-9415303 и ACR-9720738. Грант от NSF (CDA-9500991) помог обеспечить оборудование для подготовки книги и проверки программ.
И главное — я хочу поблагодарить мою жену Мэри, еще раз смирившуюся с долгими часами, которые я провел, работая над этой книгой (несмотря на клятвы вроде "больше никогда" после завершения книги о языке SR).
