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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

0050573гУ

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

Паньшенсков Михаил Алексеевич

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

05.13.18 — математическое моделирование, численные методы и комплексы программ

1 З ДЕН 2012

АВТОРЕФЕРАТ

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

Санкт-Петербург 2012

005057379

Работа выполнена на кафедре параллельных алгоритмов математико-механического факультета Санкт-Петербургского государственного университета

Научный руководитель: доктор физико-математических наук, профессор Демьянович Юрий Казимирович

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

профессор Бухановский Александр Валерьевич (зав. кафедрой высокопроизводительных вычислений фак-та ИТиП, НИУ ИТМО; директор НИИ НКТ)

доктор физико-математических наук, профессор Андрианов Сергей Николаевич (зав. кафедрой компьютерного моделирования и многопроцессорных систем фак-та ПМ-ПУ, СПбГУ)

Ведущая организация: Научно-исследовательский вычислительный центр Московского государственного университета им. М.В. Ломоносова (НИВЦ МГУ)

Защита состоится 26 декабря 2012 г. в 13 часов на заседании диссертационного совета Д 212.232.50 по защите диссертаций на соискание ученой степени кандидата наук, на соискание ученой степени доктора наук при Санкт-Петербургском государственном университете по адресу: 199034, Санкт-Петербур В.О., Университетская наб., 7/9, Менделеевский Центр.

С диссертацией можно ознакомиться в библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9. Автореферат размещен на сайте www.spbu.ru

Автореферат разослан "22 » 2012 г.

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

Курбатова Г.И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы

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

В распределенной вычислительной среде с изменением плана исполнения вычислительного задания общее время вычислений может поменяться на несколько порядков. Актуальная задача оптимального планирования вычислений относится к классу задач теории расписаний, который, в свою очередь, является подклассом более широкого класса задач дискретной оптимизации. В мировой науке теория расписаний берет свое начало в 1950е годы с работ Джексона и Джонсона и окончательно оформлена в 1970е в работах Танаева, Конвея, Максвелла и Миллера. Основной задачей дискретной оптимизации является нахождение экстремума некоторой вещественнозначной функции / : X —» К, где множество X не более чем счетно. В терминах теории расписаний X является множеством всевозможных расписаний, а / - функция оценки эффективности расписаний из X.

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

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

Цель диссертационной работы

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

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

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

1. Построить математическую модель планирования в распределенной вычислительной среде с коммуникациями.

2. Предложить методы оценки эффективности планирования независимых заданий в распределенной вычислительной среде для различных сценариев.

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

4. Проиллюстрировать допущения и ограничения модели численными экспериментами.

Методы исследования

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

Достоверность и обоснованность

Достоверность результатов подтверждена строгими доказательствами; результаты согласуются с проведенными численными экспериментами.

Результаты, выносимые на защиту

В диссертации предложена теоретическая модель распределенной вычислительной среды для интервальных систем и реализован комплекс программ Adaptive Parallel Computations framework (АРСО). Следующие теоретические и практические результаты диссертационной работы выносятся на защиту:

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

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

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

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

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

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

Теоретическая и практическая значимость

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

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

Предлагаемые автором методы, в частности, могут быть использованы в системе автоматического масштабирования эластичных ресурсов (например, Amazon ЕС2), в механизме балансировки нагрузки фреймворка MapReduce, для оценки эффективности планирования в Грид и других средах.

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

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

1. Computational Science and Its Applications - ICCSA 2007: International Conference. Kuala Lumpur, Malaysia. 26-29 August, 2007.

2. 4th International Conference on Grid and Pervasive Computing (GPC 2009). Geneve, Switzerland. 4-8 May 2009.

3. 1st International Workshop on Data Grids for e-science. Ischia, Italy. 18-20 May 2009.

4. Семинар кафедры Информационно-сетевых технологий Санкт-Петербургского государственного университета аэрокосмического приборостроения. С.-Петербург. 22 июля 2009.

5. Семинар PARALLEL.RU. Большой конференц-зал НИВЦ МГУ. Москва. 13 сентября 2010.

6. Семинар научно-исследовательского института компьютерных технологий. С.-Петербург. 15 апреля 2011.

7. Доклады кафедры параллельных алгоритмов Санкт-Петербургского государственного университета. С.-Петербург. 2008, 2009, 2011, 2012.

Публикации

Основные результаты опубликованы в семи работах [1-7]. Работы [6-7] опубликованы в изданиях, входящих в список рекомендованных Высшей аттестационной комиссией на момент публикации.

Структура и объем работы

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

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

