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

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

Якименко Александр Александрович

АЛГОРИТМЫ И ПРОГРАММНЫЙ ИНСТРУМЕНТАРИИ ДЛЯ ГИБРИДНЫХ СУПЕР-ЭВМ В ЗАДАЧАХ ОБНАРУЖЕНИЯ ПОДЗЕМНЫХ ПОЛОСТЕЙ И АНАЛИЗА ГЕНЕТИЧЕСКИХ ДАННЫХ

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

16 ЯНВ 2014 005544428

Новосибирск - 2013

005544428

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Новосибирский государственный технический университет»

Научный руководитель:

доктор технических наук, Федеральное государственное бюджетное учреждение науки Институт вычислительной математики и математической геофизики Сибирского отделения Российской академии наук, главный научный сотрудник Хайретдинов Марат Саматович

Официальные оппоненты: Сергей Николаевич Мамойленко

доктор технических наук, доцент,

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

Деменков Павел Сергеевич

кандидат технических наук,

Федеральное государственное бюджетное учреждение науки Институт цитологии и генетики Сибирского отделения Российской академии наук, научный сотрудник

Ведущая организация:

Федеральное государственное бюджетное учреждение науки Институт вычислительных технологий Сибирского отделения Российской академии наук

Защита состоится «28» января 2014 года в 15 часов на заседании диссертационного совета Д.003.061.02 при Федеральном государственном бюджетном учреждении науки Институт вычислительной математики и математической геофизики Сибирского отделения Российской академии наук, по адресу: 630090, г. Новосибирск, пр-т Академика Лаврентьева, 6.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Институт вычислительной математики и математической геофизики Сибирского отделения Российской академии наук.

Автореферат разослан «25» декабря 2013 г Ученый секретарь

диссертационного совета Д.003.061.02 при ИВМиМГ СО РАН, д.ф.-м.н.

С.Б. Сорокин

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

Актуальность работы. Моделирование с применением суперкомпыотерных информационно-вычислительных технологий является эффективным методом исследования сложных физических процессов, систем и используется во многих областях науки и техники. Параллельный принцип реализации такого моделирования - признанный способ ускорения численных экспериментов. Один из современных подходов к организации параллельного моделирования основан на использовании графических процессоров (GPU -graphics processing unit) в качестве ускорителей к центральным универсальным процессорам (CPU - central processing unit).

Развитие суперкомпыотерных технологий моделирования базируется на фундаментальных работах советских, российских ученых, среди которых: В.В. Воеводин. Г.И. Марчук, В.Г. Хорошевский, Б.И. Четверушкнн, Ю.И. Шокин. H.H. Янснко и др., а также зарубежные ученые: S. Gray, М. Flynn, I. Foster, D. Hillis. С. Kesselman, DL. Slotnick, A. Tancnbaum и другие. При решении задач моделирования сейсмических волновых полей н интерпретации полученных результатов большой вклад внесли исследования в этой области отечественных ученых: A.C. Алексеев. В.В. Адушкин, Б.М. Глинский, А.Ф. Еманов, В.В. Ковалевский. Б.Г. Мнхайленко, A.M. Овчинников, Г.В. Решетова М.С. Хайретдинов и др.

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

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

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

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

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

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

Для этого необходимо:

- разработать и реализовать на гибридном суперкомпьютере НКС-30T+GPU параллельную программу для решения задачи распространения сейсмических волн в сложнопостросиной срсдс, представленной моделью кавернозной зоны;

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

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

Предмет и объект исследования. Объектом исследования являются технологии моделирования сейсмических волновых полей в кавернозных средах и перестановочного теста в задачах генетики. Предмет исследования -

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

Методы исследования. Для достижения цели и поставленных задач применялись методы теории функционирования распределенных гибридных вычислительных систем, теории алгоритмов, статистических вычислений, а также вычислительные методы. Численные эксперименты проводились путем моделирования на гибридном суперкомпьютере ПКС-ЗОТ+GPU и персональной рабочей станции с графическим ускорителем от NVIDIA.

