Средства управления ресурсами вычислительных систем в режиме обслуживания потока задач с нефиксированными параметрами тема диссертации и автореферата по ВАК РФ 05.13.15, кандидат наук Перышкова Евгения Николаевна

• Перышкова Евгения Николаевна
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Перышкова Евгения Николаевна

Введение

1 Распределенные вычислительные системы

1.1 Архитектура распределенных ВС

1.1.1 Понятие о распределенных ВС

1.1.2 Классификация ВС

1.1.3 Кластерные ВС

1.1.4 Техническая реализация ВС с массовым параллелизмом

1.2 Параллельные алгоритмы и программы

1.2.1 Основные понятия

1.2.2 Модели параллельных вычислений

1.2.3 Средства разработки параллельных программ

1.2.4 Стандарт MPI

1.2.5 Эффективность параллельных программ

1.3 Режимы функционирования распределенных ВС

1.3.1 Монопрограммный режим

1.3.2 Мультипрограммные режимы

1.3.3 Пакетная обработка заданий

1.4 Системы управления ресурсами

1.4.1 Общие сведения

1.4.2 Система управления ресурсами TORQUE

1.4.3 Модульный планировщик Maui

1.4.4 Система управления ресурсами SLURM

1.5 Выводы

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

2.1 Обзор предшествующих работ

2.2 Обработка набора задач с фиксированными параметрами

2.3 Обработка набора задач с нефиксированными параметрами

2.3.1 Генетический алгоритм обработки наборов задач с нефиксированными параметрами

2.3.2 Последовательный алгоритм

2.3.3 Параллельный генетический алгоритм островного типа

2.3.4 Параллельный генетический алгоритм островного типа с распределением набора задач

2.4 Результаты моделирования

2.5 Пакет MOJOS обработки наборов задач с нефиксированными параметрами

2.6 Интеграция с СУР

2.7 Результаты моделирования

2.8 Выводы

3 Алгоритмы формирования подсистем элементарных машин

3.1 Задача формирования подсистемы ЭМ

3.2 Обзор предшествующих работ

3.3 Постановка задачи

3.4 Анализ конкурентного использования каналов связи

3.5 Система оценки времени выполнения коллективных операций

3.6 Эвристический алгоритм формирования подсистем ЭМ

3.7 Выводы

4 Мультикластерная вычислительная система

4.1 Архитектура мультикластерной ВС

4.2 Стандартное программное обеспечение

4.3 Средства организации мультипрограммного функционирования

4.4 Интерфейс программного пакета MOJOS

4.5 Интерфейс системы оценки времени выполнения коллективной операции All-to-All

4.6 Выводы

Заключение

Список сокращений и условных обозначений

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

Приложения

Приложение А

Приложение Б

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

Введение

Актуальность темы исследования и степень ее разработанности. Начиная с середины прошлого столетия в нашей стране и за рубежом ведутся активные исследования в области построения высокопроизводительных вычислительных систем (ВС), которые являются инструментальным средством решения сложных задач, представленных параллельными программами. В архитектурном плане ВС представляет собой совокупность множества элементарных машин (ЭМ) и коммуникационной сети, связывающей их. Основные ресурсы ВС - АЛУ, память и средства ввода/вывода являются логически и технически рассредоточенными по ЭМ. Реализация ЭМ допускает варьирование в широких пределах - от однопроцессорной системы на кристалле до многопроцессорного SMP/NUMA-сервера, оснащенного специализированными ускорителями. Количество ЭМ в современных ВС достигает 98 304 (система IBM BlueGene/Q Sequoia), а число процессорных ядер - 10 649 600 (система Sunway TaihuLight).

Фундаментальный вклад в развитие теории и практики вычислительных систем и средств организации их функционирования внесли выдающиеся ученые, среди которых Е.П. Балашов, В.Б. Бетелин, В.С. Бурцев, В.В. Васильев, В.В. Воеводин, В.М. Глушков, В.Ф. Евдокимов, Э.В. Евреинов, А.В. Забродин, В.П. Иванников, М.Б. Игнатьев, А.В. Каляев, И.А. Каляев, Ю.Г. Косарев, В.В. Корнеев, Л.Н. Королев, А.О. Лацис, С.А. Лебедев, В.К. Левин, И.И. Левин, Г.И. Марчук, В.А. Мельников, Н.Н. Миренков, О.Г. Монахов, Д.А. Поспелов, И.В. Прангишвили, Д.В. Пузанков, Г.Е. Пухов, А.Д. Рычков, Г.Г. Рябов, А.А. Самарский, В.Б. Смолов, А.Н. Томилин, Я. А. Хетагуров, В.Г. Хорошевский, Б.Н. Четверушкин, Ю.И. Шокин, Н.Н. Яненко, P. Balaji, D. Culler, S. Cray, J. Dongarra, W. Gropp, T. Hoeffler, J.L. Traff, L. Lamport , и др.

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

ЭМ системы реализуется множество параллельных программ пользователей. Организация функционирования ВС в мультипрограммных режимах требует решения оптимизационных задач, структура которых определяется информацией, известной о задачах (количестве параллельных ветвей, времени решения, приоритетах задач) и вычислительной системе - принятой модели ВС: допущений относительно топологии коммуникационной сети, конфигурации элементарных машин, а также показателей надежности программно-аппаратных компонентов системы. При решении задач оптимизации функционирования ВС в мультипрограммных режимах большую роль сыграли фундаментальные работы по теории ВС, исследованию операций и оптимальному управлению выдающихся ученых: В.Л. Береснева, Э.Х. Гимади, В.Т. Дементьева, Ю.И. Журавлева, В.С. Танаева, Э.А. Мухачевой, В.Г. Хорошевского, Д.А. Поспелова, D.P. Agrawal, R. Baraglia, R. Bellman, P. Bouvry, D. Johnson, A. Gara, M. Koffman, R. Perego, K. Steiglitz, H. Taha.

При мультипрограммном функционировании ВС считается, что (В.Г. Хорошевский, 2008), (R. Baraglia, 2008) на ресурсы ВС поступают параллельные задачи, характеризующиеся фиксированным рангом - числом ЭМ, необходимых для их реализации, и временем выполнения. В режиме обработки набора задач, предполагается, что заранее известно количество задач и их параметры. В этом случае требуется построить расписание, определяющее распределение задач по подсистемам ЭМ и последовательность их выполнения. Методы организации функционирования ВС в режиме обработки задач с фиксированными параметрами хорошо развиты и получили распространение в современных системах управления ресурсами ВС (SLURM, TORQUE, Altair PBS Pro, IBM Load Leveler, LSF). Значительная часть систем использует алгоритмы динамического улучшения расписаний путем обратного заполнения окон в них (backfilling). Одним из подходов, позволяющим повысить эффективность эксплуатации ВС, является введение задач с нефиксированными параметрами, допускающих запуск на нескольких вариантах конфигураций подсистем ЭМ. Такой подход позволяет алгоритмам организации функционирования ВС находить

более эффективные расписания решения задач (по времени выполнения, времени ожидания задач в очереди). Выделяют два типа задач с нефиксированными параметрами (D.G. Feitelson, L. Rudolph, 1996): пластичные задачи (moldable) и адаптирующейся (malleable, evolving). Адаптирующиеся задачи допускают динамическое изменение ранга подсистемы в ходе своего выполнения. На данный момент такие задачи слабо распространены, в мире ведутся работы по созданию средств их реализации (MPI ULFM, Fenix, ReInit; PMIx). Пластичные задачи допускают решение на подсистемах различных рангов из определенного пользователем множества и не допускают изменения ранга подсистемы в ходе своего выполнения. Такой подход характерен для значительной части MPI-программ, созданных за последние 20 лет. Учитывая сказанное, актуальной является разработка новых моделей, алгоритмов и программного обеспечения организации мультипрограммного обслуживания на ВС потоков задач с нефиксированными параметрами.