Модели распределенной вычислительной cpeduV. Распределенная вычислительная среда V состоит из G однородных кластеров, т. е. V = {Ai, А2,..., Aq}. Если G = 1, то вычислительная среда V является однородной и состоит из одного кластера р эквивалентных вычислителей, т. с. V = {{"Pi,.. •, Vp}}. Интервальная система - система обработки заданий, где разные задания не могут выполняться одновременно. Распределенная вычислительная среда V удовлетворяет критерию интервальной системы. Процесс передачи данных, ассоциированный с некоторым вычислительным заданием, принимается за независимое задание. Соответственно, в распределенной вычислительной среде V передача данных происходит строго до или после обработки задания на вычислительных узлах.

Модель вычислений. Центральной частью процесса является выполнение независимого вычислительного задания Jj. Процесс выполнения задания J, в интервальной системе состоит из двух частей (в произвольной последовательности): обработка задания вычислителями и передача входных / выходных данных задания J;. Вычислительное задание .Л может быть декомпозировано во множество независимых подзаданий Минимальный размер подзадания - одна машинная инструкция. Задание или подзадание не всегда может делится на новые подзадания, в этом случае такое подзадание называется неде-композируемым. Для каждого задания Jt и каждого подзадания со известно общее время последовательной обработки (без передачи данных) на одном вычислителе T/V.) и Ti(oS) соответственно.

Модель коммуникации для распределенной вычислительной среди Задержки на коммуникацию можно разделить на зависимые от объема передаваемых данных и независимые. Доступной пропускной способностью (available bandwidth) называется величина /3-р определяющая скорость передачи данных между произвольным вычислительным узлом распределенной вычислительной среды и некоторым внешним или внутренним узлом V. Константной задержкой (latency) называется общее время i-p на созда-

ние/разрыв соединения. Это время не зависит от объема передаваемых данных и соответственно от типа заданий. Следуя линейной модели передачи данных, принимая 5гге(,/г) за размер передаваемых данных задания ,/;, общее время передачи данных задания .7; в распределенной вычислительной среде V определяется как

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

Модель планирования заданий. Планирование может осуществляться в моменты г(времени доступности заданий и в моменты е{ш{) времени окончания решения каждого подзадания о»; 6 ./,-. Назовем планом х обработки заданий ■/ = {,/ь ..., /д^} на р вычислителях из множества V следующую четверку (тт, ть, те, Г2), где О - множество всех подзаданий заданий из J, ть, те : О, —> {0,1,2,...} и 7г : 3{ —> {1,2,... ,р} - сопоставляют каждому под-заданию время начала/окончания и номер вычислителя для его выполнения соответственно, при этом реализуются следующие два критерия:

1. Отсутствие коллизий: Уш1,ш2 € О (шх / ш2) :

ть(ш2) < tö(wi) < te(w2) tb{üj2) < te{uii) < те(ш2)

7r(wi) Ф 7r(w2).

2. Сохранение объема вычислений:

ш 6 П (теМ - тьН) = Ti(w).

Время обработки по плану х задания Jj, декомпозируемое во множество подзаданий fIi, в распределенной вычислительной среде V определяется как

T£(Ji) = maxTe(w) — ттт;,(ш).

weilt u£Sli

Если множество заданий J может быть декомпозировано единственным образом во множество подзаданий О, то речь идет о фиксированном разделении заданий из J на подзадания. В этом случае Q перестает быть переменной

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

За множество расписаний X задачи дискретной оптимизации принято множество планов х обработки набора заданий J в распределенной вычислительной среде V.

В диссертационной работе рассмотрены следующие функции / оценок эффективности расписаний:

1. Среднее время нахождения заданий в системе

Е^(теШ-г(.70)

Нх (Л) = -^-,

где те(Ж) = тах те{ш). а П,- - множество подзаданий задания Jг•. Тогда для х° - оптимального по целевой функции В,х плана обработки набора заданий 7 = ..., .//у}, эффективность Е-^ по целевой функции

1{х некоторого плана х определяется следующим образом:

Пх ЁхУ) '

2. Ресурсная эффективность Еф.

Если для выполнения задания используется р^ вычислителей, то ресурсная эффективность Еф при обработке заданий J определяется следующим образом:

лЛ"

ДД-0 = ^л.

(рУ-ТрЩ-ЕфЩ)

Е^И-ВД)) '

где Еф(^) - ресурсная эффективность при выполнении задания

рха.ТрШ

где Т-р(Ж) - общее время обработки задания ,7; в однородной распределенной вычислительной среде V, ТрД,/;) - время обработки задания на вычислителе Тк, а Т^(^) - время на передачу данных задания 3{ вычислителем Рь

3. Ускорение вычислений при масштабировании

Ускорение вычислений при масштабировании Б а решения задания в распределенной вычислительной среде В относительно решения 3{ в распределенной вычислительной среде А определяется как

ьа->вш - щу-у

где Та(Ж) и Тв(^) есть общее время выполнения задания ,/,• в распределенной вычислительной среде А и В соответственно.

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

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

Классификация основных теоретических результатов диссертации по области их определения приведена на рис. 1. Каждый результат выделен в виде теоремы. Теорема 1 доказана для произвольно декомпозируемых заданий распределяемых в однородной вычислительной среде без коммуникаций. Теорема 2 доказана для произвольно декомпозируемых заданий в однородной вычислительной среде. Теорема 3 доказана для заданий с фиксированным разбиением в однородной вычислительной среде. Теорема 4 и Теорема 5 доказаны для заданий с фиксированным разбиением в распределенной вычислительной среде, состоящей из двух и более кластеров соответственно.

Рассмотрена однородная распределенная вычислительная среда V без задержек на коммуникацию (\/г Тс(Зг) = 0). Планирование проводится для набора вычислительных заданий 3 = {«Л, ,/2,..., где вычислительные задания могут быть декомпозированы во множество сколь угодно малых подзаданий Для этого случая доказана следующая теорема об оптимальном плане в среде без коммуникаций.

Теорема 1 В распределенной однородной вычислительной среде без коммуникаций для решения набора произвольно делимых заданий 3 = ..., ,/лг} существует оптимальный по среднему времени нахождения заданий в системе план х = {тт,ть,те,П}.

о

х 5

ч О

Т5. Об оценке относительного ускорения при горизонтальном масштабировании.

Т2. Оценка эффективности плана.

\

\

Т1. Об \

оптимальном \ плане. \

И

Т4. Об оценке относительного ускорения

при удвоении вычислительной мощности.

ТЗ. Оценка ресурсной

эффективности для вычислений на одном кластере.

Произвольное разбиение Фиксированное разбиение на подзадания на подзадания

Рис. 1: Классификация теоретических результатов по области применения.

Рассмотрена однородная распределенная вычислительная среда V с коммуникациями. Планирование проводится для набора вычислительных заданий 3 = {./1, З2,..., ./дг}: где вычислительные задания Зг могут быть декомпозированы во множество сколь угодно малых подзаданий. Доказана следующая теорема, дающая оценку эффективности плана (из Теоремы 1) в распределенной вычислительной среде с коммуникациями.

Теорема 2 Если набор произвольно делимых заданий 3 = {«/х, З2,..., Зн} исполняется в однородной распределенной вычислительной средеТ-' из р вычислителей по плану х (из Теоремы 1), то относительная эффективность по Я плана х имеет следующую оценку:

Е**> р> + Ь

Ь я г ВД) -, гдеь = твх.—-—

Рассмотрена однородная распределенная вычислительная среда V с коммуникациями. Планирование проводится для набора заданий 3 = {3\,32, ..., Зьг}, которые декомпозируется в фиксированное множество неделимых подзаданий. Для этого случая доказана следующая теорема, дающая оценку ресурсной эффективности.

Теорема 3 Пусть набор заданий J = {J\, J2, ■ ■ ■, Jn} обрабатывается по некоторому плану х в однородной распределенной вычислительной среде V = {{Vi, Р2, • • •, Vp}} из р вычислителей, причем для обработки задания Ji используется рW < р вычислителей. Тогда ресурсная эффективность обработки всего набора заданий имеет следующую оценку:

T.L (Р(,) • (mm 2* Ш +Т£(./!)))

Еф(J) >

Eili (Р('> ■ (max (J,) + TpcV>)))

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

Теорема 4 Если кластеры А и В эквивалентны, и существует некоторый план х обработки задания Ji на А, причем время обработки каждого подзадания и> задания Ji на одном вычислителе ограничено частью общего времени выполнения: Ti(oj) < 6 ■ Tx(Ji) при 6 < 1/2, то существует параметр d е (0,1/2] и план у для Ji на АВ такой, при котором (1 — d) • size(Ji) исходных данных Ji обрабатывается на кластере А и d ■ size(Ji) исходных данных - на кластере В, а ускорение вычислений Sa-^ab(Ji) обработки задания Ji на АВ по отношению к А имеет следующую оценку:

q m> т%Ш + Т$Ш

JA^AB(Ji) >

{§; ¥) • ТлШ + тох^-у-Ц + ¿А\ +1в}'

тгп

Рассмотрены две среды: распределенная вычислительная среда с коммуникациями Ао, состоящая из одного кластера, и среда £/ = {Ло, А\,..., Ас}, состоящая из нескольких одинаковых кластеров. Планирование проводится для задания Ji, которое декомпозируется в фиксированное множество неделимых подзаданий. Для этого случая предложена и доказана оценка ускорения вычислений при переходе от однокластерной среды к многокластерной и она оформлена в виде следующей теоремы.

Теорема 5 Если С эквивалентных кластеров объедены в распределенную вычислительную среду 0 = {Ло, А1,..., Аа-г}, задание ^ декомпозируется во множество подзаданий Г2;, ограниченных по времени обработки на вычислителях: ш € =4> 2У(П) < при 6 < 1/(? и существует некоторый план обработки задания 3{ на Ад, тогда существует план обработки </г на 0 такой, при котором дд ■ вг.ге( </,) данных задания обрабатывается на кластере Ад : Х^^Го1 д,д=1, а ускорение вычислений обработки задания ^ в Я по отношению к Ао имеет следующую оценку:

Эа^Ш >-7^-

inidi' h + s}- ta»w + % ■ siz<J^ +

min

ßg = min ß„ где (-G = max t„ .

geO..G-l "

de = min d„

geO..G-l U

В Третьей главе описаны созданный автором пакет программ АРСО и численные эксперименты, проведенные с его использованием. Пакет программ АРСО позволяет запускать процесс распределенных вычислений для различных алгоритмов планирования. Программный пакет АРСО является легковесной средой с открытым исходным кодом, чем отличается от аналогичных систем, таких как X-Com, Globus Toolkit, Cilk++ и Hadoop. Пакет программ АРСО не предоставляет полной функциональности распределенного вычислительного комплекса, например, не имея собственного модуля мониторинга, но любой пользователь имеет возможность дополнить необходимой функциональностью пакет программ АРСО, находящегося в свободном доступе. Доказано, что в предложенной архитектуре АРСО модуль координатор может реализовать любой корректный план обработки заданий в распределенной вычислительной среде.

В этой главе представлены численные эксперименты, проведенные с целью иллюстрации теорем 1-4 из главы 2. Эксперименты проведены в вычислительном центре НИУ ИТМО и в лаборатории кафедры вычислительной физики СПбГУ, где был развернут программный комплекс АРСО. Вычислительные задания решали задачу поиска простых чисел большой разрядности и задачу генерации графов. Первая задача использовалась для симуляции вычислительно-трудоемких заданий, вторая - для вычислительных зада-

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

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

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

Приложение А содержит описание пакета программ АРСО, позволяющего развертывать распределенную вычислительную среду для обработки вычислительных заданий. Пакет АРСО отличается гибкими средствами настройки механизма распределения вычислительных заданий. Он реализован на языке Java с использованием сторонних библиотек для обеспечения коммуникации. Пакет оформлен как проект с отрытым исходным кодом, свободно доступным для скачивания: http://code.google.eom/p/apco/.

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

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

[1] Паньшепсков М.А. Адаптивный метод управления потоком решения изолированных заданий в параллельной вычислительной среде // Стохастическая оптимизация в информатике. Вып.4. СПбГУ, 2008.

С. 185-195.

[2] Паньшепсков М.А.. Динамическое планирование коммуникаций и методы оценивания пропускной способности каналов данных в Грид // из трудов конференции Научный сервис в сети интернет: масштабируемость, параллельность, эффективность. 2009. С. 403-408.

[3] Panshenskov М., Vakhitov A. Transfer Speed Estimation for Adaptive Scheduling in the Data Grid // Workshops at the Grid and Pervasive Computing Conference. IEEE. 2009. Pp. 58-63.

[4] Panshenskov M., Vakhitov A. Methods of linear transfer speed estima-tion in the data grid // DaGreS '09 Proceedings of the 1st ACM workshop on Data grids for eScience. Pp. 29-34.

[5] Panshenskov M., Vakhitov A. Adaptive Scheduling of Parallel Computations for SPMD Tasks // Computational Science and Its Applications -ICCSA 2007, International Conference, Kuala Lumpur, Malaysia, August 26-29, 2007. Proceedings, Lecture Notes in Computer Science 4705 Springer 2007. Pp. 38-50.

[6] Паньшепсков M. А. Эффективный план распределения неограниченно делимых заданий в среде MapReduce // Вестник Санкт-Петербургского государственного университета - Прикладная математика. Информатика. Процессы управления, сер. 10 вып. 2. Июль 2011. С. 55-66.

[7] Вахитов А.Т., Граничил О.Н., Паньшепсков М.А. Методы оценивания пропускной способности каналов данных в распределенных системах // Нейрокомпьютеры: разработка, применение, вып. 11. 2009.

С. 45-52.

Подписано в печать 19.11.12 Формат 60х84'/і6 Цифровая Печ. л. 1.0 Тираж 100 Заказ 17/11 печать

Отпечатано в типографии «Фалкон Принт» (197101, г. Санкт-Петербург, ул. Большая Пушкарская, д. 54, офис 2)

Глава 1. Введение.

1.1. Задача планирования.

1.2. Распределенная вычислительная среда.

1.3. Планирование вычислений в распределенной среде

1.4. Модель.

1.5. Описание диссертационной работы.

Глава 2. Методы оценки эффективности.

2.1. Оптимальный план в среде без задержек на соединение

2.2. Относительная эффективность плана в среде с задержками на коммуникацию

2.3. Эффективность по ресурсам при вычислении на одном кластере

2.4. Относительное ускорение при удвоении вычислительной мощности

2.5. Относительное ускорение при горизонтальном масштабировании

Глава 3. Практическая иллюстрация методов.

3.1. Система АРСО.

3.2. Эксперимент по проверке оптимальности плана для задачи поиска простых чисел в системе АРСО.

3.3. Оценка эффективности некоторого плана по решению вычислительной задачи проверки простоты чисел.

3.4. Эффективность планов вычислений на одном кластере

3.5. Относительная эффективность масштабирования.

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

Заключение

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

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

2. Предложен метод оценки эффективности плана вычисления произвольно делимых заданий в распределенной вычислительной среде с коммуникациями;

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

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

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

В общем случае, задача отыскания оптимального плана с указанными ограничениями является ЫР-трудной [9] и, соответственно, вычислительно трудоемкой. Результаты (3), (5) на практике позволяют сделать оценку снизу эффективности плана х, что на практике может сэкономить время реализации сложного алгоритма планирования.

В рамках диссертационной работы был разработан пакет программ АРСО, который позволяет запускать процесс распределенных вычислений для различных алгоритмов планирования. Для иллюстрации изложенных в рамках работы теорем на базе фреймворка АРСО были развернуты распределенные вычислительные среды в вычислительном центре НИУ ИТМО и в лаборатории кафедры вычислительной физики СПбГУ. Был проведен ряд экспериментов. Среди важных итогов экспериментов можно выделить:

1. Иллюстрация теоретических оценок теорем 1-4 описанных в теоретической части;

2. Иллюстрация линейной модели оценки доступной пропускной способности каналов связи в распределенной вычислительной среде;

3. Проведены сравнения методов оценки доступной пропускной пропускной способности каналов связи в распределенной вычислительной среде. Для сравнения были выбраны следующие методы: Метод Наименьших Квадратов (МНК), Реккурентный МНК, Фильтр Калмана, Рандомизированный МНК.

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

1. Романовский И. В. Субоптимальные решения.- Петрозаводск: ПетрГУ, 1998.- С. 96.

2. Романовский И. В. Алгоритмы решения экстремальных задач.- Москва: Наука, 1977.

3. Jackson J. R. Scheduling a production line to minimize maximum tardiness // Manag. Sci. Res. Project. Research Report.- No. 43.- Los Angeles: CA: University of California, 1955.

4. Johnson S. M. Optimal two- and three-stage production schedules with setup times included//Naval Res. Logistics Quat.- 1954.- Vol. 1.- P. 61-68.

5. Коффман Э.Г. Теория расписаний и вычислительные машины.- Москва: Наука, 1984.

6. Сигал И. X, Иванова А. П. Введение в прикладное дискретное программирование.- Москва: Физ-матлит, 2002.- С. 240.

7. Поляк Б. Т. Введение в оптимизацию.- Москва: Наука. Главная редакция физико-математической литературы, 1983.- С. 384.

8. Ковалев М. Я. Интервальные I-приближенные алгоритмы решения дискретных экстремальных задач: Кандидатская диссертация.- 1986.- С. 110.

9. Monma Clyde L., Potts Chris N. On the Complexity of Scheduling with Batch Setup Times // Operations Research.- 1989.- Vol. 37, no. 5.- P. 798-804.

10. Mattson T. G., Sanders B. A., Massingill B. L. Patterns for Parallel Programming.- Addison-Wesley. Professional, 2004.- P. 384.

11. Севастьянов С. В. Геометрические методы и эффективные алгоритмы в теории расписаний: In.- 2000.

12. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления.- СПб: БХВ-Петербург, 2002.

13. Посыпкин М. А., Хританков А. С. О понятии ускорения и эффективности в распределенных системах // Труды Всероссийской научной конференции Научный сервис в сети Интернет: решение больших задач.- 2008.- Р. 149-155.

14. Воеводин Вл. В., Жолудев Ю. А., Соболев С. И., Стефанов К. С. Эволюция системы метакомпьютинга X-Com // Вестник Нижегородского государственного университета им. Н.И. Лобачевского.- 2009.- Vol. 4.-Р. 157-164.

15. Березовский П.С. Управление заданиями в гриде с некластеризованными ресурсами: Кандидатская диссертация.- 2011.- С. 128.

16. Коваленко В. Н., Коваленко Е. И., Корягин Д. А., Любимский Э. 3. Основные положения метода опережающего планирования для грид вычислительного типа // Вестник СамГУ — Естественнонаучная серия.-2006.- Vol. 4, по. 44.- Р. 238-264.

17. Ghemawat Sanjay, MapReduce Jeffery Dean. Simplified Data Processing on Large Clusters // Proceedings of the Sixth Symposium on Operating System Design and Implementation.- Vol. 6.- San Francisco, USA: 2004.- P. 10.

18. Немнюгин С.A. // Основы параллельного программирования с использованием MPI / СПБГУ.- Санкт-Петербург, 2012.- URL: http: //www.intuit.ru/department / supercomputing/paralprogmpi/1 /.

19. Jin С., Buyya R. MapReduce programming model for .NET-based distributed computing // Technical Report GRIDS-TR-2008-15, 17 oct / Ed. by Grid Computing, Distributed Systems Laboratory.- Australia: The University of Melbourne, 2008.

20. Berthold J., Dieterle M., Loogen R. Implementing parallel google map-reduce in eden // Lecture Notes in Computer Science / Ed. by H. Sips, D. Epema, H. Lin.- Vol. 5704.- Springer-Verlag, 2009.- P. 990-1002.

21. Система метакомпьютинга X-Com.- URL: http://x-com.parallel.ru/ (дата обращения: 12.02.2009).

22. The Globus Alliance.- URL: http://www.globus.org/toolkit/ (дата обращения: 12.02.2009).

23. Хританков А. С. Один алгоритм балансировки вычислительной нагрузки в распределенных системах // Материал конференции «Параллельные Вычислительные Технологии», Нижний Новгород, 30 марта 3 апреля.-Челябинск: ЮурГУ, 2009.- Р. 783-789.

24. Демьянович Ю. К., Бурова И. Г. Алгоритмы параллельных вычислений и программирование (курс лекций).- Санкт-Петербург: СПбГУ, 2007.

25. Yu Jia, Buyya Rajkumar. Workflow Scheduling Algorithms for Grid Computing // Studies in Computational Intelligence.- 2008.- Vol. 146.- P. 173-214.

26. Xhafa F., Carretero J., Barolli L., Durresi A. Immediate mode scheduling in grid systems // Int. J. Web and Grid Services.- 2007.- Vol. 3, no. 7.-P. 219-236.

27. Xiaoshan H., Sun X.-H., von Laszewski G. QoS Guided Min-Min Heuristic for Grid Task Scheduling // Computer Science and Technology.- 2003,-Vol. 18.- P. 442-451.

28. Hef Yuxiong, Hsu Wen Jing, Leiserson. Charles E. Provably Ecient Online Non-clairvoyant Adaptive Scheduling // IEEE Transactions on Parallel and Distributed Systems archive.- 2008.- Vol. 19, no. 9,- P. 1263-1279.

29. Agrawal Kunal, He Yuxiong, Hsu Wen Jing, Leiserson Charles E. Adaptive task scheduling with parallelism feedback // PPoPP.- New York City, NY, USA: 2006.- P. 100-109.

30. Гэри M., Джонсон Д. Вычислительные машины и труднорешаемые задачи / Пер. с англ.- Москва: Мир, 1982.- С. 416.

31. Левин М. П. // Параллельное программирование с использованием Ореп-МР / СПБГУ.- Санкт-Петербург, 2008.- URL: http://www.intuit.ru/ department / se/openmp/.

32. Посыпкин М.А., Хританков А.С. О понятии производительности в распределенных вычислительных системах // Труды ИСА РАН.- 2008.-Vol. 32.

33. Хританков А. С. Оценка производительности распределенных вычислительных комплексов на основе модели эталонных систем: Кандидатская диссертация.- 2010.

34. Хританков А. С., Посыпкин М. А. Анализ эффективности распределенных вычислительных систем при решении больших задач // Труды конференции «Современные информационные технологии и ИТ-образование».- Москва: МАКС ПРЕСС, 2008.- Р. 528-536.

35. Хританков А. С. Модели и алгоритмы распределения нагрузки. Алгоритм на основе сетей СМО // Информационные технологии и вычислительные системы.- 2009.- Vol. 3.- Р. 33.

36. ATIS committee PRQC. "network topology-// ATIS Telecom Glossary 2007.-Alliance for Telecommunications Industry Solutions, Retrieved 2008-10-10.

37. Network Design Basics for Cabling Professionals.- BICSI.

38. Коваленко В. H., Корягин Д. А. Организация ресурсов в грид. Препринт № 63.- Москва: ИПМ им. М.В.Келдыша РАН, 2004.- С. 25.

39. Eisenbrand F., Rothvoss Т. Static-priority Real-time Scheduling: Response Time Computation is NP-hard // in IEEE Real-Time Systems Symposium (RTSS).- 2008.- P. 397-406.

40. Hall Leslie A., Shmoys David В., Wein Joel. Scheduling to minimize average completion time: off-line and on-line algorithms // In SODA, 1996. Society for Industrial and Applied Mathematics.- 1996.- P. 142-151.

41. Chekuri C., Motwani R., Natarajan В., Stien C. Approximation techniques for average completion time scheduling. // In SODA, 1997. Society for Industrial and Applied Mathematics.- 1997.- P. 609-618.

42. Turek John, Ludwi Walter, Wolf Joel L. et al. Scheduling parallelizable tasks to minimize average response time // In 6th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA).- 1994.- P. 200-209.

43. Хританков A.C. Метод анализа производительности распределенных приложений на основе эталонных моделей // ПаВТ'2011: труды международной научной конференции.- Москва: ЮУрГУ, 2011,-Р. 343-354.

44. Ковальчук С. В., Бухановский А. В. Параллельная производительность стохастических алгоритмов // Известия высших учебных заведений. Приборостроение.- 2008.- Vol. 12.- Р. 7-14.

45. Adaptice Parallel COmputing framework.- URL: http://sourceforge.net/ projects/apco/.

46. Ковальчук С. В. Особенности проектирования высокопроизводительных программных комплексов для моделирования сложных систем // Информационно-управляющие системы,- 2008,- Vol. 3, по. 34.- Р. 10-18.

47. Соболев С. И. Использование распределенных компьютерных ресурсов для решения вычислительно сложных задач // Системы управления и информационные технологии.- 2007.- Vol. 1.3, по. 27.- Р. 391-395.

48. Fedak G., Germain С., Neri V., Cappello F. XtremWeb : A Generic Global Computing System // Workshop on Global Computing on Personal Devices (CCGRID2001).- Berlin: IEEE Press, 2001.

49. Anderson D. P., Cobb J., Korpela E. et al. SETI@home: An Experiment in

50. Public-Resource Computing // Communications of the ACM.- 2002.- Vol. 45, no. 11.- P. 56-61.

51. Anderson D. P. BOINC: A System for Public-Resource Computing and Storage // 5th IEEE/ACM International Workshop on Grid Computing.- Pittsburgh, PA: 2004.- P. 365-372.

52. Rabin M. O. Probabilistic algorithm for testing primality // Journal of Number Theory. Elsevier Inc.- 1980.- Vol. 1, no. 12.- P. 128-138.

53. Задорожный В. H., Юдин Е. Б. Генерация статистически однородных планарных графов // Обработка информации и управление. Теория и практика. Сб. докл. науч.-практ. конф.- Омск: Изд-во ОмГТУ, 2008,-С. 27-31.

54. Milea С., Svasta P. Using distributed neural networks in automated optical inspection // Concurrent Engineering in Electronic Packaging, 24rd Int. spring seminar on electronics technology.- Calimanesti-Caciulata, Romania: 2001.-P. 286-288.

55. Venugopal S., Buyya R., Ramamohanarao K. A taxonomy of Data Grids for distributed data sharing, management, and processing // ACM Computing Surveys.- 2006.- Vol. 38, no. 1.- P. 1-53.

56. Ranganathan K., Foster I. Decoupling Computation and Data Scheduling in Distributed Data-Intensive Applications // In proceedings of the 11th IEEE International Symposium on High Performance Distributed Computing, July 24-26.- 2002.- P. 352.

57. Neginhal M. Efficient Estimation of Available Bandwidth Along Network Paths // Master's Thesis.- USA: North Carolina State University, 2006.

58. Paxson V. End-to-End Internet Packet Dynamics // IEEE/ACM Transactions on Networking (TON).- 1999.- Vol. 7, no. 3.- P. 277-292.

59. Ribeiro V., Riedi R., Baraniuk R. et al. pathChirp: Efficient Available Bandwidth Estimation for Network Paths // In Proceedings of The Conference on Passive and Active Measurements (PAM).- San Diego, USA: 2003.

60. Carter R. L., Crovella M. E. Measuring Bottleneck Link Speed in Packet-Switched Networks // Performance Evaluation.- 1996.- Vol. 27, no. 28.-P. 297-318.

61. Lai K., Baker M. Nettimer: A tool for measuring bottleneck link bandwidth // In Proceedings of the USENIX Symposium on Internet Technologies and Systems.- 2001.- P. 123-134.

62. Dovrolis C., Ramanathan P., Moore D. Packet-Dispersion Techniques and a Capacity Estimation Methodology // IEEE/ACM Transactions on Networking (TON).- 2004.- Vol. 12, no. 6.- P. 963-977.

63. Kapoor R., Chen L.-J., Lao L. et al. CapProbe: A Simple and Accurate Capacity Estimation Technique // ACM SIGCOMM Computer Communication Review.- 2004.- Vol. 34, no. 4.- P. 67-78.

64. Carter Robert L., Crovella Mark E. Dynamic Server Selection using Bandwidth Probing in Wide-Area Networks: Tech. rep.: 1996.

65. Jain M., Dovrolis C. End-to-End Available Bandwidth : Measurement Methodology, Dynamics, and Relation with TCP Throughput // IEEE/ACM Transactions on Networking.- 2003.- Vol. 11, no. 4.- P. 537-549.

66. Strauss J., Katabi D., Kaashoek F. A Measurement Study of Available Bandwidth Estimation Tools I I In ACM/USENIX Internet Measurement Conference (IMC).- 2003.- P. 39-44.

67. Seshan S., Stemm M., Katz R. H. SPAND: Shared passive network performance discovery // In USENIX Symposium on Internet Technologies and Systems.- 1997.

68. Vazhkudai S., Schopf J. M. Predicting Sporadic Grid Data Transfers // High Performance Distributed Computing, 2002. HPDC-11 2002. Proceedings. 11th IEEE International Symposium on.- 2002.- P. 188-196.

69. Guo L. Stability of recursive stochastic tracking algorithms // SIAM J. Control and Optimization.- 1994.- Vol. 32, no. 5.- P. 1195-1225.

70. Granichin O. N. Linear Regression and Filtering Under Nonstandard Assumptions (Arbitrary Noise) // IEEE Trans. Automat. Contr.- 1999.- Vol. 44, no. 3.-P. 442-453.

71. Посыпкин M. А. Мультплатформенный программный комплекс для решения задач оптимизации в распределенной вычислительной среде. // Труды ИСА РАН.- 2009.- Т. 46.- С. 24-42.

72. Silberstein М., Sharov A., Geiger D., Schuster. A. GridBot: execution of bags of tasks in multiple grids // In Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis.- ACM, 2009.-P. 11.

73. Emelianov S. V., Velikhov E. P. Distributed Computing and Its Applications.-USA: Felicity Press, 2005.- P. 298.

74. Chen S., Schlosser S. W. MapReduce meets wider varieties of applications.- URL: http://www.pittsburgh.mtcl-research.rict/chensm/papcrs/ IRP-TR-08-05.pdf.

75. Arpaci-Dusseau Andrea, Culler David E., Mainwaring Alan M. Scheduling with implicit information in distributed systems // ACM SIGMETRICS Performance Evaluation Review.- Vol. 26.- ACM, 1998.- P. 233-243.

76. Sinnen Oliver, Sousa Leonel A. Communication contention in task scheduling // Parallel and Distributed Systems, IEEE Transactions.- 2005.- Vol. 16, no. 6.- P. 503-515.

77. Sinnen Oliver, Sousa Leonel Augusto, Sandnes Frode Eika. Toward a realistic task scheduling model // Parallel and Distributed Systems, IEEE Transactions.- 2006.- Vol. 17, no. 3.- P. 263-275.

78. Anderson Thomas E., Culler David E., Patterson David. A case for NOW (networks of workstations) // IEEE Micro.- 1995.- Vol. 15, no. 1.- P. 54-64.

79. Skillicorn David B., Talia Domenico. Models and languages for parallel computation // ACM Computing Surveys (CSUR).- 1998.- Vol. 30, no. 2,-P. 123-169.

80. Zaharia M., Konwinski A., Joseph A.D., Katz R. I. Stoica Improving mapre-duce performance in heterogeneous environments // Proc. 8th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2008.- San Diego, USA: 2008.

81. Chu C., Kim S., Lin Y. A. et al. Map-reduce for machine learning on multi-core // In NIPS.- Vol. 19.- 2007.

82. Satish Nadathur, Harris Mark, Garland Michael. Designing ecient sorting algorithms for manycore GPUs // IEEE International Symposium on Paral-lel&Distributed Processing.- 2009.- P. 1-10.

83. Ekanayake J., Pallickara S., Fox G. Map-Reduce for Data Intensive Scientic // Analyses Proceedings of the IEEE International Conference on e-Science, 2008. December 7-12.- Indianapolis: 2008.

84. Hadoop implementation of MapReduce.- URL: http://hadoop.apache.org/ rriapreduce/.

85. Asanovic Krste, Bodik Ras, Catanzaro Bryan Christopher et al. The landscape of parallel computing research: A view from Berkeley // Technical Report UCB/EECS-2006-183.- Vol. 2.- Berkeley: EECS Department, University of California, 2006.

86. White Tom. Hadoop: The definitive guide.- O'Reilly Media, 2012.- P. 682.

87. Blumofe R.D. Joerg et al. Cilk: An efficient multithreaded runtime system // In Proceedings of the Fifth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP).- 1995.- P. 207-216.

88. Lee Edward A. The problem with threads // Computer.- 2006.- Vol. 39, no. 5,-P. 33-42.

89. Pinedo M. Scheduling: Theory, Algorithms, and Systems.- NJ: Prentice Hall, Englewood Cliffs, 1995.

90. Chu Cheng T., Kim Sang K., Lin Yi A. et al. Map-reduce for machine learning on multicore // Advances in neural information processing systems / Ed. by B. Scholkopf, J. Platt, T. Homan.- Cambridge: MA: MIT Press, 2007.-P. 281-288.

91. Lastovetsky Alexey L. Parallel computing on heterogeneous networks.- Wi-ley-Interscience, 2003.- P. 423.

92. Holt Chris, Heinrich Mark, Singh Jaswinder Pal et al. The Effects of Latency, Occupancy, and Bandwidth in Distributed Shared Memory Multiprocessors // Stanford University Technical Report No. CSLTR-95-660.- USA: Stanford University, 1995.

93. Frank M. I., Agarwal A., Vernon M. K. LoPC: Modeling Contention in Parallel Algorithms // Proc. 6th ACM SIGPLAN Symp. on Principles and Practices of Parallel Programming (PPoPP '97).- New York, USA: ACM, 1997.-P. 276-287.

94. Bosque J., Pastor L. A Parallel Computational Model for Heterogeneous Clusters // IEEE Transactions on Parallel and Distributed Systems.- 2006.- Vol. 17, no. 12.- P. 1390-1400.

95. Zhang Xiaodong, Yan Yong. Modeling and characterizing parallel computing performance on heterogeneous networks of workstations I I In Parallel and Distributed Processing, 1995. Proceedings. Seventh IEEE Symposium on. IEEE.-1995.- P. 25-34.

96. Melander Bob, Bjorkman Mats, Gunningberg Per. A new end-to-end probing and analysis method for estimating bandwidth bottlenecks // In Global Telecommunications Conference, 2000. GLOBECOM'OO. IEEE.- Vol. 1.2000.- P. 415-420.

97. Красовский Д. В., Фуругян Меран Габибуллаевич. Агрегирование в задаче составления оптимального расписания для многопроцессорных АСУ // Автоматика и телемеханика.- 2006,- Т. 12.- С. 205-211.

98. Canonico Massimo. Scheduling Algorithms for Bag-of-Tasks Applications on Fault-Prone Desktop Grids. Диссертация на соискание ученой степени DOTTORATO DI RICERCA.- Турин, Италия, 2005.

99. Во Y., Xun W. Research on the Performance Of Grid Computing For Distributed Neural Networks // International Journal of Computer Science and Netwrok Security.- 2006.- Vol. 6, no. 4.- P. 179-187.

100. Hu N., Steenkiste P. Evaluation and characterization of available bandwidth and probing techniques // IEEE JSAC Special Issue in Internet and WWW Measurement, Mapping, and Modeling.- 2003.- Vol. 21.- P. 879-894.

101. Silva L. M., Buyya R. «Parallel programming models and paradigms» // High Performance Cluster Computing: Architectures and Systems: Volume 2 / Ed. by R. Buyya.- NJ, USA: Prentice Hall PTR, 1999.

102. Google Protocol Buffers.- URL: http://code.google.eom/p/protobuf.

103. Хританков А. С. Математическая модель характеристик производительности распределенных вычислительных систем // Избранные труды 50й научной конференции МФТИ.- МОСКВА: МФТИ, 2007.

104. Оценка эффективности распределенных систем при решении задач переменного размера // Научно-технический вестник СПбГУ ИТМО.-Vol. 2, по. 66.- Р. 66-71.

105. Weng Chuliang, Lu Xinda. Heuristicscheduling for bag-of-tasksapplications in combination with QoS in the computationalgrid // Future Generation Computer Systems.- 2005.- Vol. 21, no. 2.- P. 271-280.

106. Oprescu Ana, Kielmann Thilo. Bag-of-tasks scheduling under budget constraints // In proceeding of: Cloud Computing Technology and Science (CloudCom), 2010 IEEE Second International Conference on.- 2010.

107. Rauber Thomas, Runger Gudula. Parallel programming: For multicore and cluster systems.- Springer, 2010.

108. Drozdowski Maciej. Scheduling for parallel processing.- Springer, 2009.1. Список публикаций

109. Паныпенсков M. А. Адаптивный метод управления потоком решения изолированных заданий в параллельной вычислительной среде // Стохастическая оптимизация в информатике вып.4,- 2008.

110. Паныпенсков М. А. Динамическое планирование коммуникаций и методы оценивания пропускной способности каналов данных в грид // из трудов конференции Научный сервис в сети интернет: масштабируемость, параллельность, эффективность.- 2009.- Р. 403-408.

111. Panshenskov M., Vakhitov A. Transfer Speed Estimation for Adaptive Scheduling in the Data Grid // Workshops at the Grid and Pervasive Computing Conference.- IEEE, 2009.- P. 58-63.

112. Panshenskov M., Vakhitov A. Methods of linear transfer speed estimation in the data grid // DaGreS '09 Proceedings of the 1st ACM workshop on Data grids for eScience.- P. 29-34.

113. Из них в рецензируемых журналах ВАК

114. Вахитов А. Т., Граничин О. Н., Паньшенсков М. А. Методы оценивания пропускной способности каналов данных в распределенных системах // Нейрокомпьютеры: разработка, применение, вып. 11.- 2009.

115. Паньшенсков М. А. Эффективный план распределения неограниченно делимых заданий в среде МарЯеёисе // Вестник ПМПУ, сер. 10 вып. 2.2011.- Р. 55-56.