авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

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


Pages:   || 2 | 3 |
-- [ Страница 1 ] --

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

СЕДЬМАЯ СИБИРСКАЯ

КОНФЕРЕНЦИЯ ПО ПАРАЛЛЕЛЬНЫМ

И ВЫСОКОПРОИЗВОДИТЕЛЬНЫМ

ВЫЧИСЛЕНИЯМ

ПРОГРАММА И ТЕЗИСЫ ДОКЛАДОВ

(12 – 14 ноября 2013 года)

Издательство Томского университета

2013

УДК 519.6

ББК 22.18

С 28

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

ным вычислениям: Программа и тезисы докладов (12 – 14 ноября 2013 года).

– Томск: Изд-во Том. ун-та, 2013. – 93 с.

ISBN 978-5-7511-2215-7 Представлены программа и тезисы докладов участников Седьмой Сибирской конференции по параллельным и высокопроизводительным вычислениям, которая пройдет в Томском государственном университете с 12 по 14 ноября 2013 года при поддержке Министерства образования и науки РФ, Суперкомпьютерного консор циума России, Российского фонда фундаментальных исследований (грант № 13-01-06095-г) и ЗАО «Интел».

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

УДК 519. ББК 22. © Томский государственный университет, ISBN 978-5-7511-2215- СЕДЬМАЯ СИБИРСКАЯ КОНФЕРЕНЦИЯ ПО ПАРАЛЛЕЛЬНЫМ И ВЫСОКОПРОИЗВОДИТЕЛЬНЫМ ВЫЧИСЛЕНИЯМ С 12 по 14 ноября 2013 года в Томском государственном универси тете при поддержке Министерства образования и науки Российской Феде рации, Российского фонда фундаментальных исследований и ЗАО «Ин тел» под эгидой Суперкомпьютерного консорциума университетов России пройдет Седьмая Сибирская конференция по параллельным и высокопро изводительным вычислениям. Проведение конференции входит в меро приятия, посвященные 135-летию Томского государственного университе та и 65-летию механико-математического факультета. Информация о предыдущих сибирских конференциях по параллельным вычислениям в ТГУ (2001, 2003, 2005, 2007, 2009, 2011 гг.) находится на сайте:

http://ssspc.math.tsu.ru/.

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



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

- параллельные алгоритмы решения сложных задач;

- современные высокоточные методы вычислительной и индустриаль ной математики;

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

Программный комитет Седьмой Сибирской конференции по параллельным и высокопроизводительным вычислениям Майер Г.В., председатель Программного комитета, ректор ТГУ, профес сор, д.ф.-м.н.;

Воеводин Вл.В., заместитель директора НИВЦ МГУ, член-корр. РАН;

Шайдуров В.В., заведующий кафедрой СФУ, директор ИВМ СО РАН, член-корр. РАН;

Афанасьев К.Е., проректор Кемеровского ГУ, профессор, д.ф.-м.н.;

Демкин В.П., проректор ТГУ, профессор, д.ф.-м.н.;

Малышкин В.Э., заведующий кафедрой НГУ, зав. отд. ИВМиМГ СО РАН, профессор, д.т.н.;

Ильин В.П., г.н.с. ИВМиМГ СО РАН, профессор, д.ф.-м.н.;

Квасов Б.И., в.н.с. ИВТ СО РАН, профессор, д.ф.-м.н.;

Берцун В.Н., декан ММФ ТГУ, доцент, к.ф.-м.н.;

Сущенко С.П., декан ФИнф ТГУ, профессор, д.т.н.;

Старченко А.В., заведующий кафедрой ТГУ, профессор, д.ф.-м.н.

Открытие конференции состоится 12 ноября 2013 года в 10.00 в конференц-зале ТГУ (227–я аудитория главного корпуса ТГУ, пр. Ленина, 36).

Программа Седьмой Сибирской конференции по параллельным и высокопроизводительным вычислениям 12 ноября 2013 года (конференц-зал ТГУ – 227-я ауд. главного корпуса ТГУ) 10.00–10.30 Открытие Седьмой Сибирской конференции Вступительное слово проректора Томского государственного университета, председателя Организационного комитета конференции профессора Г.Е. Дунаевского Доклад проректора ТГУ В.П. Демкина «Высокопроизводительная меди цинская информационная система»

Пленарные доклады 10.30–11.00 Ильин В.П. (ИВМиМГ СО РАН, НГУ, Новосибирск) «О высо копроизводительных вычислениях в «заоблачном» математическом моде лировании»

11.00–11.30 Малышкин В.Э. (ИВМиМГ СО РАН, НГУ, Новосибирск) «Грамотность грядущих столетий»

11.30–12.00 Вяткин А.В., Ефремов А.А., Карепова Е.Д., Шайдуров В.В.

(ИВМ СО РАН, СФУ, Красноярск) «Параллельная реализация модифици рованного метода траекторий»

12.00–12.30 перерыв 12.30–13.00 Квасов Б.И. (ИВТ СО РАН, Новосибирск) «Дискретный под ход в задаче формосохраняющей интерполяции»

13.00–13.30 Фадеев Р.Ю., Толстых М.А., Ибраев Р.А., Ушаков К.В., Кал мыков В.В. (ИВМ РАН, ФБУ «Гидрометцентр», Институт океанологии им. Ширшова РАН, МГУ, Москва) «Совместная модель для прогноза ано малий температуры и осадков с заблаговременностью от недели до меся ца»

13.30–14.30 перерыв 14.30–15.00 Городняя Л.В. (ИСИ СО РАН, НГУ, Новосибирск) «Парадиг ма параллельного программирования: модели, языки, системы»

15.00–15.30 Афанасьев К.Е., Власенко А.Ю. (КемГУ, Кемерово) «Автома тизированный поиск шаблонов ошибочного поведения в параллельных программах, использующих модель передачи сообщений»

15.30–16.00 Петунин Д. (ЗАО Интел, Москва) «Intel® Cluster Studio XE – инструментарий разработчика высокопроизводительных приложений»





16.00–16.30 перерыв 16.30–17.00 Старченко А.В. (ТГУ, Томск) «Численный прогноз локальных метеорологических условий с использованием суперкомпьютера»

17.00–17.30 Маркова В.П. (ИВМиМГ СО РАН, НГУ, Новосибирск) «По строение таблицы правил переходов клеточного автомата, моделирующего волновой процесс»

17.30–18.00 Свешников В.М. (ИВМиМГ СО РАН, НГУ, Новосибирск) «Параллельные алгоритмы декомпозиции расчетной области для решения трехмерных краевых задач на квазиструктурированных сетках»

13 ноября 2013 года Секция «Параллельные алгоритмы решения сложных задач»

(конференц-зал ТГУ – 227-я ауд. главного корпуса ТГУ, 9.00–13.30) (Председатели секции – В.Э. Малышкин, А.В. Старченко) Андрианов А.Н. (ИПМ РАН, Москва) «Параллельная реализация метода взаимодействующих частиц»

Катаев М.Ю., Лукьянов А.К. (ТУСУР, Томск) «Параллельные технологии в задаче моделирования сигнала спутникового Фурье-спектрометра»

