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

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

361

функции

),( tXF

) с помощью, например, кодов Maple. Следуя [1]

решение уравнения (3) будем искать в виде

∑

∞

][

)|()|()(

ttttMt XMXX o

. (4)

Матрицы

)|(

описывают аберрации соответствующих

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

матриц) возможно как в аналитическом (символьном) так и в

численном виде. Согласно идеологии матричного формализма [1] для

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

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

например, в работах [1, 2]. Например, подобное вычисление можно

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

.))|(()|(,)|()()|()|(

][

111

jjj

jjjk

ttdttttt

τττττ

MMMPMM ==

∑

∫

∞

Вычисление аберрационных матриц не вызывает принципиальных

трудностей для достаточно широкого класса функций. В частности,

использование, например, кодов Reduce и Maple позволило провести

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

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

постоянной аппроксимации внешних полей.

Для численного вычисления матриц

)|(

можно

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

.C],[,)|(,)|(

,)|()(

)|(

1],[0000

knknd

kjj

kndtttt

ttt

ttd

−+

∞

===

∑

EMEM

Здесь

- единичная матрица

-го порядка. Естественно, что

решение уравнений (6), как и в случае символьных вычислений,

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

appr

. В

отличие от решения уравнений (1), мы получаем матричное

представление искомого (приближенного) оператора эволюции без

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

числа частиц. Можно заметить, что число уравнений даже в случае

аберраций высоких порядков (величина

k до 5-го или 7-го порядка)

намного меньше, чем при решении системы уравнений (1) даже в

362

случае небольшого (

1000100

) числа частиц. Таким образом, при

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

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

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

традиционных численных методов. Именно это обстоятельство

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

эволюции является более эффективным при описании эволюции

пучков частиц (т.е. ансамбля большого числа частиц).

Реализация матричного формализма

Опишем изложенный в предыдущих разделах метод более

подробно в виде следующей последовательности операций.

Вычисление матриц

)|(

для некоторых классов

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

физике пучков.

Вычисление аберрационных матриц

)|(

для некоторых

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

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

Построение баз данных из этих матриц и соответствующих

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

Построение баз данных, содержащих дополнительные

операции над операторами и матрицами, позволяющие

существенно повысить эффективность численного

моделирования (в частности, длительной эволюции

динамических систем).

Используя знания экспертов, строятся базы знаний

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

графов), позволяющие сопоставлять тем или иным

«физическим» эффектам соответствующие матрицы, как в

уравнениях движения, так и в решении.

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

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

и симметрий.

Строится пользовательский интерфейс (с использованием

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

обеспечивающий гибкое и эффективное «изъятие»

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

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

363

Естественно, что перечисленные выше этапы моделирования не

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

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

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

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

математических моделей физических объектов (соответствующих

управляющим элементам, например, таким, как мультипольные линзы,

дипольные магниты, соленоиды и т.

п.) можно ввести декомпозицию

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

которых самостоятельного (с физической точки зрения) не имеет.

Подобное представление позволяет более гибко вводить в процесс

исследования (численного моделирования) те или иные модели и

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

получил название технологии LEGO-объектов [11]. Следует заметить,

что в

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

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

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

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

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

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

которые в процессе вычислений обмениваются информацией. Укажем

основные типы потоков, возникающих в физике пучков, и опишем

характер их взаимодействия.

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

значений блочных матриц

)|(

, является основным

поскольку «поставляет» объекты, необходимые для

моделирования динамики пучка.

Поток фазового портрета пучка – предназначен для

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

(характеристик текущего множества

() ( | )tMtt

=Μo

Поток визуализации динамики пучка – позволяет реализовать

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

геометрических, топологических и других характеристик

пучка, вычисления наблюдаемых величин (огибающих и т.п.)

и их сравнения с экспериментальными данными.

Поток сил пространственного заряда – предназначен для

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

364

электромагнитного поля, порождаемого текущим

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

Поток оптимизации – предназначен для решения задач

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

программирования [4]).

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

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

(например, при использовании инвариантов, симметрий,

присущих исходной системе).

Вычислительный эксперимент

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

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

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

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

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

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

два потока: основной – поток динамики, и вспомогательный – поток

визуализации. Каждый из потоков был

реализован на отдельных

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

кластере, состоящем из пяти 2-процессорных машин (процессор Xeon,

1.8 MHz), поток визуализации – на кластере, состоящем также из пяти

подобных машин. Процесс синхронизации данных в простейшем

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

односторонним: от потока динамики к потоку визуализации. По сути

дела в определенные моменты времени (определяемые

«местоположением» на опорной траектории пучка) информация о

характеристиках пропагатора «сбрасывалась» в поток визуализации и

там обрабатывалась.

Основное распараллеливание осуществлялось внутри указанных

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

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

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

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

рассматривались

топологии двумерного и трехмерного тора, а также гиперкуба.

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

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

матричной информации о фазовых состояниях частиц, входящих в

состав пучка. Число частиц варьировалось от

до

. Временные

365

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

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

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

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

Литература

2. Andrianov S.N. A Matrix Representation of the Lie Algebraic

Methods for Design of Nonlinear Beam Lines // AIP Conf. Proc.

1997. No 391. NY. P. 355-360.

Андрианов С.Н. Динамическое моделирование пучками

заряженных частиц. СПб: СПбГУ, 2004.

Dragt A.J. Lectures on Nonlinear Orbit Dynamics. Physics of High

Energy Particle Accelerators. AIP Conf. Proc., No 87. NY, 1982.

P. 147-313.

Andrianov S.N., Edamenko N.S. Some Problems of Optimization

Computing Process // Proc. Volume from Eleventh IFAC Int.

Workshop on Control Application of Optimization - CAO'2000,

SPb., 2000. Oxford (UK), 2000. P. 419-424.

ОПЫТ УСТАНОВКИ ПО NORDUGRID НА КЛАСТЕР

С ДВУХЪЯДЕРНЫМИ ПРОЦЕССОРАМИ

С.Н. Андрианов, А.В. Богданов, М.А. Воротынский, А.Б. Дегтярев,

Н.В. Тиц

Санкт-Петербургский государственный университет

В докладе описывается опыт установки и портирования

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

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

объединенных локальной сетью. В таблице приведены основные

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

366

АППАРАТНАЯ СОСТАВЛЯЮЩАЯ

Кол-

во

Процессор ОЗУ Диски Назначение

1 Dual Core

AMD

Opteron

Processor 270

1024

120 GB

(доступно

– 80 GB)

Сервер.

Архитектуру -

x86_64

Компьютер

8 Dual Core

AMD

Opteron

Processor 270

1024

120 GB

(доступно

– 80 GB)

Вычислительный

узел. Архитектуру

- x86_64

Сетевая карта EtherExpress Pro100 (100 Mbps)

ПРОГРАММНАЯ СОСТАВЛЯЮЩАЯ

Операционная

система

RedHat Enterprise Edition 4.0

Менеджер

ресурсов

Torque (версия 2.1.6)

Файловая

система

Все компьютеры имеют файловую систему ext3fs и NFS (Network

File System) (директории /scratch и /software со всеми

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

GRID Globus Toolkit (globus-4.0.3-0.5)

NorduGrid (nordugrid-arc-0.6.0)

Локальная сеть

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

Доступ в Интернет: сервер – прямой доступ, узлы – через сервер

В результате для работы было доступно суммарно 32

вычислительных ядра.

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

тестирования MPICH, NSF и NorduGrid применительно к выбранному

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

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

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

ядер для проведения вычислений.

Для выявления особенностей портирования

приложений была

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

двух тождественных невзаимодействующих фермионов в

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

Монте-Карло в расширенном ансамбле с настройкой балансировочных

параметров по алгоритму Ванга-Ландау. Программа была реализована

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

MPICH2.

367

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

система тестов NAS benchmark. В докладе приводятся результаты

выполнения тестов и портированного приложения. Показан эффект

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

линейного масштабирования на выбранном приложении. При помощи

системы тестов NAS benchmark исследованы особенности

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

многоуровневой кластерной архитектуре: ядро – процессор –

узел –

кластер.

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

расчетов портированного приложения. На рисунке показан рост

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

задействованных ядер на узлах кластера. В качестве числителя в

формуле для ускорения (speed up) принималось время выполнения

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

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

(при

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

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

ядрами) – нижняя линяя (красный цвет); а также при использовании

промежуточного программного обеспечения NorduGrid – верхняя

линия (синий цвет). Пунктирная линия является биссектрисой в

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

ускорение. На основании графика можно сделать заключение о

высокой

эффективности для хорошо распараллеливаемого приложения

применяемого промежуточного программного обеспечения.

368

0 5 10 15 20 25 30 35

Рис. 1

Данный кластер доступен в системе NorduGrid под именем ECO

GRID cluster SPbSU, а его состояние может быть определено при

помощи монитора NorduGrid (http://www.nordugrid.org/monitor/).

ПОТОКОВОЕ СКОРОСТНОЕ ШИФРОВАНИЕ ИНФОРМАЦИИ

И СЕАНСОВЫХ КЛЮЧЕЙ В НЕЗАЩИЩЁННЫХ КАНАЛАХ

СВЯЗИ

В.М. Денисов

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

университет

Введение

В ближайшее время появятся глобальные мобильные системы

третьего поколения с высокой пропускной способностью,

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

абонентов, но и свободный доступ в Интернет и возможности

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

соответствовать международным стандартам ITU

, это должно

ITU – (International Telecommunication Unit) – Международная Телекоммуникационная

организация, занимающаяся разработкой стандартов в структуре ISO – International

Standards Organization.

369

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

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

свойств этих систем является защищённость информации,

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

шифрования данных непосредственно в сеансе связи абонентов.

Все существующие системы передачи шифрованной информации

в сети можно разделить на 2 большие

группы:

 асимметричные, использующие 2 ключа (открытый для

шифрования и секретный для расшифрования);

 симметричные, имеющие единственный ключ.

Все существующие протоколы шифрования являются

комбинированными и работают в 2 этапа: вначале с помощью

асимметричного алгоритма формируется и передаётся ключ шифра, а

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

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

Асимметричное шифрование примерно в 1000 раз медленнее

симметричного

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

степень (примерно 1200 десятичных разрядов). По этой причине

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

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

Диффи – Хеллмана, Эль Гамаля и др. Все они слишком медленные,

чтобы обеспечить непосредственное шифрование данных.

На втором основном этапе средствами шифрования являются

продукционные

шифры, использующие быстрые симметричные

алгоритмы. Эти шифры появились достаточно давно, и в настоящее

время приняты стандарты шифрования ГОСТ 28147-89, DES-3 и AES.

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

ключом: от 112 до 256 разрядов, однако, передачу ключей они

обеспечить не могут.

Пропускную способность в десятки мегабайт в секунду

существующие системы шифрования обеспечить не могут из-за

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

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

таких систем, несмотря на их сложность и громоздкость.

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

дополнительную проблему их защиты от подмены.

370

Базовые принципы шифрования

В данной работе систематизируются базовые принципы

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

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

 производить передачу ключей и шифрование данных за один

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

алгоритмы;

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

протокола защиты передаваемых данных;

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

(ключ хранится в течение одной транзакции - это около

сек., а затем удаляется).

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

существующих и перспективных систем.

Один и тот же ключ симметричного шифрования и расшифрования

должен храниться у обоих абонентов; именно

секретность этого

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

, поскольку

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

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

оппонентам. Это так называемый

принцип Керкхофа. Все

симметричные криптографические системы, основанные на этом

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

передавать ключ в незащищённой среде. Именно это обстоятельство

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

шифрования.

В асимметричном шифре необязательно иметь один и тот же ключ

шифрования для обоих абонентов секретной связи: ситуация

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

замком, которую можно захлопнуть и

совсем без ключа, а открыть её можно только секретным ключом.

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

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

подмены ключей.

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

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

ключа для этого

шифра один и тот же специальный протокол, в

котором секретность обеспечивается вместо принципа Керкхофа

другим

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

чисел

. В результате криптостойкость и скорость шифрования