В режиме обслуживания потока задач необходимо динамически формировать подсистемы ЭМ различных рангов. При реализации параллельными программами групповых схем информационных обменов (all-to-all, one-to-all scatter, all-to-one gather) возникает одновременное конкурентное использование каналов связи коммуникационной сети ВС. В частности, при заданном размещении процессов по процессорным ядрам, процессы на ядрах одного процессора могут конкурировать за доступ к общему контроллеру памяти; процессы, размещенные на разных процессорах NUMA-узла, разделяют каналы связи межпроцессорного соединения (Intel QPI, HyperTransport); при межузловых обменах процессы одного узла конкурируют за доступ к его коммуникационному контроллеру. Конкуренция за доступ к коммуникационным ресурсам приводит к образованию очередей передачи сообщений в библиотеках стандарта MPI, сетевых адаптерах и коммутаторах, что увеличивает время реализации информационных обменов. Известные алгоритмы формирования в пределах ВС подсистем ориентированы на системы с определенными структурами сетей межмашинных связей (например, на 2D-решетки, гиперкубические и тороидальные структуры, fat tree, Dragonfly, Kautz

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

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

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

2. Разработать алгоритмы формирования расписаний решения на ВС параллельных задач с нефиксированными параметрами.

3. Реализовать программные средства поддержки режима обслуживания потока задач с нефиксированными параметрами в системах управления ресурсами TORQUE и Maui.

4. Разработать модель оценки времени реализации коммуникационных операции типа «all-to-all» для ВС на базе многопроцессорных узлов с общей памятью при разных уровнях конкурентного разделения каналов связи процессами параллельных программ.

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

Научная новизна полученных результатов определяется учетом в созданных методах и алгоритмах нефиксированных параметров параллельных

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

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

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

3. Разработанная модель динамической оценки времени реализации операции типа «all-to-all» в ВС на базе многопроцессорных узлов с общей памятью, в отличии от известных, учитывает падение производительности каналов связи при их конкурентном использовании процессами параллельных MPI-программ.

4. В отличии от известных предложенный алгоритм формирования подсистем элементарных машин выполняет ранжирование и выбор среди всех подсистем заданного ранга оптимальной по времени реализации информационных обменов типа «all-to-all».

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

1. Созданные генетические алгоритмы легли в основу пакета MOJOS поддержки мультипрограммных режимов обработки наборов параллельных задач с нефиксированными параметрами. Применение реализованных средств позволяет сократить суммарное время выполнения набора MPI-программ по сравнению с детерминированными алгоритмами FFDH и BFDH. Выполнена интеграция

разработанного пакета MOJOS с широко используемыми системами управлениями ресурсами TORQUE и Maui.

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

3. Программные средства внедрены в действующую мультикластерную ВС Центра параллельных вычислительных технологий СибГУТИ и Лаборатории вычислительных систем Института физики полупроводников им. А.В. Ржанова СО РАН (ИФП СО РАН).

Основные этапы исследования выполнены в рамках проектов №№ 03062016-0018, 0306-2018-0012 Президиума РАН; при поддержке грантов Российского фонда фундаментальных исследований №№ 18-41-540005, 16-07-00992, 16-0700712; 15-07-00048; Совета Президента РФ по поддержке ведущих научных школ РФ № НШ-2175.2012.9 (руководитель - чл.-корр. РАН В.Г. Хорошевский).

Получено четыре свидетельства о государственной регистрации программ для ЭВМ. Результаты работы внедрены в учебный процесс СибГУТИ, в систему параллельного мультипрограммирования пространственно-распределенной ВС и в систему распределения медиа-контента проекта Сибнет ПАО «Ростелеком», что подтверждается соответствующими актами.

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

сетей. Работа основана на результатах ведущей научной школы в области анализа и организации функционирования большемасштабных ВС (руководитель - чл.-корр. РАН В.Г. Хорошевский).

Положения и результаты, выносимые на защиту.

1. Генетический алгоритм построения расписаний решения задач с нефиксированными параметрами, обеспечивающий сокращение суммарного времени выполнения задач в среднем на 45 % относительно начальных решений, получаемых известными алгоритмами FFDH и BFDH.

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

3. Программное расширение системы управления ресурсами TORQUE, позволяющее сократить время обработки набора задач с нефиксированными параметрами в среднем на 24 % относительно стандартных методов.

4. Программный пакет поддержки режима обслуживания потока задач с нефиксированными параметрами для планировщика Maui, сокращающий время обработки MPI-программ в среднем на 21 % по сравнению с методом «обратного заполнения» (backfilling).

5. Алгоритмические и программные средства оценки времени реализации коммуникационных операции типа «аП-to-all», учитывающие падение производительности каналов связи иерархически организованной коммуникационной сети ВС при их конкурентном использовании процессами параллельных MPI-программ.

6. Алгоритм формирования подсистем ЭМ минимизирующий время реализации коллективных обменов типа «all-to-all» и учитывающий загруженность каналов связи, возникающую в следствии их конкурентного использования процессами параллельных программ. На вычислительных кластерах с многопроцессорными NUMA-узлами и сетью связи стандарта InfiniBand алгоритм

обеспечивает сокращение времени информационных обменов от 16% до 31% по сравнению с известным алгоритмом FF (first fit).

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

Личный вклад. Выносимые на защиту результаты получены соискателем лично. В совместных работах постановки задач и разработка методов их решения осуществлялись при непосредственном участии соискателя: разработка и исследование генетических алгоритмов построения расписаний решения задач с нефиксированными параметрами [133, 136-137], программная реализация алгоритмов и их экспериментальное исследование [96, 102-103, 132].

Степень достоверности и апробация результатов подтверждаются

проведенными экспериментами и моделированием, согласованностью с данными, имеющимися в отечественной и зарубежной литературе. Основные результаты работы докладывались и обсуждались на международных, всероссийских и региональных научных конференциях, в их числе: международные конференции «Актуальные проблемы электронного приборостроения» (г. Новосибирск, 2018), Российская конференции с международным участием «Новые информационные технологии в исследовании сложных структур» (г. Томск, 2018), «Визуальная аналитика» (г. Кемерово, 2017), школа-семинар «Проблемы оптимизации сложных систем» в рамках международной конференции IEEE SIBIRC0N-2017 (г. Новосибирск, 2017), Всероссийская научно-практической конференции с международным участием «Интеллектуальный анализ сигналов, данных и знаний: методы и средства» (г. Новосибирск, 2017), «Инжиниринг & Телекоммуникации» (г. Москва, 2015), российские конференции: «Обработка информации и математическое моделирование» (г. Новосибирск, 2018) «Национальный суперкомпьютерный форум» (г. Переславль-Залесский, 2016), «Перспективные информационные и телекоммуникационные технологии» (г. Новосибирск, 2016).

Публикации. По теме диссертации опубликована 21 работа. Из них: 4 - в журналах из перечня ВАК РФ; 1 - в изданиях, индексируемых Scopus. Получено 4 свидетельства о государственной регистрации программ для ЭВМ.

1 Распределенные вычислительные системы

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

1.1 Архитектура распределенных ВС 1.1.1 Понятие о распределенных ВС

Развитие средств вычислительной техники характеризуется увеличением производительности, надежности и живучести за счет все более полного использования принципа параллелизма. Выделяют два основных подхода к созданию вычислительной техники [1-7]:

1. Построение электронных вычислительных машин (ЭВМ), моделирующих процесс выполнения алгоритма одиночным человеком-вычислителем.

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

Модель вычислителя сформулирована в [4] и наиболее полно по отношению к вычислительным машинам отражена в [6]. Для этой модели характерны последовательное выполнение операций, фиксированная структура, неоднородность связей и функциональных элементов. Использование модели вычислителя для построения высокопроизводительных вычислительных средств

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

Модель коллектива вычислителей сформулирована в работах [9] и получила дальнейшее развитие в работах [1, 7, 8].

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

В основу коллектива вычислителей положены три основополагающих архитектурных принципа [7]:

1. Параллелизм (parallelism, concurrency) при обработке информации.

2. Программируемостъ (programmability, adoptability) структуры (настраиваемости структуры сети межмашинных связей между вычислителями, достигаемой программными средствами).

3. Однородность (homogeneity) конструкции (однородности вычислителей и структуры).

В отличие от одиночного вычислителя, коллектив машин-вычислителей обладает теоретически неограниченной производительностью, обусловленной отсутствием ограничений на увеличение их числа. Кроме того, по сравнению с ЭВМ, построенное на модели коллектива вычислительное средство способно обладать заданной надежностью и живучестью [6-7, 9-11], т.е. возможностью функционировать при отказах элементов, а также допускает простой способ наращивания производительности.

Вычислительное средство, базирующееся на модели коллектива вычислителей, называется вычислительной системой [7].

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

В общем случае, распределенные ВС представляют собой совокупность вычислительных модулей (элементарных машин - ЭМ), соединенных сетью связи, которая способна не только реализовать процесс решения сложной задачи, но и в процессе работы автоматически настраиваться и перестраиваться с целью достижения адекватности между своей структурно-функциональной организацией и характеристиками решаемой задачи [7]. Основной особенностью ВС является отсутствие единого функционального и конструктивно реализованного устройства: все компоненты (устройство управления, процессор и память) являются распределенными. Для организации эффективного функционирования распределенных ВС особое внимание уделяется методам и средствам управления вычислительного процесса и коллективного использования ресурсов в мультипрограммных режимах работы ВС.

1.1.2 Классификация ВС

К вычислительным системам относятся мультипроцессорные ВС, вычислительные кластеры, распределенные ВС и массово-параллельные системы (MPP - massively parallel processing).

Существуют различные подходы к классификации ВС. По классификации Флинна различают четыре класса архитектур вычислительных средств: SISD (Single Instruction stream, Single Data stream), SIMD (Single Instruction, Multiple Data), MIMD (Multiple Instruction, Multiple Data), MISD (Multiple Instruction, Single Data). Классификация базируется на понятии потока, под которым понимается последовательность команд или данных, обрабатываемая процессором.

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

выполнении команд потока требуются операнды (данные), следовательно, поток команд «порождает» поток данных.

Архитектуры MISD, SIMD, MIMD относятся к вычислительным системам. В этих архитектурах имеет место «множественность» потоков или (и) команд, или (и) данных. Множественность характеризуется количеством одновременно реализуемых потоков команд или (и) данных.

Особо выделяются векторные и конвейерные системы, которые часто относят к подклассам SIMD или MISD. Иногда к современным MIMD архитектурам причисляют МРР-, SMP-системы (Symmetric Multiprocessing) и кластеры, причем кластеры и МРР- системы в основном различаются по степени согласованности набора прикладных программ и характеристикам коммуникационных сред [12].

В основу классификации ВС может быть положена техническая организация оперативной памяти. К системам с общей памятью (shared memory) относят ВС, ЭМ (процессорные элементы) которых имеют доступ к общей разделяемой оперативной памяти. Как правило такие ВС работают под управлением одного экземпляра операционной системы. Известными представителями этого класса являются SMP- и NUMA-системы (Nonuniform Memory Access). В системах с распределенной памятью (distributed memory system) каждая ЭМ располагает свой локальной оперативной памятью. Доступ к памяти других ЭМ возможен только через сеть межмашинных связей. В таких ВС каждая ЭМ функционирует под управлением своего экземпляра операционной системы. К этому классу относятся MPP и кластерные системы.

Существуют и другие классификации, которые кладут в основу таксономии классификацию Флинна, а также Хокни, Фенга, Хендлера и Скилликорна [13], но они не делают различий в организации распределенных вычислений с учетом взаимодействий процессов. Общим свойством, обеспечивающим возможность повышения производительности масштабируемых систем, является распределенность процессов вычислений и данных. Это свойство характерно и для SMP-архитектур, если принять во внимание типичную иерархию «кэш процессора

— основная память — подсистема ввода/вывода». Спецификации InfiniBand, RapidIO, развивающие идеи стандарта SCI (Scalable Coherent Interface) и спецификаций Next Generation I/O, Future I/O, основаны на моделях распределенной обработки. Выигрыш от распределения вычислений и данных определяется степенью параллелизма, организацией взаимодействия и планированием процессов.

1.1.3 Кластерные ВС

Кластерная ВС или кластер (computer cluster) - это композиция множества вычислителей, сети связей между ними и программного обеспечения, предназначенная для параллельной обработки информации (реализации параллельных алгоритмов решения сложных задач). При формировании кластерной ВС используются массовые аппаратурно-программные средства. Это обеспечивает высокую технико-экономическую эффективность кластерных ВС [7, 13-15].

Основной функционально-структурной единицей вычислительных ресурсов в кластерных ВС является ЭМ (вычислительный узел), представленная, в большинстве случаев, в виде многопроцессорного узла с SMP/NUMA архитектурой.

Коммуникационные сети кластерных ВС преимущественно строятся на базе технологий InfiniBand и Gigabit Ethernet. Для объединения вычислительных узлов в систему используются коммутаторы с фиксированным количеством входных портов для подключения оконечных устройств (вычислительных узлов, коммутаторов, систем хранения данных и т. п.). В этих условиях для построения большемасштабных кластерных ВС используются различные схемы формирования составных коммутаторов. Например, топологии типа «толстое дерево» (fat tree), «бабочка» (butterfly) и Clos. Такой подход к организации коммуникационной сети позволяет обеспечить высокую пропускную способность и одинаковое количество

промежуточных коммутаторов между элементарными машинами, подключенных к коммутаторам одного уровня.

На рисунке 1.1 представлен пример кластерной ВС из 8 четырех ядерных элементарных машин, объединенных сетью с топологией «толстое дерево».

Рисунок 1.1 - Вычислительная система из 8 четырех ядерных ЭМ (топология

«толстое дерево»)

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

Список литературы диссертационного исследования кандидат наук Перышкова Евгения Николаевна, 2018 год

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

1. Дмитриев, Ю. К. Вычислительные системы из мини-ЭВМ [Текст] / Ю. К. Дмитриев, В. Г. Хорошевский. - М. : Радио и связь, 1982. - 304 с.

2. Евдокимов, В. Ф. Параллельные вычислительные структуры на основе разрядных методов [Текст] / В. Ф. Евдокимов, А. И. Стасюк. - К. : Наукова думка, 1987. - 311 с.

3. Евреинов, Э. В. О возможности построения вычислительных систем в условиях запаздывания сигналов [Текст] / Э. В. Евреинов // Вычислительные системы. - 1962. - № 3. - С. 3-16.

4. Евреинов, Э. В. Однородные вычислительные системы, структуры и среды [Текст] / Э. В. Евреинов. - М. : Радио и связь, 1981. - 208 с.

5. Евреинов, Э. В. Однородные универсальные вычислительные системы высокой производительности [Текст] / Э. В. Евреинов, Ю. Г. Косарев. -Новосибирск : Наука. Сибирское отделение. - 1966. - 308 с.

6. Евреинов, Э.В. Однородные вычислительные системы [Текст] / Э.В. Евреинов, В.Г. Хорошевский. - Новосибирск : Наука. Сибирское отд-е, 1978. -319 с.

7. Хорошевский, В. Г. Архитектура вычислительных систем [Текст] / В. Г. Хорошевский. - М. : МГТУ им. Н. Э. Баумана, 2008. - 520 с.

8. Корнеев, В. В. Архитектура вычислительных систем с программируемой структурой [Текст] / В. В. Корнеев. - Новосибирск : Наука, 1985. - 164 с.

9. Додонов, А. Г. Введение в теорию живучести вычислительных систем [Текст] / А. Г. Додонов, М. Г. Кузнецова, Е. С. Горбачик. - Киев : Наукова Думка, 1990. - 180 с.

10. Хорошевский, В. Г. Вычислительная система МИКРОС [Текст] / В. Г. Хорошевский. - Новосибирск : Препринт ИМ СО АН СССР 38 (ОВС-19), 1983. - 52 с.

11. Хорошевский, В. Г. Инженерный анализ функционирования вычислительных машин и систем [Текст] / В. Г. Хорошевский. - М. : Радио и связь, 1987. - 256 с.

12. Корнеев, В. В. Параллельные вычислительные системы [Текст] / В. В. Корнеев. - М. : Нолидж, 1999. - 320 с.

13. Воеводин, В. В. Параллельные вычисления [Текст] / В. В. Воеводин, Вл. В. Воеводин. - СПб. : БХВ-Петербург, 2002. - 608 с.

14. Забродин, А.В. Суперкомпьютеры - состояние и развитие [Текст] / А.В. Забродин, В.К. Левин // Автоматика и телемеханика. - 2007. - № 5. - С. 4-7.

15. Левин, В.К. Высокопроизводительные мультипроцессорные системы [Текст] / В.К. Левин // Информационные технологии и вычислительные системы. -1995. - № 1. - С. 12-21.

16. Alverson, R. The Gemini System Interconnect [Text] / R. Alverson, D. Roweth, L. Kaplan // Proc. 18th IEEE Symposium on High Performance Interconnects. -Washington, DC: IEEE Press. - 2010. - P. 83-87.

17. Chen, D. The IBM Blue Gene/Q interconnection network and message unit [Text] / D. Chen, Eisley N.A., Heidelberger P., Senger R., et al. // Proc. International Conference for High Performance Computing, Networking, Storage and Analysis. New York: ACM Press. - 2011. - URL: http://dx.doi.org/10.1145/ 2063384.2063419.

18. Ajima, Y. The Tofu Interconnect [Text] / Y. Ajima, T. Inoue, S. Hiramoto, T. Shimizu, Y. Takagi // IEEE Micro. - 2012. - Vol. 32, no. 1. - P. 21-31.

19. Корнеев, В.В. Вычислительные системы [Текст] / В.В. Корнеев. - М. : Гелиос АРВ, 2004. - 512 с.

20. Вальковский, В. А. Распараллеливание алгоритмов и программ. Структурный подход [Текст] / В. А. Вальковский. - М. : Радио и связь, 1989. - 176 с.

21. Васильев, В. В. Многопроцессорные вычислительные структуры для анализа задач на сетях [Текст] / В. В. Васильев, А. Г. Додонов // Проблемы электроники и вычислительной техники. - 1976. - №4. - С. 85-97.

22. Воеводин, В. В. Математические модели и методы в параллельных процессах [Текст] / В. В. Воеводин. - М. : Наука, 1986. - 296 с.

23. Гергель, В. П. Основы параллельных вычислений для многопроцессорных вычислительных систем [Текст] / В. П. Гергель, Р. Г. Стронгин. - Нижний Новгород : Изд-во ННГУ, 2003. - 184 с.

24. Каляев, А. В. Параллельный компьютер с программируемой под структуру задачи архитектурой [Текст] / А. В. Каляев [и др.] // Труды Шестого Международного семинара "Распределённая обработка информации". -Новосибирск : СО РАН, 1998. - С. 25-29.

25. Каляев, А. В. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений [Текст] / А. В. Каляев, И. И. Левин. - М. : Янус-К, 2003. - 380 с.

26. Каляев, И. А. Реконфигурируемые мультиконвейерные вычислительные структуры [Текст] / И. А. Каляев. - Ростов-на-Дону : ЮНЦ РАН, 2008. - 320 с.

27. Косарев, Ю. Г. Распараллеливание по циклам [Текст] / Ю. Г. Косарев // Вычислительные системы. - 1967. - Вып. 24. - С. 3-20.

28. Малышкин, В. Э. Параллельное программирование мультикомпьютеров [Текст] / В. Э. Малышкин, В. Д. Корнеев. - Новосибирск : НГТУ, 2006. - 296 с.

29. Миллер, Р. Последовательные и параллельные алгоритмы: Общий подход [Текст] / Р. Миллер, Л. Боксер. - М. : БИНОМ. Лаборатория знаний, 2006. - 406 с.

30. Миренков, Н. Н. Параллельное программирование для многомодульных вычислительных систем [Текст] / Н. Н. Миренков. - М. : Радио и связь, 1989. -319 с.

31. Вальковский, В. Е. Элементы параллельного программирования [Текст] / В. Е. Вальковский, В. Е. Котов, А. Г. Марчук, Н. Н. Миренков. - М. : Радио и связь, 1983. - 240 с.

32. Самарский, А. А. Языки и параллельные ЭВМ : сб. ст. [Текст] / А. А. Самарский. - М. : Наука, 1990. - 91 с.

33. Яненко, Н. Н. Параллельные вычисления в задачах математической физики на вычислительных системах с программируемой структурой [Текст] /

Н. Н. Яненко, В. Г. Хорошевский, А. Д. Рычков // Электронное моделирование. -1984. - Т. 6, № 1. - С. 3-8.

34. Kielmann, T. Fast Measurement of LogP Parameters for Message Passing Platforms [Text] / T. Kielmann, H. E. Bal, K. Verstoep // Proceedings of the 15 IPDPS 2000 Workshops on Parallel and Distributed Processing. — London, UK, UK : SpringerVerlag.- 2000. - P. 1176-1183.

35. Leslie G. Valiant. A bridging model for parallel computation [Text] / Leslie G. Valiant // Communications of the ACM. - 1990. - Vol. 33, no. 8. -P. 103-111.

36. Alexandrov, A. LogGP: Incorporating Long Messages into the LogP Model — One Step Closer Towards a Realistic Model for Parallel Computation [Text] / A. Alexandrov, M. F. Ionescu, K. E. Schauser, C. Scheiman // Technical report, University of California at Santa Barbara. - 1995. - 21 p.

37. Culler, D. LogP: Towards a Realistic Model of Parallel Computation [Text] / D. Culler, R. Karp, D. Patterson [et al.] // ACM SIGPLAN Notices. - 1993. - Vol. 28, no. 7. - P. 1-12.

38. Hockney, R. The communication challenge for MPP: Intel Paragon and Meiko CS-2 [Text] / R. W. Hockney // Parallel Computing. - 1994. - Vol. 20, no. 3. - P. 389398.

39. Badia, R. M. Predicting MPI applications behavior in grid environments [Text] / R. M. Badia, J. Labarta, J. Gimenez // In Workshop on Grid Applications and Programming Tools. — [S. l. : s. n.], 2003.

40. Bagrodia, R. Parallel Simulation of Large-Scale Parallel Applications [Text] / R. Bagrodia, E. Deelman, T. Phan // International Journal of High Performance Computing Applications. - 2001. - Vol. 15, no. 1. - P. 3-12.

41. Rodriguez, G. Generation of Simple Analytical Models for Message Passing Applications [Text] / G. Rodriguez, R. M Badia, J. Labarta // 10th International Euro-Par Conference. - [S. l. : s. n.], 2004.

42. Rugina, R. Predicting the Running Times of Parallel Programs by Simulation [Text] / R. Rugina, K. E. Schauser // Proceedings of the 12th. International Parallel

Processing Symposium on International Parallel Processing Symposium. - [S. l.] : IEEE Computer Society, 1998.

43. Schaeli, B. A simulator for adaptive parallel applications [Text] / B. Schaeli, S. Gerlach, R. D. Hersch // Journal of Computer and System Sciences. - 2008. - Vol. 74, no. 6. - P. 983-999.

44. Zheng, G. Simulation-based Performance Prediction for Large Parallel Machines [Text] / G. Zheng, T. Wilmarth, P. Jagadishprasad, L. V. Kale // Int. Journal of Parallel Programming. - 2005. - Vol. 33, no. 2. - P. 183-207.

45. Hoefler, T. LogGOPSim - Simulating Large-Scale Applications in the LogGOPS Model [Text] / T. Hoefler, T. Schneider , A. Lumsdaine // Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing. - [S. l. : s. n.], 2010. - P. 597- 604.

46. Аветисян, А. И. Прогнозирование производительности MPI-программ на основе моделей [Текст] / А.И. Аветисян, С.С. Гайсарян, В.П. Иванников, В.А. Падарян // Автоматика и телемеханика. - 2007. - С. 8-17.

47. Hoefler, T. LogGP in Theory and Practice - An In-depth Analysis of Modern Interconnection Networks and Benchmarking Methods for Collective Operations [Text] / T. Hoefler, T. Schneider, A. Lumsdaine // Elsevier Journal of Simulation Modelling Practice and Theory. - 2009. - Vol. 17, no. 9. - P. 1511-1521.

48. Барский, А. Б. Планирование параллельных вычислительных процессов [Текст]/ А. Б. Барский. - М.: Машиностроение, 1980. - 192 с.

49. Барский, А. Б. Параллельные процессы в вычислительных системах [Текст] / А. Б. Барский. - М. : Изд-во "Радио и связь", 1990. - 256 с.

50. Монахов, О. Г. Параллельные системы с распределенной памятью: структуры и организация взаимодействий [Текст] / О. Г. Монахов, Э. А. Монахова. - Новосибирск : Изд-во СО РАН, 2000. - 242 с.

51. Монахов, О. Г. Параллельные системы с распределенной памятью: управление ресурсами и заданиями [Текст] / О. Г. Монахов, Э. А. Монахова. -Новосибирск : Изд-во ИВМиМГ СО РАН, 2001. - 168 с.

52. Панфилов, И. В. Вычислительные системы [Текст] / И. В. Панфилов, А. М. Половко. - М. : Изд-во "Советское радио", 1980. - 302 с.

53. Поспелов, Д. А. Введение в теорию вычислительных систем [Текст] / Д. А. Поспелов. - М. : Изд-во "Советское радио", 1972. - 280 с.

54. Hovestadt, M. Scheduling in HPC Resource Management Systems: Queuing vs. Planning [Text] / M. Hovestadt, O. Kao, A. Keller, A. Streit // Proceedings of the 9th Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP), LNCS. - 2003.

- P. 1-20.

55. Mohr, B. System Software Stacks Survey [Electronic resource]. - [S. l. : s. n.].

- URL : http://www.exascale.org/mediawiki/images/3/3c/Iesp-sfo-mohr-stack-survey-2.pdf (online; accessed: 2018-04-10)

56. TORQUE resource manager [Electronic resource]. - [S. l. : s. n.]. - URL : http://www.adaptivecomputing.com/products/opensource/torque (online; accessed: 2018-08-25).

57. MAUI scheduler [Electronic resource]. - [S. l. : s. n.].- URL : http://www.adaptivecomputing.com/products/open-source/maui/ (online; accessed: 2018-06-15).

58. SLURM workload manager [Electronic resource]. - [S. l. : s. n.]. - URL : https://slurm.schedmd.com/documentation.html (online; accessed: 2018-07-05).

59. Ортега, Д. Введение в параллельные и векторные методы решения линейных систем [Текст] / Д. Ортега. - М. : Мир, 1991. - 366 с.

60. Коффман, Э. Г. Теория расписаний и вычислительные машины [Текст]/ Э. Г. Коффман, Л. Дж. Бруно, Р. Л. Грэхем, В. Г. Коглер. - М.: Изд-во «Наука», 1984. - 336 с.

61. Седельников, М.С. Алгоритмы распределения набора задач с переменными параметрами по машинам вычислительной системы [Текст] / М. С. Седельников // Автометрия. - 2006. - T. 42. - № 1. - С. 68-76.

62. Мухачева, Э. А. Генетический алгоритм блочной структуры в задачах двумерной упаковки [Текст] / Э .А. Мухачева, А. С. Мухачева, А. В. Чиглинцев // Информационные технологии. Машиностроение. - М., 1999. - №11. - С. 13 -18.

63. Мухачева, А. С. Задачи двумерной упаковки: развитие генетических алгоритмов на базе смешанных процедур локального поиска оптимального решения [Текст] / А. С. Мухачева, А. В. Чиглинцев, М.А. Смагин [и др.] // Приложение к журналу Информационные технологии. Машиностроение. - М., 2001. - №10. - 24 с.

64. Feitelson, D. G. Toward convergence in job schedulers for parallel supercomputers [Text] / D. G. Feitelson, L. Rudolph // Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science, 1996. - Vol. 1162. - P. 1-26.

65. Sabin, G. Moldable parallel job scheduling using job efficiency: an iterative approach [Text] / Sabin G., Lang M., Sadayappan P. // Job Scheduling Strategies for Parallel Processing. - Springer Berlin Heidelberg, 2007. - P. 94-114.

66. Khandekar, R. Real-time scheduling to minimize machine busy times [Text] / R. Khandekar [et al.] // Journal of Scheduling, 2010. - P. 1-13.

67. Huang, K-C. Online Scheduling of Moldable Jobs with Deadline [Text] / K-C. Huang, W. Hsieh, C-H. Hung // International Journal of Electronics and Information Engineering, Vol.2, No.2 - P. 73-77.

68. Thakur, R. Optimization of Collective Communication Operations in MPICH [Text] / R. Thakur, Rabenseifner R., William G. // International Journal of High Performance Computing Applications. - 2005. - Vol. 19, no. 1. - P. 49-66.

69. Jin, G. Implementation and Performance Evaluation of the HPC Challenge Benchmarks in Coarray Fortran 2.0. [Text] / G. Jin, J. Mellor-Crummey, L. Adhianto, W. N. Scherer III, C. Yang. // In Proceedings of the 2011 IEEE Intl. Parallel & Distributed Processing Symposium. - 2011. - P. 1089-1100.

70. Аветисян, А. И. Среда ParJava для разработки SPMD-программ для однородных и неоднородных сетей JavaVM [Текст] / А. И. Аветисян, И. В. Арапов, С. С. Гайсарян, В. А. Падарян // Труды Института Системного Программирования Российской Академии Наук. - 2000. - Т. 2. - C. 49-64.

71. Ильяков, В. Н. Анализ и предсказание эффективности выполнения DVM-программ на неоднородных сетях ЭВМ [Текст] / В. Н. Ильяков, И. В. Коваленко,

В. А. Крюков // Научный сервис в сети Интернет. Труды Всероссийской научной конференции. - М., 2003. - С. 181-182.

72. Алексахин, В. Ф. Система автоматизации разработки параллельных программ для вычислительных кластеров и сетей фУМсистема) [Текст] /

