WWW.KNIGA.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Книги, пособия, учебники, издания, публикации

 

Pages:     | 1 || 3 | 4 |   ...   | 10 |

«INTERNATIONAL CONGRESS ON COMPUTER SCIENCE: INFORMATION SYSTEMS AND TECHNOLOGIES Proceedings of the International Congress Republic of Belarus, Minsk, October' 31 – ...»

-- [ Страница 2 ] --

Переходы цепи t, t 0, которые не приводят к окончанию обслуживания, задаются субгенератором S размера M M. Интенсивности переходов в поглощающее состояние описываются вектором S0 = Se. Среднее время обслуживания задается формулой b1 = ( S ) 1 e. Более подробную информацию о распределении фазового типа можно найти в [4, 5].

Если в момент прихода запроса все приборы заняты и число запросов в буфере равно i, i = 0, R N 1, то этот запрос с вероятностью qi покидает систему, а с дополнительной вероятностью становится в очередь.

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

ПРОЦЕСС ИЗМЕНЕНИЯ СОСТОЯНИЙ СИСТЕМЫ. СТАЦИОНАРНОЕ

РАСПРЕДЕЛЕНИЕ ЧИСЛА ЗАПРОСОВ В СИСТЕМЕ

Пусть it, it = 0, R, – число запросов в системе, t, t = 0,W, – состояние управляющего процесса МАР-потока поступления запросов, t( l ), t( l ) = 0, min{it, N }, – число приборов, в которых процесс обслуживания находится на фазе l в момент времени t, t 0, l = 1, M. Процесс t = {it, t, t(1),, t( M ) }, t 0, является регулярной неприводимой цепью Маркова с непрерывным временем.

Перенумеруем состояния цепи t в лексикографическом порядке. Множество состояний, имеющих значение (i, ) двух первых компонент цепи, будем называть макросостоянием (i, ). Пусть Q – генератор цепи Маркова t, t 0, сформированный из блоков Qi, j, состоящих из матриц (Qi, j ), интенсивностей переходов цепи t, t 0, из макросостояния (i, ) в макросостояние ( j, ),, = 0,W. Диагональные элементы матрицы Qi,i отрицательны, и их модули определяют интенсивность выхода из соответствующего состояния цепи Маркова.

Лемма 1. Генератор Q = (Qi, j )i, j 0 имеет блочно-трехдиагональную структуру, где ненулевые блоки имеют вид:

Здесь I – единичная матрица, O – нулевая матрица, в случае необходимости порядок матрицы указывается при помощи нижнего индекса; W = W + 1;

K = C N +M 1 ; i = (i N ); и означают операции Кронекеровых произведений и Детальное описание матриц Pi (), Ai ( N, S ) и LN i ( N, S ) и рекурсивный алгоритм для их вычислений представлены в работах [6, 7].

Доказательство леммы опирается на анализ переходов цепи Маркова t,t 0, за бесконечно малый интервал времени с последующей группировкой интенсивностей соответствующих переходов в блоки матрицы Q.

Так как цепь Маркова t = {it, t, t(1),, t( M ) }, t 0, регулярная и неприводимая, а также имеет конечное пространство состояний, то существуют следующие пределы (стационарные вероятности):

Перенумеруем стационарные вероятности цепи t в лексикографическом порядке и сформируем из них векторы (i, ), состоящие из вероятностей (i,, (1),, ( M ) ), записанных в лексикографическом порядке по компонентам ( (1),, ( M ) ), и векторы i = ( (i, 0), (i,1),, (i, W )), i = 0, R.

Известно, что вектор-строка (0,, R ) – единственное решение системы линейных алгебраических уравнений В случае, когда размерность системы, приведенной выше, невелика, ее легко решить с помощью компьютера стандартными методами. В противном случае может быть использован специальный устойчивый алгоритм, приведенный в теореме 1.

Теорема 1. Векторы i, i = 0, R, вычисляются следующим образом:

где матрицы Fi вычисляются рекуррентно:

матрицы Ti, i = 0, R 1, вычисляются с помощью обратной рекурсии:

при начальном условии TR 1 = QR 1,R (QR, R ) 1, а вектор 0 является единственным решением следующей системы:

ХАРАКТЕРИСТИКИ ПРОИЗВОДИТЕЛЬНОСТИ СИСТЕМЫ

Среднее число запросов в системе L = ii e.

Интенсивность выходящего потока обслуженных запросов Вероятность потери запроса на входе в систему из-за заполненности буфера Вероятность ухода запроса на входе в систему из-за нежелания ожидать Вероятность потери произвольного запроса Вероятность того, что произвольный запрос попадет в буфер и уйдет из него изза нетерпеливости P ( imploss) = P( loss) P( ent loss) P ( escloss).

ЗАКЛЮЧЕНИЕ

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

ЛИТЕРАТУРА

1. Heyman, D. P. Modelling multiple IP traffic streams with rate limits / D. P. Heyman, D. Lucantoni // IEEE. ACM Transactions on Networking. 2003. Vol. 11. P. 948–958.

2. Klemm, A. Modelling IP traffic using the batch Markovian arrival process / A. Klemm, C. Lindermann, M. Lohmann // Performance Evaluation. 2003. Vol. 54. P. 149–173.

3. Lucantoni, D. New results on the single server queue with a batch Markovian arrival process / D. Lucantoni // Communication in Statistics-Stochastic Models. 1991. Vol. 7. P. 1–46.

4. Бочаров, П. П. Теория массового обслуживания / П. П. Бочаров, А. В. Печинкин. М.: РУДН, 5. Neuts, M. Matrix-Geometric Solutions in Stochastic Models – An Algorithmic Approach / M. Neuts.

Johns Hopkins University Press, 1981. 332 p.

6. Ramaswami, V. Independent Markov processes in parallel / V. Ramaswami // Comm. Statist.-Stochastic Models. 1985. Vol. 1, № 3. P. 419–432.

7. Ramaswami, V. Algorithms for the multi-server queue with phase-type service. / V. Ramaswami, D. Lucantoni // Comm. Statist.-Stochastic Models. 1985. Vol. 1, № 3. P. 393–417.

О ПРИМЕНЕНИИ НМ-СЕТЕЙ С ПРИОРИТЕТНЫМИ

ЗАЯВКАМИ В КАЧЕСТВЕ МОДЕЛЕЙ

ИНФОРМАЦИОННО-КОМПЬЮТЕРНЫХ СЕТЕЙ

Гродненский государственный университет имени Янки Купалы В статье получена система разностно-дифференциальных уравнений для нахождения ожидаемых доходов в системах НМ-сети с приоритетными заявками и рассмотрен метод нахождения ее решений с помощью разностных схем.

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

Ключевые слова: НМ-сеть с доходами, приоритетные заявки.

ВВЕДЕНИЕ

На базе современных информационно-компьютерных сетей (ИКС) реализуются дистанционное обучение, телемедицина, телеконференции, телебиржи и телемагазины и т. д. Быстрый рост числа ИКС, успехи в развитии оптоволоконных и беспроводных средств связи сопровождаются непрерывной сменой сетевых технологий, направленной на повышение их быстродействия и надежности. Смена технологий, непрерывный количественный и качественный рост ИКС выдвигают в ряд первоочередных задач развитие теоретических основ их проектирования на базе систематизации уже известных подходов и разработки новых методов анализа и синтеза ИКС.

Стохастический характер поступления данных и недетерминированная обработка их в узлах коммутации и каналах связи предопределяет использование моделей теории массового обслуживания (МО) для анализа и проектирования ИКС.

Математические методы теории сетей МО обеспечивают возможность решения многочисленных задач расчета характеристик качества функционирования различных компонент ИКС, включая оценку вероятностно-временных характеристик узлов коммутации и маршрутизации; учет приоритетности запросов; анализ производительности локальных сетей и сетей с множественным доступом; анализ буферной памяти узлов и методов локального и глобального управления потоками; расчет потерь и загрузку цифровых линий связи при передаче данных, голоса и видеоинформации при различных методах мультиплексирования и т. д. [8].

ОПИСАНИЕ НМ-СЕТИ С ПРИОРИТЕТНЫМИ ЗАЯВКАМИ

Рассмотрим замкнутую сеть массового обслуживания, в которой циркулируют K1 заявок первого типа и K 2 заявок второго типа, причем заявки не могут менять свой тип. Матрица вероятностей переходов заявок между системами сети является неприводимой. Система S i содержит mi параллельных линий обслуживания, время обслуживания заявки c типа любой линией системы имеет показательное распределение со средним ic1, i = 1, n, c = 1, 2. Однотипные заявки, стоящие в очереди некоторой системы обслуживания (СМО), выбираются на обслуживание в произвольном порядке, например, FIFO. Заявки первого типа имеют абсолютный приоритет по отношению к заявкам второго типа. В данном случае это означает выполнение двух условий: а) если в момент освобождения линии некоторой СМО после обслуживания заявки в ее очереди имеются приоритетные заявки, то любая из них занимает освободившуюся линию, б) если в систему обслуживания, все линии которой заняты обслуживанием, но не только приоритетных заявок, поступает приоритетная заявка, то она вытесняет неприоритетную заявку с одной из линий и начинает обслуживаться этой линией; вытесненная заявка становится в очередь рассматриваемой СМО. Когда вытесненная заявка поступает на обслуживание повторно, она дообслуживается в течение оставшегося времени обслуживания. Поскольку время обслуживания имеет показательное распределение, то можно считать, что вытесненная заявка будет обслуживаться заново, т. е. имеем так называемое неидентичное обслуживание.

Состояние сети в данном случае характеризуется вектором Пусть I i1 – вектор размерности 2n с нулевыми компонентами, за исключением компоненты с номером 2i 1, которая равна 1, I i 2 – вектор размерности 2n с нулевыми компонентами, за исключением компоненты с номером 2i, которая равна 1, I 0 – 2n -вектор с нулевыми компонентами, Известно [1,2], что система уравнений для вероятностей состояний P( k, t ) имеет вид:

