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

На правах рукописи

АНДРЕЕВ ВЯЧЕСЛАВ ВЕНИАМИНОВИЧ УДК 519.6 : 004.272:2

ОПТИМИЗАЦИЯ ПРОИЗВОДИТЕЛЬНОСТИ МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ ПРИ РЕШЕНИИ ЗАДАЧ МЕТОДОМ МОЛЕКУЛЯРНОЙ ДИНАМИКИ

Специальность 05.13.18 - Математическое моделирование, Численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических ияук

оозиьэо ии

Ижевск - 2007

003066130

Работа выполнена в УрО РАН Институт прикладной механики

Научный руководитель Липанов Алексей Матвеевич

Академик РАН, доктор технических наук, профессор

Официальные оппоненты: Тененев Валентин Алексеевич

доктор физико-математических наук, профессор (ИжГТУ)

Якобовский Михаил Владимирович

доктор физико-математических наук, институт Математического Моделирования РАН

Ведущая организация: Институт математики и механики УрО РАН

Защита диссертации состоится 19 октября 2007 г. В 16.00 часов на заседании диссертационного совета Д 212.065.04 в ГОУ ВПО Ижевском государственном техническом университете по адресу: 426069, Ижевск, ул. Студенческая, 7, корп. 1, ауд. 4.

Отзыв на автореферат, заверенный гербовой печатью, Просим, выслать по указанному адресу.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО ИжГТУ Автореферат разослан " '{Л "_& 2007 г.

Ученый секретарь диссертационного совета

Доктор технических наук, профессор

Бендерский Б.Я.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы.

Моделирование физических процессов методом молекулярной динамики (ММД) очень широко используется сегодня в самых различных областях научных исследований. Применение метода молекулярной динамики постоянно расширяется, оказывая все больше влияние на развитие научных исследований в самых различных областях знаний. Основным фактором, сдерживающим все более широкое использование ММД, является недостаточная производительность компьютеров и недостаточная эффективность алгоритмов и программ. Разработанные на сегодняшний день методы построения параллельных алгоритмов для решения задач ММД метод декомпозиции атомов, метод декомпозиции пространства и метод декомпозиции силы не позволяют построить достаточно эффективные и быстродействующие программы. Все три метода не эффективны для расчетов с использованием многочастичных потенциалов взаимодействия. Тогда как в настоящее время при постоянном расширении областей использования ММД все чаще ощущается необходимость в получении более качественных результатов моделирования, которое связано с использованием многочастичных потенциалов межатомного взаимодействия.

Разработке и исследованию методов параллельной обработки для параллельных алгоритмов метода молекулярной динамики, параллельных алгоритмов и программ уделено большое внимание в работах отечественных и зарубежных ученых Smith W., Plimpton S., Lomdahl P.S., Fincham D., Beazley, Brown D., Tamayo P., Scott W., Фадеева B.H., ФадеевД.К., Самофалов К.Г., Луцкий Г.М., Шихев К.Н., Вальковский В.Е., Котов А.Г., Марчук H.H., Головкин Б.А., Евреинов Э.В., Прангишвили И.В., и др.

Однако достигнутые в настоящее время результаты не решают проблему разработки эффективных методов параллельной обработки для ММД и разработку параллельных программ ММД для многопроцессорных вычислительных систем (МВС) обеспечивающих эффективное использование и линейный рост производительности МВС при решении задач ММД. В настоящий момент с активным использованием ММД в таких областях как биология, нанотехнология и разработка наноматериалов потребность в больших объемах вычислений ММД многократно возросла. Широкое использование многопроцессорных вычислительных систем в научных исследованиях сделало актуальной задачу разработки эффективных методов построения параллельных алгоритмов и программ для расчета задач ММД содержащих миллионы атомов и использующих многочастичные потенциалы межатомного взаимодействия.

Целью работы является разработка метода параллельной обработки информации, позволяющего проектирование параллельных алгоритмов для решения задач методом молекулярной динамики, обеспечивающих эффективное использование ресурсов МВС и линейное увеличение

производительности МВС при использовании двух частичных и многочастичных потенциалов межатомного взаимодействия.

Для достижения поставленной цели в работе решаются следующие задачи:

- разработка метода анализа параллельных процессов возникающих при решении задачи ММД на многопроцессорных вычислительных системах, обеспечивающего полное и объективное описание процесса параллельной обработки и выявляющего все существенные характеристики используемого параллельного алгоритма;

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

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

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

- разработка технологии построения модели и создание программного обеспечения для построения, редактирования и отображения процесса построения Зх мерных моделей:

- разработка метода параллельной обработки (метода декомпозиции времени), обеспечивающего построения параллельных алгоритмов ММД, позволяющих эффективное использование ресурсов многопроцессорных вычислительных систем;

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

Объектом исследования являются метод молекулярной динамики, методы параллельной обработки, используемые в методе молекулярной динамики, параллельные алгоритмы для решения задач методом молекулярной динамики, методы организации межпроцессорного обмена в МВС при решении задач методом молекулярной динамики.

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

Методы исследования. В работе применялись теоретические и экспериментальные методы исследования.

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

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

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

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

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

На защиту выносятся результаты разработки и исследования методов параллельной обработки для решении задач методом молекулярной динамики, параллельных алгоритмов ММД, результатов практической реализации этих методов и алгоритмов для метода молекулярной динамики, в том числе:

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

- параллельные алгоритмы и программы для решения задач методом молекулярной динамики, использующие метод декомпозиции времени для организации параллельной обработки и обеспечивающие эффективное использование ресурсов МВС и линейный рост производительности МВС при увеличении количества процессоров участвующих в решении задачи;

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

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

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

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

- разработаны параллельные алгоритмы и программы для метода молекулярной динамики, использующие для параллельной обработки метод декомпозиции времени и обеспечивающие эффективное использование ресурсов МВС (до 95% и более) и линейное нарастание производительности МВС при увеличении количества процессоров участвующих в расчете задачи;

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

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

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

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

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

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

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

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

Разработана и протестирована программа для решения задач методом молекулярной динамики, использующая метод декомпозиции времени для организации параллельных вычислений, обеспечивающая эффективное использование МВС (более 95%) и имеющая линейный рост производительности при увеличении количества процессоров участвующих в решении задачи.

Реализация работы состоит в выполнении Международного контракта между Академией Наук СССР (ФТИ УрО г. Ижевск) и Академией наук Венгерской республики (Институт САМАЛК г. Будапешт).

Апробация работы

Основные результаты диссертационной работы и ее отдельные части докладывались и были представлены:

- Институт математики и механики УрО АНСССР Свердловск 1988 год «Проблемно-ориентированные многопроцессорные вычислительные системы»,

- Институт САМАЛК г. Будапешт Академия наук Венгерской республики 1989 год, «Параллельные алгоритмы и программы»,

- Институт прикладной логики г. Будапешт, 1990 год «Параллельные алгоритмы и программы»,

- Международной выставке СОМТЕХ г. Будапешт 1990 год, «Параллельные компьютеры»,

- Международная выставка г. Дебрецен Венгерская республика 1990 год, «Моделирование физических процессов»,

- Международный центр теоретической физики г. Триест Италия 1994 год «Международная школа по параллельным вычислениям и их применению в физике химии и материаловедении»

Публикации. Основные материалы по теме диссертации отражены в 28 научных работах и отчетах НИР по Международным контрактам с Академией наук Венгерской республики Институт САМАЛК и Институт прикладной логики, в том числе 1 статья в списке изданий, утвержденном ВАК, 8 статей в научно-технических журналах и сборниках, 3 препринта, 16 научно-технических отчетов по НИОКР .

Объем и структура диссертационной работы. Диссертация содержит введение, 3 главы и заключение изложенные, на 139 с. машинописного текста, а также 2 приложения. В работу включены 44 рисунка, 3 таблицы и список литературы из 128 наименований. В приложении представлены акты по тестированию программы ММД использующей метод декомпозиции времени наМВС.

СОДЕРЖАНИЕ РАБОТЫ Введение содержит обоснование актуальности темы, формулировку цели и задач работы, основные положения, выносимые на защиту, и определяет содержание и методы выполнения работы.

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

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