B. Ф. Алексахин, В. Н. Ильяков, Н. А. Коновалов, Н. В. Ковалева, В. А. Крюков, Н. В. Поддерюгина, Ю. Л. Сазанов // Научный сервис в сети Интернет. Труды Всероссийской научной конференции. - М., 2002. - С. 272-273.

73. Абрамов, С.М. Т-Система с открытой архитектурой [Текст] /

C. М. Абрамов, А. И. Адамович, А. В. Инюхин, А. А. Московский, В. А. Роганов, Ю. В. Шевчук, Е. В. Шевчук // Труды международной научной конференции «Суперкомпьютерные системы и их применение». - Минск, 2004. - С. 18-23.

74. Абрамов, С.М Open TS: архитектура и реализация среды для динамического распараллеливания вычислений [Текст] / С. М. Абрамов, А. А. Московский, В. А. Роганов, Ю. В. Шевчук, Е. В. Шевчук, Н. Н. Парамонов, О. П. Чиж // Труды Всероссийской научной конференции. - М., 2005. - С. 79-81.

75. Barik, R Communication Optimizations for Distirbuted - Memory X10 Programs [Text] / R. Barik, J. Zhao, D. Grove, I. Peshansky, Z. Budimlic, V. Sarkar // IEEE International Parallel and Distributed Processing Symposium, 2011. - P. 1-13.

