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

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

Румянцев Александр Сергеевич

Вероятностный анализ процесса нагрузки вычислительного кластера

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

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

2 2 НОЯ 2012

Петрозаводск - 2012

005055705

Официальные оппоненты:

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

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

профессор

Морозов Евсей Викторович Хохлов Юрий Степанович,

доктор физико-математических наук, профессор, ФГБОУ ВПО «Российский университет дружбы народов», заведующий кафедрой теории вероятностей и математической статистики Кручек Марина Марленовна, кандидат физико-математических наук, доцент, ФГБОУ ВПО «Петрозаводский государственный университет», заместитель декана математического факультета Федеральное государственное бюджетное учреждение науки Институт проблем информатики Российской академии наук Защита состоится «20» декабря 2012 г. в 15:00 на заседании диссертационного совета Д 212.190.03 на базе ФГБОУ ВПО «Петрозаводский государственный университет» по адресу: 185910, г. Петрозаводск, пр. Ленина, 33. С диссертацией можно ознакомиться в научной библиотеке Петрозаводского государственного университета.

Автореферат разослан « ноября 2012 г. у

Ученый секретарь диссертационного совета /Аш? Р- В. Воронов

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

Общая характеристика работы

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

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

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

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

1. Исследованы свойства монотонности и условия стационарности процесса нагрузки в предложенной модели.

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

3. Методом численного моделирования проведена проверка адекватности модели на основе данных лог-файла ВК ЦКП КарНЦ РАН.

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

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

На защиту выносятся следующие результаты и положения:

1. Вероятностная модель процесса нагрузки МС, обобщающая классическую модель Кифера-Вольфовица, в которой заявка занимает случайное число процессоров на идентичное время.

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

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

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

5. Результаты численного эксперимента на основе лог-файла работы ВК ЦКП КарНЦ РАН за период 2009-2012 гг., подтверждающие адекватность предложенной модели.

Апробация работы. Результаты работы докладывались и обсуждались на международных научных семинарах "Advances in Methods of Information and Communication Technology" (Петрозаводск, 2007, 2010, 2011 гг.), на международном семинаре "Applied Problems in Theory of Probabilities and Mathematical Statistics related to modeling of information systems" в рамках конгресса ICUMT'10 (Москва, 2010 г.), на международной конференции «Распределенные компьютерные и телекоммуникационные сети: теория и приложения» DCCN'10 (Москва, 2010 г.), на всероссийской летней школе «Су-перкомпыотерное моделирование и визуализация в научных исследованиях» (Москва, 2010 г.), на всероссийской осенней школе «Суперкомпьютерные технологии и высокопроизводительные вычисления в образовании, науке и промышленности» (Нижний Новгород, 2010 г.), на международной научной конференции «Параллельные вычислительные технологии 2011» (Москва, 2011 г.), на всероссийской конференции с международным участием «Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем» (Москва, 2011 г.), на V Международном семинаре «Прикладные задачи теории вероятностей и математической статистики, связанные с моделированием информационных систем» (Светлогорск, 2011 г.), на научной конференции и школе молодых ученых «Фундаментальные и прикладные исследования в Карелии: современное состояние и перспективы развития» (Петрозаводск, 2011 г.), на XI Всероссийской конференции «Высокопроизводительные параллельные вычисления на кластерных системах» (Нижний Новгород, 2011 г.), на VIII Международной Петрозаводской конференции «Вероятностные методы в дискретной математике» (Петрозаводск, 2012 г.), на Летней Суперкомпьютерной Академии (Москва, 2012 г.).

Материалы диссертации опубликованы в 9 печатных работах, из них 2 статьи в журналах, входящих в перечень ВАК ведущих периодических изданий [1, 2], 4 статьи в сборниках трудов конференций [3-6] и тезисы 3 докла-

дов [7-9]. Получено свидетельство о государственной регистрации программы для ЭВМ в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам [10].

Связь работы с научными программами, темами. Основные результаты диссертации были получены при проведении исследований в рамках темы НИР ИПМИ КарНЦ РАН (гос. №01201151875 «Вероятностный анализ регенеративных и гауссовских коммуникационных систем с использованием методов высокопроизводительных вычислений»). Исследования были частично поддержаны Российским фондом фундаментальных исследований (07-07-00088-а, 10-07-00017-а) и Фондом содействия малых форм предприятий в научно-технической сфере (государственный контракт №10491р/16862 от 08.06.2012 г.).

Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения и списка литературы. Общий объем диссертации составляет 109 страниц, включая 12 рисунков. Библиография включает 114 наименований.

Содержание работы

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

В первой главе выполнен обзор известных результатов для вероятностных моделей МС. Представлены доказательства свойств монотонности процесса нагрузки. Приводится доказательство, уточняющее процедуру построения момента однозависимой регенерации в классической модели Gl/G/m. Анализируются результаты, касающиеся моментных свойств компонент век-

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

Опишем классическую модель МС вида GI/G/m, которая существенно используется далее. Пусть в систему обслуживания в моменты времени {t„, n ^ 1}, образующие процесс восстановления, поступают заявки с независимыми, одинаково распределенными (н, о. р.) временами обслуживания {Sn} на одном из тп (идентичных) процессоров. Обозначим функцию распределения (ф. р.) случайной величины (с. в.) времени между приходами заявок Т„ := tH+i - t„ через А(х) = Р(Т ^ х), а через В(х) = P{S ^ х) ф. р. времени обслуживания заявки. (Индекс опускается, когда рассматривается типичный элемент последовательности н. о. р. с. в.) Заявка п ожидает время Dn > 0 в очереди, формируемой в порядке поступления (FIFO), и поступает на обслуживание в момент времени tn + Dn на процессор, освободившийся первым. Пусть вектор нагрузки

Wn = (Wn, i,..., W„,m) ££:={ie R™: ц < • • ■ < xm}, n^O

состоит из упорядоченной в возрастающем порядке незавершенной работы на процессорах в момент tn прихода заявки п. Вектор Wn удовлетворяет рекурсии Кифера-Вольфовица [13]:

Wn+1 = R (W„д + Sn - Та, Wn,2 - Tn,..., W,hm - Tn)+ , (1)

где оператор R(-) : R"1 —> E располагает компоненты по возрастанию, а (-)+ = тах(0, ■). Время ожидания п-й заявки Dn := Wn>i удовлетворяет модифицированной (классической при т = 1) рекурсии Линдли:

Д.+1 = (Д, + min(Wn,2 - Wn,i, Sn) - Т„)+ , п > 1. (2)

Система GI/G/m стационарна, если выполнено условие

ES

Р = ЁТ<т' ^