Научные результаты, выноашые па защиту. К основным новым результатам, полученным в диссертации, можно отнести следующие:

- разработанные автором параллельные алгоритмы и программный инструментарий на гибридной супер-ЭВМ HKC-30T+GPU для решения трудоемких задач распространения сейсмических волн в 2D и 3D средах, а также реализации перестановочного теста в задачах генетики. Методологически решаемые задачи объединяются предложенной схемой распараллеливания и представлением структур хранения данных;

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

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

Научная новизна результатов исследования. На базе гибридного суперкомпьютера IIKC-30T+GPU, персональной рабочей станции с

графическими ускорителями и программной технологии CUDA (англ. Compute Unified Device Architecture) получены следующие новые результаты:

- разработаны новые программный инструментарий и алгоритмы па гибридной супер-ЭВМ I1KC-30T+GPU для моделирования сейсмических волновых полей в 2D и 3D сложнопостроенных средах с кавернозными включениями и реализации перестановочного тсста в задачах генетики. Методологически решаемые задачи объединяются предложенной схемой распараллеливания и представлением структур храпения данных;

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

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

Практическая значимость работы. Определяется тем, что на основе разработки и реализации программно-алгоритмического инструментария для гибридного вычислительного комплекса HKC-30T+GPU:

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

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

детерминирующих заданные признаки, при проведении массовых экспериментов;

- разработанные автором профаммные комплексы для геофизического моделирования и реализации перестановочного теста в генетике нашли свое практическое применение соответственно в Институте вычислительной математики и математической геофизики СО РАН и Институте цитологии СО РАН.

Личный вклад автора.

Основные научные результаты, включая результаты моделирования сейсмических волновых полей и интерпретацию полученных результатов численных экспериментов, являются личным вкладом автора. Параллельная профамма для реализации перестановочного теста на гибридном суперкомпьютере разработана и реализована лично автором (прототип последовательной профаммы предоставлен к.б.н. с.u.c. К.В. Гунбнным). Отдельные результаты, представленные в диссертации в главе 3 (анализ, интерпретация записей натурных экспериментов), получены совместно с д.т.н.. с.н.с. М.С. Хайретднповым. Информационно-вычислительная технология решения задачи распространения сейсмических волн в сложнопостроенной среде, представленная моделью кавернозной зоны и ее программным построителем разрабатывалась совместно с к.т.н. Караваевым Д.А..

Соответствие диссертации паспорту специальности. Содержание работы соответствует п. 8 «Модели и методы создания профамм и профаммных систем для параллельной и распределенной обработки данных, языки и инсфументальные средства параллельного профаммирования». п. 9 «Модели, методы, алгоритмы и программная инфраструктура для организации глобально распределенной обработки данных» и и. 10 «Оценка качества, стандартизация и сопровождение программных систем» паспорта специальности 05.13.11 «Математическое и профаммнос обеспечение вычислительных машнн, комплексов и компьютерных сетей».

Апробация и реализация результатов диссертации. Основные результаты диссертации докладывались па следующих конференциях:

- V Международная Азиатская школа-семинар «Проблемы оптимизации сложных систем», Бишкек, 2009 г.;

- конференция молодых ученых ИВМиМГ СО РАН, март 2010г., апрель 2013 г., Новосибирск;

- XII Всероссийская конференция молодых ученых rio математическому моделированию и информационным технологиям, 3-6 октября 2011г. -Новосибирск, 2011г.:

- международная научно студенческая конференция «Студент и научно-технический прогресс», Новосибирск, 2011г.;

- XI Всероссийская конференция с участием иностранных ученых «Проблемы мониторинга окружающей среды», 24-28 октября. 2011- Кемерово;

- VIII между нар. науч. конгресс «Интерэкспо ГЕО-Сибирь-2012», «Дистанционные методы зондирования земли и фотограмметрия, мониторинг окружающей среды, геоэкология»", 17-19 апреля 2012 г., Новосибирск, 2012г.;

