Стронгин Р.Г (ред.) Высокопроизводительные параллельные вычисления на кластерных системах

Подождите немного. Документ загружается.

301

фиксированы. Один из способов поиска оптимальной траектории –

метод перебора.

В рассматриваемой задаче наиболее «быстрой» траекторией

является плавная кривая, а ломаная линия из двух отрезков прямых –

всего лишь грубое приближение к ней. Тогда решение задачи можно

искать в классе ломаных, состоящих из

N отрезков прямых, и

увеличивать

N до тех пор, пока точность приближения не станет

приемлемой.

Задача о горнолыжнике является типичным представителем целого

семейства задач. Среди них, например, – задача о пикирующем

бомбардировщике или задача о перелете космического корабля с

одной планеты на другую.

Задание практикума для студентов физических

специальностей

В лабораторной работе рассматривается движение горнолыжника

по скользкому склону под действием сил тяжести и трения. Под

действием этих сил на прямолинейных участках траектории движение

происходит с постоянным ускорением. Данный лабораторный

практикум предназначен для изучения закономерностей подобного

движения, закона сохранения энергии, законов Ньютона.

Возможна постановка экспериментов для различных сочетаний

исходных параметров, таких

как: крутизна склона, ускорение

свободного падения, коэффициент трения.

Задание практикума для студентов математических

специальностей

Для студентов математических специальностей задача о спуске

горнолыжника представляет интерес как задача оптимального

управления. В лабораторной работе предоставляется возможность

выбора точек переключения кусочно-постоянных управлений,

приводящих к кусочно-линейной траектории движения.

Цель управления состоит в достижении точки финиша за

наименьшее время. Таким образом, студенты на практике знакомятся с

решением одной задачи

быстродействия.

Возможна постановка эксперимента в ручном и автоматическом

режимах. В ручном режиме студенту предлагается самостоятельно

выбирать точки переключения, их число. По выбранным точкам

программа строит траекторию движения и вычисляет общее время

движения.

302

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

управления таким образом, чтобы общее время движения было

минимальным.

Задание практикума для студентов компьютерных

специальностей

Студентам компьютерных специальностей предлагается

проанализировать алгоритм работы программы, подготовить его

параллельную версию, реализовать ее с использованием различных

средств многонитиевого параллельного программирования.

Предлагается исследовать процесс работы программы с

использованием различных инструментов отладки и профилирования,

оптимизировать параллельную программу для эффективного

использования ресурсов многоядерной системы, достижения

производительности, близкой к максимально возможной.

Заключение

Авторы располагают программно-методическим комплексом,

описанным в данной работе. И планируют использовать его в

читаемых ими курсах.

ЭФФЕКТИВНЫЕ ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ

И ПРОГРАММНЫЕ СРЕДСТВА ПОИСКА ГЛОБАЛЬНО-

ОПТИМАЛЬНЫХ РЕШЕНИЙ В МНОГОМЕРНЫХ

МНОГОЭКСТРЕМАЛЬНЫХ ЗАДАЧАХ

С.В. Сидоров, А.В. Сысоев, В.В. Рябов

Нижегородский государственный университет

Введение

Кафедра математического обеспечения ЭВМ факультета ВМК

Нижегородского государственного университета им. Н.И.

Лобачевского разрабатывает программный комплекс

«Абсолют Эксперт», предназначенный для решения многомерных

многоэкстремальных задач глобальной оптимизации с

функциональными ограничениями.

В настоящей работе рассматривается схема остановки и

возобновления счета в последовательной и параллельной версии

303

индексного метода [1, 2], реализованного в программной системе

“Абсолют Эксперт” [3, 5].

В рамках данной работы расширена функциональность комплекса

за счет использования различных схем распараллеливания алгоритмов.

Эффективная параллельная версия индексного метода с

множественной разверткой

Задачи оптимизации позволяют описывать многие ситуации

принятия решения. Подобные задачи часто являются вычислительно

ёмкими, многомерными, многоэкстремальными и

многокритериальными. Как результат, алгоритмы, предназначенные

для решения таких задач, требуют немало времени (дни, недели,

месяцы) для отыскания оптимальных решений. Таким образом,

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

оптимальных решений таких задач. При этом

уменьшения времени

поиска можно добиться за счет использования нескольких

вычислительных узлов. Для эффективной организации вычислений на

многопроцессорных высокопроизводительных вычислительных

системах при решении задач оптимизации необходимо наличие

параллельных методов поиска глобально-оптимальных решений.

