Анализ эффективности функционирования вычислительных систем в режиме обработки пакета задач
Найдены аналитические выражения для распределения вероятностей состояний вычислительных систем (ВС) в переходном режиме функционирования. Произведен анализ эффективности функционирования распределенных ВС (живучих и со структурной избыточностью) и осуществимости параллельного решения задач потока...
Saved in:
| Date: | 2009 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2009
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/8160 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Анализ эффективности функционирования вычислительных систем в режиме обработки пакета задач / В.Г. Хорошевский, В.А. Павский, К.В. Павский // Штучний інтелект. — 2009. — № 4. — С. 92-99. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859650168801984512 |
|---|---|
| author | Хорошевский, В.Г. Павский, В.А. Павский, К.В. |
| author_facet | Хорошевский, В.Г. Павский, В.А. Павский, К.В. |
| citation_txt | Анализ эффективности функционирования вычислительных систем в режиме обработки пакета задач / В.Г. Хорошевский, В.А. Павский, К.В. Павский // Штучний інтелект. — 2009. — № 4. — С. 92-99. — Бібліогр.: 9 назв. — рос. |
| collection | DSpace DC |
| description | Найдены аналитические выражения для распределения вероятностей состояний вычислительных
систем (ВС) в переходном режиме функционирования. Произведен анализ эффективности функционирования
распределенных ВС (живучих и со структурной избыточностью) и осуществимости параллельного решения
задач потока с отказами.
Знайдені аналітичні вирази для розподілу імовірностей станів обчислювальних систем (ОС) у перехідному
режимі функціонування. Здійснено аналіз ефективності функціонування розподілених ОС (живучих та зі
структурною надлишковістю) і здійсненності паралельного розв’язання задач течії з відмовами.
|
| first_indexed | 2025-12-07T13:32:32Z |
| format | Article |
| fulltext |
«Искусственный интеллект» 4’2009 92
2Х
УДК 681.324
В.Г. Хорошевский, В.А. Павский, К.В. Павский
Институт физики полупроводников СО РАН, г. Новосибирск, Россия
khor@isp.nsc.ru, pavvm@kemtipp.ru, pkv@isp.nsc.ru
Анализ эффективности функционирования
вычислительных систем в режиме обработки
пакета задач*
Найдены аналитические выражения для распределения вероятностей состояний вычислительных
систем (ВС) в переходном режиме функционирования. Произведен анализ эффективности функционирования
распределенных ВС (живучих и со структурной избыточностью) и осуществимости параллельного решения
задач потока с отказами.
Введение
По своей природе ВС – это стохастический объект, обслуживающий вероятност-
ные потоки задач со случайными параметрами. Естественно при изучении функцио-
нирования ВС применять аппарат теории массового обслуживания (ТМО) [1]. Однако в
этом случае рассмотрение переходного режима работы ВС, как правило, не обходится
без использования трудоемких численных методов [2-5].
В данной работе рассматривается марковская модель ТМО с отказами (в обозна-
чениях Кендалла M/M/1/n 6, 7), представляемая в виде системы дифференциальных
уравнений. Найдены аналитические выражения для распределения вероятностей
состояний ВС в переходном режиме. Произведены расчеты показателей эффек-
тивности функционирования распределенных живучих ВС и систем со структурной
избыточностью 2, 3. Выделены две группы показателей: надежности (живучести)
ВС и осуществимости параллельного решения задач 2, 3, 8.
Формулировка модели
На вычислительную систему [3] поступает пуассоновский поток простых (по-
следовательных) задач с интенсивностью , из которых формируется пакет. Количе-
ство задач в пакете ограничивается числом n элементарных машин ВС, выделяемых
для решения поступающих задач. Если пакет сформирован, то очередная задача
получает отказ и считается потерянной. Как только ВС освобождается, она присту-
пает к обслуживанию пакета (пусть даже и не до конца сформированного) и начина-
ется формирование очередного пакета. Время решения каждой задачи в системе
является случайной величиной, распределенной по экспоненциальному закону с ин-
тенсивностью решения . По окончании решения всех задач ВС переходит к реше-
нию задач из очередного пакета. Требуется проанализировать эффективность работы
системы.
* Работа выполнена при поддержке РФФИ (гранты № 07-07-00142, № 09-07-00185, № 08-08-00300),
Совета по грантам Президента РФ (грант № НШ-2121.2008.9).
Анализ эффективности функционирования вычислительных систем…
«Штучний інтелект» 4’2009 93
2Х
Пусть )(tPk – вероятность того, что в момент времени ,0t пакет состоит
из k нерешенных задач, причем 0 (0) 1P (т.е. в начальный момент времени пакет
был пустым); },...,1,0{0 nEk n .
Используя методы ТМО 6, получаем систему дифференциальных уравнений
),()()(
, ),()()()(
),()()(
1
1
11
1
00
tPtPtP
dt
d
EktPtPtP
dt
d
tPtPtP
dt
d
nnn
n
kkk
n
k
k
(1)
с начальными условиями
1)0(0 P , 0)0( kP . (2)
Условие нормировки, являющееся следствием системы уравнений (1), имеет вид:
1)(
0
n
k
k tP , ,0t . (3)
Преобразуем первое уравнение системы (1) с учетом условия (3):
)()()( 00 tPtP
dt
d .
Решение этого уравнения при начальных условиях (2) записывается в виде
tetP )(
0 )(
.
Аналогично, при 1k , получаем
tt eettP )(
2
)(
2
21 )()()(
)(
.
Для применения метода математической индукции решим уравнение (1) при 2k ,
tt etetP )(
2
2
)(
3
2
3
2
2 )()()(
)(
tet )(
23
)(!2
.
Предположим, что для некоторого 1 nk справедлива формула
t
k
k
k
k
k etP )(
11 )()(
)(
1
1
1
1
)(
)(!)(!
k
r
rk
r
k
kk
t
r
t
k
te
.(4)
Докажем ее справедливость для 1k , имеем
)(!)()(
)(
1
1
)(
1
)()(
1
k
teeCetP
kk
k
k
t
k
k
tt
k
dt
r
tk
r
rk
r
k 1
1
1)(!
.
Хорошевский В.Г., Павский В.А., Павский К.В.
«Искусственный интеллект» 4’2009 94
2Х
Раскрывая скобки и интегрируя последнее, получим
)()!1()()(
)(
12
1
1
)(
2
1
)(
1
k
tteCetP
kk
k
k
t
k
k
t
k
1
1
2
1
1
)()!1(
k
r
rk
r
k
r
t
.
Полагая 0t , находим 2
1
)(
k
k
C
.
Подставляя найденное значение константы интегрирования C в последнее ра-
венство, определяющее вероятность )(1 tPk , получим
1
1
)(
2
1
2
1
)(
1 )()()(
)( k
k
t
k
k
k
k
t
k
teetP
1
1
2
1
1
12
)()!1()()!1(
k
r
rk
r
k
kk
r
t
k
t
или
.
)(!)()!1()()(
)(
1
1)1(
1
12
)()(
2
1
2
1
1
k
r
rk
r
k
kk
tt
k
k
k
k
k r
t
k
teetP
Таким образом, формула (4) доказана.
Легко заметить, что (см. (1))
dttPeCetP n
tt
n
)()( 1
. (5)
Подставляя )(1 tPn (формулу (4) при 1 nk ) в (5), получаем
n
n
t
n
n
tt
n eeCetP
)()(
)(
1
)(
1
dt
r
t
n
te
n
r
rn
r
n
nn
t 2
1
1
1
)(
)(!)()!1(
.
Представим правую часть последнего равенства в виде суммы интегралов
dtet
n
eeCetP tn
n
t
n
n
t
n
n
t
n
1
11
)()!1()()(
)(
2
1 )(!
1n
r
tr
rn
n dtet
r
.
Далее замечаем, что
2
1 1
1
1
1
1
1
1
)!(
!
)(!
1
)!1(
)!1(
)()!1()()(
)(
n
r
r
k
k
kr
rt
rn
n
n
k
k
kn
nt
n
t
n
n
t
n
n
t
n
kr
trte
rkn
tn
te
n
eeCetP
. (6)
Анализ эффективности функционирования вычислительных систем…
«Штучний інтелект» 4’2009 95
2Х
Найдем значение произвольной постоянной в (6). При 0t имеем:
2
1
11
)()()(
0
n
r
r
n
n
n
n
n
n
C
.
Члены, стоящие под знаком суммы, образуют геометрическую прогрессию.
Следовательно,
2
12
1
)(
n
nn
r
r
,
и находим, что 0C .
Окончательно получаем, что
t
n
t
n
n
n
n
n e
n
etP )()(
1
)()!1()()(
)(
2
1
)(11
1
1
1
)(!)!1(
)!1(
n
r
rn
r
tnn
k
k
kn
n
r
te
kn
tnt
(7)
2
1 1
)(1
)!()(
n
r
r
k
rnk
kr
tn
kr
te
.
Иллюстрация к характеру изменения значений вероятностей )(tPk от времени t
представлена на рис. 1.
Рисунок 1 – Зависимость вероятностей )(tPk , 3,2,1,0k , от времени t при
1,0 1/ч., 01,0 1/ч.
Из рис. 1 видно, что стационарный режим функционирования ВС при решении
задач наступает через достаточно длительный промежуток времени, 45t ч. Следо-
вательно, для вычислительных систем, функционирующих в реальных условиях,
пренебрежение зависимостью показателей эффективности от времени недопустимо.
Хорошевский В.Г., Павский В.А., Павский К.В.
«Искусственный интеллект» 4’2009 96
2Х
Система M/M/1/n всегда эргодична, следовательно, стационарный режим
( 0)(lim
kkt
PtP , 0)('lim
tPkt
) всегда существует, так что
0P , 1)(
k
k
kP
, 1
1
nEk , n
n
nP
)(
. (8)
Как следует из (3), вероятности 0, ,n
kP k E составляют ряд распределения и,
следовательно, представляют базис, через который выражаются показатели, харак-
теризующие эффективность процесса решения (осуществимость решения 3, 8) за-
дач на ВС в момент времени t, ,0t . Рассмотрим те из них, которые можно
использовать при экспресс-анализе функционирования ВС:
1) вероятность того, что пакет не пуст
01 1 PP ;
2) вероятность отказа в обслуживании задачи
nотк PP ;
3) средний объем пакета
)ln(ln
ln
откPn , (9)
где x – целая часть числа x ;
4) среднее число задач в пакете
n
k
kn
k
nkM
1
11
1
2 )()(
; (10)
5) дисперсию числа задач в пакете
22
11
1
2
2)(
MnkD
nkn
k
. (11)
Вычисление показателей надежности распределенных ВС
Считаем, что восстановительные операции в ВС осуществляет восстанавли-
вающая система, состоящая из m однородных устройств (ВУ), nEm 1 . Это либо спе-
циальные аппараты, либо микропрограммные устройства, либо программы, либо
композиции из отмеченных средств. Производительность восстанавливающей сис-
темы определяется и числом m, и интенсивностью µ восстановления отказавших ЭМ
одним ВУ 3.
Показатели надежности распределенных ВС рассчитаем при следующих усло-
виях: а) ВС является высокопроизводительной, т.е. общее число N элементарных
машин (ЭМ) достаточно большое [3]; б) режим функционирования ВС установив-
шийся; в) в случае выхода ЭМ из строя, она сразу поступает на восстановление.
Обозначим через λ интенсивность отказов одной ЭМ, а через μ – интенсивность
восстановления отказавших ЭМ одним ВУ.
1. Вычислительные системы со структурной избыточностью представляют
программно настроенную конфигурацию 3, в которой:
а) выделена основная подсистема из n ЭМ и подсистема из (N – n) ЭМ, подчи-
ненная основной и составляющая структурную избыточность;
Анализ эффективности функционирования вычислительных систем…
«Штучний інтелект» 4’2009 97
2Х
б) основная подсистема предназначена для решения сложных задач, представ-
ленных параллельными программами из n ветвей, а подчиненная система – для
решения фоновых задач;
в) функции отказавшей ЭМ основной подсистемы берет на себя любая исправ-
ная ЭМ структурной избыточности.
Очевидно, что для решения сложных задач требуются ВС с массовым паралле-
лизмом (параллельные программы с большим числом ветвей). Можно считать, что
)( nNn , то есть производительность основной подсистемы близка к суммарной.
Если в основной подсистеме ВС со структурной избыточностью элементарная
машина выходит из строя, то она локализуется, ее функции передаются свободной
ЭМ структурной избыточности, и с помощью реконфигуратора порождается новая
конфигурация из n ЭМ. Требуется определить величину ( )N n структурной избы-
точности и вероятность R безотказной работы основной подсистемы ВС.
Поскольку режим работы ВС установившийся, то случайный процесс отказов
ЭМ ВС (как следует из асимптотических свойств процессов восстановления 5, 9)
является пуассоновским. Следовательно, вероятность ( )kV того, что за время
произойдет k отказов, равна
a
k
k e
k
aV
!
)()( , NEk 0 ,
где ))exp(1( Na – среднее число ЭМ, отказавших за время , T,0 ,
T . Принимая во внимание параметры модели ВС, полагаем, что интенсивность
входящего потока
Na
0
lim , а интенсивность обслуживания , тогда для
вероятности отказа ВС получаем
( )N n
отк
NP
N
,
отсюда вероятность безотказной работы основной подсистемы
( )1 /( ) N nR N N . (12)
Рисунок 2 – Зависимость вероятности R безотказной работы ВС от числа ЭМ
структурной избыточности, 20;10;5;2)( nN , 10 1/ч.
Хорошевский В.Г., Павский В.А., Павский К.В.
«Искусственный интеллект» 4’2009 98
2Х
Зависимость )(NRR от числа 64 1010 N ЭМ системы при 410 1/ч.,
10 1/ч. и числа ЭМ структурной избыточности 20;10 ;5 ;2)( nN , иллюстриру-
ется рис. 2.
Из рисунка видно, что при 10)( nN вероятность 63,0R .
Расчеты показывают, что при 5102 N , 410/1 ч., 10 1/ч., вероятность
98,0R . Следовательно, можно считать, что для большемасштабных ВС число
( )N n ЭМ структурной избыточности не превосходит 0,02%.
2. Под живучей ВС понимается программно настроенная конфигурация из N
ЭМ 2, в которой
а) указано минимально допустимое число n работоспособных ЭМ, обеспечи-
вающих производительность системы не менее требуемой;
б) реализована возможность решения сложных задач, представленных адапти-
рующимися параллельными программами;
в) отказы любых ЭМ и восстановления отказавших приводят только к увеличе-
нию или уменьшению времени реализации параллельной программы.
Вычислительное ядро в живучей ВС составляют все n исправных ЭМ, а число
избыточных – переменное от 0 до )( nN .
Если во время решения сложной задачи ЭМ выходит из строя, то она покидает
вычислительное ядро и берется на учет реконфигуратором, который в свою очередь
передает ее в восстанавливающую систему (где ЭМ ремонтируется одним из сво-
бодных ВУ). При функционировании большемасштабных реконфигурируемых ВС
используются виртуальные ВУ, и ремонт отказавших ЭМ сводится к их замене на
машины из резерва 4. В этом случае интенсивность воспринимается как среднее
число ЭМ резерва, включаемых в единицу времени одним ВУ в состав ВС.
Следовательно, для живучих систем влияние числа m ВУ на интенсивность
восстановления ЭМ может оказаться существенным. Найдем число m ВУ, при кото-
ром время ожидания ЭМ в очереди на восстановление будет пренебрежимо малым
по сравнению с временем восстановления.
Пусть откP – вероятность отказа одной ЭМ в стационарном режиме работы.
Если восстанавливающая система состоит из m ВУ, то среднее время ремонта одной
ЭМ равно )/(1 m 9. Из (12) получаем
( )( 1)N n
откm N P . (13)
Формула (13) подтверждает, что чем меньше времени тратится на ремонт ЭМ, тем
меньше требуется восстанавливающих устройств для вычислительной системы. В табл.
1, 2 представлены количества ВУ, рассчитанные по формуле (13) при 10)( nN ,
410 1/ч. соответственно для 99,0 ;95,0R .
Таблица 1 Таблица 2
N
1 10 100
N
1 10 100
5 1 1 7 5 1 2 12
10- 1 1 4 10 1 1 6
Анализ эффективности функционирования вычислительных систем…
«Штучний інтелект» 4’2009 99
2Х
Из таблиц следует, что с вероятностью, близкой к единице ( 0,95) для больше-
масштабных живучих ВС (при надежности ЭМ не ниже двух порядков относительно
числа N ЭМ в ВС), число ВУ не превосходит 0,012% от N.
Заключение
Построена модель ВС со структурной избыточностью, функционирование ко-
торой осуществляется в режиме обработки пакета задач. Получены аналитические
выражения для расчета функции надежности ВС (вероятности безотказной работы
системы на временном промежутке).
Модель дает возможность не только анализировать качество функционирова-
ния ВС, но и вычислять значения ее параметров для достижения заданного уровня
надежности.
Литература
1. Вишневский В.М. Теоретические основы проектирования компьютерных сетей / Вишневский В.М. –
Москва : Техносфера, 2003. – 512 с.
2. Евреинов Э.В. Однородные вычислительные системы / Э.В. Евреинов, В.Г. Хорошевский. – Новоси-
бирск : Наука, 1978. – 319 с.
3. Хорошевский В.Г. Архитектура вычислительных систем / Хорошевский В.Г. – М. : МГТУ им. Н.Э. Бау-
мана, 2008. – 520 с.
4. Игнатьев М.Б. Надежность однородных вычислительных систем / М.Б. Игнатьев, Б.С. Флейшман,
В.Г. Хорошевский [и др.] // Вычислительные системы. – Вып. 48. – Новосибирск : Наука, 1972. – С. 16-47.
5. Гнеденко Б.В. Математические методы в теории надежности / Б.В. Гнеденко, Ю.К. Беляев, А.Д. Со-
ловьев. – М. : Наука, 1965. – 524 с.
6. Клейнрок Л. Вычислительные системы с очередями / Клейнрок Л. – М. : Мир, 1979. – 600 с.
7. Клейнрок Л. Теория массового обслуживания / Клейнрок Л. – М. : Машиностроение, 1979. – 432 с.
8. Павский В.А. Вычисление показателей живучести распределенных вычислительных систем и осуществи-
мости решения задач / В.А. Павский, К.В. Павский, В.Г. Хорошевский // Искусственный интеллект. –
2006. – № 4. – С. 28-34.
9. Кокс Д.Р. Теория восстановления / Д.Р. Кокс, В.Л. Смит. – М. : Сов. радио, 1967. – 312 с.
В.Г. Хорошевський, В.О. Павський, К.В. Павський
Аналіз ефективності функціонування обчислювальних систем у режимі обробки пакета задач
Знайдені аналітичні вирази для розподілу імовірностей станів обчислювальних систем (ОС) у перехідному
режимі функціонування. Здійснено аналіз ефективності функціонування розподілених ОС (живучих та зі
структурною надлишковістю) і здійсненності паралельного розв’язання задач течії з відмовами.
Статья поступила в редакцию 10.06.2009.
|
| id | nasplib_isofts_kiev_ua-123456789-8160 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-12-07T13:32:32Z |
| publishDate | 2009 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Хорошевский, В.Г. Павский, В.А. Павский, К.В. 2010-05-14T07:52:58Z 2010-05-14T07:52:58Z 2009 Анализ эффективности функционирования вычислительных систем в режиме обработки пакета задач / В.Г. Хорошевский, В.А. Павский, К.В. Павский // Штучний інтелект. — 2009. — № 4. — С. 92-99. — Бібліогр.: 9 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/8160 681.324 Найдены аналитические выражения для распределения вероятностей состояний вычислительных систем (ВС) в переходном режиме функционирования. Произведен анализ эффективности функционирования распределенных ВС (живучих и со структурной избыточностью) и осуществимости параллельного решения задач потока с отказами. Знайдені аналітичні вирази для розподілу імовірностей станів обчислювальних систем (ОС) у перехідному режимі функціонування. Здійснено аналіз ефективності функціонування розподілених ОС (живучих та зі структурною надлишковістю) і здійсненності паралельного розв’язання задач течії з відмовами. Работа выполнена при поддержке РФФИ (гранты № 07-07-00142, № 09-07-00185, № 08-08-00300), Совета по грантам Президента РФ (грант № НШ-2121.2008.9). ru Інститут проблем штучного інтелекту МОН України та НАН України Интеллектуальный анализ данных Анализ эффективности функционирования вычислительных систем в режиме обработки пакета задач Аналіз ефективності функціонування обчислювальних систем у режимі обробки пакета задач Article published earlier |
| spellingShingle | Анализ эффективности функционирования вычислительных систем в режиме обработки пакета задач Хорошевский, В.Г. Павский, В.А. Павский, К.В. Интеллектуальный анализ данных |
| title | Анализ эффективности функционирования вычислительных систем в режиме обработки пакета задач |
| title_alt | Аналіз ефективності функціонування обчислювальних систем у режимі обробки пакета задач |
| title_full | Анализ эффективности функционирования вычислительных систем в режиме обработки пакета задач |
| title_fullStr | Анализ эффективности функционирования вычислительных систем в режиме обработки пакета задач |
| title_full_unstemmed | Анализ эффективности функционирования вычислительных систем в режиме обработки пакета задач |
| title_short | Анализ эффективности функционирования вычислительных систем в режиме обработки пакета задач |
| title_sort | анализ эффективности функционирования вычислительных систем в режиме обработки пакета задач |
| topic | Интеллектуальный анализ данных |
| topic_facet | Интеллектуальный анализ данных |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/8160 |
| work_keys_str_mv | AT horoševskiivg analizéffektivnostifunkcionirovaniâvyčislitelʹnyhsistemvrežimeobrabotkipaketazadač AT pavskiiva analizéffektivnostifunkcionirovaniâvyčislitelʹnyhsistemvrežimeobrabotkipaketazadač AT pavskiikv analizéffektivnostifunkcionirovaniâvyčislitelʹnyhsistemvrežimeobrabotkipaketazadač AT horoševskiivg analízefektivnostífunkcíonuvannâobčislûvalʹnihsistemurežimíobrobkipaketazadač AT pavskiiva analízefektivnostífunkcíonuvannâobčislûvalʹnihsistemurežimíobrobkipaketazadač AT pavskiikv analízefektivnostífunkcíonuvannâobčislûvalʹnihsistemurežimíobrobkipaketazadač |