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

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

005018YUO

-сЪ.

Амиршахи Бита

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

05. ¡3.15. — «Вычислительные машины, комплексы и компьютерные сети»

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

Москва - 2012

005018705

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

Научный руководитель - доктор технических наук, профессор

Барский Аркадий Бенционович

Официальные оппоненты - доктор технических наук, профессор

Доенин Виктор Василевич, МИИТ, заведующей кафедрой МО АСУ

Ведущая организация - Научно-исследовательский и проектно-конструкторский институт информатизации, автоматизации и связи на железнодорожном транспорте, ОАО «НИИАС»

Защита диссертации состоится 27 Марта 2012 г. в 15:00 часов на заседании диссертационного совета Д 218.005.10 при Московском государственном университете путей сообщения (МИИТ) по адресу: 127994, ГСП-4, г. Москва, ул. Образцова, 9, стр. 9, ауд. 1235.

С диссертацией можно ознакомиться в библиотеке МИИТа. Автореферат разослан «27» февраля 2012 года.

кандидат технических наук Смирнова Елена Викторовна, Компания «Д-Линк Интернешнл ПТЕЛтд», менеджер

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

Соловьёв В.П.

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

Актуальность темы. Тема исследований является актуальной. Решение поставленных в соответствии с ней задач позволяет на практике оптимально реализовать принцип распределённых вычислений с учётом высоких требований к структуре обмена, обусловленных алгоритмом решения задач. Это тем более важно, что идеи СЛ/£>-вычислений, рассматриваются как ждущие воплощения в ближайшее будущее, как выполнение распределённой обработки данных на основе сетевых технологий.

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

Объект исследований. Объектом исследования являются

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

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

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

2. Разработан новый параллельный алгоритм кластеризации ресурсных процессоров вычислительной сети. Применение этого алгоритма кластеризации позволило получить дальнейшее снижение времени распределённых вычислений с количества процессоров порядка 15 до привлечения гораздо большего количества процессоров (порядка 90). При этом время решения тестовой задачи сокращается в 2000 раз.

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

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

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

Апробация работы. Основные результаты диссертации докладывались и обсуждались на ежегодных научных конференциях МИИТа (Неделя науки «Наука МИИТа - транспорту» в 2009, 2011 гг.); на IV международной научно-студенческой конференции в неделю науки Ирана, в 2010 г.; на VII международной научно-практической конференции студентов и молодых ученых «Trans-Mech-Art-Chem», МИИТ в 2010 г.; на 26th IEEE International Parallel & Distributed Processing Symposium, Shanghai, China, в 2011 г.; на IX международной конференции «Mathematical and Informational Technologies, MIT-2011» , Vrnjacka Banja, Serbia, в 2011 г.

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

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

2. Показана возможность значительного увеличения числа процессоров, с вводом в использование которых время решения задачи убывает. Так, для размерности задачи п это количество используемых процессоров возросло с 15 (кластеризация не производилось) до порядка 90. Общее время решения задачи сокращается в 2000 раз.

3. Получены зависимости времени решения задачи от числа процессоров с учётом их кластеризации. Они позволяют в будущем создать методику оптимального назначения вычислительных ресурсов. Публикации. По теме диссертации опубликовано 10 работ, из них 2 работы в ведущих изданиях из перечня, определенного ВАК России для опубликования основных результатов диссертаций.

Структура и объем диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы (34 источников) и приложения. Работа изложена на 117 страницах машинописного текста, включая 22 рисунков, 7 таблиц, 1 приложение на 2 страницах. Основные научные положения, выносимые на защиту:

1. Разработана тестовая задача на основе решения системы линейных уравнений методом Крамера для исследования схемы распределённых вычислений типа «раздача заданий - решение - сбор результатов вычислений».

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

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

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

5. Предложенный алгоритм ПАК почти в 100 раз быстрее (по сравнению с известными) формирует трафик для сборки данных при реализации распределённых GRID- вычисленный по изучаемой схеме.

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