- международная Летняя Супсркомпыотерная академия при МГУ, 25 июня - 7 июля 2012г., Москва, 2012г.;

- Всероссийская научно-практическая конференция "Новые технологии в науке о земле и горном деле", 13-21 сентября. - Новый Афон, 2012г.;

Всероссийская научно-практическая конференция «День суперкомиьютерных технологий: наука, образование, промышленность», 20-22 мая. — Новосибирск, 2013;

- отчетные сессии АВТФ-НГТУ, март 2011г., март 2012г, март 2013г. Новосибирск.

Исследования выполнялись в рамках Государственного контракта с Мииобрнаукой № П-857 от 25 мая 2010 г. «Разработка программного обеспечения для высокопроизводительных вычислений в биоинформатике», государственного контракта №14.740.11.0350, грантам РФФИ №№ 10-07-00387-а, 09-07120075. 11-05-92215-Монг_а.

Публикации. Основное содержание диссертации отражено в тринадцати печатных работах соискателя, включая три работы в журналах из списка ВАК и регистрацию программы в Фонде Алгоритмов и Программ СО РАН. Имеются

два акта о внедрении от Института цитологии и генетики СО РАН и Института вычислительной математики и математической геофизики СО РАН.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованных источников из 87 наименований и приложения. Диссертация изложена на 108 страницах основного текста, включая 43 рисунка. 5 таблиц и 2 приложения.

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

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

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

> dt дх + dz

r dt дх dz '

+ (1)

dt дх dz

dt дх dz

doXz _ (dUz , ЗиЛ dt L \дх dz)'

с соответствующими начальными и граничными условиями. их, uz— компоненты скоростей смещений, <тхх, <rzz, <rxz - компоненты тензора напряжений, X, ц параметры Ламе, р - плотность, F(t,x,z) - внешняя возмущающая сила. Необходимо рассчитать компоненты волнового поля ux,uz в течение моделируемого времени.

В (1) предполагается, что параметры к. ¡д. р зависят от пространственных переменных. Для решения поставленной задачи применяется конечно-разностный метод. Используется разностная схема, которая имеет второй порядок аппроксимации по времени и пространству. В §2 представлен программный комплекс для моделирования сейсмических волновых полей в сложнопостроенных средах. Выдвинуты требования к реализации и общая характеристика программного комплекса.

Определены особенности реализации параллельных алгоритмов расчета волновых полей, в основе которого лежит трехмерная декомпозиция расчетной области. По одной координате разрезание происходит средствами MPI (англ. Message Passing Interface), по двум другим - с использованием технологии CUDA. Предложена организация параллельных вычислений на основе топологии MPI GRAPH (Рис 1).

Такой подход к распараллеливанию определяется архитектурой вычислительных средств, имеющихся в Сибирском суперкомпыотерном центре (ССКЦ).

Выполнена оценка времени работы программы в зависимости от количества доступных ядер для архитектур программных реализаций вида: используется только CPU и MPI; используется комбинация CPU и GPU, т.е. MPI и CUDA.

В третьей главе приводится постановка задачи обнаружения и локализации кавернозных зон в проблеме инспекции па месте. Описаны соответствующие вычислительная технология и программа моделирования волновых полей. В §1 представлена обобщенная модель кавернозной зоны с указанием параметров упругости прилегающих слоев. В качестве примера на рисунке 2 показана исследованная 2D модель неоднородной упругой среды с линейными размерами 3.4 км по оси Ох и 1.0 км по оси Oz, содержащая одну подобласть, являющуюся каверной (4). Каверна окружена двумя внешними кольцами: одно из них полностью однородно (3). второе (2). имитирующее зону трещиноватости, заполнено равномерно распределенными включениями (Рис.2)

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

