Якобовский М.В. Распределительные системы и сети

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

- 81 -

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

частей по геометрическому принципу - разрезанием графа, изобра-

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

плохие результаты. Несложно разбить вершины графа на примерно

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

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

что уменьшает общее число ребер между группами .

Рис. 50. Фрагмент нерегулярной сетки

Для графов небольшого объема существуют достаточно хоро-

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

тральный - будет рассмотрен ниже.

Для разбиения графов большого размера хорошо зарекомендо-

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

вершин графа на требуемые группы осуществляется в несколько эта-

пов:

1 - рекурсивное огрубление графа - уменьшение его размера,

2 - рекурсивная бисекция

вершин графа на заданное число

групп,

3 - рекурсивное разукрупнение графа и локальное уточнение

разбиения промежуточных графов.

Рекурсивное огрубление графа

Для уменьшения размера графа (уменьшения числа входящих в

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

его огрубления. Полученный в результате первого огрубления умень-

Бисекция графа - разбиение графа на две части.

- 82 -

шенный граф можно, в свою очередь, снова уменьшить. Построенная

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

сколь угодно малого размера.

Алгоритм огру бле ния графа может выглядеть сле дующим образом:

1 - выбрать некоторое множество ребер графа таким образом,

чтобы никакие два ребра не имели общих вершин (рис. 51);

2 - "стянуть" пары вершин, соединенные выбранными ребрами,

заменив каждую пару вершин одной. Соседями полученной

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

ее вес - сумме весов исходных вершин, веса ребер - сумме ве-

сов объединяемых ребер;

Рис. 51. Огрубление графа из 11 вершин до графа из 7 вершин

Рекурсивная бисекция

Для разбиения графа размером n (содержащего n вершин) на

произвольное число частей k можно использовать рекурсивную про-

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

дит следующим образом:

7.1.

bisect(

graf

(n),k1,k2)

7.2.

{

7.3.

kkk

nnn

112

++−

=−

()

7.4.

if(k

>1) bisect(

graf

)

7.5.

else сформирована часть графа размером k

7.6.

if(k

>1) bisect(

graf

)

7.7.

else сформирована часть графа размером k2

7.8.

}

Листинг 7. Алгоритм рекурсивной бисекции

- 83 -

Обратившись к этой процедуре с помощью вызова

bisect(

graf

(n),

) мы получим требуемое разбиение. Нетрудно ви-

деть, что если k четно (k

), граф разбивается на очередном шаге

на две равные части, в противном случае (k=(k

+1)+k

) граф разбива-

ется на две части в пропорции

. Пример разбиения графа из 100

вершин на 7 част ей примерно одинакового размера приведен на рис. 52.

100

4 / 3

2 / 2

2 / 1

1428

1 / 1

14 1414151415

Рис. 52. Бинарное дерево разрезов

Спект ральный алгоритм

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

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

группы, были примерно равны, а вес разрезанных ребер был минима-

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

графа имеют разные веса. Многочисленные эксперименты показали,

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

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

Рассмотрим (без доказательства) основную идею метода.

Пусть дан граф G=(N,E), где N - множество вершин графа, E -

множество его ребер, e

- веса ребер. Поставим в соответствие графу

G, не содержащему петель и кратных ребер, матрицу

()( )

aGA

, назы-

ваемую Лапласианом графа G, такую, что

()

Ekikiaa

kiik

∉≠==

,,0

;

()

Ekikieaa

kikiik

∈≠−==

;

∑

≠

∈−=

ikii

Nkiaa ,,

- 84 -

Вычислим a(G) - второй наименьший собственный вектор A(G).

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

шины графа G в соответствии с координатами вектора a(G) и разде-

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

наты, соответственно.

Наиболее трудоемким этапом при применении этого метода яв-

ляется поиск собственных векторов матрицы A(G), что ограничивает

размер разрезаемого графа.

Этап локального уточнения

После того, как огрубленный граф небольшого размера разбит

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

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

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

графа они будут входить. Естественным представляется поместить по-

лученные при разбиении вершины в ту же группу, в которую входила

разбиваемая вершина. Для улучшения качества разбиения следует по-

сле очередного шага восстановления графа выполнить процедуру ло-

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

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

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

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

ления вершин по группам. Поскольку рассматриваются только еди-

ничные переносы вершин, общее их число пропорционально произве-

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

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

• при каждом уточняющем шаге каждая вершина переносится

из одного набора в другой не более одного раза;

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

го числа, например при оптимизации графов с числом вер-

шин < 5000 можно ограничиться 500 перемещениями.

Примеры разбиения нерегулярного графа, содержащего 75790

точек и 226300 ребер на 32 части в соответствии с исходной нумера-

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

ритмом, приведены на рис. 53, 54, а данные о разрезанных ребрах - в

таблице 5.

Таблица 5

Разбиение графа

Число разрезанных ребер

Число

процессоров

при начальном

разбиении

при спектральном

разбиении

Во сколько раз

уменьшилось

8 12406 2664 4.7

12 16553 3109 5.3

32 34612 5474 6.3

- 85 -

Рис. 53. Разбиение на 32 части, в соот-

ветствии с исходной нумера-

цией вершин

Рис. 54. Спектральное разбиение на 32

части

Тема 8. Визуализация в распределенных вычислитель-

ных системах

Быстрое развитие многопроцессорной вычислительной тех-

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

лительных систем традиционной архитектуры. Речь идет о факторах,

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

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

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

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

тем самым сдерживая их дальнейшее развитие.

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

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

традиционно отмечают сложность адаптации последовательных алго-

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

ной памятью в особенности. Хорошо известно, что множество тради-

ционных алгоритмов не имеют эффективных параллельных аналогов.

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

сконцентрированы на поиске и изучении новых подходов к построе-

нию параллельных алгоритмов. Здесь и алгоритмы, специфичные для

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

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

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

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

круга.

В качестве следующего препятствия на пути эффективного

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

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

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

- 86 -

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

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

успехи в решении отмеченных задач, типичный коэффициент инте-

гральной загрузки большинства систем массового параллелизма со-

ставляет по разным оценкам всего от 10% до 3%. И это несмотря на

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

(часто более 90%) коэффициент распараллеливания при решении мно-

гих задач.

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

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

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

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

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

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

администратор многопроцессорного комплекса. Первое приводит к

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

тива разработчиков к новой ситуации - процесс, занимающий не один

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

ям вычислительной системы, даже в условиях наличия достаточного

набора задач, способных в принципе обеспечить близкую к 100% за-

грузку системы - служба системного администратора просто не в со-

стоянии обеспечить эффективную дисциплину запуска задач без соот-

ветствующего системного обеспечения, а оно отсутствует практиче-

ски всегда. Вероятно, пройдет заметное время, прежде чем многопро-

цессорные системы станут стандартом де-факто и появятся надежные

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

средствами управления.

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

ния, обработки и визуализации больших объемов данных, неизбежно

сопровождающих проводимые масштабные вычислительные экспери-

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

во всех исследовательских центрах, обладающих техникой нетрадици-

онный архитектуры.

Рассмотрим в качестве примера задачу визуализации резуль-

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

движущихся со сверхзвуковыми скоростями, а именно обтекание не-

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

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

щены самолеты и ракеты, заглублены в корпус аппарата. Простой мо-

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

прямоугольной двумерной полости вязким потоком (рис. 57). Данная

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

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

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

- 87 -

Качество визуализации играет определяющую роль при изу-

чении и интерпретации численных результатов. Использование при

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

жащие результаты вычислений, достигают значительных размеров

(уже при использовании всего лишь 6 процессоров их размер состав-

ляет десятки мегабайт). Определенно, точность вычислений (а следо-

вательно, и размер файлов) ограничивается только скоростью, с кото-

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

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

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

этому в самом скором времени стоит ожидать значительного увеличе-

ния объема файлов с результатами вычислений. Это предъявляет

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

дит к появлению новых методов обработки информации.

Сложность визуализации данных большого объема опреде-

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

• оперативной памяти и вычислительной мощности последователь-

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

ния;

• разрешение устройств вывода данных уже не соответствует объему

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

узлов сетки могут попадать в одну точку (pixel) экрана, полностью

лишая исследователя возможности увидеть что-либо в областях

сгущения сетки;

• наборы данных, порождаемые при решении задач, описываемых

большим числом пространственных функций (например задач хи-

мической кинетики, описывающих взаимодействие десятков хими-

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

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

дельного файла значительно затрудняет функционирование файло-

вой системы (из-за очень большого числа файлов) и, несмотря на

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

практически невозможной;

• проблема снижения трафика (объема данных, передаваемых между

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

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

вся работа с многопроцессорными системами осуществляется че-

рез локальную и глобальную сети.

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

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

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

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

- 88 -

Технология клиент/сервер

Современные требования к программам, интерактивно взаи-

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

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

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

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

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

В связи с этим разумно использовать параллельные системы не только

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

Естественным будет построение системы визуализации данных на ос-

нове перспективной и популярной в последнее время технологии кли-

ент/сервер (рис. 55). Сервер запускается на мощной многопроцессор-

ной системе и обслуживает многих клиентов, работающих на своих

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

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

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

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

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

сывают формируемое на экране изображение, их объем может быть

сравнительно небольшим. Как будет показано ниже (рис. 56), этот

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

файла и величины изучаемого фрагмента.

Мощные вычислительные системы работают, как правило,

под управлением операционной системы, совместимой с Unix, графи-

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

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

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

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

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

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

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

ютера пользователя? Но эффективность такого решения невелика, так

как пропускная способность сети ограничена, потребности в ней очень

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

объем графической информации. Как правило, этого можно избежать.

Например, зачем передавать изображения векторов, когда можно пе-

редать только их положение и координаты (объем передаваемых по

сети данных уменьшается при этом на несколько порядков). Совре-

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

стры, чтобы обеспечить передачу большого объема данных за прием-

лемое время, так что сокращение объемов передаваемой информации

очень важно.

- 89 -

Клиент Сервер

Пользователь

Интерфейс

Ядро

Виртуальный

сервер

Сетевой интерфейс

(Windows Sockets)

Сетевой интерфейс

(Berkeley Sockets)

Сервер

Ожидание

зап

оса

Сервер

Работа

с клиентом

Диск

Рис. 55. Структура системы визуализации

Подход на основе технологии клиент/сервер имеет еще мно-

го важных преимуществ. В частности, переносимость. Парк вычисли-

тельных систем обновляется очень быстро, все время появляются но-

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

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

ное программное обеспечение. Облегчить этот процесс призваны

стандарты на программный интерфейс и возможности операционной

системы. Но всегда существуют накладки и несоответствия, особенно

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

можности системы стандартов не существует вообще. В частности,

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

ческой подсистемы. В то время как поддержка математики и сетевые

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

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

сти, переносить очень легко - зачастую достаточно просто заново

скомпилировать программу на новой системе. При этом вся графиче-

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

изменений с новым сервером, работающим на новой системе.

- 90 -

Вторым важным преимуществом технологии клиент/сервер

является универсальность. В последнее время для персональных ком-

пьютеров появилось много популярных операционных систем и обо-

лочек - например, OS/2, Windows, Windows ‘95, Windows NT, Unix.

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

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

нет единого стандарта. Приложения, созданные для одной из этих

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

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

Под каждую из этих операционных систем можно написать свою кли-

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

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

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

ноуловимые ошибки. При этом каждый пользователь сможет анализи-

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

онной системе.

Третьим преимуществом технологии клиент/сервер является

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

большой популярностью пользуются не только локальные компью-

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

телем такой сети является Internet. Пользователи имеют возможность,

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

ным системам. Как уже было отмечено, файлы с данными моделиро-

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

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

неудобно и требует большого количества ресурсов. При проведении

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

хранятся на нем, а исследователь сможет с помощью технологии кли-

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

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

ра и ресурсы глобальной сети.

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

при визуализации больших объемов данных в последнюю очередь

преследует своей целью уменьшение времени построения изображе-

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

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

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

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

скольку затраты на распределение исходных данных между процессо-

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

формирование изображения. Но если объем данных превышает объем

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

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

бежно.