где В данной статье мы будем рассматривать замкнутую HM (Howard-Matalytski) – сеть произвольной структуры с приоритетными заявками. Заявка при переходе из одной СМО в другую приносит последней системе некоторый доход, и соответственно доход первой системы уменьшается на эту величину [3]. Рассмотрим случай, когда доходы от переходов между состояниями являются детерминированными функциями, зависящими от состояний сети и времени. В работе представлен метод нахождения ожидаемых доходов систем сети за время t при условии, что нам известны их доходы в начальный момент времени.

Задача исследования HM-сетей с различными особенностями была поставлена в [3].

Ранее в работах [2,5,6] было произведено исследование марковских HM-сетей с дисциплинами обслуживания заявок FIFO в СМО с ограниченным временем пребывания заявок в очередях систем обслуживания, а также с ненадежными системами обслуживания.

ОЖИДАЕМЫЕ ДОХОДЫ СИСТЕМ СЕТИ

Пусть vi (k, t ) – полный ожидаемый доход, который получает система Si за время t, если в начальный момент времени сеть находится в состоянии k, и предположим, что эта функция дифференцируема по t ; ri (k ) – доход системы Si в единицу времени, когда сеть находится в состоянии k ; r (1) (k + I i1 I j1, t ) – доход системы Si (расход или убыток системы S j ), когда сеть меняет свое состояние из ( k, t ) на убыток системы S j ), когда сеть меняет свое состояние из ( k, t ) на (k + I i 2 I j 2, t + t ) Для ожидаемого дохода системы Si получена система дифференциальных уравнений:

Система (1) в матричной форме может быть записана в виде где Vi (t ) = (vi (1, t ),, vi ( L, t )) – вектор доходов системы Si, L – число состояний сети.

Количество приоритетных и неприоритетных заявок не зависит друг от друга, поэтому число состояний в рассматриваемой нами сети равняется числу способов размещения K приоритетных заявок и K 2 неприоритетных заявок по n системам обслуживания, т. е. L = Cn+ K1 1Cn+ K2 1.

Пример. Рассмотрим замкнутую сеть большей размерности со следующими параметрами n = 20, K1 = 60, K 2 = 40, m = ( 2,1,1,3,1,4,1,5,3,2,4,3,2,1,3,2,1,3,4,2), где i -я компонента вектора является числом линий обслуживания в i -ой СМО. Вероятности переходов заявок между СМО сети равны p12 = p13 = p14 = p15 = p16 =, p 21 = 1, p31 = 1, p 41 = 1, p51 = p56 = p57 = p 58 = p 59 = p 5,10 = p5,11 = p 5,12 =, p65 = 1, p75 = 1, p85 = 1, p95 = 1, p10,5 = 1, p11,5 = p11,12 = p11,13 = p11,14 = p11,15 = p11,15 =, p12,11 = 1, p13,11 = 1, p14,11 = 1, p15,11 = 1, p16,11 = 1, p17,11 = p17,18 = p17,19 = p17, 20 =, p18,17 = 1, p19,17 = 1, p 20,17 = 1. Остальные вероятности переходов равны 0.

Интенсивности обслуживания систем зададим следующим образом: i1 = 15, i 2 = 10, если остаток от деления i на 3 равен 1; i1 = 13, i 2 = 18, если остаток от деления i на 3 равен 2; i1 = 17, i 2 = 16, если остаток от деления i на 3 равен 0.

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

где a и c — некоторые целочисленные коэффициенты. Получаемая последовательность зависит от выбора стартового числа X 0 и при разных его значениях получаются различные последовательности случайных чисел [7].

Число состояний такой сети равняется L = C n + 1 1 1C n + 1 2 1 = 1234957962 2514650786 1377557949 0700.

Система (2) решалась с помощью разностных схем. График дохода первой системы для состояния k = (3,2;3,2;3,2;3,2;3,2;3,2;3,2;3,2;3,2;3,2;3,2;3,2;3,2;3,2;3,2;3,2;3,2;3,2;3,2;3,2) выглядит следующим образом (рисунок).

График дохода первой системы для вышеуказанного состояния сети

ЛИТЕРАТУРА

Малинковский, Ю. В. О разностных уравнениях, возникающих в одной задаче теории массового обслуживания / Ю. В. Малинковский // Доклады АН БССР. 1997. Том 23, № 1. С. 22–25.

Маталыцкий, М. А. Теория массового обслуживания и ее применение / М. А. Маталыцкий, А. В. Паньков, О. М.Тихоненко. Гродно: ГрГУ, 2008. 771 с.

Matalytski, M. On some results in analysis and optimization of Markov networks with incomes and their application / M. Matalytski // Automation and Remote Control. 2009. Vol. 70, № 10. P. 1683–1697.

Черная, Н. В. О методах нахождения доходов НМ-сетей с зависимыми от времени интенсивностями обслуживания заявок / Н. В. Черная, М. А. Маталыцкий // Вестник ГрГУ. Сер. 2. 2011, № 1.

С. 132–139.

Matalytski, M. Investigation of HM-network with limited of waiting time in quencing systems / M. Matalytski, A. Pankov, S. Statkevich // Computer Science. 2009. Vol. 7, № 13. P. 29–40.

Matalytski, M. Investigation of HM-network with unreliable quencing systems and random incomes / M. Matalytski, S. Statkevich // Scientific Research of the Institute of Mathematics and Computer Science Czestochowa University of Technology. 2010. Vol. 1, № 9. P. 173–192.

Кнут, Д. Искусство программирования / Д. Кнут. М.: «Вильямс», 2007. 832 с.

Вишневский, В. М. Теоретические основы проектирования компьютерных сетей / В. М. Вишневский. М.: Техносфера, 2003. 506 с.

ON RETRIAL QUEUES CONTROLLED BY THE

THRESHOLD AND HYSTERESIS STRATEGIES

Retrial queues of the type M Q / M / m / with controlled rate of input flow are considered. For calculation of stationary probabilities an approximate approach have been developed. Proposed calculating scheme was applyed to solve an optimization problem in a class of the threshold strategies.

Keywords: retrial queues, stationary distribution, threshold and hysteresis strategies, optimization problems.

We deal with a m- server retrial model of the type M/M/m in which a rate of primary call flow j depends on the number j – of customers in the orbit. The rates of repeated calls and of the service process are supposed to be constant. The effective approach to find a steady state distribution of the service process is proposed. It consists of two stages.

At the first stage we construct the explicit vector-matrix form of the stationary distribution for the queue with finite orbit. At the second stage the stationary probabilities for the queue with infinite orbit are approximated by the formulae which are obtained at the first stage.

Let us define the basic model as the two-dimensional Markov chain with continuous time Q(t ) = (Q1 (t ), Q2 (t )), t 0 in space S = I J, I = {0,1,..., m}, J = {0,1,...}, Q1 (t ) – number of busy servers, Q2 (t ) – number of repeated call sources. Infinitesimal characteristics q (i, j )(i, j ) of Q(t ) are given by the parameters j,, in the ordinary way (see [1], p.

95–96).

We point out the conditions of existence of the stationary regime in the following lemma.

godic and its limit distribution coincides with the unique stationary distribution.

At first we consider the M Q / M / m / N - model where N is a maximal possible numq((iNj))(i, j ) Q (N ) (t ) = (Q1( N ) (t ), Q2N ) (t )) coincide with ( i, j )( i, j ) under i = 0,1,..., m 1, under i = m, j = 0,1,..., N 1. If i = m, j = N, then Via ( N ), ( i, j ) S ( N ) = {0,1,..., m} {0,1,..., N } we denote the stationary probabiliij ties of Q (N ) (t ). To formulate the basic result we introduce the notation:

Via D(N ) we will designate a triangular matrix Also it be necessary for us the following vectors:

– dimensional vector composed of 1, ei (m 1) is (m-1) – dimensional vector with i-th component is equal to 1 and the rest are equal to 0. Via 1, ei we will designate the same vectors of dimensional m.

Theorem 1. If j 0, j = 0,1,...N then stationary probabilities ijN ), (i, j ) S ( N ) has the following form Evidently these formulas is an effective recurrent procedure to calculate the stationary distribution.

When the conditions of Lemma 1 hold true and N the stationary probabilities (i, j ) S ( N ) converge to the corresponding probabilities for the system M Q / M / m /.

Variable rate of the input flow allows to consider a queue controlled by different strategies. In the report we consider two variants: threshold and hysteresis strategies.

Let us consider the threshold strategy which realizes the following algorithm of the service process control: we set j = (1) if j = 0,1,..., h and j = (2) if j = h + 1,....

The explicit formulae for steady state probabilities enable to propose an effective algorithm for optimal decision making which consists in finding of optimal position for a level to maximize some objective functional. As such a function we took the following where S1 (h ) is the number of calls have being served; S 2 (h ) – the number of calls which become repeated calls; S3 (h ) – the number of switching of the input flow; C1 – income associated with service of a call; C2 – penalty connected with a refusal in service; C3 – penalty connected with a switching of the input flow rate.

We seek the threshold h which maximizes a mean income for the system operating in a stationary regime. In the conditions of the stationary regime existence (conditions of Lemma 1) functionals Si (h ), i = 1,2,3 also exist and can be written through stationary probabilities ij = ij (h ), Thus to solve the problem (1) we must calculate the stationary distribution of the A hysteresis strategy may be introduced by means of the two thresholds 0 h1 h2.

The rate of input flow changes from (1) to (2) if the number of repeated calls reaches the level h2 from below and it changes from (2) to (1) if the number reaches h1 from above.

If the number of repeated calls is in the interval [ h1, h2 ) then the queue follows the mode in which it was at the previous moment of time. The similar controlled systems with single server have been considered in [2, 3].

We will consider hysteresis strategy on the example of the system M Q / M / m /.