Рис. 2. Схема 20 модели упругой Рис. 3. Рассчитанная синтетическая среды в плоскости хОх сейсмограмма для компоненты и7

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

Источник I Сейсмопригмннкн

К':тс|>И;|

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

В §3 приведены результаты численных экспериментов и выполнена их интерпретация для случая, когда каверна размещается в однородной (рис.2) и слоистой средах. На рисунке 3 показан пример синтетической сейсмограммы для компоненты волнового поля и2. На синтетической сейсмограмме (рис. 3) выделяются несколько групп упругих волн, отмеченных цифрами 1 6. С учетом времен прихода волн к сейсмоприемникам. выделенные группы соответствуют следующим типам волн: 1 - прямая Р-волна: 2 - поверхностная волна Рэлея: 3 - Р-волна. отраженная от каверны: 4 - Б-волна. отраженная от каверны: 5 - НР-волна. отраженная от каверны. 6 - ББ-волна. отраженная от каверны. Таким образом, группы волн, отмеченные цифрами 3 - 6. вызваны присутствием каверны и являются информативным признаком присутствия ее в среде.

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

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

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

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

В §5 приведены показатели ускорения параллельной программы относительно последовательной. Результаты показаны на рисунках 5 и 6.

Рис.5. Результаты расчета для задачи Рис.6. Результаты расчета для задачи с с размерами матриц 2256 х782 размерами матриц 19147 х 898

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

В приложениях представлены копии актов о внедрении результатов кандидатской диссертации и свидетельства о регистрации программы в Фонде алгоритмов и программ СО РАИ.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

1.Разработаны алгоритмы и программный инструментарий для гибридной супер-ЭВМ HKC-30T+GPU для решения рассматриваемых трудоемких задач геоинформатики н биоипформатики. Методологически решаемые задачи объединяются предложенной схемой распараллеливания и представлением структур хранения данных.

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ИССЛЕДОВАНИЯ

1. Якименко A.A., Ковалевский В.В.. Седухина Г.Ф., Хайретдинов М.С., Гсза Н.И., Юшнн В.И. Экспериментальная оценка абсолютных уровней

когерентных сейсмических колебаний с помощью вибрационных технологий. // Технологии сейсморазведки - 2011 - №3 - С. 84-92.

2. Ковалевский В.В., Седухина Г.Ф., Хайретдинов М.С., Якименко A.A., Теза Н.И., Юшин В.И. Технология вибросейсмической нанометрии в проблеме активного мониторинга. // Вестник ИЯЦ PK. - 2012. - №12. - С.48-54.

3. A.A. Якименко, Д. А. Караваев. Численное моделирование распространения упругих волн в средах с подземными полостями на суперЭВМ // Научный Вестник НГТУ. - 2013. - №2. - с. 99-104.

4. Д.А. Караваев, A.A. Якименко, H.A. Караваев. Численное моделирование на суперкомпьютерах в задачах вибросейсмического зондирования сложнопостроенных сред // Проблемы информатики. - 2013. -№3. - с. 65-71.

5. М.С. Хайретдинов, С.А. Авроров, Г.Ф. Седухина, A.A. Якименко. Оценивание сейсмоакустических эффектов техногенных взрывов с помощью сейсмических вибраторов. // Мат. XI Всероссийской конференции с участием иностранных ученых «Проблемы мониторинга окружающей среды», 24-28 октября, - Кемерово, 2011 - С. 118-122.

6. Yakimenko A.A., Khairetdinov M.S., Glinsky B.M., Karavaev D.A., Martynov V.N., Algorithms and methods for the numerical simulation os seismic wave fields in cavernous zones. // Bulletin of the Novosibirsk computing center, Math. Model. In Geoph. - 2010 - №13 - P. 71-78.

7. Авроров C.A., Якименко A.A. Применение сейсмических вибраторов для исследования сейсмоакустических эффектов и геоэкологической угрозы от техногенных взрывов. // Мат. XII Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям, 3-6 октября 2011г. - Новосибирск, 2011 - С. 43.