Дементьева Е.В., Карепова Е.Д. (ИВМ СО РАН, СФУ, Красноярск) «Эф фективность параллельной реализации метода конечных элементов для задачи распространения поверхностных волн»

Богословский Н.Н. (ТГУ, Томск) «Параллельный алгоритм усвоения спут никовых данных измерений»

Евдокимов Д.В., Прудников П.В. (ОмГУ, Омск) «Компьютерное модели рование фазовых превращений в спиновых системах с использованием графических ускорителей»

Купчишин А.Б., Сарычев В.Г. (НГТУ, Новосибирск) «Разработка про граммного комплекса для конструирования программ обработки геофизи ческих данных на высокопроизводительных вычислительных системах»

Волков А.С. (НГТУ, Новосибирск), Городничев М.А. (ИВМ иМГ СО РАН, Новосибирск) «Параллельный фреймворк для реализации метода частиц в ячейках»

Берцун В.Н. (ТГУ, Томск) «Параллельный алгоритм разделения сеточного графа на домены»

Ткачева А.А. (ИВМиМГ СО РАН, Новосибирск) «Средства для задания управления фрагментированных программ на примере задачи моделирова ния самогравитирующего вещества методом частиц в ячейках»

Шельмина Е.А. (ТУСУР, ТГУ, Томск) «Численное решение обратных за дач переноса примеси на основе разностных схем высокого порядка и тех нологий параллельного программирования»

Заведяев В.В. (КемГУ, Кемерово) «Фотореалистическая визуализация движения жидкости с использованием графического процессора»

Чувашов И.Н. (НИИПММ, Томск) «Параллельные алгоритмы для решения обратных задач динамики небесных тел»

Подстригайло А.С. (НГУ, Новосибирск) «Реализация модели многоча стичного газа FHP-MP на гибридном кластере»

Кулбаев С.С. (ТУСУР, Томск) «Применение технологии CUDA для повы шения скорости работы алгоритма фрактального сжатия изображений на основе перцептивного хеширования»

Абрамов С.В., Егоров С.Я., Егоров Е.С. (ТГТУ, Тамбов) «Разработка алго ритмов трассировки технологических соединений с использованием мно гопроцессорной техники»

Шашев Д.В., Шидловский С.В. (ТГУ, Томск) «Перестраиваемая вычисли тельная среда для задач обработки бинарных изображений»

Черноскутов М.А. (ИММ УрО РАН, УрФУ, Екатеринбург) «Оптимизация производительности параллельной реализации алгоритма поиска в ширину на графе»

Щукин Г.А. (ИВМиМГ СО РАН, Новосибирск) «Исследование фрагментированной реализации метода конечных элементов для начально краевой задачи мелкой воды»

Секция «Современные высокоточные методы вычислительной и индустриальной математики»

(конференц-зал ТГУ – 227-я ауд. главного корпуса ТГУ, 14.30–18.00) (Председатели секции – Б.И. Квасов, В.Н. Берцун) Паасонен В.И. (ИВТ СО РАН, НГУ, Новосибирск) «Применение разност ных схем высокого порядка точности в методе декомпозиции областей»

Кудуев А.Ж., Шумилов Б.М., Абдыкалык кызы Ж. (ОшГУ, Ош, Кыргыз стан, ТГАСУ, Томск) «Алгоритмическое и программное обеспечение вейвлет-моделирования поверхностей автомобильных дорог по материа лам лазерного сканирования»

Ыманов У.С., Шумилов Б.М. (ОшГУ, Ош, Кыргызстан, ТГАСУ, Томск) «О мультивейвлетах эрмитовых сплайнов произвольной нечетной степени»

Абеляшев Д.Г., Михайлов М.Д. (ТГУ, Томск) «Математическое моделиро вание процессов самоочищения загрязннного участка реки с помощью модификации моделей Герберта и Стритера–Фелпса»

Мартюшев С.Г., Шеремет М.А. (ТГУ, Томск) «Математическое моделиро вание термогравитационной конвекции и теплового поверхностного излу чения в дифференциально обогреваемом параллелепипеде»

Фомин А.А., Фомина Л.Н. (КузГТУ, КемГУ, Кемерово) «Принцип прямого сочетания релаксационных и градиентных методов решения систем разностных эллиптических уравнений»

Шерина Е.С. (ТГУ, Томск) «Численный подход к решению коэффициент ной обратной задачи электроимпедансной томографии»

Алымкулов К., Турсунов Д.А. (ОшГУ, Ош, Кыргызстан) «Обобщение ме тода погранфункций для бисингулярно возмущенных эллиптических урав нений»

Фомин А.А., Фомина Л.Н. (КузГТУ, КемГУ, Кемерово) «Применение не явного итерационного полинейного рекуррентного метода для решения задачи о течении несжимаемой вязкой жидкости в плоской каверне»

Цыденов Б.О., Старченко А.В. (ТГУ, Томск) «Алгоритм SIMPLED согла сования полей скорости и давления для численного моделирования термо бара в глубоком озере»

Кошкина А.А. (ТГУ, Томск) «Численное решение уравнения эллиптиче ского типа на неструктурированной сетке в области сложной геометрии»

Иванов В.Г. (ТГУ, Томск) «Сравнительный анализ некоторых численных методов решения уравнений Навье–Стокса»

Эркебаев У.З. (ОшГУ, Ош, Кыргызстан) «Применение эрмитовых сплайн вейвлетов (4n-1)-й степени к численному решению обыкновенных диффе ренциальных уравнений»

Баглаев И.И. (БурГУ, Улан-Удэ) «Поворотный метод моделирования кри вых»

18.00-20.00 Мастер-класс «Основы программирования Intel® Xeon™ Phi»

(314-я ауд., 2-й учебный корпус ТГУ), преподаватели – Д.В. Петунин (ЗАО «Intel»);

инструкторы – сотрудники ТГУ С.А. Проханов, Н.Н. Богослов ский.

14 ноября 2013 года Секция «Современные высокоточные методы вычислительной и индустриальной математики» (продолжение) (конференц-зал ТГУ – 227-я ауд. главного корпуса ТГУ, 9.00–11.00) (Председатели секции – Б.И. Квасов, В.Н. Берцун) Турсунов Д.А., Семенов М.Е. (Ошский ГУ, Ош, Кыргызстан, ТПУ, Томск) «Алгоритм для численного решения обыкновенных дифференциальных уравнений одношаговым блочным методом»

Бубенчиков М.А., Бубенчиков А.М., Баатарын Очирбат, Гончиг Чимэд Очир, Б.В. Заятуев (ТГУ, Томск, БурГУ, Улан-Удэ) «Кручение бруска прямоугольного сечения»

Бубенчиков М.А., Бубенчиков А.М., Тумэрпурэвийн Намнан, Баатарын Очирбат, Цыренова В.Б., Энхбат Р. (ТГУ, Томск, БурГУ, Улан-Удэ) «По тенциальная деформация упругого параллелепипеда»