которое гарантирует, что процесс {Wn,n ^ 0} является однозависимо регенерирующим, т. е. существует такой вложенный процесс восстановления {Рп, п ^ 1}, что цикл регенерации Wk = {W^+j, 0 ^ j < Д. := 0k+i - Pi,} не зависит от Ри и имеет одно и то же распределение при всех к ^ 1, при этом допускается зависимость только между соседними циклами Wt:, VV^+1, а циклы Wk,Wk+i, г > 1, независимы при любом к ^ 1. Регенерирующий процесс называется положительно возвратным, если Е(3 < со.

В главе 1 получено доказательство стационарности описанной системы GI/G/m, уточняющее процедуру построения момента однозависимой регенерации в следующем фундаментальном результате [12].

Теорема 1. Пусть ES < оо,ЕТ < оо и выполнено условие (3). Тогда при нулевых начальных условиях {Wn, п ^ 0} является положительно возвратным однозависимым регенерирующим процессом.

Далее в главе 1 рассматриваются условия конечности момента порядка к ^ 1 компонент стационарного вектора нагрузки W = [W],..., IV,,), которые существенно используются в дальнейшем анализе [14]. Именно, при условии (3), для компонент вектора W с индексами г ^ \р\ имеют место одни и те же достаточные условия ([а;] — наименьшее целое, не меньшее х):

Е < оо влечет Е [Ж/' < оо, (4)

а для компонент с индексами \р\ < г ^ т моментные свойства зависят от индекса компоненты Wx:

Е < оо влечет Е Щ]к < ос. (5)

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

Ф. р. имеет тяжелый хвост (F 6 Т£), если Е(есХ) = оо для любого е > 0. В качестве такой ф. р. часто используется распределение Парето, представляющее важный для приложений класс распределений с правильно меняющимся хвостом. Ф. p. F имеет правильно меняющийся хвост с показателем —а ^ 0 (F € 7£(—а)), если F(x) := 1 — F(x) ~ x~aL(x) при х —» оо, где функция L медленно меняется на бесконечности (L S 72.(0)). Если X Е 7Z(—a), то с ростом х средняя величина перескока (эксцесса) растет линейно, т. е.

Е(Х-х\X>x) = S*(i/Z*\dF(y)~x, *->оо. (6)

F(x)

Линейный вид графика среднего эксцесса, построенного по значениям выборки, позволяет на практике отнести распределение F к классу TZ := UQ>oi2(—а). Этот способ анализа применяется в экспериментальной части представленной работы (см. гл. 4).

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

нято использовать усеченное на [а, 6] распределение Парето, имеющее вид

F{x) = —0 < а < х < Ь, а > 0. (7)

\ь) 1

Отметим, что метод подбора параметров распределения (7) рассмотрен в работе [11] и используется далее в главе 4.

В третьей главе сначала проведен анализ моделей МС, которые могут быть использованы для описания ВК. Затем основное внимание уделено построению и исследованию следующей новой модели ВК, предложенной в работах [6, 7] и обобщающей классическую модель GI/G/m. Пусть г-й приходящей заявке требуется одновременно случайное число процессоров jV, £ [1, т] на одинаковое время Si. В этом случае рекурсия (1) для вектора нагрузки W, (Ж;д, • • • , Wi<m) принимает вид

Wi+1 = R(Wj,Ni + Sj- Tiy. , Wj,Ni + Sj- Ti,WiiNi+1-Ti,..., Wtjn-Ti)* (8) n, компонент

причем время ожидания заявки г определяется как D, := Wt(N-i), г ^ 1.

Для предложенной модели минорантной будет система в которой

г-я заявка представляет собой группу из TV* независимых заданий, каждое из которых имеет одно и то же время обслуживания S",. Очередное задание немедленно занимает освободившийся процессор. Имеет место следующее свойство монотонности для процессов нагрузки в исходной системе и в системе £<'ош>.

Лемма 1. Пусть = Wq = 0. Тогда

Т] < Wi+U i ^ 0. (9)

Отметим, что система

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

В настоящее время мощности ВК исчисляются сотнями тысяч процессоров, однако задач, масштабируемых на такое количество процессоров, сравнительно немного. Поэтому ограничение Р(ЛГ < ЛАшах) = 1 для некоторого Лгшах <С гп представляется вполне »мотивированным. Обозначим

Т77 711

3 = тт{к > 1 : Р(ЛГ < = 1}, 7\Гтах = (10)

К з

Заметим, что случай 7 = 1 типичен для небольших ВК. Для исходной системы мажорантной будет система где каждая заявка занимает ровно Л'тах = [у] процессоров. Именно, имеет место следующее утверждение.

Лемма 2. Пусть \У0 = = 0. Тогда

Wi < \У\ир\ г > 1.

Отметим, что система эквивалентна стандартной системе обслуживания а/СЦ (с теми же управляющими последовательностями {£„,Тп}). Достаточное условие (3) является, таким образом, достаточным условием стационарности модели ВК.

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

Лемма 3. Рассмотрилг две идентичные т-процессорные систелш £ и Е при начальных условиях ]¥о = в ^ £ = \Уо € Е. Пусть для входных потоков и времен обслуоюивания имеют место неравенства Т* ^ Т;, ¿>г ^ и •ЭД ^ г > 1. Тогда Щ ^ Wi, г ^ 1.

Обозначим р = \ENES, пусть есть число процессоров, требуемых заявкам, находящимся в системе в момент времени Имеет место следующее условие нестационарности предложенной модели (8).

Лемма 4. Если р > т, то у{Ь) —> оо с в. 1.

11

Необходимым и достаточным условием стационарности системы явля-

ется условие

ХЕМ ЕБ < то. (11)

Таким образом, (11) есть необходимое условие стационарности модели (8). В общем случае, различие необходимого условия (11) и достаточного условия (3) может быть значительным и форма критерия стационарности остается открытой проблемой. Однако следующий результат является важным элементом решения проблемы получения критерия стационарности. Обозначим Дп,т = - ШпЛ, п ^ 1.

Лемма 5. Пусть \¥о = 0. Тогда последовательность {Дит}, п > 1 стохастически ограничена.

Подчеркнем, что утверждение леммы 5 верно независимо от стационарности системы (8).

Для модели (8) обозначим

Рх := ~ (Рг 00 при Щ + > то),

{/, := тах(<5г, тт(Рг, 5,)) = тт(Р„ тах(<Зг, 5,)).

Следующее утверждение обобщает классический результат (2).

Лемма 6. В модели (8) величина задержки удовлетворяет рекурсии

А+1 = (А + и{ - Т,)+, г > 0.

Обозначим через IV = (ТУ],..., \Ут) стационарный вектор нагрузки в модели (8). Пусть к(г) — \г/Мтах], 1 ^ г < ш, см. (10). Следствием леммы 2 являются следующие моментные свойства компонент вектора IV, обобщающие результаты (4), (5).