8. Караваев Д.А., Якименко A.A. Численное моделирование и исследование поля упругих волн для кавернозных сред // Материалы XLIX Международной научной студенческой конференции «Студент и научно-технический прогресс», Новосибирск, 2011, с. 252.

9. Якименко A.A. Использование гибридных вычислительных систем для численного моделирования волновых полей. // Сб. мат. VIII междунар. науч. конгресса «Интерэкспо ПЮ-Сибирь-2012», «Дистанционные методы зондирования земли и фотограмметрия, мониторинг окружающей среды,геоэкология»". - Новосибирск: СГГА, 2012. - Т. 1. - С. 85-89.

10. Якименко A.A. Преимущества применения GPU для численного моделирования 3D сейсмических волновых полей разностным методом. // Сб. мат. междунар. конф. "Современные вопросы науки и образования - XXI век". - Тамбов: изд-во ТРОО "Бизнес-Наука-Общество», 2012. - Ч. 6. - С. 158-161.

11. С. А. Авроров, Г.М. Воскобойникова, Г.Ф. Седухина, М.С. Хайретдинов, A.A. Якименко. Вибрационная технология оценивания геоэкологических рисков.//Мат. Всеросс. науч.-практ. конф. "Новые технологии в науке о земле и горном деле", 13-21 сентября. - Новый Афон, 2012.

12. A.A. Якименко. Разработка и исследование параллельной реализации программы перестановочного теста в генетике // Труды конференции молодых ученых. - Новосибирск, 2013. - с. 190-199.

13. Губарев В.В., Хайретдинов М.С., Альсова O.K., Абалов Н.В., Якименко A.A.. Нетрадиционные подходы к обработке сейсмических сигналов // Труды IX международной азиатской школы-семинара «Проблемы оптимизации сложных систем». - Алматы, 2013. - с.92-94.

Отпечатано в типографии Новосибирского государственного технического университета 630073, г.Новосибирск, пр. К. Маркса, 20, Тел./факс (383) 346-08-57 Формат 60 х 84/16. Объем 1 п.л. Тираж 100 экз. Заказ 87. Подписано в печать 23.12.2013 г.

j

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Новосибирский государственный технический университет»

АЛГОРИТМЫ И ПРОГРАММНЫЙ ИНСТРУМЕНТАРИЙ ДЛЯ ГИБРИДНЫХ СУПЕР-ЭВМ В ЗАДАЧАХ ОБНАРУЖЕНИЯ ПОДЗЕМНЫХ ПОЛОСТЕЙ И АНАЛИЗА ГЕНЕТИЧЕСКИХ ДАННЫХ

05.13.11 - «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»

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

04201454927

Якименко Александр Александрович

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель д.т.н. Хайретдинов М.С.

Новосибирск - 2013

Оглавление

Введение...........................................................................................................5

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

1.1 Общие сведения..................................................................................17

1.2 Проблема инспекции на месте...........................................................17

1.3 Подходы к решению задач моделирования сейсмических волновых полей...................................................................................................................20

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

1.5 Характеристики используемых вычислительных средств.............24

1.6 Выводы.................................................................................................26

2. Задача моделирования сейсмических волновых полей в сложнопостроенных средах.................................................................................28

2.1 Постановка двумерной задачи моделирования сейсмических волновых полей.................................................................................................28

2.2 Программный комплекс для моделирования сейсмических волновых полей в трехмерных сложнопостроенных средах........................30

2.2.1 Требования к реализации и общая характеристика программного комплекса..............................................................................30

2.2.3 Построитель ЗБ модели неоднородной сложно построенной упругой среды................................................................................................35

2.2.4 Программа для моделирования волновых полей в ЗБ неоднородных упругих средах....................................................................38

2.2.5 Верификация построителя моделей...........................................40

2.2.6 Оценка времени работы программы..........................................45

2.3 Выводы.................................................................................................46

