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

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

411

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

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

выполнением всех шагов алгоритма и непосредственной передачей по

мере готовности строк изображения от одной операции к другой.

В данном случае единицей разбиения служит операция,

выполняющая один шаг обработки. Все операции выполняются

параллельно. Данные передаются от одной

операции к другой по мере

готовности, т.е. после завершения обработки строки изображения на i-

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

выполнения (i+1)-ого шага. Фактически формируется поток данных

изображения, элементы которого на i-ом процессоре подвергаются

преобразованию в соответствии с алгоритмом i-ого шага и передаются

последующему процессору

для дальнейшей обработки. При этом

результаты всего процесса обработки формируются с той же

скоростью, с которой производится и ввод, но, после задержки,

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

Глобальные операции редукции. Операторы редукции, как правило,

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

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

на фрагменты. Но для определения некоторых параметров полезно

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

Глобальные операции обработки. Наиболее простым вариантом

распараллеливания для этих операций является любой вариант

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

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

обработке. Если полная репликация обрабатываемого изображения по

каким-либо причинам невозможна, то при

параллельном выполнении

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

данными между параллельно выполняющимися задачами обработки. В

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

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

заранее сделать этот выбор очень сложно.

Геометрические преобразования. Данный вид операций включает

в себя операции масштабирования и поворота, а так же нелинейного

преобразования координат общего вида. С точки зрения минимизации

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

преобразований общего вида над распределенными изображениями

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

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

412

более эффективным является одномерная декомпозиция. Причем как в

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

соответствующие фрагменты с перекрытием.

Наиболее популярным вариантом организации вычислений при

распараллеливании низкоуровневых операций на основе

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

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

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

осуществляет

декомпозицию исходных изображений и распределение

их фрагментов по задачам обработки, а также последующую сборку

результирующего изображения. В зависимости от конкретного набора

операций графа решения задачи обработки программа-менеджер для

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

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

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

производит обмен

перекрывающимися частями фрагментов

изображения на узлах обработки, если разбиение не изменяется при

переходе к следующему шагу обработки.

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

обработки изображений существенно снижается из-за наличия

следующих узких мест: канал доступа к подсистеме хранения

обрабатываемых изображений, когда задачи, обрабатывающие

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

необходимые данные,

и собственно программа-менеджер,

осуществляющая декомпозицию и распределение фрагментов по

задачам обработки, а также последующую сборку результирующего

изображения [6, 7].

Крайне желательно устранить или существенно сократить

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

изображений в виде рассылки данных исходных изображений по

компьютерам распределенной системы и последующего сбора

обработанных фрагментов в единое изображение.

Это возможно

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

распределить по компьютерам заранее, то есть хранить их там, где

выполняется обработка. Каждая программа обрабатывает тот

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

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

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

узлов, участвующих в распределенной обработке. Перспективной

413

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

изображений в настоящий момент становится сервис-ориентированная

архитектура.

Заключение

В Институте систем обработки изображений РАН ведутся работы

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

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

вычислительной среды SORCER (Service Oriented Computing

Environment), разработанной в SORCER Research Group, Texas Tech

University.

Предлагаемая в рамках этих работ концепция организации данных

в виде распределенных изображений снимает большинство из

существующих на сегодня проблем, позволяет для большинства

операций формировать

новые изображения без обмена данными

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

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

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

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

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

изображений с достаточной степенью интерактивности.

Работа поддержана грантом РФФИ № 07-07-00210.

Литература

1. D. Ballard and C. Brown. Computer Vision. Prentice Hall, 1982.

Chaudhary V., J.K. Aggarwal. Parallelism in Computer Vision: a

review. In Vipin Kumar, P.S. Gopalakrishnan, and Laveen N.

Kanal, editors, Parallel Algorithms for Machine Intelligence and

Vision, pages 271–309. Springer-Verlag, 1990.

Методы компьютерной обработки изображений. Под

редакцией В.А. Сойфера. Издание 2-ое исправленное. – М.:

Физматлит, 2003, 784 с.

R.G. Gonzales and R.E. Woods. Digital Image Processing.

Addison-Wesley, 1992.

I. Pitas. Parallel Algorithms for Digital Image Processing,

Computer Vision and Neural Networks. John Wiley&Sons, 1993.

D. Koelma, P.P. Jonker, and H.J. Sips. A software architecture for

application driven high performance image processing. In