76. Chen, W. Communication Optimizations for Fine-grained UPC Applications [Text] / W. Chen, C. Iancu, K. Yelick // 14th International Conference on Parallel Architectures and Compilation Techniques (PACT), 2005. Tech Report LBNL-58382.

77. Callahan, D. The Cascade High Productivity Language [Text] / D. Callahan, B. L. Chamberlain, H. P. Zima // HIPS 2004, 2004. - P. 52-60.

78. Курносов, М. Г. Реализация алгоритмов коллективных обменов: временная и пространственная эффективность [Текст] / М. Г. Курносов // Тринадцатая международная азиатская школа-семинар "Проблемы оптимизации сложных систем" в рамках международной мультиконференции IEEE SIBIRCON-2017, 2017.

79. Танаев, В. С. Теория расписаний. Одностадийные системы [Текст] / В. С. Танаев, В. С. Гордон, Я. М. Шафранский. - М. : Наука, 1984. - 381 с.

80. Танаев, В. С., В. Шкурба В. Введение в теорию расписаний [Текст] / В. С. Танаев, В. В. Шкурба. — М. : Наука, 1975. — 256 с.

81. Шмелев, В. В. Метод упорядочения в задачах календарного планирования [Текст] / В. В. Шмелев. Препринт. - М.: ВНИИСИ, 1983. — С. 5-16.

