Распараллеливание

On 11.11.2013 by nikellanjilo

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

Распараллеливание на уровне задач нам демонстрирует операционная система на примере «Диспетчера задач» Windows. Если первая программа показывает нам фильм, а вторая является файлообменным клиентом, то операционная система спокойно сможет организовать их параллельную работу. Другими примерами распараллеливания на этом уровне абстракции является параллельная компиляция файлов в Visual Studio 2008, обработка данных в пакетных режимах, например, в сети.  .NET Framework4 дополнен множеством средств, которые значительно облегчают выражение параллелизма в приложениях и обеспечивают его эффективность. Например, новое подпространством имен включает новый тип — Parallel, который предоставляет ряд статических методов для реализации параллельных циклов.

Для нескольких ядер программист явным образом указывает, какие функции на каких ядрах должны выполняться, — это физически параллельная система. Простота идеи программирования физически параллельных систем выливается на практике в целый ряд сложных методик и условий.

— алгоритм должен допускать распараллеливание.
— при вычленении параллельных участков приходится придавать алгоритму специальную форму. Например, если необходимо определить сумму массива, при распараллеливании на первом шаге одновременно суммируются соседние четные и нечетные элементы массива, а на втором попарно суммируются результаты, полученные на первом шаге, и т. д.
— в многопроцессорной системе разбиение на слишком крупные части не позволяет равномерно загрузить процессоры и добиться минимального времени вычислений, а излишне мелкая «нарезка» означает рост непроизводительных расходов на связь и синхронизацию.
— процесс создания максимально эффективного алгоритма практически не автоматизируется и связан с большими трудозатратами на поиск специфической структуры алгоритма. Более суровое следствие зависимости структуры алгоритма от вычислительной платформы — тотальная непереносимость не только исполняемых кодов, но и самого исходного текста.

Распараллеливание

Что бы распараллелить однородные задачи, нужно спуститься на уровень ниже. «Параллелизм данных» заключается в применении одной и той же операции к множеству элементов. Параллелизм данных демонстрирует архиватор, использующий для упаковки несколько ядер процессора. Данные разбиваются на блоки, которые единообразным образом упаковываются на разных узлах.

Данный вид параллелизма широко используется при решении задач численного моделирования. Счетная область представлена в виде ячеек, описывающих состояние среды в соответствующих точках пространства — давление, плотность, процентное соотношение газов, температура и так далее. Количество таких ячеек может быть огромным — миллионы и миллиарды. Каждая из этих ячеек должна быть обработана одним и тем же способом. Здесь модель параллелизма по данным крайне удобна, так как позволяет загрузить каждое ядро, выделив ему определенный набор ячеек. Счетная область разбивается на геометрические объекты, например параллелепипеды, и ячейки, вошедшие в эту область, отдаются на обработку определенному ядру. В математической физике такой тип параллелизма называют геометрическим параллелизмом.

Следующий уровень, это распараллеливание отдельных процедур и алгоритмов. Сюда можно отнести алгоритмы параллельной сортировки, умножение матриц, решение системы линейных уравнений. На этом уровне абстракций удобно использовать такую технологию параллельного программирования, как OpenMP.

Open Multi-Processing — это набор директив компилятора, библиотечных процедур и переменных окружения, которые предназначены для программирования многопоточных приложений на многопроцессорных системах. В основу положена идея использования специальных компиляторов («знающих» про параллельное программирование), для которых в коде программы расставляются специальные пометки-примечания, указывающие, что и где следует делать параллельно, а что — последовательно.
Компилятоp  — системная программа, выполняющая преобразование программы, написанной на одном алгоритмическом языке, в программу на языке, близком к машинному. Некоторые компиляторы (например, Java) переводят программу не в машинный код, а в программу на некотором специально созданном низкоуровневом языке. Такой язык, байт-код, также можно считать языком машинных команд, поскольку он подлежит интерпретации виртуальной машиной. Для каждой целевой машины (IBM, Apple и т.д.) и каждой операционной системы или семейства операционных систем, работающих на целевой машине, требуется написание своего компилятора.  Компилятор содержит две части — транслятор и компоновщик, именно последний помогает решать задачи распараллеливания.
Например, компилятор GCC содержит следующие инструментальные программные компоненты: препроцессор, транслятор, ассемблер, компоновщик (редактор связей — линковщик), которые реализуют выполнение одноименных фаз компиляции. Препроцессор вставляет в исходный текст программы заголовочные файлы, указанные директивой # include stdlib;, # define Macros( ) подставляет значения макросов, заданные директивой . Транслятор выполняет грамматический разбор программы на данном языке (С, С++) для проверки синтаксических ошибок. Ассемблер конвертирует текст программы на языке ассемблера в объектный код из машинных инструкций. Основной задачей компоновки является настройка внешних ссылок объектных модулей на точки входа функций переменных, которые определены в других объектных модулях программы и стандартных библиотеках системы программирования.
OpenMP позволяет работать на нескольких уровнях — либо задавать низкоуровневые объекты вручную, либо указывать, какие переменные являются «общими» и требуют синхронизации, передоверяя собственно синхронизацию компилятору.
В OpenMP используется модель параллельного выполнения «ветвление-слияние». Программа OpenMP начинается как единственный начальный поток выполнения. Когда поток встречает параллельную конструкцию, он создает новую группу потоков, состоящую из себя и некоторого числа дополнительных потоков, и становится главным в новой группе. Все члены новой группы (включая главный поток) выполняют код внутри параллельной конструкции. В конце параллельной конструкции имеется неявный барьер. После параллельной конструкции выполнение пользовательского кода продолжает только главный поток. Разработчик не создает новую параллельную программу, а просто последовательно добавляет в текст последовательной программы OpenMP-директивы.

Недостатков у OpenMP два. Первый — относительно жесткая модель программирования, навязываемая программисту — не очевидно, как заставить OpenMP-программу работать в режиме «системы массового обслуживания», когда некий «главный» поток принимает поступающие извне задания (скажем, запрос к веб-серверу) по отдельным потокам. А вручную подобная система делается элементарно. Второй — только сейчас появляющаяся поддержка сообщества Open Source.
Первая спецификация компилятора OpenMP (Open specifications for Multi-Processing) появилась в 1997 году и предназначалась для одного из древнейших языков программирования Fortran, на котором некогда было написано большинство «серьезных» вычислительных приложений. В 1998 году появились варианты OpenMP для языков C/C++; стандарт прижился, получил распространение и к настоящему моменту дорос до версии 2.5. Поддержка спецификации есть во всех компиляторах Intel, в компиляторе Microsoft C/C++, стандартизованно OpenMP — расширении для GCC (GNU-систем типа Linux).
Наиболее низкий уровень параллелизма осуществляется на уровне параллельной обработки процессором нескольких инструкций (команд). Можно изменить порядок этих инструкций, распределить их по группам, которые будут выполняться параллельно, без изменения результата работы всей программы (технологии MMX, SSE, SSE2 ит.д.). Это называется параллелизмом на уровне инструкций. Для реализации данного вида параллелизма в микропроцессорах используется несколько конвейеров команд, технологии предсказание команд, переименование регистров. Программист редко заглядывает на этот уровень. Работу по расположению команд в наиболее удобной последовательности для процессора выполняет компилятор. Интерес этот уровень распараллеливания может представлять только для узкой группы специалистов.

Добавить комментарий