Теорема 2. Пусть р := ES/ET < j и а ^ 1. Тогда имеют место следующие импликации:

1. Для компонент вектора W с индексами 1 ^ г ^ [p]iVmax

< оо влечет EWf < оо.

2. Для компонент вектора W с индексами fр] Nmax < i iC m

ES1+j=x~>т < оо влечет EWf < оо.

Следствием теоремы 2 являются также следующие моментные свойства стационарной задержки заявки в очереди D.

Теорема 3. Пусть выполнены условия теоремы 2. Тогда

< оо влечет ED" < оо.

В четвертой главе приводятся результаты вычислительного эксперимента по моделированию ВК ЦКП КарНЦ РАН (ВК ЦКП) на основе исходных данных лог-файла системы управления заданиями CLEO 5.22 за период с 03.06.2009 г. по 04.02.2011 г., содержащего характеристики п = 8282 заданий, расчет которых велся как в однопроцессорном (47.5% от общего числа), так и в многопроцессорном режимах. Именно, на основе управляющих последовательностей {Ti,Si,Ni, 1 < г < п}, извлеченных из лог-файла CLEO, был проведен расчет процесса нагрузки системы {Wi, 1 <С -i п}. Далее по данным расчета были восстановлены значения времен ожидания заявок в очереди £);, которые были сопоставлены с реально зафиксированными в лог-файле. В таблице 1 представлены основные результаты эксперимента, демонстрирующие хорошее согласие между данными, полученными на основе модели и реальными данными работы кластера. Эксперименты проводились с использованием программного модуля [10] на базе программного пакета R.

Следствием согласованности данных численного моделирования и реальных данных является возможность на основе модели оценить влияние числа процессоров m на такие характеристики качества обслуживания, как среднее время ожидания ED и число неожидающих заявок J2'l=i H А = 0)- Это, в свою очередь, позволяет прогнозировать эффект от увеличения числа процессоров, т. е. планировать развитие аппаратной части системы. В частности, по результатам моделирования, при m ^ 280 на ВК ЦКП не было бы ожидающих заявок. С помощью предложенной модели также было оценено влияние на указанные характеристики качества обслуживания возможности разделения узла для нескольких задач. Именно, в исходной конфигурации каждой заявке узлы предоставлялись в монопольное пользование, что позволяло лучше использовать оперативную память. Однако, при этом возникали простои оборудования, особенно в случае Ni = 1. Для преодоления этого недостатка были проведены эксперименты по моделированию конфигурации, в которой узлы могут разделяться между конкурирующими заявками. Результаты эксперимента, представленные в таблице 1, говорят о значительном снижении среднего времени ожидания заявки в очереди. Это позволило обосновать изменение правил использования ВК ЦКП. В результате активации возможности разделения узла на ВК ЦКП, в действительности, наблюдалось снижение среднего времени ожидания.

Далее в главе 4 выдвинуто и проверено в эксперименте предположение о н. о. р. и независимых между собой с. в. {Ti,Sj, N,}. На основе данных лог-файла CLEO были идентифицированы вид и параметры распределений с. в. Принадлежность распределения классу <S или 1Z определялась на основе соотношения (6). Для моделирования интервалов между приходами заявок использовалось лог-нормальное распределение (относящееся к классу

Таблица 1. Основные результаты числешюго эксперимента по проверке адекватности модели (8) на основе данных лог-файла системы CLEO

Источник данных ¿EÏLiA minj Di maxj Di £Г=1 /(A = o)

JIor-файл CLEO 722 0 288500 7738

Модель 926 0 288500 7672

Модель, разделение узла 176 0 156500 8128

<S), плотность которого имеет вид

f(x) = —1 х > 0. (12)

xcrV 2ix

Методом максимального правдоподобия были получены следующие оценки параметров распределения (12): ц « 5.527872, а « 2.501084. Для моделирования времен между приходами заявок использовалось усеченное распределение Парето (7) с параметрами а = 1, b — 259204, а = 0.2069721. В качестве распределения Ni в модели принято лог-равномерное распределение для заявок, которым требуется 2г, 1 ^ г ^ 6 процессоров. Более точно, использовалось распределение N следующего вида:

il, pi = 0.4758512, „ ч

(1з)

[ 2к, pfc+i = 0.0873581,1 < к ^ 6.

В результате вычисления рекурсии (8) с использованием выборок из распределений интервалов между приходами (12), времен обслуживания (7) и числа требуемых процессоров (13), среднее время ожидания заявки составило и 25000 е., что значительно выше зафиксированного в лог-файле CLEO. Полученный результат говорит, что предположение о н. о. р. управляющих последовательностях не имеет места в данных условиях для рассматриваемого небольшого, не сильно нагруженного ВК ЦКП. Этот результат может быть объяснен наличием обратной связи ВК ЦКП с пользователями, которая

осуществляется при помощи системы отслеживания состояния очереди. Однако, модель с н. о. р. управляющими последовательностями {Т,-, Л7;} может применяться для ВК, в которых отсутствует механизм отслеживания очереди, а также для высоконагруженных ВК. Поэтому результаты моделирования в предположении н. о. р. с. в. могут быть использованы для определения верхней границы (наихудших значений) для соответствующих характеристик реальных систем. В то же время, предложенная модель позволяет охватить широкий класс зависимостей управляющих последовательностей, сохраняя марковский характер рекурсии (8), что делает ее весьма перспективной для исследования отмеченной выше проблемы.

Дополнительным аргументом в пользу адекватности предложенной модели (8) является хорошая согласованность полученных при моделировании значений числа свободных процессоров в системе, т. е. XX1 ЛЖг.г = 0], и соответствующих значений, зафиксированных системой мониторинга ВК ЦКП (данные также приведены в главе 4). Эта вспомогательная, но важная характеристика позволяет оценить степень равномерности нагрузки кластера во времени.

Заключение

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

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

Список публикаций по теме диссертации

1. Морозов Е. В., Румянцев А. С. Модели многосерверных систем для анализа вычислительного кластера // Труды Карельского научного центра Российской академии наук. 2011. Т. 5. С. 75-86.

2. Морозов Е. В., Румянцев А. С. Вероятностные модели многопроцессорных систем: стационарность и моментные свойства // Информатика и ее применения. 2012. Т. 6, № 3. С. 99-106.

3. Morozov Е., Pagano M., Rumyantsev A. Heavy-tailed Distributions with Applications to Broadband Communication Systems // Proceedings of AM-ICT'2007. Vol. 9. Petrozavodsk, 2008. Pp. 157-174.