Дериглазова И.А. (ТГУ, Томск) «Монотонная разностная схема высокого порядка аппроксимации для конвективно-диффузионного уравнения»

Чуруксаева В.В., Михайлов М.Д. (ТГУ, Томск) «Математическое модели рование распространения примеси в канале со сложным профилем дна»

Карпова В.В., Каминская Е.В. (ТГУ, Томск) «Об использовании весового кубического сплайна в численном решении уравнения переноса»

Рейбандт А.И., Репнв А.В., Сартин С.А. (СКГУ, Петропавловск, Казах стан) «Расчт распределения влаги и транспорта водяных паров в мезосфе ру»

Тынкевич М.А. (КузГТУ, Кемерово) «К программной реализации решения задачи геометрического программирования»

Бервено Е.В. (ИВМиМГ СО РАН, Новосибирск) «Моделирование филь трации двухфазной жидкости в неоднородной среде»

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

(конференц-зал ТГУ – 227-я ауд. главного корпуса ТГУ, 11.00–14.00) (Председатели секции – С.П. Сущенко, Н.Н. Богословский) Перепелкин В.А. (ИВМиМГ СО РАН, Новосибирск) «Автоматическое обеспечение динамической балансировки загрузки процессоров в системе фрагментированного программирования LuNA»

Беляев Н.А. (Новосибирский государственный технический университет, Новосибирск) «Организация безопасных отказоустойчивых вычислений на распределенных мобильных устройствах»

Вайцель С.А., Городничев М.А. (НГТУ, ИВМиМГ СО РАН, Новосибирск) «HPC Community Cloud: разработка инструментария для повышения уров ня взаимодействия пользователей с объединенными HPC-системами»

Повар А.В., Прудников П.В. (ОмГУ, Омск) «Среда распределенных высо конагруженных вычислений Aurora»

Пименов Е.С., Поляков А.Ю. (СибГУТИ, ИФП СО РАН, Новосибирск) «Анализ статистических данных отказов кластерных систем национальной лаборатории Лос-Аламоса»

Полежаев П.Н., Легашев Л.В. (ОрГУ, Оренбург) «Использование про граммно-конфигурируемых сетей для управления потоками данных в вы сокопроизводительных вычислениях»

Рейбандт А.И., Сартин С.А. (СКГУ, Петропавловск, Казахстан) «О воз можности классификации запросов с использованием ГПУ процессоров»

Кандрюкова Т.А. (ИВМиМГ СО РАН, Новосибирск) «Численное модели рование процесса фильтрационного горения на машинах Xeon»

Poghosyan A.H., Astsatryan H.V., Shahinyan A.A. (International Scientific Ed ucational Center, Institute for Informatics and Automation Problems, НАНРА, Ереван, Армения) «Parallel Performance of GROMACS Package on HPC Plat forms»

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

ГРАМОТНОСТЬ ГРЯДУЩИХ СТОЛЕТИЙ В.Э. Малышкин Институт вычислительной математики и математической геофизики СО РАН, Новосибирск Новосибирский государственный университет, Новосибирск Рассматривается проблема обучения грамотности, необходимой в нынешних и будущих временах, с учетом тенденций развития общества, науки и техники. На базе моделей параллельных вычислений предлагается система технологической грамотности «на будущее». Последовательно рассматриваются вопросы:

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

2. Методы синтеза программ (логический и структурный) как способы описания активных знаний.

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

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

5. Необходимая будущая грамотность – это умение оперировать аксиома тическими теориями: разрабатывать, использовать, модифицировать.

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

7. Заключительные замечания:

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

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

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

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

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

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

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

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

Умение правильно формулировать задачи и составит основу будущего высшего образования.

И лишь единицы, хорошие математики, будут заниматься самой интересной работой – конструированием баз активных знаний.

Литература 1. Kraeva M.A., Malyshkin V.E. Assembly Technology for Parallel Realization of Numerical Models on MIMD-Multicomputers // International Journal on Fu ture Generation Computer Systems, Elsevier Science. 2001. Vol. 17, No. 6.

P. 755–765.

2. Вальковский В.А., Малышкин В.Э. Синтез параллельных программ и систем на вычислительных моделях. – Новосибирск:Наука, 1988, 128 с.

http://ssd.sscc.ru/ru/chair/literature 3. Malyshkin V. Two approaches to Program Synthesis or Implementation of Partially Defined Theories // In the Proceedings of the 11-th Int. Conference on New Trends in Software Methodologies, Tools and Techniques, IOS Press, 2012. Vol. 246. P. 285–291.

4. Малышкин В.Э. Параллельные вычисления и представление активных знаний // Параллельные вычисления и задачи управления PACO’2012. Ше стая международная конференция, Москва, 24-26 октября 2012 г. Труды: в 3 т. – М.: ИПУ РАН, 2012. Т. 1. 390 с., С. 70–77.

ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ МОДИФИЦИРОВАННОГО МЕТОДА ТРАЕКТОРИЙ А.В. Вяткин1, А.А. Ефремов1, Е.Д. Карепова1,2, В.В. Шайдуров Институт вычислительного моделирования СО РАН, Красноярск Институт математики и фундаментальной информатики Сибирского фе дерального университета, Красноярск В течение двух последних десятилетий активно развивались чис ленные алгоритмы [1-4] решения уравнения переноса (в зарубежной лите ратуре – уравнения адвекции или конвекции), основанные на смешанном полу–лагранжевом (semi-Lagrangian) методе. Преимуществом метода яв ляется отсутствие условия Куранта–Фридрихса–Леви на шаг по времени, что делает метод удобным инструментом для решения задач с большими значениями скоростей. Другим достоинством подхода является выполне ние закона сохранения в консервативных версиях метода. Консерватив ность метода основана на выполнении локального закона сохранения, ко торый справедлив для внутренних узлов сетки. При этом учет граничных узлов, как правило, не производится. Представленная в работе разностная схема является одним из вариантов этого метода. В данной работе пред ставлена теорема, позволяющая точно учитывать краевые условия. Кроме этого, в работе обоснована сходимость метода с первым порядком точно сти.

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

Для OpenMP-версии проведено исследование влияния технологии HyperThreading, зависимости ускорения от размерности задачи и количе ства используемых потоков. Кроме того, обсуждаются проблемы реализа ции и производительности алгоритма для вычислительных систем гибрид ной архитектуры с помощью технологии CUDA. На первый взгляд сравне ние технологий OpenMP и CUDA применительно к нашему алгоритму де монстрирует преимущества OpenMP. Однако хочется заметить следую щее: некорректно сравнивать количество ядер GPU (в нашем случае ядер на видеокарту) и количество ядер CPU (у нас 12 физических или логических). В архитектуре ядра GPU можно найти только один аналог составляющих ядра CPU – арифметико-логическое устройство. Правиль нее сравнить ядро CPU c потоковым мультипроцессором (SM), который, кроме ядер GPU, содержит разнообразные устройства управления и иерар хию памяти. Таким образом, в нашем исследовании проводилось сравне ние технологии OpenMP на 12 ядрах CPU и технологии NVIDEA CUDA на 14 потоковых мультипроцессорах. В таком ракурсе результаты с учетом дальнейшего развития CUDA-версий следует интерпретировать как выиг рышные для графических процессоров.