Авторами была выполнена реализация параллельной версии

индексного метода с множественными развертками, основанная на

равномерном распределении интервала поиска между

вычислительными процессами. При этом каждый процесс на каждой

итерации выбирает следующую точку испытания в своем интервале

поиска.

В предположении, что вычисление значений функционалов в

различных точках может занимать существенно различное время, в

реализации использованы неблокирующие посылки MPI. Схема

обмена данными между процессами асинхронная.

Предположение о длительном вычислении функционалов

позволяет разбить пересылки данных

на каждой итерации на два шага:

 рассылка новой точки испытания с признаком блокирования

остальным, что гарантирует процессам одновременное

проведение испытаний в разных точках и не даёт использовать

интервалы, на одном из концов которых ещё не вычислено

значение функции;

 рассылка результатов испытания в новой точке и её

разблокирование.

304

L-1 L

…

L-2

Рис. 1. Схема отображения многомерной точки на множество одномерных

Выполнение поиска глобально-оптимального решения сложных

производственных задач может длиться от нескольких часов до суток

ввиду вычислительной сложности функционалов, входящих в задачу.

При этом возникает необходимость остановки и возобновления

вычислений.

Вместе с остановкой алгоритма сохраняется вся накопленная

информация о проведённых испытаниях, а также исходные данные о

решаемой задаче. Все данные после

остановки счёта располагаются во

внешней памяти и могут быть перенесены с одного вычислительного

узла на другой с возможностью продолжения счёта на нем. При

возобновлении поиска происходит загрузка всех данных о решаемой

задаче с возможным некоторым изменением параметров задачи.

Необходимость остановки счета обусловлена рядом факторов.

Наличие такой возможности влияет на гибкость

использования

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

прикладных задач прекратить в определенный момент счет с

получением текущей оценки глобального минимума. В дальнейшем

можно использовать сохранённую поисковую информацию и

продолжить нахождение ещё более точной оценки.

Возможность остановки и возобновления счета серьезно

расширяет функциональность системы, позволяя начать вычисления

на одном узле, потом

при необходимости прекратить счёт с

сохранением всей накопленной информации, и затем продолжить

вычисления на этом или другом узле через любой промежуток

времени. Таким образом, в случае окончания квоты на использование

вычислительных ресурсов можно прекратить вычисления и

продолжить их при появлении таких ресурсов.

305

В рамках данной работы выполнена реализация остановки и

возобновления вычислений для четырёх алгоритмов глобального

поиска.

Литература

1. Гергель В.П., Сысоев А.В. О реализации параллельной версии

индексного метода поиска глобально-оптимальных решений в

многомерных задачах оптимизации в программном комплексе

“Абсолют Эксперт” // Труды всероссийской конференции

“Научный сервис в сети Интернет: технологии параллельного

программирования”, 2006, с. 115-118.

Стронгин Р.Г. Поиск глобального оптимума. Математика и

кибернетика. – Знание, 2. 1990.

Сысоев А.В., Сидоров С.В. Использование чисел расширенной

точности в реализации индексного метода поиска глобально-

оптимальных решений // Материалы пятого Международного

научно-практического семинара “Высокопроизводительные

параллельные вычисления на кластерных системах”. 2005.

Стр. 208-215.

Strongin R.G., Sergeev Ya.D. Global optimization with non-

convex constraints: Sequential and parallel algorithms. – Kluwer

Academic Publisher. Dordrecht. 2000.

Sysoyev A.V. Program system of parallel computations for solving

the tasks of global-optimum choice // VI International Congress on

Mathematical Modeling/Book of abstracts. 2004. p. 62.

ИСПОЛЬЗОВАНИЕ ТЕХНОЛОГИИ INFINIBAND ПРИ

ПОСТРОЕНИИ КЛАСТЕРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

А.Н. Суслов

Рязанский государственный радиотехнический университет

Кластеры - это мощное, масштабируемое, экономически

эффективное решение для приложений, требующих больших объемов

вычислений.

Вычислительный кластер можно определить как совокупность

компьютеров, объединенных в рамках некоторой сети для решения

одной задачи. Архитектура системы определяется задачей, для

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

306

компьютеры, разнообразные по архитектуре и мощности, а также с

разнообразным установленным программным обеспечением. Одним из

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

является коммуникационная среда, выбор которой определяется

свойствами решаемых задач.

На сегодняшний момент доступны несколько стандартов сетевого

оборудования, обладающих высокой скоростью передачи данных и

низкой латентностью. К их числу можно