82. Шмелев, В. В. Точные штрафные функционалы в задачах календарного планирования [Текст] / В. В. Шмелев // Автоматика и телемеханика. - 1999. - № 9. - С. 107-114.

83. Coffman, E.G. Performance bounds for level-oriented two-dimensional packing algorithms [Text] / E.G. Coffman, M.R. Garey, D.S. Johnson, R.E. Tarjan. // SIAM Journal on Computing. - 1980. - P. 808-826.

84. Baker, B.S. A 5/4 algorithm for two-dimensional packing [Text] / B.S. Baker, D.J. Brown, and H.P. Katseff // Journal of Algorithms. - 1981. - P. 348-368.

85. Berkey, J.O. Two dimensional finite bin packing algorithms [Text] / J.O. Berkey, P.Y. Wong // Journal of Operational Research. - 1987. - Vol 2. -P. 423-429.

86. Chazelle, B. The bottom-left bin packing heuristic: An efficient implementation [Text] / B. Chazelle // IEEE Transactions on Computers. - 1983. - Vol. 32. - P. 697-707.

87. Chung, F.K.R. On packing two-dimensional bins [Text] / F.K.R. Chung, M.R. Garey, D.S. Johnson // SIAM J. Algebraic Discrete Methods. - 1982. - Vol. 3. -P. 66-76.

