О параллелизме с разных сторон

41УДК 519.6О ПАРАЛЛЕЛИЗМЕ С РАЗНЫХ СТОРОНВ.П. КутеповМосковский Энергетический Институт (Технический Университет)Россия, 111250, Москва, Е-250, Красноказарменная улица, дом 14E-mail: kutepov@appmat.ruРассматриваются наиболее важные особенности параллелизма,которые существенны для построения языков параллельногопрограммирования и для разработки параллельных программ.Предлагается обзор языков и сред параллельного программирования.Изложены подходы к созданию методов и программных средств,предназначенных для эффективного управления процессамивыполнения параллельных программ на компьютерной системе.PARALLELISM THROUGH DIFFERENT PERSPECTIVES / V.P.Kutepov (Moscow Power Engineering Institute (Technical University), st.Krasnokazarmennaya 14, Moscow, 111250, Russia). Significant features ofparallelism that important for parallel programming languages compositionand parallel programs development are considered.

The review of parallelprogramming languages and development environments is suggested. Theapproach for development of techniques and software tools that are used forefficient control of execution of parallel programs at computers is described.ПЛЕНАРНЫЕ ДОКЛАДЫ ПЯТОЙ МЕЖДУНАРОДНОЙ КОНФЕРЕНЦИИ«ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ И ЗАДАЧИ УПРАВЛЕНИЯ», МОСКВАPACO ‘2010PLENARY PAPERS OF THE FIFTH INTERNATIONAL CONFERENCE“PARALLEL COMPUTING AND CONTROL PROBLEMS”, MOSCOW42Введение.История развития компьютерной индустрии, старту которой мы обязаны фон Нейману,сегодня вполне может быть удовлетворена своими достижениями.

На смену первымкомпьютерам, занимающим неколько комнат, с быстрнодействием в несколько тысячопераций в секунду, пришли книжного размера компьютеры с быстродействием в несколькомиллиардов операций в секунду и компьютерные системы, насчитывающие несколько сотентысяч компьютерных элементов. Они способны решать сложные научно-технические задачи,требующие быстродействия 1015 ÷ 1017 операций в секунду.Напомним, что в 60-е годы послеизобретения Л.В.

Канторовичем методов линейного программирования экономистыпытались решить задачу оптимизации перевозок в рамках страны с помощью компьютеров.Математическая модель этой задачи, описанная системой линейных уравнений, содержала106 переменных и 104 ограничений и не могла быть решена в приемлемое время накомпьютерах того времени. Да и сегодня потребуется большое искусство программированияи большая компьютерная система (КС), чтобы достичь желаемого времени решения этойзадачи, используя параллелизм.Конечно, сегодня нет особых проблем увеличить масштаб компьютеной системы,тиражируя стандартные многопроцессорные или многокомпьютерные узлы, используярасширямые коммуникации. Однако, обычно заявленная пиковая производительность такихсистем будет, как правило, весьма далека от реальной при решении конкретной сложнойзадачи.

При недостатке оперативной памяти придется обращаться к дискам, а это уже 1,5мсек из-за латентности для каждого обращения; при частых обменах данными между узламикомпьютерной системы узким «горлом», заметно удаляющим нас от пиковойпроизводительности, станут каналы и инфраструктура коммуникаций [1].Поэтому так не проста работа программиста по выбору метода решения задачи,разработке и оптимизацции параллельной программы и организации ее выполнения наконкретной КС.Не будем здесь говорить о том, какие нас ожидают трудности, если мы будем пытатьсяоптимизировать наши программы для выполнения на GRID системах и т.п.Сегодня достаточно хорошо исследована традиционная поледовательность решения накомпьютерах задач вычислительной математики, включающая этапы: выбор метода и языка,разработка и оптимизация программы, выполнение. При этом у программиста естьвозможность использования подходящего языка последовательного программирования(FORTRAN, PASKAL, C, C++ и др.), если довериться ОС в том, что ресурсы во времявыполнения его программы будут эффективно использованы.У КС пока эти возможности сильно ограничены, и программисту самому приходитсяискать ответы на принципиально новые и более сложные вопросы: как определитьо масштабКС, обеспечивающий достижение требуемого времени выполнения программыы, как найтинаилучший метод решения задачи, каким языком необходимо воспользоваться, чтобы он быладекватен задаче и позволял отразить возникший параллелизм в методе ее решения, какопрелить максимальную зернистость (степень распараллеливания задачи [2]) в параллельнойпрограмме, наконец, как организовать выполнение программы (синхронизировать процессыи распределить ресурсы), чтобы достичь желаемого эффекта.ПЛЕНАРНЫЕ ДОКЛАДЫ ПЯТОЙ МЕЖДУНАРОДНОЙ КОНФЕРЕНЦИИ«ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ И ЗАДАЧИ УПРАВЛЕНИЯ», МОСКВАPACO ‘2010PLENARY PAPERS OF THE FIFTH INTERNATIONAL CONFERENCE“PARALLEL COMPUTING AND CONTROL PROBLEMS”, MOSCOW43Поиск ответов на все эти вопросы далеко не завершен и, по-видимому, потребуетсянемалое время для проб и ошибок, чтобы найти приемлемые решения перечисленныхпроблем.Ниже мы попытаемся более предметно поговорить об особенностях и способах заданияпараллелизма, языках и средах параллельного программирования, управлениипараллельными процессами и операционных средствах, необходимых для его реализации.1.