Работа выполнена при поддержке РФФИ (грант № 11-01-000224-a), Президиума РАН (проект 18.2) и Президиума СО РАН (интеграционный проект № 130).

Литература 1. Priestley A. A quasi-conservative version of the semi-Lagrangian advection scheme // Mon. Weather Rev. – 1993 – V. 121 – P. 621–629.

2. Phillips T.N., Williams A.J. Conservative semi-Lagrangian finite volume schemes // Numer. Meth. Part. Diff. Eq. – 2001 – V. 17 – P. 403–425.

3. Iske A. Conservative semi-Lagrangian advection on adaptive unstructured meshes // Numer. Meth. Part. Diff. Eq. – 2004 – V. 20 – P. 388–411.

4. Osher S. Convergence of generalized MUSCL schemes // SIAM J. Numer.

Anal. – 1985. – V. 22. – P. 947–961.

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

СОВМЕСТНАЯ МОДЕЛЬ ДЛЯ ПРОГНОЗА АНОМАЛИЙ ТЕМПЕРАТУРЫ И ОСАДКОВ С ЗАБЛАГОВРЕМЕННОСТЬЮ ОТ НЕДЕЛИ ДО МЕСЯЦА Р.Ю.Фадеев1, М.А.Толстых1,2, Р.А. Ибраев1,3, К.В.Ушаков3, В.В.Калмыков Институт вычислительной математики РАН, Москва ФГБУ «Гидрометцентр России», Москва Институт океанологии им. Ширшова РАН, Москва Московский государственный университет им. Ломоносова, Москва Совместная модель представляет собой комплекс отдельно разраба тываемых компонентов-моделей, объединенных в единую программу с помощью каплера. В функции каплера входит распределение вычисли тельных ресурсов, обеспечение вывода результатов и промежуточной диа гностики, организация обмена данными между отдельными компонентами (в том числе синхронизация времени и процедура интерполяции данных с сетки одной модели на сетку другой модели).

В докладе обсуждается совместная модель атмосферы, океана и почвы, ориентированная на прогноз погоды с заблаговременностью от не дели до месяца. Под прогнозом здесь понимается вероятностный прогноз осредненных аномалий погоды по отношению к климату. В совместной модели использовались модель атмосферы ПЛАВ [1], модель Мирового океана ИВМ-ИО РАН [2], модель почвы ISBA [3]. В рамках создания си стемы совместного моделирования впервые в России был реализован кап лер [4].

Представлены первые результаты расчетов, которые проводились на суперкомпьютере «Ломоносов» и межведомственном суперкомпьютере «МВС-10П» на нескольких тысячах ядер.

Работа выполнена при поддержке грантов в форме субсидии Ми нобрнауки России в рамках ФЦП «Кадры» (соглашения 8344 и 8350 от 17.08.2012), частичной поддержке РФФИ (13-05-00868).

Литература 1. Толстых М.А. Глобальная полулагранжева модель численного прогноза погоды. М.;

Обнинск: ОАО ФОП. 2010. 111 с.

2. Ибраев Р.А., Хабеев Р.Н., Ушаков К.В. Вихреразрешающая 1/10° модель Мирового океана // Известия РАН. Физика атмосферы и океана. 2012. Т.

48. С. 45–55.

3. Noilhan J., Mahfouf J.-F. The ISBA land surface parameterization scheme // Global Planet. Change. 1996. V. 13. P. 145—149.

4. Толстых М.А., Ибраев Р.А., Володин Е.М., Ушаков К.В., Калмыков В.В., Шляева А.В., Мизяк В.Г., Хабеев Р.Н. Модели глобальной атмосферы и Мирового океана: алгоритмы и суперкомпьютерные техно логии. М.: Изд-во МГУ, 2013. 144 с.

ПАРАДИГМА ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ:

МОДЕЛИ, ЯЗЫКИ, СИСТЕМЫ Л.В. Городняя Институт систем информатики СО РАН, Новосибирск Новосибирский государственный университет, Новосибирск В докладе рассмотрены результаты анализа основных средств и ме тодов представления программ организации параллельных процессов, опробованных в современных языках программирования, и резервы опре деления языков высокого уровня с целью повышения эффективности и надежности использования новых возможностей аппаратуры и информа ционных технологий.

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

Более удачной оказалась идея поэлементной обработки однородных струк тур данных в языке APL. Algol-68 включил механизм непрерывно испол няемых критических участков и представления их защиты в терминах се мафоров. Э.Дейкстра предложил защищенные команды и озвучил идеи структурного программирования, нацеленные на снижение сложности от ладки программ. В язык Ada предпочли включить «рандеву», подобное сигналам в оборудовании.

В языке теоретико-множественного программирования Setl постро ение формул с кванторами погружено в схему последовательного управ ления процессами. Идеи явного порождения процессов и организации их взаимодействия через каналы возникли в языках управления заданиями (JCL) и процессами в операционных системах (Unix). В практике общих баз данных и языка запросов (SQL) возникла концепция транзакционной памяти – перспективная основа работы с памятью в новых языках парал лельного программирования. Функциональный язык параллельного про граммирования Sisal предложил пространства итераций для распараллели вания циклов и фильтрацию мультизначений. MPI и Open MP обеспечи вают параллелизм в рамках языков Fortran и C.

В нашей стране разработаны языки БАРС и Поляр с разными кон цепциями сетевого управления процессами и представления дисциплины доступа к памяти. Программы стали многопоточными, циклы – параллель ными, память обретает копии и реплики, события происходят одновремен но в разных процессах, вычисление результата может не означать завер шение процесса. Такая ревизия понятий учтена в языке mpC в терминах барьеров и специальных категорий переменных, обладающих особым, ап паратно реализуемым поведением.

Известны прецеденты успешного применения таких систем, как Promela, Spin и др., в области проверки протоколов взаимодействия про цессов.

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

Литература 1.Бурдонов И.Б., Косачев А.С., Кулямин В.В. Теория соответствия для систем с блокировками и разрушениями. – М.: ФИЗМАТЛИТ, 2008. – с.

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

Одним из наиболее перспективных представляется подход автоматизиро ванного контроля корректности, используемый в таких инструментальных средствах, как ITAC (Intel Trace Analyzer and Collector) и MUST (Marmot Umpire Software Tool). Основная идея данного метода заключается в том, что во время компиляции пользовательская программа статически связы вается с профилировочной библиотекой, которая перехватывает вызовы MPI-функций в программе и по заложенным в систему отладки правилам проводит анализ на возникновение логических ошибок. Одной из главных проблем этого подхода является чрезвычайно большое количество различ ных возможных ситуаций в MPI-программе, которые можно расценить как ошибочные. Реализовать обнаружение всех таких ситуаций в инструмен тальном средстве автоматизированного контроля корректности едва ли возможно, хотя бы потому, что для некоторых ситуаций вопрос о том, от носить ли ее в разряд ошибочных или нет, является спорным.

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