4. Morozov E., Rumyantsev A. Moment properties of queueing systems and networks // Proceedings of 2010 International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), Moscow, 18-20 Oct. 2010. Moscow: IEEE, 2010. Pp. 1056-1061.

5. Морозов E. В., Румянцев А. С. Регенерация и корреляционные свойства стационарной задержки в одноканальной очереди // Proceedings of International Workshop Distributed Computer and Communication Networks. Theory and Applications (DCCN-2010). Moscow: R&D Company «Information and Networking Technologies», 2010. Pp. 58-67.

6. Морозов E., Румянцев А. Некоторые модели многопроцессорных систем

17

обслуживания с тяжелыми хвостами // Параллельные вычислительные технологии 2011: сборник трудов Международной научной конференции. Челябинск: ЮУрГУ, 2011. С. 555-566.

7. Румянцев А. О стохастическом моделировании вычислительного кластера // Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем: Тезисы докладов Всероссийской конференции с международным участием (18-22 апреля 2011). Москва: РУДН, 2011. С. 46-47.

8. Румянцев А. Моделирование процесса нагрузки вычислительного кластера на примере кластера ЦКП КарНЦ РАН «Центр высокопроизводительной обработки данных» // Материалы XI Всероссийской конференции «Высокопроизводительные параллельные вычисления на кластерных системах». Нижний Новгород: Изд-во Нижегородского госуниверситета, 2011. С. 272-275.

9. Morozov Е. V., Rumyantsev A. S. Stability analysis of a multiprocessor model describing a high performance cluster // XXIX International Seminar on Stability Problems for Stochastic Models and V International Workshop «Applied Problems in Theory of Probabilities and Mathematical Statistics related to modeling of information systems», Book of Abstracts. Moscow: Institute of Informatics Problems, RAS, 2011. Pp. 82-83.

10. Румянцев А. С. Пакет hpcwld для программной среды вычислений R. Свидетельство Федеральной службы по интеллектуальной собственности, патентам и товарным знакам о государственной регистрации программы для ЭВМ №2012610210. 2012.

Цитированная литература

11. Aban I., Meerschaert M., Panorska A. Parameter estimation for the truncated Pareto distribution // Journal of the American Statistical Association. 2006. Vol. 101, no. 473. Pp. 270-277.

12. Chariot F., Ghidouche M., Hamami M. Irréducibilité et récurrence au sens de Harris des «Temps d'attente» des files GI/G/q // Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete. 1978. Vol. 43. Pp. 187-203.

13. Kiefer J., Wolfowitz K. On the theory of queues with many servers // Transactions of the American Mathematical Society. 1955. Vol. 78, no. 1. Pp. 1-18.

14. Scheller-Wolf A., Vesilo R. Sink or Swim Together: Necessary and Sufficient Conditions for Finite Moments of Workload Components in FIFO Multiserver Queues // Queueing Systems. 2011. Vol. 67, no. 1. Pp. 47-61.

Подписано в печать 05.11.12. Формат 60x84 1/16 Гарнитура «Times». Уч.-изд. л. 1,0. Усл. печ. л. 1,0.Тираж 100 экз. Изд. № 336. Заказ № 88.

Карельский научный центр РАН Редакционно-издательский отдел 185003, Петрозаводск, пр. А. Невского, 50

Введение

Глава 1. Классические модели многопроцессорных вычислительных систем.

1.1. Система а/О/т

1.2. Стационарность и возвратность по Харрису.

1.3. Конечность моментов вектора нагрузки.

1.4. Многопроцессорные системы и распределения с тяжелым хвостом

Глава 2. Распределения с тяжелым хвостом.

2.1. Определение классов.

2.2. Замкнутость классов.

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

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

3.1. Системы с независимым освобождением процессоров.

3.2. Системы без ожидания.

3.3. Системы с бесконечным числом процессоров и групповым поступлением

3.4. Модель вычислительного кластера

Глава 4. Численный эксперимент.

4.1. Кластер ЦКП КарНЦ РАН.

4.2. Исследование маргинальных распределений.

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

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

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

Для целей оптимального разделения ресурсов МС между конкурирующими заявками, в МС используются планировщики заданий, или менеджеры очередей (МО). Это, как правило, программные системы, которые на основе данных о текущей нагрузке в МС и некоторой дополнительной информации управляют вычислением задач на процессорах МС. МО позволяют по заранее заданному алгоритму выбирать следующее задание из очереди и отправлять его на выполнение, завершать или приостанавливать задания, прерывать текущее выполнение с учетом приоритетов, вести статистику использования системы. Алгоритм работы таких систем является актуальным объектом для изучения, а оптимизация работы МО является важной и актуальной задачей. Имеющиеся в настоящее время алгоритмы МО плохо справляются с задачей уменьшения простоев оборудования (см. [60, 62, 106]). При разработке новых или настройке параметров уже существующих МО в настоящее время, как правило, прибегают к проверке МО на основе данных реальных лог-файлов запусков задач, архивы которых открыты для общего доступа (например, [41]). Такой подход, с одной стороны, позволяет проверить функционирование МО на реальной системе. С другой стороны, лог-файл отражает конкретную конфигурацию отдельной системы, которая может значительно отличаться от других подобных систем. Скорректировать лог-файл так, чтобы отразить поведение системы с измененными характеристиками, весьма затруднительно [44]. Поэтому важной задачей является изучение свойств потока заявок с целью проведения численных экспериментов по оптимизации МО.

ВК, наряду с МС, занимают важное место в ряду инструментальных средств поддержки научных исследований. Как на этапе проектирования, так и на этапе эксплуатации таких систем важным является вопрос оценки качества обслуживания в них. Это требует разработки методов исследования и новых моделей функционирования ВК. Отметим, что проведение натурного эксперимента на ВК нецелесообразно. Это связано с высоким уровнем финансовых затрат на эксплуатацию ВК, почти половину из которых составляют расходы на электроэнергию. Поэтому необходимо построение адекватной математической модели, отражающей основные особенности ВК. Отметим работы [42, 54, 65], исследующие возможности моделирования ВК, а также работу [108], в которой проведено сравнение имеющихся моделей ВК на основе данных реальных лог-файлов ВК. Наконец, отметим работу [73], которая содержит обзор имеющихся в литературе моделей массово-параллельных МС, а также анализ некоторой новой модели на основе марковских цепей. Важным показателем качества обслуживания в МС является задержка задачи (время ожидания в очереди на обслуживание) и относительное замедление, рассчитываемое как отношение задержки ко времени вычисления задачи. В этой связи важной является задача прогнозирования развития системы и оценки влияния административного решения на показатели качества обслуживания, например, на среднее (или максимальное) время ожидания заявки в очереди.

