СКИПОДы 2007 полная версия (1127795), страница 41
Текст из файла (страница 41)
Эти процессы опрашивают состояние решающего поля инастраиваются на выполнение своей части вычислений.(Они могут узнать: сколько ихпорождено, свои уникальные, внутренние имена, и т.д.)Процессы, работающие на равных правах (не вызовы процедур и не процессы, связанныепонятиями "главная-подчиненная"), иногда называемые сопроцессами, могут выполнятьсяпараллельно и при этом общаться друг с другом - не часто (слабо связанные процессы).Требования с системам программирования методом передачисообщений.Кое-что…Основной моделью параллельного выполнения программы на кластере является модельпередачи сообщений .В этой модели параллельная программа представляет собой систему процессов,взаимодействующих посредством передачи сообщений .Можно выбрать модель передачи сообщений и в качестве модели программирования.При этом возможны три способа построения языка программирования:·Расширение стандартного языка последовательного программированиябиблиотечными функциями (например, Фортран+MPI);·Расширение стандартного языка последовательного программирования специальнымиконструкциями (например, Fortran-GNS);·Разработка нового языка (например, Occam).Однако модель передачи сообщений является слишком низкоуровневой, непривычной инеудобной для программистов, разрабатывающих вычислительные программы.
Оназаставляет программиста иметь дело с параллельными процессами и низкоуровневымипримитивами передачи сообщений .Поэтому вполне естественно, что прикладной программист хотел бы получить инструмент,автоматически преобразующий его последовательную программу в параллельнуюпрограмму для кластера. К сожалению, такое автоматическое распараллеливаниеневозможно в силу следующих причин.134Во-первых, поскольку взаимодействие процессоров через коммуникационную системутребует значительного времени (латентность – время самого простого взаимодействия велика по сравнению со временем выполнения одной машинной команды), товычислительная работа должна распределяться между процессорами крупными порциями.Совсем другая ситуация была на векторных машинах и на мультипроцессорах, гдеавтоматическое распараллеливание программ на языке Фортран реально использовалось идавало хорошие результаты.
Для автоматического распараллеливания на векторныхмашинах (векторизации) достаточно было проанализировать на предмет возможностипараллельного выполнения (замены на векторные операции) только самые внутренниециклы программы. В случае мультипроцессоров приходилось уже анализироватьобъемлющие циклы для нахождения более крупных порций работы, распределяемых междупроцессорами.Укрупнение распределяемых порций работы требует анализа более крупных фрагментовпрограммы, обычно включающих в себя вызовы различных процедур.
Это, в свою очередь,требует сложного межпроцедурного анализа. Поскольку в реальных программах на языкеФортран могут использоваться конструкции, статический анализ которых принципиальноневозможен (например, косвенная индексация элементов массивов), то с увеличениемпорций распределяемой работы увеличивается вероятность того, что распараллеливательоткажется распараллеливать те конструкции, которые на самом деле допускаютпараллельное выполнение.Во-вторых, в отличие от многопроцессорных ЭВМ с общей памятью, на системах сраспределенной памятью необходимо произвести не только распределение вычислений, нои распределение данных, а также обеспечить на каждом процессоре доступ к удаленнымданным - данным, расположенным на других процессорах.
Для обеспечения эффективногодоступа к удаленным данным требуется производить анализ индексных выражений нетолько внутри одного цикла, но и между разными циклами. К тому же, недостаточно простообнаруживать факт наличия зависимости по данным, а требуется определить точно тотсегмент данных, который должен быть переслан с одного процессора на другой.В третьих, распределение вычислений и данных должно быть произведено согласованно.Несогласованность распределения вычислений и данных приведет, вероятнее всего, к тому,что параллельная программа будет выполняться гораздо медленнее последовательной.Если на системе с общей памятью распараллелить один цикл, занимающий 90 процентоввремени решения задачи, то можно рассчитывать на почти десятикратное ускорениепрограммы (даже если оставшиеся 10 процентов будут выполняться последовательно). Насистеме с распределенной памятью распараллеливание этого цикла без учетапоследовательной части может вызватьне ускорение, а замедление программы.Последовательная часть будет выполняться на одном процессоре или на всех процессорах.Если в этой части используются распределенные массивы, то для такого выполненияпотребуется интенсивный обмен данными между процессорами.Согласованное распределение вычислений и данных требует тщательного анализа всейпрограммы, и любая неточность анализа может привести к катастрофическому замедлениювыполнения программы.Невозможностьполностьюавтоматическогораспараллеливанияимеющихсяпоследовательных программ для их выполнения на кластерах, не означает, конечно,неактуальности работ в этом направлении.
Если ввести некоторую дисциплину при135написании программ, и, возможно, позволить вставлять в программу некоторые подсказкираспараллеливателю, то такие программы могут автоматически преобразовываться впрограммы, способные выполняться параллельно на кластере. Однако в этом случае следуетговорить скорее не о распараллеливании имеющихся последовательных программ, а онаписании новых параллельных программ на традиционных языках последовательногопрограммирования или их расширениях.Система программирования MPI.MPI является на данный момент самой развитой системой параллельногопрограммирования с передачей сообщений. MPI позволяет создавать эффективные инадежные, переносимые параллельные программы высокого уровня.
Эффективность инадежность обеспечиваются такими механизмами как: определение MPI операций непроцедурно, а логически, т.е. внутренние механизмы выполнения операций скрыты отпользователя; использование непрозрачных объектов в MPI (группы, коммуникаторы, типыи т.д.);хорошей реализацией функций передачи данных, адаптирующихся к структуресистемы и обеспечивающих необходимую буферизацию данных. Переносимостьобеспечивается такими механизмами, как: определение одного вычислительногокомпьютера в виде виртуального компьютера и возможность задания произвольногоколичества таких виртуальных компьютеров в системе не зависимо от количествафизических компьютеров (зависимость только от объема оперативной памяти в системе);компиляторы для соответствующих языков на компьютерах вычислительной системы.Уровень языка параллельного программирования определяется языковыми конструкциями,с помощью которых создаются параллельные программы.
Чтобы более четко представитьсебе этот уровень нужно ответить на вопрос: - В чем одно из важных отличий в написаниипоследовательной и параллельной программ? Здесь имеется ввиду параллельная программадля рассматриваемых MIMD систем. Прежде чем создавать параллельную программу,необходимо знать общую архитектуру (виртуальной) параллельной машины и топологию(виртуальных) межпроцессорных связей, которая существенно используется припрограммировании.
Это связано с тем, что невозможно создание автоматическогораспараллеливателя, который позволял бы превращать последовательную программу впараллельную, и обеспечивал бы ее высокую производительность. Поэтому в программеприходится в явном виде задавать операторы инициации виртуальных топологий иоператоры обменов данными между (виртуальными) процессорами. При написании жепоследовательной программы знать архитектуру процессора, на котором будет исполнятьсяпрограмма, зачастую нет необходимости, поскольку учет особенностей архитектурыскалярного процессора может быть сделан компилятором с приемлемыми потерями впроизводительности программы.
Поэтому языковый уровень параллельной программыявляется заведомо ниже уровня последовательной программы, т.к. пользователю нужно вявном виде увязывать структуру алгоритма своей задачи со структурой вычислительнойсистемы. Таким образом языковый уровень рассматривается в рамках уровнейпараллельных конструкций, для создания параллельных программ. Для решения своейзадачи, пользователь с помощью команды (в командной строке): mpirun […] -np N, задаетвычислительную систему из N виртуальных компьютеров, соединенных между собойвиртуальными каналами с топологией связи - "полный граф". В дополнение к этому,наличие операторов парных взаимодействий между процессорами в такой среде,достаточно для реализации всего спектра используемых в программах схем системныхвзаимодействий.