Light-electric.com

IT Журнал
2 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Что такое параллельное программирование

ПРОГРАММИРОВАНИЕ ПАРАЛЛЕЛЬНОЕ

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

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

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

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

Предпосылкой для распараллеливания выражений служит тот факт, что входящие в них операции и функции удовлетворяют нек-рым соотношениям, индуцирующим на всем множестве выражений отношение эквивалентности по результатам (например, для арифметич. операций — ассоциативность, коммутативность, дистрибутивность). Задача распараллеливания состоит в построении по заданному выражению Еэквивалентного выражения E’, к-рое может быть исполнено за наименьшее число параллельных шагов, где параллельный шаг — это совокупность действий, выполняемых одновременно на разных вычислителях (процессорах). Напр., выражение

преобразуется в эквивалентное выражение

исполнение к-рого осуществляется за 3 параллельных шага. Отношение числа параллельных шагов исполнения к числу последовательных шагов наз. ускорением распараллеливания. Любое арифметич. выражение с поперандами может быть вычислено параллельно за О(log n).шагов с использованием п процессоров. Относительная простота алгоритмов распараллеливания выражений позволяет реализовать их автоматически в ЭВМ с помощью специальных программ или аппаратными средствами.

Большее ускорение может быть получено за счет распараллеливания обработки структурных данных. В алгоритмич. языках типа алгол или фортран выражения над структурными данными программируются с помощью операторов цикла вида FOR I=A, В, С,DO S, где I — целочисленный параметр цикла, А — его начальное значение, В — конечное значение, С — шаг изменения параметра, S — тело цикла, задающее действия, выполнимые на одном шаге итерации. Для распараллеливания системы вложенных циклов рассматривается n-мерное целочисленное пространство итераций с координатными осями I1, I2, . . ., In. Выполнение K1 -й итерации по параметру Il, K2 йитерации но параметру I2, . . ., К п йитерации по параметру I п изображается точкой (K1, . . ., К n).этого пространства. В пространстве итераций ищется семейство поверхностей, удовлетворяющих условию: все итерации ( К 1, . . ., К п), лежащие на любой из этих поверхностей, могут выполняться параллельно. Для программного представления параллельной обработки структурных данных необходимы специальные языковые средства. С этой целью разработаны модификации существующих языков программирования (в основном — фортрана), в к-рые вводятся параллельные операторы циклов, напр., вида

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

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

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

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

Наиболее известными и простыми программными механизмами синхронизации являются семафоры и события. Семафор — это специальная управляющая переменная, принимающая целочисленные значения. Семафор обычно связан с нек-рым конфликтным ресурсом. К семафору применимы только две операции Ри V. Если в ходе исполнения процесса встретится операция P(s), где s — семафор, то процесс может продолжаться с уменьшением значения s на 1 только в том случае, когда значение s положительно; в противном случае он приостанавливается и занимает место в очереди q(s).процессов, ждущих соответствующего ресурса. Операция Vувеличивает значение s на 1 и возобновляет первый в очереди q(s).процесс. Механизм семафоров широко используется в языках управления процессами в операционных системах ЭВМ и в ряде универсальных языков программирования (напр., алгол-68). Механизм событий включает управляющие переменные, текущие значения к-рых отмечают наступление каких-либо программных или системных событий (завершение процессов, прерывания и т. п.), и специальные операторы ожидания событий.

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

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

В теории П. п. разрабатываются формальные модели параллельных программ, процессов и систем и с их помощью исследуются различные аспекты П, п.: автоматич. распараллеливание последовательных алгоритмов и программ; разработка параллельных методов вычислений для разных классов задач и разных классов параллельных вычислительных систем- оптимальное планирование параллельных вычислений и распределение ресурсов между параллельными процессами; формальное описание семантики программ и языков П. п. Среди таких моделей — схемы параллельных программ, отражающие с разной степенью детализации структурные свойства программ; графовые модели и асинхронные сети ( Петри сети), являющиеся математич. абстракциями дискретных процессов и систем. Лит.:[1] Котов В. К., «Кибернетика», 1974, № 1, с. 1-16; №2, с. 1-18; [2] Нариньяни А. С., там же, № 3, с. 1-15; № 5, с. 1 — 14; [3] Фаддеева В. Н., Фаддеев Д. К., там же, 1977, № 6, с. 28-40; [4] Кuсk D. J., «Сотр. Surveys», 1977, v. 9, Mi 1, p. 29-59. В. Е. Котов.

Математическая энциклопедия. — М.: Советская энциклопедия . И. М. Виноградов . 1977—1985 .

Параллельное программирование

С отображением результата на экране все понятно. Но вот действия, которые программа должна произвести «за кадром» иногда занимают достаточно много времени. Естественный вопрос для разработчика — как ускорить выполнение программы? Конечно, можно посоветовать пользователю использовать более быстрый компьютер, но это решение очень ограничено, да и скорости компьютеров сейчас несильно увеличиваются. А вот что увеличивается — это количество ядер на компьютере.

Что дают эти ядра? Возможность независимо запустить несколько программ так, чтобы они не мешали друг другу. На четырехядерном компьютере вы можете одновременно запустить четыре линейных программы, требующих полной загрузки, и производительность не упадет. Возникает вопрос: а можно ли так сделать, чтобы одна программа стала работать в четыре раза быстрее?

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

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

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

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

2. .Таксономия (Классификация) Флинна (англ. Flynn’s taxonomy) — общая классификация архитектур ЭВМ по признакам наличия параллелизма в потоках команд и данных. Была предложена в 1970-е годы Майклом Флинном. Всё разнообразие архитектур ЭВМ в этой таксономии Флинна сводится к четырём классам:

  • ОКОД — Вычислительная система с одиночным потоком команд и одиночным потоком данных
    (SISD, Single Instruction stream over a Single Data stream).
  • ОКМД — Вычислительная система с одиночным потоком команд и множественным потоком данных
    (SIMD, Single Instruction, Multiple Data).
  • МКОД — Вычислительная система со множественным потоком команд и одиночным потоком данных
    (MISD, Multiple Instruction Single Data).
  • МКМД — Вычислительная система со множественным потоком команд и множественным потоком данных
    (MIMD, Multiple Instruction Multiple Data).
Читать еще:  C веб программирование

Типичными представителями SIMD являются векторные архитектуры. К классу MISD ряд исследователей относит конвейерные ЭВМ, однако это не нашло окончательного признания, поэтому можно считать, что реальных систем — представителей данного класса не существует. Класс MIMD включает в себя многопроцессорные системы, где процессоры обрабатывают множественные потоки данных.

Отношение конкретных машин к конкретному классу сильно зависит от точки зрения исследователя. Так, конвейерные машины могут быть отнесены и к классу SISD (конвейер — единый процессор), и к классу SIMD (векторный поток данных с конвейерным процессором) и к классу MISD (множество процессоров конвейера обрабатывают один поток данных последовательно), и к классу MIMD — как выполнение последовательности различных команд (операций ступеней конвейера) на множественным скалярным потоком данных (вектором).

1.Преимущества параллельного программирования

Программы, надлежащее качество проектирования которых позволяет воспользоваться преимуществами параллелизма, могут выполняться быстрее, чем их последовательные эквиваленты, что повышает их рыночную стоимость. Иногда скорость может спасти жизнь. В таких случаях быстрее означает лучше. Иногда решение некоторых проблем представляется естественнее в виде коллекции одновременно выполняемых задач. Это характерно для таких областей, как научное программирование, математическое и программирование искусственного интеллекта. Это означает, что в некоторых ситуациях технологии параллельного программирования снижают трудозатраты разработчика ПО, позволяя ему напрямую реализовать структуры данных, алгоритмы и эвристические методы, разрабатываемые учеными. При этом используется специализированное оборудование. Например, в мультимедийной программе с широкими функциональными возможностями с целью получения более высокой производительности ее логика может быть распределена между такими специализированными процессорами, как микросхемы компьютерной графики, цифровые звуковые процессоры и математические спецпроцессоры. К таким процессорам обычно обеспечивается одновременный доступ. МРР-компьютеры (Massively Parallel Processors — процессоры с массовым параллелизмом) имеют сотни, а иногда и тысячи процессоров, что позволяет их использовать для решения проблем, которые просто не реально решить последовательными методами. Однако при использовании МРР-компьютеров (т.е. при объединении скорости и «грубой силы») невозможное становится возможным. К категории применимости МРР-компьютеров можно отнести моделирование экологической системы (или моделирование влияния различных факторов на окружающую среду), исследование космического пространства и ряд тем из области биологических исследований, например проект моделирования генома человека. Применение более совершенных технологий параллельного программирования открывает двери к архитектурам ПО, которые специально разрабатываются для параллельных сред. Например, существуют специальные мультиагентные архитектуры и архитектуры, использующие методологию «классной доски», разработанные специально для среды с параллельными процессорами.

2. .Зако́н Амдала — иллюстрирует ограничение роста производительности вычислительной системы с увеличением количества вычислителей. Джин Амдал сформулировал закон в 1967 году, обнаружив простое по существу, но непреодолимое по содержанию ограничение на рост производительности при распараллеливании вычислений: «В случае, когда задача разделяется на несколько частей, суммарное время её выполнения на параллельной системе не может быть меньше времени выполнения самого длинного фрагмента». [1] Согласно этому закону, ускорение выполнения программы за счёт распараллеливания её инструкций на множестве вычислителей ограничено временем, необходимым для выполнения её последовательных инструкций.

Закон Густафсона (иногда Густавсона) — Барсиса — оценка максимально достижимого ускорения выполнения параллельной программы, в зависимости от количества одновременно выполняемых потоков вычислений («процессоров») и доли последовательных расчётов. Аналог закона Амдала.

Закон Густафсона — Барсиса выражается формулой: , где

g — доля последовательных расчётов в программе,

p — количество процессоров.

Данную оценку ускорения называют ускорением масштабирования (англ. scaled speedup), так как данная характеристика показывает, насколько эффективно могут быть организованы параллельные вычисления при увеличении сложности решаемых задач.

1. .Синхронизация процессов — приведение двух или нескольких процессов к такому их протеканию, когда определённые стадии разных процессов совершаются в определённом порядке, либо одновременно.

Синхронизация необходима в любых случаях, когда параллельно протекающим процессам необходимо взаимодействовать. Для её организации используются средства межпроцессного взаимодействия. Среди наиболее часто используемых средств — сигналы и сообщения, семафоры и мьютексы, каналы (англ. pipe), совместно используемая память.

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

Способ синхронизации данных зависит от делаемых дополнительных предположений. Главной проблемой тут является то, что независимо сделанные изменения могут быть несовместимы друг с другом (так называемый «конфликт правок»), и даже теоретически не существует общего способа разрешения подобных ситуаций.

Тем не менее, есть ряд частных способов, применимых в тех или иных случаях:

  • Наиболее простой способ: предполагают, что изменения вносились лишь в одну из копий — «рабочую» — и другая копия просто перезаписывается её содержимым. Этот способ реализуют большинство приложений синхронизации; в силу необратимости делаемых изменений пользователю даётся выбор, какую копию считать «главной».
  • Если данные представляют собой набор независимых записей (то есть любое сочетание записей является корректным — это, напр., телефонная книга), то можно просто объединить множества записей. Это ликвидирует риск потери информации, но чтобы удалить запись из набора, этот способ приходится сочетать с первым.
    • Если наборы синхронизируются неоднократно, можно автоматически вводить в них дополнительную служебную информацию: дата и время последнего изменения записи, пометки об удалённых записях (стираются после следующей синхронизации или через достаточно большое время) и пр. . Этот подход используется, например, в Outlook.
  • Обрабатывать конфликты правок: автоматически (если возможно), иначе — вручную. Этот, наиболее общий способ применяется только если указанные выше упрощённые недопустимы — например, в системах контроля версий. Так, CVS при обнаружении двух независимых изменений объявляет о «конфликте» и либо (в простых случаях) разрешает его автоматически, либо предоставляет пользователю разрешить его вручную. В этих случаях конфликтов стараются просто избегать — например, распределением областей компетенции.

Одним из механизмов синхронизации данных является репликация, которая в частности находит применение для синхронизации содержимого баз данных.

2. Библиотека параллельных шаблонов (PPL) предоставляет алгоритмы, обеспечивающие параллельную работу с коллекциями данных.Эти алгоритмы похожи на алгоритмы из стандартной библиотеки шаблонов (STL).

Параллельные алгоритмы строятся на основе существующих функциональных возможностей среды выполнения с параллелизмом.Например, алгоритм concurrency::parallel_for использует объект concurrency::structured_task_group, чтобы выполнять итерации параллельного цикла.Алгоритм parallel_for оптимальным образом разделяет работу на секции в соответствии с определенным доступным количеством вычислительных ресурсов.

