СППР

49

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

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

Прежде всего, необходимо подчеркнуть, что при выборе компьютера должны быть соблюдены общесистемные требования: системного единства, развития, совместимости, стандартизации ; [28]. Это обуславливает необходимость выбора ПЭВМ из серийных средств вычислительной техники общего назначения с минимальным использованием специализированных устройств, применение которых должно быть технически и экономически обосновано.

Обобщённая схема выбора ПЭВМ приведена на рис. 1.9.

*

Рис. 1.9. Схема выбора ПЭВМ

Рис. 1.10. Дерево локальных критериев задачи выбора

51

Дерево локальных показателей задачи выбора ПЭВМ показано на рис. 1.10.

Общая постановка задачи выбора ПЭВМ может быть описана следующим образом.

Существует множество вариантов выбора ПЭВМ: i= l,s. Каждый г'-й вариант характеризуется набором технических средств: Xi = jx,0,...,*'0!.

В соответствии с рис. 1.10 в состав ПЭВМ могут входить: микропроцессор, материнская плата, ОЗУ, монитор, видеоадаптер, накопитель на жёстком магнитном диске (НЖМД), накопитель на гибком магнитном диске (НГМД) и другие средства.

Для каждого варианта комплектации ПЭВМ существует вектор показателей качества Q = ^gi(Xl),..., q^ X i)... qm{X,)\. Будем считать, что

среди показателей есть I количественных ( j = 1,/), приведённых к нормированному виду от нуля до единицы ^1(Jf1), ..., qi(Xt) и (т - I) качественных, представленных в виде функции принадлежности требуемому уровню качества μ;+1(Jff),...^e (Jff). Необходимо выбрать такой вариант Z0 состава ПЭВМ, который обеспечит оптимальное

(рациональное) значение векторного критерия Q , т.е.

I 0 = srgopt Qi ( X i )
/ o i i	О·” )
і - I1S

Задача (1.11) относится к классу задач нечёткой многокритериальной оптимизации. Обзор возможных методов решения подобных задач приведен, например, в работе [29].

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

Применение метода сводится к следующим операциям. 1. Упорядочиваются показатели по важности

qx >q1 > ...>qj > ...>qm; j = l,m.

2. При согласии ЛПР для каждого показателя назначается величина допустимой уступки Aqj ; j = 1,/я, в границах которой рассмотренные

альтернативы считаются практически равноценными.

3. Для первого по важности показателя ςτ, формируется множество π, "практически равноценных" альтернатив, которые удовлетворяют условию

52

шах "Ч&ХіУЧіІХк) -		(I-12)
/=1,S	к*4п
.=Zi0

4. Если множество K1 содержит только один вариант, то он и является наилучшим. Если множество Tt1 содержит более одного варианта,

то переходим к рассмотрению множества It1 по показателю q2.

5. Для второго показателя q2 формируется множество π2 вариантов из множества U1, которые удовлетворяют условию

	шах q2(Xi} - q l(Xk)<&q2.			(1.13)
	/etc,	кєк,
	<=/>>	MJn
6. Если множество It2 содержит только один вариант, то				он и
считается наилучшим;	если больше одного -		рассматриваем эти варианты
по показателю q3 и т.д.
7. Если все показатели последовательно рассмотрены и в результате
получено множество	π - π 1χ π 2χ...χπΛ,		содержащие более	одной
альтернативы, то можно применить два подхода:

-уменьшить величину допустимой уступки Aqj , начиная с первого по важности показателя и повторить все шаги решения;

-предоставить ЛПР окончательный выбор лучшего варианта.

1.53. ОПТИМАЛЬНАЯ ОРГАНИЗАЦИЯ ФУНКЦИОНИРОВАНИЯ РАСПРЕДЕЛЁННОЙ СППР

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

Пусть Г = {ґ,} - множество задач, требующих обслуживания, η( -

функции штрафа за пребывание задачи г, в системе. Необходимо найти такую перестановку задач П, где П(Аг) = /, если f-я задача должна быть решена к-й по счёту, чтобы суммарная функция была минимальной, т.е.

53

(1.14)

Задача составления расписаний в постановке (І.14) относится к классу NP-полных, которые традиционно считаются трудноразрешимыми. Учитывая то обстоятельство, что задача решается часто в реальном масштабе времени, необходимо использовать такие методы, которые обладали бы наименьшей вычислительной сложностью. Одним из таких методов является метод [11], вычислительная сложность которого в худшем случае равна 0(п2). В этом методе в качестве показателя эффективности (критерия стоимости) расписания используется среднее взвешенное время завершения заданий.

Для формализации задачи P составления расписания введём следующие обозначения:

(Fj <) - система заданий, где F есть индексированное множество из

и заданий, п > О, а < - отношение частичного порядка (отношение предшествования), заданное HaF;

I(P) - набор индексов F; Tj ,j є I(P) - элемент F;

Xj,j є I(P) - потребность задания Tj- во времени обслуживания;

(оj , j е I(P) —стоимость пребывания задания Tj в системе (важность

задачи).

Величины X j и O ij определяются либо как средние значения при

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

Поскольку мы рассматриваем лишь один процессор, то будем рассматривать расписания, задаваемые перестановкой индексов заданий.

Перестановка а = а 1, а 2,...,ал элементов I(P) совместима с Р, если Tj < Tj

влечёт к < к , где в* = j и a* = j

Перестановка а = а 1(а 2,...,а„ элементов I(P) определяет расписание естественным образом: задание Tai выполняется первым, задание Jai -

вторым и так далее. Среднее взвешенное время завершения задания для расписания, определяемого перестановкой а , определяется следующим образом:

54

Перестановка а (расписание) является оптимальной, если а совместима с P и при этом достигается минимум /'(а) среди всех

ω,

перестановок, совместимых с Р. Пусть Pj = — для всех j из I(P).

z J

Теорема 1.1 [11]. Пусть P - задача упорядочения. Тогда перестановка а = CClyCt2,...,ал оптимальна по отношению к P тогда и только тогда, когда

Рщ * Pai * -	^ Po, ·
Приведённая теорема по сути определяет содержание алгоритма
нахождения такой перестановки.
Пусть	U a I ( P )		и	U * 0 .	Определим	t(U),	a(U) и р(Ц)
следующим образом:
	Ч Ю = Σ τ; . ω(ί/) = Σ ® , . Ρ Ψ ) = ~ Г						■
		JeV			JeU	τ Ψ )
Определение 1.1. Набор U c I(P) назовём начальным множеством
по отношению к Pt если:
1 ) U * 0 ;				є U влечёт / t U .
2) если Tj < Tj, то j
Пусть	У -	класс		начальных множеств (по отношению к Р).
Определим число р* = max p(U).
Определение		1.2.	Множество		U £ I(P) назовём /^максимальным
множеством по отношению к Р, если:
I) U e Y ;

2)P(U) = P*;

3)если V е Y ; p(V) = р* и V с U , то V = U .

Пусть U с I(P) и определим FSU как F fU ~ (Tj \ Tj є F ,j є U }.

Обозначим через Hj множество, состоящее из индекса j и индексов

івсех заданий, для которых Ti < Tj . Построение оптимальной

перестановки в задаче P составления расписания может быть осуществлено следующим образом. Каждому заданию T1 ставится в

соответствие число р(Нj), а затем определяется индекс I такой, что

P(H1) > P(Hj ) для j є I(P), причём P(H1) > P(Hj ) для всех индексов

j *1 . Поскольку T1 является предшественником всех заданий, индексы которых входят в H1, то существует оптимальная относительно P перестановка а такая, что а = а /(H1-{/}); а /(I(P) - H 1). Таким образом,

55

задача P может быть "разложена" на две меньшие, а именно: P/(H 1- {/}) и

P I(I(P )-H 1) .

Алгоритм. Вход: P - задача составления расписания. Выход: оптимальное расписание для Р.

procedure OPT(P) begin

ifP пусто then return λ (пустая перестановка) else

begin

Пусть I есть индекс задания из P такой, что H1 является р- максимальным множеством для Р.

U - = H 1- U y t V ^ I ( P ) - H l .

return OPT(PZU),, OPT(PfV) end

end OPT.

Процедура ОРТ является рекурсивной, она имеет в качестве единственного входного параметра задачу упорядочения. Результатом её выполнения оказывается оптимальная перестановка по отношению к входной задаче. Выполнение оператора return <выражение> заключается в вычислении <выражения> и возврате в точку вызова процедуры с вычисленными значениями в качестве результата.

1.5.3.2. Маршрутизаций вычислений в распределённой СППР.

Распределение потоков информации в сети, образованной локальными GiUlP, возлагается на систему управлению сетью. Задача распределения состоит в выборе и установлении оптимального пути передачи информации от источника информации к потребителю с учётом ситуации на сети. В [18] показано, что кратчайший путь между узлами і и j сети является наиболее надёжным.

В основу алгоритма маршрутизации положим модифицированный алгоритм Флойда [30]. Структурная схема алгоритма приведена на рис. 1.11 и включает следующие операции.

1.Вводится размерность рассматриваемой сети п.

2.Вводится треугольная матрица весовых коэффициентов сети

Mi,j).

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

4.Строится квадратная матрица последовательно растущей

размерности

элементы которой есть длины кратчайших маршрутов,

соединяющих узлы г и j при условии, что промежуточными узлами этих

Рис. 1.11 Структурная схема алгоритма нахождения кратчайших маршрутов

57

маршрутов могут быть только узлы, номер которых не превышает размерности построенной матрицы.

5. Строится квадратная матрица последовательно растущей размерности s ( i,j) , элементы которой - номера узлов, записанные в определённом порядке, позволяют восстановить кратчайший маршрут, соединяющий узлы і иj.

номер первой промежуточной вершины на текущем маршруте s ( і , j j = от j кj , если такая существует;

j, если промежуточных вершин не существует.

6.	Рассматриваем		матрицу	a (i,j)	размерности	2.
а(1,2) = а(2,1) = Ц1.2);		*(1,2) = s(2,l) = 1.
.7.	Итерация по	А + 1.	Построив	матрицу a ( i , j ) к-й размерности,
матрицу (£ + 1)-й размерности строим следующим образом:
а)	в матрице весовых коэффициентов Mi, j)				просматриваем	Jt+ 1

столбец и запоминаем весовые коэффициенты и номера узлов, из которых существует маршрут в узел к + 1: s(p,j) = р;

б) вычисляем весовые коэффициенты возможных маршрутов ^(i,j)x a(i,p)+ * ip ,j) и выбираем среди них маршрут с минимальным весом;

в) заполняем £ + 1 столбец и £ + 1 строку матрицы полученными весовыми коэффициентами.

8.*:=* + 2.

9.Если jfc = я + 1, то останов, иначе - переход на 7.

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

1.5.3.3. Стратегия информационного обмена между локальными СППР. Для реализации обмена данными между локальными СППР в процессе функционирования распределённой СППР целесообразно использовать так называемую "доску объявлений" [31]. Доска объявлений - это глобальная структура данных, предназначенная для осуществления обмена информацией о фактах, логических выводах и целях между различными локальными СППР, образующими узлы распределённой СППР. Её возможности определяются способом обеспечения общей основы и интерфейса для совместного использования полезной информации как внутри отдельных локальных СППР, так и сети взаимодействующих локальных систем.

58

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

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

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

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

Для выбора информации, которая должна передаваться или приниматься на локальную доску объявлений СППР, должна быть