автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.06, диссертация на тему:Модельно-алгоритмическое обеспечение конвейерного выполнения задач в распределенных АСУ

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

003454442

Богданова Ольга Витальевна

МО ДЕЛЬНО-АЛГОРИТМИЧЕСКОЕ ОБЕСПЕЧЕНИЕ КОНВЕЙЕРНОГО ВЫПОЛНЕНИЯ ЗАДАЧ В РАСПРЕДЕЛЕННЫХ АСУ

05 13.06 - Автоматизация и управление технологическими процессами и производствами (промышленность)

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Красноярск - 2008

003454442

Работа выполнена в Сибирском государственном аэрокосмическом университете имени академика М.Ф. Решетнева, г. Красноярск

Научный руководитель:

доктор технических наук, профессор Ковалев Игорь Владимирович

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

доктор технических наук, профессор Терсков Виталий Анатольевич

кандидат технических наук, доцент Зеленков Павел Викторович

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

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

Защита состоится «19» декабря 2008 года в 14 часов на заседании диссертационного совета Д 212.249.02 при Сибирском государственном аэрокосмическом университете имени академика М.Ф. Решетнева по адресу: 660014, г. Красноярск, пр. им. газ. «Красноярский рабочий», 31

С диссертацией можно ознакомиться в библиотеке Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева

Автореферат разослан «13» ноября 2008 года

Ученый секретарь диссертационного совета

Е.П. Моргунов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Очевидно, что при организации однотипных последовательностей задач в конвейерный план повышается эффективность работы распределенных АСУ.

Теоретические и методологические аспекты типизации задач в модульных системах обработки данных (СОД) отражены в работах отечественных и зарубежных авторов, таких как А.Г. Мамиконов, В.В. Кульба, С.А Косяченко, A.C. Миронов, E.H. Сидоров, A.A. Ашимов, Ю Ю Кесс, В.М. Ревако, A.B. Товмасян, Б. Дюран, П Оделл, X. Берж, О. Ope. Модели и методы обработки информации в технических и организационно - технологических системах рассмотрены в работах В.В. Воеводина, Б.А. Головкина, К.Г. Самофалова, Г.М. Луцкого, А.Б. Барских, E.JI. Шлимовича, А.П. Шабанова, Д. Филлипса, А. Гарсиа-Диаса, Р.В. Конвея, В.Л. Максвелла, Л.В. Миллера.

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

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

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

Поставленная цель достигается путем решения следующих задач: • анализа принципов обработки данных в автоматизированных системах управления;

• адаптации методики типизации задач для АСУ с конвейерной организацией обработки данных;

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

• оценки достаточной мощности СОД для распределенной АСУ с конвейерным типом выполнения задач;

• реализации системы модельно-алгоритмической поддержки методов конвейерной организации выполнения задач в распределенных АСУ;

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

Методы исследования. При выполнении работы использовались математическое и вероятностное моделирование параметров систем обработки данных конвейерного типа, элементы теории вероятностей, объектно-ориентированный анализ, количественные и оперативные методы управления проектами, сетевые диаграммы и диаграммы Ганта, теория систем массового обслуживания.

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

■ адаптацию методики типизации задач для СОД конвейерного типа в распределенных АСУ;

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

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

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

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

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

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

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

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

Реализация результатов работы. Диссертационная работа выполнялась в рамках тематического плана Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева (20052008гг.). Программные разработки по данной теме прошли экспертизу и зарегистрированы в Отраслевом фонде алгоритмов и программ (№ государственной регистрации 02067910.00014-01, 02067910.00016-01, 03524577.01902-01), что делает их доступными широкому кругу специалистов по автоматизации и управлению технологическими процессами и производствами.

Апробация работы. Основные положения и результаты работы прошли апробацию на всероссийских конференциях, научных семинарах и научно-практических конференциях. В том числе, на XII Всероссийской научно-практической конференции «Перспективные материалы, технологии, конструкции, экономика», Государственный университет цветных металлов и золота (Красноярск, июнь 2006г.), XI Международной научной конференции «Решетневские чтения», Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева (Красноярск, ноябрь 2007г.), I Всероссийской научно-практической конференции «Перспективы развития информационных технологий», Центр развития научного сотрудничества (Новосибирск, апрель 2008г.), Межрегиональной научно-технической конференции «Совершенствование методов поиска и разведки, технологии добычи и переработки полезных ископаемых», Сибирский федеральный университет (Красноярск, апрель 2008г.). Диссертационная работа в целом обсуждалась

на научных семинарах Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева (2006-2008 гг.).

Публикации. По теме диссертации опубликовано 17 печатных работ (в том числе, три работы в изданиях по перечню ВАК РФ), го них 5 без соавторов. Полный список публикаций представлен в конце автореферата.

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Методология проектирования систем обработки данных является естественным развитием методологии создания автоматизированных систем управления.

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

Так как отдельный модуль есть некий подграф графовой модели СОД О выбранного уровня абстракции (а этому уровню, естественно, соответствует некоторый граф СОД б°), то можно определить типовую задачу СОД как подграф графа принадлежащий графам нескольких задач СОД При этом основным параметром типового модуля является вес вершин и дуг, определяющий степень его типовости. Дадим формальное определение типового модуля. Пусть __1Г = \и" ,1 = 1,1} - множество процедур управления и обработки данных задачи АСУ г„;

Оп - р", у = 1, У | - множество информационных элементов задачи гп\

N _

и = ,п = 1,Ы - множество вершин интегрированного графа

п -1

N _

О- = 1 ,Ы - множество дуг интегрированного графа Сопределим

«=1

N

структуру системы как совокупность задач: 2 = \}гп,2\и х-И], причем

: л» 1

е 2е,, где 2е - множество технологически близких задач.

Типовым модулем называется модуль, для которого значение р> 2 (где р - требуемый уровень абстракции описания задач), чем выше значение параметра р, тем для решения большего числа задач АСУ он используется.

Максимальное значение параметра р = N, где N — мощность множества проектируемых задач, принадлежащих множеству 2? , п = \,И. Состав множества задач, проектируемых при разработке СОД, зависит от мощности множества 2е, которая определяется мерой близости входящих в множество 2 задач Чем более мощным является 2?, тем большее число модулей, обладающих высоким уровнем типовости, может быть синтезировано и принято в качестве базовых для АСУ с конвейерным типом обработки данных. Следует отметить, что мощность множества 2? определяет не только уровень типовости используемых задач, но и их собственную мощность. Базовая задача может не обладать высоким уровнем типовости, но обладать большой мощностью, и наоборот.