функции, вызываемые данными процессами;

условия на аргументы функций. Соответственно, файл шаблона разбит на 3 блока. Так, шаблон «Различное количество отправляемых и принимае мых элементов в операциях точка-точка» выглядит следующим образом:

Name= Different amount of elements in send-recv operations 1block K=2 p1= 2block F1=p1:Send_any F2=p2:Recv_any 3block F1(2)!=F2(2) Шаблон говорит о том, что в ситуации участвуют два процесса (K=2), первый из которых имеет номер 0 в коммуникаторе MPI_COMM_WORLD. Номер второго процесса также можно специфици ровать. Во втором блоке указано, что первый процесс должен вызвать лю бую операцию отправки (Send_any – макрос, заменяющий Send, Ssend, Isend,…), а второй процесс – любую операцию приема (Recv, Irecv). Усло вие третьего блока означает, что вторые аргументы функций должны быть не равны.

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

Созданная система прошла апробацию на тестовых MPI программах, для чего использовались вычислительные ресурсы центра коллективного пользования «Высокопроизводительные параллельные вы числения» Кемеровского государственного университета (icp.kemsu.ru/CKP).

ЧИСЛЕННЫЙ ПРОГНОЗ ЛОКАЛЬНЫХ МЕТЕОРОЛОГИЧЕСКИХ УСЛОВИЙ С ИСПОЛЬЗОВАНИЕМ СУПЕРКОМПЬЮТЕРА А.В. Старченко Томский государственный университет, Томск Представлены мезомасштабные метеорологическая и фотохимиче ская модели высокого разрешения для прогноза и исследования погодных явлений и качества приземного воздуха над ограниченной урбанизирован ной территорией или крупным промышленным или транспортным узлом.

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

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

Представленные мезомасштабные метеорологические модели были применены для краткосрочного прогнозирования опасных погодных явле ний в аэропорту Богашево и для исследования влияния химического и аэрозольного состава набегающего потока, характерного для воздуха с продуктами горения, на интенсивность образования фотохимического смога над городом Томск. Результаты расчетов сравниваются с измерени ями, выполненными сотрудниками ИОА СО РАН и ИМКЭС СО РАН, а также с расчетами, проведенными по модели Weather Research & Forecast.

Работа выполнена при финансовой поддержке ФЦП "Научные и научно-педагогические кадры инновационной России" на 2009-2013 (со глашение № 14.B37.21.0667), РФФИ, грант № 12-01-00433а и по заданию Министерства образования и науки РФ № 8.4859.2011.

ПОСТРОЕНИЕ ТАБЛИЦЫ ПРАВИЛ ПЕРЕХОДОВ КЛЕТОЧНОГО АВТОМАТА, МОДЕЛИРУЮЩЕГО ВОЛНОВОЙ ПРОЦЕСС В.П. Маркова Институт вычислительной математики и математической геофизики СО РАН, Новосибирск Клеточные автоматы типа Lattice-Gas Automata (решеточные газы) описывают волновой процесс множеством гипотетических частиц, кото рые движутся в дискретном пространстве по некоторым правилам. Эти правила представляют моделируемый процесс на микроскопическом уровне, исходя из общих законов физики. Пространство разбито на мно жество одинаковых клеток, организованных в решетку. В каждой клетке может находиться несколько движущихся частиц. Движущиеся частицы имеют одинаковую массу, равную единице, и единичный вектор скоро сти, направленный в сторону ближайшего соседа. Каждой клетке клеточ ного автомата ставится в соответствие конечный автомат. Такт работы конечного автомата состоит из двух этапов: столкновение и сдвиг. Все клетки клеточного автомата вычисляют новое состояние синхронно и па раллельно, в результате чего происходит изменение глобального состоя ния клеточного автомата. Итеративная смена глобальных состояний (эво люция) клеточного автомата описывает динамику волнового процесса.

Интерес к КА-моделированию объясняется многими причинами.

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

Одной из сложных задач в построении клеточных автоматов являет ся конструирование таблицы правил переходов, которая описывает работу клеточного автомата на этапе столкновения частиц. Таблица правил пере ходов представляет собой квадратную матрицу, (i,j)-тый элемент которой задает вероятность перехода конечного автомата из состояния i в состоя ние j. Для элементов таблицы должны выполняться ряд условий: закон сохранения массы и импульса, нормализация, баланс (детальный или по лудетальный) и т.д.

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

Исследование выполнено по Программе фундаментальных исследо ваний Президиума РАН, проект № 15-9, а также при финансовой под держке РФФИ в рамках научного проекта № 11-01-00567a.

Литература 1.Zhang M., Cule D., Shafai L., Bridges G., Simons N. Computing Electro magnetic Fields in Inhomogeneous Media Using Lattice Gas Automata // In:

Proceedings of 1998 Symposium on Antenna Technology and Applied Electro magnetics, Aug.14-16, Ottawa, Canada.

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

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

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

Математическое обоснование данного подхода можно найти в работе [2], которая и послужили основой для настоящей работы.

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

- Установить связи между частицами. В модельной задаче связь между частицами считается установленной, если расстояние между ними меньше заданного числа.

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

Для решения данных задач используются две модели параллелиз ма – MPI и OpenMP. Каждый MPI-процесс обрабатывает фрагмент сетки и все частицы, находящиеся в данном фрагменте сетки. Ввиду большого объема данных процесса (порядка 10 Gb), каждый процесс проводит свой расчет на узле процессора. Для эффективного использования ядер узла используется модель распараллеливания OPENMP. При решении задачи установления связи необходимо учитывать порядок построения связей и обеспечить место (соответствующий массив) для размещения обнаружен ных связей. Последнее замечание важно, поскольку заранее нельзя пред ставить количество таких связей и необходимо предусмотреть динамиче ское расширение такого массива. При расчете функций для частиц важно, что эти функции носят интегральный характер (неформально это сумма некоторых значений от всех линий связей, в которые входит частица).

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

Проводился расчет модельной задачи на МВС-100К, установленной в ИПМ им. М.В. Келдыша РАН [3]. Выбрана сетка с размерами 200х200х400. Первоначально частицы расположены в подсетке – (50...150)х(50...150)х(200...300). В каждой ячейки этой подсетки размеща лись 64 частицы. Общее число частиц равно 64000000. Общее число уста новленных связей равно 7586611200.

Литература 1. Андрианов А.Н., Ефимкин К.Н. Подход к параллельной реализации метода частиц в ячейках. Препринт ИПМ РАН. М., 2009. № 9.

2. Мажукин В.И., Шапранов А.В. Математическое моделирование про цессов нагрева и плавления металлов. Часть I: Модель и вычислительный алгоритм. Препринт ИПМ. М., 2012. №31.