Proceedings of SPIE Conference, vol. 3166, pages 340-351, 1997.

414

F. Serot, D. Ginhac, and J.P. Derutin. SKIPPER : A skeleton-based

programming environment for image processing applications. In

Proceedings of the Fifth International Conference on Parallel

Computing Technologies, 1999.

РЕАЛИЗАЦИЯ ПОДМНОЖЕСТВА ФУНКЦИЙ ПАКЕТА

ЛИНЕЙНОЙ АЛГЕБРЫ BLAS НА SIMD АРХИТЕКТУРЕ

ГРАФИЧЕСКОГО УСКОРИТЕЛЯ С ПОВЫШЕНИЕМ

ТОЧНОСТИ ДО ДВОЙНОЙ

В.В. Березовский, А.В. Рудалев

Поморский государственный университет имени М.В. Ломоносова,

Архангельск

Введение

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

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

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

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

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

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

физические, химические и биологические процессы и явления.

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

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

невозможно без применения параллельных вычислений. Одним из

наиболее эффективных и дешевых способов создания мощной

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

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

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

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

включенных в систему узлов, их вычислительной мощности и

производительностью коммуникационной сети связывающей узлы.

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

современных технологий и высокой стоимостью

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

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

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

оправданно. Согласно закону Амдала рост производительности

системы не может быть линейным

в зависимости от количества узлов.

415

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

затраты, нелинейно увеличивающиеся с ростом числа узлов. С другой

стороны, одним из ресурсов любой современной вычислительной

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

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

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

обработке. Таким образом, полное использование этого ресурса может

позволить

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

дополнительного ее увеличения.

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

использованию графических процессоров для вычислений задач

общего назначения [1-3]. Модуль обработки графики аппаратно

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

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

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

определенного круга задач, от

двух до десятков раз большую, в

сравнении с производительностью центрального процессора. Тем не

менее, на сегодняшний день генеральной тенденцией в увеличении

вычислительной мощности систем, является увеличение количества

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

внутренние возможности систем.

Библиотека BLAS является ”промышленным” стандартом в

прикладной математике, в частности модули для решения систем

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

матриц и другие задачи линейной алгебры, реализуются с

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

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

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

технических расчетов. Ее реализация с помощью графического

ускорителя (GPU) позволяет значительно увеличить

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

. К сожалению, сегодня

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

проводить операции лишь одинарной точности.

Повышение точности

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

точности с одинарной до необходимой, поэтому он приведен ниже.

416

Рис. 1. Представление числа с плавающей точкой одинарной (вверху) и

двойной (внизу) точности (IEEE Standard 754 for Binary Floating-Point

Arithmetic)

Пусть z=xy, z,x,y – числа плавающей точки необходимой точности.

Рис.1 дает наглядное представление о структуре чисел различной

точности. Разложим их на составляющие в представлении числа с

одинарной точности. Для простоты изложения рассмотрим

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

бита

0...0

...X

E-11-e

E-22-e

E-33-e

Рис. 2. Разложение числа плавающей точки произвольной точности в сумму

чисел одинарной точности (e

, e

- число нулей перед первой единицей в

соответствующей части числа)

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

чисел одинарной точности (см. рис.2):

⎪

⎩

⎪

⎨

⎧

+++=

4321

zzzzz

yyyyy

xxxxx

(1)

417

…Y

...X

…Z

2N+1

…Y

...X

…Z

N+1

0...0

Рис.3. Произведение и сложение чисел плавающей точки (в случае сложения

должно выполняться E

)

Тогда результат произведения будет

⎪

⎩

⎪

⎨

⎧

++=

+++=

111

12212

1322313

142332414

yxz

yxyxz

yxyxyxz

yxyxyxyxz

(2)

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

мантиссами из N значащих бит, является число с мантиссой из 2N+1

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

равное N+1, а в случае суммы четырех чисел соответственно N+2. Это

и выражение (2) накладывает ограничение на возможное количество

значащих бит в разложении на

числа одинарной точности.

Следует отметить, что в случае нахождения результата

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

разложение числа в выражении (1) на шесть слагаемых одинарной

точности и, соответственно число произведений в выражении (2) будет

21, т.е. вычислительная сложность в сравнении с приведенной

удвоится.

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

одинаковой экспоненте и для его реализации, проще всего перевести

числа в большие целые с последующими их сложениями и

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

отметить что последнюю операцию требуется сделать лишь

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