88. Frenk, J.B. Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem [Text] / J.B. Frenk, G.G. Galambos // Computing. - 1987. - Vol. 39. -P. 201-217.

89. Schiermeyer I. Reverse-fit: A 2-optimal algorithm for packing rectangles [Text] / I. Schiermeyer // In Proceedings of 2nd European Symposium on Algorithms. -1994. - P. 290-299.

90. Sleator, D.D. A 2.5 times optimal algorithm for packing in two dimensions [Text] / D.D. Sleator // Information Processing Letters. - 1980. - Vol. 10, no. 1. -P. 37-40.

91. Steinberg. A. A strip-packing algorithm with absolute performance bound [Text] / A. Steinberg // SIAM Journal on Computing. - 1997. - Vol. 9. - P. 401-409.

92. Ntene, N. A survey and comparison of guillotine heuristics for the 2D oriented offline strip packing problem [Text] / Ntene N., Vanvuuren J. // Discrete Optimization. -2009. - Vol. 6, no. 2. - P. 174-188.

93. Grudenic, I. Scheduling Algorithms and Support Tools for Parallel Systems [Text] / I. Grudenic // IEEE, 2012.

94. Utrera, G. Another approach to backfilled jobs: applying virtual malleability to expired windows [Text] / G. Utrera, J. Corbalan, J. Labarta // Proceedings of the 19th annual international conference on Supercomputing. - ACM, 2005. - P. 313-322.

95. Sarood, O. Maximizing throughput of overprovisioned hpc data centers under a strict power budget [Text] / O. Sarood et al. // Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. -IEEE Press, 2014. - P. 807-818.

96. Свидетельство 2012613762 РФ. Программа моделирования и анализа алгоритмов формирования расписаний решения масштабируемых задач на распределённых вычислительных системах: свидетельство о государственной регистрации программы для ЭВМ / В. Г. Хорошевский, А. В. Ефимов, С. Н. Мамойленко, Е. Н. Перышкова, К. Е. Крамаренко, Р. И. Кожушко; заявитель и патентообладатель СибГУТИ; заявл. 05.03.2012, опубл. 20.04.2016. [Электронный ресурс]. - [Б. м. : б. и.]

97. Сайт центра параллельных вычислительных технологий СибГУТИ [Электронный ресурс] - URL : http://cpct.sibstuis.ru

98. Parallel workloads archive [Electronic resource]. - [S. l. : s. n.]. - URL : http://www.cs.huji.ac.il/labs/parallel/workload (online; accessed: 2018-04-10).

99. Cirne, W. A model for moldable supercomputer jobs [Text] / W. Cirne, F. Berman // 15th Intl. Parallel & Distributed Processing Symp. - 2001.

100. Cirne, W. A Comprehensive Model of the Supercomputer Workload [Text] / W. Cirne, F. Berman // 4th Ann. Workshop Workload Characterization. - 2001.

101. Downey, A. B. A Parallel Workload Model and Its Implications for Processor Allocation [Text] / A. B. Downey // 6th Intl. Symp. High Performance Distributed Computing. - 1997.

102. Свидетельство 2016618446 РФ. Модуль планировщика MAUI, организующий работу масштабируемых задач на распределенных вычислительных системах: свидетельство о государственной регистрации программы для ЭВМ / Е. Н. Перышкова, А. В. Ефимов, С. Н. Мамойленко; заявитель и патентообладатель ИФП СО РАН; заявл. 01.06.2016, опубл. 20.08.2016. [Электронный ресурс]. - [Б. м. : б. и.]

103. Свидетельство 2016618768 РФ. Модуль системы управления ресурсами TORQUE организующий работу масштабируемых задач на распределенных вычислительных системах: свидетельство о государственной регистрации программы для ЭВМ / Е. Н. Перышкова, А. В. Ефимов, С. Н. Мамойленко; заявитель и патентообладатель СибГУТИ; заявл. 08.06.2016, опубл. 05.08.2016. [Электронный ресурс]. - [Б. м. : б. и.]

104. Bani-Mohammed, S. An efficient non-contiguous processor allocation strategy for 2D mesh connected multicomputers [Text] / S. Bani-Mohammed [et al.] // Information Sciences: an International Journal. - 2007. -Vol. 177, no. 14 - P. 2867-2883.

105. Bender, M. A. Communication-Aware Processor Allocation for Supercomputers [Text] / M. A. Bender [et al.] // Algorithmica. - 2008. - Vol. 50, no. 2. - P. 279-298.

106. Choo, H. Processor Scheduling and Allocation for 3D Torus Multicomputer Systems [Text] / H. Choo [et al.] // IEEE Transactions on Parallel and Distributed Systems. - 2000. - Vol. 11, no. 5. - P. 475-484.

107. Lo, V. Non-Contiguous Processor Allocation Algorithms for Mesh-Connected Multicomputers [Text] / V. Lo, K. Windisch, W. Liu, B. Nitzberg // IEEE Transactions on Parallel and Distributed Systems. - 1997. - Vol. 8, no. 7. - P. 712-726.

108. Steffenel, L. A. Modeling Network Contention Effects on All-to-All Operations [Text] / L. A. Steffenel // IEEE Press. - 2006.

