Например, Бобцов

СРЕДСТВА ВЕКТОРНОЙ ОПТИМИЗАЦИИ СТРУКТУРЫ КЛАСТЕРОВ В СРЕДЕ MATHCAD НА ОСНОВЕ МЕТОДА STEM

СРЕДСТВА ВЕКТОРНОЙ ОПТИМИЗАЦИИ СТРУКТУРЫ КЛАСТЕРОВ…
6 КОМПЬЮТЕРНЫЕ СИСТЕМЫ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ
УДК 519.816+338.24
СРЕДСТВА ВЕКТОРНОЙ ОПТИМИЗАЦИИ СТРУКТУРЫ КЛАСТЕРОВ В СРЕДЕ MATHCAD НА ОСНОВЕ МЕТОДА STEM
К.А. Булыгин, В.Ю. Пинкевич, В.А. Богатырев
Предложены средства решения задач векторной оптимизации в системе компьютерной математики Mathcad на основе метода STEM. Рассмотрено применение предлагаемых средств для оптимизации структуры кластера. Ключевые слова: векторная оптимизация, STEM, принятие решений, кластер, компьютерная математика, Mathcad.
Введение Проектирование компьютерных систем кластерной архитектуры связано с обеспечением их высокой надежности и производительности при низких затратах на построение и эксплуатацию системы, что обуславливает необходимость решения задач векторной оптимизации [1]. Эффективность векторной оптимизации во многом зависит как от выбора метода поиска решений, так и от используемых для этого инструментальных средств. В качестве инструментальных средств оптимизации может использоваться система компьютерной математики Mathcad, включающая встроенные функции оптимизации Minimize (f, x1, x2,…) / Maximize (f, x1, x2, …) [2]. Сведение векторной задачи оптимизации к скалярной на основе метода отклонения от идеала, мультипликативного или аддитивного критерия [1], программная реализация которых в среде Mathcad предложена в [3], сопряжена с субъективностью задания весов (важности) частных критериев. Формально определить веса частных критериев позволяет известной метод STEM, предполагающий выполнение многоэтапной процедуры [1]. В настоящей работе решается задача расширения возможностей системы Mathcad в результате программирования набора средств (функций) поддержки векторной оптимизации на основе метода STEM.
Постановка задачи оптимизации кластера В качестве объекта оптимизации рассмотрим многоуровневую компьютерную систему кластерной архитектуры с резервированием узлов на каждом уровне (рисунок) [4, 5].
Рисунок. Структура кластерной системы
Требуется найти кратность резервирования (число узлов на каждом уровне) m1, m2 ,..., mM , при которой обеспечивается максимум надежности системы, минимум среднего времени пребывания в ней заявок, максимум интенсивности входного потока заявок, который система выдерживает в стационарном режиме, и минимум стоимости. Кроме того, стоимость реализации системы не должна превышать C0.
Таким образом, U (m1, m2 ,..., mM )  min , (m1, m2 ,..., mM )  max и C(m1, m2 ,..., mM )  min при
M
C(m1, m2 ,..., mM )  mici  C0 . Возможна постановка задачи минимизации стоимости при ограничении i 1
остальных показателей. Задачи векторной оптимизации кластеров в различных постановках решались в [5–9]. При оптимизации будем считать заданными: интенсивность входного потока заявок λ; вероятности безотказной работы узлов p1, p2 , p3 ,..., pM ; средние времена обработки заявок узлами v1, v2 , v3 ,..., vM ; стоимости узлов соответствующих уровней c1, c2 , c3 ,..., cM .
70 Научно-технический вестник информационных технологий, механики и оптики,
2012, № 4 (80)

К.А. Булыгин, В.Ю. Пинкевич, В.А. Богатырев

Оценка частных показателей качества

Надежность системы оценим по вероятности сохранения работоспособности, которая зависит от формулировки условия отказа (сохранения функционирования Y). Если система работоспособна, когда

на i-м уровне системы исправно не менее чем di узлов, то надежность системы [6, 7] составляет

   m1
P(m1 , m2 , m3 ,..., mM ) 

m2

m3 mM
...

C C C ...C k1 k2 k3 m1 m2 m3

kM mM

k1  d1 k2  d2 k3  d3 kM  d M

,



p k1 1

p k2 2

p

k3 3

...

p

kM M

(1 

p1 )m1  k1 (1 

p2 )m2  k2 (1 

p3

)m3 k3 ...(1 

p )mM kM M

где m1, m2 , m3 ,..., mM – число узлов на каждом уровне, Cmk  m!/(k !(m  k)!) – число сочетаний из m по k. Если условие работоспособности заключается в исправности на каждом уровне хотя бы одного

M
узла [8, 9], то P(m1, m2 , m3 ,..., mM )  (1 (1 pi )mi ) . i 1
Представим каждый узел системой массового обслуживания типа M/M/1. Считая, что каждая заявка последовательно обслуживается одним из исправных узлов на каждом уровне системы, среднее время

пребывания заявок в системе равна

