Вероятностный анализ процесса нагрузки вычислительного кластера тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Румянцев, Александр Сергеевич

• Румянцев, Александр Сергеевич
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Румянцев, Александр Сергеевич

Введение

Глава 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 наименований.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Румянцев, Александр Сергеевич

Заключение

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Румянцев, Александр Сергеевич, 2012 год

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