109. Prisacari, B. Bandwidth-optimal all-to-all exchanges in fat tree networks [Text] / B. Prisacari, G. Rodriguez, C. Minkenberg, T. Hoefler // Proceedings of the 27th international ACM conference on International conference on supercomputing. - 2013.

110. Chuang, P.-J. Allocating Precise Submeshes in Mesh Connected Systems [Text] / P.-J. Chuang, N.-F. Tzeng // IEEE Transactions on Parallel and Distributed Systems. - 1994. - Vol. 5, no. 2. - P. 211-217.

111. Li, K. A Two-Dimensional Buddy System For Dynamic Resource Allocation in a Partitionable Mesh Connected System [Text] / K. Li, K. Cheng, // Journal of Parallel and Distributed Computing. - 1991. - Vol. 12, no. 1. - P. 79-83.

112. Qiao, W. Efficient Processor Allocation for 3D Tori [Text] / W. Qiao, L. M. Ni // Proceedings of the International Parallel Processing Symposium. - 1995. -P. 466-471.

113. Moore, S. Q. The Effects of Network Contention on Processor Allocation Strategies [Text] / S. Q. Moore, L. M. Ni // Proceedings of the International Parallel Processing Symposium. - 1996. - P. 268-273.

114. Bae, M. M. Spare Processor Allocation for Fault Tolerance in Torus-Base Multicomputers [Text] / M. M. Bae and B. Bose // Proceedings of the International Symposium on FaultTolerant Computer. - 1996. - P. 282-291.

115. Balaji, P. MPI on Millions of Cores [Text] / Balaji P., Buntinas D., Goodell D., Gropp W., Hoefler T., Kumar S., Lusk E., Thakur R., Traff J. // Parallel Processing Letters. - 2011. - Vol. 21, Issue 1. - P. 45-60.

116. Chun, A.T.T. Realistic communication model for parallel computing on cluster [Text] / A. T. T. Chun, C. L. Wang // In: Proceedings of the International Workshop on Cluster Computing. - 1999. - P. 92-101

117. Chun, A.T.T. Performance Studies of High-Speed Communication on Commodity Cluster [Text] / A. T. T. Chun // PhD thesis, University of Hong Kong. - 2001.

118. Christara, C. An efficient transposition algorithm for distributed memory computers [Text] / C. Christara, X. Ding, K. Jackson // Proceedings of the High Performance Computing Systems and Applications. - 1999. - P. 349-368

119. Pjesivac-Grbovic, J. Performance analysis of MPI collective operations [Text] / J. Pjesivac-Grbovic, T. Angskun, G. Bosilca, G. E. Fagg, E. Gabriel, J. J. Dongarra // Proceedings of the Wokshop on Performance Modeling, Evaluation and Optimisation for Parallel and Distributed Systems (PMEO). - 2005.

120. Johnssonn, S.L. Optimum broadcasting and personalized communication in hypercubes [Text] / S. L. Johnssonn, C. T. Ho // IEEE Transactions on Computers. -1989. - Vol. 38, no. 9. - P. 1249-1268.

121. Adve, V. Analysing the Behavior and Performance of Parallel Programs [Text] / V. Adve // PhD thesis, University of Wisconsin, Computer Sciences Department. - 1993.

122. Bruck, J. Efficient algorithms for all-to-all communications in multiport message-passing systems [Text] / J. Bruck, C. T. Ho, S. Kipnis, E. Upfal, D. Weathersby // IEEE Transactions on Parallel and Distributed Systems. - 1997. - Vol. 8, no. 11. -P. 1143-1156.

123. Clement, M. Network performance modelling for PM clusters [Text] / M. Clement, M. Steed, P. Crandall // Proceedings of Supercomputing. - 1996.

124. Labarta, J. DiP: A parallel program development environment [Text] / J. Labarta, S. Girona, V. Pillet, T. Cortes, L. Gregoris // Proceedings of the 2nd Euro-Par Conference. - 1996. - Vol. 2. - P. 665-674.

125. König, J.C. Analysis of gossiping algorithms with restricted buffers [Text] / J. C. König, P. S. Rao, D. Trystram // Parallel Algorithms and Applications. - 1998. -Vol. 13, no. 2. - P. 117-133.

126. Jeannot, E. Two fast and efficient message scheduling algorithms for data redistribution through a backbone [Text] / E. Jeannot, F. Wagner // Proceedings of the IPDPS. - 2004.

127. Moritz, C.A. LoGPC: Modeling network contention in messagepassing programs [Text] / C. A. Moritz, M. I. Frank // IEEE Transactions on Parallel and Distributed Systems. - 2001. - Vol. 12, no. 4. - P. 404-415.

128. Calvin, C. All-to-all broadcast in torus with wormhole-like routing [Text] / C. Calvin, S. Perennes, D. Trystram // Proceedings of the IEEE Symposium on Parallel and Distributeed Processing. - 1995. - P. 130-137.

129. Kale, L. V. A framework for collective personalized communication [Text] / L. V. Kale, S. Kumar, K. Varadarajan // Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS'03). - 2003.

130. Yang, Y. Optimal all-to-all personalized exchange in multistage networks [Text] / Y. Yang, J. Wang // Proceedings of the International Conference on Parallel and Distributed Systems (ICPADS'00). - 2000. - P. 229-236.

131. Feitelson, D. G. Parallel Job Scheduling [Text] / D. G. Feitelson, L. Rudolph, U. Schwiegelshohn // A Status Report, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing. - 2004. - P. 1-9.

132. Хорошевский, В. Г. Масштабируемый инструментарий параллельного мультипрограммирования пространственно-распределенных вычислительных систем [Текст] / В. Г. Хорошевский, М. Г. Курносов, С. Н. Мамойленко, К. В. Павский, А. В. Ефимов, А. А. Пазников, Е. Н. Перышкова // Вестник СибГУТИ. - 2011. - № 4. - С. 3-18.

133. Ефимов, А. В. Организация функционирования распределенных вычислительных систем при обработке наборов масштабируемых задач [Текст] / А. В. Ефимов, С. Н. Мамойленко, Е. Н. Перышкова // Вестник ТГУ. Управление, вычислительная техника и информатика. - 2011. - № 2(15). - С. 51-60.

134. Свидетельство 2018619237 РФ. Программа моделирования алгоритмов коммуникационных обменов All-to-all на вычислительных кластерах: свидетельство о государственной регистрации программы для ЭВМ / Е.Н. Перышкова, М. Г. Курносов; заявитель и патентообладатель СибГУТИ; заявл. 21.06.2018, опубл. 02.08.2018. [Электронный ресурс]. - [Б. м. : б. и.]

135. Курносов, М.Г. Эвристический алгоритм формирования подсистем в вычислительных системах [Текст] / М. Г. Курносов // Материалы 9 Международной научно-практической конференции "Искусственный интеллект-2008. Интеллектуальные системы". - Изд-во: НИИ МВС ЮФУ. - 2008. - Ч. 2. -С. 346-351.

136. Ефимов, А. В. Модернизация системы управления ресурсами PBS/TORQUE и планировщика Maui для обслуживания масштабируемых задач [Текст] / А. В. Ефимов С. Н. Мамойленко, Е. Н. Перышкова // Вестник компьютерных и информационных технологий. - 2016. - № 2. - С. 34-39.

137. Перышкова, Е. Н. Инструментарий решения масштабируемых задач на распределённых вычислительных системах [Текст] / Е. Н. Перышкова, А. В. Ефимов С. Н. Мамойленко // Вестник СибГУТИ. - 2015. - №4. - С. 82-89.

138. Перышкова, Е.Н. Влияние размещения процессов параллельной программы по вычислительным узлам на эффективность операции All-to-all [Текст] / Е. Н. Перышкова, М. Г. Курносов // Материалы российской научно-технической конференции «Обработка информации и математическое моделирование». Новосибирск. - 2018. - С. 299-304.

