Содержание к диссертации
Введение
1. Проблемы анализа и синтеза вычислительных систем 10
1.1. Вычислительные сети как объект моделирования и синтеза 10
1.2. Теория систем массового обслуживания как инструмент анализа вычислительных систем 15
1.3. Задачи структурного синтеза распределённой вычислительной системы с несколькими центрами обработки данных 24
1.4. Цель и задачи исследования 33
2. Аналитическое моделирование и оптимизация состава распределённой вычислительной системы 35
2.1. Постановка оптимизационной задачи 35
2.2. Пути оптимизации состава распределённой вычислительной системы 40
2.2.1. Поиск значений вероятностей, доставляющих минимум целевой функции 40
2.2.2. Классификация возможных способов решения задачи (2.7) 41
2.3. Оптимизация состава системы с фиксированной структурой 44
2.4. Вычислительная система с многофазными задачами 48
2.4.1. Постановка задачи 48
2.4.2. Решение задачи с известными интенсивностями 50
2.5. Оптимизация состава вычислительной системы с многофазными задачами 54
2.5.1. Исследование одного из вариантов решения 54
2.5.2. Способ для отыскания решения 56
2.5.2.1. Доказательство монотонного убывания функции вероятности полной загрузки 57
2.5.2.2. Поиск области, в которой находится решение 60
2.5.2.3. Модификация алгоритма поиска решения с учётом ограничений 62
2.6. Выводы 67
3. Алгоритмизация структурного синтеза распределённой вычислительной системы с центральным сервером 69
3.1. Модификация алгоритмов 69
3.2. Структурный синтез многоточечных информационно-вычислительных систем с разноскоростными каналами связи 81
3.3. Выводы 93
4. Программный комплекс анализа и синтеза распределённой вычислительной системы с несколькими центрами обработки данных 95
4.1. Общая структура программного комплекса 95
4.2. Подсистема выбора оптимального состава сети 98
4.3. Подсистема оптимизации топологической структуры сети 104
4.4. Результаты работы программного средства 112
4.5. Выводы 114
Заключение 116
Список используемых источников 118
Приложение 128
- Теория систем массового обслуживания как инструмент анализа вычислительных систем
- Пути оптимизации состава распределённой вычислительной системы
- Структурный синтез многоточечных информационно-вычислительных систем с разноскоростными каналами связи
- Подсистема оптимизации топологической структуры сети
Введение к работе
Актуальность темы. В связи с широким распространением и развитием информационных технологий распределённой информации возникает необходимость в совершенствовании аппарата, предназначенного для моделирования и анализа функционирования распределённых вычислительных систем.
Одной из важных задач является планирование загрузки распределённых вычислительных систем, на вход которых поступает неоднородный поток задач с фиксированными маршрутами их решения различными узлами (или центрами обработки данных) системы.
Построение адекватной математической модели такой системы позволит выбрать её структуру, оптимизирующую загрузку отдельных узлов с использованием различных критериев, таких, например, как критерий равномерной загрузки системы, критерий её максимальной загрузки и ряд других.
Задачей, непосредственно связанной с выбором структуры распределённой вычислительной системы, является синтез оптимальной топологической структуры сети. Выбор критерия оптимальности существенно влияет на многие характеристики сети. Например, наличие резервных связей повышает надёжность сети и делает возможным балансирование загрузки отдельных каналов. Простота присоединения новых узлов, свойственная некоторым топологиям, делает сеть легко расширяемой. Экономические соображения часто приводят к выбору топологий, для которых характерна минимальная суммарная длина линий связи.
Актуальность темы диссертационного исследования связана с проблемой повышения эффективности распределённых вычислительных систем путём реализации аппарата аналитического моделирования для выбора оптимального состава и топологической структуры сети.
Диссертационная работа выполнена в соответствии с одним из научных направлений Воронежского государственного технического университета -«Вычислительные и информационно - телекоммуникационные системы для управления технологическими процессами».
Целью работы является разработка эффективных моделей, алгоритмов и программных средств автоматизированного анализа, обеспечивающих оптимальный выбор состава и структуры распределённой информационно-вычислительной системы с несколькими центрами обработки данных.
Исходя из данной цели, в работе определены следующие задачи:
построение математической модели распределённой вычислительной системы с несколькими центрами обработки данных;
постановка и численное решение задачи оптимального выбора состава системы с точки зрения её равномерной загрузки;
сравнительный анализ основных алгоритмов структурного синтеза и их модификация с целью повышения их эффективности;
разработка программного комплекса, осуществляющего выбор оптимального состава распределённой вычислительной системы с точки зрения её равномерной загрузки, и её топологической структуры.
Методы исследования основаны на теории систем массового обслуживания, теории вероятностей, численных методах, методах оптимизации, объектно-ориентированного программирования.
Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:
Математическая модель распределённой вычислительной системы, отличающаяся наличием нескольких центров обработки данных, учитывающая необходимость обработки множественного потока задач с фиксированными маршрутами их решения.
Оптимизационная модель выбора состава распределённой вычислительной системы и численный метод решения, обеспечивающие равномерную загрузку вычислительной системы.
Аналитическое условие минимума функции стоимости системы в задаче структурного синтеза, обеспечивающее ускорение процедуры перебора за счёт исключения заведомо неоптимальных вариантов топологических структур.
Модифицированные алгоритмы структурного синтеза, отличающиеся повышенной эффективностью за счёт изменения порядка присоединения подграфов к уже синтезированному графу сети.
Практическая ценность работы. Предложенный подход к созданию математической модели распределённой вычислительной системы может быть применён при построении моделей не только вычислительных систем, но и других многофазных систем обработки заявок, движущихся по различным маршрутам, в частности, конвейерных систем перестраиваемых многономенклатурных производств, транспортных потоков и медицинского обслуживания в многопрофильных лечебно - профилактических учреждениях.
Разработанный программный комплекс выбора состава и топологической структуры распределённой вычислительной системы может быть применен при анализе и синтезе аналогичных систем, особенностями которых является наличие различных фиксированных маршрутов и множество центров обработки данных.
Реализация и внедрение результатов работы. Результаты исследования по моделированию и оптимизации распределённых вычислительных систем с неоднородным входящим потоком заявок используются в учебном процессе Международного института компьютерных технологий при обучении студентов специальности 220100 «Вычислительные машины, комплексы, системы и сети». Они включены в курс лекций по дисциплинам «Вычислительные системы и сети телекоммуникаций», «Моделирование», а также в рекомендации по курсовому проектированию.
Апробация работы. Основные положения работы докладывались и обсуждались на первой международной электронной научно-технической конференции «Автоматизация и информатизация в машиностроении», Тула, 2000; Международной научно-практической конференции «Компьютерные технологии в науке, производстве, социальных и экономических процессах», Новочеркасск, 2000; III Международной электронной научной конференции «Новые технологии в образовании», Воронеж, 2000; IV Международной открытой научной конференции «Современные проблемы в технике и технологиях» Воронеж, 2001; Международной научно-практической конференции «Развивающиеся интеллектуальные системы автоматизированного проектирования и управления», Новочеркасск, 2001; VII Международной открытой научной конференции «Современные проблемы информатизации в технике и технологиях», Воронеж 2002; Всероссийской конференции «Интеллектуализация управления в социальных и экономических системах», Воронеж, 2002; а также на научных семинарах кафедры ABC ВГТУ.
Публикации. Основные результаты работы опубликованы в 15 печатных работах, 3 из которых написаны без соавторов. В работах, опубликованных в соавторстве, лично соискателем предложены: [48] - методика сравнительного анализа базовых алгоритмов структурного синтеза распределённых вычислительных систем; [46] - зависимость стоимости сети для базовых алгоритмов от количества узлов; [47] — теоретическая основа, показывающая соотношение между минимальной и максимальной длиной сети; [68] - [70] -формулировка и доказательство теоремы о необходимом условии минимума функции стоимости и её применение; [63], [67] - формулировка задачи оптимального выбора состава сети и её решение; [66] - решение задачи оптимизации потоков; [65], [64], [16] - математическое моделирование распределённых вычислительных систем, на вход которых поступает неоднородный поток задач с фиксированными маршрутами их решения различными узлами системы.
Структура и объём работы. Диссертация состоит из введения, четырёх глав, заключения, списка литературы из 109 наименований, 4 приложений. Основная часть работы изложена на 125 страницах машинописного текста, содержит 51 рисунок и 5 таблиц. Во введении показана актуальность проблемы, сформулированы цели и представлены основные научные результаты работы, приведено краткое содержание работы по главам. В первой главе проведён анализ общей проблематики вопросов моделирования распределённых информационно-вычислительных систем с несколькими центрами обработки данных. Рассмотрены некоторые системы массового обслуживания, с помощью которых в дальнейшем будет описываться распределённая информационно-вычислительная система, и определены основные характеристики, которые понадобятся для анализа такой системы.
В данной главе также приведена постановка задачи структурного синтеза распределённых информационно-вычислительных систем с центральным сервером. Рассмотрены и проанализированы базовые алгоритмы структурного синтеза: Исау-Вильямса, Краскала, Фогеля, Прима и Шарма. В результате данного анализа сделаны выводы о работе каждого из вышеперечисленных алгоритмов, а также о причинах, по которым алгоритмы в тех или иных случаях работают не оптимально, и о возможных способах их модификации. Вторая глава посвящена исследованию распределённой вычислительной системы с несколькими центрами обработки данных с целью дальнейшей оптимизации её состава. В первой части главы рассматривается оптимизационная задача. Далее приводится способ для отыскания оптимального состава распределённой вычислительной системы, при ограничениях затрат на ресурсы, выделяемые для функционирования системы. Третья глава посвящена выбору топологической структуры информационно-вычислительной сети с центральным сервером. В данной главе произведён сравнительный анализ базовых алгоритмов структурного синтеза, в результате которого выявлены недостатки некоторых алгоритмов. Исходя из этого, эти алгоритмы были модифицированы с целью снижения стоимости сети. В четвёртой части представлена реализация программного комплекса анализа и синтеза распределённой вычислительной сети с несколькими центрами обработки данных. Результатом работы данной главы является построение системы выбора оптимального состава и структуры сети.
В заключении формулируются научные и практические результаты диссертационного исследования.
Приложения содержат листинги программ, а также документы, подтверждающие внедрение результатов диссертационного исследования.
Теория систем массового обслуживания как инструмент анализа вычислительных систем
Системой массового обслуживания называется любая система, предназначенная для обслуживания какого-либо потока заявок [8,17,23, 25,26,38]. Системы массового обслуживания включают в себя: Входной поток требований или заявок. Приборы (или каналы) обслуживания. Очередь требований, ожидающих обслуживания. Выходной поток обслуженных заявок (или заявок, получивших отказ в обслуживании). Системы массового обслуживания можно классифицировать по следующим признакам [38]: 1. По потокам заявок. Поток заявок носит случайный характер и может иметь различные законы распределения [43,44]. Наиболее простой поток - пуассоновский. Под пуассоновским потоком понимается случайный процесс (t), представляющий из себя число событий из простейшего потока событий, наступивших в интервале (0,t). 2. По времени обслуживания заявки Время обслуживания - случайная величина, которая может иметь различные законы распределения (чаще всего показательный). Показательный закон распределения — это закон распределения с полностью f(t) = Ле .
При таком законе распределения если в какой-то момент времени t0 происходит обслуживание заявки, то закон распределения оставшегося времени не зависит от того, сколько времени обслуживание уже продолжалось [18,40]. 3. По числу каналов обслуживания Все системы массового обслуживания делятся на одноканальные и многоканальные [38,79]. Одноканальная система массового обслуживания имеет следующий вид (рис. 1.8) Здесь состояние 0 означает, что система свободна, а 1 - система занята. Многоканальная система массового обслуживания, в отличие от одноканальной, имеет несколько каналов обслуживания (рис. 1.9). 4. По наличию или отсутствию очереди. Согласно этому признаку, все системы массового обслуживания делятся на системы с отказами (когда заявка, пришедшая в момент, когда все каналы обслуживания заняты, покидает системы не обслуженной) и системы с ожиданием [39,94]. В этих системах заявка, пришедшая в момент, когда все каналы заняты, не покидает систему, а становится в очередь и ждёт, пока не освободится какой-нибудь канал. Время ожидания и число мест в очереди могут быть как неограниченными, так и ограниченными.
Одноканальная и многоканальная системы массового обслуживания без очереди представлены на рис. 1.8 и рис. 1.9. Многоканальная система массового обслуживания с очередью показана на рис. 1.10. 5. По дисциплине (порядку) ожидания и обслуживания заявок. Она задаёт порядок выбора требований из очереди для обслуживания. Примерами стационарных дисциплин обслуживания являются обслуживание в порядке поступления (Fifo - первым пришёл, первым ушёл), обслуживание в обратном порядке (lifo - последним пришёл, первым ушёл) и случайный выбор требования для обслуживания. Если поступающие требования различаются по группам, и устанавливается некоторый приоритет обслуживания групп, то говорят о приоритетной дисциплине обслуживания. 6. Системы массового обслуживания могут также делиться на замкнутые и разомкнутые [38]. В замкнутых СМО источник заявок находится в самой СМО, и поток заявок зависит от состояния системы. Если поступает заявка от технического устройства, то объект начинает обслуживаться и в данный момент времени не подаёт новой заявки. Таким образом, интенсивность поступления заявок зависит от количества устройств, которые в данный момент времени не обслуживаются или не ожидают обслуживания.
Пути оптимизации состава распределённой вычислительной системы
Прежде чем рассматривать всевозможные способы решения задачи (2.7), проанализируем целевую функцию (2.5). По определению, дисперсия является неотрицательной. Тогда, если найдутся точки из области определения, при которых дисперсия обращается в ноль, можно будет сказать, что они доставляют минимум целевой функции в заданной области (т.е. решение будет найдено). Выясним, при каких значениях вероятности дисперсия обращается в ноль. Из формулы (2.5) имеем
В исходных терминах это утверждение будет переформулировано следующим образом.
Распределённая вычислительная система с N центрами обработки данных будет загружена равномерно, если вероятности полной загрузки каждого центра обработки данных будут совпадать между собой (т.е. будет выполняться условие (2.8)).
Условие (2.8) является достаточным для достижения функцией (2.5) своего минимального значения (т.е. нуля). Но это не означает, что у задачи (2.7) не может быть других решений, отличных от вида (2.8). Рассмотрим возможные способы решения этой задачи [3, 63].
В силу того, что Si может быть только целым числом (т.к. это количество вычислительных компонент і-го центра обработки данных), то описанная выше задача является задачей целочисленного программирования. Поэтому первый из вариантов решения данной задачи является решение её одним из методов целочисленного программирования[ 10,15,92,96]. Недостатком данного варианта решения задачи (2.7) является то, что все эти методы так или иначе сводятся к перебору [78], что в случае больших N существенно замедляет поиск решения. Более того, при достаточно сильном разбросе значений Sj количество переборов также значительно возрастёт. Поэтому необходимо искать какие-либо другие пути решения данной задачи.
Другим вариантом решения данной задачи является её решение с помощью методов множителей Лагранжа. Этот метод заключается в следующем [15,56]. Пусть имеется следующая задача на условный экстремум:
Выписывается функция Лагранжа вида и решение (и ,у ) ищется из следующей системы уравнений
Для того, чтобы рассматривать эту задачу как задачу на условный экстремум, необходимо дифференцировать целевую функцию[93]. В частности, необходимо дифференцировать Sj! и Х п0 переменной Sj, что сделать непосредственно нельзя. Более того, целевая функция имеет достаточно сложный вид, и задача получается с ограничениями типа неравенств, поэтому решать её с помощью данного метода будет не совсем рационально. Для нахождения минимума функции воспользуемся стандартным методом. Согласно второй теореме Вейерштрасса [93], всякая непрерывная в ограниченной области функция достигает в данной области своего наибольшего и наименьшего значения. Как известно, своего минимального (или максимального) значения функция может достигать в точках экстремума или на границе области. Тогда минимум функции можно найти следующим образом [42,93].1. Найти точки экстремума целевой функции. 2. Найти граничные точки области, на которой целевая функция определена. 3. Сравнить значение целевой функции в точках экстремума и граничных точках и выбрать минимальное.
Но для использования данного метода необходимо, чтобы целевая функция была 1. Определена для всех значений аргументов в области определения. 2. Непрерывна в области определения.
В данной же задаче функция определена лишь для целых значений аргументов, поэтому использование классического метода поиска минимума в данном случае невозможно. Более того, целевая функция определяется такими выражениями, которые могут быть определены лишь для целых чисел (например, Sj! или суммирование от 1 до S;). Тогда возникает следующая задача аппроксимации. Необходимо заменить исходную целевую функцию такой, чтобы она была определена для всех действительных чисел, непрерывна в области определения целевой функции и как можно меньше отличалась от исходной функции. Тогда можно решить задачу для аппроксимирующей функции, а потом приближённо найти значения исходной функции, которые доставляли бы минимум задаче (2.8).
В некоторых случаях у администратора вычислительной системы есть возможность управления интенсивностями поступающих потоков задач (например, в случае административного управления). В этом случае можно найти Х\ опт (т.е. интенсивности, при которых загрузка будет равномерной) и стремиться к ним. Для этого решим задачу (2.7) при фиксированных интенсивностях обслуживания и количеству вычислительных компонент для каждого центра обработки данных. Требуется найти такую интенсивность входного потока задач, чтобы загруженность системы была равномерной. Для этого найдём сначала дисперсию
Структурный синтез многоточечных информационно-вычислительных систем с разноскоростными каналами связи
До сих пор решалась задача построения сети минимальной стоимости при фиксированной цене единицы канала связи. В этом случае стоимость сети зависит только от её длины. Но в жизни мы имеем дело с каналами связи с различными пропускными способностями, при этом стоимость канала связи прямо пропорционально зависит от пропускной способности. В силу этого стоимость сети теперь будет определяться не только её протяжённостью, но и пропускной способностью каналов, составляющих эту сеть.
Далее рассматривается расширенная постановка задачи синтеза, ориентирующаяся на наличие набора каналов связи с различными пропускными способностями [68,69,70]. Модель позволяет варьировать большим числом параметров и более близка к реально проектируемым системам.
Постановка задачи. Пусть даны координаты узлов, которые необходимо соединить в сеть. Пусть также дана функция стоимости S(h) единицы канала пропускной способности h. Необходимо построить сеть минимальной стоимости, удовлетворяющую ограничениям по пропускной способности. Если известна длина сети L, то стоимость сети Sd(h) будет определяться следующим образом: Sd(h)=LhS(h).
Если зависимость L от h является кусочно-постоянной функцией с разрывами в точках ho, hi, Ьг, ..., hn (а в данной задаче рассматривается именно такой случай), стоимость сети будет определяться следующим образом Sd(h)=L(h)S(h) [47].
При h h0 L не определена. При h=h0 получим первое значение функции L. Значение функции может измениться, как только пропускная способность рёбер увеличится на величину минимального трафика, генерируемой каким-либо узлом. Далее изменение произойдёт при увеличении пропускной способности до величины, равной значению второго по малости объёма, генерируемого каким-либо узлом и т.д.
Функция стоимости единицы линии связи с пропускной способностью d -S(d) - будет монотонно неубывающей функцией. S(d) также является кусочно-постоянной функцией (имеются линии связи с конкретными пропускными способностями, которых, вообще говоря, конечное множество). В зависимости от трафика выбирается линия связи с той или иной пропускной способностью. Пусть функция стоимости единицы канала S(h) от пропускной способности h имеет вид: где 5j 0 для всех і: 0 i n-l. Предположим также, что функция зависимости длины сети от пропускной способности L(h) имеет следующий вид: (3.2) где (3i 0 для всех і: 0 i n-l. Без ограничения общности можно предположить, что точки разрыва и у L и у S одни и те же, так как в противном случае в качестве точек разрыва можно взять объединение точек разрыва у этих функций. п Предположим, что Ь0 нам известно (Ь0 Хс о ) Из (- -2) следует, что к=\ 1. В силу того, что функция стоимости является монотонно возрастающей, рассматривать Sd(h) при h hn не имеет смысла, т.к. стоимость сети возрастает, а длина уже не уменьшается. 2. В силу того, что функция стоимости является монотонно возрастающей и того, что функции стоимости и длины являются кусочно-постоянными функциями, функция Sd будет достигать минимума в одной из точек ho, hi, ..., hn-i. Т.е. задача поиска минимума функции Sd сводится к выбору минимального из значений афй,ахЬх,...,апЬп. Задача поиска минимума функции Sd является задачей перебора. Сложность данной задачи растёт с увеличением количества узлов. Итак, будем искать минимум функции Sd(h). Аналогично (3.4), можно получить
Подсистема оптимизации топологической структуры сети
На данном этапе у администратора сети есть возможность выбора положения узлов сети. На вход системы поступают полученные на предыдущем этапе необходимые объёмы (мощности) компонент вычислительной системы (т.е. информационные объёмы, генерируемые каждым узлом сети). Задавая произвольные географические координаты каждому из узлов сети, и изменяя их, администратор получает возможность сравнить стоимость сети в каждом случае и выбрать сеть оптимальной стоимости. Сеть можно синтезировать с помощью одного из перечисленных в предыдущей главе алгоритмов (Прима, Исау-Вильямса, Краскала, Фогеля, Шарма, а также модифицированного алгоритма Краскала и модифицированного алгоритма Шарма).
Таким образом, подсистема выбора топологической структуры сети будет состоять из нескольких модулей: основной модуль, обрабатывающий исходные данные, запрашивающий алгоритм, согласно которому будет синтезироваться сеть и представляющий графически и численно результаты работы программы; модули, реализующие каждый из алгоритмов структурного синтеза: Прима, Исау-Вильямса, Краскала, Модифицированного алгоритма Краскала и Фогеля. Как уже отмечалось выше, алгоритм Шарма несколько отличается по структуре от остальных алгоритмов, поэтому он реализован непосредственно в основном модуле; вспомогательный модуль, который содержит описание структуры данных и основные процедуры и функции для работы каждого из вышеперечисленных алгоритмов: поиск ближайшего подграфа к заданному, проверка подграфа на пустоту, определение расстояние между двумя подграфами, соединение двух подграфов в один и др.
Подпрограмма, реализующая основной алгоритм структурного синтеза находится в основном модуле, и при выборе одного из алгоритмов для соединения двух подграфов в один обращается к модулю, содержащему этот алгоритм. Графически данную подсистему можно изобразить следующим образом (рис.4.6). Здесь модули, содержащие алгоритмы Прима, Исау-Вильямса, Краскала, Фогеля и модифицированный алгоритм Краскала состоят лишь из одной процедуры, результатом которой (в каждом модуле) являются два числа: номера подграфов, которые необходимо соединять на данном шаге.
Т.к. при решении задачи с использованием алгоритма Шарма на каждом шаге ищется подграф, который необходимо соединить с сервером, а не два узла, соединяемые в подграф, метод Шарма описан непосредственно в основном модуле, а поиск топологической структуры сети по этому алгоритму осуществляется отдельно от остальных алгоритмов структурного синтеза. Каждый из перечисленных выше модулей при своей работе обращается к модулю dat, в котором содержатся следующие подпрограммы: - Функция проверки подграфа на пустоту function empty(ind:integer):boo!ean.
Выдаёт результат «истина» (true) если подграф ind является пустым и «ложь» false в противном случае; Процедура определения состава подграфаprocedure int(ind:integer; var mc:mass).
В качестве первого параметра поступает номер подграфа, в качестве результата массив, состоящий из номеров узлов, входящих в подграф ind. Процедура определения расстояния между двумя подграфами procedure rasst(indl,ind2:integer; var min:doubie; var minindl,minind2:integer).
В качестве параметров поступают номера подграфов, в качестве результата -расстояние min между этими подграфами и номера узлов minindl и minind2, на которых это расстояние достигается.
Процедура определения ближайшего к подграфу indl подграфа procedure minrasst(indl:integer;prop:boolean;var ind2:inleger; var minrdouble; var minindl,minind2:integer).
