Историческая справка
Как уже отмечалось, параллельное программирование возникло в 1960-х годах после появления независимых аппаратных контроллеров (каналов). Операционные системы были первыми программными системами, организованными как многопоточные параллельные программы. Исследование и первоначальные прототипы привели на рубеже 1960-х и 1970-х годов к современным операционным системам. Первые книги по операционным системам появились в начале 1970-х годов.
Создание компьютерных сетей привело в 1970-х годах к разработке распределенных систем. Изобретение в конце 1970-х сети Ethernet существенно ускорило темпы развития. Почти сразу появилось изобилие новых языков, алгоритмов и приложений; их создание стимулировалось развитием аппаратного обеспечения. Например, как только рабочие станции и локальные сети стали относительно дешевыми, была разработана модель вычислений типа клиент-сервер; развитие сети Internet привело к рождению языка Java, Web-броузеров и множества новых приложений.
Первые мультипроцессоры появились в 1970-х годах, и наиболее заметными из них были SIMD-мультипроцессоры Illiac, разработанные в университете Иллинойса. Первые машины были дорогими и специализированными, однако в течение многих лет трудоемкие научные вычисления выполнялись на векторных процессорах. Изменения начались в середине 1980-х годов с изобретения гиперкубовых машин в Калифорнийском технологическом институте и их коммерческой реализации фирмой Intel. Затем фирма Thinking Machines представила Connection Machine с массовым параллелизмом. Кроме того, фирма Cray Research и другие производители векторных процессоров начали производство многопроцессорных версий своих машин. В течение нескольких лет появлялись и вскоре исчезали многочисленные компании и машины. Однако сейчас группа производителей машин достаточна стабильна, а высокопроизводительные вычисления стали почти синонимом обработки с массовым параллелизмом.
В исторических справках следующих глав описываются разработки, связанные с самими этими главами.
Одной из первых и наиболее влиятельных статей по параллельному программированию была статья Эдсгера Дейкстры [Dijkstra, 1965]. В ней представлены задача критической секции и оператор parbegin, который позже стал называться оператором cobegin. Наш оператор со является обобщением cobegin. В другой работе Дейкстры [Dijkstra, 1968] были представлены задачи о производителе и потребителе, об обедающих философах и некоторые другие, которые рассматриваются в следующих главах.
Арт Бернстайн [Bernstein, 1966] был первым, кто определил условия, достаточные для независимости, и, значит, возможности параллельного выполнения двух процессов. Условия Бернстайна, как они и сейчас называются, выражены в терминах множеств ввода и вывода для каждого процесса; множество ввода содержит переменные, читаемые процессом, а множество вывода — переменные, записываемые процессом. Три условия Бернстайна для независимости двух процессов состоят в том, что пересечения множеств (вход, выход), (выход, вход) и (выход, выход) не пересекаются между собой. Условия Бернстайна также дают основу для анализа зависимости данных, выполняемого распараллеливающими компиляторами (эта тема описана в главе 12), В нашем определении независимости (2.1) использованы множества чтения и записи для каждого процесса, и переменная находится только в одном из этих множеств для каждого процесса. Это приводит к более простому, но эквивалентному условию.
В большинстве книг по операционным системам показано, как реализация оператора присваивания с использованием регистров и мелкомодульных неделимых действий приводит к задаче критических секций в параллельных программах. Современное аппаратное обеспечение гарантирует, что существует некоторый базовый уровень неделимости (обычно слово) для чтения и записи памяти. Статья Лампорта [Lamport, 1977b] содержит интересное обсуждение того, как реализовать неделимые чтение и запись "слов", если неделимым образом могут записываться и читаться только отдельные байты.
Впервые задача критической секции была описана Дейкстрой [Dijkstra, 1965]. Эту фундаментальную задачу изучали десятки людей, опубликовавших буквально сотни работ по данной теме. В данной главе были представлены четыре наиболее важных решения. (Рейнал [Raynal, 1986] написал целую книгу по алгоритмам взаимного исключения.) Хотя разработка решений с активным ожиданием вначале была чисто академическим упражнением (поскольку активное ожидание неэффективно в однопроцессорной системе), появление мультипроцессоров подстегнуло новую волну интереса к этой теме. В действительности все современные мультипроцессоры имеют команды, поддерживающие как минимум одно решение с активным ожиданием. Большинство этих команд описаны в упражнениях в конце главы.
В работе Дейкстры [1965] было представлено первое программное решение для п процессов. Это было расширение решения для двух процессов, разработанного голландским математиком Т. Деккером (см. упражнения). Однако в исходной формулировке Дейкстры не требовалось свойство возможности входа (3.5). Дональд Кнут [Knuth, 1966] стал первым, кто опубликовал решение, гарантирующее возможность входа.
Алгоритм разрыва узла был изобретен Г. Питерсоном [Peterson, 1981]; теперь его часто называют алгоритмом Питерсона. В отличие от ранних решений Дейкстры, Деккера и других авторов, этот алгоритм очень прост для двух процессов. Алгоритм Питерсона также легко обобщается для n-процессного решения (см. листинг 3.7). Это решение требует, чтобы процесс прошел через все п-1 уровней, даже если ни один другой процесс не делает попыток войти в критическую секцию. Блок и By [Block and Woo, 1990] представили вариант этого алгоритма, в котором необходимо только m уровней, если m процессов пытаются войти в критическую секцию (см. упражнения).
Алгоритм поликлиники был изобретен Лампортом [Lamport, 1974]. (В листинге 3.11 представлена его улучшенная версия из работы [Lamport, 1979].) Кроме того, что этот алгоритм нагляднее, чем предыдущие решения задачи критической секции, он позволяет процессам входить, по существу, в порядке FIFO (first in — first out, первым вошел — первым вышел).
В середине 1960-х годов Эдсгер Дейкстра (Edsger Dijkstra) и пять его коллег из Технического университета Эйндховена (Нидерланды) разработали одну из первых мультипрограммных операционных систем. (Разработчики назвали ее просто мультипрограммной системой "THE" — по первым буквам названия института на голландском языке.) Эта система имеет элегантную структуру, состоящую из ядра и уровней виртуальных машин, реализованных процессами [Dijkstra, 1968a]. В ней были представлены семафоры, которые Дейкстра изобрел как полезное средство реализации взаимного исключения и выработки сигналов о таких событиях, как прерывания. Дейкстра также ввел термин частный семафор.
Поскольку Дейкстра голландец, названия операций р и V происходят от голландских слов. Р — это первая буква голландского слова passeren (пропустить), а V — первая буква слова \rijgeven (освободить). (Отметим аналогию с железнодорожными семафорами.) Дейкстра и его группа позже решили связать букву Р со словом prolagen, составленного из нидерландских сяовргоЬегеп (попытаться) и verlagen (уменьшить), а букву V — со словом verhogen (увеличить).
Примерно в это же время Дейкстра написал важную работу [Dijkstra, 1968b] по взаимодействию последовательных процессов. В этой работе было показано, как использовать семафоры для решения различных задач синхронизации, и представлены задачи об обедающих философах и о спящем парикмахере (см. раздел 5.2).
В своей основополагающей работе по мониторам (обсуждаемым в главе 5) Тони Хоар [Ноаге, 1974] представил идею разделенного двоичного семафора и показал, как его использовать для реализации мониторов. Однако именно Дейкстра позже дал этому методу название и доказал его практичность. Дейкстра [Dijkstra, 1979] описал использование разделенных двоичных семафоров для решения задачи о читателях и писателях. Он также показал, как реализовать обычные семафоры, используя только разделенные двоичные семафоры [Dijkstra, 1980].
Автор этой книги, вдохновленный работами Дейкстры о разделенных двоичных семафорах, разработал метод передачи эстафеты [Andrews, 1989].
Понятие инкапсуляции данных происходит от конструкции class языка Simula-67. Эдс-гер Дейкстра [Dijkstra, 1971] считается первым, кто начал использовать инкапсуляцию данных для управления доступом к разделяемым переменным в параллельной программе. Он на-
Глава 5. Мониторы 203
звал такой модуль "секретарем", но не предложил синтаксического механизма для программирования секретарей. Бринч Хансен [Brinch Hansen, 1972] выступил с той же идеей, а в своей работе [Brinch Hansen, 1973] предложил особую языковую конструкцию shared class.
Хоар в своей замечательной статье [Ноаге, 1974] дал название мониторам и популяризировал их с помощью интересных примеров, включавших кольцевой буфер, интервальный таймер и диспетчер доступа к диску (с использованием алгоритма лифта). Условная синхронизация в варианте Хоара поддерживала порядок сигнализации "сигнализировать и срочно ожидать". Полезно сравнить решения Хоара с решениями из этой главы, в которых использован порядок SC. Хоар также представил понятие разделенного двоичного семафора и показал, как его использовать для реализации мониторов.
Язык Concurrent Pascal [Brinch Hansen, 1975] стал первым языком параллельного программирования, в который были включены мониторы. В нем есть три структурных компонента: процессы, мониторы и классы. Классы похожи на мониторы, но не могут совместно использоваться процессами и, следовательно, не нуждаются в условной синхронизации или взаимном исключении. Язык Concurrent Pascal был использован для написания нескольких операционных систем [Brinch Hansen, 1977]. Устройства ввода-вывода в нем рассматриваются как особые мониторы, реализованные с помощью системы времени выполнения (run-time system) этого языка, скрывавшей понятие прерывания.
Мониторы были включены еще в несколько языков программирования. Язык Modula был разработан создателем языка Pascal Никлаусом Виртом (Nicklaus Wirth) как системный язык для задач программирования, связанных с компьютерными системами, включая приложения для управления процессами [Wirth, 1977]. (Первый вариант языка Modula весьма отличается от своих преемников, Modula-2 и Modula-З.) В Xerox PARC был разработан язык Mesa [Mitchell et al., 1979].
Примитивы fork, join и quit впервые были представлены Деннисом и Ван Хорном [Dennis and Van Horn, 1966]. Различные варианты этих примитивов есть в большинстве операционных систем. Например, в операционной системе UNIX [Ritchie and Thompson, 1974] обеспечены соответствующие системные вызовы fork, wait и exit. Похожие примитивы были включены в такие языки программирования, как PL/I, Mesa и Modula-3.
Реализация однопроцессорного ядра особенно хорошо описана в книгах [Bic and Shaw, 1988] и [Holt, 1983]. В них рассмотрены и другие функции, которые должна обеспечивать операционная система (файловая система и управление памятью), и их взаимосвязь с ядром. В [Thompson, 1978] описана реализация ядра системы UNIX, а в [Holt, 1983] -UNIX-совместимая система Tunis.
К сожалению, в работах по операционным системам недостаточно подробно рассмотрена тема многопроцессорного ядра. Однако прекрасный отчет о ранних мультипроцессорах, разработанных в университете Карнеги-Меллон (Carnegie-Mellon University), представлен в обзорной статье [Jones and Schwartz, 1980]. Из этой же работы взят принцип блокировки мультипроцессора (6.1). Несколько многопроцессорных операционных систем описаны в работах [Hwang, 1993] и [Almasi and Gottlieb, 1994]. В [Tucker and Gupta, 1989] рассмотрены вопросы управления процессами и планирования для мультипроцессоров с разделяемой памятью и равномерным распределением времени доступа к памяти, в [Scott et al., 1990] — вопросы ядра для мультипроцессоров с неравномерным временем доступа к памяти, включая использование нескольких списков готовых к работе процессов.
Хорошими источниками информации по последним работам в области языков программирования и программного обеспечения, связанной с мультипроцессорами, являются доклады следующих трех конференций: "Архитектурная поддержка языков программирования и операционных систем" (Architectural Support for Programming Languages and Operating Systems, ASPLOS), "Симпозиум по принципам операционных систем" (Symposium on Operating Systems Principles— SOSP) и "Принципы и практика параллельного программирования" (Principles and Practice of Parallel Programming — PPoPP).
Все парадигмы, описанные в этой главе, были разработаны между серединой 1970-х годов и серединой 1980-х. В течение этих десяти лет интенсивно исследовались многие модели, а затем больше внимания стало уделяться их применению. Многие задачи можно решить несколькими способами, используя разные парадигмы. Некоторые из них описаны ниже; дополнительные примеры приводятся в упражнениях и в главе 11.
Парадигма "управляющий-рабочие" была представлена в статье [Gentleman, 1981] и названа парадигмой "администратор-рабочий". В других работах (fCarriero et al., 1986], [Carriero and Gelernter, 1989]) эта же идея называлась распределенным портфелем задач. В них были представлены решения нескольких задач, запрограммированные с помощью примитивов Linda (см. раздел 7.7). В статье [Finkel and Manber, 1987] использовался распределенный портфель задач для реализации алгоритмов с возвратом (backtracking). Модель "управляющий-рабочие" широко используется в параллельных вычислениях, где эту технику иногда называют рабочим пулом, процессорной или рабочей фермой. Независимо от названия идея всегда одна и та же: несколько рабочих процессов динамически делят набор задач.
Алгоритмы пульсации широко используются в распределенных параллельных вычислениях, а особенно часто — в сеточных вычислениях (см. раздел 11.1). Автор этой книги ввел гермин алгоритм пульсации в конце 1980-х; это словосочетание показалось ему точно характеризующим действия процессов: закачка (передача), сокращение (прием), подготовка к следующему циклу (вычисления) и повторение этого цикла. Бринч Хансен [Bnnch Hansen, 1995] назвал это парадигмой клеточных автоматов, хотя этот термин больше подходит для описания гипа приложения, а не стиля программирования. В любом случае ставший каноническим стиль программирования "передать-принять-вычислить" многие никак не называют, а просто говорят, что процессы обмениваются информацией.
В разделе 9.2 были представлены алгоритмы пульсации для задачи выделения областей в изображении и для игры "Жизнь", которую придумал математик Джон Конвей (John Conway)
История научных вычислений тесно связана с общей историей вычислений. Первые вычислительные машины разрабатывались для решения научных проблем, а Фортран — первый язык высокого уровня — был создан специально для программирования численных методов. Научные вычисления также стали синонимом высокопроизводительных вычислений, заставляя увеличивать предельные возможности самых быстрых машин.
Математические основы научных вычислений представлены в учебниках по численному анализу, а методы решения дифференциальных и матричных уравнений — по вычислительной математике. Книга [Forsythe and Moler, 1967] является классической; в ней содержатся очень ясные описания линейных алгебраических систем и алгоритмов их решения. Она послужила основным источником для материала раздела 11.2. Книга [Van Loan, 1997] представляет собой введение в (непараллельные) научные вычисления, включая линейные и нелинейные системы уравнений. В учебнике [Mathews and Fink, 1999] описываются численные методы для целого ряда приложений, включая интегрирование, системы уравнений и дифференциальные уравнения. В последних двух книгах для иллюстрации алгоритмов используется пакет MATLAB.
Некоторые книги по параллельным вычислениям дают более подробные описания методов данной главы, представляют родственные алгоритмы и дополнительные темы. В книге [Fox et al., 1998] рассматриваются методы конечных разностей и конечных элементов для решения дифференциальных уравнений в частных производных, матричных и точечных вычислений, а также методы Монте-Карло (рандомизированные). Особое внимание уделяется алгоритмам с передачей сообщений, которые предназначены для работы на гиперкубах, но могут быть адаптированы к другим архитектурам с распределенной памятью. В книге [Bertsekas and Tsitsiklis, 1989] рассматриваются прямые и итерационные методы для ряда линейных и нелинейных задач, динамическое программирование, проблемы потоков в сетях и асин-
444 Часть 3.
Библиотеки параллельного программирования долгое время разрабатывались производителями параллельных машин. Однако, за редкими исключениями, все эти библиотеки были несовместимыми. В 1990-х годах стали появляться стандартные библиотеки, облегчавшие разработку переносимых кодов. Библиотека Pthreads рассматривалась в главе 4; там же в справке есть ссылки на другие источники информации о ней. Библиотека MPI была представлена в главе 7; реализации MPI и ее "близкой родственницы" библиотеки PVM описаны в исторической справке главы 7. Информацию по ОрепМР, включая онлайновые обучающие программы, можно найти в Internet по адресу: www. openmp. org.
Основополагающая работа по анализу зависимости была проведена под руководством Д. Кука (David Kuck) сотрудниками Иллинойского университета У. Банерджи (Utpal Banerjee) и М. Вольфом (Michael Wolfe) и представлена в книге [Wolfe, 1989]. В работе [Bacon, Graham, Sharp, 1994] дан прекрасный обзор анализа зависимости и преобразований компилятора для быстродействующих вычислений; работа содержит множество ссылок. В статье [McKinley, Carr, Tseng, 1996] описаны эксперименты, использующие различные преобразования для улучшения распределения данных, и даются рекомендации по очередности выполнения оптимизаций.
Некоторые из языков, перечисленных на рис. 12.3, были объектами учебных примеров в предыдущих главах: Ada в главе 8, Java в главах 5, 7 и 8, SR в главе 8, CSP/Occam и Linda в главе 7. Другие источники информации по этим языкам указаны в исторических справках соответствующих глав.
Из объектно-ориентированных языков на рис. 12.3 указаны только Java и Огса. Для параллельного программирования разработано также много других объектно-ориентированных языков. Например, в книге [Wilson and Lu, 1996] представлено более дюжины языков и систем, основанных на C++. Отличное описание одного из этих языков — Compositional C++, а также Фортрана М, HPF и библиотеки MPI содержится в [Foster, 1995]. Обзор языков программирования для распределенных вычислений, включая объектно-ориентированные и функциональные языки, можно найти в статье [Bal, Steiner, Tanenbaum, 1989].