частичную сумму в аккумуляторе. Алгоритмы сложения больших

целых широко освещена в литературе (см. например [4])

Тестирование

Тестирование проводилось с использованием видеокарты nVidia

GeForce EW 8800 GTS.

418

 Число арифметико-логических устройств в графическом

процессоре: 96.

 Общая память: 320 МБ.

 Программное обеспечение: CUDA Toolkit/CUDA SDK.

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

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

операции преобразования чисел с повышенной точности в числа

одинарной точности внутри GPU.

Максимальный размер тестируемой матрицы был 1000х1000.

Тестирование показало выигрыш в производительности при

умножении матриц 2-5 раз по сравнению с центральным процессором

– Intel Core 2 Duo 2.4 GHz.

Заключение

Результатом данной работы явилась демонстрация возможности

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

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

К сожалению, отсутствие возможности проведений операций двойной

точности значительно сужают круг приложений данного аппаратного

обеспечения. Тем не менее, его можно значительно расширить

используя методы повышения точности, что позволяет приблизить

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

компьютера к

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

Работа выполнена при поддержке гранта администрации

Архангельской области «Приоритетные направления развития науки в

архангельской области», 2007 г., проект № 03-3.

Литература

1. Buck I., et. al. Brook for GPUs: Stream Computing on Graphics

Hardware. SIGGRAPH (2004).

Owens J., et. al., A Survey of General-Purpose Computation on

Graphics Hardware. Eurographics 2005, State of the Art Reports,

(2005).

Göddeke D., Strzodka R. Turek S. Accelerating Double Precision

FEM Simulations with GPUs. Proceedings of ASIM 2005 - 18th

Symposium on Simulation Technique (2005).

Вельшенбах М. Криптография на Си и Си++ в действии. М.:

Издательство ТРИУМФ (2003).

419

NVIDIA CUDA Compute Unified Device Architecture,

Programming Guide. NVIDIA Corporation.

http://www.nvidia.com (2007).

СОЗДАНИЕ СИСТЕМЫ ДИНАМИЧЕСКОГО

РАЗВЕРТЫВАНИЯ КЛАСТЕРА

В.В. Березовский, И.А. Шаврин, А.В. Рудалев

Поморский государственный университет имени М.В. Ломоносова,

Архангельск

Введение

Сложность задач решаемых с помощью ЭВМ в последние

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

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

естественно-научных знаний, в которой нет острой необходимости в

проведении массивных расчетов. Такое положение привело к тому что

лимитирующим фактором в развитии многих сфер научной и

практической деятельности

является стоимость современных

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

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

системы - это создание кластера. Заманчивость этой технологии

обусловлена тем, что элементы, из которых она строится, широко

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

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

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

нормального учебного

процесса порог. Как избежать потерь

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

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

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

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

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

проблемы. С помощью технологии тонких клиентов, когда

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

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

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

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

доступном оборудовании уже была воспроизведена [1, 2] и хорошо

420

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

свойств углеродных наноструктур [3].

Целью данной работы стало построение системы, аналогичной

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

кластерной вычислительной системы с помощью сетевой загрузки

операционной системы (ОС). Это позволит подключать свободные в

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

состав

и производительность.

Описание работы

Загрузка ОС через сеть возможна благодаря сетевому протоколу

DHCP (расширенный BOOTP). Сервер DHCP, настроенный в нашей

системе разделяет все клиент-машины на зарегистрированные и нет. За

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

для авторизации в системе. Новый (освободившийся от выполнения

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

работать в составе кластера)

узел, при перезагрузке, запрашивает у

DHCP сервера образ ОС. Сервер, в свою очередь, отправляет ему образ

ядра ОС, оптимизированное под его аппаратное обеспечение и работу

в составе кластера. Узел затем подключается к сетевой файловой

системе, где он может получить необходимое ему программное

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

необходимых для работы

в составе кластера системных библиотек. А

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

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

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

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

(машины beta) запрашивает у DHCP-сервера (alpha) IP адрес.

Определяет MAC адрес beta как неизвестный.

С помощью BOOTP и TFТP beta получает ядро LINUX и

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

На beta произойдет полный тест аппаратного оборудования.

Отчет отсылается к alpha.

Получив отчет alpha регистрирует beta, закрепляя за ней

определенное ядро и настройки.

В дальнейшем, когда beta обратится к BOOTP-серверу, alpha

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

характеристики.