отнести такие технологии,

как SCI (Scalable Coherent Interface), Fast Ethernet, Gigabit Ethernet,

Myrinet 2000, QSW (Quadrics Supercomputers World), InfiniBand,

каждая из которых имеет свои преимущества и недостатки.

Одной из наиболее быстро развивающихся технологий является

InfiniBand, поддерживаемая рядом ведущих мировых производителей,

таких как Intel, IBM, Cisco, Sun, Qlogic и др.

InfiniBand - это стандарт, описывающий новую архитектуру и

спецификации на передачу данных между процессорами и

интеллектуальными устройствами ввода/вывода. InfiniBand заменяет в

серверах шину PCI, обещая тем самым большую пропускную

способность, более распределенную структуру и большую гибкость в

архитектуре серверов. Она предлагает гораздо более широкие

возможности и высокую производительность, чем PCI. Хотя PCI

достаточно надежна и обеспечивает приемлемую скорость, тем не

менее, она во многом уступает канальной архитектуре InfiniBand.

С помощью InfiniBand связь с удаленными модулями хранения,

сетевые функции

и соединения между серверами будут

осуществляться за счет подключения всех устройств через

центральную, унифицированную структуру коммутаторов и каналов

InfiniBand. Именно таким образом InfiniBand решает «вопросы

расстояния», возникающие при использовании архитектур на базе

шин, таких как PCI, при которых расстояние между модулем

ввода/вывода и материнской платой с процессором не может

превышать нескольких дюймов

или даже сантиметров. Канальная

архитектура InfiniBand позволяет размещать устройства ввода/вывода

на расстоянии до 17 м от сервера с помощью медной проводки, а также

до 300 м с помощью многомодового волоконно-оптического кабеля и

до 10 км — с помощью одномодового волокна. Данная возможность

позволит проектировщикам пересмотреть внутреннее строение

серверов, уменьшив размеры корпуса сервера, что позволит

более

307

эффективно использовать полезное пространство серверных

помещений.

Спецификация InfiniBand предусматривает наличие в канальных

адаптерах одного, четырех или 12 каналов, в зависимости от

требуемого уровня производительности. Реализуемая ими скорость

при двунаправленной передаче данных — 500 Мбит/с, 2 и 6 Гбит/с

соответственно.

InfiniBand использует расширенную адресацию, поддерживаемую

IPv6. В заголовках InfiniBand Global Route Header пересылаемые

пакеты содержат адреса отправителя (HCA) и получателя (TCA), что

позволяет коммутаторам InfiniBand сразу направлять пакет на нужное

устройство.

Для обеспечения устойчивости к сбоям коммутаторы InfiniBand

можно каскадировать. При использовании шин PCI серверы всегда

имели критически уязвимую точку, а поскольку InfiniBand

поддерживает более распределенную конструкцию и канальную

архитектуру, можно организовать автоматическое резервное

копирование и восстановление после сбоя, чего нельзя было сделать в

системах с шинами

. Боб Пирсон, вице-президент компании Vieo,

считает, что InfiniBand позволит разработчикам создавать более

быстрое программное обеспечение, поскольку они смогут получить

приложения, способные напрямую обращаться к устройствам

ввода/вывода вместо того, чтобы вовлекать в эти операции

центральный процессор.

РЕАЛИЗАЦИЯ ТИПОВЫХ АЛГОРИТМОВ ОБРАБОТКИ

ИЗОБРАЖЕНИЙ НА МУЛЬТИЯДЕРНЫХ ПРОЦЕССОРАХ

В.А. Фурсов, С.Б. Попов, И.И. Доровских

Самарский государственный аэрокосмический университет имени

академика С.П. Королева (СГАУ),

Институт систем обработки изображений Российской академии

наук (ИСОИ РАН), Самара

Постановка задачи

Одним из следствий прогресса в развитии технических средств

регистрации изображений является быстрый рост их размеров.

Связано это в первую очередь с возрастанием требований к

пространственному разрешению систем видеонаблюдения. Кроме

308

того, есть области (геоинформатика, аэрокосмический мониторинг

Земли), где традиционно используются большеформатные

изображения.

Для улучшения качества этих изображений обычно осуществляют

их обработку с использованием как линейных, так и нелинейных

фильтров. Такая обработка особенно актуальна в ситуациях, когда

получен единственный экземпляр изображения при плохих условиях

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

должны использоваться высокопроизводительные процессоры.

В настоящее время массовое распространение получили

многоядерные процессоры, которые показывают существенное

