Контакты
Подписка
МЕНЮ
Контакты
Подписка

В рубрику "Решения корпоративного класса" | К списку рубрик  |  К списку авторов  |  К списку публикаций

Способы реализации параллельных вычислений

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

Лариса Меньшикова
экономический советник
департамента информационных систем
Банка России, к.ф.-м.н., доцент МИРЭА

Виды организации передачи данных

 

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

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

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

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

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

Балансировка нагрузки

 

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

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

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

Распараллеливание программ проводят двумя способами:

  • применение специальных библиотек программ некоторого стандартного языка программирования путем переписывания кода программ на специальный язык, описывающий параллелизм и понятный трансляторам целевой вычислительной системы (например, Windows API - многопоточные приложения для C++);
  • вставка некоторой специальной разметки (например, в соответствии со стандартом систем передачи сообщений между параллельно исполняемыми процессами инструкций Message Passing Interface (MPI) или стандартом интерфейса приложений для параллельных систем с общей памятью ОрепМР). Распараллеливание может быть ручным, автоматизированным и полуавтоматизированным. Для оценки эффективности его качества применяются вышеописанные характеристики - ускорение и загруженность.

Кроме того, можно использовать POSIX Threads - стандарт реализации потоков выполнения программ.

В случае распределенных вычислений используется PVM (Parallel Vir tual Machine), позволяющий объединить разнородный (но связанный сетью) набор компьютеров в общий вычислительный ресурс.

Стандарт параллельного программирования ОрепМР

 

ОрепМР - это стандарт параллельного программирования в среде с общей памятью. ОрепМР предоставляет программистам набор прагм, процедур и переменных среды, позволяющих легко параллелизовать код, написанный на Фортране, С или C++.

Прагма - это директива компилятора, указывающая, как обрабатывать код, следующий за прагмой. Когда прагмы ОрепМР используются в программе, они дают указание компилятору, поддерживающему ОрепМР, создать исполнимый модуль, который будет выполняться параллельно с использованием нескольких потоков. Прагмы ОрепМР позволяют использовать единообразный и переносимый интерфейс для параллелизации программ на различных архитектурах и системах. Спецификация ОрепМР принята многими и поддерживается такими поставщиками, как Sun, Intel, IBM и SGI.

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

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

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

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

Интерфейс передачи сообщений MPI

 

Message Passing Interface (MPI) - программный интерфейс для передачи информации, который позволяет процессам, выполняющим одну задачу, обмениваться сообщениями. Разработан Уильямом Гроуппом и Эвином Ласком.

MPI является наиболее распространенным стандартом интерфейса обмена данными при организации параллельных вычислений, существуют его реализации для большого числа компьютерных платформ. Этот стандарт также используется при разработке программ для кластеров и суперкомпьютеров. В стандарте MPI описан интерфейс передачи сообщений, который может поддерживаться как платформой, так и приложением пользователя. В настоящее время существует большое количество бесплатных и коммерческих реализаций MPI. Существуют реализации для языков Фортран 77/90, Си и Си++.

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


Первая версия MPI разрабатывалась в 1993 г. Большинство современных реализаций MPI поддерживают версию 1.1. Стандарт MPI версии 2.0 поддерживается большинством современных реализаций, но в нем пока не все функции "реализованы корректно".

В MPI 1.1 (опубликован 12 июня 1995 г., первая реализация появилась в 2002 г.) поддерживаются следующие функции:

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

В MPI 2.0 (опубликован 18 июля 1997 г.) дополнительно поддерживаются следующие функции:

  • динамическое порождение процессов и управление процессами;
  • односторонние коммуникации (Get/Put);
  • параллельный ввод и вывод;
  • расширенные коллективные операции (процессы могут выполнять коллективные операции не только внутри одной задачи, но и в рамках нескольких).

В начале сентября 2008 г. вышла версия MPI 2.1.

Выводы

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

Литература

  • Использование технологии параллельных вычислений для хранилищ данных //Технологии и средства связи. -2011,-№6.-С. 14-15.
  • Воеводин В.В., Воеводин В.В. Параллельные вычисления. - СПб.: БХВ-Петербург. 2004. - 608 с
  • Абрамов С.М. Суперкомпьютерные технологии России: объективные потребности и реальные возможности / Суперкомпьютеры и высокопроизводительные вычисления // CAD/CAM/CAE Observer. - 2 (54). -2010.-С. 1-11

Опубликовано: Журнал "Технологии и средства связи" #3, 2012
Посещений: 34255

Статьи по теме

  Автор

Меньшикова Л. В.

Меньшикова Л. В.

Ведущий инженер Радиочастотной службы ЦБ РФ к.ф.-м.н.

Всего статей:  9

В рубрику "Решения корпоративного класса" | К списку рубрик  |  К списку авторов  |  К списку публикаций