Подразделы

  • Алгоритм parallel_for
  • Алгоритм parallel_for_each
  • Алгоритм parallel_invoke
  • Алгоритмы parallel_transform и parallel_reduce
    • Алгоритм parallel_transform
    • Алгоритм parallel_reduce
    • Пример. Параллельное выполнение сопоставления и уменьшения
  • Секционирование работы
  • Параллельная сортировка
    • Выбор алгоритма сортировки

· В следующем примере показана основная структура алгоритма parallel_for.Этот пример параллельно выводит на консоль все значения в диапазоне [1, 5].

Параллельное программирование: описание, технология, задачи и преимущества

Идеи параллельных вычислений и обработки информации долгое время были уделом специалистов и достаточно значительной проблемой в плане реализации. Особенное значение и массовый интерес они приобрели не так давно.

Можно утверждать, что именно развитие интернет-технологий дало новый импульс и параллельное программирование приобрело новые потребительские качества. Это обусловило не только очевидный прогресс технологий и языков программирования. Это реально создало обратное влияние на понимание параллельного процесса.

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

Параллельные вычисления: смысл и реализация

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

Последовательность команд, данных, функционально полных последовательных алгоритмов рассматривалась как объект, который можно исполнить параллельно с другим подобным объектом.

При таком подходе сущность каждого объекта не имела значения, но имело значение такое разбиение на параллельные участки кода, которые могли быть исполнены независимо, то есть данные на входе и выходе каждого потока не пересекались. Каждый поток не зависел от другого потока, а если он нуждался в данных от другого потока, то переходил в режим ожидания.

Такая идея привела к четырем архитектурам:

  • SISD — простой поток команд и простой поток данных;
  • MISD — множественный поток команд и простой поток данных;
  • SIMD — простой поток команд и множественный поток данных;
  • MIMD — многовариантный поток команд и множественный поток данных.

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

Недосток архитектурной идеи: отсутствие семантики

Как и конструкция жилого здания, архитектура вычислительной системы не касалась семантики. Как будут жить жильцы в здании, какой они смогут сделать ремонт и какую решат установить мебель, никогда не волновало строителей.

В самом начале системы параллельного программирования также не придавали значения алгоритму, который должен будет исполняться. Процессор сам разделял код и данные на участки, которые исполнял параллельно. Это давало заметный прирост производительности, но волновала, в частности:

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

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

Промышленное применение параллельности

Первое назначение компьютеров: сложные математические вычисления, промышленное применение и всё, что не касалось повседневной жизни, мобильности и интернета. Естественно, когда задачи параллельного программирования столь «ограничены», трудно ожидать интересных достижений.

Когда компьютеры стали продукцией массового применения, появился интернет и мобильные девайсы, требования к параллельности резко изменились и разработчикам пришлось кардинально менять стиль и скорость работы.

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

Windows и ей подобные системы закрепили эту идею и фактически сделали её законодательной нормой: параллельность и обмен сообщениями — это одно целое для всякой многопроцессорной , многоядерной, а по существу — для любой информационной системы.

От вычислений к обработке информации

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

Читать еще:  Основы программирования на языке c

«Промышленное» мышление в программировании, когда параллельное многопоточное программирование является целью, а не средством, сущестовало недолго. К каким фундаментальным результатам оно привело, сказать трудно. Однако нет сомнений в том, что программирование, которое было до эпохи интернет-программирования, стало основанием для отличных идей и хорошего потенциала современных языков и инструментальных средств.

Аппаратная составляющая

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

Следующее поколение компьютеров — персональные. Персоналки помещались на рабочем столе, а сотовые телефоны можно было носить на плече. Персоналки быстро изменились и приобрели современный вид, дали жизнь ноутбукам, планшетам и иным девайсам, а сотовые телефоны превратились в удобные многофункциональные смартфоны.

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

Сегодня количество ядер процессора, количество процессоров, уровень технологии, параллельность и функциональность кода критичны даже непосвященному пользователю.

Математический аппарат

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

Можно говорить о количестве ядер в процессоре девайса, но процессор для отображения информации уже давно один и занимается своим делом. Видеокарта может иметь не один процессор и не одно ядро, но математический аппарат в нее имплантирован.

