WWW.DISSERS.RU

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

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

Pages:     ||
|

Описание графа содержится в текстовых файлах, которые можно подать на вход набору программных компонент, осуществляющих преобразование граф-программы в исходный код на C++ с вызовами MPI-функций. Код на С++ c MPI-вызовами компилируется совместно с кодом управляющего MPI-процесса. Управляющий процесс осуществляет непосредственное управление назначениями вершин графа на MPI-процессы, а также осуществляет контроль передаваемых по рёбрам данных во время исполнения получившейся параллельной MPI-программы на многопроцессорной системе.

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

Эта информация используется при назначении вершины на процессор.

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

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

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

Создано специальное приложение, которое анализирует зависимости по данным в C-программе и строит по ним граф зависимости по данным в формате, понимаемом системой «PARUS». Данное программное средство можно считать прототипом автораспараллеливающего компилятора.

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

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

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

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

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

Рисунок 1. Компоненты и связи (преобразование в C++ программу) Рисунок 2. Внутренняя структура ребра граф-программы С каждым ребром графа сопоставляется набор фрагментов данных («чанков»). На рисунке 2 представлена иллюстрация процесса выделения чанков на множестве переменных MPI-программы для ребра графа.

Чанк задаёт фрагмент в области памяти MPI-процесса, который будет сопоставлен с аналогичным фрагментом в памяти другого MPI-процесса. Один чанк связан с определённой переменной в вершине — источнике данных или в вершине — приёмнике данных.

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

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

В пятой главе приведены примеры использования системы «PARUS». Работоспособность системы «PARUS» была протестирована на решении нескольких модельных задач. Система «PARUS» используется для решения конкретных прикладных задач. Как модельные задачи были рассмотрены: распределённая операция над массивом и параллельная реализация перцептрона. В качестве прикладных задач в главе рассмотрены: задача создания параллельной реализации частотного фильтра звуковых сигналов и задача параллельного построения множественного выравнивания нуклеотидных и белковых последовательностей.

В шестой главе обсуждаются результаты тестирования системы «PARUS» на различных многопроцессорных системах. Система «PARUS» была установлена на следующие многопроцессорные вычислительные системы: МВС-1000М, IBM eServer pSeries 690 Regatta и Fujitsu Sun PRIMEPOWER 850. Исследовался характер влияния длины сообщения на время его доставки для многопроцессорных систем различной архитектуры, влияние «фоновых» сообщений на задержки.

Перцептрон был протестирован на машине Regatta. Параллельная реализация перцептрона написана как граф зависимости по данным. Для тестирования был выбран трехслойный перцептрон с большим количеством вершин (до 18500 в одном слое). Для генерации графпрограммы было написано специальное приложение на языке C, которое по заданным характеристикам нейронной сети, а также параметрам группировки нейронов создаёт текстовый файл с описанием графа. Результаты тестирования этой задачи на системе Regatta показали, что при некоторых приёмах группирования нейронов достигается семикратное ускорение, и при увеличении числа нейронов оно стабилизируется.

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

размерность массива – 1 миллиард ячеек, размер одного фрагмента – 1 миллион ячеек. До процессоров ускорение можно считать линейным, причём с коэффициентом наклона больше 0,7. Однако далее кривая становится более пологой: хотя ускорение растёт, но значительно медленнее. Максимальное ускорение, которое было получено, – это 42,7 на 100 процессорах.

В человеческом геноме существуют неоднократно повторяющиеся слабо отличающиеся по последовательности нуклеотидов участки – повторы. Повторы занимают приблизительно 50% от всего размера генома. Как часть работ по совместному проекту Института физикохимической биологии им. А.Н. Белозерского МГУ и Людвиговского института раковых исследований "Ludwig Institute for Cancer Research" (грант CRDF RB01277-MO-2), проводилось исследование одного из типов повторов в человеческом геноме, а именно так называемого LTR класса 5. Важным инструментом для классификации повторов и выявления их свойств, моделирования их эволюции – является инструмент множественных выравниваний. C целью изучения LTR5 и их классификации на машине PRIMEPOWER была установлена система «PARUS». Затем с её помощью была создана параллельная программная реализация для выравнивания последовательностей.

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

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

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

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

