СПОСОБ РАСПРЕДЕЛЕННОЙ ОБРАБОТКИ НЕСТАЦИОНАРНОГО ПОТОКА ЗАПРОСОВ В ГЕТЕРОГЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЕ Российский патент 2010 года по МПК G06F15/16 

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

Известны способы распределения запросов пользователей в вычислительных системах (см., например, патент Японии №2-30534, кл. G06F 15/16; а.с. СССР №1624473, кл. G06F 15/20, 1991; а.с. СССР №1730626 А1, кл. G06F 9/46, 1992), суть которых заключается в распределении заданий процессорами в многопроцессорной вычислительной системе при вертикальном распараллеливании программ. При освобождении любого процессора очередное задание распределяется сразу еще до окончания текущего задания.

Перечисленные аналоги имеют следующие недостатки:

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

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

- отсутствие возможности адаптации алгоритмов управления к динамически изменяющимся характеристикам пропускной способности системы передачи данных;

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

Наиболее близким по технической сущности к заявленному способу распределения запросов пользователей в вычислительной системе является способ, предложенный в патенте РФ №2121709, кл. G06F 15/16, 1996.

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

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

Указанный способ-прототип имеет недостатки:

- низкая эффективность планирования вычислений при наличии у запросов функций важности его обработки;

- неприменимость способа при динамически изменяемых характеристиках потока запросов;

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

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

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

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

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

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

Проведенный анализ уровня техники позволил установить, что аналоги, характеризующиеся совокупностью признаков, тождественны всем признакам заявленного технического решения, отсутствуют, что указывает на соответствие заявленного устройства условию патентоспособности «новизна». Результаты поиска известных решений в данной и смежных областях техники с целью выявления признаков, совпадающих с отличительными от прототипа признаками заявленного объекта, показали, что они не следуют явным образом из уровня техники. Из уровня техники также не выявлена известность влияния предусматриваемых существенными признаками заявленного изобретения преобразований на достижение указанного технического результата. Следовательно, заявленное изобретение соответствует условию патентоспособности «изобретательский уровень».

Заявленное техническое решение поясняется чертежами, на которых представлено:

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

фиг.2 - схема организации обработки запросов пользователей в распределенной вычислительной системе;

фиг.3 - схема ресурсных требований запроса, определяемая «блоком прогнозирования требований»;

фиг.4 - алгоритм кластерного анализа и определения классов запросов;

фиг.5 - алгоритм определения ресурсоемкости запроса пользователя;

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

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

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

В наибольшей степени специфику ГРВС как объекта управления, функционирующего на основе объединения вычислительных узлов, определяют следующие факторы:

- невозможность централизованного получения информации о состоянии коллективно используемых ресурсов системы;

- наличие вычислительных узлов различной производительности и архитектуры;

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

- значительная вариабельность параметров потока запросов в зависимости от внешних условий: времени суток, планов, сторонних факторов;

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

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

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

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

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

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

Процесс обслуживания начинается, когда пользователь формирует запрос на обслуживание. Запрос на обслуживание формируют в блоке «источник запросов». Через «блок связи» запросы передают на «блок приема запросов пользователей». С «блока приема запросов пользователей» запрос передают на «блок классификации запросов». В «блоке классификации запросов» накапливают информацию о свойствах множества запросов, получают информацию о результатах обработки запросов из «блока сопровождения очереди класса узлов», анализируют полученную информацию, при изменении свойств потока запросов адаптируют алгоритм прогнозирования ресурсных требований запроса. В «блоке классификации запросов» множество запросов разбивают на несколько классов, соответствующих классам вычислительных узлов, определяют условия принадлежности запроса каждому классу и вычисляют функцию прогнозирования ресурсных требований для запросов из каждого класса согласно алгоритма на фиг.4. Условия принадлежности запроса определенному классу передают из «блока классификации запросов» в «блок определения класса запроса», а функцию прогнозирования ресурсных требований запроса - в «блок прогнозирования требований». Алгоритм прогнозирования ресурсных требований запроса представлен на фиг.5.

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

При освобождении вычислительного узла согласно результатам сетеметрии опрашивают все «блоки сопровождения очереди класса узлов» на предмет наличия запроса на обслуживание и его эффективности, в «блоке выбора первоочередного запроса» выбирают первоочередной запрос пользователя, обслуживание которого приведет к максимальному повышению эффективности. Запрос пользователя, принятый на обслуживание, исключается из очереди.

При переполнении очереди запросов в «блоке сопровождения очереди класса узлов» выявляют оптимальную схему переадресации запросов между «блоками сопровождения очереди класса узлов». Корректировку схемы переадресовки запросов пользователей для всех очередей запросов в «блоках сопровождения очереди класса узлов» выполняют с помощью размещенных на них самообучающихся вероятностных автоматов с переменной структурой.

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

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

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

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