Таким образом, введенное понятие типовой задачи СОД конвейерного типа непосредственно отвечает задачам проектирования распределенной АСУ. Реализация именно этой концепции даст существенный эффект на практике.

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

При рассмотрении видов классификации основным является вопрос: должен ли граф задачи, обрабатываться одним процессором или СОД в рамках АСУ, содержащей более одного процессора? Решение разграничить планы обработки данных именно таким образом не является

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

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

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

Разработанное модельно-алгоритмическое обеспечение позволяет реализовать алгоритм Джонсона (ГО) для формирования двухмашинных конвейерных планов обработки данных. Предложена процедура сравнительного анализа конвейерных планов с начальной очередностью, с минимальным временем потока, БРТ-план. Ниже представлен сформированный план с минимальным временем потока (рисунок 1).

Рисунок 1 - Двухмашинный конвейерный план с минимальным временем

потока

Следует отметить, что алгоритм Джонсона упорядочивает задачи, одновременно доступные на двухмашинном конвейерном плане, таким образом, чтобы минимизировать максимальное время потока. По алгоритму Джонсона задача Г,- предшествует 7}, если Ai + В1 > А, + В, и

А: < Aj, где Ai и В, представляют требования 7} для процессора класса А и

класса В соответственно.

Предложена модификация алгоритма Джонсона (MJO), позволяющая формировать многомашинные конвейерные планы.

Процедуры предыдущего алгоритма обобщены для ситуации, когда более чем один процессор может существовать в каждом из двух классов -классе А и классе В. Для модифицированного алгоритма Джонсона (М.Ю) в конвейерной среде с т процессорами класса А и п процессорами класса В, задача Tt предшествует 7}, в соответствии с (MJO), если min{A,/m,Bj «)< min[Aj jm,Bl /п).

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

Предложена процедура сравнительного анализа трехмашинных конвейерных планов: FSIIS-план с бесконечной промежуточной памятью, FSNIS-план без промежуточной памяти, FSFIS-план, с ограниченной промежуточной памятью Ниже представлен сформированный FSNIS-план без промежуточной памяти (рисунок 2).

(Нмм Дммшть Нмк .taHtvMM ГГх¥Ггё~Т;ТБ¥~С<Де1Т':г'Да|Зе' :18ДаТ6

•¡__JE______ ___________у*""1! ВшШШПЮЭйЕшШшЕ. П'Т с 7п16"' еТч; с ;"п 'с; г' в; в; ч 1 с; п ■ с; п. в

1 вд ЗиИмшдамаш» *

;»*| Щ iцчей:Г1н 15.D1 .С?Вт 16.01.0? *

3 щ 33|№Нт23.1ШСрЩ11.0П "к

4 Щ 15днетЧт23.1ЦК Cs0e.12.06/! S

5 ТЗД 5 (Ией-Ср 1 ¿01 ¿7 'Вт 1 В.01 Я7 6 ¡5 5 ТЭД 4»(нЛй17.в1ЙДГЗ !в

ГЗВ 4 дней:Чт 0712.03 Бт 12.12-05 4 С » Щ 3 дией Ср 17.01 Л7 Пт 1ЭЛ1.В7 5 С :! 1ЭД 5|№СВ10МВТ1ИШВ с"

Рисунок 2 - Трехмашинный конвейерный FSNIS - план без промежуточной

памяти

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

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

В основе метода лежит математический аппарат теории массового обслуживания с ожиданием (с очередью). Задача разработки модели, позволяющей получить оценку мощности СОД с накоплением информации, является в настоящее время актуальной. Данная задача относится к проблеме минимизации ресурсов АСУ.

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

где Тзад - заданное

максимально-допустимое значение времени ожидания требованием обслуживания, Р(< ТшА) - заданное минимально-допустимое значение вероятности непревышения Тзад, <2 " максимальное количество требований, обслуживаемых в непрерывном интервале времени (интервале занятости), К (г) - объём записанной информации. Значение К(г) изменяется со временем, " длительность одного интервала

обслуживания. Является зависимой от объёма информации величиной

и определяется как )1 = Гсот"--+ Т; м - количество процессоров

М

в СОД, тсош1 - постоянная составляющая интервала обслуживания, определяемая в основном временем, затрачиваемым непосредственно на выполнение работ по обслуживанию требования, [^(г)] - составляющая интервала обслуживания, которая зависит от объёма информации. Параметр гуаг[У(?)] определяется временем, затрачиваемым на выполнение действий с информацией и принятие решений, к - порядковое место требования в интервале занятости, ] - время ожидания для ¿-го требования, выраженное в количестве интервалов обслуживания, Р^Х0) ~ вероятность того, что требование, поступившее в СОД, не ожидает обслуживания. В одном интервале занятости таким требованием может быть только первое требование (к=7), при этом Р^,(о) для любого значения Q является постоянной, равной 1, Рск0°^(1) - вероятность того, что длительность ожидания обслуживания второго, по порядку обслуживания в системе, требования (к=2), равна одному интервалу обслуживания. В одном интервале занятости Р^ (¡) для любого значения О, является постоянной, равной 1. В работе определяется также -Р^ИОвО' - вероятностей того, что любое требование, начиная с третьего, по порядку обслуживания в интервале занятости, ожидало не более у интервалов обслуживания, ]-1,2, ...Д 3 - максимально-допустимое время ожидания, выраженное в

количестве интервалов обслуживания. Параметр 3 соответствует параметру Тзад и является зависимым от параметра

Модель позволяет получить зависимость между максимальным количеством требований, обслуживаемых в СОД в непрерывном интервале времени (интервале занятости), и объёмом Ур) записанной информации при условии соблюдения заданных значений времени Т ожидания требованиями обслуживания и вероятности Р(< Тзад) его не превышения. Рассмотренная модель позволяет определить зависимость между мощностью СОД и объёмом информации, постепенно накапливаемой и осваиваемой процессорами конвейерного плана обработки данных. Важным применением модели является выбор стратегии для организации процесса обслуживания требований с возможностью количественной оценки различных вариантов при распределении основных задач между процессорами.

Зависимость объёма информации от времени I определяется в

основном исходя из состава предметных сущностей в среде обеспечения

деятельности потребителей задач и условий функционирования СОД,

предоставляющей такие задачи. Например, на рисунке 3 показана

зависимость объёма записанной информации от времени ей обновления. Г 1

Объем информации, у.и.е.

1200

г

200 .--.........--------

О 5 10 15 20

Вред га обновлен ни н пформпцш!

_ Рисунок 3 - Пример зависимости У(Х)

Длительность интервала обслуживания

МПН

Врсмя о6IIЧвленни информации

Рисунок 4 - Пример зависимости ттт [у{()]

Зависимость переменной составляющей гуаг|У(?)] интервала обслуживания определяется в основном исходя из класса процессоров СОД, организации обслуживания требований, поступающих от потребителей задач. Например, на рисунке 4 показано изменение переменной гуаг[г(?)] в зависимости от времени обновления информации.

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

В работе исследовалась система обработки данных, обслуживающая 20 задач. В среднем на одну задачу приходится 60 [у.и.е] информации, поэтому общий объём V =1200 [у.и.е.]. Обслуживание требований осуществляется М=10 процессорами. В СОД реализована стратегия организации процесса обработки информации, при которой каждый процессор выполняет следующие функции «Классификация требования», «Формулирование проблемы», «Определение задач» и «Сопровождение задач». Функционирование системы обработки данных предполагает с началом её эксплуатации запись информации из расчёта одной порции объёмом <5у=60 [у.и.е] через каждые ¿1 =10 дней (и = 1200/60=20). Задачи предоставляются на следующих условиях: максимально допустимое время ожидания требованием обслуживания ГЗОЙ=120 мин., минимально допустимая вероятность его непревышения Р(<Тзад)=0,9%, первоначальное среднее время обслуживания требования т=140 мин. (т = гИ0] = гсяи,+т™), тсив,=40 мин, С=100 мин, <5гуаг=4,5 мин. Требуется оценить эффективность использования информации в СОД в ходе её освоения. Выполняя необходимые расчеты в соответствии с описанной выше методикой, получена зависимость мощности Q системы обработки данных от объёма У(0 информации на протяжении периода 51 х п = 10х 20 = ЮОдней ввода СОД в эксплуатацию. Данная зависимость отражена в таблице 1 и характеризует эффективность от использования информации.

Таблица 1 Зависимость мощности Q системы обработки данных от объёма V(t) информации

Номер интервала времени 1 2 3 4 5 6 7 8 9 10

Объем информации, у и е 0 60 120 180 240 300 360 420 480 540

Длительность интервала обслуживания т,аг[У(1)], мин 100,0 95,5 91,0 86,5 82,0 77,5 73,0 68,5 64,0 59,5

Максимально-допустимое время ожидания требования, J 85,0 88,0 91,0 94,0 98,0 102,0 106,0 110,0 115,0 120,0

Мощность 0 4 4 7 7 7 7 7 7 7 11

11родолжение таблицы 1

Номер интервала времени 11 12 13 14 15 16 17 18 19 20

Объем информации, у.и.е. 600 660 720 780 840 900 960 1020 1080 1140

Длительность интервала обслуживания мин 55,0 50,5 46,0 41,5 37,0 32,5 28,0 23,5 19,0 14,5

Максимально-допустимое время ожидания требования. .1 126,0 132,0 139,0 147,0 155,0 165,0 176,0 188,0 203,0 220,0

Мощность 2 11 11 И 11 17 17 17 28 28 45

Как видно на рисунке 5, наращивание мощности СОД конвейерного типа осуществляется не пропорционально приращению объёма информации. Данное обстоятельство обусловлено наличием полиноминальной зависимости между временем т обслуживания требования и вероятностью Р(< Тзад) не превышения допустимого времени ожидания.___________________ ____________

Мощность <2 |

40

35 § ЛО

| " 20

10

О

Рисунок 5 - Пример наращивания мощности <2 системы обработки данных конвейерного типа в АСУ

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

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

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

О 200 ЮО <ЧСЮ коо ЮОО 1200

Объем информации !

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

Модель СОД конвейерного типа (рисунок 6) представляет собой СОД, состоящую из накопителя и элементов, распределенных по г уровням (г=7, 2, ., 'И'; м>~2, 3, ...). В состав каждого элемента входит определённое количество процессоров. Распределение элементов по уровням осуществляется по следующему правилу: каждый элемент верхнего уровня является источником требований для группы элементов нижнего уровня; в каждый элемент нижнего уровня поступают требования только из одного элемента верхнего уровня; в элементах каждого уровня реализуется одна или более функций процесса обслуживания требований.

На рисунке 6 обозначено: Ж- количество уровней в СОД, м>~1, 2,...\ п, - количество элементов г-го уровня; (а,/],у) - время, затрачиваемое на обслуживание требования в г'-м элементе, размещённом на а-м уровне, причём требование в этот элемент поступило из элемента у, размещённого на /]-м уровне.

Система обработки данных, в случае реализации принципа равномерного распределения нагрузки между элементами одного уровня и между процессорами внутри каждого элемента, функционирует следующим образом: на вход системы поступает требование, которое при занятости всех элементов 1-го уровня размещается в накопителе.

При освобождении одного из элементов 1-го уровня, в него поступает требование из накопителя. Производится выполнение возложенных на этот элемент функций; после выполнения функций в элементе 1-го уровня требование передаётся в свободный элемент, размещённый на 2-м уровне. Производится выполнение возложенных на этот элемент функций. Для класса СОД конвейерного типа решается задача определения зависимости между мощностью СОД и объёмом информации. Условия решения задачи: критерием для оценки мощности является максимальное количество требований, обслуживаемых в СОД в непрерывном интервале времени (интервале занятости), при соблюдении заданных максимально-допустимых значений времени ожидания требованиями обслуживания и вероятности его не превышения; объем технологической информации измеряется в условных информационных единицах [у.и.е]. Одна [у.и.е] соответствует объёму информации, необходимому для выполнения всех действий по одному из возможных типов событий (проблем) в целом для процесса: одному достоверно известному признаку любого события, одной достоверно известной труппе признаков, соотнесённой с одним событием (проблемой), одной достоверно известной группе задач, соотнесённой с одним событием (проблемой), одной достоверно известной группе работ, соотнесённой с решением всех задач, относящихся к одному событию (проблеме); процесс накопления (добавление или корректировка) технологической информации реализуется в заданной последовательности периодов обновления информации.

Следует отметить, что для практической реализации рассмотренных процедур обработки данных предлагается методика определения количества процессоров в зависимости от групп однотипных задач Количество Л/,(1,0,0),М2(1Д0),...,Л/Я,(1Д0) процессоров для элементов 1-го уровня системы определится следующим образом: находится выражение для параметра 3 (максимально-допустимого времени ожидания требованием обслуживания, выраженным в количестве интервалов обслуживания) через параметры М,(1,0,0), Тзад и ?((1Д0):

'7^x^,(1,0,0) К (1,0,0)

1=1, 2,. ,,п1; вместо параметра ./ устанавливается выражение, задаются значениями Тзад, 0,(1,0,0) и /,(1Д0). Определяются максимальные целые значения параметров М,(1,0,0), которые удовлетворяют заданным условиям.

7 =

где [...] - округление до меньшего целого,

В четвертом разделе приводится реализация модельно-алгоритмической поддержки при формировании СОД конвейерного типа

Рисунок 7 - Структурная схема реализации СОД конвейерного типа в распределенных АСУ Система обработки данных состоит из пяти блоков (рисунок 7). В первом блоке СОД производится сбор и запись информации обо всех проявившихся признаках, сопутствовавших поступившему требованию; во втором блоке на основании результатов анализа информации о признаках формулируется проблема или описывается событие, обусловившее требование; в третьем блоке - составляется список задач, решение которых должно привести к решению проблемы или соответствовать событию, обусловившему требование.

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

блоке уточняется принятое решение, регистрируются учетные записи, и составляется конвейерный план решения задачи

Информационные элементы рассмотренной модели хранятся в базе данных реляционного типа в виде совокупности отношений различной структуры. Поиск этих элементов осуществляется по запросу СУБД, сформированному на языке SQL и выдаваемому при обработке каждой производственной ситуации.

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

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

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

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

Приложения содержат графическую часть моделыю-алгоритмического обеспечения конвейерного выполнения задач в распределенных АСУ, диаграммы Ганта, сетевые графики и сравнительные диаграммы показателей эффективности многомашинных конвейерных планов обработки данных.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

Решение проблемы модельно-алгоритмического обеспечения конвейерного выполнения задач в распределенных АСУ базируется на следующих основных результатах, имеющих самостоятельное научное и практическое значение.

Система модельно-алгоритмического обеспечения реализована за

счет:

* адаптации методики типизации задач для АСУ с конвейерной организацией обработки данных, которая дала существенный эффект, так как совершенствуется внутренняя технология работы АСУ;

■ модификации алгоритма Джонсона (MJO), которая позволила ослабить действие нескольких ограничений, используемых в алгоритме Джонсона, сформировать многомашинные конвейерные планы, сделать объем доступной промежуточной памяти равным нулю;

■ модели оценки влияния процесса накопления информации на эффективность конвейерной обработки данных в распределенных АСУ, которая позволяет организовать процесс обслуживания информационных требований в АСУ с учетом количественной оценки различных вариантов распределения задач между процессорами СОД;

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

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

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

Основные результаты диссертационной работы опубликованы в следующих работах.

Публикации в изданиях, рекомендованных ВАК РФ:

1. Богданова, О.В. Анализ периодичных задач при реализации алгоритмов распределенной обработки информации и управления [Текст] / О.В. Богданова, Е JI. Вайтекунене, И.В. Ковалев, Р.Ю. Царев // Приборы и системы. Управление, контроль, диагностика. - М.: НАУЧТЕХЛИТИЗДАТ, 2008. Вып. 11. -С. 56-60.

2. Богданова, О.В. Планирование задач при мультиресурсной реализации алгоритмов распределенной обработки информации и управления [Текст] / H.A. Алексеев, О.В. Богданова, A.A. Волков //

Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева. - Красноярск, 2007. Вып 3(16) - С. 20 -23.

3. Богданова, О.В. Автоматизированная система оперативного производственного планирования и управления [Текст] / А.А. Алексеев, О.В. Богданова // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева - Красноярск, 2007. Вып. 3(16)-С. 55-58.

Прочие публикации по теме диссертационного исследования:

4. Богданова, О.В. Многоверсионность при управлении параллельными транзакциями [Текст] / О.В. Богданова, Г.А. Волкова, Е.С. Огнерубов // Вестник университетского комплекса: Сб. научн. трудов ВСФ РГУИТП, НИИ СУВПТ. - Красноярск, 2006. Выи. 7(20). -С. 231 - 234.

5. Богданова, О.В. Моделирование программной архитектуры автоматизированных систем обработки информации и управления [Текст] / О.В Богданова, Г.А. Волкова, Е.С. Огнерубов // Вестник университетского комплекса: Сб. научн трудов ВСФ РГУИТП, НИИ СУВПТ. - Красноярск, 2006. Вып. 7(20). - С. 235 - 240.

6. Богданова, О.В. Разработка структуры и алгоритмов поисковой мультиагентной системы [Текст] / О В. Богданова, Г.А. Волкова, Е.С. Огнерубов // Вестник университетского комплекса: Сб. научн. трудов ВСФ РГУИТП, НИИ СУВПТ. - Красноярск, 2006. Вып. 7(20). - С. 241 - 247.

7. Богданова, О.В. Система надежностного анализа клиент-серверной архитектуры распределенного программного обеспечения «программная система CSR-Analysis ver. 1.0» [Текст] / Н.Д. Амбросенко, О.В. Богданова, И.В. Ковалев, В.А. Морозов // Инновации в науке и образовании. Телеграф отраслевого фонда алгоритмов и программ. - М.. ВНТИЦ, 2006. Вып. 9(20) - С. 20 - 21.

8. Богданова, О.В. Универсальная информационная система мониторинга жизненного цикла продукции «программная система PLC-Monitor ver. 1.0» [Текст] / Н.А. Алексеев, О В Богданова, И.В. Ковалев, П.А. Саботаж, Р.Ю. Царев // Инновации в науке и образовании. Телеграф отраслевого фонда алгоритмов и программ. - М.: ВНТИЦ, 2006. Вып. 12(23)-С. 15-16.

9 Богданова, О.В. Планировщик расписаний «программная система Scheduling planning system ver. 1.0» [Текст] / Н.А. Алексеев, OB. Богданова, ИВ. Ковалев, К.В. Полянский, РЮ. Царев // Инновации в науке и образовании. Телеграф отраслевого фонда алгоритмов и программ. -М.. ВНТИЦ, 2007. Вып. 3(26) - С. 18 - 19.

10. Богданова, О.В. Типизация задач в информационных системах конвейерного управления [Текст] / О.В. Богданова // Вестник университетского комплекса: Сб. научн. трудов ВСФ РГУИТП, НИИ СУВПТ. - Красноярск, 2005. Вып. 6(20). - С. 180 - 190.

11. Богданова, O.B. Метод типизации задач в информационных системах конвейерного управления [Текст] / О.В. Богданова // Перспективные материалы, технологии, конструкции, экономика (июнь 2006г.) Материалы XII Всероссийской научно-практической конференции ГОУ ВПО ГУЦМиЗ. - Красноярск, 2006. Вып. 12.- - С. 195 - 198.

12. Богданова, О В. Типизация задач в информационных системах конвейерного управления [Текст] / О.В. Богданова // Решетневские чтения (ноябрь 2007г.). Материалы XI Международной научной конференции ГОУ ВПО СибГАУ. - Красноярск, 2007. - С. 277 - 278.

13. Богданова, О.В. Периодичные задачи при реализации алгоритмов распределенной обработки информации [Текст] / О.В. Богданова // Перспективы развития информационных технологий (апрель 2008г.). Материалы I Всероссийской научно-практической конференции ЦРНС - Новосибирск, 2008. - С.7 - 11.

14. Богданова, О.В. Обеспечение методов конвейерной организации выполнения информационных задач в АСУ [Текст] /О.В. Богданова // Совершенствование методов поиска и разведки, технологии добычи и переработки полезных ископаемых (апрель 2008). Материалы Межрегиональной научно-технической конференции ФГОУ ВПО СФУ, -Красноярск, 2008.-С. 10- 13.

Разработки, прошедшие регистрацию в Отраслевом фонде алгоритмов и программ:

15. Богданова О.В., Амбросенко Н.Д., Ковалев И В., Морозов В.А. Система надежностного анализа клиент-серверной архитектуры распределенного программного обеспечения «программная система CSR-Analysis ver. 1.0» М.: ВНТИЦ, 2006. - № 02067910.00014-01, Per. № ОФАП 6908.

16 Богданова О.В., Алексеев H.A., Ковалев И.В., Саботаж П.А., Царев Р.Ю. Универсальная информационная система мониторинга жизненного цикла продукции «программная система PLC-Monitor ver. 1.0» М • ВНТИЦ, 2006. - № 02067910.00016-01, Per. № ОФАП 7382.

17. Богданова О.В., Алексеев H.A., Ковалев И.В., Полянский К.В., Царев Р.Ю. Планировщик расписаний «программная система Scheduling planning system ver.1.0» M : ВНТИЦ, 2007. - № 03524577.01902-01, Per. № ОФАП 7916.

Богданова Ольга Витальевна М о д е л ь н о - а л го р и т.м и ч е с ко е обеспечение конвейерного выполнения задач в распределенных АСУ

Автореферат

Подписано в печать 6.11.2008. Заказ № -9Л& Формат 60x84/16. Усл. печ. л. 1,4. Тираж 100 экз. Отпечатано в отделе копировально-множительной техники СибГАУ 660014, г. Красноярск, просп. им газ. «Красноярский рабочий», 31

Соискатель

О.В. Богданова

ВВЕДЕНИЕ.

1 ОРГАНИЗАЦИЯ ОБРАБОТКИ ДАННЫХ В АСУ.

1.1 Информационное обеспечение АСУ.

1.1.1 Состав и свойства информационного обеспечения.

1.1.2 Стандартная схема обработки информации в АСУ.

1.2 Системы обработки данных (СОД).

1.2.1 Принципы проектирования СОД.

1.2.2 Этапы и механизмы обработки типовых задач в СОД конвейерного типа.

1.3 Типизация задач обработки данных конвейерного типа в АСУ.

1.3.1 Исходные данные, критерии и ограничения при решении задач обработки данных

1,3.20пределение типовых задач СОД конвейерного типа.

1.3.3 Методология анализа технологий обработки данных при разработке АСУ.

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

Выводы по разделу 1.

2 МОДЕЛЬНО - АЛГОРИТМИЧЕСКАЯ ПОДДЕРЖКА МЕТОДОВ ПАРАЛЛЕЛЬНОГО И КОНВЕЙЕРНОГО ВЫПОЛНЕНИЯ ЗАДАЧ В АСУ.

2.1 Процессы параллельной обработки информации.

2.1.1 Распараллеливание обработки информации в АСУ.

2.1.2 Задачи формирования параллельных процессов.

2.1.3 Детерминированные модели формирования параллельных процессов.

2.2 Классификация моделей.

2.2.2 Однопроцессорные модели.

2.2.3 Конвейерные модели.

2.2.4 Мультипроцессорные модели.

2.2.5 Периодичные задачи при формировании процессов.

Выводы по разделу 2.

3 МОДЕЛЬНО-АЛГОРИТМИЧЕСКОЕ ОБЕСПЕЧЕНИЕ МЕТОДОВ АНАЛИЗА ЭФФЕКТИВНОСТИ КОНВЕЙЕРНОГО ВЫПОЛНЕНИЯ ЗАДАЧ В АСУ.

3.1 Модель оценки влияния процесса накопления информации на эффективность конвейерной обработки данных в распределенных АСУ.

3.2 Метод оценки достаточной мощности системы обработки данных (СОД) конвейерного типа.

3.3 Технология обработки данных конвейерного типа в распределенных АСУ.

Выводы по разделу 3.

4 РЕАЛИЗАЦИЯ МОДЕЛЬНО - АЛГОРИТМИЧЕСКОЙ ПОДДЕРЖКИ ПРИ ФОРМИРОВАНИИ СОД КОНВЕЙЕРНОГО ТИПА В АСУ.

4.1 Описание СОД конвейерного типа в распределенных АСУ.

4.2 Алгоритм работы СОД конвейерного типа в распределенных АСУ.

Выводы по разделу 4.

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

Теоретические и методологические аспекты типизации задач в модульных системах обработки данных (СОД) отражены в работах отечественных и зарубежных авторов, таких как А.Г. Мамиконов, В.В. Кульба, С.А. Косяченко, А.С. Миронов, Е.Н. Сидоров, А.А. Ашимов, Ю.Ю. Кесс, В.М. Ревако, А.В. Товмасян, Б. Дюран, П. Оделл, X. Берж, О. Оре. Модели и методы обработки информации в технических и организационно - технологических системах рассмотрены в работах В.В. Воеводина, Б.А. Головкина, К.Г. Самофалова, Г.М. Луцкого, А.Б. Барских, E.JI. Шлимовича, А.П. Шабанова, Д. Филлипса, А. Гарсиа-Диаса, Р.В. Конвея, B.JL Максвелла, JI.B. Миллера.

Конвейерное выполнение типовых задач в распределенных АСУ определяет новый этап в проектировании АСУ, требует модельно -алгоритмического обеспечения выполнения задач и адаптации методики типизации задач для СОД конвейерного типа. Предложенная нами технология обработки данных предоставляет возможность формирования показателей эффективности работы отдельных процессоров, реализующих конвейерные планы, СОД и АСУ в целом. Реализация этой технологии даст существенный эффект на практике, так как совершенствуется внутренняя технология работы АСУ. Помимо этого описанный подход дает следующие преимущества: увеличение пропускной способности конвейерной системы обработки данных; обеспечение однородности функций конвейерной системы обработки данных, что позволяет снизить требования к АСУ; уменьшение времени и улучшение качества коммуникаций в системе.

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

Поставленная цель достигается путем решения следующих задач:

• анализа принципов обработки данных в автоматизированных системах управления;

• адаптации методики типизации задач для АСУ с конвейерной организацией обработки данных;

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

• оценки достаточной мощности СОД для распределенной АСУ с конвейерным типом выполнения задач;

• реализации системы модельно-алгоритмической поддержки методов конвейерной организации выполнения задач в распределенных АСУ;

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

Методы исследования. При выполнении работы использовались математическое и вероятностное моделирование параметров систем обработки данных конвейерного типа, элементы теории вероятностей, объектно-ориентированный анализ, количественные и оперативные методы управления проектами, сетевые диаграммы и диаграммы Ганта, теория систем массового обслуживания.

Научная новизна работы. Предложена концепция конвейерной обработки данных, для реализации которой разработано модельно-алгоритмической обеспечение, включающее: адаптацию методики типизации задач для СОД конвейерного типа в распределенных АСУ. модификацию алгоритма Джонсона, позволяющую формировать многомашинные конвейерные планы обработки данных. модель оценки влияния процесса накопления информации на эффективность конвейерной обработки данных в распределенных АСУ, которая позволяет организовать процесс обслуживания информационных требований в АСУ с учетом количественной оценки различных вариантов распределения задач между процессорами. алгоритм оценки достаточной мощности СОД для конвейерного выполнения задач в распределенных АСУ, позволяющий минимизировать общее время обслуживания информационных требований при совместном выполнении задач процессорами разных классов.

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

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

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

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

Реализация результатов работы. Диссертационная работа выполнялась в рамках тематического плана Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева (2005-2008гг.). Программные разработки по данной теме прошли экспертизу и зарегистрированы в Отраслевом фонде алгоритмов и программ (№ государственной регистрации 02067910.00014-01, 02067910.00016-01, 03524577.01902-01), что делает их доступными широкому кругу специалистов по автоматизации и управлению технологическими процессами и производствами.

Апробация работы. Основные положения и результаты работы прошли апробацию на всероссийских конференциях, научных семинарах и научно-практических конференциях. В том числе, на XII Всероссийской научно-практической конференции «Перспективные материалы, технологии, конструкции, экономика», Государственный университет цветных металлов и золота (Красноярск, июнь 2006г.), XI Международной научной конференции «Решетневские чтения», Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева (Красноярск, ноябрь 2007г.), I Всероссийской научно-практической конференции «Перспективы развития информационных технологий», Центр развития научного сотрудничества (Новосибирск, апрель 2008г.), Межрегиональной научно-технической конференции «Совершенствование методов поиска и разведки, технологии добычи и переработки полезных ископаемых», Сибирский федеральный университет (Красноярск, апрель 2008г.). Диссертационная работа в целом обсуждалась на научных семинарах Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева (2006-2008 гг.)

Публикации. По теме диссертации опубликовано 17 печатных работ (в том числе, три работы в изданиях по перечню ВАК РФ), из них 5 без соавторов. Полный список публикаций представлен в конце автореферата.

Выводы по разделу 4

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

Реализованная модельно - алгоритмическая поддержка при формировании СОД конвейерного типа позволит следующее: описывать процессы через последовательность и ветвления выполнения задач, где за каждой задачей закреплен конкретный конвейерный план обработки данных; после запуска первой задачи СОД и до выполнения последней стадии контролировать соответствие действий конвейерного плана описанию; предоставлять всю необходимую информацию для выполнения конкретной задачи; после выполнения очередной задачи информировать следующий (следующих) конвейерный план о возникновении у них задачи; сохранять информацию о времени появления, времени и качестве выполнения задачи; при отклонении от нормативных параметров информировать администратора о просрочках выполнения или о некачественном выполнении задачи.

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

ЗАКЛЮЧЕНИЕ

Система модельно-алгоритмического обеспечения реализована за счет: адаптации методики типизации задач для АСУ с конвейерной организацией обработки данных, которая дала существенный эффект, так как совершенствуется внутренняя технология работы АСУ; модификации алгоритма Джонсона (MJO), которая позволила ослабить действие нескольких ограничений, используемых в алгоритме Джонсона, сформировать многомашинные конвейерные планы, сделать объем доступной промежуточной памяти равным нулю; модели оценки влияния процесса накопления информации на эффективность конвейерной обработки данных в распределенных АСУ, которая позволяет организовать процесс обслуживания информационных требований в АСУ с учетом количественной оценки различных вариантов распределения задач между процессорами СОД; алгоритма оценки достаточной мощности СОД для конвейерного выполнения задач в распределенных АСУ, который позволяет минимизировать общее время обслуживания информационных требований при совместном выполнении задач процессорами разных классов.

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

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

1. Поспелов Д.А. Введение в теорию вычислительных систем.- М.: Советское радио, 1972. С. 450.

2. Алексеев А.А., Богданова О.В. Автоматизированная система оперативного производственного планирования и управления//Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева. Красноярск, 2007,.Вып 3(16) - С. 58

3. Прангишвили И. В., Стецюра Г. Г. Современное состояние проблемы создания ЭВМ с нетрадиционной структурой и архитектурой, управляемых потоком данных//Электронная промышленность. 1981. С. 365

4. Воеводин В.В. Информационная структура алгоритмов. М.: Изд-во МГУ, 1997-С. 500.

5. Воеводин В.В., Капитонова А.П. Методы описания и классификация архитектур вычислительных систем. М.: Изд-во МГУ, 1994 С. 350.

6. Ginsberg М. Some observations on supercomputer computational environments//Parallel and large-scale computers: performance, architecture, applications. Amsterdam: North-Holland, 1983.P. 184.

7. Слепцов, А.И. Автоматизация проектирования управляющих систем/ А.И. Слепцов, А.А. Юрасов.- Киев: Техника, 1986. С. 268.

8. Олифер, В.Г. Компьютерные сети. Принципы, технологии, протоколы/В.Г. Олифер, Н.А. Олифер.- СПб: Питер, 1999. С. 698.

9. Neumann, К. Stochastic Project Networks. Temporal Analysis, Scheduling and Cost Minimization/ K. Neumann//Lecture Notes in Economics and Mathematical Systems, No. 34, Springer-Verlag, 1990. C. 452

10. Блюменау Д.И. Информация и информационный сервис. — Д.: Наука, 1989. С. 623

11. П. Богданова, О.В. Типизация задач в информационных системах конвейерного управления/Материалы XI Международной научной конференции «Решетневские чтения», Красноярск. 2007,. — С. 278.

12. Shaw М., Garlan D. Formulations and formalisms in software architecture//Computer Science Today. 1995. №1000. P. 323.

13. Spencer D. Webster's new world dictionary of computer terms. New York: Prentice Hall, 1993. C. 289.

14. Гаврилова T.A., Хорошевский В.Ф. Базы знаний интеллектуальных систем. СПб: Питер, 2001. - С.384.

15. Глушков В.М. Введение в АСУ. Киев: Техника, 1974. - С. 318.

16. Липаев В.В. Проектирование тематического обеспечения АСУ. — М.: Сов. радио. 1977.-С. 400.

17. Мамиконов А.Г. Основы построения АСУ. М.: Высш.шк., 1981. -С. 248.

18. Мамиконов А.Г., Кульба В.В., Миронов А.С., Товмасян А.В. Предпроектный анализ структуры информационных потоков и технологий обработки данных при разработке модульных СОД. М.: ИПУ, 1980 - С. 43.

19. Мамиконов А.Г., Кульба В.В., Косяченко С.А. Типизация модульных систем обработки данных. М.: Наука, 1989 - С. 125.

20. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов/Пер. с англ. — М.: Мир, 1981 С.366.

21. Модин А.А., Яковенко Е.Г., Погребной Е.П. Справочник разработчика АСУ. М.: Экономика, 1978 - С. 583.

22. Жимерин Д.Г., Мясников В.А. Автоматизированные и автоматические системы управления. М.: Энергия, 1979. - С. 592.

23. Комков Н.И., Левин Б.И., Журдан Б.Е. Организация систем планирования и управления прикладными исследованиями и разработками. -М.: Наука, 1986-С. 233.

24. Бурков В.Н., Кондратьев В.В., Механизмы функционирования организационных систем. -М.: Наука, 1981 С. 383.

25. Дюран Б., Оделл П. Кластерный анализ. М.: Статистика, 1977 - С.170.

26. Берж X. Теория графов и ее применения. М.: Изд-во иностр. лит., 1962-С. 319.

27. Воеводин В.В. Математическая модель конвейерных вычислений. — М., 1982-С. 34.

28. О. Оре. Графы и их применение: М.: Мир, 1965. - С. 241.

29. Липатов Е.П. Теория графов и её применение. М.: Знание, 1986.

30. Н.С. Новиков. Дискретная математика. СПб.: Питер, 2001. С. 423.

31. Блох А.Ш. Граф-схемы и алгоритмы, Минск, Высшая школа, 1987. -С. 438.

32. Головкин Б.А. Параллельные вычислительные системы. — М.: Наука, 1980.-С. 216.

33. Анфилатов B.C., Емельянов А.А. Системный анализ в управлении. — М.: Финансы и статистика, 2007. С. 368.

34. Артамонов Г.Т. Анализ производительности ЭВМ методами теории массового обслуживания. — М.: Энергия, 1972. — С. 439.

35. Лютерник Л.А., Соболев В.И. Элементы функционального анализа. -М.: Наука, 1985.-С. 136.

36. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. -М.: Наука, 1987.-С. 226.

37. Богданова О.В., Слободин М.Ю., Третьяков В.Г. Типизация задач в информационных системах конвейерного управления//Вестник университетского комплекса: Сб. научн. трудов; Красноярск: ВСФ РГУИТП, НИИ СУВПТ. 2005. Вып. 6(20). - С. 184.

38. Барский А.Б. Параллельные процессы в вычислительных системах. Планирование и организация.- М.: Радио и связь, 1990, С. 256.

39. Воеводин В.В. Математические модели и методы в параллельных процессах.- М.: Наука, 1986, С. 328.

40. Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов. М: Радио и связь, 1983, С. 272.

41. Ковалев И.В., Царев Р.Ю., Шиповалов Ю.Г. Параллельные процессы в информационно-управляющих системах. Формирование и оптимизация//Под ред. д.т.н., проф. А.В. Медведева. Красноярск: НИИ СУВПТ, 2001. - С. 143.

42. Ковалев И.В., Царев Р.Ю. Моделирование и оптимизация параллельных процессов в информационно-управляющих системах: Учебное пособие, Красноярск: ИПЦ КГТУ, 2003. - С. 124.

43. Лебедев В.А., Трохов Н.Н., Царев Р.Ю. Параллельные процессы обработки информации в управляющих системах. Красноярск: НИИ СУВПТ, 2001.-С. 143.

44. Липаев В.В. Проектирование программных средств. М.: Высш. шк., 1990, С. 303.

45. Олифер В.Г., Олифер Н.А. Сетевые операционные системы. СПб.: Питер, 2001.-С. 544.

46. Толковый словарь по вычислительным системам.//Под ред. В. Иллигуорта и др.: Пер с англ.- М.: Машиностроение, 1991.- С. 560.

47. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей: Пер. с англ.- М.: Мир, 1984, С. 496.

48. Gonzalez J.M. Deterministic Processor Scheduling // Computing Surveys, Vol. 9, No. 3, 1977.

49. Phillips D. Т., Garsia-Diaz A. Fundamentals of network analysis, Prentice-Hall, Inc., Englewood Gliffs, New Jersy, 1981, P. 386.

50. Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем / Под общ. ред. А. П. Ершова. -М.: Наука, 1982.-С. 356.

51. Кухарчук А.Г., Луцкий Г. М., Реутов Г. В. Конвейерный принцип обработки информации.//Кибернетика. 1968. № 6. С. 49.

52. Луцкий Г.М. Концепция структурной организации эффективных ВС конвейерного типа/Распараллеливание обработки информации. Ч.З./Ф.МИ АН УССР.-Львов, 1983. С. 56.

53. Луцкий Г.М. Структурная организация многомерных конвейерно-циклических вычислительных средств//Распараллеливание обработки информации. Ч.2/ФМИ АН УССР. Львов, 1985. - С. 76.

54. Луцкий Г.М., Кулаков Ю.А., Русанова О.В. Повышение эффективности выполнения линейных программ в конвейерных вычислительных системах/УПараллельное программирование и высокопроизводительные системы. Киев: Наукова думка, 1982. Ч. 3. - С. 458.

55. Мануэль Т. Усовершенствованные параллельные архитектуры как способ ускорения вычислений//Электроника. 1983. № 12. С. 25 39.

56. Нагорный Л.Я. Методы распараллеливания систем управлений большой размерности для решения их на многопроцессорных структурах//Электронное моделирование. 1980. № 1. С. 28 -32.

57. Самохвалов К.Г., Луцкий Г.М. Основы построения конвейерных ЭВМ.—Киев: Вищашкола, 1981.-С. 224.

58. Самохвалов К.Г., Луцкий Г.М., Талаев А.К. Архитектура многоуровневых конвейерных вычислительных систем/Распараллеливание обработки информации. Ч.2/ФМИ АН УССР. Львов, 1985. С. 23.

59. Васкевич Д. Стратегия клиент/сервер. Киев: Диалектика, 1997.

60. Vaskevitch D. Client/server strategies. A survival guide for corporate reengineers. Foster City: IDG Books Worldwide, 1995. C. 265.

61. Чаудхари С. Методы оптимизации запросов в реляционных системах//СУБД. 1998. №3. С. 36.

62. Гилу а М.М. Множественная модель данных в информационных системах. М.: Наука, 1992. - С. 320.

63. Оззу М.Т., Валдуриз П. Распределенные и параллельные системы баз данных//СУБД. 1996. №4. С. 26.

64. Арефьев А.А, Кораблин Ю.П., Кутепов В.П. Язык граф — схем параллельных алгоритмов и его расширения. М.: Программирование, 1981, № 4, С. 25.

65. Барский А.Б. Планирование параллельных вычислительных процессов. М.: Машиностроение, 1980. —С. 191.

66. Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем/Под ред. В.Е. Котова, И. Миклюшко. М.: Наука 1982. - С. 336.

67. Шабанов А.П. Подход к формализации учётно-контрольного процесса при решении проблемы минимизации ресурсов организационной структуры// Современные сложные системы управления: Сб. тр. науч. практ. конф. - Воронеж, ВГАСУ,2005, С. 186

68. Барсегян А.А. Технологии анализа данных: Data Mining, Visual Mining, Text Mining, OLAP. СПб.: БХВ-Петрбург, 2007. - С. 384.

69. Шлимович E.JI. Концепция управленческого учета, основанная на методах «конвейерного» управления. М.: AvaccoSoft, 2005. - С. 26.

70. Богданова, О.В. Периодичные задачи при реализации алгоритмов распределенной обработки информации/Материалы I Всероссийской научно-практической конференции «Перспективы развития информационных технологий», Новосибирск. 2008,. - С. 100.

71. Балабанов А.С. Многопроцессорные системы. Основные принципы организации. Управл. системы и машины, 1983, № 3, С. 216.

72. Артамонов Г.Т. Анализ производительности ЭВМ методами теории массового обслуживания. М.: Энергия, 1972. - С. 268.

73. Лютерник Л.А., Соболев В.И. Элементы функционального анализа. — М.: Наука, 1985.-С. 435.

74. Вдовин В.М., Суркова Л.Е. Информационные технологии в финансово-банковской сфере: Практикум. — М.: Издательско-торговая корпорация «Дашков и К», 2008. С. 248.

75. Брандт 3. Анализ данных. Статистические и вычислительные методы для научных работников и инженеров: Пер. с англ. М.: Мир, 2003. — 686 с.

76. Ганшин Г.С. Методы оптимизации и решение уравнений. М.: Наука. Гл. ред. физ.-мат. лит., 1987. — С. 128.

77. Банди Б. Методы оптимизации. Вводный курс: пер. с англ. — М.: Радио и связь, 1988. С. 128.

78. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров: пер. с англ. М.: Наука. Гл. ред. физ.-мат. лит., 1984. - С. 831.

79. Авиженис А.Н. Гарантоспособные вычисления: от идей до реализации в проектах/Авиженис А.Н., Лапри Ж.-К.: ТИИЭР, 1989. С. 21.

80. Волкова В.Н., Денисов А.А. Основы теории систем и системного анализа. СПб: Изд-во СПбГТУ, 2001. С. 512.

81. Проектирование информационных систем: учеб. пособие/ Клещев Н., под общей ред. К.И. Курбакова. — М.: Изд-во Рос. экон. акад., 2000. С. 386.

82. Вендеров А. CASE-технологии. Современные методы и средства проектирования информационных систем. — М.: Финансы и статистика, 1998. — С. 176.

83. Вендеров А. Практикум по проектированию программного обеспечения экономических информационных систем: Учеб. пособие. — М.: Финансы и статистика, 2002. — С. 192: ил.

84. Федорова Г. Проектирование информационных систем: Учебное пособие М.: Изд-во МЭСИ, 2001 - С. 142.

85. Смирнова Г. Проектирование экономических информационных систем: Учеб./Г. Смирнова, А. Сорокин, Ю. Тельнова; под ред. Ю.Ф. Тельнова. -М.: Финансы и статистика, 2001. С. 512: ил.

86. Богданова О.В., Алексеев Н.А., Ковалев И.В., Саботаж П.А., Царев Р.Ю. Универсальная информационная система мониторинга жизненного цикла продукции «программная система PLC-Monitor ver.1.0» М.: ВНТИЦ, 2006. № 02067910.00016-01, Per. № ОФАП 7382.

87. Гэри Хансен. Базы данных: разработка и управление: Пер. с англ. — М.: ЗАО Изд-во «БИНОМ», 1999. С. 704: ил.

88. Поспелов Д.А. Введение в теорию вычислительных систем. — М.: Советское радио, 1972, С. 450.

89. Богданова О.В., Алексеев Н.А., Ковалев И.В., Полянский К.В., Царев Р.Ю. Планировщик расписаний «программная система Scheduling planning system ver.1.0» M.: ВНТИЦ, 2007. № 03524577.01902-01, Per. № ОФАП 7916.

90. Хокпи Р., Джесхоуп К. Параллельные ЭВМ. М.: Мир, 1986 - С.390.

91. Эрглис К. Открытые модульные многопроцессорные информационно — измерительно — управляющие системы/Юткрытые системы. — 1995г. -№2. С. 61.

92. Мячев А.А. Спецификация многопроцессорных систем компании Intel/Юткрытые системы. 1995г. -№3. С. 63.

93. Рудаков А.В. Технология разработки программных продуктов: учеб. пособие/А.В. Рудаков. — М.: Academia, 2006. С. 208.

94. Фельдман Я.А. Создаем информационную систему. М.: Солон, 2006.-С. 120.