M
U (m1, m2 , m3 ,...mM )  i /(1 i mi ) . i 1
Максимальная интенсивность входного потока заявок

(m1, m2 , m3 ,...mM )  miin(mi / i ). Функцию для вычисления надежности в Mathcad зададим как

P(N ):= r  1

for j  0 .. last  p

     r  r N j combin N j ,i p j i 1 p j N j i i elem _ min j
r

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

Метод STEM

Метод STEM предусматривает выполнение многоэтапной процедуры [1]. Сначала проводится оптимизация по каждому критерию в отдельности, в результате формируется матрица значений критериев для найденных вариантов. Затем эта матрица нормализуется, и по ней находятся технические веса критериев. После этого проводится оптимизация по аддитивному критерию с использованием найденных весов. Результат предъявляется лицу, принимающему решение (ЛПР), которое может принять найденный вариант или изменить условия (ограничения) по частному критерию, не удовлетворяющему требованиям к системе, и этапы поиска решения повторяются.

Описание реализованных средств оптимизации

Система функций реализации метода STEM включает несколько вспомогательных и основных функций. Далее описаны только самые важные из них. Исходными данными для представленных функций является множество вариантов, заданное в виде матрицы, строки которой являются векторами критериев.
Вспомогательные функции нужны для выполнения некоторых операций с векторами. Функция is_member(z, V) служит для проверки, является ли значение z элементом вектора V. Функция fill_vector(value, length) возвращает вектор длины length, заполненный значением value. Функции i_max(V) и i_min(V) возвращают индексы максимального и минимального элемента в векторе.
Функция нормализации нормализует значения всех критериев в заданной матрице по столбцам и приводит их к виду «чем больше, тем лучше». Эта и другие функции принимают в качестве параметра вектор (L_b) («less better») с номерами критериев вида «чем меньше, тем лучше».
Функции для нахождения множества вариантов, удовлетворяющих заданным ограничениям. Функция is_satisfied(Crits,Lim, L_b) проверяет значения критериев одного варианта на соответствие ограничениям, а функция stem_R(R, Lim, L_b) возвращает матрицу из тех векторов критериев, которые удовлетворяют наложенным ограничениям:

Научно-технический вестник информационных технологий, механики и оптики, 2012, № 4 (80)

71

СРЕДСТВА ВЕКТОРНОЙ ОПТИМИЗАЦИИ СТРУКТУРЫ КЛАСТЕРОВ…

stem _ R(R,Lim,L _ b):= j  0 for i  0..rows(R) 1

if is _ satisfied (RT ) i ,Lim,L _ b newR j  (RT ) i j  j 1

newRT Функция скалярной оптимизации, stem_T ( R,Lim,L_b ):= SR  stem _ R(R,Lim,L _ b)
Cols  SRT for n  0..cols(SR) 1

T n  Cols i _ max(SR n ) if is _ member(n,L _ b)

Cols i _ max(SR n ) otherwise

TT ,

находит варианты, лучшие по каждому из частных критериев (располагаемые по диагонали полученной матрицы).
Функции для нахождения технических весов критериев. По нормализованной матрице, формируемой функцией stem_T(R, Lim, L_b) вычисляются средние значения элементов по столбцам (кроме диагонально расположенных элементов матрицы):

 j



 

m
Cij
i 1

 



C

j j

  

/

m 1 ,

где m – количество критериев (количество строк в таблице).

 Затем из соотношений

i j



1 1

i j

и

m
i
i 1

 1 находятся веса:

i



1



i



/

 

m



m



j

 

.

 j1 

Функции имеют вид

stem _ s(R,Lim,L _ b) : T  normalize (stem _ T (R,Lim,L _ b),L _ b)

T T  fill _ vector(1,cols(T )) 1 cols(T ) 1

stem_  s ( R,Lim,L_b ) : s  stem _ s(R,Lim,L _ b)
1 s
length(s)   s
Функция оптимизации по глобальному критерию проводит оптимизацию по аддитивному кри-
m
терию Cgl  ci  i с использованием формально найденных весов и возвращает вектор значений i 1
критериев оптимальной системы. stem(R , Lim , L _ b) : SR  stem(R , Lim , L _ b)
Cols  normalize(SR ,L _ b)T
 s  stem _  s(R ,Lim,L _ b)
max_value  
for i  0..cols(Cols)  1

value   s  Cols i if value  max_value

max_value  value max_ind  i

(SRT ) max_ind

72 Научно-технический вестник информационных технологий, механики и оптики,
2012, № 4 (80)

К.А. Булыгин, В.Ю. Пинкевич, В.А. Богатырев

Пример поиска решений

Рассмотрим применение предложенных функций при оптимизации кластера. Зададим ограничения для критериев и вектор, указывающий, значения каких критериев при оптимизации надо максимизировать, а каких – минимизировать: P0:=0,9, U0:=10 c, Λ0:=0, C0:=100 у.е., век-
тор ограничений L:= stack (P0,U 0,0,C0) , вектор L _ b:=stack(1,3) , это означает, что минимизируем U и
C. Время пребывания будет рассчитываться при λ:=0,2 с. Сформируем матрицу RN, содержащую значения критериев и имена систем, которые представля-
ют собой перечисление числа узлов на каждом уровне в виде «a-b-c». Затем отделим критерии от имен и найдем область Парето, чтобы сузить поиск.
Pareto names filter
RN:= make_RN (L,L _ b)

R:= RN_to_R(RN )

N:= RN_to_N (RN )

R _ n:=normalize (R,L _ b)

N _ p:= pareto_names(R _ n,N )

R _ p:=filter _names(R,N ,N _ p)

R _ p – матрица критериев для решений из области Парето. По этой матрице и будем проводить оптимизацию методом STEM.
Решение получаем, применяя функцию stem(R _ p,L,L _ b) , при этом искомый вектор критериев

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

 0,999468

  

9,

065934 1, 5

  

.

 

51

 

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

Первый шаг – оптимизация по частным критериям: T:=stem _ T (R _ p,L,L _ b).

Для заданных исходных данных результат получаем в виде матрицы

P T C

1

8,554331 2, 25 100

T



 

0,

999997

 0,999999

8, 500444 8, 571429

2, 5 3

100

 

99 

 

0,

983566

10

1

33

 

.

Второй шаг – нахождение технических весов, используя функцию stem _ s(R _ p,L,L _ b) , в ре-

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

 0,149437 

 

0,161837

 

 0, 242768

 

0,

445958 

.

Третий шаг – оптимизация по глобальному критерию. Вспомогательная функция позволяет получить имя и параметры выбранной системы:

characteristics:= stem(R _ p,L,L _ b)

name:= crits_to_name(characteristics,R _ p,N _ p)

name  "3-6-3" В результате применения этой функции для рассматриваемого примера получаем вектор

 0,999468

characteristics



  

9,

065934

 

1,5 

.

 

51

 

Четвертый шаг – уточнение условий. Результат предъявляется ЛПР, которое может указать, по ка-

кому частному критерию его не устраивает решение, после чего на соответствующий критерий устанав-

Научно-технический вестник информационных технологий, механики и оптики, 2012, № 4 (80)

73

СРЕДСТВА ВЕКТОРНОЙ ОПТИМИЗАЦИИ СТРУКТУРЫ КЛАСТЕРОВ…

ливается ограничение. Допустим, ЛПР не удовлетворено средним временем пребывания заявок и требует, чтобы оно было меньше 9 с. Из результатов оптимизации по частным критериям видно, что есть возможность снижать это время почти до 8,5 с. Изменяя ограничение для времени пребывания U0:=9 c, получим:
name  "4-8-4",

 0,999959

characteristics



  

8, 77193 2

 .

 

68

 

Заключение

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

Литература

1. Ларичев О.И. Теория и методы принятия решений, а также Хроника событий в Волшебных странах: Учебник. – М.: Логос, 2002. – 392 с.
2. Воскобойников Ю.Е., Очков В.Ф. Программирование и решение задач в пакете Mathcad. – Новосибирск: НГАСУ, 2002. – 69 с.
3. Богатырев В.А., Булыгин К.А., Пинкевич В.Ю. Векторная оптимизация с программированием в среде Mathcad при комплексировании машин и агрегатов // Технико-технологические проблемы сервиса. – 2011. – № 4. – С. 48–54.
4. Богатырев В.А., Богатырев С.В. Критерии оптимальности многоустойчивых отказоустойчивых компьютерных систем // Научно-технический вестник СПбГУ ИТМО. – 2009. – № 5 (63). – С. 92–98.
5. Богатырев В.А. Оценка надежности и оптимальное резервирование кластерных компьютерных систем // Приборы и системы. Управление, контроль, диагностика. – 2006. – № 10. – С. 18–21.
6. Богатырев В.А. Оптимальное резервирование системы разнородных серверов // Приборы и системы. Управление, контроль, диагностика. – 2007. – № 12. – С. 30–36.
7. Богатырев В.А., Богатырев С.В. К анализу и оптимизации серверных систем кластерной архитектуры с балансировкой нагрузки // Приборы и системы. Управление, контроль, диагностика. – 2010. – № 2. – С. 4–9.
8. Богатырев В.А., Богатырев С.В., Богатырев А.В. Оптимизация кластера с ограниченной доступностью кластерных групп // Научно-технический вестник СПбГУ ИТМО. – 2011. – № 1 (71). – С. 63–66.
9. Богатырев В.А., Богатырев С.В. Объединение резервированных серверов в кластеры высоконадежной компьютерной системы // Информационные технологии. – 2009. – № 6. – С. 41–47.

Булыгин Кирилл Александрович Пинкевич Василий Юрьевич Богатырев Владимир Анатольевич

– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, студент, kirill.bulygin@gmail.com
– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, студент, vasiliy.pinkevich@yandex.ru
– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, доктор технических наук, профессор, vladimir.bogatyrev@gmail.com

74 Научно-технический вестник информационных технологий, механики и оптики,
2012, № 4 (80)