139. Перышкова, Е.Н. Формирование подсистем элементарных машин в вычислительных системах с учетом конкурентного разделения каналов связи [Текст] / Е. Н. Перышкова, М. Г. Курносов // Материалы двенадцатой конференции с международным участием «Новые информационные технологии в исследовании сложных структур» / Издательский дом Томского государственного университета. Томск. - 2018. С. 8-9.

140. Перышкова, Е.Н. Анализ масштабируемости алгоритмов обслуживания потоков задач в системе управления ресурсами SLURM [Текст] / Е. Н. Перышкова // Материалы российской научно-технической конференции «Обработка информации и математическое моделирование». Новосибирск: СибГУТИ. - 2017. - С. 357-363. - ISBN: 978-5-31434-038-1.

141. Перышкова, Е.Н. Формирование подсистем элементарных машин в вычислительных кластерах на базе составных коммутаторов [Текст] /

Е. Н. Перышкова // Труды 13-й Международной школы-семинара «Проблемы оптимизации сложных систем» в рамках международной конференции IEEE SIBIRCON 2017, Новосибирск. - 2017.

142. Перышкова, Е.Н. Моделирование конкурентного разделения каналов связи при реализации параллельных программ на мультиархитектурных вычислительных системах [Текст] / Е. Н. Перышкова, М. Г. Курносов // Визуальная аналитика: сборник докладов Международной конференции. Кемерово. - 2017. -С. 62-65.

143. Перышкова Е.Н. Анализ влияния конкурентного использования коммуникационной среды вычислительных систем на динамические характеристики параллельных программ [Текст] / Е. Н. Перышкова // Интеллектуальный анализ сигналов, данных и знаний: методы и средства: сборник статей всероссийской научно-практической конференции с международным участием. Новосибирск. - 2017. - С. 206-210.

144. Мамойленко, С. Н. Исследование эффективности обработки масштабируемых задач на распределенных вычислительных системах [Электронный ресурс] / С. Н. Мамойленко, А. В. Ефимов, Е. Н. Перышкова // Национальный Суперкомпьютерный Форум: сборник тезисов докладов, Переславль-Залесский, ИПС им. А.К. Айламазяна РАН. - 2016. - URL :

http://2016.nscf.ru/nauchno-prakticheskaya-konferenciya/tezisy-dokladov.

145. Перышкова, Е. Н. Использование масштабируемых задач на распределенных вычислительных системах [Текст] / Е. Н. Перышкова, А. В. Ефимов С. Н. Мамойленко // Материалы Российской научно-технической конференции "Перспективные информационные и телекоммуникационные технологии". Новосибирск. - 2016. - С. 234-236.

146. Ефимов, А. В. Инструментарий решения масштабируемых задач на распределенных вычислительных системах [Текст] / А. В. Ефимов, Е. Н. Перышкова, С. Н. Мамойленко // Материалы Российской научно-технической

конференции "Перспективные информационные и телекоммуникационные технологии". Новосибирск. - 2016. - С. 165-169.

147. Перышкова, Е.Н. Модификация системы управления распределенными ресурсами Torque [Текст] / Е. Н. Перышкова, С. Н. Мамойленко // материалы Российской научно-технической конференции "Обработка информации и математическое моделирование". Новосибирск. - 2015. - С. 349-353.

148. Ефимов, А. В. Инструментарий решения масштабируемых задач на распределенных вычислительных системах [Текст] / А. В. Ефимов, Е. Н. Перышкова, С. Н. Мамойленко // Сборник трудов 8-й Сибирской конференция по параллельным и высокопроизводительным вычислениям. Томск : Изд-во Томского университета. - 2015. - С. 143-150

142

Приложения Приложение А

о государственной регистрации программы для ЭВМ

№ 2016618446

Модуль планировщика МАШ, организующий работу масштабируемых задач на распределенных вычислительных системах

Правообладатель: Федеральное государственное бюджетное учреждение науки Институт физики полупроводников им. A.B. Ржанова Сибирского отделения Российской академии наук (ИФП СО PAH) (RU)

Акторы: Перышкова Евгения Николаевна (&и), Ефимов Александр Владимирович (Ш), Мамойленко Сергей Николаевич (ЯЩ

Заявка № 2016615648

Дата поступления 01 ИЮНЯ 2016 Г.

Дата государственной регистрации

в Реестре программ для ЭВМ 29 ИЮЛЯ 2016 г.

.о х ®

Руководитель Федеральной службы по интеллектуальной собственности

Г.П. Ивлиев

АШ #1

шшшш

ш

СВИДЕТЕЛЬСТВО

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

образовательное учреждение высшего образования «Сибирский

Авторы: Перышкова Евгения Николаевна (Я11), Ефимов Александр

Заявка № 2016615995

Дата поступления 08 ИЮНЯ 2016 Г. Дата государственной регистрации

в Реестре программ для эвм 05 августа 2016 г.

¡^ЕЛСТУАЛь,

Руководитель Федеральной службы по интеллектуальной собственности

Г.П. Ивлиев

теешшежАш ФВДЮАЩШШ

жжжжжж

жжжжжж

СВИДЕТЕЛЬСТВО

о государственной регистрации программы для ЭВМ

№ 2016618768

Модуль системы управления ресурсами TORQUE,

Правообладатель: Федеральное государственное бюджетное

государственный университет телекоммуникаций и

информатики» (К II)

Владимирович (Я11), Мамойленко Сергей Николаевич (ки)

жжшжшшшшжжжмжжжжжжжжжжмжмжжжжж^

146

Приложение Б

СПРАВКА

об использовании результатов диссертационной работы Перышковой Евгении Николаевны «Средства управления ресурсами вычислительных систем в режиме обслуживания потока задач с нефиксированными параметрами», представленной на соискание ученой степени кандидата технических наук по специальности 05.13.15 - «Вычислительные машины, комплексы и компьютерные сети»

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

проект РФФИ 16-07-00992 «Алгоритмы и программное обеспечение самодиагностики распределенных вычислительных систем» (2016-2017 гг., руководитель проекта - к.т.н., доцент Молдованова О.В.);

проект РФФИ 12-07-31015 «Разработка алгоритмов и программного инструментария эффективной самодиагностики болыпемасштабных распределенных вычислительных систем» (2012-2013 гг., руководитель проекта - к.т.н., доцент Молдованова О.В.);

- методы формирования подсистем элементарных машин для решения задач с нефиксированными параметрами;

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

Руководитель проектов РФФИ

(СибГУТИ):

а именно:

№16-07-00992 и №12-03-31015 к.т.н., доцент

Проректор

по научной работе СибГУТИ

О.В. Молдованова

Е.Р. Трубехин

УТВЕРЖДАЮ

СиёГУТИ

-yJ В.Г. Беленький

_2018 г.

АКТ

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

степени кандидата технических наук по специальности 05.13.15 -«Вычислительные машины, комплексы и компьютерные сети», в учебный процесс федерального государственного бюджетного образовательного учреждения высшего образования «Сибирский государственный университет телекоммуникаций и информатики» (СибГУТИ)

Мы, нижеподписавшиеся, заместитель заведующего Кафедрой вычислительных систем к.т.н. доцент О.В. Молдованова, заместитель декана Факультета информатики и вычислительной техники доцент В.И. Агульник, составили настоящий акт о том, что результаты диссертационной работы E.H. Перышковой «Средства управления ресурсами вычислительных систем в режиме обслуживания потока задач с нефиксированными параметрами» используются в учебном процессе СибГУТИ, а именно: теоретические результаты по планированию решения задач с нефиксированными параметрами, а также методы формирования подсистем элементарных машин для решения задач с нефиксированными параметрами на вычислительных системах используются в курсе лекций по дисциплине «Высокопроизводительные вычислительные системы» (уровень бакалавриата), результаты по анализу методов планирования выполнения параллельных программ в системах управления ресурсами вычислительных систем в курсе «Анализ функционирования распределенных вычислительных систем» (уровень магистратуры).

Заместитель заведующего Кафедрой вычислительных систем к.т.н. доцент

Заместитель декана

Факультета информатики и вычислительной техники доцент