М,-|гМ(?) (1)

Где: г = 1,2,3,ТУ-число частиц, г1 - радиус-вектор 1 частицы, М1 - масса 1 частицы,

Р,- суммарная сила, действующая на 1 частицу со стороны остальных частиц.

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

АСТ--^ И

дг,

Здесь:? = Я,^- радиус-вектор 1 частицы,

и (г)- потенциальная энергия, зависящая от взаимного расположения всех частиц.

Начальные условия задаются набором координат и скоростей частиц для момента / = 0.

{х„¥„г,,уХ1,уг,уг1 / = цу} (3)

Где: N - число частиц,

X, У, 7 - координаты частиц,

УХ,УГ,У2- проекции скоростей частиц на оси координат.

Для моделирования обычно применяются центральные парные потенциалы взаимодействия. Чаще всего потенциалы парного взаимодействия используется в форме Борна-Майера (4), Ленарда-Джонса (5), Морзе (6).

к(г) = Лехр[-/?(г-г0)/г0] (4)

«(тО = 4(Г0/Г)12-2(Г0/Г)6] (5)

и(г) = £>{ехр[-2а(г - г^ - 2ехр[~а{г - ?])]} (6) Для численного интегрирования уравнений движения обычно применяют скоростную форму алгоритма Варлета (7,8).

г,"+1 = г; + к • V," + (к1 !1тЩ" (7)

у,"+1=у," + (А/2 + (8)

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

На сегодняшний день разработано три метода параллельной обработки для построения параллельных алгоритмов ММД.

1 .Метод декомпозиции атомов Replicated-Data (RD) предложенный W. Smith. Основная идея метода декомпозиции атомов в распределении всех атомов между процессорами МВС. Каждый процессор рассчитывает только свое подмножество атомов. Пример структуры данных при построении параллельного алгоритма методом декомпозиции атомов для 8 процессоров

показан на рисунке 1. В алгоритме декомпозиции атомов каждому процессору Р назначается подматрица матрицы F, которая состоит из N/P строк матрицы. Если z индексирует процессоры от 1 до Р, то процессор Pz вычисляет элементы матрицы F в подматрице Fz, а также соответствующие подвекторы векторов х, у, z длины N/P.

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

Основным недостатком метода декомпозиции атомов является то, что для каждого процессорного узла в системе, объем памяти и время затрачиваемое на межпроцессорную связь находятся в пропорциональной зависимости от количества атомов в модели 7V и не зависят от количества используемых процессоров Р. Поэтому при большом количестве атомов в модели время затачиваемое МВС на межпроцессорную связь преобладает над временем расчета модели и алгоритм становится неэффективным.

X

1

г

4

5

6

7 S f

1

г

Y3

4

5

Ь 7 S 9

1

г

ш

4

s" 6

Vx i г

V

2.Метод декомпозиции пространства Spatial-Decomposition (SD) предложенный D. Firicham. Основная идея метода в распределении пространства модели между процессорами MB С. Каждый процессор рассчитывает только свое подпространство модели. Пример структуры данных при построении параллельного алгоритма методом декомпозиции пространства для 9 процессоров показан на рисунке 2. В алгоритме декомпозиции пространства каждому процессору Р назначается подмножество атомов

размером N/P. Назначение атомов в подмножества связаны с и к пространственным расположением в моделируемом пространстве и определяются их координатами. Все пространство модели, состоящее из N атомов, разбивается между

процессорами на подпространства размером N/P как показано на рисунке 2, Для Зх мерной модели каждый процессор должен иметь связь с 26 соседними процессорами.

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

Основным недостатком метода декомпозиции пространства является резкое снижение производительности МВС при неравномерной плотности распределения атомов в модели и увеличении радиуса потенциала межатомного взаимодействия.

3. Метод декомпозиции силы Force-Decomposition (FD) предложенный S.

J. Plimpton. Основная идея

хз

4

5 S

7 3 9

1

2

V

4 5~ 6

7

5 9

1

г

Ы

4

5~ i

7

8 9

вектор - X

X У

- so.

X

Li.

О

ш

1 2 - 3 4 - - -

5 г6 7 8 Х«Е ЕЧ« г ¿6

9 10 11 12 2 2 : i

13 14 15 16

N х Л/

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

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

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

В алгоритме декомпозиции силы каждому процессору назначается прямоугольная подматрица матрицы /■", которая состоит из Н/Р атомов. Все пространство модели, состоящее из N атомов, разбивается между процессорами

на подпространства размером N/P . Так же как в методе декомпозиции атомов процессоры связаны по принципу «каждый с каждым».

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

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

Рассмотрены и проанализированы характеристики конкретных программных систем LAMMPS, CHARMM, AMBER, NAMD предназначенных для решения задач ММД на МВС.

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

Метод декомпозиции времени. Будем рассматривать пространство модели, рассчитываемой методом молекулярной динамики, как пространство, в котором происходят процессы близкого взаимодействия, т.е. такого взаимодействия, область которого ограничена конкретным значением и размер области взаимодействия значительно меньше размера рассчитываемой модели. Рассмотрим плоскую модель, пространство которой представляет собой прямоугольник (рисунок 4). На рисунке 4 все атомы в пространстве модели имеют координаты и скорости, определяемые временным шагом h. Часть пространства модели уже рассчитана для временного шага h+1. При этом атомы в закрашенной (серым цветом) области будут иметь измененные значения данных (координат и скоростей) так как в значении данных этих атомов учтено взаимодействие их с атомами, рассчитанными для временного шага h+1, но расчет параметров этих атомов не закончен. Если область пространства модели, рассчитанная для временного шага h+1, достаточно

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

рассчитанная для временного шага h+1 может быть рассчитана для следующего временного шага h+2, не дожидаясь окончания расчета всей модели для временного шага h.

Рисунок 4. Различные области пространства модели могут быть рассчитаны в одно и тоже время для различных шагов интегрирования Ь, Ь+1, Ь+2, Ь+З, и т.д..

Аналогично если область модели, рассчитанная для временного шага Ь+2, достаточно велика, то вполне можно допустить, что часть этого пространства модели может быть рассчитана для следующего временного шага 1г+3, не дожидаясь окончания расчета модели для временного шага Ь+2 и т.д.. (рисунок 4).Рассмотрим два процессора связанные между собой каналом передачи данных. Второй процессор Р2, приняв достаточно большой объем данных от процессора Р1 рассчитанных для временного шага /г/, может начать расчет некоторых атомов для временного шага А2. Пример распределения пространства модели в памяти двух процессоров, одновременно рассчитывающих для этой модели два временных шага И1. И2, представлен на рисунке 5.

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

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

Первый вариант организации буферной зоны. Предположим, что размер пространства модели по одной из координат (2) является кратным радиусу потенциала межатомного взаимодействия. Всс пространство модели разобьем на одинаковые подпространства 5 вдоль одной из координатных осей (Щ шириной равной радиусу потенциала межатомного взаимодействия. Тогда все атомы модели, разобьются на п подмножеств 5. Атомы в подмножества будем назначать соответственно их координат. Тогда все множество атомов модели можно записать следующим образом.

' = '.Я+2 >' > '52+1 > '12+2'""'' '¿'3+1' '¡3*2 ! ■■>'&»] > '»+2'' ; '¡V )

Пусть каждый процессор Р передает параметры атомов младшего из подмножеств § следующему процессору Р+1 только тогда, когда количество принятых от предыдущего процессора Р-1 подмножеств атомов 5 я нем становится больше чем п/Р как показано на рисунке 6.

Процессор 1 Процессор 2 Процессор 3

Рисунок 6. Каждый из 3 процессоров начинает передачу данных следующему процессору только в том случае если имеет в памяти более чем п/Р подпространств S с параметрами атомов.

Радиус взаимодействия атомов, а следовательно и ширина подпространства S имеет размер исчисляемый единицами ангстрем. Устойчивость схем численного интегрирования при использовании их в ММД допускает перемещение атомов за один шаг интегрирования в пределах десятых долей среднего межатомного расстояния, что составляет десятые и сотые доли ангстрема. При такой организации параллельных вычислений, удается избежать ошибок в расчетах траектории движения атомов, которые находятся у границы области интегрирования. Так как область подпространства модели за границей области интегрирования значительно больше, чем расстояние, которое может пройти любой из атомов модели за один шаг интегрирования (рисунок б) не нарушив условий устойчивости процесса численного интегрирования.

Процессор 1 Процессор 2

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

При таком методе организации буферной зоны в каждом процессоре должно находиться не менее трех подпространства 5. Назначение подпространств показано на рисунке 7.

Второй вариант решения проблемы, состоит в расчете ширины буферной юны. Требования к ширине буферной зоны просты. Буферную зону за время расчета шага интегрирования не должен пересечь [¡и один атом модели. Поэтому будем рассчитывать ширину буферной зоны как расстояние, которое может пройти самый быстрый атом. Ширину буферной зоны будем

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

^ = 1

Где: средняя скорость самого быстрого атома модели. Л! - размер

временног о шага, С1 - коэффициент для управления шириной буферной зоны.

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

¡14

н* г д.'. не и -

->~У ■■¿ Я

t,

Р'11

нет длимых ;;-

шшШ

¿нет длины

нет д.жнык*

" '. ьз

Процессор 1 П[гоц.ес1:о)) 2 ПроцессорЭ Процессор4 Рисунок 8. Структура данных в памяти 4 процессоров рассчитывающих одновременно 4 шага интегрирования с использованием буферной зоны.

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

Основные параметры структуры модели. Для расчета модели методом декомпозиции времени, разобьем пространство модели на расчетные зоны ¿Г. Чтобы построить расчетные зоны все пространство модели разобьем трехмерной сеткой на ячейки (с). Размер ячеек выоерем таким образом, чтобы в каждой ячейке находилось не более одного атома. Рассмотрим конкретный пример модели, состоящей из 80x80x80 ячеек, разбитых на 16 одинаковых

расчетных зон 5 вдоль координатной оси 2 (рисунок 9). Ширину расчетных зон примем равной радиусу потенциала межатомного взаимодействия.

А х

Рисунок 9. Пример модели в виде параллелепипеда, разбитого на ячейки с трехмерной сеткой и поделенного на расчетные зоны — ,!|6.

Пусть радиус потенциала межатомного взаимодействия равен 5 ячейкам (рисунок 9а). Атомы назначаются в зоны расчета соответственно своим координатам. При такой разбивке модели на расчетные зоны каждый процессор начинает расчет временного шага с первой зоны расчета и рассчитывает модель последовательно по номерам расчетных зон ,,53,з4,,,Л'7,,...,Л'|6, закапчивая расчет временного шага последней 16 расчетной зоной. Затем весь никл расчетов повторяется для другого временного шага. Рассмотрим методику расчета модели на примере расчета задачи ММД на восьми процессорах.

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

Расчетные зоны обозначим символом 5. Будем различать пять типов расчетных зон Номер расчетной зоны будем указывать в

индексе перед ее типом.

- рассчитанная расчетная зона готовая к передаче в процессор Р+1.

расчетная зона, которая рассчитывается в данный момент времени, расчетная зона, расчет которой не закончен.

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

5С- расчетная зона, которая в данный момент не содержит информации о координатах и скоростях атомов.

Расчетные зоны будем записываться как множества.

Описание процессов преобразования расчетных зон, будем обозначать символом —> , Пример: 5[о

Принадлежность описания к тому или иному процессору будем обозначать символом => . Пример: Р2 => з1о —» ,чы.

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

В начальный момент вся информация о модели находится в процессоре Р1, все расчетные зоны процессора Р1 имеют тип Запишем это же самое в символьной нотации:

Р\ Оо) > > > • • • 515<;' ^б^ } (9)

Рг (^0 ) ^ {51о' 52о ' 5Зо' ■ ■ • ^Ио»^160 ) ) ^ > > ^Зо > ■ • ■ Я15о' "^бо }

Будем рассматривать интервал времени одного временного шага состоящим из множества под интервалов количество которых равно количеству расчетных зон (10).

/г = {й,ЛЛАЛЛ>........А«> (Ю)

Начало расчета зоны я1с/ процессором Р1 приводит к преобразованию типов расчетных зон —» и Л'2н, (11).

Время М, соответствует времени начала расчета первой расчетной зоны для временного шага И[ процессором Р1.

{■^^Л КлЬ К-}. (1!)

Пропустим описание вычислительных процессов для 15 под интервалов и сразу рассмотрим временной под интервал Р((/г116). Этот временной под интервал для процессора Р1 совпадает с первым под интервалом обработки следующего временного шага /¡(/г9,). В этот период времени процессор Р1 рассчитывает шестнадцатую расчетную зону для временного шага М и принимает данные для расчета временного шага 1г9. Следовательно загрузка задачи завершена. Перед началом расчета процессор Р1 принимает данные от

процессора Р%, так как процессор Р% сформировал расчетную зону Л']р для передачи.

Р2(И215) => -> {^„^Л .{¿м^зЛ {¿МО^Л .«Не ¡¡Ир

12с —* Х12 р

8 с>

/>6(/г67) => Кр,^} {^„^ЬК^Л -> ^

V ) >^4 с ~р

Ps(h83) => {.S'lp,S3o} {il0,5К^З.М* hp

Начало расчета процессором Pl нового временного шага h9. Перед началом расчета нового временного шага процессор Рх передает данные готовые к передаче sl6p оставшиеся от расчета предыдущего временного шага.

Pl(h%) => {■S'lep^zo} {516о'S2d}''S2d} slc Slp

W^b) => {^Мрэ^бо} ~> {•S'l4o>'S'l6rf}>{i154'',S16ii} —* {^lSC^iewi'^lSc ~^ Sl5p Рз(^и) => {^Пр^мЛ {■S12o'i14i/}'{'yi3wJ'S'l4i} {^BcW}>S13c Sl3p

{"^Юр'^иЛ {^Юо'^гЛЛ^Н^цЛ {^ПС^г»-}'^llc ^ "^Up

) => {5g/), 510o } —> {igo, }, {л9и,, Sl0il} —> {i9(., } ,59c —> s9p

>S»d >Std ~* {i7c',S8iv}>,57c

Pl(h7e) => {^/«J -> Ц^бЛ.^ S5p

At S3p

Как видно из процесса запуска задачи, в случае разбиения пространства модели на одинаковые расчетные зоны вдоль одной из координат установившийся синхронизированный процесс полной равномерной загрузки процессоров МВС наступает по истечении времени расчета одного временного шага.

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

Разобьем модель на расчетные зоны по координатной оси Z. Пусть радиус потенциала взаимодействия атомов равен пяти слоям ячеек с. В этом случае минимальный размер расчетной зоны sw составит пять слоев ячеек. Размер расчетных зон s0, sd, sc, sp типа примем равным одному слою ячеек с. Тогда разбивка моделируемого пространства на расчетные зоны будет иметь вид представленный на рисунке 10.

Для процессора Р{ на момент времени t0 все 80 расчетных зон будут иметь тип sd. Расчетные зоны остальных процессоров имеют тип sa и не содержат информации о координатах и скоростях атомов.

Р\ ('о ) {^ld > S2d' S2d' • ■ ■ >SS0d }

^(/0) ^ {^о'^о'^Зо'"' >■%<>}

PXi0)^{sio,s2a,s3o>... ,Si0o} Будем рассматривать интервал времени одного временного шага состоящим из множества подинтервалов, количество которых равно количеству расчетных зон наименьшего размера.

h = {hl,h2,h3,h4,h5,h6,........Д0}

Время h\ соответствует времени начала расчета первой расчетной зоны для временного шага hi процессором Рг При расчете первым процессором

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

(рисунок 10).

А X

Рисунок 10. Начало подинтервала М,, Размер расчетных зон равен

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

В используемой нами символьной нотации запись вида {s2d, sitj,SAl{, sSJ ,s6J} —> -S/2+6)» обозначает, что множество расчетных зон

{s2d,s2d,Sid,Sid,Sçn} вошло в расчетную зону (или образованно расчетную зону) Тогда процесс расчета первой расчетной зоны процессором Р[ (в

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

Всего в каждом процессоре согласно (12) должно быть не менее шести слоев ячеек. Так как рассматриваемая модель содержит 80 слоев, то вся модель может рассчитываться не более чем на 80/6=13,33-13 процессорах. Полностью синхронизированный процесс расчета при полной загрузке МВС для 13 процессоров будет иметь вид представленный ниже. Время Й173 начало расчета расчетной зоны j7. процессором Pt для временного шага h\.

тЛп> Т^ -Ьзр * Sno> iSnà ~ J ' ï^l71+771» >5 78<; } ~~^ Î^IJi? ^(7Л-78)н î J S77c STtp

Pjyhl^ ) ■—* , S12(j } —* is«7tJ } - S(7c ~~* Sblp

р№ш) StMp * i«.n S6t.tl } ~~* ÎSSk> ^61. ~~*

P5(h454)^>s4tp^s Pt{h7x) => s30/, н> s Pu(M018)=^12/,->

-^2(^^12) ^ S6p ~>S6t» S12о ■Sl2rf'{i(7+ll)wJ'S12rf} ^^вч-^)»}' Slc

Pn(hl26) s6o s6d,{su,s2d,-;s6d},{sld,s2d,...,s6d} ^ Sic

Загрузка задачи завершена процессор PI 3 приготовил зону ,?|рдля передачи в

процессор PL Так как расчетных зон больше, чем необходимо для полной загрузки процессоров, то две расчетные зоны (80-13*6=2) будут находиться в процессе расчетов в памяти первого процессора. На момент времени М73 это расчетные зоны {s19d,smd}, поэтому первому процессору при прочих равных условиях желательно иметь оперативную память большего объема.

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

Рассмотрим разбивку модели на расчетные зоны по двум координатным осям. Рассмотрим конкретный пример модели, состоящей из 80x80x80 ячеек, разбитых 16 х 16=256 на одинаковых расчетных зон S (рисунок 11). Ширину расчетных зон примем равной радиусу потенциала межатомного взаимодействия. Пусть радиус потенциала межатомного взаимодействия равен 5 ячейкам. В начальный момент времени все информация о модели находится в первом процессоре.

ДО —^ {sld's2d's3d'-- SlSd'S2S6d)

^8^0) {Я1о'Я2о'ЯЪо>— Я15о'5256О}

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

Рассмотрим сразу расчет девятнадцатой расчетной зоны процессором рх. Он совпадает с началом расчета второго временного шага И2 следующим процессором р2. Видно, что процессор р2 для начала расчета первой расчетной зоны должен был принять 18 расчетных зон (14).

-^(/о) ^ {^о'^го'^Зо'— ■$15о»,У256о}

h = {hi,h1,h3,h4ДЛ>........Лзб)

(13)

Рисунок 11. Разбивка модели на расчетные зоны по двум координатным осям Z и У. Радиус потенциала межатомного взаимодействия равен пяти слоям ячеек С,

Дальнейший анализ параллельных процессов МВС показывает, что для эффективной синхронизированной работы МВС каждый процессор должен иметь не менее 18 расчетных зон. Оптимальное количество процессоров для расчета модели представленной на рисунке 11 определяется следующим образом P^ ~s/smm. Где: Р - оптимальное количество процессоров, s-общее количество расчетных зон в модели, ,imln- минимальное количество расчетных зон для одного процессора.

Для рассматриваемого случая & m = 18 и определяется выражением (14).

Pop ~ smm = 256/18 = 14,22 я: 14

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

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

Таблица 1.

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

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

Время расчета ^ лг р 2 Р \Р) n n р + 4р Ы/Р

Время приема перед. n чзг ъл-4¥ Н/Р

Объем памяти n з^ я n1р

Колич. каналов Р 27 р 2

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

Использование многочастичных потенциалов взаимодействия.

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

Расчет временного шага при использовании буферной зоны. Расчет временного шага для процессора Рг+1 осуществляется процессором Рг во время расчета модели и передается процессору Р+1 с передачей расчетной зоны. Шаг интегрирования Дг выбирается таким образом, чтобы самый быстрый атом в модели мог пройти расстояние не более чем ширина буферной зоны по соответствующей координате.

Где: ширина буферной зоны по соответствующей координате, С2-

коэффициент, определяющий какую часть расстояния РЬи/, разрешается

проходить самому быстрому атому за один временной шаг, ^_тах- скорость самого быстрого атома модели на этом временном шаге.

Тестирование разработанной параллельной программы ММД показало, что эффективность и быстродействие полностью соответствуют предполагаемым результатам (рисунок 12 и рисунок 13).

100.00 ■

и (Я 2!

90.00 80.00

70.00 60.00

50.00 • 40.00

Я а Я и м

п

30.00 20.00

10.00 0.00

1000000 атомов

4000000 атомов

10 15 20

Количество процессоров

Рисунок 12. Зависимость потерь МВС на межпроцессорный обмен в зависимости от размера модели.

0.80

& 0.70

к

0.60

о

СЗ

0? 0.50

К

Ш а 0.40

о

о.

О. 0.30

и

Н X 0.20

Я

в о 0 10

Й

3 0.00

1000000 атомов ^

2000000 атомов

^ 4000000 атомов

___-----—•

10 15 20

Количество процессоров

Рисунок 13. Зависимость быстродействия МВС от количества процессоров и размера модели.

В приложении помещены акты тестовых испытаний разработанных параллельных программ ММД использующих метод декомпозиции времени.

ЗАКЛЮЧЕНИЕ

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

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

2. Разработаны параллельные алгоритмы и программы для ММД, использующие метод декомпозиции времени для организации параллельной обработки. Программы, использующие данный метод, позволяют эффективно использовать ресурсы многопроцессорных вычислительных систем (до 95% и более).

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

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

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

6. Разработана программа, использующая метод декомпозиции времени, для организации параллельной обработки ММД. Тестирование программы полностью подтвердило предполагаемые возможности данного метода. Производительность МВС при решении задач ММД нарастает линейно и эффективность использования ресурсов вычислительной системы может достигать 95% и более.

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

и

НАУЧНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Андреев В.В., Чудинов В.Г. Оптимизация временных характеристик метода молекулярной динамики в комплексе программ MMDYN. ВИНИТИ 2242-В. 1988. - 14 с.

2. Chudinov V.G., Andreev V.V. Atomic Mechanism of primary defect heterogeneous nucleation under radiation in FCC metals with a large stacking energy. Nucl. Mater. 1990. v.172. p.106-113.

3. Chudinov V.G., Andreev V.V. Atomic Mechanism of Solid-Liquid Transition in F.C.C. Metals with a Large Stacking-Fault Energy, phys. stat. sol. (a) 118, 1990. p.415-423

4. Chudinov V.G., Goshchitskii B.N., Moseev N.V., Andreev V.V. Kinetics of Radiation-Induced Segregation of Impurities in F.C.C. Metals at the Thermal Stage of the Collision Cascade, phys! stat. sol. (a) 119,1990. p. 437-442.

5. Chudinov V.G., Cotterill R.M.J., Andreev V.V. Possible Mechanism for the Solid-Liquid Phase Transition in H.C.P. and B.C.C. Structures, phys. stat. sol. (a) 122, 1990. p. 187-193.

6. Chudinov V.G., Cotterill R.M.J., Andreev V.V., Kinetics of the Diffuse Processes within a Cascade Region in the Sub-Threshold Stages of F.C.C. and H.C.P. Metals, phys. stat. sol. (a) 122, 1990. p. 111-120.

7. Чудинов В.Г., Андреев В.В. Атомарный механизм сегрегации тяжелых примесей в условиях облучения. ВИНИТИ 1420-В. 1989. 18 с.

8. Андреев В В. Метод классификации вычислительных процессов в многопроцессорных вычислительных системах при решении задач методом молекулярной динамики // Химическая физика и мезоскопия - 2006. - Т. 8, №2.-С. 295-303.

9. Андреев В.В. Анализ производительности многопроцессорных Вычислительных систем при решении задач методом молекулярной динамики // Химическая физика и мезоскопия - 2006. - Т. 8, №2. - С. 187-

10. Алиев A.B., Андреев В.В. Разработка параллельных алгоритмов расчета задач газовой динамики методом крупных частиц // Интеллектуальные системы в производстве.-2006.-№ 1- С.4-17.

11. Андреев В.В., Использование метода декомпозиции времени в параллельных алгоритмах метода молекулярной динамики, препринт, выпуск 1, Ижевск: Изд-во ИПМ УрО РАН, 2006. - 55 с.

12. Андреев В.В. Разработка параллельных алгоритмов для метода молекулярной динамики // Известия Тульского государственного университета. Серия «Математика. Механика. Информатика». - Тула: ТГУ, 2006. - Т. 12. - Вып. 3. - С. 7-20

Отпечатано на оборудовании Института прикладной механики УрО РАН 426067, г.Ижевск, ул. Т. Барамзиной, 34 Усл. печ. л. 1.0, Тираж 100

197.

В.В. Андреев

ОБОЗНАЧЕНИЯ

ВВЕДЕНИЕ

ГЛАВА 1. МЕТОД МОЛЕКУЛЯРНОЙ ДИНАМИКИ

1.1. Молекулярная динамика

1.2. Алгоритмы метода молекулярной динамики

1.3. Потенциалы взаимодействия

1.4. Параллельные алгоритмы ММД

1.5. Метод декомпозиции атомов

1.6. Метод декомпозиции пространства

1.7. Метод декомпозиции силы

1.8. Современные программы ММД

1.9. Выводы по главе

ГЛАВА 2. ПАРАЛЕЛЬНЫЙ АЛГОРИТМ ДЕКОМПОЗИЦИИ ВРЕМЕНИ ДЛЯ МЕТОДА МОЛЕКУЛЯРНОЙ ДИНАМИКИ

2.1. Метод декомпозиции времени

2.2. Организация вычислений в методе декомпозиции времени при разбиении пространства модели на расчетные зоны одинакового размера по одной координатной оси

2.3. Организация вычислений в методе декомпозиции времени при разбиении модели на расчетные зоны различного размера по одной координатной оси

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

2.5. Организация вычислений в методе декомпозиции времени при разбиении модели на расчетные зоны по трем координатным осям

2.6. Эффективность и быстродействие алгоритмов ММД использующих метод декомпозиции времени

2.7. Выводы по главе

ГЛАВА 3. ИСПОЛЬЗОВАНИЕ МЕТОДА ДЕКОМПОЗИЦИИ ВРЕМЕНИ ДЛЯ АЛГОРИТМОВ И ПРОГРАММ ММД

3.1. Особенности построения модели для метода декомпозиции времени

3.2. Использование много частичных потенциалов взаимодействия

3.3. Расчет временного шага

3.4. Влияние быстродействия каналов межпроцессорной связи на производительность МВС при использовании метода декомпозиции времени в ММД

3.5. Тестирование параллельного алгоритма ММД использующего метод декомпозиции времени

3.6. Тестирование надежности параллельной программы

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

3.7. Выводы по главе

Актуальность темы

Моделирование физических процессов методом молекулярной динамики (ММД) очень широко используется сегодня в самых различных областях научных исследований: разработка и изучение наноматериалов [106], изучение, белков и биологических процессов [99,101-104], динамики жидких металлов [100], радиационного воздействия [38,40,43], Липановым A.M. разрабатываются основы отработки твердых ракетных топлив [98] с использованием ММД и т.д. . При этом применение метода молекулярной динамики постоянно расширяется, оказывая все больше влияние на развитие научных исследований в самых различных областях знаний. Не смотря на то, что разработке параллельных вычислительных систем и программ уделяется большое внимание [107-125], основным фактором, сдерживающим все более широкое использование метода молекулярной динамики, является недостаточная . производительность компьютеров и недостаточная эффективность алгоритмов и программ [51, 52, 73-80, 86-90]. Разработанные на сегодняшний день методы построения параллельных алгоритмов для решения задач ММД на многопроцессорных вычислительных системах (МВС) [45-46, 48-52, 59,69,95] не позволяют построить достаточно эффективные и быстродействующие программы.

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

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

Задачи исследования:

- разработка метода анализа параллельных процессов возникающих при решении задачи ММД на многопроцессорных вычислительных системах, обеспечивающего полное и объективное описание процесса параллельной обработки и выявляющего все существенные характеристики используемого параллельного алгоритма;

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

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

- разработка1 технологии построения модели и создание программного обеспечения для построения, редактирования и отображения процесса построения Зх мерных моделей:

- разработка метода параллельной обработки (метода декомпозиции времени), обеспечивающего построения параллельных алгоритмов ММД, позволяющих эффективное использование ресурсов многопроцессорных вычислительных систем;

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

Объектом исследования являются метод молекулярной динамики, методы параллельной обработки, используемые в методе молекулярной динамики, параллельные алгоритмы для решения задач методом молекулярной динамики, методы организации межпроцессорного обмена в МВС при решении задач методом молекулярной динамики.

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

Методы исследования. В работе применялись теоретические и экспериментальные методы исследования.

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

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

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

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

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

На защиту выносятся результаты разработки и исследования методов параллельной обработки для решении задач методом молекулярной динамики, параллельных алгоритмов ММД, результатов практической реализации этих методов и алгоритмов для метода молекулярной динамики, в том числе:

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

- параллельные алгоритмы и программы для решения задач методом молекулярной динамики, использующие метод декомпозиции времени для организации параллельной обработки и обеспечивающие эффективное использование ресурсов МВС и линейный рост производительности МВС при увеличении количества процессоров участвующих в решении задачи;

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

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

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

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

- разработаны параллельные алгоритмы и программы для метода молекулярной динамики, использующие для параллельной обработки метод декомпозиции времени и обеспечивающие эффективное использование ресурсов МВС (до 95% и более) и линейное нарастание производительности МВС при увеличении количества процессоров участвующих в расчете задачи;

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

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

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

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

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

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

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

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

Разработана и протестирована программа для решения задач методом молекулярной динамики использующая метод декомпозиции времени для организации параллельных вычислений, обеспечивающая эффективное использование МВС (более 95%) и имеющая линейный рост производительности при увеличении количества процессоров участвующих в решении задачи.

Реализация работы состоит в выполнении Международного контракта между Академией Наук СССР (ФТИ УрО г. Ижевск) и Академией наук Венгерской республики (Институт САМАЛК г. Будапешт).

Апробация работы

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

• Институт математики и механики УрО АНСССР Свердловск 1988 год «Проблемно-ориентированные многопроцессорные вычислительные системы»,

• Институт САМАЛК г. Будапешт, 1989 год, «Параллельные алгоритмы и программы»,

• Институт прикладной логики г. Будапешт, 1990 год «Параллельные алгоритмы и программы»,

• Международной выставке СОМТЕХ г. Будапешт 1990 год, «Вычислительные системы в научных исследованиях»,

• Международная выставка г. Дебрецен Венгерская республика 1990 год, «Моделирование физических процессов»,

• Международный центр теоретической физики г. Триест Италия 1994 год «Международная школа по параллельным вычислениям и их применению в физике химии и материаловедении»

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

Основные материалы по теме диссертации отражены в 28 научных работах и отчетах НИР по Международным контрактам с Академией наук Венгерской республики Институт САМАЛК и Институт прикладной логики, в том числе 1 статья в списке изданий, утвержденном ВАК, 8 статей в научно-технических журналах и сборниках, 3 препринта, 16 научно-технических отчетов по НИОКР.

Объем и структура диссертационной работы

Диссертация содержит введение, 3 главы и заключение, изложенные на 139 с. машинописного текста, а также 2 приложения. В работу включены 44 рисунка, 3 таблицы и список литературы из 128 наименований. В приложении представлены акты по тестированию программы ММД использующей метод декомпозиции времени на МВС.

3.7. Выводы по главе 3

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

Алгоритм декомпозиции времени, использованный в программе метода молекулярной динамики TIME-MD для организации параллельной обработки, позволяет получать линейный рост нарастания производительности при увеличении числа процессоров, участвующих в расчете задачи. Эффективность использования вычислительных ресурсов МВС может составлять более 95% .

Тестирование программы метода молекулярной динамики TIME-MD подтвердило высокую надежность алгоритма ММД, использующего для параллельной обработки метод декомпозиции времени с автоматическим подбором временного шага.

ЗАКЛЮЧЕНИЕ

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

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

2. Разработаны параллельные алгоритмы и программы для ММД, использующие метод декомпозиции времени для организации параллельной обработки. Программы, использующие данный метод позволяют эффективно использовать ресурсы многопроцессорных вычислительных систем (до 95% и более).

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

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

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

6. Разработана программа, использующая метод декомпозиции времени, для организации параллельной обработки ММД. Тестирование программы полностью подтвердило предполагаемые возможности данного метода. Производительность МВС при решении задач ММД нарастает линейно и эффективность использования ресурсов вычислительной системы может достигать 95% и более.

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

8. Тестирование разработанной программы, использующей метод декомпозиции времени для организации параллельной обработки ММД, полностью подтвердило предполагаемые возможности данного метода.

1. Alder В.J., Wainwright Т.Е., 1п: Transport process in statistical mehanics/Ed. I. Prigogine. N.Y.: Intersci., 1958, p. 321-376.

2. Alder B.J., Wainwright Т.Е., J. Chem. Phys., 1960, v.33, N4, p. 1439-1447.

3. Gibson J.B., Goland A.N., Milgram., Vineyard G.H. Dynamics of Radiation Damage.-Phys.Rev,v. 120,1960, p.1229-1235.

4. Вайниард Дж. Динамика радиационного повреждения. УФН, 1961, т.74, С.435-442.

5. Verlet L., "Computer 'experiments' on classical fluids. I. Thermodynamical properties of Lennard Jones molecules" Physical Review, V.159,1967. P. 98-103.

6. Alder B.J., Wainwright Т.Е., Phase Transitions for a Hard Sphere System, J. of Chem. Phys. v.27, 1957. P. 1208-1213.

7. W. W. Wood and F. R. Parker, Monte Carlo Equation of State of Molecules Interacting with the Lennard-Jones Potential. I. A Supercritical Isotherm at About Twice the Critical Temperature, J. Chem. Phys. V.27, 1957. P. 720-725.

8. A. Rahman, Correlation in the Motion of Atoms in Liquid Argon, Phys. Rev. v. 136, 1964. P. 405-4011.

9. A. Rahman, J. Chem. Phys., 1966, v. 45, N7, p.2528-2589.

10. B. J. Alder and T. E. Wainwright, Decay of the Velocity Autocorrelation Function, Phys. Rev. V.A 1, N.l, 1970. P. 18-27.

11. A. Rahman and F. H. Stillinger, Molecular Dynamics Study of Liquid Water, J. Chem. Phys. V.55, N.7, 1971. P. 3356-3359.

12. D. J. Evans and S. Murad. Singularity Free Algorithm for Molecular Dynamics Simulation of Rigid Polyatomics, Mol. Phys. V.34, 1977. P.32,7-331.

13. G. Ciccotti, M. Ferrario and J. P. Ryckaert. Molecular Dynamics of Rigid Systems in Cartesian Coordinates. A General Formulation,

14. Mol. Phys. V.47, 1982. P. 1253-1258.

15. G. M. Torrie and J. P. Valleau, Nonphysical Sampling Distributions in Monte Carlo Free-Energy Estimation: Umbrella Sampling, J. Comp. Phys. V.23, 1977. P. 187-190.

16. D. Frenkel and A. J. L. Ladd, New Monte Carlo Method to Compute the Free Energy of Arbitrary Solids. Application to the FCC and

17. HCP Phases ofHard Spheres, J. of Chem. Phys. V. 81, 1984. P.3188-3192.

18. C. H. Bennett, Efficient Estimation of Free Energy Differences from Monte Carlo Data, J. of Comp. Phys. V.22, 1976. P. 245-249.

19. D. J. Evans and S. Murad. Singularity Free Algorithm for Molecular Dynamics Simulation of Rigid Polyatomics, Mol. Phys. V.34„ 1977. P. 327330.

20. H. C. Andersen, Molecular Dynamics Simulations at Constant Pressure and/or Temperature, J. Chem. Phys. V.72, 1980. P. 2384-2389.

21. M. Parrinello and A. Rahman, Polymorphic Transitions in Single Crystals: A New Molecular Dynamics Method, J. Appl. Phys. 52, 1981. P.7182-7186.

22. S. Nose, A Unied Formulation of the Constant Temperature Molecular Dynamics Methods, J. Chem. Phys. V.81, 1984. P. 511-514.

23. W. Hoover, Canonical Dynamics: Equilibrium Phase-Space Distributions, Phys. Rev. V. 31, 1985. P. 1695-1698.

24. D. Fincham, Programs for the Molecular Dynamics Simulation of Liquids: I. Spherical Molecules with Short-Range Interactions, Comp.

25. Phys. Comm. V.21, 1980. P. 247-250.

26. R. Vogelsang, M. Schoen and C. Hoheisel, Vectorization of Molecular Dynamics Fortran Programs Using the Cyber 205 Vector Processing Computer, Comp. Phys. Comm. 30, 1983. p.235-241.

27. D. Fincham and B. J. Ralston, Molecular Dynamics Simulation Using the Cray-1 Vector Processing Computer, Comp. Phys. Comm. V.23, 1981. P. 127-131.

28. M. Schoen, Comp. Phys. Comm. V.52, 1989. P. 175-178.

29. R. Car and M. Parrinello, Unied Approach for Molecular Dynamics and Density-Functional Theory, Phys. Rev. Lett. V.55, 1985. P. 2471-2475.

30. Моделирование на ЭВМ дефектов кристаллической решетки, (под. Редакцией Билера) М.:Мир, 1974, С. 112-207.

31. Ганн В.В., Марченко И.Г. Комплекс программ ДИМОД для динамического моделирования дефектов в металлах и сплавах. Препринт Харьков.:Изд. ХФТИ АН УССР, 1987. 23с.

32. Михайлин А.И. Экономичный алгоритм подсчета взаимодействия в задаче многих тел. Сб.докладов Всесоюзного совещания по радиационным дефектам в кристаллах, Алма-Ата, 1977, С.6-7.

33. Dahlquist G., Bjorck A. Numerical Methods. Englewood Cliffs, N.J.: Prentice Hall, 1964. p.33-38.3l.Swope W.C., Andersen H.S., Berens P.H., Wilson K.R. // J. Chem. Phys. 1982. v.76. p.637-641.

34. Ralston A., Wilf W. Mathematical methods for digital computers. N. Y.: Wiley, 1966. 127 P.

35. Rahman A., Stillinger F.H. Chem. Phys.,1971, V. 55, N7, p. 3336-3359.

36. Berne B.J, Harp G.D.- Adv. Chem. Phys, 1970, V. 17, N1, p. 63-69.

37. Brown D, Clarke J.H.R. //Mol. Phys. 1984. V.51 p.1423-1428.

38. Протасов В.И., Чудинов В.Г. Оптимизация временных характеристик алгоритма метода молекулярной динамики. В кн.: Моделирование на ЭВМ дефектов в кристаллах. - Л.:Изд.ФТИ им.Иоффе АН СССР, 1980, С.105-106.

39. Андреев В.В., Чудинов В.Г. Оптимизация временных характеристик метода молекулярной динамики в комплексе программ MMDYN. ВИНИТИ 2242-В. 1988. 14 с.

40. Chudinov V.G., Andreev V.V. Atomic Mechanism of primary defect heterogeneous nucleation under radiation in FCC metals with a large stacking energy. Nucl. Mater. 1990. v. 172. p.106-113.

41. Chudinov V.G., Andreev V.V. Atomic Mechanism of Solid-Liquid Transition in F.C.C. Metals with a Large Stacking-Fault Energy, phys. stat. sol. (a) 118, (1990). p. 415-423.

42. Chudinov V.G., Goshchitskii B.N., Moseev N.V., Andreev V.V. Kinetics of Radiation-Induced Segregation of Impurities in F.C.C. Metals at the Thermal Stage of the Collision Cascade, phys. stat. sol. (a) 119,1990. p.437-442.

43. Chudinov V.G., Cotterill R.M.J., Andreev V.V. Possible Mechanism for the Solid-Liquid Phase Transition in H.C.P. and B.C.C. Structures, phys. stat. sol. (a) 122, 1990. p. 187-193.

44. Chudinov V.G., Cotterill R.M.J., Andreev V.V., Kinetics of the Diffuse Processes within a Cascade Region in the Sub-Threshold Stages of F.C.C. and H.C.P. Metals, phys. stat. sol. (a) 122, 1990. p. 111-120.

45. Чудинов В.Г., Андреев B.B. Атомарный механизм сегрегации тяжелых примесей в условиях облучения. ВИНИТИ 1420-В. 1989. 24 с.

46. Н. Schreiber, О. Steinhauser, Р. Schuster,"Parallel molecular dynamics of biomolecules", Parallel Computing, V.18,1992, P. 557.-559.

47. W. Smith, "Molecular dynamics on hypercube parallel computers", Computer Physics Communications, V.62, 1991. P.229-234.

48. L. L. Boyer, G. S. Pawley, "Molecular dynamics of clusters of particles interacting with pairwise forces using a massively parallel computer", Journal of Computational Physics, V.78, 1988. P. 405-409.

49. J. P. Brunet, A, Edelman, and J. P. Mesirov, "Hypercube algorithms for direct N-body solver for different granularities", SIAM Journal of Scientific and Statistical Computing, V.14, 1993,. P 1143.-1149.

50. S. Plimpton, "A new parallel method for molecular dynamics simulation of macromolecular system", Journal of Computational Chemistry, V.17, 1996 P. 326-331.

51. D. Fincham, "Parallel computers and molecular simulation", Molecular Simulation, V.l, 1987. P. 1-7.

52. S. Gupta, "Computing aspects of molecular dynamics simulation", Computer Physics Communications, V.70, 1992. P. 243-246.

53. Plimpton S., Fast Parallel Algorithms for Short-Range Molecular Dynamics, J. Comp. Phys. V.l 17, 1995. P. 1-5.

54. Beazley D.M., Lomdahl P.S., Message-Passing Multi-Cel 1 Molecular Dynamics on the Connection Machine 5, Parall. Comp. 1993. p.27-34.

55. Lomdahl P.S., Tamayo P., Granbech-Jensen N., Beazley D.M., in Proceedings of Supercomputing 1993. p. 520-527.

56. S. Plimpton and G. Heelnger, Scalable Parallel Molecular Dynamics on MIMD Supercomputers, Procs. of the High Performance Computing Conference 92, IEEE Computer Society 1992. p.246-251.

57. S. Plimpton, Fast Parallel Algorithms for Short-Range Molecular Dynamics, Sandia Report SAND91-1144 * UC-705,1993. 24 p.

58. Rapaport D.C., Multi-Million Particle Molecular Dynamics I. Design Considerations for Vector Processing. Comp. Phys. Comm. 62, 1991. P. 198202.

59. Rapaport D.C., Multi-Million Particle Molecular Dynamics II. Design Considerations for Distributed Processing. Comp. Phys. Comm. 62, 1991. p.217-221.

60. Rapaport D.C., Multi-Million Particle Molecular Dynamics III. Design Considerations for Data-Parallel Processing. Comp. Phys. Comm. 76, 1993. P.301-304.

61. Rapaport D.C., Details of Large-Scale Demonstrations of Molecular Dynamics on the CM-5, HLRZ Julich draft report, August 1993. 23 p.

62. Brown D, Clarke J.H.R, Okuda M, Yamazaki T, A Domain Decomposition Parallelization Strategy for Molecular Dynamics Simulations on Distributed Memory Machines, Comp. Phys. Comm. 74, 1993. P.67-72.

63. Scott W, Gunzinger A, Baumle B, Kohler P, Muller U.A, Vonder Muhll H-R, Eichenberger A, Guggenbuhl W, Ironmonger N, Muller-Plathe F, van Gunsteren W.F, Parallel Molecular Dynamics on a Multi Signalprocessor System, Comp. Phys. Comm. 75, 1993. P.65-69.

64. Kalia R.K, S. de Leeuw, Nakano A, Vashishta P, Molecular Dynamics Simulations of Coulombic Systems in Distributed-Memory MIMD machines, Comp. Phys. Comm. 74, 1993. p.316-401.

65. V. Buchholtz and T. Poschel, A Vectorized Algorithm for Molecular Dynamics of Short Range Interacting Particles. Preprint 1980. 22 p.

66. A. R. C. Raine, D. Fincham and W. Smith, Comp. Phys. Comm. 55, 1989. p. 13-16.

67. K. Esselink, B. Smit and P. A. J. Hilbers, Ecient Parallel Implementation of Molecular Dynamics on a Toroidal Network, Part I: Parallelizing Strategy. J. Comp. Phys. 106, 1993. p. 101-107.

68. F. Hedman and A. Laaksonen, Data Parallel Large-Scale Molecular Dynamics for Liquids, Int. Jour, of Quantum Chem. 46, 1993. p.27-31.

69. F. Bruge and S. L. Fornili, Comp. Phys. Comm. 60,1990. p.31-39.

70. Mel'cuk A.I., Giles R.C., Gould H., Molecular Dynamics Simulation of Liquids on the Connection Machine, Computers in Physics, May/June 1991. p.311-317.

71. D.M.Beazley and P. S. Lomdahl, Message-Passing Multi-Cell Molecular Dynamics on the Connection Machine CM-5, Los Alamos tech. report LA-UR-92-3158 and Parallel Computing 20, 1994. p.137-143.

72. Tamayo P., Mesirov J.P., Boghosian B. Parallel Approaches to Short-Range Molecular Dynamics Simulations, Procs. of the Supercomputing'91 conference, Albuquerque NM, IEEE Computer Society 1991. p.462-469.

73. Tamayo P., Giles R. A Parallel Scalable Approach to Short-Range Molecular Dynamics on the CM-5,Procs. of the High Performance Computing Conference 92, IEEE Computer Society 1992. p.240-252.

74. W. Smith. Molecular dynamics on hypercube parallel computers. Comp. Phys. Comm., V. 62, 1991. p. 229-248.

75. B. R. Brooks and M. HodoU.sU.cek. Parallelization of CHARMM for MIMD machines. Chemical Design Automation News, V. 7, 1992. p. 16-22.

76. T. W. Clark, J. A. McCammon, and L. R. Scott. Parallel molecular dynamics. In Proc. 5th SIAM Conference on Parallel Processing for Scientific Computing, SIAM, 1992. p. 338-344.

77. S. E. DeBolt and P. A Kollman. AMBERCUBE MD, Parallelization of AMBER's molecular dynamics module for distributed-memory hypercube computers. J. Comp. Chem., V. 14, 1993. p. 312-329.

78. H. Heller, H. Grubmuller, and K. Schulten. Molecular dynamics simulation on a parallel computer. Molec. Sim., 5, 1990. p.133-165.

79. J. F. Janak and P. C. Pattnaik. Protein calculations on parallel processors: II. Parallel algorithm for forces and molecular dynamics. J. Comp. Chem., 13, 1992. p. 1098-1102.

80. S. L. Lin, J. MellorHCrummey, B. M. Pettit, and G. N. Phillips Jr. Molecular dynamics on a distributed-memory multiprocessor. J. Comp. Chem., 13, 1992. p.1022-1035.

81. W. Smith and T. R. Forester. Parallel macromolecular simulations and the replicated data strategy: I. The computation of atomic forces. Comp. Phys. Comm., 79, 1994. p.52-62.

82. M. Barnett, L. Shuler, R. van de Geijn, S. Gupta, D. Payne, and J. Watts. Interprocessor collective communication library (Intercom). In Proc. Scalable High Performance Computing Conference-94, IEEE Computer Society Press, 1994. p.357-364.

83. G. C. Fox, M. A. Johnson, G. A. Lyzenga, S. W. Otto, J. K. Salmon, and D. W. Walker. Solving Problems on Concurrent Processors: Volume 1. Prentice Hall, Englewood Cliffs, NJ, 1988. p.45-49.

84. R. van de Geijn. Efficient global combine operations. In Proc. 6th Distributed Memory Computing Conference, IEEE Computer Society Press, 1991. p. 291-294.

85. D. Fincham. Parallel computers and molecular simulation. Molec. Sim., V.l, 1987. p. 1-45.

86. S. J. Plimpton. Fast parallel algorithms for short-range molecular dynamics. J. Comp. Phys., V. 117, 1995. p. 1-19.

87. D. Brown, J. H. R. Clarke, M. Okuda, and T. Yamazaki. A domain decomposition parallel processing algorithm for molecular dynamics simulations of polymers. Comp. Phys. Comm., V. 83, 1994. p 1-13.

88. S. Chynoweth, U. C. Klomp, and L. E. Scales. Simulation of organic liquids using pseudo-pairwise interatomic forces on a toroidal transputer array. Comp. Phys. Comm., V. 62,1991. p. 297-306.

89. T. W. Clark, R. V. Hanxleden, J. A. McCammon, and L. R. Scott. Parallelizing molecular dynamics using spatial decomposition. In Proc. Scalable High Performance Computing Conference-94, IEEE Computer Society Press, 1994. p 95-102.

90. K. Esselink, P. A. J. Hilbers. Efficient parallel implementation of molecular dynamics on a toroidal network: II. Multi-particle potentials. J. Comp. Phys., V. 106. 1993. p. 108-114

91. A. Windemuth Advanced algorithms for molecular dynamics simulations: The program PMD. In T. G. Mattson, editor, Parallel Computing in Computational Chemistry, American Chemical Society, 1995. p. 151-160.

92. В. А. Hendrickson, S. J. Plimpton. Parallel many-body simulations without all-to-all communication. J. Par. and Dist. Comp, 1995. p. 27-15.

93. S. J. Plimpton, B. A. Hendrickson. A new parallel method for molecular dynamics simulation of macromolecular systems. Technical Report SAND94-1862, 1994.24 p.

94. S. J. Plimpton, B. A. Hendrickson. Parallel molecular dynamics with the embedded atom method. In Materials Theory and Modeling, volume 291, Materials Research Society Symposium Proc, Fall 1992. p. 37-42.

95. J. H. Li, Z. W. Zhou, and R.J. Sadus, "Modified force decomposition strategies for three-body interactions in molecular dynamics simulations," submitted to Journal of Computational Physics, 2006. p.32-37.

96. S. J. Plimpton, R. Pollock, M. Stevens, Particle-Mesh Ewald and rRESPA for Parallel Molecular Dynamics Simulations, in Proc of the Eighth SIAM Conference on Parallel Processing for Scientific Computing, Minneapolis, MN 1997. p.76-83.

97. Андреев B.B. Метод классификации вычислительных процессов в многопроцессорных вычислительных системах при решении задач методом молекулярной динамики // Химическая физика и мезоскопия, мезоскопия 2006. - Т. 8, №2. - С. 295-303.

98. Андреев В.В. Анализ производительности многопроцессорных Вычислительных систем при решении задач методом молекулярной динамики // Химическая физика и мезоскопия 2006. - Т. 8, №2. - С. 187-197.

99. A.M. Липанов. Теоретические основы отработки твердых ракетных топлив. Институт прикладной механики УрО РАН, Ижеск 2003. С.26-40.

100. Шайтан К.В., Немухин А.В., Фирсов Д.А., Богдан Т.В., Тополь И.А. Электронно-конформационные взаимодействия и значение эффективных зарядов на атомах в пептидах//Молекулярная биология. 1997. Т.31. С. 109-117.

101. Полухин В. А., Ухов В.Ф., Дзугутов М.М. Компьютерноемоделирование динамики и структуры жидких металлов. М.:Наука 1981.323 с.

102. Crubmuller Н., Tavan P. Molecular dynamics of conformational substates for a simplified protein model. J. Chem. Phys., 1994. V. 101, p. 50475057.

103. Wall F.T., Mandel F. Macromolecular dimensions obtained by an efficient Monte Carlo method without sample attrition. J. Chem. Phys., 1975. V. 63, P. 4592-4595.

104. Bahar I., Jernigan R.L. Stabilization of intermediate density states in globular proteins by homogeneous intramolecular attractive interactions. Biophysical J., 1994. V. 66, p. 454-466.

105. Bahar I., Jernigan R.L. Cooperative structural transitions induced by nonhomogeneous intramolecular interactions in compact globular proteins. Biophysical J., 1994. V. 66, p. 467-481.

106. Транспьютеры. Архитектура и программное обеспечение: Пер. с англ./Под ред. Г. Харпа. М.:Радио и связь, 1993. - 304с.

107. М.В. Суетин. Хранение водорода в фуллеренах, их модификациях и составленных их них кластеров. Демидовские чтения на Урале, Екатеринбург, т.1, С.205-206.

108. Головкин Б. А. Параллельные вычислительные системы. М.: Наука, 1980.-520 с.

109. Ю8.Голыытейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа. М.: Наука, 1969. - 384 с.

110. Ю9.Гери М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: Пер. с англ. -М.: Мир, 1982.-416 с.

111. Евреинов Е. В. Однородные вычислительные системы, структуры и среды. М.: Радио и связь, 1981. - 208 с.

112. Евреинов Е. В., Хорошевский Е. Г. Однородные вычислительные системы. Новосибирск: Наука, 1978. - 316 с.

113. Липаев В. В. Распределение ресурсов в вычислительных системах. -М.: Статистика, 1979. 247 с.

114. ПЗ.Пярнпуу А. А., Хохлюк В. И. Параллельные вычисления в прикладных задачах // Сообщение по прикладной математике / Вычислительный центр АН СССР. М., 1985. - 64 с.

115. Самофалов К. Г., Луцкий Г. М. Основы построения конвеерных ЭВМ. Киев: Вища школа, 1981,- 224 с.

116. Системы параллельной обработки: Пер. с англ. / Под ред. Д. Ивенса. -М.: Мир, 1985.-416 с.

117. Фадеева В. Н., Фадеев Д. К. Параллельные вычисления в линейной алгебре II // Кибернетика. 1982. - № 3. - С. 18 - 31.

118. Шихев К. Н. Разностные алгоритмы параллельных вычислительных процессов. -М.: Радио и связь, 1982. 136 с.

119. Элементы параллельного программирования / В. А. Вальковский, В. Е. Котов, А. Г. Марчук, Н. Н. Миренков. М.: Радио и связь, 1983. -240 с.

120. Алгоритвы, математическое обеспечение и архитектура многопроцессорных вычислительных систем / Под общ. ред. А. П. Ершова. М.: Наука, 1982. - 342 с.

121. Головкин Б. А. Параллельные вычислительные системы. -М.: Наука, 1980.-519 с.

122. Еврейнов Э. В., Косарев Ю. Г. Однородные универсальные вычислительные системы высокой производительности. -Новосибирск: Наука, 1966. 213 с.

123. Кухарчук А. Г., Луцкий Г. М., Реутов Г. В. Конвеерный принцип обработки информации. // Кибернетика. 1968. - № 6.- С. 43 - 49.

124. Нагорный Jl. Я. Методы распараллеливания систем управлений большой размерности для решения их на решения их на многопроцессорных структурах // Электронное моделирование. -1980.-№ 1.-С. 28-32.

125. Прангишвили И. В, Виленкин С. Я, Медведев И. Л Параллельные вычислительные системы с общим управлением. М.: Энергоатомиздат, 1983. - 312 с.

126. Алиев A.B., Андреев В.В. Разработка параллельных алгоритмов расчета задач газовой динамики методом крупных частиц // Интеллектуальные системы в производстве.-2006.-№ 1 -С.4 -17.

127. Андреев В.В, Использование метода декомпозиции времени в параллельных алгоритмах метода молекулярной динамики, препринт, выпуск 1, Ижевск: Изд-во ИПМ УрОРАН, 2006. 55 с.

128. Липанов A.M., Кисаров Ю.Ф, Ключников И.Г. Численный эксперимент в классической гидромеханике турбулентных потоков. Екатеринбург: УрО РАН, 2001. 161 с.

129. Андреев В.В. Разработка параллельных алгоритмов для метода молекулярной динамики // Известия Тульского государственного университета. Серия «Математика. Механика. Информатика». Тула: ТГУ, 2006. - Т. 12. - Вып. 3. - С. 7-20