Let us define our model as the three-dimensional Markov chain with continuous time Q (t ) = Q1 (t ), Q2 (t ), Q3 (t ), t 0 in space S = {0,1} {0,1, 2,...} {1, 2}, Q1 (t ) – number of busy servers, Q2 (t ) – number of repeated call sources, Q3 (t ) – regime in which the system operates in the moment t. If Q (t ) = 1 then the system operates in the first regime with the rate of input. If Q3 (t ) = 2 then the rate of input is (2). Infinitesimal characteristics q (i, j,r ) of Q (t ) may be written via the system parameters.

Under (2) / m 1 for Q (t ) there exists the stationary regime. As an approximation of Q(t ) we consider the Markov chain Q (t ) in by analogy with Q (t ).

Let us introduce the following notations: ei ( m ) = ( io, i1,..., im 1 ), ij is Kronecker delta, Theorem 2. The stationary probabilities of Q ( N ) (t ) may be represented in the form Theorem 2 may be applied to solve the optimization problems related to (1).

REFERENCES

Falin, G. I. Retrial queues / G. I. Falin, J. G. C. Templeton. London Chapman & Hall, 1997. 331 p.

Klimenok, V. I. Optimization of dynamic control for a work regime of informational-computing systems with repeated calls / V. I. Klimenok // Automation and tehnology. 1990. № 1. P. 25–30.

Dudin, A. N. Optimization of dynamic control of input load in node of informational-computing network / A. N. Dudin, V. I. Klimenok // Automation and tehnology. 1991. № 2. P. 25–31.

QUEUEING SYSTEM GI/M/1 WITH RANDOMIZED THRESHOLD

ADMISSION CONTROL

Queueing system type GI/M/1 with randomized threshold admission control is considered. The stationary distribution at arrival moments and at arbitrary moments is calculated. The Little's law is proved for this system.

Keywords: GI/M/1 queueing model, threshold admission control, Little’s law.

MATHEMATICAL MODEL

Queueing systems with variable operating conditions are adequate mathematical model of processes occurring in many components of modern communication networks and computer networks. Some results for systems with threshold admission control type M/G/1, GI/M/1 [3, 7], BMAP/G/1 [6], GI/PH/1 [8] and also for other systems [5, 9, 10] were obtained. In this paper, we will consider a queueing system type GI/M/1 with randomized threshold admission control; find the stationary probabilities and calculate some characteristics of this system.

Consider a single-server queueing system that can work in two modes. The system will switch to the first mode if the number of customers in this system is not larger than a fixed threshold j, else switch to the second mode in the opposite case. Assume that in the mode, the distribution function of inter-arrival times is A (t ) with intensity = (1 A(t ))dt and its Laplace-Stieltjes transform A* ( s) = e st dA(t ) while service times have exponential distribution with parameter. A customer arriving in the mode will be accepted with probability p or rejected with probability 1 p, = 1, 2.

Let in denote the number of customers in the system immediately before the arrival moment of n-th customer. Clearly, {in }n0 is a homogeneous irreducible Markov chain. Let pik = P{in = k | in 1 = i}, i, l 0 be the one-step transition the one-step transition probability of this Markov chain. By the complete probability formula, we easily obtain that, where = e mode, there are k customers leaving from the system after completing their services,

STATIONARY PROBABILITIES

Let rl = lim P{in = l}, l 0 denote the stationary probability of the Markov chain {in }n0. Applying the Chapman – Kolmogorov equation, we have the following recurrent relation where Solving the system of recurrent relations (1)–(2)–(3) by applying of geometric method, we get the following result Theorem 1. The stationary probabilities of Markov chain {in }n0 are given by the formula where 1. is the unique solution in the interval (0,1) of the equation 2. Сoefficients ak, k = 0,1,... are calculated by their generating function defined by where coefficients bk = function defined by Corollary 1. 1. The loss probability of an arbitrary customer is calculated as 2. The mean number of customers in the system immediately before the arrival moment of a customer is calculated as where coefficients ck = function Let it denote the number of customers in the system at an arbitrary moment t and n is the arrival moment of the n-th customer. Let l = lim P{it = l} be the stationary probabilt ity of the random process {it }t 0. We can easily verify that, process {it }t 0 is a semigenerative process with embedded Markov renewal chain {in, n }n0, i. e. satisfying following properties:

a) For each n 0, n – is a stopping time for {t }t 0 and in is deterministic function of b) {in }n0 is a process on a countable state space E such that and probability P{in +1 = j, n +1 n t | in = i} = Fij (t ), i, j E is independent of n ;

Theorem 2. Let {it }t 0 be a semi-generative process with irreducible and positive recurrent embedded Markov renewal chain (in, n )n0 with stationary probabilities {rl }lE.

Assume that m = E (1 | i0 = k )rk, then See the proof in [1, с. 211–213], or [2, с. 144–146].

Applying the fact in Theorem 2, using method intergral by parts and taking the generating functions, we get the following result Theorem 3. The stationary probabilities of the process {it, t 0} are given by the formula where coefficients n, n = 0,1, 2,..., j, are calculated by their generating function If 1 = 2, we can simplify the function to the form Corollary 2. The mean number of customers in the system at an arbitrary moment is calculated as

SOME CHARACTERISTICS OF THE SYSTEM

In the next sequence, we assume that in two working mode of the system, the difference of two mode is only between the distribution of inter-arrival times and the accepted probability p1, p2, while service rates of two service mode are identical, i. e. 1 = 2 =.

A customer arriving into the system when there are m other customer, may be loss with probability 1 p or accepted to the system with probability p ( = 1, if m j, = 2 if m j + 1 ) and he will wait until all m customers, who had arrived into the system before him, completing their services. Their waiting times have Erlangian distribution Em (). Applying formula of completed probability, we obtain the stationary distribution of waiting time of a customer arriving into the system in the form Similarly, function of stationary distribution of sojourn time of a customer arriving into the system has the following form Laplace transforms of functions W (t ), V (t ) are calculated as Theorem 4. 1. The mean waiting time is calculated as 2. The mean sojourn time is calculated as Consequently, we obtain that.

Theorem 5. Little’s Law holds true for the abovementioned system, i. e. V = mL.

LITERATURE

Asmussen, S. Applied Probability and Queue / S. Asmussen. Springer, 2003.

Breuer, L. An Introduction to Queueing Theory and Matrix Analytic Methods / L. Breuer, D. Baum.

Springer, 2005.

3. Дудин, A. Н. Оптимизация динамического управления входной нагрузкой в узле информационновычислительной сети / A. Н. Дудин, В. И Клименок. Автоматика и вычислительная техника. 1991.

4. Dudin, A. N. Optimal control for a BMAP/G/1 queue with two service modes / A. N. Dudin, S. Nishimura.

Mathematical Problems in Engineering. 1999. Vol. 5, № 3. P. 255–273.

5. Dudin, A. N. Optimal control for an MX/G/1 queue with two operation modes / A. N. Dudin. Probability in the Engineering and Informational Sciences. 1997. Vol. 11, № 2. P. 255–265.

6. Dudin A. N. Optimal multithreshold control for a BMAP/G/1 queue with N service modes / A. N. Dudin.

Queueing Systems. 1998. Vol. 30, № 3-4. P. 273–287.

7. Дудин, A. Н. Практикум на ЭВМ по теории массового обслуживания / A. Н. Дудин, Г. А. Медведев, Ю. В. Меленец. Минск, 2000.

8. Dudin, A. N. Optimal admission control in a queueing system with heterogeneous traffic / A. N. Dudin, V. I. Klimenok. Operations Research Letters. 2003. Vol. 31, № 2. P. 108–118.

9. Dudin, A. N. Multi-threshold control of the BMAP/SM/1/K queue with group services / A. N. Dudin, S.

R. Chakravarthy. Journal of Applied Mathematics and Stochastic Analysis. 2003. Vol. 16, № 4. P. 327– 10. Kim, C. S. Optimal multi-threshold control by the BMAP/SM/1 retrial system / C. S. Kim, V. Klimenok, A. Birukov, A. Dudin. Annals of Operations Research. 2006. Vol. 141, № 1. P. 193–210.

STOCHASTIC SERVER MODEL

WITH LIMITED STORAGE SIZE

In this paper analytic model of server servicing requests of many users is presented. Every user can dispose of computer system having its own characteristics and can be represented by classical queue but in fact users are dependent because they are connected via common memory space which is limited. Analogous models can represent mail or ftp servers and can be used to calculate needed server storage size ([1, 2]). In this research stationary distribution function of number of requests and stationary refusal probability for every user was obtained. It contains also review of some special cases.

transform inversion; Stieltjes convolution.

MODEL DESCRIPTION AND ANALYSIS

For such one number of requests distribution function and refusal probability for every system will be obtained - both in the steady state. Let us then consider two classical independent systems denoting them as. Let be suitable entrance Poisson flow and service time parameters for i-th queueing system. In addition we assume that every request in i-th system has some random size. Let be distribution function of this random variable. Denote as - summary size of all requests present in server storage at time t and assume that server storage size is limited by value V and requests service times and their sizes are independent. Let be the number of requests present in i-th system at time t, - the size of j-th request in i-th system at time t,. Then the combination of two systems can be described by the following Markovian process Process (1) can be characterized by the following functions It is clear that steady state exists for analysed combination if value of V is finite. Then we the sense of weak convergence.

Now we will obtain stationary number of requests distribution function.

Denote as the k-th order Stieltjes convolution of functions, and for convolution of distribution functions of non-negative random variables we will use the following notation We introduce also the notation By the substitution we can check that solution of the (5)-(8) system has the form From (10) we easily obtain The value of can be obtained from normalization condition Obtained results can be extended for the arbitrary r number of computer systems. Then we have The value of can be obtained from analogous normalization condition.

REFUSAL PROBABILITY

Stationary refusal probability for i-th system (i=1,2) can be obtained from the following equilibrium condition (in the steady state, during the same interval of time, the mean number of arriving requests that are not lost is equal to the mean number of serviced requests).