повышение производительности на ряде задач [1]. Следует заметить,

что компании, осуществляющие тестирование производительности

процессоров, как правило, уделяют большее внимание компьютерным

играм (ориентация на домашний компьютер) или задачам,

использующим различные операции с матрицами (ориентация на

компьютер в научном

учреждении). Однако исследования

производительности графических редакторов, таких как Photoshop®,

Gimp, Digital Flash® (Retinex) и других, менее популярно.

Существующие наборы тестов включают, например, исследование

скорости конвертации фотографий (уменьшение размера). Вместе с

тем такая типичная задача, как повышение контрастности, вообще не

рассматривается.

Настоящая работа посвящена исследованию реализации

параллельных алгоритмов обработки изображений на многоядерных и

мультитредовых процессорах. Основная

цель работы – получить

сравнительные характеристики эффективности различных схем

реализации типовых алгоритмов обработки изображений, а также

оценки производительности различных типов процессоров на этих

задачах.

Типовые схемы обработки изображений

Среди схем обработки изображения выделяют [2] следующие

основные типы:

операции поэлементной обработки, формирующие значение

каждой точки результирующего изображения на основе одной

точки исходного изображения (рис. 1а);

обработка локальной окрестности или локальная обработка

скользящим окном (рис. 1б), специальным классом операций

309

над локальной окрестностью является рекурсивная обработка

локальной окрестности (рис. 1в);

глобальные операции обработки, при которых в качестве

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

изображения.

а) б) в)

Рис. 1. Схемы обработки изображения

В задачах улучшения качества изображений обычно используется

локальная обработка скользящим окном, которая реализуется с

помощью линейных и нелинейных фильтров. К линейным фильтрам

относятся фильтры с конечной импульсной характеристикой

(вычисления для текущего отсчета производятся на основании

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

опорной области конечного размера, рис. 1б) и

бесконечной

импульсной характеристикой (рис. 1в). При обработке

квазиоптимальным линейным фильтром значение функции яркости в

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

значений функции яркости входного изображения в пределах

выбранной области.

Заметим, что наиболее характерными для регистрируемых

изображений являются динамические искажения (дефокусировка, смаз

и т.п.). Кроме того, изображения могут подвергаться воздействию

как

нормальных (зернистость фотопленки, шумы радиотехнических

систем и т.п.), так и импульсных (могут вноситься цифровыми

элементами системы) помех. Для их устранения могут применяться

как линейные, так и нелинейные, например, медианные фильтры [3]. С

точки зрения вычислительной схемы реализации они соответствуют

схеме, использующей обработку локальной окрестности (рис. 1б).

Качество изображение является

неудовлетворительным, если на

нем присутствуют аддитивные и импульсные (следствие

использования цифровых систем передачи и хранения изображения)

помехи, оно дефокусировано или смазано. Для устранения такого рода

дефектов могут быть использованы типовые линейные фильтры и

медианные фильтры (подкласс нелинейных фильтров).

310

Описание экспериментов

Испытания проводились на компьютерах трех типов:

 мультитредовый – процессор Intel Pentium 2.4 GHz

MultiThread,

 двухъядерный – процессор Intel Core Duo 2.4 GHz,

 восьмиядерный - 2 четырехъядерных процессора Intel Xeon

2.0GHz.

Разработанная тестовая система имеет в основе многопоточное

приложение, написанное на Java. Количество потоков, создающихся в

системе, может варьироваться. Общее время работы системы

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

из входного файла, времени его обработки и времени записи

обработанного изображения в выходной файл (т.е. не учитывается

время

визуализации, а также время, необходимое для запуска java-

машины), и измеряется в секундах. Время обработки изображения, по

сути, представляет собой максимальное время существования нити

(потока, занимающегося обработкой).

В качестве задачи для одного потока используется либо набор

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

изображения или, в зависимости от способа распределения работы,

набора точек. Задача включает в себя: считывание значений функции

яркости в пределах выбранного окна, обработка – формирование

функции яркости выходного изображении в центре окна, запись

получившегося значения в выходное изображение. Под общей задачей

будем понимать обработку изображения в целом.

Исследовались два различных подхода к распределению общей

задачи между потоками:

декомпозиция данных – закрепление за определенным

потоком определенного набора входных данных (в нашем

случае область исходного изображения) перед началом работы

системы;

функциональная декомпозиция – каждый поток будет

получать очередную задачу самостоятельно в процессе

работы.

Функциональную декомпозицию, в свою очередь, также можно

выполнить различными способами: