WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 || 3 | 4 |   ...   | 24 |

• Средства сбора статистики по использованию кластера.

• Веб-интерфейс для просмотра состояния кластеров и очередей.

• Переносимость кода – система реализована на языке Perl с отдельными элементами на языке Си.

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

Поддержка пользователей Большое внимание в работе Центра уделяется взаимодействию с пользователями и комплексной поддержке их работы. В качестве элементов такой деятельности стоит выделить:

• Подготовку справочной и методической литературы, документации для пользователей; публикация в рамках Интернет-центра Parallel.Ru.

• Оперативную поддержку пользователей по электронной почте и по телефону.

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

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

ЧИСЛЕННОЕ МОДЕЛИРОВАНИЕ ОБРАЗОВАНИЯ СПИРАЛЬНЫХ ГАЛАКТИК НА СУПЕР-ЭВМ С РАСПРЕДЕЛЕННОЙ ПАМЯТЬЮ С.М. Бахрах, А.О.Наумов РФЯЦ – ВНИИЭФ, г. Саров.

Моделируется формирование спиральных галактик из скопления звёзд, случайным образом расположенных внутри сферы. Всем звёздам сообщается одинаковая угловая скорость. Учитывается гравитационное взаимодействие каждой звезды с другой, т.е. с момента времени t = 0 решается следующая система дифференциальных уравнений r r r ri N ri - r j = - i = 1,2,K, N.

2 r r t ji ri - r j Для решения данной системы был выбран метод «с перешагиванием», учитывающий специфику выписанных уравнений:

r ri r = vi, t r r r n vi N - r nj r i -.

= t r r n n ji r i - r j Алгоритм решения задачи о взаимодействии звёзд, входящих в модель галактики, удалось распараллелить на супер-ЭВМ с распределённой памятью. Трудность состояла в том, что необходимо учитывать взаимодействие каждой звезды с каждой другой. Проблема была решена за счёт поэтапного счёта и круговых обменов данными между процессорами.

Разработанный и реализованный оригинальный алгоритм распараллеливания позволил провести расчёты с различным числом звёзд (от 103 -105 ).

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

ЧИСЛЕННОЕ МОДЕЛИРОВАНИЕ РОСТА НАЧАЛЬНОГО ВОЗМУЩЕНИЯ ПРИ КОСОМ СОУДАРЕНИИ МЕТАЛЛИЧЕСКИХ ПЛАСТИН С.М.Бахрах, В.Ф.Спиридонов, Н.А.Володина РФЯЦ – ВНИИЭФ, г.Саров.

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

Сложнее обстоит дело при соударении пластин, обладающих прочностью.

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

В настоящее время подробно исследован дозвуковой режим косого соударения: Uточки контакта<Сзвука. В таких условиях нагружения в точке контакта образуется постоянно кумулятивная струя, если давление в окрестности точки соударения превышает прочность металла.

Если Сзвука

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

В одном из отделений ВНИИЭФ были проведены эксперименты по соударению пластин из алюминия. Предполагалось получить при переходе к бесструйному режиму соударения пластин практически мгновенное прекращение процесса развития возмущений. То есть, как только Uточки контакта= Uкритическая возмущения возникать не должны. Однако в экспериментах было получено, что при дальнейшем увеличении точки контакта амплитуда возмущений уменьшается монотонно. Такие данные были получены впервые.

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

Счетная сетка бралась таким образом, чтобы на длину волны приходилось порядка 20 счетных ячеек. Общее число точек 1120740=828800. Проведение таких расчетов на ЭВМ в скалярном (однопроцессорном) режиме проблематично. Поэтому расчеты проводились на многопроцессорной ЭВМ с разделенной памятью в комплексе ЛЭГАК-МП.

РАСПАРАЛЛЕЛИВАНИЕ ЯВНО-НЕЯВНОГО АЛГОРИТМА СЧЕТА ГАЗОДИНАМИКИ НА МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ С РАСПРЕДЕЛЕННОЙ ПАМЯТЬЮ С.М.Бахрах, С.В.Величко, О.Н.Кулыгина, М.В.Лучинин, В.Ф.Спиридонов РФЯЦ – ВНИИЭФ, г. Саров Использование явных разностных схем для численного решения задач газовой динамики приводит к ограничениям на шаг по времени, которые связаны с устойчивостью разностной схемы. От этого недостатка свободны безусловно устойчивые разностные схемы. Однако объём вычислений в таких схемах существенно больше нежели в явных. Поэтому в комплексе программ ЛЭГАК был реализован явнонеявный алгоритм расчета давления, в котором в целях экономии машинного времени неявная схема используется для тех точек, где шаг по времени оказался значительно меньше, чем в остальных. Данный алгоритм позволяет существенно сократить время счета задач.



