Расчет показателей осуществимости решения задач набора на распределенных вычислительных системах
Предлагается подход к расчету показателей осуществимости решения задач набора, характеризующих функционирование ВС в среднем. В его основе лежат вероятностные процессы теории массового обслуживания. Полученные формулы обладают наглядностью и могут быть использованы при ручном счете. Пропонується п...
Saved in:
| Date: | 2008 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2008
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/7659 |
| 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: | Расчет показателей осуществимости решения задач набора на распределенных вычислительных системах / В.А. Павский, К.В. Павский // Штучний інтелект. — 2008. — № 4. — С. 682-685. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859715609590235136 |
|---|---|
| author | Павский, В.А. Павский, К.В. |
| author_facet | Павский, В.А. Павский, К.В. |
| citation_txt | Расчет показателей осуществимости решения задач набора на распределенных вычислительных системах / В.А. Павский, К.В. Павский // Штучний інтелект. — 2008. — № 4. — С. 682-685. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| description | Предлагается подход к расчету показателей осуществимости решения задач набора, характеризующих
функционирование ВС в среднем. В его основе лежат вероятностные процессы теории массового
обслуживания. Полученные формулы обладают наглядностью и могут быть использованы при ручном счете.
Пропонується підхід до розрахунку показників здійсненності розв’язання задач набору, що
характеризують функціонування ОС в середньому. У його основі лежать процеси вірогідності теорії
масового обслуговування. Одержані формули володіють наочністю і можуть бути використані при
ручному рахунку.
The approach to calculation of realizability parameters of set solving problems is offered. The approach is
based on the probabilistic processes of queueing theory. Obtained formulas are obvious and can be used for
hand computations.
|
| first_indexed | 2025-12-01T08:00:04Z |
| format | Article |
| fulltext |
«Искусственный интеллект» 4’2008 682
8П
УДК 681.324
В.А. Павский, К.В. Павский
Кемеровский технологический институт, Кемерово, Россия
pavvm@kemtipp.ru
Институт физики полупроводников СО РАН, Новосибирск, Россия
pkv@isp.nsc.ru
Расчет показателей осуществимости
решения задач набора на распределенных
вычислительных системах*
Предлагается подход к расчету показателей осуществимости решения задач набора, характеризующих
функционирование ВС в среднем. В его основе лежат вероятностные процессы теории массового
обслуживания. Полученные формулы обладают наглядностью и могут быть использованы при ручном счете.
Введение
При анализе эффективности функционирования вычислительных систем (ВС),
как сосредоточенных, так и распределенных, используются показатели осуществи-
мости 1, 2. В зависимости от сложности задач и характера их поступления выделяют
следующие режимы работы ВС:
решение сложной задачи;
обработка набора задач;
обслуживание потока задач.
Целью работы является разработка подхода к расчету математических
ожиданий и дисперсий показателей осуществимости решения задач набора.
Постановка задачи
Рассмотрим решение i сложных задач набора на ВС. Сложная задача (пред-
ставлена параллельной программой [2]) решается на всем выделенном ресурсе [3].
Пусть выделенный ресурс составляет n ЭМ, тогда интенсивность решения
задачи будем считать равной n , где – интенсивность решения задачи на одной ЭМ
(оцениваются потенциальные возможности ВС [1], [2]).
Так как задачи сложные, то решаются последовательно, поскольку каждая из
них решается на всех ЭМ. Предполагается, что поток событий для параметра
пуассоновский.
Требуется вычислить математическое ожидание Ai(t) – числа задач, находящихся в
системе [2], и соответствующую дисперсию Di(t) в момент времени t[0, ) при на-
чальных условиях:
iAi )0( , 0)0( iD , ,...2,1,00 Ei (1)
*Работа выполнена при поддержке РФФИ (гранты №07-07-00142, №08-08-00300) и Совета по
грантам Президента РФ (грант №НШ-2121.2008.9)
Расчет показателей осуществимости решения задач набора…
«Штучний інтелект» 4’2008 683
8П
Расчет показателей осуществимости
решения задач набора на ВС
Обозначим через )(tPk вероятность того, что к моменту времени t в ВС нахо-
дится k задач (включая обслуживаемую), iEk 0 .
В такой постановке имеем систему [3]
),()(' );()('
; ),()()('
10
1
11
tPntPtPntP
EktPntPntP
ii
i
kkk
(2)
с начальными условиями
1)0( iP , 0)0( kP , ik .
Условие нормировки, являющееся следствием системы уравнений, имеет вид
1)(
0
i
k
k tP , ),0[ t .
Вводя производящую функцию
n
k
k
k tPztzF
0
)(),( ,
систему (2) приводим к уравнению
))(),(()1(),(
0 tPtzFzn
t
tzFz
, izzF )0,( , (3)
из которого, после необходимых преобразований, получаем систему
)(2)()()(
)),(1()(
2
0
tAntAtAtD
dt
d
tPntA
dt
d
iiii
i
(4)
с начальными условиями (1).
Вероятность )(0 tP неизвестна, однако, если число i задач велико, то можно
считать, что i , то 0)(0 tP , ),0[ t . Система (4) имеет очевидное решение
),/( ,)(
,)(
nittntD
tnitA
i
i (5)
где )(tAi – среднее число задач, оставшихся в системе к моменту времени t.
Из (5) следует, что среднее время, необходимое для решения i сложных задач
набора, tср = i / (n ) при стандартном отклонении i . Например, при выделенном
ресурсе n = 100 ЭМ, время, необходимое для решения набора из 400 задач, при = 0,1 1/ч
составит tср = 400 / (100 0,1)=40 ч. С учетом отклонения, 20400 , получаем
tср = 20 / (100 0,1) = 2 ч. Таким образом, для среднего времени решения набора задач с
учетом стандартного отклонения имеем: 240~ cpt ч.
Замечание. Точное решение системы (4) слишком громоздко. Именно поэтому
решение (5), при указанных упрощениях, оправдано [4]. Приведем решение системы (2).
Павский В.А., Павский К.В.
«Искусственный интеллект» 4’2008 684
8П
Применяя преобразование Лапласа ( dttfesf ts
0
)()(~ , где )(tf – функция ограни-
ченного изменения 5 к уравнению (3), получим
))(~),(~()1(),(~
0 sPszFznzszFsz i , 0)Re( s (6)
Или
)1(
)(~)1(
),(~ 0
1
znzs
sPznzszF
i
. (7)
Так как в знаменателе 1)/(|| nsnz , то применяя теорему Руше 5, находим
insnssP )]/([)(~ 1
0 . (8)
Подставляя правую часть формулы (8) в (7) и разделив полученный числитель
на знаменатель, будем иметь
k
i
k
kii nsnznsnsszF )]/([)]/([),(~ 1
0
1
. (9)
Взяв обратное преобразование Лапласа, предварительно разложив правую часть (9)
на простейшие множители, получим
1
01
!/)()exp()!/()()exp(1),(
i
k
kki
i
k
ki ktnztnkitntntzF
Учитывая, что
),0(
!
1)( tF
zk
tP k
k
k
,
находим искомое решение
1
0
0 !
)()exp(1)(
i
k
k
k
tntntP
,
)exp(
)!(
)()( tn
ki
tntP
ki
k
, iEk 1 .
Таким образом,
i
k
i
ki
i
i
k
ki
i
tA
ik
tnktntD
ki
tnktntA
1
22
1
.))((
)!(
)()exp()(
,
)!(
)()exp()(
Погрешность решения в сравнении с (5) для )(tAi
1 !
)()()exp()(
ik
k
i k
tniktnt
.
Заметим, что )(0 tP представлена распределением Эрланга порядка i, для
которого
)/( niM , 2)/( niD ,
где – полное время нахождения последней обслуженной задачи в наборе, что вполне
согласуется с решением (5).
Расчет показателей осуществимости решения задач набора…
«Штучний інтелект» 4’2008 685
8П
Заключение
Предложен подход к расчету показателей осуществимости решения задач
набора, характеризующих функционирование ВС в среднем. В его основе лежат
вероятностные процессы теории массового обслуживания. Предложенный подход
позволяет вычислять моменты (центральные и начальные) любых порядков, не
вычисляя вероятности состояний системы, что особенно важно для анализа функцио-
нирования многомашинных ВС. Полученные формулы обладают наглядностью и
могут быть использованы при ручном счете.
Литература
1. Евреинов Э.В., Хорошевский В.Г. Однородные вычислительные системы. – Новосибирск: Наука, 1978.
2. Хорошевский В.Г. Архитектура вычислительных систем. – М.: МГТУ им. Баумана, 2005. – 512 с.
3. Павский В.А., Павский К.В., Хорошевский В.Г. Вычисление показателей живучести распределен-
ных вычислительных систем и осуществимости решения задач // Искусственный интеллект. –
2006. – № 4. – С. 28-34.
4. Павский В.А., Хорошевский В.Г., Павский К.В. Вычисление показателей осуществимости решения
задач на вычислительных системах // Материалы VII Междунар. науч.-техн. конф. «Искусственный
интеллект. Интеллектуальные и многопроцессорные системы – 2006». – Кацивели (Крым, Украина). –
Изд-во ТРТУ, 2006. – Т. 2. – С. 14-17.
5. Клейнрок Л. Вычислительные системы с очередями. – М.: Мир, 1979. – 600 с.
В.О. Павський, К.В. Павський
Розрахунок показників здійсненності розв’язання задач набору на розподілених
обчислювальних системах
Пропонується підхід до розрахунку показників здійсненності розв’язання задач набору, що
характеризують функціонування ОС в середньому. У його основі лежать процеси вірогідності теорії
масового обслуговування. Одержані формули володіють наочністю і можуть бути використані при
ручному рахунку.
Valery A. Pavsky, Kirill V. Pavsky
Calculation of Realizability Parameters of Set Solving Problems on Distributed Computer systems
The approach to calculation of realizability parameters of set solving problems is offered. The approach is
based on the probabilistic processes of queueing theory. Obtained formulas are obvious and can be used for
hand computations.
Статья поступила в редакцию 21.07.2008.
|
| id | nasplib_isofts_kiev_ua-123456789-7659 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-12-01T08:00:04Z |
| publishDate | 2008 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Павский, В.А. Павский, К.В. 2010-04-06T12:59:47Z 2010-04-06T12:59:47Z 2008 Расчет показателей осуществимости решения задач набора на распределенных вычислительных системах / В.А. Павский, К.В. Павский // Штучний інтелект. — 2008. — № 4. — С. 682-685. — Бібліогр.: 5 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/7659 681.324 Предлагается подход к расчету показателей осуществимости решения задач набора, характеризующих функционирование ВС в среднем. В его основе лежат вероятностные процессы теории массового обслуживания. Полученные формулы обладают наглядностью и могут быть использованы при ручном счете. Пропонується підхід до розрахунку показників здійсненності розв’язання задач набору, що характеризують функціонування ОС в середньому. У його основі лежать процеси вірогідності теорії масового обслуговування. Одержані формули володіють наочністю і можуть бути використані при ручному рахунку. The approach to calculation of realizability parameters of set solving problems is offered. The approach is based on the probabilistic processes of queueing theory. Obtained formulas are obvious and can be used for hand computations. Работа выполнена при поддержке РФФИ (гранты №07-07-00142, №08-08-00300) и Совета по грантам Президента РФ (грант №НШ-2121.2008.9) ru Інститут проблем штучного інтелекту МОН України та НАН України Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем Расчет показателей осуществимости решения задач набора на распределенных вычислительных системах Розрахунок показників здійсненності розв’язання задач набору на розподілених обчислювальних системах Calculation of Realizability Parameters of Set Solving Problems on Distributed Computer systems Article published earlier |
| spellingShingle | Расчет показателей осуществимости решения задач набора на распределенных вычислительных системах Павский, В.А. Павский, К.В. Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем |
| title | Расчет показателей осуществимости решения задач набора на распределенных вычислительных системах |
| title_alt | Розрахунок показників здійсненності розв’язання задач набору на розподілених обчислювальних системах Calculation of Realizability Parameters of Set Solving Problems on Distributed Computer systems |
| title_full | Расчет показателей осуществимости решения задач набора на распределенных вычислительных системах |
| title_fullStr | Расчет показателей осуществимости решения задач набора на распределенных вычислительных системах |
| title_full_unstemmed | Расчет показателей осуществимости решения задач набора на распределенных вычислительных системах |
| title_short | Расчет показателей осуществимости решения задач набора на распределенных вычислительных системах |
| title_sort | расчет показателей осуществимости решения задач набора на распределенных вычислительных системах |
| topic | Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем |
| topic_facet | Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/7659 |
| work_keys_str_mv | AT pavskiiva rasčetpokazateleiosuŝestvimostirešeniâzadačnaboranaraspredelennyhvyčislitelʹnyhsistemah AT pavskiikv rasčetpokazateleiosuŝestvimostirešeniâzadačnaboranaraspredelennyhvyčislitelʹnyhsistemah AT pavskiiva rozrahunokpokaznikívzdíisnennostírozvâzannâzadačnaborunarozpodílenihobčislûvalʹnihsistemah AT pavskiikv rozrahunokpokaznikívzdíisnennostírozvâzannâzadačnaborunarozpodílenihobčislûvalʹnihsistemah AT pavskiiva calculationofrealizabilityparametersofsetsolvingproblemsondistributedcomputersystems AT pavskiikv calculationofrealizabilityparametersofsetsolvingproblemsondistributedcomputersystems |