From (13) we obtain the following formula Analogous formula can be obtained for the arbitrary number of systems.

RESULTS IN SOME SPECIAL CASES

Now we will investigate some special case - combination of two one-device systems connected via common memory space. Generalization for the arbitrary number of systems is obvious. In practice this case is the model of server servicing requests of some systems consisting of single computer. In addition we suppose that all requests have the same size distribution function which is exponential with the same parameter f and where where Obtained formulas can be extended for the arbitrary number of systems.

During the analysis, calculating loss probabilities, we can notice that investigated combination of one-device systems with exponential request distribution function with the same parameter f for every system can belong to one of the following classes:

If the parameters of exponential request distribution function are not the same then refusal probabilities vary.

The simulation results presented in table 1 show that fact.

Now we will investigate one more special case. Let us suppose that we have combination of two one-device systems with finite number of waiting places. In addition we assume that request distribution function is uniform on the [a,b] interval and number of waiting places is the same for both systems.

Using Laplace transform inversion we can find formula for the k-th order Stieltjes convolution of uniform distribution functions on the [a,b] interval which has the form where H(x) is a Heaviside unitstep function.

Then from (11) and (14), using (19), we can calculate numerical results for probabilities.

We can notice (after calculations) that in this case refusal probabilities are not the same and converge to 0 in stable state or to the in the overload state.

LITERATURE

Tikhonenko, O. M. Queueing systems of a random length demands with restrictions. Automation and Remote Control 52. / O. M. Tikhonenko. 1991. P.1431–1437.

Tikhonenko, O. Probability Analysis of Information Systems. / O. M. Tikhonenko. Warsawa 2006.

ПАРАЛЛЕЛЬНАЯ

И РАСПРЕДЕЛЕННАЯ

ОБРАБОТКА ДАННЫХ,

МНОГОПРОЦЕССОРНЫЕ

СИСТЕМЫ И СЕТИ

ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ ЛОКАЛЬНО-ОДНОМЕРНОГО

МЕТОДА ЧИСЛЕННОГО РЕШЕНИЯ КВАЗИЛИНЕЙНЫХ

ДВУМЕРНЫХ ПАРАБОЛИЧЕСКИХ УРАВНЕНИЙ

С. В. Баханович, Н. А. Лиходед, Г. М. Заяц, С. А. Артемчик E-mail: bsv@im.bas-net.by, likhoded@im.bas-net.by, zayats@im.bas-net.by Предлагается параллельная реализация локально-одномерного метода численного решения квазилинейных двумерных параболических уравнений на суперкомпьютерах с распределенной памятью. Параллельная реализация получена путем адаптации к параллельному выполнению предварительно разработанной последовательной программы. Приводятся результаты численных экспериментов.

Ключевые слова: параллельные вычисления, параболические уравнения, локально-одномерный метод.

ЛОКАЛЬНО-ОДНОМЕРНЫЙ МЕТОД ЧИСЛЕННОГО РЕШЕНИЯ

ДВУМЕРНЫХ ПАРАБОЛИЧЕСКИХ УРАВНЕНИЙ

Рассмотрим в области QT = G [0 t T ], G = [0 x1 l1 ] [0 x2 l2 ], квазилинейное параболическое уравнение с начальными и краевыми условиями.

Согласно [1] осуществим дифференциальное расщепление задачи (1)–(3). На отрезке [0 t T ] введем сетку узлов = {t j = j, j = 0, 1,..., j0, j0 = T }. На отрезках t j 1 t t j, j = 1, 2,..., j0, уравнению (1) поставим в соответствие уравнения Уравнения (4) и (5) связаны соотношениями При этом За приближенное решение задачи (1)–(3) на каждом слое t j принимается функция (2) (x, t ). Задача (4)–(10) аппроксимирует задачу (1)–(3) в суммарном смысле [1].

Для численного решения задачи (4)–(10) в области G введем сетку узлов h = {x1(i1 ) = i1h1, i1 = 0, 1,..., N1, N1h1 = l1, x2i2 ) = i2 h2, i2 = 0, 1,..., N 2, N 2 h2 = l2 }. Обозначим y(1) и y(2) соответственно численные значения функций (1) и (2) на сетке = h. Введем следующие коэффициенты:

a1,j i1, i2 = 0,5( k1 ( xi1, xi2, t j,(1) ) + k1 ( xi1 1, xi2, t j,(1) )), i1 = 1,..., N1, i2 = 1,..., N 2 1, j = 1,..., j0, a2, i1, i2 = 0,5( k2 ( xi1, xi2, t j,(2) ) + k2 ( xi1, xi2 1, t j,(2) )), i1 = 1,..., N1 1, i2 = 1,..., N 2, j = 1,..., j0.

Для решения задач (4), (6), (8), (9) построим итерационный процесс [1]:

при этом y (1) i1,i2 = y (1)i1,i2 = j Итерационный процесс для решения задач (5), (7), (10) имеет вид при этом y (j2 ) i1,i2 = y (j2) 11,i2, i1 = 1,..., N1 1, i2 = 1,..., N 2 1, j = 1, 2,..., j0.

Итерирование ведется до выполнения условия где 1 и 2 эмпирические параметры (при этом полагают, что 1 = 0, если y ( m ) i1,i Зафиксировав в (11) j и i2, получим систему алгебраических уравнений отноs + которую можно решить методом скалярной прогонки [1] s (1) j, i2 раз ( s (1) j, i2 – количество итераций, необходимых для выполнения неравенства (13) при фиксированных j и i2 ). На каждом слое t j необходимо выполнить N 2 1 независимых итерационных процесса (для каждого i2 = 1,..., N 2 1 ).

Аналогично, решение задачи (12) на каждом слое t j представляет собой решение N1 1 независимой задачи при фиксированном i1 = 1,..., N1 1. Каждая из указанных задач является системой из N 2 1 линейного уравнения относительно значеs + y (j20) i1, N 2 = ( xi1, l2, t j0 ), i1 = 0, 1,..., N1, является приближенным решением задачи (1)–(3).

ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ

Для отображения алгоритмов на параллельные компьютеры с распределенной памятью требуется распределить операции алгоритма между процессорами, распределить данные между процессорами, установить порядок выполнения операций в каждом процессоре и организовать обмены данными [2, 3].

Решение задачи (1)–(3) осуществляется через решение задач (4), (6), (8), (9) (итерационный процесс (11)) и задач (5), (7), (10) (итерационный процесс (12)) на каждом временном слое t j.

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

Каждому процессору при фиксированном параметре j назначим выполнение итерационного процесса с решением ( N 2 1) P систем уравнений вида (11) и итерационного процесса с решением ( N1 1) P систем уравнений вида (12). Решение систем (11) и (12) будем осуществлять методом правой прогонки. Поскольку решение систем можно производить независимо друг от друга, то для обеспечения этой возможности необходимо перераспределять данные, полученные в результате выполнения каждого итерационного процесса:

1) после завершения итерационного процесса (11) p-й процессор должен 2) по завершении итерационного процесса (12) p-й процессор должен получить от q-го ( q p ) процессора данные

РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТОВ

Параллельная версия локально-одномерного метода, описанная в предыдущем разделе, программно реализована на языке С++ с использованием MPI. Ниже приведены результаты экспериментов с программной реализацией метода, проведенных на суперкомпьютере СКИФ (ОИПИ НАН Беларуси).

Рис. 1. График зависимости времени выполнения алгоритма Рис. 2. График зависимости эффективности от количества процессов На рисунках 1, 2 представлены графики зависимости времени выполнения алгоритма и эффективности от количества процессов при выполнении параллельной программы в предположении, что T=l1=l2=1 и N1=N2=j0=1440. Эффективность параллельной реализации алгоритма определялась по формуле Tseq/(Tpar·P), где Tseq – время последовательной реализации алгоритма, Tpar – время параллельной реализации, P – количество процессов. Графики показывают достаточно высокую эффективность параллельной реализации локально-одномерного метода на относительно небольшом количестве процессов. С увеличением количества процессов эффективность снижается, что объясняется возрастающей долей накладных расходов на коммуникации при выполнении алгоритма. Среднее количество итераций процессов (11) и (12) составляет 4 итерации (min=3, max=17) для 1=2=10–6 и 5 итераций (min=3, max=28) для 1=2=10–7.

ЛИТЕРАТУРА

1. Самарский, А. А. Теория разностных схем / А. А. Самарский. М.: Наука, 1989. 616 c.

2. Баханович, С. В. Параллельная реализация локально-одномерного метода численного решения двумерных параболических уравнений / С. В. Баханович, Г. М. Заяц, Н. А. Лиходед, В. А. Цурко // Информатика. 2010. Т. 17, № 4. С. 72–80.

3. Воеводин, В. В. Параллельные вычисления / В. В. Воеводин, Вл. В. Воеводин. СПб.: БХВПетербург, 2002. 600 с.

О ВОЗМОЖНОСТИ РАСШИРЕНИЯ ФУНКЦИОНАЛЬНОМОДУЛЬНОГО ПОДХОДА К ПОСТРОЕНИЮ ПРИЛОЖЕНИЙ

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

Ключевые слова: портал, социальные сети, открытый API, системы облачных вычислений, мобильные приложения.

ВВЕДЕНИЕ

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

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

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

МЕТОДОЛОГИЯ ФУНКЦИОНАЛЬНО-МОДУЛЬНОГО ПОДХОДА

К ПРОЕКТИРОВАНИЮ

Система модульной разработки приложений представляет собой одновременно как методологию разработки, так и конкретный базовый модуль, состоящий из общих интерфейсов, классов, конфигураций и менеджеров. Что касается методологического представления системы – это набор определенных правил разработки системы, базирующихся на популярном в настоящее время шаблоне проектирования систем MVC (model – view – controller). Идея методологии проектирования базируется на том, что, во-первых, весь набор стандартных действий над объектами и соответственно над данными уже заложен в структуру базового модуля. Также этот модуль содержит стандартный набор средств для организации распределения прав доступа к объектам и методам приложений, утилиты для работы с метаданными, средства локализации, доступа к ресурсам и многое другое.

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

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