Процессор компьютера только формулирует простые команды на отображение информации или выборку её из видеопамяти, остальное — забота процессора видеокарты.

Собственно, математические вычисления уже давно были выделены из основного процессора в математический сопроцессор. В настоящее время это тоже норма вещей.

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

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

Объектно-ориентированное программирование

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

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

Информационная система, построенная на объектах, как правило, это некоторая система абстракций, допускающая различные варианты создания объектов различного типа и назначения. Будучи описанными на уровне абстракций, информационные системы могут обеспечивать различные комбинации объектов, включая создание последними самих себя.

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

Кластеры и распределенная параллельность

Современное интернет-программирование для решения сложных и уникальных задач предлагает единственно возможное решение: ручная работа! Для обыденного и коммерческого применения используются многочисленные и разнообразные системы управления сайтами.

Характерная черта интернет-программирования:

  • неопределенность;
  • множественность;
  • одновременность.

Создавая сайт, программист (чаще коллектив программистов) не знает, сколько посетителей должен будет принимать веб-ресурс, но знает точно, что всем клиентам сайт должен обеспечить одинаковое и минимальное время отклика на любое действие.

Очевидное решение: разместить сайт на множестве серверов или кластеров по территориальному признаку, и тогда каждый регион будет обслуживать конкретный сервер. Но современный сайт не только предоставляет информацию, но и использует её. Например, интернет-магазин не может торговать воздухом и, если одно изделие было приобретено в Москве, оно должно исчезнуть со склада для потребителя во Владивостоке.

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

В таком контексте параллельное программирование приобретает совершенно иной смысл. Если раньше разработчик ставил во главу угла механизм реализации параллельности, не имея ввиду саму задачу, то сегодня разработчика меньше всего волнует, как реализована параллельность на уровне аппаратуры или инструментального средства, его интересует параллельность на уровне клиентов, то есть самой задачи, самой сферы применения веб-ресурса.

Кластер, как вариант параллельной реализации

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

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

Разработчик, работая с кластерами, может планировать и реализовывать собственный функционал параллельной распределенной обработки информации. Это очень существенный прогресс в современной разработке.

«Жизнь» современного объекта

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

Современная динамичная страница состоит из различного контента, каждая часть страницы может быть загружена самостоятельно, в зависимости от поведения посетителя. В этом контексте объектно-ориентированное программирование показывает, что далеко не весь его потенциал раскрыт.

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

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

Собственный сервер будет держать нужную систему объектов в актуализированном состоянии, что значительно ускорит обработку запросов как от одной страницы, так и от всех страниц, открытых во всем интернет-пространстве для конкретного веб-ресурса.

Параллельное программирование

С отображением результата на экране все понятно. Но вот действия, которые программа должна произвести «за кадром» иногда занимают достаточно много времени. Естественный вопрос для разработчика — как ускорить выполнение программы? Конечно, можно посоветовать пользователю использовать более быстрый компьютер, но это решение очень ограничено, да и скорости компьютеров сейчас несильно увеличиваются. А вот что увеличивается — это количество ядер на компьютере.

Что дают эти ядра? Возможность независимо запустить несколько программ так, чтобы они не мешали друг другу. На четырехядерном компьютере вы можете одновременно запустить четыре линейных программы, требующих полной загрузки, и производительность не упадет. Возникает вопрос: а можно ли так сделать, чтобы одна программа стала работать в четыре раза быстрее?

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

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

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

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

2. .Таксономия (Классификация) Флинна (англ. Flynn’s taxonomy) — общая классификация архитектур ЭВМ по признакам наличия параллелизма в потоках команд и данных. Была предложена в 1970-е годы Майклом Флинном. Всё разнообразие архитектур ЭВМ в этой таксономии Флинна сводится к четырём классам:

  • ОКОД — Вычислительная система с одиночным потоком команд и одиночным потоком данных
    (SISD, Single Instruction stream over a Single Data stream).
  • ОКМД — Вычислительная система с одиночным потоком команд и множественным потоком данных
    (SIMD, Single Instruction, Multiple Data).
  • МКОД — Вычислительная система со множественным потоком команд и одиночным потоком данных
    (MISD, Multiple Instruction Single Data).
  • МКМД — Вычислительная система со множественным потоком команд и множественным потоком данных
    (MIMD, Multiple Instruction Multiple Data).

Типичными представителями SIMD являются векторные архитектуры. К классу MISD ряд исследователей относит конвейерные ЭВМ, однако это не нашло окончательного признания, поэтому можно считать, что реальных систем — представителей данного класса не существует. Класс MIMD включает в себя многопроцессорные системы, где процессоры обрабатывают множественные потоки данных.

Отношение конкретных машин к конкретному классу сильно зависит от точки зрения исследователя. Так, конвейерные машины могут быть отнесены и к классу SISD (конвейер — единый процессор), и к классу SIMD (векторный поток данных с конвейерным процессором) и к классу MISD (множество процессоров конвейера обрабатывают один поток данных последовательно), и к классу MIMD — как выполнение последовательности различных команд (операций ступеней конвейера) на множественным скалярным потоком данных (вектором).

1.Преимущества параллельного программирования

Программы, надлежащее качество проектирования которых позволяет воспользоваться преимуществами параллелизма, могут выполняться быстрее, чем их последовательные эквиваленты, что повышает их рыночную стоимость. Иногда скорость может спасти жизнь. В таких случаях быстрее означает лучше. Иногда решение некоторых проблем представляется естественнее в виде коллекции одновременно выполняемых задач. Это характерно для таких областей, как научное программирование, математическое и программирование искусственного интеллекта. Это означает, что в некоторых ситуациях технологии параллельного программирования снижают трудозатраты разработчика ПО, позволяя ему напрямую реализовать структуры данных, алгоритмы и эвристические методы, разрабатываемые учеными. При этом используется специализированное оборудование. Например, в мультимедийной программе с широкими функциональными возможностями с целью получения более высокой производительности ее логика может быть распределена между такими специализированными процессорами, как микросхемы компьютерной графики, цифровые звуковые процессоры и математические спецпроцессоры. К таким процессорам обычно обеспечивается одновременный доступ. МРР-компьютеры (Massively Parallel Processors — процессоры с массовым параллелизмом) имеют сотни, а иногда и тысячи процессоров, что позволяет их использовать для решения проблем, которые просто не реально решить последовательными методами. Однако при использовании МРР-компьютеров (т.е. при объединении скорости и «грубой силы») невозможное становится возможным. К категории применимости МРР-компьютеров можно отнести моделирование экологической системы (или моделирование влияния различных факторов на окружающую среду), исследование космического пространства и ряд тем из области биологических исследований, например проект моделирования генома человека. Применение более совершенных технологий параллельного программирования открывает двери к архитектурам ПО, которые специально разрабатываются для параллельных сред. Например, существуют специальные мультиагентные архитектуры и архитектуры, использующие методологию «классной доски», разработанные специально для среды с параллельными процессорами.

Читать еще:  Модульное программирование в си

2. .Зако́н Амдала — иллюстрирует ограничение роста производительности вычислительной системы с увеличением количества вычислителей. Джин Амдал сформулировал закон в 1967 году, обнаружив простое по существу, но непреодолимое по содержанию ограничение на рост производительности при распараллеливании вычислений: «В случае, когда задача разделяется на несколько частей, суммарное время её выполнения на параллельной системе не может быть меньше времени выполнения самого длинного фрагмента». [1] Согласно этому закону, ускорение выполнения программы за счёт распараллеливания её инструкций на множестве вычислителей ограничено временем, необходимым для выполнения её последовательных инструкций.

Закон Густафсона (иногда Густавсона) — Барсиса — оценка максимально достижимого ускорения выполнения параллельной программы, в зависимости от количества одновременно выполняемых потоков вычислений («процессоров») и доли последовательных расчётов. Аналог закона Амдала.

Закон Густафсона — Барсиса выражается формулой: , где

g — доля последовательных расчётов в программе,

p — количество процессоров.

Данную оценку ускорения называют ускорением масштабирования (англ. scaled speedup), так как данная характеристика показывает, насколько эффективно могут быть организованы параллельные вычисления при увеличении сложности решаемых задач.

1. .Синхронизация процессов — приведение двух или нескольких процессов к такому их протеканию, когда определённые стадии разных процессов совершаются в определённом порядке, либо одновременно.

Синхронизация необходима в любых случаях, когда параллельно протекающим процессам необходимо взаимодействовать. Для её организации используются средства межпроцессного взаимодействия. Среди наиболее часто используемых средств — сигналы и сообщения, семафоры и мьютексы, каналы (англ. pipe), совместно используемая память.

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

Способ синхронизации данных зависит от делаемых дополнительных предположений. Главной проблемой тут является то, что независимо сделанные изменения могут быть несовместимы друг с другом (так называемый «конфликт правок»), и даже теоретически не существует общего способа разрешения подобных ситуаций.

Тем не менее, есть ряд частных способов, применимых в тех или иных случаях:

  • Наиболее простой способ: предполагают, что изменения вносились лишь в одну из копий — «рабочую» — и другая копия просто перезаписывается её содержимым. Этот способ реализуют большинство приложений синхронизации; в силу необратимости делаемых изменений пользователю даётся выбор, какую копию считать «главной».
  • Если данные представляют собой набор независимых записей (то есть любое сочетание записей является корректным — это, напр., телефонная книга), то можно просто объединить множества записей. Это ликвидирует риск потери информации, но чтобы удалить запись из набора, этот способ приходится сочетать с первым.
    • Если наборы синхронизируются неоднократно, можно автоматически вводить в них дополнительную служебную информацию: дата и время последнего изменения записи, пометки об удалённых записях (стираются после следующей синхронизации или через достаточно большое время) и пр. . Этот подход используется, например, в Outlook.
  • Обрабатывать конфликты правок: автоматически (если возможно), иначе — вручную. Этот, наиболее общий способ применяется только если указанные выше упрощённые недопустимы — например, в системах контроля версий. Так, CVS при обнаружении двух независимых изменений объявляет о «конфликте» и либо (в простых случаях) разрешает его автоматически, либо предоставляет пользователю разрешить его вручную. В этих случаях конфликтов стараются просто избегать — например, распределением областей компетенции.

Одним из механизмов синхронизации данных является репликация, которая в частности находит применение для синхронизации содержимого баз данных.

2. Библиотека параллельных шаблонов (PPL) предоставляет алгоритмы, обеспечивающие параллельную работу с коллекциями данных.Эти алгоритмы похожи на алгоритмы из стандартной библиотеки шаблонов (STL).

Параллельные алгоритмы строятся на основе существующих функциональных возможностей среды выполнения с параллелизмом.Например, алгоритм concurrency::parallel_for использует объект concurrency::structured_task_group, чтобы выполнять итерации параллельного цикла.Алгоритм parallel_for оптимальным образом разделяет работу на секции в соответствии с определенным доступным количеством вычислительных ресурсов.

Подразделы

  • Алгоритм parallel_for
  • Алгоритм parallel_for_each
  • Алгоритм parallel_invoke
  • Алгоритмы parallel_transform и parallel_reduce
    • Алгоритм parallel_transform
    • Алгоритм parallel_reduce
    • Пример. Параллельное выполнение сопоставления и уменьшения
  • Секционирование работы
  • Параллельная сортировка
    • Выбор алгоритма сортировки

· В следующем примере показана основная структура алгоритма parallel_for.Этот пример параллельно выводит на консоль все значения в диапазоне [1, 5].

Основы программирования параллельных вычислений

Основными особенностями программирования параллельных вычислений являются: более высокая производительность программ и применение специальных приемов программирования, с которыми связаны более высокая трудоемкость и проблемы с переносимостью программ. В отличие от последовательного программирования (на распространенных языках Бейсик, Паскаль, Си, Фортран и др.) при этом возникают дополнительные проблемы: управление работой множества процессоров, организация межпроцессорных пересылок данных и т.д. Наиболее распространенные подходы к распараллеливанию вычислений и обработки данных основаны на моделях параллелизма данных и параллелизма задач.

Модель параллелизма данных предполагает применение одной операции сразу к нескольким элементам массива данных. Векторизация или распараллеливание чаще всего выполняется уже во время трансляции. Основные особенности модели:

· обработкой данных управляет одна программа;

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

· слабая синхронизация вычислений на параллельных процессорах – выполнение команд на разных процессорах происходит, как правило, независимо и только иногда производится согласование (синхронизация) выполнения циклов или других элементов программы.

· параллельные операции над элементами массива выполняются одновременно на всех доступных данной программе процессорах.

Упрощению программирования способствует использование базовых операций:

· операций управления данными;