3 Задача обнаружения и локализации кавернозных зон в проблеме ИнМ........................................................................................................................47

3.1 Постановка задачи..............................................................................47

3.2 Вычислительная технология и средства моделирования...............51

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

3.4 Технология вибрационного просвечивания земной коры..............59

3.4.1 Результаты регистрации и измерения абсолютных уровней колебаний от вибратора ЦВ-100..................................................................65

3.4.2 Результаты регистрации и измерения абсолютных уровней колебаний от вибратора ЦВ-40....................................................................69

3.4.3 Преимущества подхода и итоги выполнения работ.................77

3.5 Выводы.................................................................................................78

4 Применение информационно-вычислительных технологий в задачах генетического анализа. Опыт реализации перестановочного теста на графическом процессоре.......................................................................80

4.1 Обзор проблемы и подход к решению..............................................80

4.2 Методика решения задачи..................................................................81

4.3 Алгоритм перестановочного теста для последовательной версии на языке С...............................................................................................................83

4.4 Реализация на графическом процессоре...........................................86

4.5 Производительность параллельной и последовательной версий программ............................................................................................................89

4.6 Выводы.................................................................................................91

Заключение....................................................................................................92

3

Список использованных источников..........................................................94

Приложение А. Акты о внедрении............................................................106

Приложение В. Свидетельство регистрации программы.......................108

Введение

Актуальность работы. Моделирование с применением суперкомпьютерных информационных технологий является эффективным и широко распространенным методом исследования сложных физических процессов и систем и используется практически во всех отраслях науки и техники. Параллельный принцип реализации такого моделирования -признанный способ ускорения численных экспериментов. Один из современных подходов к организации параллельного моделирования основан на использовании графических процессоров (GPU - graphics processing unit) в качестве ускорителей к центральным универсальным процессорам (CPU -central processing unit).

Развитие суперкомпьютерных технологий моделирования базируется на фундаментальных работах советских, российских ученых, среди которых: Е.П. Балашов, В.Б. Бетелин, B.C. Бурцев, В.В. Васильев, В.В. Воеводин, В.Ф. Евдокимов, Э.В. Евреинов, A.B. Забродин, В.П. Иванников, М.Б. Игнатьев, A.B. Каляев, С.А. Лебедев, В.К. Левин, Г.И. Марчук, Д.А. Поспелов, И.В. Прангишвили, Г.Е Пухов, A.A. Самарский, В.Б. Смолов, А.Н. Томилин, Я.А. Хетагуров, В.Г. Хорошевский, Б.Н. Четвертушкин, Ю.И. Шокин, H.H. Яненко, а также зарубежные ученые: S. Gray, М. Flynn, I. Foster, D. Hillis, С. Kesselman, DL. Slotnick, A. Tanenbaum и другие. При решении задач моделирования сейсмических волновых полей и интерпретации полученных результатов большой вклад внесли исследования в этой области отечественных ученых: A.C. Алексеев, В.В. Адушкин, Б.М. Глинский, А.Ф. Еманов, В.В. Ковалевский, Б.Г. Михайленко, A.M. Овчинников, Г.В. Решетова М.С. Хайретдинов и др.

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

проведения скрытых подземных ядерных взрывов [2, 11] и генетической детерминации признаков.

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

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

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

Объект исследования. Технологии моделирования сейсмических волновых полей в кавернозных средах (задача геофизики) и перестановочного теста в задачах генетики.

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

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

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

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

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

В рамках диссертационной работы:

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

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

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

В диссертации поставлены и решены следующие задачи:

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

- разработать и реализовать на гибридном суперкомпьютере НКС-ЗОТ параллельную программу для решения задачи распространения сейсмических волн в сложнопостроенной среде, представленной моделью кавернозной зоны;

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

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

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