НАТИВНЫЕ ПОДСИСТЕМЫ ПОРТАЛА

Базовой идеей, проходящей через каждый из модулей, является централизованная система аутентификации пользователей в приложениях. На сегодняшний день, как это и предсказывалось несколько лет назад, огромную популярность приобрела технология авторизации посредством OAuth, вполне зарекомендовавшая себя при применении в наиболее популярных социальных системах Google, Facebook, Twitter и многих других. На базе данной технологии в рамках описываемого проекта уже была разработана система управления пользователями, данная система была выделена в отдельный модуль и позиционируется как одна из обязательных частей каждого приложения.

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

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

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

ПОРТИРОВАНИЕ ПРИЛОЖЕНИЙ ДЛЯ МОБИЛЬНЫХ ПЛАТФОРМ

Основополагающей идеей разрабатываемой системы является тесная интеграция всех подсистем портала с мобильными устройствами. Следует отметить, что абсолютно все разрабатываемые системы изначально снабжаются открытым API, базирующимся на обмене данными через HTTP-протокол в формате JSON, который является наиболее приемлемым для мобильных приложений. В качестве целевых устройств были выбраны наиболее популярные в данный момент КПК на базе операционных систем Android и iOS, также в перспективе рассматривается разработка приложений для Windows Mobile 7, Meego, Symbian, однако для принятия окончательного решения необходимо проанализировать предположительный успех развития данных систем в будущем.

Исследование рынка мобильных устройств на базе iOS и Android показало достаточно стремительный рост их популярности за последние 3 года, причем эта популярность продолжает возрастать с каждым днем в геометрической прогрессии, выпускается все большее количество устройств, обновляются сами системы и что особенно знаково – популяризируются приложения для данных систем. Как показал все тот же анализ рынка – специфические приложения, разработанные в качестве клиентских модулей для популярных сервисов, пользуются гораздо большим спросом, нежели мобильные веб-версии тех же сервисов. Исходя из этой позиции, мобильные приложения для подсистем портала оказались на более высоком уровне по значимости по сравнению с адаптацией пользовательских веб-интерфейсов (хотя этот момент также не исключается).

Мобильная часть реализации систем портала не заканчивается на разработке аналогов подсистем, адаптированных под мобильные устройства, помимо этого в рамках проекта запланирована (и частично реализована) система библиотек расширений мобильных приложений. Другими словами, это набор библиотек, реализующих API-подсистем портала, а также дополнительных фоновых подсистем (не видимых пользователю, однако выполняющих важные функции по взаимодействию между подсистемами, а также между серверной частью реализации портала и приложениями, установленными на мобильные устройства). Данные библиотеки не являются полноценными приложениями, однако обладают набором методов и интерфейсов, базирующихся все на тех же идеях, что и их аналоги на серверной стороне – функциональная реализация модулей, требующая лишь специфической адаптации под нужды проекта и разработки пользовательского интерфейса. Такие библиотеки позволят буквально «собирать» мобильные приложения из определенных модулей, при этом избавляя разработчика от написания одного и того же кода каждый раз при разработке очередного приложения. Помимо значительного уменьшения временных затрат на построение мобильных приложений, данная идея позволит объединять множество сторонних приложений различной направленности в рамках разрабатываемого портала (что достаточно активно практикуется на данный момент в рамках вебразработки известными поставщиками услуг в сети интернет, такими как Google, Facebook, Microsoft, VKontakte, SalesForce и т. д.).

ДОПОЛНИТЕЛЬНЫЕ ПОДСИСТЕМЫ, РАЗРАБАТЫВАЕМЫЕ

В РАМКАХ ПРОЕКТА

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

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

ЗАКЛЮЧЕНИЕ

Следует отметить, что разрабатываемые модули не являются абсолютно новой идеей, данная тема развивается в рамках проекта на протяжении 4 лет, за это время во многом схожие системы были разработаны крупными корпорациями, такими как Google, Microsoft, Apple. Несмотря на это, существующие системы по-прежнему обладают большим количеством недочетов, зачастую оказываются недостаточно или неправильно интегрированными между собой и со сторонними сервисами, часто они и вовсе не позволяют выполнять интеграцию со стороны сторонних приложений, что значительно ограничивает возможности разработки для сторонних программистов.

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

ЛИТЕРАТУРА

http://www.infoworld.com/d/cloud-computing/what-cloud-computing-really-means-031. Date of access:

28.06.2011.

2. QuickStudy: Application Programming Interface (API) [Electronic resource] Mode of access:

http://www.computerworld.com/s/article/43487/Application_Programming_Interface. Date of access:

28.03.2011.

ОБОБЩЕННАЯ МОДЕЛЬ АВТОМАТИЗИРОВАННОГО

РАБОЧЕГО МЕСТА СПЕЦИАЛИСТА

НА ВЫЧИСЛИТЕЛЬНОМ КЛАСТЕРЕ

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

Ключевые слова: обобщенная модель, документно-ориентированная система, артефакт, псевдоартефакт, агент, субагент, вычислительный кластер.

ВВЕДЕНИЕ

Современное рабочее место специалиста, должностные обязанности которого сопряжены с обработкой и созданием документов, – как правило, это объединение стандартного пакета офисных приложений и набора узкоспециализированных программных средств. Документооборот – это движение документов от момента их создания до передачи в архив. Жизненный цикл самого документа в общем случае описывается следующей схемой: постановка задачи создания документа, выбор типа (шаблона) и инструментов реализации, поиск информации, непосредственное формирование документа, создание электронного документа на рабочем компьютере (сохранение файла), печать документа, сбор подписей и/или передача его по электронной почте. Каждый из данных этапов, естественно, может быть автоматизирован. В частности, могут быть определены шаблоны, по которым будут формироваться документы. Передача документов по электронной почте также можно назвать формой автоматизации транспортного уровня документооборота. Если проанализировать потоки документов среднестатистического учреждения, то они включают: распоряжения, отчеты, назначения, информационные письма, бухгалтерские документы и т. д.

Рассмотрим частный случай документа – отчет. Как правило, несколько подразделений готовят отчет о своей деятельности с некоторой периодичностью (день, неделя, месяц, квартал, год и т. д.). Затем на основании этих отчетов, в большинстве случаев вручную, генерируется сводный отчет. Кроме того, копии документов хранятся как в электронном виде в нескольких экземплярах, так и на бумаге с подписями исполнителей и ответственных лиц. Даже на таком небольшом примере очевидно, как неэффективно используются ресурсы организации. Таким образом, актуальной является задача автоматизации всей схемы движения потоков документов, что позволит оптимизировать трудозатраты сотрудников, а также эффективнее использовать ресурсы организации в части аппаратной составляющей.

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

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

ОБОБЩЕННАЯ МОДЕЛЬ ДОКУМЕНТНО–ОРИЕНТИРОВАННОЙ

СИСТЕМЫ

Очевидно, что основным предметом исследования в документноориентированных системах является сам документ, а основными задачами изучения документа – определение его свойств, характеристик, а также классификация.

В терминах данного исследования документ назовем артефактом. Артефакт – это созданное кем-то, как правило человеком (автором), описание некоторого факта, представленное в виде электронного документа.

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

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

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

Полномочиями создания и анализа артефактов наделен исполнитель, а основную нагрузку по их наполнению выполняют агенты посредством своих программных субагентов.

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

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

Пользователь Рис. 1. Схема работы системы в однопользовательском режиме На рисунке 1 представлена поведенческая схема работы системы в однопользовательском режиме. Расширим модель введением следующей абстракции – пользователь.

Пользователи должны взаимодействовать с системой на основании их ролей и могут быть объединены в группы. Роли регламентируют сферу деятельности пользователя, т. е. определяют набор артефактов и набор агентов, доступных ему.

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

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

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

На рисунке 2 представлена модель многопользовательского режима работы, где П1, П2, …, Пn – пользователи, Пa – администратор, А1, А2, …, Аn – агенты, доступные пользователям, Аа – агент по управлению пользователями и ролями.

Рис. 2. Схема многопользовательского режима работы

ЗАКЛЮЧЕНИЕ

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

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

• web-сервер в качестве бизнес-ядра приложения;

• RIA-технологии для организации пользовательского интерфейса;

• документо-ориентированные СУБД в качестве хранилища данных.

ЛИТЕРАТУРА

1. Chodorow, K. MongoDB: The Definitive Guide / K. Chodorow, M. Dirolf. O'Reilly, 2010. 216 p.

2. Буза, М. К. Информационная модель процесса расследования правонарушений / М. К. Буза, Н. В. Деева // Журн. Информатика. 2009. № 4(24). С. 112–123.

3. Макдональд, М. Microsoft ASP. NET 4 с примерами на C# 2010 для профессионалов / М. Макдональд, А. Фримен, М. Шпушта. М: Вильямс, 2011. 1424 с.

4. Торопов, Б. А. Об организации системы электронного документооборота в органах внутренних дел / Б. А. Торопов // Управление защитой информации. 2010. Т.14, № 1. С.85–88.

МОДЕЛИРОВАНИЕ МЕТОДОМ МОЛЕКУЛЯРНОЙ

ДИНАМИКИ НА МНОГОПРОЦЕССОРНЫХ

КОМПЬЮТЕРАХ

Рассматривается реализация параллельной версии алгоритма молекулярной динамики на суперкомпьютер СКИФ-1000-2 для решения задач по моделированию в физике твердого тела. Выполнена модификация и дополнение известного пакета молекулярной динамики XMD.

Ключевые слова: моделирование методом молекулярной динамики, пакет XMD, суперкомпьютер СКИФ-1000-2.

ВВЕДЕНИЕ

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

В данном докладе представлены результаты МД-моделирования в физике твердого тела на суперкомпьютере СКИФ-1000-2, установленном в Белорусском государственном университете. Для моделирования выбран имеющий хорошую репутацию в среде исследователей пакет XMD.

ПАКЕТ XMD

Пакет МД-моделирования XMD (Molecular Dynamics for Metals and Ceramics) [1] имеет большую историю и много пользователей. Очевидными преимуществами пакета являются широкий набор поддерживаемых потенциалов, сравнительная простота использования и открытость исходных кодов.

Авторы XMD предлагают параллельную версию пакета, которая основана на использовании библиотеки потоков POSIX Thread Library и работает на компьютерах с общей памятью. Правда, в XMD многопоточный вариант поддерживается только для вычисления EAM-потенциалов (предназначенных для металлов).

Функционал пакета XMD расширен нами за счет включения многопоточных функций вычисления эмпирических потенциалов для полупроводниковых ковалентных материалов [2]. Для распараллеливания алгоритма МД использовался его естественный параллелизм: расчет потенциальной энергии системы, сил, координат и скоростей можно выполнять одновременно для всех атомов в пределах одного временного шага. Список всех частиц делился на равные части, и каждый процессор вычислял значения, соответствующие распределенным ему частицам. Были проведены эксперименты на персональном компьютере с четырехъядерным процессором Intel Core 2 Quad Q9400 и ноутбуке с двухъядерным процессором Celeron Dual-Core T под управлением операционной системы Microsoft Windows XP с созданным многопоточным Windows-приложением, которые привели к следующим выводам:

• существуют задачи, для которых использование естественного параллелизма алгоритма МД дает хорошее ускорение;

• поддержка потоков требует малых накладных расходов;

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

• наибольшая эффективность достигается при использовании двух потоков;

• задачи «Отжиг» и «Диффузия» дают приемлемое общее ускорение для двухпоточного варианта, равное примерно 1,5.

Суперкомпьютер СКИФ К-1000 является старшей моделью семейства «СКИФ».

Это – кластер из 288 двухпроцессорных вычислительных узлов на базе 64-разрядных процессоров [3]. Каждый узел СКИФ К-1000 содержит двухпроцессорную системную плату SMP 2xOpteronTM 248, 2,2 GHz. На суперкомпьютере СКИФ-1000-2 установлена операционная система Linux Fedora 8.0.

Исходя из характеристик процессоров можно предположить, что:

время выполнения последовательной программы на суперкомпьютере соизмеримо со временем выполнения на стандартном персональном компьютере (эксперименты полностью подтвердили это предположение);

• двухпоточное приложение может дать хорошее ускорение для рассматриваемых задач.

МНОГОПОТОЧНЫЕ ПРОГРАММЫ

Для проведения экспериментов на суперкомпьютере СКИФ-1000-2 потребовалась настройка пакета XMD для EAM-потенциала и разработка многопоточного приложения с использованием POSIX Thread Library для потенциалов, предназначенных для полупроводниковых ковалентных материалов.

Сделать однопоточную программу многопоточной гораздо сложнее, чем это может показаться на первый взгляд. Некоторые из возможных трудностей рассмотрены в [4]. Но многопоточные программы отличаются легкостью переноса из-под других операционных систем. Поэтому из разработанной многопоточной Windowsпрограммы несложно было получить аналог для Unix-системы.

ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ

Пакет XMD был настроен для вычисления EAM-потенциалов в многопоточном варианте на суперкомпьютере СКИФ-1000-2. Была также адаптирована многопоточная Windows-программа для полупроводниковых ковалентных материалов.

Некоторые из результатов для задач «Отжиг» и «Диффузия» показаны в таблице.

ЛИТЕРАТУРА

1. XMD – Molecular Dynamics for Metals and Ceramics // [Electronic resource]. March, 2010. Mode of access : http://xmd.sourceforge.net/about.html. Date of access: 30.06.2011.

2. Буза, М. К. Параллельная реализация метода молекулярной динамики на многоядерном процессоре / М. К. Буза, О. М. Кондратьева // Информатика. 2011. № 1. С. 44–51.

3. СКИФ К-500 // [Electronic resource]. 2011. Mode of access : http://skif.pereslavl.ru/skif/index.html.

Date of access : 30.06.2011.

4. Таненбаум, Э. Современные операционные системы / Э. Таненбаум. СПб.: Питер, 2002. 1040 с.

ОСОБЕННОСТИ РЕАЛИЗАЦИИ МЕТОДА МИНИМАЛЬНЫХ

АВТОНОМНЫХ БЛОКОВ НА ВИДЕОКАРТАХ

А. М. Дежурко, С. В. Малый, С. Г. Мулярчик, И. М. Шевкун Белорусский государственный университет E-mail: aliaksandr.dziazhurka@gmail.com В данной статье описывается реализация метода минимальных автономных блоков для расчета электромагнитных полей на видеокартах. Рассмотрены особенности реализации данного метода на графических процессорах с учетом их архитектуры.

Ключевые слова: метод минимальных автономных блоков, вычисления на видеокартах, CUDA, моделирование электромагнитных полей.

ВВЕДЕНИЕ

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

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

ВЫЧИСЛЕНИЯ НА ВИДЕОКАРТАХ

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

Для реализации такой вычислительной парадигмы была изобретена архитектура параллельных вычислений CUDA[3], на данный момент представленная в графических процессорах GeForce, ION, Quadro и Tesla и обеспечивающая необходимую базу разработчикам программного обеспечения. Архитектура CUDA состоит из сотен процессорных ядер, которые работают в связке, чтобы разом справится с набором данных в приложении.

Аппаратной архитектуре параллельных вычислений CUDA сопутствует среда программирования CUDA, которая обеспечивает набор абстракций, позволяющих выражать как параллелизм данных, так и параллелизм задач. Программист сам выбирает средства разработки: языки высокого уровня, такие как C, C++, Fortran или же API OpenCL и DirectX 11 Compute.

Главным успехом вычислений на видеокартах в течение последних нескольких лет стала простота программирования соответствующей модели параллельных вычислений. Благодаря данной модели программирования разработчики могут изменить свои приложения и перенаправить обработку требовательных к ресурсам блоков программ на GPU. Для переноса функции программы на GPU требуется изменение кода функции для включения возможностей параллелизма и добавление ключевых слов «C», позволяющее перенос данных с и на GPU. Задача разработчика – задействовать десятки тысяч потоков одновременно. Аппаратное обеспечение GPU контролирует и планирует потоки.

МЕТОД МИНИМАЛЬНЫХ АВТОНОМНЫХ БЛОКОВ

Конфигурационная сложность и протяженность объектов очень быстро ставят предел прямой формализации, при которой моделируемому объекту в целом сопоставляется краевая задача. Метод автономных блоков позволяет значительно уменьшить вычислительную сложность задачи за счет декомпозиции сложного объекта на независимо анализируемые части, автономные блоки. В результате анализа каждая выделенная подобласть (автономный блок) получает дескриптор, описывающий отклик на всякое граничное возбуждение. Вплотную примыкающие друг к другу блоки можно считать соединенными посредством «виртуальных каналов», волноводов бесконечно малой длины. В рамках общего декомпозиционного подхода не предрешается выбор того или иного метода анализа подобластей, а сами эти подобласти рассматриваются как независимые электродинамические объекты.

При уменьшении размера блока декомпозиция переходит в новый тип дискретизации, названный авторами [1] методом минимальных автономных блоков (МАБ).

В методе минимальных автономных блоков автономные блоки измельчаются, а виртуальные каналы строятся таким образом, что в спектре собственных волн остаются две векторные константы. Это значит, что дескриптор МАБ в виде параллелепипеда представляется матрицей рассеяния двенадцатого порядка – это минимальный порядок дескрипторных матриц.

ОСОБЕННОСТИ РЕАЛИЗАЦИИ МЕТОДА МИНИМАЛЬНЫХ

АВТОНОМНЫХ БЛОКОВ НА ВИДИОКАРТЕ

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

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

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

Для оптимизации доступа к памяти можно использовать механизмы текстурного кэширования, константную память и разделяемую память. Например, в связи с тем, что количество различных автономных блоков ограничено, становится возможным обеспечить быстрый доступ к дескрипторам минимальных автономных блоков за счет хранение матриц дескрипторов в константной памяти, характеризующейся более высокой скоростью доступа. Максимальный объем константной памяти равен 64Kb, что позволяет хранить до 100 различных дескрипторов минимальных автономных блоков.

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

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

Для объединения запроса должны удовлетворяться следующие условия в пределах группы из 16 нитей [2]:

• нити должны обращаться либо к 32-битовым словам, давая при этом в результате один 64-байтовый блок (транзакцию), либо к 64-битовым словам, давая при этом один 128-байтовый блок (транзакцию);

• если используется обращение к 128-битовым словам, то в результате будет выполнено две транзакции, каждая из которых вернет по 128 байт информации;

• нити должны обращаться к элементам памяти последовательно, каждой следующей нити должно соответствовать следующее слово в памяти (некоторые нити могут вообще не обращаться к соответствующим словам);

• все 16 слов должны быть в пределах блока памяти, к которому выполняется

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

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

Сравнительные результаты тестирования программы на CPU и на GPU

ЗАКЛЮЧЕНИЕ

Применение параллельных вычислений на графическом процессоре дает значительный прирост производительности. Из результатов видно, что даже использование не самой мощной графической карты (Geforce GTX 460 768MB) позволяет сократить время моделирования с нескольких часов до нескольких минут.

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

ЛИТЕРАТУРА

1. Никольский, В. В. Декомпозиционный подход к задачам электродинамики / В. В. Никольский. М.:

Наука, 1983. 304 c.

2. Боресков, А. В. Основы работы с технологией CUDA / А. В. Боресков, А. А. Харламов. ДМКПресс, 2010. 232 с.

3. CUDA Technology. URL: http://developer.nvidia.com/category/zone/cuda-zone

НЕЙРОДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

И ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ В ЗАДАЧЕ

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

СИСТЕМОЙ

В работе рассматривается задача оптимального управления динамической системой. Исследуется подход к ее решению на основе нейродинамического программирования с применением приближенного Q-обучения. Предлагается метод декомпозиции пространства состояний динамической системы для параллельного решения данной задачи на многопроцессорной вычислительной системе. В качестве примера рассмотрена задача оптимального по быстродействию управления летательным аппаратом.

Ключевые слова: летательный аппарат, нейродинамическое программирование, оптимальное управление динамической системой.

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

Динамическая система описывается системой обыкновенных дифференциальных уравнений где X = X (t ) = (x1 (t ),x2 (t ), xn (t )) – n-мерный вектор фазовых переменных системы;

U = U (t ) = (u1 (t ),u2 (t ),um (t )) – m-мерный вектор управлений; X 0 – n-мерный вектор начальных условий, t [0, T ] – рассматриваемый период времени. Задано множество допустимых управлений DU, а также множество допустимых значений фазовых переменных D X. Таким образом, полагается, что U DU, X DX. В качестве критерия качества управления используем интегральный функционал вида где f 0 (t, X,U ) – заданная скалярная функция.

Требуется найти вектор управления U * DU, который на решениях системы ОДУ (1) обеспечивает минимум критерия оптимальности (2) при выполнении ограничений на вектор фазовых переменных:

МЕТОД НЕЙРОДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

Одним из методов определения субоптимального управления с помощью нейродинамического программирования является метод Q-обучения [1]. Пусть U – управление, которое из состояния X приводит систему (1) в состояние X и при этом увеличивает текущее значение критерия оптимальности на величину g X,U,X. Процедуру вычисления оптимального значения Q-фактора можно определить как двухшаговую версию уравнения оптимальности Беллмана На каждой итерации алгоритм Q-обучения сохраняет Q-фактор для одной пары состояние-управление, а именно – для текущего наблюдаемого состояния и фактически применяемого управления. Как только оптимальные значения Q-факторов становятся известными, оптимальное управление может быть определено достаточно просто – как решение задачи В классическом варианте процесс Q-обучения реализуют на основе представления значений Q-факторов в табличном виде. Однако, если размерность входного пространства, состоящего из пар состояние-управление, высока или, как в нашем случае, входные переменные непрерывны, использование таблиц может быть недопустимо затратным вследствие требования слишком больших объемов памяти. В такой ситуации для аппроксимации Q-факторов могут быть использованы нейронные сети [2].

При этом алгоритм приближенного Q-обучения может быть записан в следующем виде.

1. Начиная с произвольного вектора весов w0 аппроксимирующей нейронной сети получаем значение Q-фактора Q ( X,U, w0 ).

2. Для итераций i = 1, 2, последовательно выполняем следующие действия.

2а. Для данного вектора весов w нейронной сети определяем оптимальное управление 2б. Определяем значение целевого Q-фактора 2в. Применяем вектор (X i,U i ) в качестве входа нейронной сети, выход которой Qiцел ( X i,U i, w ). Варьируем вектор весов w таким образом, чтобы приблизить величину Q ( X,U,w ) к целевому значению Q цел ( X,U, w ).

2г. Возвращаемся к шагу 2а и повторяем вычисления.

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

ОПРЕДЕЛЕНИЕ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ

ЛЕТАТЕЛЬНЫМ АППАРАТОМ

При решении задачи траекторной безопасности летательного аппарата (ЛА) возникает задача оптимального по быстродействию управления этим аппаратом [3].

Задача оптимального быстродействия является частным случаем задачи оптимального управления. Критерий оптимальности получается в этом случае из критерия оптимальности (2) при f 0 (t, X,U ) 1 и имеет вид Уравнения движения центра масс ЛА в нормальной земной системе координат описывает система нелинейных дифференциальных уравнений [4] Здесь v – скорость ЛА; – угол наклона траектории; – угол поворота траектории; x, y, z – координаты центра масс ЛА; u1 – тангенциальная перегрузка; u 2 – нормальная перегрузка; u 3 – скоростной угол крена; g – ускорение свободного падения. Вектор управления ЛА имеет вид U = (u1, u2, u3 ). На управления наложены ограничения Покроем временной интервал [0, T ] равномерной сеткой t k, k = [0 : N ] с шагом (рис. 1).

Рис.1. Равномерная временная сетка на интервале [0, T ] Зададим постоянные управления на промежутках [tk, tk +1 ] для всех k = [0 : ( N 1)]. В результате значение Q-фактора на i-й итерации определяет вектор состояния ЛА ( vi, i, i, xi, yi, zi ), вектор управления U i = (u1,i, u2,i u3,i ), а также координаты точки x T, y T, z T, в которую требуется перевести ЛА. Структура нейронной сети, аппроксимирующей Q-фактор, представлена на рис. 2.

Рис.2. Структура нейронной сети, аппроксимирующей Q-фактор

РАСПАРАЛЛЕЛИВАНИЕ ВЫЧИСЛЕНИЙ

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

Декомпозицию множества DX можно выполнить многими способами. В рассматриваемой задаче оптимального управления ЛА выполним декомпозицию по координатам центра масс ЛА. Схему декомпозиции для варианта разбиения по координатам x, y иллюстрирует рисунок 3.

Поставим следующую задачу: для каждой из областей j,k построить свою нейронную сеть N j,k ( w j,k ) с вектором весов w j,k, аппроксимирующую значения Q-фактора в этой области.

Положим, что многопроцессорная вычислительная система имеет распределенную память (является вычислительным кластером), число процессорных элементов Pj, k которой равно числу подмножеств j, k. В процессе Q-обучения нейронная сеть N j,k ( w j,k ) обучается независимо на своем процессоре Pj, k. При вычислении значений Q-фактора Qi X i,U, w в области j,k на этапе 2б алгоритма может возникнуть ситуация, когда X i j,k, то есть состояние X i, в которое может перейти динамическая система, не принадлежит данной области, а принадлежит некоторой другой области l, m. В этом случае необходимое приближенное значение Q-фактора запрашивается у процессора Pl, m, обрабатывающего область l,m. Таким образом, данная схема распараллеливания вычислений приводит, вообще говоря, к асинхронным итерациям.

Вычислительный эксперимент показал высокую эффективность данного подхода к распараллеливанию обучения аппроксимирующих нейронных сетей N j,k ( w j,k ).

Рис.3. Декомпозиция двухмерного пространства координат ЛА

ЗАКЛЮЧЕНИЕ

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

ЛИТЕРАТУРА

1. Bertsekas, D. P. Neuro-Dynamic Programming / D. P. Bertsekas, J. N. Tsitsiklis. Athena Scientific.

Bellmont, MA. 1996. P. 59–75.

2. Хайкин, С. Нейронные сети: полный курс. 2-е изд. / С. Хайкин. Вильямс, 2006. C. 778–790.

3. Бердышев, Ю. И. Синтез оптимального по быстродействию управления для одной нелинейной системы четвертого порядка / Ю. И. Бердышев // Прикл. математика и механика, 1975. Т. 39.

Вып. 6. С. 985–994.

4. Воронов, Е. М. Алгоритм оценки границ области достижимости летательного аппарата с учетом тяги / Е. М. Воронов, А. А. Карпунин // Вестник МГТУ. Сер. Приборостроение. 2007. № 4(69).

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

ПРОИЗВОДСТВЕННОЙ СИСТЕМЫ

С ПАРАЛЛЕЛЬНО–ПОСЛЕДОВАТЕЛЬНОЙ ОРГАНИЗАЦИЕЙ

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

Ключевые слова: управляемая производственная система, способ формализации, метод исследования, средства автоматизации моделирования.

АНАЛИЗ РАЗВИТИЯ СИСТЕМ МОДЕЛИРОВАНИЯ



Pages:     | 1 || 3 | 4 |   ...   | 10 |





Похожие работы:

«Сведения об авторе. Сведения о дисциплине Международный консорциум Электронный университет Московский государственный университет экономики, статистики и информатики Евразийский открытый институт М.С. Каменецкая Международное частное право Учебно-практическое пособие Москва 2007 Международное частное право УДК - 341 ББК – 67.412.2 К – 181 Каменецкая М.С. МЕЖДУНАРОДНОЕ ЧАСТНОЕ ПРАВО: Учебно-практическое пособие. – М.: Изд. центр ЕАОИ, 2007. – 306 с. © Каменецкая М.С., 2007 © Евразийский открытый...»

«ІІ. ІСТОРІЯ ФІЛОСОФІЇ Клаус Вигерлинг (Германия)1 К ЖИЗНЕННОЙ ЗНАЧИМОСТИ ФИЛОСОФИИ – ПО ПОВОДУ ОДНОГО СТАРОГО ФИЛОСОФСКОГО ВОПРОСА В статье производится ревизия современного состояния философии, анализируется её значение на основании философского анализа умозаключений, сделанных Гуссерлем, Хёсле. Данная статья подготовлена на основе двух докладов, которые были сделаны в университете Баня-Лука (Босния-Герцоговина). Ключевые слова: философия, жизненный мир, первоосновы, современное состояние...»

«Направление бакалавриата 210100 Электроника и наноэлектроника Профиль подготовки Электронные приборы и устройства СОДЕРЖАНИЕ ИСТОРИЯ ИНОСТРАННЫЙ ЯЗЫК ФИЛОСОФИЯ ЭКОНОМИКА И ОРГАНИЗАЦИЯ ПРОИЗВОДСТВА КУЛЬТУРОЛОГИЯ ПРАВОВЕДЕНИЕ ПОЛИТОЛОГИЯ СОЦИОЛОГИЯ МАТЕМАТИКА ФИЗИКА ХИМИЯ ЭКОЛОГИЯ ИНФОРМАТИКА ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА МЕТОДЫ МАТЕМАТИЧЕСКОЙ ФИЗИКИ ФИЗИЧЕСКИЕ ОСНОВЫ ЭМИССИОННОЙ ЭЛЕКТРОНИКИ И КАТОДЫ СПЕЦИАЛЬНЫЕ ВОПРОСЫ ФИЗИКИ СПЕЦИАЛЬНЫЕ ВОПРОСЫ МАТЕМАТИКИ ОСНОВЫ ТЕОРИИ НАДЁЖНОСТИ ТЕОРИЯ ИНЖЕНЕРНОГО...»