3. http://www.kiam.ru/MVS/resourses ПАРАЛЛЕЛЬНЫЕ ТЕХНОЛОГИИ В ЗАДАЧЕ МОДЕЛИРОВАНИЯ СИГНАЛА СПУТНИКОВОГО ФУРЬЕ-СПЕКТРОМЕТРА М.Ю. Катаев, А.К. Лукьянов Томский государственный университет систем управления и радиоэлек троники, Томск Стоящий на спутнике GOSAT Фурье-спектрометр среднего разре шения измеряет отраженное излучение от поверхности Земли в ближней инфракрасной области. Траектория полета настроена так, чтобы за три дня спутник приходил в точку вылета. За это время происходит более 12 тысяч измерений. За год таких измерений набирается более 1,5 млн. Спектрометр имеет три канала (0,7;

1,6 и 2 мкм) с спектральным разрешением 0,1 – 1 см.

В совокупности число спектральных точек в трех каналах составляет око ло 20 тысяч. Пятно обзора составляет 8х8 км, расстояние между точками 80 км в направлении полета спутника, расстояние между траекториями около 80 км. Для исследования точностных характеристик методов вос становления информации о газовом и аэрозольном составе атмосферы по данным измерений прибором TANSO-FTS, отработки различных методик коррекции спутникового сигнала необходимо проводить моделирование спутниковых сигналов. Задача эта весьма трудоемкая, так как число точек расчета составляет не менее 312 (с учетом разбиения атмосферы на слоев). Расчет спутниковых сигналов с учетом априорной информации о глобальном распределении параметров (газовый состав, температура, дав ление, аэрозоль, рельеф, типы поверхности и др.) требует больших вычис лительных затрат. В связи с этим существует необходимость решать эту задачу с помощью высокопроизводительной многопроцессорной вычисли тельной системы.

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

Программный комплекс в настоящее время адаптирован для вычислитель ного кластера ТУСУР. Проведены массовые расчеты модельных спутни ковых сигналов, которые сравнивались с реальными сигналами. Среднее отличие модельных от реальных сигналов составляет примерно 1,5 – 6 %, в зависимости от угла склонения Солнца (10 – 60 градусов).

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

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

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

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

В работе показано, что при сборке невязки по элементам явное преимуще ство показывает MPI-версия программы, поскольку синхронизация нитей в OpenMP-версии дает большие накладные расходы. Кроме того, сборка не вязки по элементам в MPI-версии выполняется немного быстрее, чем сборка невязки по узловым точкам, что объясняется более выгодным рас пределением памяти в первом случае.

Для систем с общей памятью алгоритм сборки невязки в МКЭ су щественно влияет на эффективность параллельной реализации. Сборка невязки по узловым точкам практически не предполагает синхронизацию нитей в OpenMP-программе. Эффективность в этом случае на 75% выше в сравнении со сборкой невязки по элементам.

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

Работа выполнена при поддержке РФФИ (грант № 11-01-000224-a), Президиума РАН (проект 18.2) и Президиума СО РАН (интеграционный проект № 130).

ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ УСВОЕНИЯ СПУТНИКОВЫХ ДАННЫХ ИЗМЕРЕНИЙ Н.Н. Богословский Томский государственный университет, Томск В настоящее время для составления прогноза погоды используются численные расчеты по математической модели. Численная модель прогно зирования ПЛАВ [1] представляет собой математические уравнения, опи сывающие физические процессы в атмосфере, их свойства и характер их изменения со временем. Для математической модели необходимо задавать начальные значения. Важность точного задания начальных значений поч венных переменных показали в Европейском центре среднесрочных про гнозов на примере чувствительности 72–часовых прогнозов к ошибкам в начальных полях почвенных переменных [2]. Ошибки в задании влажно сти почвы согласно этой работе оказывают значительное влияние на каче ство краткосрочного и среднесрочного численного прогноза погоды и да же оказывают влияние на сезонные прогнозы. Для улучшения качества задания начальных полей почвенных переменных реализовано вариацион ное усвоение данных наблюдений наземных станций и усвоение спутнико вых данных измерений влажности почвы ASCAT [3] на основе оптималь ной интерполяции. Прибор ASCAT позволяет получить измерения с раз решением, приблизительно равным 50 км.

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

Увеличение производительности современных вычислительный си стем идет не только за счет увеличения числа процессоров, но и за счет увеличения количества ядер в каждом процессоре, поэтому необходимо проводить распараллеливание не просто с использованием какой-либо определенной параллельной технологии, но и с учетом архитектурных особенностей. Для этого распараллеливание проводилось как с помощью технологии ОрenМР, так и с помощью MPI. В результате использования гибридной технологии удалось увеличить ускорение на 30% по сравнению с параллельным алгоритмом, в котором использовалась только технология MPI.

Работа выполнена при поддержке гранта РФФИ № 12-05- мол_а и по заданию Министерства образования и науки РФ № 8.4859.2011.

Литература 1. Толстых М. А. Полулагранжева модель атмосферы с высоким разреше нием для численного прогноза погоды // Метеорология и гидрология.

2001. № 4. С. 5–16.

2. Giard D., Bazile E. Assimilation of soil temperature and water content with ISBA in ARPEGe: some new development ant tests // HIRLAM Newsl. Swe dish Meteorological and Hydrological Institute. 1996. №21. P. 10–12.

3. Bartalis Z., Wagner W., Naeimi V., Hasenauer S., Scipal K., Bonekamp H., Figa J. and Anderson C. Initial soil moisture retrievals from the METOP-A Advanced Scatterometer (ASCAT) // Geophysical Research Letters. 2007.

№24 L20,401.

КОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕ ФАЗОВЫХ ПРЕВРАЩЕНИЙ В СПИНОВЫХ СИСТЕМАХ С ИСПОЛЬЗОВАНИЕМ ГРАФИЧЕСКИХ УСКОРИТЕЛЕЙ Д.В. Евдокимов, П.В. Прудников Омский государственный университет им. Ф.М. Достоевского, Омск В последние годы резко возрос интерес к технике GPGPU. Порядка 10 процентов суперкомпьютеров, входящих в рейтинг топ-500 (top500.org) самых мощных компьютеров в мире, построены на основе GPU, и это чис ло продолжает расти, как продолжает расти и производительность новых моделей GPU, попадающих на рынок. Интерес к применению графических процессоров в научных исследованиях привел к появлению серии ви деокарт NVIDIA Tesla, предназначенных для научных вычислений. В по следние годы выходит достаточно большое количество статей, посвящен ных применению графических процессоров в численном исследовании физических систем. Описанное в них применение графического процессо ра позволяет как ускорить процесс вычисления на 1–4 порядка [1–3], так и рассмотреть спиновые системы больших (с линейным размером L 512) размеров [4, 5]. Данное преимущество GPU перед CPU объясняется тем, что GPU изначально был спроектирован для задач трехмерных преобразо ваний и растеризации, являющихся параллельными. В архитектуру GPU изначально заложены только коллективные операций над данными. Как устройства, способные только на коллективные операции, GPU не лишены общих недостатков параллельных систем – проблем падения производи тельности при синхронизации данных между потоками и при обработке ветвлений в алгоритмах. В данном докладе исследуются возможности ро ста производительности при применении GPU к моделированию спиновых систем на примере исследования критического поведения 2D и 3D модели Изинга, выявляются требования и ограничения, налагаемые на алгоритмы применением графического процессора, а также впервые проводится чис ленное моделирование критического поведения ультратонкой ферромаг нитной плнки при помощи GPU.

