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

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

Напрамер, для вычисления n! такая программа может быть следующего вида:,Где F(i, j) – ранее описанная функция для вычисления n!, k – параметр, определяющийколичество отрезков разбиения интервала [i – j], на которых выполняется одновременноевычисление произведений, заключенных в них целых чисел. Очевидно, что F(1, k, 1, m) = m!.Аналогичные функции с подобной параметризацией, задающей степеньраспараллеливания, легко строятся для вычисления,, численного интегрированияфункций на отрезке, перемножения матриц (здесь k определяет количество одновременноперемножаемых блоков матриц ) и др.Гораздо сложнее подобная параметризация осуществляется для параллельныхвычислений по сложным рекуррентным зависимостям, рекурсивных функций и др.Глубина и степень распараллеливания всегда ограничены. Например, максимальныйпараллелизм при перемножении матриц A и B достигается, когда все элементырезультирующей матрицы вычисляются одновременно при одновременномвычислении произведений и последующих сложений в приведенной формуле.

Хотя примаксимальном распараллеливании эффект часто негативный и может быть достигнут видеальном случае и, возможно, на компьютерах и компьютерных системах, построенных надругих принципах и элементах.2. Языки и среды параллельного программирования.Введенное в свое время различение Скоттом и Стречи в языках программировнияденотационной и операционной семантик для языков параллельного программированияимеет принципиальное значение.Очевидно, что универсализм языка с позиций представления параллелизмапредполагает возможность отражения в программе любых форм его проявления как назадачном уровне, т.е. данотационными средствами языка, так и на процессном уровнесредствами операционной семантики. Из этого ясно, что если мы, например, ограничиваемсебя на задачном уровне возможностью представления только вектороного параллелизмаили параллелизма ветвей (конструкциями fork и join), а в качестве операционных средтвбудем использовать Multithreading с достаточно большим набором описателей параллельныхпроцессов, то это будет стрельба из пушек по воробьям.

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

Это позволяет, в часности для вычислительныхзадач, разделить аспекты разработки параллельной программы, приблизить языковыесредства к задачной, т.е. проблемной области. При этом, если параллельная программа ссамого начала не связана с описанием процессов, программист может вовсе неинтересоваться тем, как будет выполняться его параллельная программа.Примерами таких двухаспектных языков являются язык граф-схемного потоковогопараллельногопрограммирования[8,9],языкфункциональногопараллельногопрограммирования FPTL [10,11], отчасти параллельный FORTRAN, DVM и др.В языке граф-схемного потокового параллельного программирования на задачномуровне (в его формальной денотационной семантике) реализована принципиально отличнаяот языков последовательного программирования парадигма (см. п.1), основанная напредставлении фрагментов декомпозиции задачи в виде функций (программ модулей) иявном указании (через граф-схему) связей по данным (и только их) между подпрограммами.Как следствие, независимые фрагменты могут выполняться одновременно.

Операционнаясемантика языка, определяющая правила параллельного выполнения граф-схемнойпрограммы, достаточно проста и основана на инициализации выполнения любого еефрагмента по поступавшим на его входы тегированным данным.Реализованная на многомашинных и многопроцессорных системах операционнаясемантика [8,9] в принципе избавляет программиста от необходимости планированияпроцессов выполнения программы и динамического распределения ресурсов компьютернойсостемы.Денотационная семантика параллельного FORTRAN`а, DVM и др.

языков легкопрослеживается в силу их узкого предназначения для описания легко распараллеливаемыхзадач линейной алгебры, где векторизация и распараллеливание «по циклам» – основныемеханизмы отражения параллелизма.В языке FPTL [10,11] используется функциональная нотация для описания методарешения задач, а реализация параллелизма основана на модели асинхронного параллельноговычисления значений функций на КС [11]. Параллелизм в этом языке отражается вфункциональной программе явно через используемые в ней операции композиции функций.В расширении языков HASKELL, ML, последовательных языков с целью задания впрограмме параллелизма используют специальные примитивы задания параллелизма (мыуже говорили о векторных командах, операторах fork-join) или программисту предоставленавозможность по тексту программы вводить комментарии, какие ее фрагменты и какимобразом должны быть распараллелены на стадии компиляции (OpenMP).

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

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

Поэтому так важны инструменты прогонок программы на конкретнойКС, сбор и обработка статистических данных, определяющих эффективность ее выполнения,средства оптимизации программы, проверки ее правильности как по содержанию, так и привыполнении (отсутствие тупиков, зацикливаний и т.п.).Не менее важными являются инструменты, поддерживающие технологиюдекомпозиционного программирования (программирование сверху-вниз) и сборочного(снизу-вверх), коллективную разработку программы и др. [2].

Очевидно, все это заставитпересмотреть и существенно расширить те многобразные инструменты поддержкипроцессов программирования, созданные сегодня Microsoft, IBM и др., чтобы их можно былоприменять и в параллельном программировании.3. Реализация параллелизма на компьютерных системах.Помимо собственно обeспечения логического управления процессами параллельноговыполнения программы на КС, предопределенного операционной семантикой языка,управление предполагает наличие в нем механизмов планирования процессов ираспределения для них ресурсов, от чего в большой степени зависит и время выполненияпрограммы, и использование ресурсов [14]. К сожалению, эта задача пока далека отудовлетворительного решения, в связи с чем программист сам заранее должен спланировать(определить приоритеты) выполнения процессов и даже распределить их насоответствующие узлы КС (пример, MPI).В [14] мы изложили наши подходы к созданию методов и программных средств,предназначенных для эффективного управления процессами выполнения параллельныхпрограмм на КС.