Методы исследования. Для достижения цели и поставленных задач применялись методы теории функционирования распределенных вычислительных систем, теории алгоритмов. Численные эксперименты проводились путем моделирования на гибридном суперкомпьютере НКС-ЗОТ и персональной рабочей станции с графическим ускорителем от NVIDIA. Для обработки исходных вибросейсмических сигналов использовался метод кросскорреляционной свертки.

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

разработаны программный инструментарий и алгоритмы с использованием гибридной супер-ЭВМ НКС-ЗОТ для моделирования сейсмических волновых полей в 2D и 3D сложнопостроенных средах с кавернозными включениями и реализации перестановочного теста в задачах генетики. Методологически решаемые задачи объединяются предложенной схемой распараллеливания и представлением структур хранения данных;

- выполнено численное моделирование волновых полей для случаев

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

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

групп. Показано, что в качестве информативных выделяются группы S-, SP-,

8

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

- оценена производительность разработанных программ при решении задачи перестановочного теста на реальных данных объемом 19147x898. Показано, что за счет перехода к матричному формату представления данных и распараллеливания задачи на графических процессорах достигается ускорение решения до 150 раз;

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

- внедрены и успешно используются разработанные параллельные программы для супер-ЭВМ НКС-30Т в Институте цитологии и генетики СО РАН и Институте вычислительной математики и математической геофизики СО РАН.

Практическая ценность результатов работы.

1. Разработана и реализована на базе гибридного вычислительного комплекса НКС-30Т суперкомпьютерная информационно-вычислительная технология для моделирования сейсмических волновых полей в сложнопостроенных средах с включениями неоднородности типа кавернозной зоны.

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

3. Разработаны параллельные алгоритмы и программы реализации перестановочного теста на гибридном суперкомпьютере НКС-30Т, которые будут способствовать ускорению решения задачи генетической детерминации признаков на основе данных массовых экспериментов.

4. Разработанные автором программные комплексы для геофизического моделирования и реализации перестановочного теста в генетике нашли свое практическое применение соответственно в Институте вычислительной математики и математической геофизики и Институте цитологии СО РАН.

Реализация и внедрение результатов работы.

Исследования выполнялись в рамках Государственного контракта с

Минобрнаукой № П-857 от 25 мая 2010 г. «Разработка программного

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

государственного контракта №14.740.11.0350, грантам РФФИ 10-07-00387-а

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

геоинформационной технологии оценивания экологического риска от

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

сейсмических вибраторов», 11-05-92215-Монг_а «Исследование

характеристик волнового поля мощного вибратора для целей

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

Сибирского региона», 11-07-10000-к «Организация и проведение

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

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

сейсмических вибраторов», 12-05-00786-а «Исследование

сейсмовулканических процессов Эльбрусской вулканической области на

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

низкоэнергетических сейсмических событий», Программе СО РАН 1.4.1.

«Математическое моделирование в задачах геофизики, физики океана и

атмосферы и охраны окружающей среды», Междисциплинарному проекту

СО РАН № 54 - "Развитие методов математического моделирования

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

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

проекты НГТУ-СО РАН № С1-13 «Мониторинг гидроразрыва пласта на

основе решения прямой и обратной задач восстановления трещиноватости

нефтяного коллектора», №С1-20 «Разработка и проведение теоретических и

10

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

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

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

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

Основные защищаемые положения. Основными защищаемыми положениями диссертационной работы являются:

1. Разработанные параллельный программный инструментарий и алгоритмы с использованием супер-ЭВМ НКС-ЗОТ для моделирования сейсмических волновых полей в 2Т> и ЗБ сложнопостроенных средах с кавернозными включениями. Отличительная особенность созданных средств связана с построителем численной модели среды сложной конфигурации, а также с оригинальной топологией организации параллельных вычислений на гибридном вычислительном комплексе НКС-ЗОТ.

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

3. Разработанные и реализованные в интересах решения задачи генетики параллельные алгоритмы и программы перестановочного теста на гибридном суперкомпьютере НКС-ЗОТ и оценки их времени выполнения.

Личный вклад автора.

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