«Отечественный и зарубежный опыт 5. Заключение Вышеизложенное позволяет сформулировать следующие основные выводы. • Использование коллекций ЦОР и ЭОР нового поколения на базе внедрения современных информационных технологий в сфере образовательных услуг является одним из главных показателей развития информационного общества в нашей стране, а их разработка – коренной проблемой информатизации российского образования. • Коллекции ЦОР и ЭОР нового поколения – важный инструмент для повышения качества...»

«Научные исследования подавателей факультета I математики и информатики 70-летию университета посвящается УДК 517.977 Е.А. Наумович ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДЕЯТЕЛЬНОСТИ КАФЕДРЫ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ И ОПТИМАЛЬНОГО УПРАВЛЕНИЯ (1979-2009 гг.) В статье приводятся краткие сведения из истории создания и развития кафедры дифференциальных уравнений и оптимального управления. Сформулированы основные научные направления и наиболее важные результаты, полученные сотрудниками кафедры. Приведена информации...»

«Направление подготовки: 010400.68 Прикладная математика и информатика (очная) Объектами профессиональной деятельности магистра прикладной математики и информатики являются научно - исследовательские центры, государственные органы управления, образовательные учреждения и организации различных форм собственности, использующие методы прикладной математики и компьютерные технологии в своей работе. Магистр прикладной математики и информатики подготовлен к деятельности, требующей углубленной...»

«Кирикчи Василий Павлович Эволюция развития, организация и экономические аспекты внедрения IPTV Специальность: 5А522104 – Цифровое телевидение и радиовещание Диссертация на соискание академической степени магистра Работа рассмотрена Научный руководитель и допускается к защите к.т.н., доцент Абдуазизов А.А. зав. кафедрой ТВ и РВ к.т.н., доцент В.А. Губенко (подпись) (подпись) _ 2012...»

«УДК 621.37 МАХМАНОВ ОРИФ КУДРАТОВИЧ Алгоритмические и программные средства цифровой обработки изображений на основе вейвлет-функций Специальность: 5А330204– Информационные системы диссертация на соискание академической степени магистра Научный руководитель : к.т.н., доцент Хамдамов У. Р. ГОСУДАРСТВЕННЫЙ КОМИТЕТ СВЯЗИ,...»

«Теоретические, организационные, учебно-методические и правовые проблемы ПРАВОВЫЕ ПРОБЛЕМЫ ИНФОРМАТИЗАЦИИ И ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ Д.ю.н., профессор А.В.Морозов, Т.А.Полякова (Департамент правовой информатизации и научнотехнического обеспечения Минюста России) Развитие общества в настоящее время характеризуется возрастающей ролью информационной сферы. В Окинавской Хартии Глобального информационного Общества, подписанной главами “восьмерки” 22 июля 2000 г., государства провозглашают...»

«Предисловие Раздел 1. Общие вопросы методики преподавания  информатики и ИКТ в школе Глава 1. Предмет информатики в школе 1.1. Информатика как наука и как учебный предмет 1.2. История введения предмета информатика в отечественной  школе 1.3. Цели и задачи школьного курса информатики Контрольные вопросы и задания Глава 2. Содержание школьного курса информатики и ИКТ 36   2.1. Общедидактические подходы к определению содержания курса  информатики...»

«министерство образования российской федерации государственное образовательное учреждение московский государственный индустриальный университет информационно-вычислительный центр Информационные технологии и программирование Межвузовский сборник статей Выпуск 3 (8) Москва 2003 ББК 22.18 УДК 681.3 И74 Информационные технологии и программирование: Межвузов ский сборник статей. Вып. 3 (8) М.: МГИУ, 2003. 52 с. Редакционная коллегия: д.ф.-м.н. профессор В.А. Васенин, д.ф.-м.н. профессор А.А. Пярнпуу,...»

«Содержание 1 Организационно-правовое обеспечение образовательной деятельности 2 Структура подготовки магистров 3 Содержание подготовки магистров 3.1. Анализ рабочего учебного плана и рабочих учебных программ 3.2 Организация учебного процесса 3.3 Информационно-методическое обеспечение учебного процесса 3.4 Воспитательная работа 4 Качество подготовки магистров 4.1 Анализ качества знаний студентов по результатам текущей и промежуточной аттестации. 15 4.2 Анализ качества знаний по результатам...»

«УДК 37 ББК 74 М57 Автор: Витторио Мидоро (Институт образовательных технологий Национального исследовательского совета, Италия) Консультант: Нил Батчер (эксперт ЮНЕСКО, ЮАР) Научный редактор: Александр Хорошилов (ИИТО ЮНЕСКО) Руководство по адаптации Рамочных рекомендаций ЮНЕСКО по структуре ИКТ-компетентности М57 учителей (методологический подход к локализации UNESCO ICT-CFT). –М.: ИИЦ Статистика России– 2013. – 72 с. ISBN 978-5-4269-0043-1 Предлагаемое Руководство содержит описание...»

«Зарегистрировано в Минюсте РФ 16 декабря 2009 г. N 15640 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ПРИКАЗ от 9 ноября 2009 г. N 553 ОБ УТВЕРЖДЕНИИ И ВВЕДЕНИИ В ДЕЙСТВИЕ ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО ОБРАЗОВАТЕЛЬНОГО СТАНДАРТА ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ПО НАПРАВЛЕНИЮ ПОДГОТОВКИ 230100 ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА (КВАЛИФИКАЦИЯ (СТЕПЕНЬ) БАКАЛАВР) (в ред. Приказов Минобрнауки РФ от 18.05.2011 N 1657, от 31.05.2011 N 1975) КонсультантПлюс: примечание. Постановление...»

«Н. В. Максимов, Т. Л. Партыка, И. И. Попов АРХИТЕКТУРА ЭВМ И ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ Рекомендовано Министерством образования Российской Федерации в качестве учебника для студентов учреждений среднего профессионального образования, обучающихся по группе специальностей 2200 Информатика и вычислительная техника Москва ФОРУМ - ИНФРА-М 2005 УДК 004.2(075.32) ББК 32.973-02я723 М17 Рецензенты: к т. н, доцент кафедры Проектирование АИС РЭА им. Г. В. Плеханова Ю. Г Бачинин, доктор экономических наук,...»

«Зарегистрировано в Минюсте РФ 28 апреля 2010 г. N 17035 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ПРИКАЗ от 29 марта 2010 г. N 224 ОБ УТВЕРЖДЕНИИ И ВВЕДЕНИИ В ДЕЙСТВИЕ ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО ОБРАЗОВАТЕЛЬНОГО СТАНДАРТА ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ПО НАПРАВЛЕНИЮ ПОДГОТОВКИ 021300 КАРТОГРАФИЯ И ГЕОИНФОРМАТИКА (КВАЛИФИКАЦИЯ (СТЕПЕНЬ) МАГИСТР) КонсультантПлюс: примечание. Постановление Правительства РФ от 15.06.2004 N 280 утратило силу в связи с изданием Постановления...»

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В.ЛОМОНОСОВА ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ А.М. ДЕНИСОВ, А.В. РАЗГУЛИН ОБЫКНОВЕННЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ Часть 2 МОСКВА 2009 г. Пособие отражает содержание второй части лекционного курса Обыкновенные дифференциальные уравнения, читаемого студентам факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносова в соответствии с программой по специальности Прикладная математика и информатика. c Факультет...»

«ТЕОРИЯ И МЕТОДОЛОГИЯ УДК 336.722.112:316 Т. А. Аймалетдинов О ПОДХОДАХ К ИССЛЕДОВАНИЮ ЛОЯЛЬНОСТИ КЛИЕНТОВ В БАНКОВСКОЙ СФЕРЕ АЙМАЛЕТДИНОВ Тимур Алиевич - директор по исследованиям ЗАО НАФИ, кандидат социологических наук, доцент кафедры социальной и педагогической информатики РГСУ. Email: aimaletdinov@nacfin.ru Аннотация. В статье приводится обзор классических и современных подходов к теоретической интерпретации и эмпирическим исследованиям лояльности клиентов к банкам. На основе анализа...»

«МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ СТАВРОПОЛЬСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ УТВЕРЖДАЮ Проректор по учебной и воспитательной работе И. В. Атанов _2013 г. ОТЧЕТ о самообследовании основной образовательной программы высшего образования Направление подготовки: 230700.68 - Прикладная информатика Профиль: 230700.68.01 Системы корпоративного управления (код, наименование...»

«ДОКЛАДЫ БГУИР №2 ЯНВАРЬ–МАРТ 2004 УДК 538.945 НАНОЭЛЕКТРОНИКА И НАНОТЕХНОЛОГИЯ В БЕЛОРУССКОМ ГОСУДАРСТВЕННОМ УНИВЕРСИТЕТЕ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ: ОТ ПЕРВЫХ ШАГОВ ДО СЕГОДНЯШНЕГО ДНЯ В.Е. БОРИСЕНКО Белорусский государственный университет информатики и радиоэлектроники П. Бровки, 6, Минск, 220013, Беларусь Поступила в редакцию 19 ноября 2003 Представлены основные этапы развития работ по наноэлектронике и нанотехнологии в БГУИР. Показаны организационная структура научных исследований и...»







 
© 2014 www.kniga.seluk.ru - «Бесплатная электронная библиотека - Книги, пособия, учебники, издания, публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.