Для уменьшения календарного времени счета задач в комплексе ЛЭГАК этот алгоритм был распараллелен.

На ЭВМ с распределенной памятью производилось разбиение задачи на фрагменты по столбцам.

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

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

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

Распараллеленная программа явно-неявной газодинамики тестировалась на задаче об обжатии сферической оболочки газа.

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

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

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

РАСПАРАЛЛЕЛИВАНИЕ ОБХОДА ДЕРЕВА ПОИСКА ДЛЯ РЕШЕНИЯ ЗАДАЧИ О РЮКЗАКЕ НА КЛАСТЕРНОЙ СИСТЕМЕ В.А.Беляев, Н.Е.Тимошевская Томский государственный университет Введение Задача о рюкзаке относится к классу комбинаторно-логических задач, связанных с нахождением подмножества конечного множества с заданными свойствами, причем она известна как труднорешаемая задача, лежащая в классе NP-полных задач [1]. Этот факт обусловил возможность применения данной задачи в криптографии для создания криптосистем с открытым ключом [2]. Необходимость решения задачи о рюкзаке возникает при попытке вскрытия криптосистемы c открытым ключом рюкзачного типа, а также при анализе её стойкости.

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

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

Пусть заданы натуральное число и некоторое множество A={a1, a2, …, an} из n натуральных чисел. Найти все подмножества множества А, если таковые существуют, сумма элементов в которых в точности равна. Такие подмножества будем называть -совместимыми.

Предполагается, что элементы в множестве A упорядочены некоторым образом, так что наряду с множеством A будем использовать обозначение вектор A=(a1, a2, …, an), называемый в дальнейшем рюкзачным вектором.

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

Шаги расширения и возврата могут быть наглядно представлены с помощью дерева поиска, которое строится следующим образом. Вершинам дерева сопоставляются подмножества множества А, а ребрам – его элементы. Корню дерева (вершине нулевого яруса) ставится в соответствие само множество А. Пусть построено i ярусов дерева поиска.

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

Изложенный выше алгоритм перечисления всех -совместимых подмножеств множества А можно представить в виде специальной процедуры обхода дерева, которая состоит из двух операций – операции спуска (переход с i-го яруса на i+1), соответствующей расширению строящегося множества, и операции подъема, соответствующей шагу возврата. Данная процедура обеспечивает левый обход дерева в глубину. Если сумма элементов, сопоставленных ребрам пути, ведущего от корня к концевой вершине, в точности равна, то эти элементы образуют -совместимое множество.

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





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

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

• обмен информацией между процессами должен быть минимальным.

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

в соответствующем дереве выделяется поддерево, обход которого будет выполняться подключенным процессом.

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

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

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

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

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

Литература 1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.

2. Саломаа А. Криптография с открытым ключом / Пер. с англ.

М.:Мир,1989. 264с.

3. Агибалов Г. П., Беляев В. А. Технология решения комбинаторнологических задач методом сокращённого обхода дерева поиска.

Томск: Изд-во Томского ун-та, 1981. 125 с.

РАСПАРАЛЛЕЛИВАНИЕ СЧЕТА ПО ПРОГРАММЕ ДМК НА МНОГОПРОЦЕССОРНЫХ МАШИНАХ С ОБЩЕЙ ПАМЯТЬЮ С ИСПОЛЬЗОВАНИЕМ ИНТЕРФЕЙСА OPENMP А.А. Воропинов, В.Н. Мотлохов, В.В. Рассказова РФЯЦ – ВНИИЭФ, г. Саров Краткое описание комплекса программ ДМК Комплекс программ ДМК предназначен для решения задач газодинамики с учетом процессов упругопластики и теплопроводности на регулярных и нерегулярных многоугольных сетках в лагранжевой постановке. Для предотвращения возможных перехлестов в процессе решения задач применяется оригинальный способ локальной коррекции счетной сетки, основанный на механизме упругого соударения.

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

Преимущества OpenMP перед моделью с передачей сообщений Преимущества OpenMP:

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

• эффективное использование преимуществ общей памяти;

Pages:     | 1 || 3 | 4 |   ...   | 24 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.