· операций над массивами в целом и их фрагментами;

· операций приведения (вычисления для массива одного числа, например, суммы его элементов);

· операций сканирования, например префиксная операция суммирования, при которой сумма N последовательных элементов одного массива присваивается N-му элементу другого массива;

· операций, связанные с пересылкой данных, например, между массивами разной формы, размерности и протяженности по каждому измерению.

Для составления программ в модели параллелизма данных используются специализированные языки – CM FORTRAN, C*, FORTRAN+, MPP FORTRAN, Vienna FORTRAN, а также HPF (High Performance FORTRAN – высокопроизводительный фортран), основанный на языке программирования FORTRAN-90 с его удобными операциями над массивами. Реализация модели параллелизма данных выполняется на уровне трансляции программы на машинный язык с помощью препроцессоров, использующих библиотеки с реализациями параллельных алгоритмов, предтрансляторов для предварительного анализа и оптимизации и распараллеливающих трансляторов, которые выявляют параллелизм в исходном коде программы и выполняют его преобразование в параллельные конструкции.

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

· повышенная трудоемкость разработки и отладки программ;

· необходимость обеспечения равномерной и сбалансированной загрузки всех процессоров;

· необходимость минимизации обмена данными между задачами для уменьшения времени передачи;

· повышенная опасность тупиковых ситуаций.

Однако положительными сторонами являются большая гибкость и свобода и, как следствие, возможность достижения максимального быстродействия на основе эффективного использования ресурсов. Примерами специализированных библиотек являются распространяемые свободно в исходных кодах библиотеки MPI (Message Passing Interface – Интерфейс Передачи Сообщений) и PVM (Parallel Virtual Machines). Реализации спецификации MPI представляют собой библиотеки подпрограмм, которые могут использоваться в программах на языках C/C++ и FORTRAN. Пример простейшей MPI-программы на языке С:

int main(int argc, char *argv[])

int myid, numprocs;

fprintf(stdout,”Process %d of %d n”, myid, numprocs);

В программе используются подпрограммы MPI_Comm_size и MPI_Comm_rank. Первая возвращает количество процессоров, входящих в область взаимодействия, коммуникатор со стандартным именем MPI_COMM_WORLD, который указан в качестве ее первого аргумента, вторая подпрограмма определяет ранг процесса.

Средой выполнения параллельных программ являются операционные системы с поддержкой мультипроцессирования, многозадачности и многопоточности, например UNIX, LINUX, Microsoft Windows NT/2000/2003 Server.

Система разработки и выполнения параллельных программ PVM позволяет объединить разнородный набор компьютеров, связанных сетью в общий вычислительный ресурс, называемый Параллельной Виртуальной Машиной. Компьютеры могут быть многопроцессорными машинами любого типа: суперкомпьютерами, рабочими станциями и т.д., объединенными в сети любого вида (Ethernet, ATM и др. Поддерживаются языки C/C++ и FORTRAN и ряд других. Виртуальная машина допускает динамическое изменение конфигурации. Масштабируемость виртуальной машины позволяет включать в ее состав сотни хостов и выполнять в ее среде тысячи процессов. Система PVM может быть реализована в кластерах рабочих станций, имеющих относительно низкую стоимость – для создания кластера можно использовать даже сравнительно недорогие персональные компьютеры. Система PVM состоит из двух основных компонентов:

демона (процесса) pvmd3 (или pvdm), который запускается на всех компьютерах, входящих в состав виртуальной машины; Демоном в ОС UNIX называют процессы, управляющие различными службами, в данном случае выполнением PVM-программ.

· набора библиотек, реализующих операции параллельных вычислений и обмена данными, которые используются в параллельных программах на языках С и С++, а также через функции интерфейса и в программах на языке FORTRAN.

Для работы с виртуальной машиной в интерактивном режиме предназначена программа PVM –консоль.

Современное состояние программирования параллельных вычислений рассмотрено в [65].

Компания NEC предложила новую технологию создания многоядерных процессоров, позволяющую повысить эффективность параллельного выполнения приложений с неадаптированным программным кодом. В ее основе лежит возможность принудительного использования шаблонов разделения выполнения приложений, что ускоряет их работу. Это позволяет избавиться от трудоемкой предварительной отладки программ вручную. [66]

Ссылка на основную публикацию
Adblock
detector