значения ~ 24. Общее время решения задачи при этом сокращается в 16 раз.

7. Построены зависимости времени решения тестовой задачи для общего случая применения суперкомпьютера «СКИФ». Графики позволяют выявить недопустимый рост времени решения.

8. Разработана схема распределенного решения теста - системы линейных уравнений методом Крамера на кластерном суперкомпьютере МИИТ СКИФ Т-4700 и произведено моделирование с использованием предложенного алгоритма кластеризация ПАК. Без применения этого алгоритма «точка насыщения», где введение новых процессоров приводит к уменьшению времени решения задачи (фиксированной размерности), наступает при числе процессоров, равном 15. Применение алгоритма ПАК позволяет значительно отдалить «точку насыщения» до значения ~ 96. Общее время решения задачи сокращается в 2000 раз.

9. Количество выбранных процессоров полностью соответствует SPMD-технологии.

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

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

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

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

Рис 1. Определение точки насыщения, где (-время решения, п- число процессоров, х-точка насыщения

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

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

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

Во второй главе диссертации автором предложен новый параллельный алгоритм кластеризации (ПАК) СЫГО-ресурсов для оптимизации информационного обмена при совместной обработке результатов распределённых вычислений.

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

является требование к устойчивости по отношению к большим объёмам структурируемых данных.

Как известно, существует 3 методы кластеризации точек данных:

1. Иерархическая кластеризация отображается деревом, где концевые вершины - процессоры разбиваются на кластеры. Затем рекурсивно эти кластеры объединяются по парам, образуя кластеры более высокого уровня. Так - до достижения общего кластера корневого уровня.

2. Разделенная кластеризация: Процессоры объединяются в кластеры на основе их «близкого» (по некоторой метрике) расположения относительно образовавшегося центра

3. «Ящик» кластеризации: Этот метод подразумевает разделение всего пространства компьютеров на подпространства, возможно перекрывающихся, «ящиков». Кластеризация при распределении вычислений определяется принадлежностью компьютеров «ящикам».

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

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

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

Алгоритм Прима. Предварительно рассмотрим прототип - не параллельный алгоритм Прим, от которого будем отталкиваться при построении алгоритма ПАК.

Алгоритм Прима допускает распараллеливание при графической реализации метода одинарной связи (Single Link). Этот алгоритм заключается в построения минимального покрывающего дерева взвешенного связного неориентированного графа, объединяющего точки данных, т.е. компьютеры, выработавшие данные для обмена. Минимальное покрывающее дерево — это остовое дерево графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер. Построение начинается с дерева, включающего в себя одну (произвольную) вершину. В процессе работы алгоритма дерево разрастается, пока не охватит все вершины исходного графа. На каждом шаге алгоритма к текущему дереву

присоединяется самый «легкий» из рёбра, соединяющих вершину из построенного дерева, и вершину не из дерева.

Прежде, чем объяснить алгоритм ПАК, необходимо познакомиться с понятием метрики для проведения кластеризации. Эти метрики используются для агломерации или для определения расстояния до минимального покрывающего дерева. Поскольку в предложенном ниже алгоритме кластеризации целесообразно использовать только, метрики Евклидово и Манхэттен, приведём таблицу этих, практически применяемых метрик.

Табл. 1. Методы оп Название расстояния «деления расстоянии между точками данных Формула

Евклидово 11« - ь\\2 = /О* - &02 V £

Манхэттен \\a-b\U =Е г

где а и Ь -точки данных

Построение Параллельного Алгоритма Кластеризации ПАК

Пусть граф в = (Е, V) - граф, связывающий точки данных, где Е -множество дуг и К - множество вершин.

Построим МБТ(С) - минимальное покрывающее дерево графа в. Алгоритм ПАК предполагает следующие основные шаги.

• Разделение С на 5 подграфов, С, = {(Ер .....^ где позже в этом

разделе будет определяться стоимость 5; V, - множество вершин в Ор

и £} С £ - множество дуг, соединяющих вершины V/,

• Выделение двудольных графов В,, = {К и V,, Ец}, где V, и V, являются множествами вершин О, и С,р и £у С £ -множества дуг между вершинами V, и вершинами Уь г ф у, для каждой такой пары подграфов из

• Параллельное построение минимального покрывающего дерева (Т),) на каждом С, и минимального покрывающего дерева (Т„) на каждом В„.

• Построение нового графа С" = , /</</£?, по

объединению всех минимальных покрывающих деревьев на предыдущем шаге. Граф С° является подграфом графа в с множеством вершин V и дуг деревьев Т,,, /</</<$.

• Построение минимального покрывающего дерева (МБТ(0°)) на графе в" (рис. 2).

Доказано, что М8Т(С°) = ЖГ(О).

Рис. 2. Алгоритм ПАК - Построение минимального покрывающего дерева (MST(G°)) на графе G0.

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

При этом следует воспользоваться кучей Фибоначчи для каждого подграфа G„ и каждого двудольного графа B,h чтобы облегчить операцию «поиска следующей маленькой дуги» в алгоритме Прима, который имеет оценку сложности О (\Е\ + \ V\ log(\V\)) для построения каждого подграфа G„ и О (\Vi\\Vj\+(\Vi\ + \Vj\log(\V,\ + \Vj\)) для формирования каждого двудольного графа.

Очевидно, что время построения MST T(D, V) зависит от V и D, где V - числа объектов и D - размерности объектов. Покажем, что время построения MST зависит также от числа 5 подграфов. Определим оптимальное число s.

Время выполнения шага предварительной обработки параллельного алгоритма, на основе использования s(s+l)/2 процессоров, равно

max { max RT (<GJ, max RT (В,}}, где RT (G,) и RT (B,j) - время построения

1 <=/<=! !<=/<=.(

графа Gj и

Необходимо вычислить число s разделов множества V, которое минимизирует max { max RT (GJ, max RT (В,)}.

1<=/<=.V 1<=/<=Л

rlf • _ ^

Введем новые переменные aha2,...,as, ~~ , ai >0, так, что

\Vi\~ a, \V\, aha2.....av представляют собой вариант разбиения

вершин. Таким образом, мы имеем: |£/| = \У]2 а,2 /2 и |£,/| =

Игнорируя значительно малый второй член в RT, получим выражение для минимизации F(a,,a2,...,aJ = max (тах^ (а, /Д тад (ар)}

„аЕ?=1т= 1 „

Очевидно, что чем больше число произведённых разбиении (ускоряющее одновременное построение минимального покрывающего дерева), тем больше число дуг образуется в графе G0 (что следует из увеличения времени построения оригинального окончательного минимального покрывающего дерева на последнем шаге). Поэтому, до нахождения времени объединения всех минимальных покрывающих деревьев TM(s, V), необходимо узнать оптимальное значение s.

Результат многих экспериментов показал, что если s=2, min(F(ahaT)\ а,+а2 = 1} = 2/9 достигается при а, -- 1/3 и а2 = 2/3. Тогда такое разделение на два подграфа будет оптимальным при условием а2 = 2ah

Для s>2 оптимальное число разбиений достигается при а, = l/s, i =

1,2.....5 , и mm{F(a,,...,aJ|2f=ifl' = 1 } = \V\2 / i2- То есть, для s>2

оптимальное число разбиений будет достигнуто при V, = l/s, i - 1,2.....5 или

при |F,1=1^1 •

Время построения полного окончательного графа находится по формуле (1):

T(D, V,s) = T„(D, V/s) + TM(s, V) (1)

где Тц0-время построения двудольных графов и Тм()-время объединения всех минимальных покрывающих деревьев.

Время построения полного графа зависит не только от D и V где V -числа объектов, D - размерности объектов, но и от числа s подграфов. Поэтому необходимо узнать оптимальное значение 5.

Теперь, проверим эффективность алгоритма ПАК, т. е. сравнительное время выполнения на множестве 1000000 точек. На первом шаге построим график зависимости времени построения минимального

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

Яопт (РИС. 3) .

Например, для этого положим размерность О = 80.

Рис. 3- График зависимости времени построения минимального покрывающего лерева от числа подграфов.

На основе анализа полученного графика можно считать, что з0„т равно 14.

Рассчитаем ускорение 677, (В, V), получаемое при построении минимального покрывающего дерева с использованием параллельных вычислений по сравнению с применением одного процессора:

1)

811Г(0,У)=

(2)

Результаты, отражённые в таблице 2 показывают, что алгоритм ПАК может решить проблему кластерной идентификации, на множестве данных с 1000000 точек на графе, почти в 90-100 раз быстрее, чем на единственном процессоре. Это доказывает преимущества алгоритма ПАК.

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

Табл. 2. Теоретический SU Коэффициент Ускорения Параллельного

Конструкция MST, по сравнению с реализацией Одиночного процессора.

V D 5 Расстояние

Евклидово Манхэттен

SU SU

250,000 20 9 20 21

500,000 40 10 42 43

750,000 60 13 65 67

1,000,000 80 14 90 93

В третье главе изложены методы и обоснован план решения тестовой задачи решения «большой» системы линейных уравнений на вычислительной сети и на суперкомпьютере кластерного типа МИИТ Т- 4700 (СКИФ).

В данной работе использовался суперкомпьютер МИИТ Т-4700, который создан на базе 64-х двухпроцессорных узлов Discus с четырехъядерными процессорами AMD Opteron™ (Barcelona) и обеспечивает пиковую производительность 4,7 триллионов операций в секунду (TFlops). Реальная производительность кластера на тесте Unpack составила 3,89TF/ops (82% от пиковой). Благодаря объединению всех составляющих новой информационной системы высокоскоростной сетью InfiniBand, доступ к суперкомпьютеру осуществляется непосредственно через университетский портал, что существенно упрощает процесс исследований и разработок.

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

Пусть:

s- Число подграфов. А- Исходная матрица системы: а п................. а,„

............

В- Столбец свободных членов: 'Ь,

Процесс распределённых вычислений реализуется по SPMD- технологии

при наличии головного процессора.

Представим алгоритм организации вычислении по шагам:

1. Инициализация параллельной программы. Начало фазы «раздача заданий».

2. Ввод количества процессоров п.

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

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

5. Проверка номера процессора. Если этот номер равен нулю, осуществляется переход на следующий шаг, иначе - на шаг 11.

6. Ввод исходной матрицы А.

7. Ввод исходной матрицы В.

8. Проверка условия не равенства определителя системы (Д) нулю. Для этого с помощью функций «определитель» процессор находит определитель матрицы А. Если определитель равен нулю, на экране, появиться сообщение «No Answer!». В противном случае выполняется следующий шаг.

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

10. Установление времени начала вычислений.

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

12. Вызов функции «определитель».

13. Каждый процессор по исходной матрице А находит столбец, номер которого соответствует номеру этого процессора, и на его место вставляет столбец В.

14. Вычисление значения полученного определителя.

15. Деление определителя, полученного на предыдущем шаге, на определитель Д. Получен один корень системы уравнений.

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

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

18. Сбор результатов продолжается по дереву, таким образом, пока они все не соберутся в нулевом процессоре, т.е. на головном процессоре в центре в ЯГО-технологий.

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

20. Определение продолжительности вычисленного процесса с помощью времени окончания и начала.

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

22. Завершение параллельной программы.

23. Выход.

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

- без применения кластеризации,

- с помощью алгоритма кластеризации ПАК.

Моделирования метода Крамера в вычислительной сети предлагает следующие шаги:

Шаг 1) Сравнение параллельных и последовательных методов решения задачи.

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

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

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

Вывод: Проблема в сборе данных и это не удивительно. Ведь, несмотря на то, что процесс вычисления реализуется параллельно, сбор результатов является последовательным процессом.

Предложенное решение: Применение параллельного алгоритма кластеризации (ПАК) для организации быстрого сбора результатов.

Шаг 2) Сравнение метода сбора данных без применения алгоритма ПАК, с методом сбора данных с применением алгоритма ПАК.

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

Ниже изложена попытка оптимизации ОНО-вычислений при решении систем линейных уравнений с помощью метода Крамера на суперкомпьютере кластерной архитектуры МИИТ СКИФ Т -4700. Результаты измерений представлены в таблице 3.

Отметим, что количество выбранных процессоров полностью соответствует БРМО-технологии.

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

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

Здесь:

Значение <выч - время вычисления в секундах.

Значение п - количество процессоров.

Значение £>- число подграфов.

Табл. 3. Результаты измерений

1выч (сек) 1аыч Без кластеризации ^выч с кластеризацией

п О

2 10 0 0

3 15 0 0

4 20 0 0

7 35 0,686 0

8 40 2,215 0

10 50 80,979 0

11 55 669,13 0,241

12 60 8045,09 3,844

15 75 18500,1 5,013

16 80 оо' 21,741

24 120 оо 43.182

32 160 со 64,193

40 200 00 941,535

48 240 00 1151,124

56 280 ОО 1749,69

64 320 00 2753,219

80 400 оо 5122,683

96 480 00 16843,863

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

' - Значение со условно обозначает, что времени ожидания результатов является больше чем суток.

л- число процессоров

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

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

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

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

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

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

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

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

Типичным примером задач, предъявляющих высокие требование к обмену, является задача решения систем линейных уравнений. Её распределённое решение по SPMD- технологи возможно лишь в случае применения метода Крамера. Эта задача может служить тестом для проводимых исследований.

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

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

1. Разработана тестовая задача на основе решения системы линейных уравнений методом Крамера для исследования схемы распределённых вычислений типа «раздача заданий - решение - сбор результатов вычислений».

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

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

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

5. Предложенный алгоритм ПАК почти в 100 раз быстрее (по сравнению с известными) формирует трафик для сборки данных при реализации распределённых GRID- вычисленный по изучаемой схеме.

6. Разработана схема распределенного решения теста системы линейных уравнений в вычислительной сети и произведено моделирование решения этой системы с использованием предложенного алгоритма кластеризация ПАК. Сравнительная оценка показала, например, что без применения этого алгоритма «точка насыщения», где введение новых процессоров приводит к уменьшению времени решения задачи (фиксированной размерности), наступает при числе процессоров равном 12. Применение алгоритма ПАК позволяет значительно отдалить «точку насыщения» до значения ~ 24. Общее время решения задачи при этом сокращается в 16 раз.

7. Построены зависимости времени решения тестовой задачи для общего случая применения суперкомпьютера «СКИФ». Графики позволяют выявить недопустимый рост времени решения.

8. Разработана схема распределенного решения теста - системы линейных уравнений методом Крамера на кластерном суперкомпьютере МИИТ СКИФ Т-4700 и произведено моделирование с использованием предложенного алгоритма кластеризация ПАК. Без применения этого алгоритма «точка насыщения», где введение новых процессоров приводит к уменьшению времени решения задачи (фиксированной размерности), наступает при числе процессоров, равном 15. Применение алгоритма ПАК позволяет значительно отдалить «точку насыщения» до значения ~ 96. Общее время решения задачи сокращается в 2000 раз.

9. Количество выбранных процессоров полностью соответствует SPMD-технологии.

ОСНОВНЫЕ ПОЛОЖЕНИЯ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В СЛЕДУЮЩИХ РАБОТАХ:

Публикации в изданиях из перечня ВАК

1. Кластеризация GRID-Ресурсов для оптимизации информационного обмена при совместной обработке результатов распределённых вычислений. // Информационные технологии, 2011, No 2, Стр. 22 - 28.

2. GRID- технологии решения больших систем линейных уравнений на вычислительной сети и на суперкомпьютера кластерного типа. // Информационные технологии, 2011, No 6, Стр. 17 - 22.

Монография

3. Бита Амиршахи, «Оптимизация межрусурсного обмена в распределенных GRID- вычислениях», монография - М: Saarburken, Germany, LAP LAMBERT Academic Publishing GmbH & Co. KG, 2012.

Прочие публикации

4. NGN & adHoc networks, // III международная научно-студенческая конференция в неделю науки Ирана, Керман Государственный университет, Иран, 2009.

5. Параллельные методы кластеризации GRID-ресурсов при совместной обработке результатов распределённых вычислений. // Международная научная конференция «Актуальные вопросы современной технически и технологии», г. Липецк, Российская Федерация, 2010.

6. Parallel Algorithms for Hierarchical Clustering in computer Networks // VII международная научно-практическая конференция студентов и молодых ученых «Trans-Mech-Art-Chem», МИИТ, Moscow, Russia, 2010.

7. Parallel Cluster Algorithm for Solving Large Linear Equation Systems, Using GRID-Technology and Cramer's Rule, on a Supercomputer.// 26th IEEE International Parallel & Distributed Processing Symposium, Shanghai, China, May ,2011.

8. Оптимизация обмена в GRID- системах- труды научно-практической конференции Неделя науки «Наука МИИТа - транспорту»,2011.

9. Локально-сетевая модель параллельного решения задачи линейного программирования, Ш-ой межрегиональной научно-методической конференции «АКТУАЛЬНЫЕ ПРОБЛЕМЫ СОВРЕМЕННОГО ОБРАЗОВАНИЯ», Воронежский институт экономики и социального управления, 15 февраля 2011 г.

10. Новый алгоритм кластеризации GRID-ресурсов для оптимизации информационного обмена в распределённых вычислениях, International Conference «Mathematical and Informational Technologies, М1Т-2011» IX Conference «Computational and Informational Technologies for Science, Engineering and Education», Vrnjacka Banja, Serbia, August, 27-31, 2011

Амиршахи Бита

ОПТИМИЗАЦИЯ МЕЖРЕСУРСНОГО ОБМЕНА ПРИ СБОРКЕ ДАННЫХ В РАСПРЕДЕЛЁННЫХ GRID - ВЫЧИСЛЕНИЯХ НА ОСНОВЕ СЕТЕВЫХ И СУПЕРКОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ 05.13.15 - «Вычислительные машины, комплексы и компьютерные сети»

Подписано к печати 21.02.2012г. Тираж 80 экз. Заказ № 411

Объем 1,5 п.л. Формат 60x84/16

УПЦ ГИ МИИТ, 127994, Москва, ул. Образцова, 9, стр. 9

61 12-5/1870

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫШСЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ» (МИИТ)

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

АМИРШАХИБИТА

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

05.13.15 —

«Вычислительные машины, комплексы и компьютерные сети»

ДИССЕРТАЦИЯ

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

Научный руководитель: Профессор д.т.н. Барский А.Б.

МОСКВА, 2012 г.

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

Оглавление

Введение 6

Глава 1. Параллельные и распределённые информационные технологии в основе СК/О-системы и их эффективность................. 19

1.1. Проблема оптимизация межрессурсного обмена в распределённых ОКГО-вычислениях........................................... 19

1.2. Распараллеливание, его сложность и необходимость...... 21

1.3. Определение ОШБ-технологий................................. 24

1.4. Основные направления исследований в области ОШО-технологий........................................................................... 25

1.5. Методологические и технологические особенности выполнения пакета параллельных прикладных программ. ЭРМБ-технология............................................................................ 30

1.6. Выводы................................................................. 36

Глава 2. Кластеризация СШО-ресурсон для оптимизации информационного обмена при совместной обработке результатов распределённых вычислений..................................................... 39

2.1. Основное понятие кластеризации................................. 39

2.1.1. Применение методов кластеризации для распределённых вычислений..........................................................................................39

2.1.2. Вычислительные кластеры...........................................................41

2.1.3. Основные методы кластеризации............................................42

2.2. Анализ известных алгоритмов кластеризации, Алгоритмы кластеризации, допускающие распараллеливание......................................................46

2.3. Параллельный Алгоритм Кластеризации (ПАК)........................49

2.3.1. Актуальность предлагаемого алгоритма ПАК..............50

2.3.2. Алгоритм Прим..........................................................................................52

2.3.3. Метрики кластеризации....................................................................56

2.3.4. Построение Параллельного Алгоритма Кластеризации ПАК..................................................................................................................57

2.3.5. Оценка сложности алгоритма ПАК..........................................59

2.3.6. Моделирование и реализация параллельного алгоритма кластеризации ПАК......................................................................................................61

2.4 Выводы..................................................................................................................................64

Глава 3. Выбор метода и обоснование плана решения тестовой задачи решения «большой» системы линейных уравнений на вычислительной сети и на суперкомпьютере кластерного типа МИИТ

Т- 4700 (СКИФ)..........................................................................................................................................67

3.1. Суперкомпьютер МИИТ Т-4700....................................................................68

3.1.1. Аппаратное обеспечение..................................................................68

3.1.2. Программное обеспечение..............................................................70

3.2. Алгоритм распределенного решения системы линейных уравнений методом Крамера............................................................................................................73

3.3. Решение системы линейных уравнений методом Крамера

на суперкомпьютере СКИФ............................................................................................................77

3.4. Решение системы линейных уравнений методом Крамера

в вычислительной сети........................................................................................................................81

3.4.1. Понятие многопоточной обработки данных..................83

3.4.2. Алгоритм решения..................................................................................86

3.5. Выводы..................................................................................................................................86

Глава 4. Результаты моделирования сетевой реализации метода

Крамера в вычислительной сети и на кластерном суперкомпьютере... 89

4.1. Результаты моделирования сетевой реализации метода Крамера в вычислительной сети................................................................................................90

4.2. Результаты моделирования сетевой реализации метода Крамера на кластерном суперкомпьютере........................................................................94

4.2.1. Этап первый: Кластеризация и Раздача заданий... 94

4.2.2. Этап второй: параллельные вычисления........................98

4.2.3. Этап третий: сбор результатов................................................99

4.3. Выводы..............................................................................................................................104

Заключение 107

Список литературы 112

Приложение 116

Введение

Как известно [1,2,3], главным критерием оптимальной параллельной и распределенной обработки информации является минимум времени решения задачи. Это определяет критерий эффективности такой обработки: Трешение = min. Традиционно, параллельная обработка предполагает наличие общей оперативной памяти, решающей задачи взаимодействия программных модулей и массивов данных, выполняемых или обрабатываемых разными процессорами вычислительной системы. Временем обмена для обеспечения этого взаимодействия в таком случае пренебрегают.

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

В частности, суперкомпьютер типа СКИФ полностью основан на применении сетевой технологии, представляя собой «сеть в коробке».

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

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

Рис В.1. Определение точки насыщения, где I - время решения на одном процессоре, п- число процессоров, х- точка

насыщения

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

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

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

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

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

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

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

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

распараллеливания.

На рисунке В.2 представлена схема обслуживания вычислительных запросов центром бЛЯ>-технологий. Выделена обработка таких задач (ярким представлением которых является задача решении «большой» системы линейного уравнения), которые предъявляют особо высокие требования к желательно одновременному или близкому к одновременному обмену данными с главным процессором.

Поток запросов —........V

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

Г

Главный процессор

т

Выделение ресурса

Кластеризация

7

Рис. В.2. Попарная сборка результатов вычислений (двоичное дерево)

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

времени передачи данных. Аналогичные возможности «близкой» передачи с учётом особенностей структуры используются в суперкомпьютере кластерного типа.

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

(Становится понятным, почему Бернерс Ли- идеолог первой СЯЮ-системы для обработки экспериментов ЦЕРН, группировал данные на региональных серверах).

Актуальность темы исследования.

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

Используемые методы исследования.

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

Объект исследования.

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

Цель работы.

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

Научная новизна.

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

2. Разработан новый параллельный алгоритм кластеризации ресурсных процессоров вычислительной сети. Применение этого алгоритма кластеризации позволило получить дальнейшее снижение времени распределённых вычислений с количества процессоров порядка 15 до привлечения гораздо большего количества процессоров (порядка 90).

3. Обоснована модель реализации метода Крамера решение системы линейных уравнений с применением разработанного нового параллельного алгоритма кластеризации в вычислительной сети. Такая модель увеличивает границу эффективности распределённых вычисленной. Например система уравнений порядка п = 10 при распределённых вычислениях становится эквивалентной (по времени решения) порядки 24 переменных.

4. Разработаны рекомендации по структуре организации

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

задач, предполагающих схему вычислений типа «распределенных

работ - счёт - сборка результатов», позволившие значительно

12

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

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

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

2. Предложен новый параллельный алгоритм кластеризации

вычислительных ресурсов.

3. Показана возможность значительного увеличения числа процессоров, с вводом в использование которых время решения задачи убывает. Так, для размерности задачи п = это количество используемых процессоров возросло с 15 (кластеризация не производилось) до порядка 90. Общее время решения задачи сокращается в 2000 раз.

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

Публикации.

Статьи в изданиях из перечня ВАК

1. Кластеризация GRID-Ресурсов для оптимизации информационного обмена при совместной обработке результатов распределённых вычислений. // Информационные технологии, 2011, No 2.

2. GRID- технологии решения больших систем линейных уравнений на вычислительной сети и на суперкомпьютера кластерного типа. // Информационные технологии, 2011, No 6.

Статьи в международных изданиях

3. Optimization of Data Aggregation in a Distributed Grid-System using Supercomputer Technology. // Journal of Supercomputing, Springer, 2012, No 6.

Доклады на международных конференциях:

4. NGN & adHoc networks, // III международная научно-студенческая конференция в неделю науки Ирана, Керман Государственный университет, Иран, 2009.

5. Параллельные методы кластеризации GRID-ресурсов при совместной обработке результатов распределённых вычислений. // Международная научная конференция «Актуальные вопросы

современной технически и технологии», г. Липецк, Российская Федерация, 2010.

6. Parallel Algorithms for Hierarchical Clustering in computer Networks // VII международная научно-практическая конференция студентов и молодых ученых «Trans-Mech-Art-Chem», МИИТ, Moscow, Russia, 2010.

7. Parallel Cluster Algorithm for Solving Large Linear Equation Systems, Using GRID-Technology and Cramer's Rule, on a Supercomputer.// 26th IEEE International Parallel & Distributed Processing Symposium, Shanghai, China, May,2011.

8. Оптимизация обмена в GRID- системах- труды научно-практической конференции Неделя науки «Наука МИИТа - транспорту»,2011.

9. Локально-сетевая модель параллельного решения задачи линейного программирования, Ш-ой межрегиональной научно-методической конференции «АКТУАЛЬНЫЕ ПРОБЛЕМЫ СОВРЕМЕННОГО ОБРАЗОВАНИЯ», Воронежский институт экономики и социального управления, 15 февраля 2011 г.

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