Рис.1. Ускорение расчтов при использовании GPU для 2D, 3D модели Изинга и для ультратонкой магнитной плнки в зависимости от линейных размеров рештки Литература 1. Preis T., Virnau P., Paul W., Schneider J.J. // J. Comput. Phys. – 2009. – V.

228. – P. 4468.

2. Komura Y., Okabe Y. // J. Comput. Phys. – 2012. – V. 231. – P. 1209.

3. Okabe Y. // Computer Physics Communications. – 2012. – V. 183. – P. 1155.

4. Kaupuzs J., Rimsans J. // Physical Review E. – 2010. – V. 81. – P. 026701.

5. Komura Y., Okabe Y. // Computer Physics Communications. – 2013. – V.

184. – P. 40.

РАЗРАБОТКА ПРОГРАММНОГО КОМПЛЕКСА ДЛЯ КОНСТРУИРОВАНИЯ ПРОГРАММ ОБРАБОТКИ ГЕОФИЗИЧЕСКИХ ДАННЫХ НА ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ А.Б. Купчишин, В.Г. Сарычев Новосибирский государственный технический университет, Новосибирск При анализе геофизических данных требуется организовывать це почки операций обработки данных, в частности, для этих целей на сего дняшний день используется набор вычислительных модулей Madagascar (http://www.ahay.org/wiki/Main_Page). Актуальной задачей является разра ботка эффективных реализаций таких операций обработки данных для различных вычислительных архитектур и разработка инструментария для композиции цепочек обработки данных и автоматизированного выбора подходящей реализации каждой операции цепочки.

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

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

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

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

Для типичного размера задачи 25х25 датчиков на поверхности, 300х300х300 пробных точек в исследуемом объеме среды параллельная реализация когерентного суммирования демонстрирует эффективность выше 80% при использовании до 48 ядер на кластере Сибирского супер компьютерного центра (процессоры Intel(R) Xeon(R) X5560 2.8 GHz, Intel(R) Xeon(R) X5670 2.93GHz).

Литература 1.Колесников Ю.И., Хогоев Е.А., Полозов С.В., Донцов М.В. Применение сейсмоэмиссионной томографии для локализации сейсмических источни ков // Сборник докладов Международной конференции, посвященной 90 летию академика Пузырева Н.Н. «Сейсмические исследования Земной ко ры» Новосибирск, 2004. С.129–134.

ПАРАЛЛЕЛЬНЫЙ ФРЕЙМВОРК ДЛЯ РЕАЛИЗАЦИИ МЕТОДА ЧАСТИЦ В ЯЧЕЙКАХ А.С.Волков1, М.А. Городничев Новосибирский государственный технический университет, Новосибирск, Институт вычислительной математики и математической геофизики СО РАН, Новосибирск При моделировании процессов гидро- и газодинамики, поведения плазмы, поведения вещества под действием гравитации часто использует ся метод частиц-в-ячейках (particles-in-cells, PIC) [1, 2]. В расчетной обла сти задается сетка и помещаются модельные частицы с необходимыми в задаче параметрами. Метод итерационный, и схема каждой итерации со стоит из следующих этапов: частицы порождают поле;

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

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

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

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

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

В настоящий момент такой фреймворк разрабатывается с использо ванием языка C++, библиотек MPI [3], libconfig[4], google-glog[5]. Пользо ватель задает параметры задачи в конфигурационном файле и доопределя ет функции, описывающие математическую модель. Результатом являются текстовые файлы, отражающие характеристики частиц на выбранных вре менных слоях. Запланирована реализация визуализатора текстовых ре зультатов.


Литература 1. Хокни Р., Иствуд Дж. Численное моделирование методом частиц: Пер. с англ. – М.: Мир, 1987. – 640 с.

2. Умнов А.М., Туриков В.А., Муратов М.Н., Сковорода А.С. Современ ные методы вычислительного эксперимента в прикладной физике: Учеб.

пособие. – М.: РУДН, 2008. – 248 с.

3. Стандарты Message Passing Interface(MPI) [Электронный ресурс] – URL:

http://www.mpi-forum.org/docs/ 4. Библиотека разбора конфигурационных файлов (libconfig) [Электрон ный ресурс] – URL:

http://www.hyperrealm.com/libconfig/libconfig_manual.html 5. Библиотека google-glog [Электронный ресурс] – URL:

http://code.google.com/p/google-glog/ ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ РАЗДЕЛЕНИЯ СЕТОЧНОГО ГРАФА НА ДОМЕНЫ В.Н. Берцун Томский государственный университет, Томск Решение значительного числа прикладных задач может быть сведе но к анализу соответствующих им графов. Зная характеристический мно гочлен матрицы смежности графа Gn, можно вычислить его спектр, позво ляющий определять различные параметры исходной прикладной зада чи [1]. Рассмотрена параллельная модификация метода Леверье нахожде ния коэффициентов характеристического многочлена графа с симметрич ной матрицей смежности А размерности n1, имеющей сложность О(n4).

Создание параллельных алгоритмов механики сплошной среды на неструктурированных сетках большой размерности приводит к необходи мости разделения сеточного графа Gn на домены с целью балансировки загрузки процессоров. Для этих целей можно использовать, например, ме тод спектральной бисекции, основанный на нахождении компонент векто ра Фидлера [2,3] для матрицы Лапласа L с элементами:

1, если вершины i и j смежны, li j 0, если i j и вершины i и j не смежны,,если i j.

i где vi– степень вершины xi графа G.

Рис. В этом методе минимизируется суммарный вес ребер, соединяющих вер шины из двух разных доменов S1 и S2. Рассматриваются различные спосо бы определения собственного числа вектора Фидлера. На диаграмме Шле геля (рис. 1) представлено разделение графа фуллерена C20 на два домена вектором Фидлера.

Работа выполнена по заданию Министерства образования и науки РФ № 8.4859.2011.

Литература 1. Акимов О. Е. Конструктивная математика. – М., 2005. – 294 с.

2. Волков К.Н. Балансировка нагрузки процессоров при решении краевых задач механики жидкости и газа сеточными методами. URL: http://num meth.srcc.msu.ru/ 3. Fiedler M. Eigenvectors of aciyclic matrices // Czechoslovak Mathematical Journal. 1975. 25(100). P. 607-618.

4. Гергель В. П. Высокопроизводительные вычисления для многопроцес сорных многоядерных систем. – МГУ, 2010. – 544 с.

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

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

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

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

Литература 1. Malyshkin V.E., Perepelkin V.A. LuNA Fragmented Programming Sys tem,Main Functions and Peculiarities of Run-Time Subsystem // Proceedingsof the 11-th Conference on Parallel Computing Technologis, LNCS 6873,Springer, 2011. – P. 53–61.

2. Киреев С.Е. Параллельная реализация метода частиц в ячейках для мо делирования задач гравитационной космодинамики //Автометрия. 2006.

Т.42, № 3. С.32–39.

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

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

В представляемой работе проведено численное решение обратных задач переноса примеси. Для численной реализации обратных задач ис пользовались метод конечного объма и явные разностные схемы высокого порядка точности: схема Ботта [1] и схема ENO [2] для аппроксимации адвективных членов. Все рассмотренные разностные схемы были проте стированы на двумерном уравнении переноса примеси с известным анали тическим решением. При этом было получено, что используемые разност ные схемы высокого порядка точности дают результаты, достаточно близ кие к аналитическому решению.

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

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

Работа выполнена при поддержке гранта РФФИ № 12-01- мол_а и по заданию Министерства образования и науки РФ № 8.4859.2011.

Литература 1. Bott A. Monotone Flux Limitation in the Area – preserving Flux – form Ad vection Algorithm // J. Monthly Weather Review. – 1992. – V.120. – P. 2592– 2602.

2. Chi-Wang Shu. Essentially non-oscillatory schemes for hyperbolic conserva tion laws //Preprint of Division of Applied Mathematics. –Brown University. – 1996. – 92 p.

ФОТОРЕАЛИСТИЧНАЯ ВИЗУАЛИЗАЦИЯ ДВИЖЕНИЯ ЖИДКОСТИ С ИСПОЛЬЗОВАНИЕМ ГРАФИЧЕСКОГО ПРОЦЕССОРА В.В. Заведяев Кемеровский государственный университет, Кемерово На данный момент параллельные вычисления играют огромную роль в моделировании разнообразных физических процессов. С каждым годом производительность вычислительной техники стремительно растет, что позволяет проводить более детальные, точные расчеты. В то же время количество выходных данных, полученных в результате расчетов, пропор ционально увеличивается. Появляется проблема обработки полученных результатов. Уже сейчас графические процессоры позволяют моделиро вать течение жидкости вплоть до нескольких миллионов точек. Но средств визуализации расчетов не так много, а для такой специфичной области, как гидромеханика, – тем более. В связи с данной проблемой и была вы брана тема данной работы.

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

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

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

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

Разработка данного программного средства ведется на языке C++ с использованием графического API OpenGL. На данный момент в програм ме реализован расчет триангуляции Делоне в одном потоке, посчитанные треугольники выводятся на сцену с учетом параметра, цветом, направле нием нормалей. Реализовано свободное перемещение камеры по сцене, применение источников освещения из файла настроек.

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

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

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

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

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

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

Работа выполнена по заданию Министерства образования и науки РФ № 8.4859.2011 и при частичной финансовой поддержке РФФИ, грант 11-02-00918-а.

РЕАЛИЗАЦИЯ МОДЕЛИ МНОГОЧАСТИЧНОГО ГАЗА FHP-MP НА ГИБРИДНОМ КЛАСТЕРЕ А.С. Подстригайло Новосибирский государственный университет, Новосибирск Для имитационного моделирования потоков жидкости и газа в 70-х годах прошлого века было разработано семейство дискретных клеточно автоматных (КА) моделей (решеточные газы – Lattice Gas). Эти модели имеют ряд ограничений, в частности, верхний предел чисел Рейнольдса составляет несколько сотен, граничные условия позволяют задавать только неподвижные твердые объекты (стенки), моделирование околозвуковых скоростей влечет искажение результата и т.д.

Для решения этих проблем в ИВМиМГ СО РАН была предложена новая КА модель, названная FHP-MP (multi-particle) [1]. Она является обобщением классической булевой модели FHP (Frish, Hasslacher, Pomeau), в которой допускается более одной частицы по каждому направ лению скорости.

Процесс моделирования представляет собой итеративный процесс.

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

Первая часть работы посвящена параллельной реализации модели FHP-MP на одном графическом ускорителе. Реализованы алгоритмы столкновения частиц кубической [2] и линейной сложности. Приводятся сравнительные оценки производительности. На графическом ускорителе GTX 680 в зависимости от начальных условий эксперимента было достиг нуто ускорение от 15 до 50 раз по сравнению с последовательной про граммой на процессоре Core i7. Кроме того, было установлено, что в слу чае модели FHP-MP при вычислениях на одной видеокарте не наблюдается дисбаланса вычислительной нагрузки, т.е. планировщик блоков потоков справляется с распределением задачи по вычислительным ядрам видеокар ты самостоятельно и дополнительной балансировки нагрузки в рамках одного ускорителя не требуется.

Вторая часть работы посвящена параллельной реализации модели на нескольких графических ускорителях в рамках одного узла гибридного кластера НКС-30Т+GPU. На двух графических ускорителях Tesla M было достигнуто ускорение в 1,95 раза по сравнению с одним ускорите лем. В ходе экспериментов было установлено, что при равномерном деле нии области вычислений между видеокартами в зависимости от начальных условий вычислительная нагрузка может скапливаться на одном графиче ском ускорителе, что порождает дисбаланс вычислений, негативно сказы вающийся на времени работы алгоритма. В дальнейшем планируются раз работка и реализация алгоритма динамической балансировки нагрузки между графическими ускорителями.

Литература 1. Медведев Ю. Г. Многочастичная клеточно-автоматная модель потока жидкости FHP-MP // Вестник Томского государственного университета. – 2009. – №1(6). – С.33-40.

2. Kalgin K. Optimization of transition rule computation algorithm in multipar ticle lattice gas. // Proc. of Combinatorics. 2010. P. 148.

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

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

На практике самыми популярными алгоритмами сжатия изображе ний являются алгоритмы поблочного кодирования с последующими пре образованиями. Одним из таких алгоритмов является алгоритм фракталь ного сжатия изображений на основе перцептивного хеширования, в кото ром также происходит разбиение изображения на блоки. В данном алго ритме процесс сравнивания блоков является трудоемким из-за итеративно го вычисления, но при этом блоки обрабатываются независимо друг от друга, что способствуют достаточно легкому распараллеливанию вычис лительного процесса. Для быстроты сравнения двух блоков применяется функции перцептивного хеширования. Хеш-функции с большой вероятно стью возвращают разные значения для разных данных и всегда одинако вые значения хешей для одних и тех же данных [1]. Для похожих данных обычные хеш-функции могут возвращать различные значения, а для оди наковых нет. А перцептивное хеширование – это частный случай локаль но-чувствительного хеширования.

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

Оптимизация вычислительных процессов поиска доменных блоков соответствующему ранговому блоку достигается за счет применения более быстрых алгоритмов сравнения [1] и распараллеливания вычислительных процессов на графические процессоры [3]. Распараллеливание происходит на основе технологии CUDA для использования всех возможностей рабо ты со сложной иерархической памятью ускорителей GPU. Используемая для распараллеливания технология CUDA предполагает потоковую модель вычислений. Таким образом, разработан алгоритм фрактального сжатия изображений на основе перцептивного хеширования, адаптированный к особенностям технологии CUDA [3]. Максимально возможное ускорение разработанного алгоритма зависит не только от числа имеющихся процес соров и количества "независимых" частей в выполняемых вычислениях, но и от способов реализации и оптимизации выполняемых вычислений на каждом процессоре (потоке).



Pages:   || 2 | 3 |
 

Похожие работы:





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

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