Наконец, отметим задачи, связанные с построением эффективных параллельных алгоритмов для вычисления на МС. Если степень параллелизма заявки может принимать несколько значений, то возникает задача аналитического описания ускорения, достигаемого на различном числе процессоров, для нахождения оптимального значения степени параллелизма [54].

Большой поток вычислительных задач и заранее неизвестное время выполнения задачи в МС приводят к необходимости использования вероятностных моделей для описания функционирования МС. (Отметим, что параллельные вычисления в качестве основы для вероятностной модели впервые упомянуты в работе [37].) При этом, как правило, рассматривается следующая общая постановка задачи. В МС в случайные моменты времени ti, i ^ 1 поступает поток заявок. Заявке i требуется (случайное или детерминированное) число процессоров Ni для выполнения заданий. В случае, когда задания внутри заявки независимы и могут начинать вычисления в разное время, говорят о приходе пачки заданий.

Если Л^ = 1, говорят о классической МС типа 01/0/т. Если заявке с номером г одновременно требуется случайное число А^ ^ 1 процессоров (т. е. задания должны начать выполнение одновременно), то системы можно разделить на МС с независимым освобождением процессоров [30, 58] и МС с одновременным освобоэ/сдением процессоров [57, 72]. В первом случае времена обслуживания на всех Л^ процессорах являются независимыми одинаково распределенными (н. о. р.), а во втором случае на всех М{ процессорах используется одна и та же реализация времени обслуживания (т. е. времена обслуживания идентичны). Системы второго типа существенно более сложны для анализа [57]. Для таких систем известны лишь численные результаты [72], а при отсутствии буфера — также некоторые аналитические результаты [37, 69, 112]. Заметим, что модели с независимым освобождением процессоров пригодны для описания грид-систе-мы, в то время как одновременное освобождение более соответствует работе ВК.

Вероятностные модели для времени ожидания в очереди Д- заявки с номером г в классической системе 01/0/тп, а также для вектора нагрузки — состоящего из упорядоченной по возрастанию незавершенной работы на процессорах, впервые исследованы в работах [70, 71]. В предположении, что входной поток является процессом восстановления (величины Тг — ¿2-|-1 — являются н. о. р.), а времена обслуживания являются н. о. р. с. в., в [70] получено условие стационарности модели, а в [71] также достаточные условия конечности моментов стационарного времени ожидания V в очереди, а также цикла занятости системы. В работе [99] впервые получен критерий конечности моментов всех компонент стационарного вектора нагрузки У/, а также обнаружена зависимость моментного индекса (максимального конечного момента) от номера компоненты ]¥( в стационарном векторе нагрузки Ш, а также от коэффициента загрузки р — (где без индексов обозначены типичные времена обслуживания и времена между приходами заявок соответственно). Вопрос конечности моментов является особенно актуальным в связи с обнаружением распределений с тяжелым хвостом в процессах, описывающих функционирование МС, см. [92, 108]. Распределения с тяжелым хвостом могут характеризоваться бесконечными значениями моментов с. в., что, в свою очередь, затрудняет оценивание характеристик системы в стационарном режиме (если он существует).

Отдельно следует отметить модели, не связанные непосредственно с описанием ВК, однако позволяющие в той или иной степени отразить основные особенности его функционирования. Так, в предположении т max¿^i N{ (т. е. при большом числе процессоров), поведение МС может быть описано моделью G/G/oo с бесконечным числом процессоров и групповым поступлением заданий. (Применимость таких моделей для описания МС с большим числом процессоров обсуждается в работах [1, 2].) В этой связи отметим работы [15, 77], в которых рассмотрены модели типа GI/G/oo с групповым поступлением и независимым освобождением процессоров.

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

В данной работе выполнен анализ существующих моделей МС, приведены классические результаты, касающиеся стационарности и моментных свойств процесса нагрузки МС. Основное внимание уделено новой модели на основе модели Кифера-Вольфовица для вектора нагрузки МС типа GI/G/m, что позволяет обобщить известные результаты для модели, учитывающей существенные особенности функционирования ВК. Актуальность диссертационной работы подтверждается большим вниманием, которое уделяется моделям МС как при проведении теоретических исследований, так и при внедрении результатов моделирования в технологические процессы.

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

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

1. Исследованы свойства монотонности и условия стационарности процесса нагрузки в предложенной модели.

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

3. Методом численного моделирования проведена проверка адекватности модели на основе данных лог-файла ВК ЦКП КарНЦ РАН.

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

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

На защиту выносятся следующие результаты и положения:

1. Вероятностная модель процесса нагрузки МС, обобщающая классическую модель Кифера-Вольфовица, в которой заявка занимает случайное число процессоров на идентичное время.

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

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

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

5. Результаты численного эксперимента на основе лог-файла работы ВК ЦКП КарНЦ РАН за период 2009-2012 гг., подтверждающие адекватность предложенной модели.

Связь работы с научными программами, темами. Основные результаты диссертации были получены при проведении исследований в рамках темы НИР ИПМИ КарНЦ РАН (гос. №01201151875 «Вероятностный анализ регенеративных и гауссовских коммуникационных систем с использованием методов высокопроизводительных вычислений»). Исследования были частично поддержаны Российским фондом фундаментальных исследований (0Т-07-00088-а, 10-07-00017-а) и Фондом содействия малых форм предприятий в научно-технической сфере (государственный контракт №10491р/16862 от 08.06.2012 г.).

Апробация работы. Результаты работы докладывались и обсуждались па международных научных семинарах "Advances in Methods of Information and Communication Technology" (Петрозаводск, 2007, 2010, 2011 гг.), на международном семинаре "Applied Problems in Theory of Probabilities and Mathematical Statistics related to modeling of information systems" в рамках конгресса ICUMT'10 (Москва, 2010 г.), на международной конференции «Распределенные компьютерные и телекоммуникационные сети: теория и приложения» БСС№10 (Москва, 2010 г.), на всероссийской летней школе «Суперкомпьютерное моделирование и визуализация в научных исследованиях» (Москва, 2010 г.), на всероссийской осенней школе «Суперкомпьютерные технологии и высокопроизводительные вычисления в образовании, науке и промышленности» (Нижний Новгород, 2010 г.), на международной научной конференции «Параллельные вычислительные технологии 2011» (Москва, 2011 г.), на всероссийской конференции с международным участием «Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем» (Москва,

2011 г.), на V Международном семинаре «Прикладные задачи теории вероятностей и математической статистики, связанные с моделированием информационных систем» (Светлогорск, 2011 г.), на научной конференции и школе молодых ученых «Фундаментальные и прикладные исследования в Карелии: современное состояние и перспективы развития» (Петрозаводск, 2011 г.), на XI Всероссийской конференции «Высокопроизводительные параллельные вычисления на кластерных системах» (Нижний Новгород, 2011 г.), на VIII Международной Петрозаводской конференции «Вероятностные методы в дискретной математике» (Петрозаводск, 2012 г.), на Летней Суперкомпьютерной Академии (Москва,

2012 г.).

Материалы диссертации опубликованы в 9 печатных работах, из них 2 статьи в журналах, входящих в перечень ВАК ведущих периодических изданий [9, 10], 4 статьи в сборниках трудов конференций [5, 8, 85, 86] и тезисы 3 докладов [И, 12, 87]. Получено свидетельство о государственной регистрации программы для ЭВМ в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам [13].

Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения и списка литературы. Общий объем диссертации составляет 109 страниц, включая 12 рисунков. Библиография включает 114 наименований.

Заключение

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

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

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

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

1. Боровков А. А. Вероятностные процессы в теории массового обслуживания. М.: Наука, 1972.

2. Гнеденко Б. В., Коваленко И. Н. Ведение в теорию массового осблужива-ния. М.: Наука, 1987.

3. Кормен Т., Лейзерсон Ч., Риверст Р. Алгоритмы: построение и анализ. Москва: МЦНМО, 2002.

4. Лемешко Б. Ю., Постовалов С. Н. О правилах проверки согласия опытного распределения с теоретическим // Методы менеджмента качества. Надежность и контроль качества. 1999. Т. 11. С. 34-43.

5. Морозов Е., Румянцев А. Некоторые модели многопроцессорных систем обслуживания с тяжелыми хвостами // Параллельные вычислительные технологии 2011: сборник трудов Международной научной конференции. Челябинск: ЮУрГУ, 2011. С. 555-566.

6. Морозов Е. В. Регенеративная декомпозиция неоднородных сетей массового обслуживания с марковской маршрутизацией: Докторская диссертация / Институт проблем управления РАН. 1996.

7. Морозов Е. В., Дельгадо Р. Анализ стационарности регенеративных систем обслуживания // Автоматика и Телемеханика. 2009. Т. 70. С. 42-58.

8. Морозов Е. В., Румянцев А. С. Модели многосерверных систем для анализа вычислительного кластера // Труды Карельского научного центра Российской академии наук. 2011. Т. 5. С. 75-86.

9. Морозов Е. В., Румянцев А. С. Вероятностные модели многопроцессорных систем: стационарность и моментные свойства // Информатика и ее применения. 2012. Т. 6, № 3. С. 99-106.

10. Румянцев А. С. Пакет hpcwld для программной среды вычислений R. Свидетельство Федеральной службы по интеллектуальной собственности, патентам и товарным знакам о государственной регистрации программы для ЭВМ №2012610210. 2012.

11. Система управления заданиями Cleo. URL: http://parallel.ru/ cluster/batch-syst em. html (дата обращения: 07.06.2012).

12. Тихоненко О. М. Модели массового обслуживания в системах обработки информации. Минск: Университетское, 1990.

13. Фосс С. Г., Чернова Н. И. Об оптимальности дисциплины FCFS в многоканальных системах и сетях обслуживания // Сибирский математический журнал. 2001. Т. 42, № 2. С. 434-450.

14. ЦКП КарНЦ РАН «Центр высокопроизводительной обработки данных». UR.L: http://cluster.krc.karelia.ru (дата обращения: 07.06.2012).

15. Aban I., Meerschaert М., Panorska A. Parameter estimation for the truncated Pareto distribution // Journal of the American Statistical Association. 2006. Vol. 101, no. 473. Pp. 270-277.

16. Asmussen S. Applied probability and queues. New York: Springer-Verlag, 2003.

17. Athreya K., Ney P. Branching Processes. Berlin: Springer Verlag, 1972.

18. Athreya К. В., Ney P. A new approach to the limit theory of recurrent Markov Chains // Transactions of the American Mathematical Society. 1978. Vol. 245. Pp. 493-501.

19. Bachmat E., Sarfati H. Analysis of SITA policies // Perform. Eval. 2010. Vol. 67, no. 2. Pp. 102-120.

20. Beirlanta J., de Wet Т., Goegebeur Y. A goodness-of-fit statistic for Pareto-type behaviour // Journal of Computational and Applied Mathematics. 2006. Vol. 186. Pp. 99-116.

21. Bischof W. Analysis of M/G/l-Queues with Setup Times and Vacations under Six Different Service Disciplines // Queueing Systems. 2001. Vol. 39. Pp. 265-301.

22. Borovkov A. A. Asymptotic Methods in Queueing Theory. New York: Wiley, 1984.

23. Borst S. C., Boxma O. J., nez queija R. N. Heavy tails: the effect of the service discipline //In Computer Performance Evaluation Modelling Techniques and Tools (TOOLS 2002). Springer, 2002. Pp. 1-30.

24. Botta R. F., Harris C. M. Approximation with generalized hyperexponential distributions: weak convergence results // Queueing Systems. 1986. Vol. 2. Pp. 169-190.

25. Boxma O., Zwart B. Tails in scheduling // SIGMETRICS Perform. Eval. Rev. 2007. Vol. 34, no. 4. Pp. 13-20.

26. Brandt A., Sulanke H. On the GI/M/oo queue with batch arrivals of constant size // Queueing Systems. 1987. Vol. 2. Pp. 187-200.

27. Brill P., Green L. Queues in which customers receive simultaneous service from a random number of servers: A system point approach // Management Science. 1984. Vol. 30, no. 1. Pp. 51-68.

28. Chariot F., Ghidouche M., Hamami M. Irréducibilité et récurrence au sens de Harris des «Temps d'attente» des files GI/G/q // Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete. 1978. Vol. 43. Pp. 187-203.

29. Chistyakov V. P. A theorem on sums of independent positive random variables and its applications to branching random processes // Theory of Probability and Applications. 1964. Vol. 9. Pp. 640-648.

30. Cime W., Berman F. A comprehensive model of the supercomputer workload // Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop. WWC '01. Washington, DC, USA: IEEE Computer Society, 2001. Pp. 140-148.

31. Crovella M. E. Performance Evaluation with Heavy Tailed Distributions (Extended Abstract) //In Job Scheduling Strategies for Parallel Processing. Springer Verlag, 1991. Pp. 1-10.

32. Daley D. The Busy Period of the M/GI/oo Queue // Queueing Systems. 2001. Vol. 38. Pp. 195-204.

33. Dattatreya G. F. Performance Analysis of Queuing and Computer Networks. New York: Chapman & Hall / CRC, 2008.

34. Dijk N., Smeitink E. A non-exponential queueing system with batch servicing. Researchmemorandum, No. 13. Free University, Amsterdam. 1988.

35. Downey A. B. A Parallel Workload Model and Its Implications for Processor Allocation. 1996.

36. Eliazar I. The M/G/oo system revisited: finiteness, summability, long range dependence, and reverse engineering // Queueing Systems. 2007. Vol. 55. Pp. 71-82.

37. Fay G., González-Arévalo В., Mikosch Т., Samorodnitsky G. Modeling teletraf-fic arrivals by a Poisson cluster process // Queueing Systems. 2006. Vol. 54, no. 2. Pp. 121-140.

38. Feitelson D. G. Parallel Workloads Archive: Logs. URL: http:// www.es.huji.ас.il/labs/parallel/workload/logs.html (дата обращения: 07.06.2012).

39. Feitelson D. G. Packing Schemes for Gang Scheduling //In Job Scheduling Strategies for Parallel Processing. Springer-Verlag, 1996. Pp. 89-110.

40. Feitelson D. G. Random Number Generators and Heavy-Tail Distributions.

41. Technical Report 2001-2, School of Computer Science and Engineering, The Hebrew University of Jerusalem. 2001.

42. Feitelson D. G. Workload modeling for computer systems performance evaluation (web draft). http://www.cs.huji.ac.il/ feit/wlmod/wlmod.pdf. 2012.— 05.

43. Feldmann A., Whitt W. Fitting mixtures of exponentials to long-tail distributions to analyze network performance models // Performance Evaluation. 1998. Vol. 31, no. 3-4. Pp. 245-279.

44. Feller W. An introduction to probability theory and its applications. New York: Wiley, 1950.

45. Fialovâ A., Jureckovâ J., Picek J. Estimating Pareto tail index based on sample means // Statistical Journal. 2004. Vol. 2, no. 1. Pp. 75-100.

46. Foss S. Some open problems related to stability. arXiv:0909.0462vl math.PR. 2009.-September.

47. Foss S., Konstantopoulos T. An overview of some stochastic stability methods // Journal of the Operations Research. 2004. Vol. 47, no. 4. Pp. 275-303.

48. Foss S., Korshunov D., Zachary S. An Introduction to Heavy-Tailed and Subex-ponential Distributions. New York: Springer, 2011. P. 123.

49. Foss S. G. On the ergodicity conditions for stochastically recursive sequences // Queueing Systems. 1992. Vol. 12. Pp. 287-296.

50. Foss S. G., Kalashnikov V. V. Regeneration and renovation in queues // Queueing Systems. 1991. Vol. 8. Pp. 211-224.

51. Ganglia Monitoring System. UR.L: http://ganglia.sourceforge.net/ (дата обращения: 07.06.2012).

52. Glynn P. Wide-sense regeneration for Harris recurrent Markov processes: an open problem // Queueing Systems. 2011. Vol. 68, no. 3-4. Pp. 305-311.

53. Goldie C. M., Klüppelberg C. Subexponential distributions // A Practical Guide to Heavy Tails: Statistical Techniques for Analysing Heavy Tails. Birkhauser, Basel., 1997.

54. Green L. Comparing operating characteristics of queues in which customers require a random number of servers // Management Science. 1980. Vol. 27, no. 1. Pp. 65-74.

55. Green L. A Queueing System in Which Customers Require a Random Number of Servers // Operations Research. 1980. Vol. 28, no. 6. Pp. 1335-1346.

56. Greiner M., Jobmann M., Klüppelberg C. Telecommunication traffic, queueing models and subexponential distributions // Queueing Systems. 1999. Vol. 33. Pp. 125-152.

57. Gupta V., Burroughs M., Harchol-Balter M. Analysis of scheduling policies under correlated job sizes // Performance Evaluation. 2010. Vol. 67, no. 11. Pp. 996-1013.

58. Gupta V., Harchol-Balter M., Dai J., Zwart B. On the inapproximability of M/G/K: why two moments of job size distribution are not enough // Queueing Systems. 2010. Vol. 64. Pp. 5-48.

59. Harchol-Balter M. The Effect of Heavy-Tailed Job Size Distributions on Computer System Design //In Proceedings of ASA-IMS Conference on Applications of Heavy Tailed Distributions in Economics. 1999.

60. Harchol-Balter M. Task Assignment with Unknown Duration // Journal of the ACM. 2000. Vol. 49. Pp. 260-288.

61. Jessen A., Mikosch T. Regularly varying functions // Publications de l'institut mathématique. 2006. Vol. 80. Pp. 171-192.

62. Juneja S. Estimating tail probabilities of heavy tailed distributions with asymptotically zero relative error // Queueing Systems. 2007. Vol. 57. Pp. 115-127.

63. Kalashnikov V. V. Regenerative queueing processes and their qualitative and quantitative analysis // Queueing Systems. 1990. Vol. 6. Pp. 113-136.

64. Kaufman J. Blocking in a shared resource environment // IEEE Transactions on Communications. 1981. Vol. 29, no. 10. Pp. 1474-1481.

65. Kiefer J., Wolfowitz K. On the theory of queues with many servers // Transactions of the American Mathematical Society. 1955. Vol. 78, no. 1. Pp. 1-18.

66. Kiefer J., Wolfowitz K. On the Characteristics of the General Queueing Process, with Applications to Random Walk // The Annals of Mathematical Statistics. 1956. Vol. 27, no. 1. Pp. 147-161.

67. Kim S. M/M/s Queueing System Where Customers Demand Multiple Server Use: Dr. Sci. dissertation / Southern Methodist University. 1979.

68. Krampe A., Lepping J., Sieben W. A hybrid Markov chain model for workload on parallel computers // Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing. HPDC '10. New York, NY, USA: ACM, 2010. Pp. 589-596.

69. Leland W., Ott T. J. Load-balancing heuristics and process behavior // SIG-METRICS Perform. Eval. R.ev. 1986. Vol. 14, no. 1. Pp. 54-69. URL: http://doi.acm.org/10.1145/317531.317539.

70. Leslie J. On the non-closure under convolution of the subexponential family // Journal of Applied Probability. 1989. Vol. 26. Pp. 58-66.

71. Lindley D. V. The theory of queues with a single server // Proceedings of Cambridge Philosophic Society. 1952. Vol. 48, no. 2. Pp. 277-289.

72. Liu L., Templeton J. Autocorrelations in infinite server batch arrival queues // Queueing Systems. 1993. Vol. 14. Pp. 313-337.

73. Marsan M. A., Carofiglio G., Garetto M. et al. Of Mice and Models // QoS-IP. 2005. Pp. 15-32.

74. M.E. Crovella A. B. Self-similarity in World Wide Web traffic: evidence and possible causes // IEEE/ ACM Transactions on Networking. 1997. Vol. 5. Pp. 835-846.

75. Morozov E. Stochastic boundness of some queueing systems. Preprint No R-95-2022, ISSN 0908-1216, Dept. Math, and Computer Sci., Aalborg Univ., Aalborg, Denmark. 1995.

76. Morozov E. The tightness in the ergodic analysis of regenerative queueing processes // Queueing Systems. 1997. Vol. 27. Pp. 179-203.

77. Morozov E. Instability of Nonhomogeneous Queueing Networks // Journal of Mathematical Sciences. 2002. Vol. 112, no. 2. Pp. 4155-4167.

78. Morozov E. Coupling and monotonicity of queueing systems. http://hdl.handle.net/2072/9171 CRM Preprint No 779 . 2007.-12.

79. Morozov E. A general multiserver state-dependent queueing system. http://hdl.handle.net/2072/65543 CRM Preprint No 927 . 2010.-02.

80. Morozov E., Pagano M., Rumyantsev A. Heavy-tailed Distributions with Applications to Broadband Communication Systems // Proceedings of AM-ICT'2007. Vol. 9. Petrozavodsk, 2008. Pp. 157-174.

81. Nadarajah S., Kotz S. R. Programs for Computing Truncated Distributions // Journal of Statistical Software. 2006. Vol. 16. Pp. 1-8.

82. Nummelin E. A Splitting Technique for Harris Recurrent Markov Chains // Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete. 1978. Vol. 43. Pp. 309-318.

83. Parkhurst J., Darringer J., Grundmann B. From single core to multi-core: preparing for a new exponential // Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design. ICCAD '06. New York, NY, USA: ACM, 2006. Pp. 67-72.

84. Prabhu N. U. Comments on two papers on queueing theory by J. Kiefer and J. Wolfowitz // Queueing Systems. 1987. Vol. 1. Pp. 311-315.

85. Psounis K., Molinero-Fernández P., Prabhakar B., Papadopoulos F. Systems with multiple servers under heavy-tailed workloads // Performance Evaluation. 2005. Vol. 62. Pp. 456-474.

86. Resnick S. Heavy tailed analysis. Eurandom report 2005-024. 2005.

87. Samorodnitsky G. Long Range Dependence // Foundations and Trends in

88. Stochastic Systems. 2007. Vol. 1, no. 3. Pp. 163-257.

89. Scheller-Wolf A. Further delay moment results for FIFO multiserver queues // Queueing Systems. 2000. Vol. 34. Pp. 387-400.

90. Scheller-Wolf A., Sigman K. Delay moments for FIFO GI/GI/s queues // Queueing Systems. 1997. Vol. 25. Pp. 77-95.

91. Scheller-Wolf A., Sigman K. New bounds for expected delay in FIFO GI/GI/c queues // Queueing Systems. 1997. Vol. 26. Pp. 169-186.

92. Scheller-Wolf A., Vesilo R. Structural interpretation and derivation of necessary and sufficient conditions for delay moments in FIFO multiserver queues // Queueing Systems. 2006. Vol. 54. Pp. 221-232.

93. Scheller-Wolf A., Vesilo R. Sink or Swim Together: Necessary and Sufficient Conditions for Finite Moments of Workload Components in FIFO Multiserver Queues // Queueing Systems. 2011. Vol. 67, no. 1. Pp. 47-61.

94. Schrage L. A proof of the optimality of the shortest remaining processing time discipline // Operations Research. 1968. Vol. 16, no. 3. Pp. 687-690.

95. Shedler G. Regeneration and networks of queues. New York: Springer-Verlag,1987.

96. Sigman K. Queues as Harris recurrent Markov chains // Queueing Systems.1988. Vol. 3. Pp. 179-198.

97. Sigman K. A primer on heavy-tailed distributions // Queueing Systems. 1999. Vol. 33. Pp. 261-275.

98. Sigman K., Wolff R. W. A review of regenerative processes // SIAM Review. 1993. Vol. 35, no. 2. Pp. 269-288.

99. Srinivasan S., Kettimuthu R., Subramani V. Characterization of Backfilling Strategies for Parallel Job Scheduling // In IEEE International Conference on Parallel Processing Workshops. 2002. Pp. 514-519.

100. Starobinski D., Sidi M. Modeling and analysis of power-tail distributions via classical teletraffic methods // Queueing Systems. 2000. Vol. 36. Pp. 243-267.

101. Talby D., Feitelson D. G., Raveh A. A Co-Plot analysis of logs and models of parallel workloads // ACM Transactions on Modeling and Computer Simulation (TOMACS). 2007. Vol. 17, no. 3.

102. Thomson H. Coupling, stationarity, and regeneration. New York: Springer-Verlag, 2000.

103. Whitt W. Embedded renewal processes in the GI/G/s queue // Journal of Applied Probability. 1972. Vol. 9. Pp. 650-658.

104. Whitt W. Comparing counting processes and queues // Advances in Applied Probability. 1981. Vol. 13, no. 1. Pp. 207-220.

105. Whitt W. Blocking when service is required from several facilities simultaneously // AT&T Technical Journal. 1985. Vol. 64, no. 8. Pp. 1807-1856.

106. Willinger W., Taqqu M., Leland M., Wilson D. Self-similarity in high-speed packet traffic: analysis and modelling of ethernct traffic measurements // Statistical Science. 1995. Vol. 10. Pp. 67-85.

107. Wolff R. Stochastic Modelling and the Theory of Queues. New Jersey: Prentice Hall, 1989.1. U'9,1. Список иллюстраций «

108. Время ожидания в реальной (серая линия) и исходной (черная линия) системах на основе лог-файла CLEO . 75

109. Среднее время ожидания в системе с m процессорами на основе лог-файла CLEO. 77

110. Число неожидающих заявок в системе с m процессорами на основе лог-файла CLEO . 78

111. Плотность распределения времени ожидания в системе с блокировкой узла (пунктирная линия) и без блокировки (сплошная линия) на основе лог-файла CLEO. 794.5- Зависимость среднего эксцесса от времени обслуживания. 81

112. Зависимость среднего эксцесса от времени между приходами . 82

113. Квантиль-квантиль график ф. р. времени между приходами и соответствующей равновесной ф. р. 83

114. Плотность распределения времени между приходами (лог. шкала) 85

115. Плотность распределения реального (CLEO) и модельного времен между приходами (лог. шкала). 86

116. Хвост распределения реального (CLEO) и модельного времен обслуживания (лог-лог график). 88

117. График частот требующегося числа процессоров по данным CLEO (серые) и по данным моделирования (без заполнения). 90

118. Автокорреляционная функция числа требуемых процессоров на данных лог-файла SLUR,M. 92

119. Число используемых процессоров (моделирование, серая линия) и среднее число занятых процессоров за сутки по данным Ganglia (черпая линия). 94