В однопроцессорном варианте выравнивание всех известных LTR5 в человеческом геноме занимает 1 час 8 минут. В многопроцессорном варианте на двенадцати процессорах оно же занимает 28 минут, что в 2,4 раза быстрее, чем последовательный вариант. На первый взгляд, эффективность параллельной реализации не очень высокая. Однако, ускорение параллельной реализации для конкретного множества выравниваемых последовательностей будет очень сильно зависеть от сбалансированности построенного кластерного или филогенетического дерева. Кроме всего прочего, в случае уточнения информации о последовательности LTR5 или обнаружения нового экземпляра LTR5 в геноме придётся перестраивать выравнивание. С большим количеством последовательностей или с последовательностями большой длины алгоритм MUSCLE, изначально не параллельный, может работать значительный промежуток времени – до нескольких суток; даже незначительное ускорение для параллельной программы в этом случае может значительно ускорить работу исследователя.

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

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

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

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

Публикации автора по теме диссертации 1. Сальников А.Н. Некоторые технические аспекты инструментальной системы для динамической балансировки загрузки процессоров и каналов связи // Программные системы и инструменты. Тематический сборник № 3 факультета ВМиК МГУ им. Ломоносова. 2002 г., стр. 152-164, ISBN: 5-89407-149-6.

2. Сальников А.Н. Разработка инструментальной системы для динамической балансировки загрузки процессоров и каналов связи // Высокопроизводительные параллельные вычисления на кластерных системах. Материалы Международного научно-практического семинара. Изд-во Нижегородского университета, 2002 г., стр. 159-167, ISBN: 5-85746-681-4.

3. Булочникова Н.М., Сальников А.Н. Разработка прототипа CASE средства создания программ для гетерогенных многопроцессорных систем «PARUS» // Программные системы и инструменты. Тематический сборник № 4 факультета ВМиК МГУ им.

Ломоносова, 2003 г. Издательский отдел факультета ВМиК МГУ. Cтр. 203-209, ISBN: 5-89407-170-4.

4. Сальников А.Н., Сазонов А.Н., Карев М.В. Прототип системы разработки приложений и автоматического распараллеливания программ для гетерогенных многопроцессорных систем // Вопросы Атомной Науки и Техники. Cерия:

Математическое моделирование физических процессов. Министерство Российской Федерации по атомной энергии ФГУП, Российский федеральный ядерный центр – ВНИИЭФ. Научно-технический сборник, выпуск № 1. 2003 г., стр. 61-68.

5. Булочникова Н.М., Горицкая В.Ю., Сальников А.Н. Методы тестирования производительности сети с точки зрения организации вычислений // Труды Всероссийской научной конференции «Научный сервис в сети Интернет 2004».

Издательство Московского университета 2004 г., стр. 221-223, ISBN 5-211-05007-X.

6. Alexeevski A.V., Lukina E.N., Salnikov A.N., Spirin S.A. Database of long terminal repeats in human genome: structure and synchronization with main genome archives // Proceedings of the fours international conference on bioinformatics of genome regulation and structure.

Volume 1. BGRS 2004, Novosibirsk, редакционно-издательский отдел ИЦиГ СО РАН, стр. 28-29.

7. Алексеевский А.В., Лукина Е.Н., Спирин С.А., Сальников А.Н. Структура базы данных длинных терминальных повторов в человеческом геноме и синхронизация данных с основными архивами генной информации // Труды Всероссийской научной конференции «Научный сервис в сети Интернет 2004». Издательство Московского университета, стр. 219, 2004 г., ISBN: 5-211-05007-X.

8. Сальников А.Н. Разработка структуры хранения и организация синхронизации информации по повторяющимся нуклеотидным последовательностям в человеческом геноме // Сборник тезисов Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов - 2004». Том 1. 12-15 апреля 2004 г. МГУ им. М.В. Ломоносова, стр. 28.

9. Булочникова Н.М., Горицкая В.Ю., Сальников А.Н. Система поддержки сбора и анализа статистики о работе вычислительной системы // Методы и средства обработки информации. Труды Второй всероссийской научной конференции. – Москва, издательский отдел факультета ВМиК МГУ. 2005 г., cтр. 136-141, ISBN: 5-89407-230-1.

10. Булочникова Н.М., Горицкая В.Ю., Сальников А.Н. Некоторые аспекты тестирования многопроцессорных систем // Программные системы и инструменты. Тематический сборник № 5 факультета ВМиК МГУ им. М.В. Ломоносова. Москва, издательский отдел факультета ВМиК МГУ, 2005 г., cтр. 73-82, ISBN: 5-89407-216-6.

Pages:     ||
|



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

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