Особенности, способы представления и характеристики параллелизма.Понятие параллелизма введено в статье С. Гилла [3] с целью изменения парадигмыпрограммы как последовательного алгоритмического процесса и создания языков,позволяющих описывать параллельные действия, естественные в любом алгоритме. Однако,концепция последовательной программы фон Неймана оказалась настолько простой, как и еекомпьютерная реализация, что и сейчас параллелизм часто рассматривается как нечтоспецифическое и искусственно вводимое в программу дополнение, направленное наускорение ее выполнения.Однако каждый програмист хорошо знает, какие трудности возникают припрограммировании на последовательных языках задач моделирования, управленияраспредленнымисистемами,операционныхсистем,многихмногоаспектныхвычислительных задач и др.

Поэтому при создании языков параллельного программированияидут двумя путями: либо пытаются расширить последовательный язык за счет включения внего средств описания параллелизма, сохраняя тем самым привычные и неплохоотработанные приемы последовательного программирования, либо пытаются изначальносоздавать язык параллельного программирования. Векторные команды, примитивы созданияветвей fork и join (первые широко использовались в системах ILLIAC, вторые – в системахБЭРРОУЗ и Эльбрус), API средства для описания параллельных процессов: PVM, MPI иMultithreading – примеры расширения последовательных языков с целью возможностиописания параллелизма.

На другом конце – попытки создания языков параллельногопрограммирования на основе определенных базовых конструкций, адекватных тем общимформам параллелизма, которые возникают в реальных задачах.Ясно, что в конечном итоге (в реализации) параллелизм – это одновременноепротекание и взаимодействие процессов. Способы порождения и взаимодействия процессов,их асинхронность и синхронизация, одновременность и строгое упорядочивание –основополагающие понятия процессных моделей [4-7], на которых стоят хорошо известныеяыковые средства для описания параллелизма на уровне процессов: PVM, MPI,Multithreading.На задачном уровне фундаментальным условием параллелизма являетсяинформационная независимость (независимость по данным) фрагментов декомпозициизадачи при построении алгоритма ее решения, будь это подзадачи или более мекие элементы,например, команды или операторы программы.На этой основе мы создалиязык граф-схемного потокового параллельногопрограммирования [8,9], который принципиально изменяет парадигму последовательнойпрограммы и основывается на явном задании в программе зависимостей по данным (и толькоПЛЕНАРНЫЕ ДОКЛАДЫ ПЯТОЙ МЕЖДУНАРОДНОЙ КОНФЕРЕНЦИИ«ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ И ЗАДАЧИ УПРАВЛЕНИЯ», МОСКВАPACO ‘2010PLENARY PAPERS OF THE FIFTH INTERNATIONAL CONFERENCE“PARALLEL COMPUTING AND CONTROL PROBLEMS”, MOSCOW44их) между фрагментами программы.

Как следствие, независимые фрагменты могутвыполняться одновременно.Другие важные особенности этого языка:•••••возможность визуального проектирования параллельной программы в виде графсхемы, одновременно отражающей посредством введения модулей декомпозициюзадачи и связи по данным между модулями программы;возможность построения рекурсивных граф-схем и отражение иерархии придекомпозиционной стратегии пошаговой разработки программы;простое описание потоковой обработки, в частности, при применении программы кпотоку (в том числе поступающему в реальном времени) тегированных данных;естественное представление вычислений с упреждением;использование различных языков последовательного программирования дляпостроения программ модулей.Другой способ неявного отражения параллелизма на задачном уровне – использованиефункциональной нотации.

Ясно, что для любой n-арной функции f(x1, x2,..., xn), n ≥ 1, можноодновременно вычислять значения функций, подставленных вместо ее аргументов.Условный оператор if P(x) then f1(x) else f2(x) также может рассматриваться как специальнаятернарная функция Y(P(x), f1(x), f2(x)), из чего следует возможность одновременноговычисления функций P(x), f1(x), f2(x).Мы создали язык функционального параллельного программирования FPTL [10], вкотором в отличие от функциональных языков ML, Haskell и других, основанных на lambdaисчислении, используются традиционные математические формы задания функций.Введенные в этом языке операции композиции функций позволяют в схемной формеотражать параллелизм в функциональной программе. В языке FPTL можно определятьабстрактные типы данных, использовать библиотечные функции, организовывать модульныефункциональные программы.