|
|
| (не показано 29 промежуточных версий 2 участников) |
| Строка 17: |
Строка 17: |
| | Здесь <math>\{(\theta_j, \eta_j)\}</math>, <math>j\ge1</math>, -- последовательность независимых одинаково распределенных двумерных случайных векторов таких, что <math>0 < \eta_1 < 1</math>; <math>0 < \theta_1 < 1</math> почти наверное. Начальная надежность <math>p_0</math> считается заданной, случайные величины <math>\eta_j</math> (параметры <<дефективности>>) и <math>\theta_j</math> (параметры <<эффективности>>) описывают соответственно возможное уменьшение и повышение надежности. | | Здесь <math>\{(\theta_j, \eta_j)\}</math>, <math>j\ge1</math>, -- последовательность независимых одинаково распределенных двумерных случайных векторов таких, что <math>0 < \eta_1 < 1</math>; <math>0 < \theta_1 < 1</math> почти наверное. Начальная надежность <math>p_0</math> считается заданной, случайные величины <math>\eta_j</math> (параметры <<дефективности>>) и <math>\theta_j</math> (параметры <<эффективности>>) описывают соответственно возможное уменьшение и повышение надежности. |
| | | | |
| − | Обозначим <math>\lambda = 1 - {\sf E}\theta_j</math>, <math>\mu = {\sf E}\eta_j</math>. | + | Обозначим <math>\lambda = 1 - {E}\theta_j</math>, <math>\mu = {E}\eta_j</math>. |
| − | В книге \cite{KS2006} доказано, что при условии <math>\lambda+\mu\neq1</math> | + | В книге <ref> Королев В. Ю., Соколов И. А. Основы математической теории надежности модифицируемых систем. --- М.: ИПИ РАН, 2006. 102~с. </ref> доказано, что при условии <math>\lambda+\mu\neq1</math> |
| − | <math>p=\lim_{j\to\infty}\e p_j = \frac{\mu}{\lambda+\mu}.</math> | + | <math> |
| | + | p=\lim_{j\to\infty}E p_j = \frac{\mu}{\lambda+\mu}. |
| | + | </math> |
| | Величина <math>p</math> характеризует асимптотическое значение надежности системы в рамках некоторой рекуррентной модели, задаваемой набором <math>\{(\theta_j, \eta_j)\}</math>. | | Величина <math>p</math> характеризует асимптотическое значение надежности системы в рамках некоторой рекуррентной модели, задаваемой набором <math>\{(\theta_j, \eta_j)\}</math>. |
| | | | |
| − | В рамках байесовского подхода в постановке задач теории надежности можно рассмотреть более сложную ситуацию, где основные параметры системы $\lambda$ и $\mu$ предполагаются случайными. В таком случае наиболее естественной и удобной для изучения характеристикой является усредненное значение предельной надежности, то есть | + | В рамках байесовского подхода в постановке задач теории надежности можно рассмотреть более сложную ситуацию, где основные параметры системы <math>\lambda </math> и <math>\mu </math> предполагаются случайными. В таком случае наиболее естественной и удобной для изучения характеристикой является усредненное значение предельной надежности, то есть |
| − | $$p_{\mbox{\tiny сред}} = \e p = \e \frac{\mu}{\lambda+\mu},$$
| + | <math> |
| − | где усреднение ведется по совместному распределению случайных величин $\lambda$ и $\mu$. | + | p_{average} = Ep = E\frac{\mu}{\lambda+\mu}, |
| | + | </math> |
| | + | где усреднение ведется по совместному распределению случайных величин <math>\lambda </math> и <math>\mu </math>. |
| | | | |
| − | Так как случайные величины $\eta_1$ и $\theta_1$ удовлетворяют ограничениям $0 < \eta_1 < 1$, $0 < \theta_1 < 1$, средние значения $\lambda$ и $\mu$ величин $1 - \e\theta_j$ и $\e\eta_j$ соответственно также находятся на отрезке $[0,1]$. Поэтому в качестве априорных распределений параметров $\lambda$ и $\mu$ следует выбирать только распределения, сосредоточенные на $[0,1]$. | + | Так как случайные величины <math>\eta_1 </math> и <math>\theta_1 </math> удовлетворяют ограничениям <math>0 < \eta_1 < 1, 0 < \theta_1 < 1 </math>, средние значения <math>\lambda </math> и <math>\mu </math> величин <math>1 - E\theta_j </math> и <math>E\eta_j </math> соответственно также находятся на отрезке [0,1]. В частном случае, рассмотрим независимые случайные параметры <math>\lambda </math> и <math>\mu </math>, имеющие параболические распределения на некоторых (вообще говоря, разных) отрезках, являющихся подмножествами отрезка [0,1]. |
| − | | |
| − | Далее будут рассмотрены независимые случайные параметры $\lambda$ и $\mu$, имеющие параболические распределения на некоторых (вообще говоря, разных) отрезках, являющихся подмножествами отрезка $[0,1]$.
| |
| − | | |
| − | \ \
| |
| − | | |
| − | {\bf 2 Основные результаты}
| |
| − | | |
| − | \ \
| |
| − | | |
| − | Итак, пусть средний параметр <<эффективности>> $\lambda$ и средний параметр <<дефективности>> $\mu$ независимы и имеют параболическое распределение $P(a_\lambda, b_\lambda)$, $0\le a_\lambda<b_\lambda\le1$, и $P(a_\mu, b_\mu)$, $0\le a_\mu<b_\mu\le1$, соответственно.
| |
| − | \ \
| |
| − | | |
| − | \ \
| |
| − | Для плотности $f_\xi(x)$ некоторой случайной величины $\xi$, имеющей параболическое распределение с параметрами $(a_\xi, b_\xi)$, справедливо:
| |
| − | \begin{equation}\label{Density Parabolic}
| |
| − | f_\xi(x) = \frac{6(x-a_\xi)(b_\xi-x)}{(b_\xi-a_\xi)^3},\ \ \ \ x\in[a_\xi, b_\xi].
| |
| − | \end{equation}
| |
| − | | |
| − | Заметим, что плотность параболического распределения может быть представлена в виде полинома:
| |
| − | $$f_\xi(x)=\sum_{i=0}^{2}c_{\xi,i}\, x^i\cdot\I(x\in[a_\xi,b_\xi]),$$
| |
| − | где \ \ \ $$c_{\xi,0} = - \frac{6a_\xi b_\xi}{(b_\xi-a_\xi)^3},\ \ \ \
| |
| − | c_{\xi,1} = \frac{6(a_\xi + b_\xi)}{(b_\xi-a_\xi)^3},\ \ \ \ c_{\xi,2} =- \frac{6}{(b_\xi-a_\xi)^3}.$$
| |
| − | | |
| − | Очевидно, что при байесовском подходе вычисление вероятностных характеристик надежности $p = \mu/{(\lambda+\mu)}$ удобно производить, базируясь на известном распределении величины $\rho=\lambda/\mu$. В работе \cite{K2016} были получены формулы для плотности распределения случайной величины $\rho$ в предположении, что плотности параметров $\lambda$ и $\mu$ имеют полиномиальный вид.
| |
| − | Основываясь на характеристиках распределения параметра~$\rho$ и учитывая, что $p =1/(1+\rho),$
| |
| − | имеем для функции распределения и плотности $p$ следующие соотношения:
| |
| − | $$F_p(x)=1-F_\rho\left(\frac{1-x}{x}\right)\ \ \ \ \mbox{и} \ \ \ \
| |
| − | f_p=\frac{1}{x^2}f_\rho\left(\frac{1-x}{x}\right).$$
| |
| − | | |
| − | | |
| − | Введем обозначение:
| |
| − | $$L(a,b,x)=\frac{1}{x^2} \il{a}{b}{y}\fl\Bigg({1-x\over x}\cdot y\Bigg)\fm(y)\, dy =$$
| |
| − | %$$= \frac{1}{x^2}\il{a}{b}\sum_{i=0}^{2}\sum_{j=0}^{2}c_{\lambda,i}c_{\mu,j}\, \Bigg(\frac{1-x}{x}\Bigg)^{i}y^{i+j+1}\, dy=$$
| |
| − | \begin{equation}\label{Integral_General}
| |
| − | =\sum_{i=0}^{2}\sum_{j=0}^{2}c_{\lambda,i}c_{\mu,j}
| |
| − | \frac{b^{i+j+2}-a^{i+j+2}}{i+j+2}\cdot {(1-x)^i\over x^{i+2}},
| |
| − | \end{equation}
| |
| − | где $a$ и $b$ одновременно принадлежат отрезкам $[a_\mu,b_\mu]$ и $[a_\lambda/x,b_\lambda/x]$.
| |
| − | | |
| − | Рассмотрев всевозможные комбинации взаимного расположения точек $a_\mu$, $b_\mu$, $a_\lambda/x$, $b_\lambda/x$ на отрезке $[0,1]$, убеждаемся в справедливости следующего утверждения.
| |
| − | \ \
| |
| − | | |
| − | {\bf Теорема 1.} {\it Пусть независимые случайные величины $\lambda$ и $\mu$ имеют параболическое распределение, а их плотности $\fl(x)$ и $\fm(x)$ определяются соотношением (\ref{Density Parabolic}) с соответствующими параметрами.
| |
| − | Тогда случайная величина $p = {{\mu}/{(\lambda+\mu)}}$ имеет плотность
| |
| − | $$f_p(x)=\I\left(\frac{\am}{\bl+\am}<x\le\min\left\{\frac{\am}{\al+\am},\frac{\bm}{\bm+\bl}\right\}\right)L\Bigg(\am,\frac{x\bl}{1-x},x\Bigg)+$$
| |
| − | $$+\I\left(\frac{\bm}{\bl+\bm}<x\le\frac{\am}{\al+\am}\right)L(\am,\bm,x)+$$
| |
| − | $$+\I\left(\frac{\am}{\al+\am}<x\le\frac{\bm}{\bl+\bm}\right)L\Bigg(\frac{x\al}{1-x},\frac{x\bl}{1-x},x\Bigg)+$$
| |
| − | $$ %\begin{equation}\label{Density_rho_Polynomial_case}
| |
| − | +\I\left(\max\left\{\frac{\am}{\am+\al},\frac{\bm}{\bm+\bl}\right\}<x\le\frac{\bm}{\al+\bm}\right)L\Bigg(\frac{x\al}{1-x},\bm,x\Bigg),
| |
| − | $$ %\end{equation}
| |
| − | где величины $L(a,b,x)$ определены соотношением (\ref{Integral_General}).
| |
| − | }
| |
| − | | |
| − | Введем дополнительное обозначение:
| |
| − | \begin{multline}\label{Integral_J}
| |
| − | J_\xi(d,b)=\sum_{i=0}^{2}\sum_{j=0}^{2}c_{\lambda,i}c_{\mu,j}\frac{d^{i+j+2}}{i+j+2}\times\\
| |
| − | \times\sum_{k=0}^{l_\xi}C_{l_\xi}^k(-1)^k \Bigg[\I\left(k\neq l_\xi\right)\frac{b^{k-l_\xi}}{k-l_\xi}+\I\left(k=l_\xi\right)\ln \,b\Bigg].
| |
| − | \end{multline}
| |
| − | Здесь при значении случайной величины $\xi$ равном $\lambda$, $l_\lambda=i$, а при $\xi\equiv\mu$, $l_\mu=j+1$.
| |
| − | | |
| − | %\begin{multline}\label{Integral_J}
| |
| − | %J(d,b)=\sum_{i=0}^{2}\sum_{j=0}^{2}c_{\lambda,i}c_{\mu,j}\frac{d^{i+j+2}}{i+j+2}\times\\
| |
| − | %\times\sum_{k=0}^{j+1}C_{j+1}^k(-1)^k \Bigg[\I\left(k\neq j+1\right)\frac{b^{k-j-1}}{k-j-1}+\I\left(k=j+1\right)\ln \, %b\Bigg].
| |
| − | %\end{multline}
| |
| − | | |
| − | Воспользовавшись теоремой~1 для вычисления средней надежности системы
| |
| − | $$p_{\mbox{\tiny сред}} = \e p =\int x f_p(x)\,dx,$$
| |
| − | убеждаемся в справедливости следующего утверждения.
| |
| − | | |
| − | {\bf Теорема 2.} {\it Пусть средний параметр <<эффективности>> $\lambda$ и средний параметр <<дефективности>> $\mu$ удовлетворяют условиям теоремы~1. Тогда средняя предельная надежность системы имеет вид
| |
| − | $$p_{\mbox{\tiny сред}}=J_\mu\Bigg(b_\lambda,\frac{b_\lambda}{b_\lambda+a_\mu}\Bigg) + J_\mu\Bigg(a_\lambda, \frac{a_\lambda}{a_\lambda+b_\mu}\Bigg)+ J_\lambda\Bigg(a_\mu,\frac{a_\mu}{b_\lambda+a_\mu}\Bigg)+$$
| |
| − | $$+ J_\lambda\Bigg(b_\mu,\frac{b_\mu}{a_\lambda+b_\mu}\Bigg)-J_\lambda\Bigg(a_\mu,\frac{a_\mu}{a_\lambda+a_\mu}\Bigg) -J_\lambda\Bigg(b_\mu,\frac{b_\mu}{b_\lambda+b_\mu}\Bigg)-$$
| |
| − | \begin{equation}\label{Mean}
| |
| − | - J_\mu\Bigg(b_\lambda, \frac{b_\lambda}{b_\lambda+b_\mu}\Bigg) - J_\mu\Bigg(a_\lambda, \frac{a_\lambda}{a_\lambda+a_\mu}\Bigg),
| |
| − | \end{equation}
| |
| − | где величины $J_\lambda(d,b)$ и $J_\mu(d,b)$ определены соотношением (\ref{Integral_J}).
| |
| − | }
| |
| − | | |
| − | \ \
| |
| | | | |
| | + | Итак, пусть средний параметр <<эффективности>> <math>\lambda </math> и средний параметр <<дефективности>> <math>\mu </math> независимы и имеют параболическое распределение <math>P(a_\lambda, b_\lambda) </math>, <math>0\le a_\lambda<b_\lambda\le1 </math>, и <math>P(a_\mu, b_\mu) </math>, <math>0\le a_\mu<b_\mu\le1 </math>, соответственно. |
| | | | |
| | + | Для плотности <math>f_\xi(x) </math> некоторой случайной величины <math>\xi </math>, имеющей параболическое распределение с параметрами <math>(a_\xi, b_\xi) </math>, справедливо: |
| | + | <math> f_\xi(x) = \frac{6(x-a_\xi)(b_\xi-x)}{(b_\xi-a_\xi)^3},\ \ \ \ x\in[a_\xi, b_\xi]. </math> |
| | | | |
| | == Вычислительное ядро алгоритма == | | == Вычислительное ядро алгоритма == |
| | Пусть рассматривается изменение надежности группы однотипных системы на интервале времени [0, T]. | | Пусть рассматривается изменение надежности группы однотипных системы на интервале времени [0, T]. |
| − | Для каждой системы моделируем модификации, происходящие в случайные моменты времени t:t<T, следующим образом:
| |
| − | 1. Генерируем случайные величины
| |
| − |
| |
| − | lambda = parab_random_variable(a_l,b_l);
| |
| − | mu = parab_random_variable(a_m,b_m);
| |
| − | if ((lambda == 7) or (mu == 7))
| |
| − | {
| |
| − | kol2 = kol2 - 1;
| |
| − | p[i] = 0;
| |
| − | continue;
| |
| − | }
| |
| − | // cout << "lambda = "<<lambda<< " mu = "<< mu << endl;
| |
| − | //lambda = 1 - E_tetta = 1 - (a_t + b_t)/2 => a_t = - 2*lambda + 2 - b_t
| |
| − | //mu = E_etta = (b_e + a_e)/2 => a_e = 2*lambda - b_e, ãäå b_e = 1
| |
| − | long double b_t = 1;
| |
| − | long double b_e = 1;
| |
| − | long double a_e, a_t;
| |
| − | /*a_t = -2*lambda + 2 - b_t;
| |
| − | if (a_t < 0)
| |
| − | {
| |
| − | a_t = 0;
| |
| − | a_t_0 = a_t_0 + 1;
| |
| − | }
| |
| − | a_e = -2*mu + b_e;
| |
| − | if (a_e < 0)
| |
| − | {
| |
| − | a_e = 0;
| |
| − | a_e_0 = a_e_0 + 1;
| |
| − | }
| |
| − | */
| |
| − | a_t = 1-lambda-eps/2;
| |
| − | a_e = mu-eps/2;
| |
| − | b_t = a_t+eps/2;
| |
| − | b_e = a_e+eps/2;
| |
| − |
| |
| − | if (a_t<0)
| |
| − | { a_t = 0; }
| |
| − | if (a_e<0)
| |
| − | { a_e = 0; }
| |
| − | if (b_t>1)
| |
| − | { b_t = 1; }
| |
| − | if (b_e>1)
| |
| − | { b_e = 1; }
| |
| − |
| |
| − |
| |
| − | // cout <<"a_t = " <<a_t << endl;
| |
| − | // cout <<"a_e = " <<a_e << endl;
| |
| − |
| |
| − | p[i] = rand();
| |
| − | p[i] = double(p[i]/RAND_MAX); // îò 0 äî 1
| |
| − | long double etta; // ïàðàìåòð äåôôåêòèâíîñòè ÐÁ
| |
| − | long double tetta; // ïàðàìåòð ýôôåêòèâíîñòè ÐÁ
| |
| − | long double t = 0;
| |
| − | int z = 0;
| |
| − | do
| |
| − | {
| |
| − | z++;
| |
| − | t += rand(); // ãåíåðèðóåì âðåìÿ ìîäèôèêàöèè
| |
| − | etta = rand();
| |
| − | etta = (etta*(b_e - a_e))/RAND_MAX + a_e; //ÍÀÄÎ ãåíåðèñòü ðàâíîìåðíîå ðàñïðåäåëåíèå íà îòðåçêå a , b=1
| |
| − | tetta = rand();
| |
| − | tetta = (tetta*(b_t - a_t))/RAND_MAX + a_t;
| |
| − | p[i] = etta*p[i] + tetta*(1-p[i]);
| |
| − | //cout<<p[i]<<" ";
| |
| − | }
| |
| − | while(t<my_time);
| |
| − | //
| |
| − |
| |
| − |
| |
| − |
| |
| | | | |
| | + | '''1.''' Для каждой системы моделируем модификации, происходящие в случайные моменты времени <math>t_j: \sum_{j}t_j <= T</math>, следующим образом: |
| | | | |
| | + | * Генерируем реализацию случайных величин <math>\lambda </math>, <math>\mu </math> с параболическим распределением на заданных интервалах <math>[a_\lambda, b_\lambda], [a_\mu, b_\mu]</math> соответственно. Задаем начальную надежность системы, как реализацию случайной величины с равномерным на [0,1] распределением. |
| | | | |
| | + | * Пока <math> \sum_{j}t_j <= T </math>, моделируем поступления модификаций в систему в момент времени <math>t_j</math>: генерируем реализацию случайных величин <math>\theta_j </math>, <math>\eta_j </math> таких, что <math>\lambda = 1 - {E}\theta_j</math>, <math>\mu = {E}\eta_j</math>, изменяем надежность системы по формуле <math> p_{j+1} = \eta_{j+1}p_j + \theta_{j+1}(1-p_j).</math> |
| | | | |
| | + | '''2.''' Вычисляем усредненную надежность группы однотипных систем после всех модификаций. |
| | | | |
| | == Макроструктура алгоритма == | | == Макроструктура алгоритма == |
| − | Если алгоритм использует в качестве составных частей другие алгоритмы, то это указывается в данном разделе. Если в дальнейшем имеет смысл описывать алгоритм не в максимально детализированном виде (т.е. на уровне арифметических операций), а давать только его макроструктуру, то здесь описывается структура и состав макроопераций. Если в других разделах описания данного алгоритма в рамках AlgoWiki используются введенные здесь макрооперации, то здесь даются пояснения, необходимые для однозначной интерпретации материала. Типичные варианты макроопераций, часто встречающиеся на практике: нахождение суммы элементов вектора, скалярное произведение векторов, умножение матрицы на вектор, решение системы линейных уравнений малого порядка, сортировка, вычисление значения функции в некоторой точке, поиск минимального значения в массиве, транспонирование матрицы, вычисление обратной матрицы и многие другие.
| + | Основную часть алгоритма составляет расчет надежности модифицируемых объектов после каждой модификации. Могут быть рассмотрены другие априорные распределения параметров <math>\lambda</math> и <math>\mu</math> в рамках данной модели или совершенно другие математические модели, описывающие изменение надежности сложных модифицируемых систем. |
| − | | |
| − | Описание макроструктуры очень полезно на практике. Параллельная структура алгоритмов может быть хорошо видна именно на макроуровне, в то время как максимально детальное отображение всех операций может сильно усложнить картину. Аналогичные аргументы касаются и многих вопросов реализации, и если для алгоритма эффективнее и/или технологичнее оставаться на макроуровне, оформив макровершину, например, в виде отдельной процедуры, то это и нужно отразить в данном разделе.
| |
| − | Выбор макроопераций не однозначен, причем, выделяя различные макрооперации, можно делать акценты на различных свойствах алгоритмов. С этой точки зрения, в описании одного алгоритма может быть представлено несколько вариантов его макроструктуры, дающих дополнительную информацию о его структуре. На практике, подобные альтернативные формы представления макроструктуры алгоритма могут оказаться исключительно полезными для его эффективной реализации на различных вычислительных платформах.
| |
| | | | |
| | == Схема реализации последовательного алгоритма == | | == Схема реализации последовательного алгоритма == |
| − | Здесь описываются все шаги, которые нужно выполнить при последовательной реализации данного алгоритма. В некотором смысле, данный раздел является избыточным, поскольку математическое описание уже содержит всю необходимую информацию. Однако он, несомненно, полезен: схема реализации алгоритма выписывается явно, помогая однозначной интерпретации приводимых далее оценок и свойств.
| |
| − |
| |
| − | Описание может быть выполнено в виде блок-схемы, последовательности математических формул, обращений к описанию других алгоритмов, фрагмента кода на Фортране, Си или другом языке программирования, фрагмента кода на псевдокоде и т.п. Главное - это сделать схему реализации последовательного алгоритма полностью понятной. Совершенно не обязательно все шаги детализировать до элементарных операций, отдельные шаги могут соответствовать макрооперациям, отвечающим другим алгоритмам.
| |
| − |
| |
| − | Описание схемы реализации вполне может содержать и словесные пояснения, отражающие какие-либо тонкие нюансы самого алгоритма или его реализации. Уже в данном разделе можно сказать про возможный компромисс между объемом требуемой оперативной памяти и временем работы алгоритма, между используемыми структурами данных и степенью доступного параллелизма. В частности, часто возникает ситуация, когда можно ввести дополнительные временные массивы или же отказаться от использования специальных компактных схем хранения данных, увеличивая степень доступного параллелизма.
| |
| | | | |
| | + | Схема реализации последовательного алгоритма приведена в [[#Вычислительное ядро алгоритма|описании вычислительного ядра алгоритма]]. |
| | + | |
| | == Последовательная сложность алгоритма == | | == Последовательная сложность алгоритма == |
| − | В данном разделе описания свойств алгоритма приводится оценка его [[глоссарий#Последовательная сложность|''последовательной сложности'']], т.е. числа операций, которые нужно выполнить при последовательном исполнении алгоритма (в соответствии с [[#Описание схемы реализации последовательного алгоритма|п.1.5]]). Для разных алгоритмов понятие операции, в терминах которой оценивается его сложность, может существенно различаться. Это могут быть операции для работы с вещественными числами, целыми числами, поразрядные операции, обращения в память, обновления элементов массива, элементарные функции, макрооперации и другие. В LU-разложении преобладают арифметические операции над вещественными числами, а для транспонирования матриц важны лишь обращения к памяти: это и должно найти отражение в описании.
| + | * <math>[0;T]</math> - рассматриваемый временной интервал; |
| − | | + | * <math>N</math> - количество модифицируемых систем. |
| − | Если выбор конкретного типа операций для оценки сложности алгоритма не очевиден, то нужно привести обоснование возможных вариантов. В некоторых случаях можно приводить оценку не всего алгоритма, а лишь его вычислительного ядра: в таком случае это нужно отметить, сославшись [[#Общее описание алгоритма|на п.1.1]].
| + | Тогда для вычисления средней надежности <math>N</math> модифицируемых объектов за время <math>T</math> в последовательном (наиболее медленном) варианте требуется: |
| − | | + | * <math>N(34+6T)+1</math> сложений (вычитаний), |
| − | Например, сложность алгоритма суммирования элементов вектора сдваиванием равна <math>n-1</math>. Сложность быстрого преобразования Фурье (базовый алгоритм Кули-Тьюки) для векторов с длиной, равной степени двойки – <math>n\log_2n</math> операций комплексного сложения и <math>(n\log_2n)/2</math> операций комплексного умножения. Сложность базового алгоритма разложения Холецкого (точечный вариант для плотной симметричной и положительно-определенной матрицы) это <math>n</math> вычислений квадратного корня, <math>n(n-1)/2</math> операций деления, по <math>(n^3-n)/6</math> операций умножения и сложения (вычитания).
| + | * <math>N(51+5T)</math> умножений. |
| | | | |
| | == Информационный граф == | | == Информационный граф == |
| − | Это очень важный раздел описания. Именно здесь можно показать (увидеть) как устроена параллельная структура алгоритма, для чего приводится описание и изображение его информационного графа ([[глоссарий#Граф алгоритма|''графа алгоритма'']] <ref name="VVVVVV">Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с. </ref>). Для рисунков с изображением графа будут составлены рекомендации по их формированию, чтобы все информационные графы, внесенные в энциклопедию, можно было бы воспринимать и интерпретировать одинаково. Дополнительно можно привести полное параметрическое описание графа в терминах покрывающих функций <ref name="VVVVVV" />.
| + | [[Файл:инф_граф.png]] |
| | | | |
| − | Интересных вариантов для отражения информационной структуры алгоритмов много. Для каких-то алгоритмов нужно показать максимально подробную структуру, а иногда важнее макроструктура. Много информации несут разного рода проекции информационного графа, выделяя его регулярные составляющие и одновременно скрывая несущественные детали. Иногда оказывается полезным показать последовательность в изменении графа при изменении значений внешних переменных (например, размеров матриц): мы часто ожидаем "подобное" изменение информационного графа, но это изменение не всегда очевидно на практике.
| + | Описание информационного графа: |
| | | | |
| − | В целом, задача изображения графа алгоритма весьма нетривиальна. Начнем с того, что это потенциально бесконечный граф, число вершин и дуг которого определяется значениями внешних переменных, а они могут быть весьма и весьма велики. В такой ситуации, как правило, спасают упомянутые выше соображения подобия, делающие графы для разных значений внешних переменных "похожими": почти всегда достаточно привести лишь один граф небольшого размера, добавив, что графы для остальных значений будут устроены "точно также". На практике, увы, не всегда все так просто, и здесь нужно быть аккуратным.
| + | * Красная вершина графа обозначает начальный блок программы, в котором задаются входные данные и вычисляются общие для всех модифицируемых объектов характеристики. |
| | | | |
| − | Далее, граф алгоритма - это потенциально многомерный объект. Наиболее естественная система координат для размещения вершин и дуг информационного графа опирается на структуру вложенности циклов в реализации алгоритма. Если глубина вложенности циклов не превышает трех, то и граф размещается в привычном трехмерном пространстве, однако для более сложных циклических конструкций с глубиной вложенности 4 и больше необходимы специальные методы представления и изображения графов.
| + | * Желтые вершины графа обозначают выполнение одной модификации для одной модифицируемой системы. Так как для разных объектов количество модификаций, вообще говоря, различно, количество желтых вершин в параллельных нитях графа различно. |
| | | | |
| − | В данном разделе AlgoWiki могут использоваться многие интересные возможности, которые еще подлежат обсуждению: возможность повернуть граф при его отображении на экране компьютера для выбора наиболее удобного угла обзора, разметка вершин по типу соответствующим им операций, отражение [[глоссарий#Ярусно-параллельная форма графа алгоритма|''ярусно-параллельной формы графа'']] и другие. Но в любом случае нужно не забывать главную задачу данного раздела - показать информационную структуру алгоритма так, чтобы стали понятны все его ключевые особенности, особенности параллельной структуры, особенности множеств дуг, участки регулярности и, напротив, участки с недерминированной структурой, зависящей от входных данных.
| + | * Зеленые вершины графа обозначают заключительный этап вычислений для каждого модифицируемого объекта. На этом этапе происходит вычисление надежности объекта после последней модификации. |
| | | | |
| − | На рис.1 показана информационная структура алгоритма умножения матриц, на рис.2 - информационная структура одного из вариантов алгоритма решения систем линейных алгебраических уравнений с блочно-двухдиагональной матрицей.
| + | * Синяя вершина графа обозначает заключительный участок выполнения программы, на котором происходит вычисление усредненной надежности по всем модифицируемым объектам. |
| − | | |
| − | [[file:Fig1.svg|thumb|center|300px|Рис.1. Информационная структура алгоритма умножения матриц]]
| |
| − | [[file:Fig2.svg|thumb|center|300px|Рис.2. Информационная структура одного из вариантов алгоритма решения систем линейных алгебраических уравнений с блочно-двухдиагональной матрицей]]
| |
| | | | |
| | == Ресурс параллелизма алгоритма == | | == Ресурс параллелизма алгоритма == |
| − | Здесь приводится оценка [[глоссарий#Параллельная сложность|''параллельной сложности'']] алгоритма: числа шагов, за которое можно выполнить данный алгоритм в предположении доступности неограниченного числа необходимых процессоров (функциональных устройств, вычислительных узлов, ядер и т.п.). Параллельная сложность алгоритма понимается как высота канонической ярусно-параллельной формы <ref name="VVVVVV" />. Необходимо указать, в терминах каких операций дается оценка. Необходимо описать сбалансированность параллельных шагов по числу и типу операций, что определяется шириной ярусов канонической ярусно-параллельной формы и составом операций на ярусах.
| + | Ресурс параллелизма алгоритма заключается в независимости модифицируемых объектов. Таким образом на разных процессах могут происходить вычисления для разных объектов независимо друг от друга. |
| − | | |
| − | Параллелизм в алгоритме часто имеет естественную иерархическую структуру. Этот факт очень полезен на практике, и его необходимо отразить в описании. Как правило, подобная иерархическая структура параллелизма хорошо отражается в последовательной реализации алгоритма через циклический профиль результирующей программы (конечно же, с учетом графа вызовов), поэтому циклический профиль ([[#Описание схемы реализации последовательного алгоритма|п.1.5]]) вполне может быть использован и для отражения ресурса параллелизма.
| |
| − | | |
| − | Для описания ресурса параллелизма алгоритма (ресурса параллелизма информационного графа) необходимо указать ключевые параллельные ветви в терминах [[глоссарий#Конечный параллелизм|''конечного'']] и [[глоссарий#Массовый параллелизм|''массового'']] параллелизма. Далеко не всегда ресурс параллелизма выражается просто, например, через [[глоссарий#Кооодинатный параллелизм|''координатный параллелизм'']] или, что то же самое, через независимость итераций некоторых циклов (да-да-да, циклы - это понятие, возникающее лишь на этапе реализации, но здесь все так связано… В данном случае, координатный параллелизм означает, что информационно независимые вершины лежат на гиперплоскостях, перпендикулярных одной из координатных осей). С этой точки зрения, не менее важен и ресурс [[глоссарий#Скошенный параллелизм|''скошенного параллелизма'']]. В отличие от координатного параллелизма, скошенный параллелизм намного сложнее использовать на практике, но знать о нем необходимо, поскольку иногда других вариантов и не остается: нужно оценить потенциал алгоритма, и лишь после этого, взвесив все альтернативы, принимать решение о конкретной параллельной реализации. Хорошей иллюстрацией может служить алгоритм, структура которого показана на рис.2: координатного параллелизма нет, но есть параллелизм скошенный, использование которого снижает сложность алгоритма с <math>n\times m</math> в последовательном случае до <math>(n+m-1)</math> в параллельном варианте.
| |
| − | | |
| − | Рассмотрим алгоритмы, последовательная сложность которых уже оценивалась в [[#Последовательная сложность алгоритма|п.1.6]]. Параллельная сложность алгоритма суммирования элементов вектора сдваиванием равна <math>\log_2n</math>, причем число операций на каждом ярусе убывает с <math>n/2</math> до <math>1</math>. Параллельная сложность быстрого преобразования Фурье (базовый алгоритм Кули-Тьюки) для векторов с длиной, равной степени двойки - <math>\log_2n</math>. Параллельная сложность базового алгоритма разложения Холецкого (точечный вариант для плотной симметричной и положительно-определенной матрицы) это <math>n</math> шагов для вычислений квадратного корня, <math>(n-1)</math> шагов для операций деления и <math>(n-1)</math> шагов для операций умножения и сложения.
| |
| | | | |
| | == Входные и выходные данные алгоритма == | | == Входные и выходные данные алгоритма == |
| − | В данном разделе необходимо описать объем, структуру, особенности и свойства входных и выходных данных алгоритма: векторы, матрицы, скаляры, множества, плотные или разреженные структуры данных, их объем. Полезны предположения относительно диапазона значений или структуры, например, диагональное преобладание в структуре входных матриц, соотношение между размером матриц по отдельным размерностям, большое число матриц очень малой размерности, близость каких-то значений к машинному нулю, характер разреженности матриц и другие.
| + | '''Входные параметры:''' |
| − | | + | * <math>N</math> - количество объектов в рассматриваемой группе; |
| | + | * <math>T</math> - временной интервал, <math>T>0 ;</math> |
| | + | * <math>a_l, b_l</math> - интервалы параболического распределения для случайной величины <math>\lambda, a_l >= 0, b_l <=1 ;</math> |
| | + | * <math>a_m, b_m</math> - интервалы параболического распределения для случайной величины <math>\mu, a_m >= 0, b_m <=1 .</math> |
| | + | Выходные параметры: усредненная надежность группы однотипных объектов. |
| | == Свойства алгоритма == | | == Свойства алгоритма == |
| − | Описываются прочие свойства алгоритма, на которые имеет смысл обратить внимание на этапе реализации. Как и ранее, никакой привязки к конкретной программно-аппаратной платформе не предполагается, однако вопросы реализации в проекте AlgoWiki всегда превалируют, и необходимость обсуждения каких-либо свойств алгоритмов определяется именно этим.
| |
| − |
| |
| − | Весьма полезным является ''соотношение последовательной и параллельной сложности'' алгоритма. Оба понятия мы рассматривали ранее, но здесь делается акцент на том выигрыше, который теоретически может дать параллельная реализация алгоритма. Не менее важно описать и те сложности, которые могут возникнуть в процессе получения параллельной версии алгоритма.
| |
| − |
| |
| − | [[глоссарий#Вычислительная мощность|''Вычислительная мощность'']] алгоритма равна отношению числа операций к суммарному объему входных и выходных данных. Она показывает, сколько операций приходится на единицу переданных данных. Несмотря на простоту данного понятия, это значение исключительно полезно на практике: чем выше вычислительная мощность, тем меньше накладных расходов вызывает перемещение данных для их обработки, например, на сопроцессоре, ускорителе или другом узле кластера. Например, вычислительная мощность скалярного произведения двух векторов равна всего лишь <math>1</math>, а вычислительная мощность алгоритма умножения двух квадратных матриц равна <math>2n/3</math>.
| |
| | | | |
| − | Вопрос первостепенной важности на последующем этапе реализации - это [[глоссарий#Устойчивость|''устойчивость'']] алгоритма. Все, что касается различных сторон этого понятия, в частности, оценки устойчивости, должно быть описано в данном разделе.
| + | = Программная реализация алгоритма = |
| | | | |
| − | ''Сбалансированность'' вычислительного процесса можно рассматривать с разных сторон. Здесь и сбалансированность типов операций, в частности, арифметических операций между собой (сложение, умножение, деление) или же арифметических операций по отношению к операциям обращения к памяти (чтение/запись). Здесь и сбалансированность операций между параллельными ветвями алгоритма. С одной стороны, балансировка нагрузки является необходимым условием эффективной реализации алгоритма. Вместе с этим, это очень непростая задача, и в описании должно быть отмечено явно, насколько алгоритм обладает этой особенностью. Если обеспечение сбалансированности не очевидно, желательно описать возможные пути решения этой задачи.
| + | Алгоритм реализован на C++, код программы приведен здесь [https://github.com/SofiaPalionnaya/Parallelism]. |
| | + | == Особенности реализации последовательного алгоритма == |
| | + | == Локальность данных и вычислений == |
| | + | == Возможные способы и особенности параллельной реализации алгоритма == |
| | + | == Масштабируемость алгоритма и его реализации == |
| | + | === Масштабируемость алгоритма === |
| | + | {| class="wikitable" |
| | + | |- |
| | + | ! Количество процессов |
| | + | ! Время выполнения |
| | + | |- |
| | + | |1 |
| | + | |2.36 |
| | + | |- |
| | + | |2 |
| | + | |2.41 |
| | + | |- |
| | + | |4 |
| | + | |2.12 |
| | + | |- |
| | + | |8 |
| | + | |2.03 |
| | + | |- |
| | + | |16 |
| | + | |1.98 |
| | + | |- |
| | + | |32 |
| | + | |1.65 |
| | + | |- |
| | + | |64 |
| | + | |1.4 |
| | + | |- |
| | + | |128 |
| | + | |1.04 |
| | + | |- |
| | + | |} |
| | | | |
| − | На практике важна [[глоссарий#Детерминированность|''детерминированность алгоритмов'']], под которой будем понимать постоянство структуры вычислительного процесса. С этой точки зрения, классическое умножение плотных матриц является детерминированным алгоритмом, поскольку его структура при фиксированном размере матриц никак не зависит от элементов входных матриц. Умножение разреженных матриц, когда матрица хранятся в одном из специальных форматов, свойством детерминированности уже не обладает: его свойства, например, степень локальности данных зависит от структуры разреженности входных матриц. Итерационный алгоритм с выходом по точности также не является детерминированным: число итераций, а значит и число операций, меняется в зависимости от входных данных. В этом же ряду стоит использование датчиков случайных чисел, меняющих вычислительный процесс для различных запусков программы. Причина выделения свойства детерминированности понятна: работать с детерминированным алгоритмом проще, поскольку один раз найденная структура и будет определять качество его реализации. Если детерминированность нарушается, то это должно быть здесь описано вместе с описанием того, как недетерминированность влияет на структуру вычислительного процесса.
| + | === Характеристики программно-аппаратной среды === |
| | + | Результаты тестов были получены на суперкомпьютере Ломоносов (в очередях test и regular4) с использованием компилятора языка С++ GNU 4.4.6. |
| | + | При запусках программы ограничений по времени и по числу процессов на узле не было. |
| | | | |
| − | Серьезной причиной недетерминированности работы параллельных программ является изменение порядка выполнения ассоциативных операций. Типичный пример - это использование глобальных MPI-операций на множестве параллельных процессов, например, суммирование элементов распределенного массива. Система времени исполнения MPI сама выбирает порядок выполнения операций, предполагая выполнение свойства ассоциативности, из-за чего ошибки округления меняются от запуска программы к запуску, внося изменения в конечный результат ее работы. Это очень серьезная проблема, которая сегодня встречается часто на системах с массовым параллелизмом и определяет отсутствие повторяемости результатов работы параллельных программ. Данная особенность характерна для [[#ЧАСТЬ. Программная реализация алгоритмов|второй части AlgoWiki]], посвященной реализации алгоритмов, но вопрос очень важный, и соответствующие соображения, по возможности, должны быть отмечены и здесь.
| + | == Динамические характеристики и эффективность реализации алгоритма == |
| | + | == Выводы для классов архитектур == |
| | + | == Существующие реализации алгоритма == |
| | + | Для данной постановки задачи существующих реализаций не найдено. |
| | | | |
| − | Заметим, что, в некоторых случаях, недетерминированность в структуре алгоритмов можно "убрать" введением соответствующих макроопераций, после чего структура становится не только детерминированной, но и более понятной для восприятия. Подобное действие также следует отразить в данном разделе.
| + | = Литература = |
| | + | <references /> |
| | + | 2. Кудрявцев А. А. Байесовские модели массового обслуживания и надежности: априорные распределения с компактным носителем // |
| | + | Информатика и ее применения, 2016. Т. 10. Вып. 1. |
| | | | |
| − | [[глоссарий#Степень исхода|''Степень исхода вершины информационного графа'']] показывает, в скольких операциях ее результат будет использоваться в качестве аргумента. Если степень исхода вершины велика, то на этапе реализации алгоритма нужно позаботиться об эффективном доступе к результату ее работы. В этом смысле, особый интерес представляют рассылки данных, когда результат выполнения одной операции используется во многих других вершинах графа, причем число таких вершин растет с увеличением значения внешних переменных.
| + | 3. Кудрявцев А. А., Палионная С.И. Байесовская рекуррентная модель роста надежности: параболическое распределение параметров // Информатика и ее применения. — 2016. Т. 10, выпуск 2, страницы 80–83. |
| | | | |
| − | ''"Длинные" дуги в информационном графе'' <ref name="VVVVVV" /> говорят о потенциальных сложностях с размещением данных в иерархии памяти компьютера на этапе выполнения программы. С одной стороны, длина дуги зависит от выбора конкретной системы координат, в которой расположены вершины графа, а потому в другой системе координат они попросту могут исчезнуть (но не появится ли одновременно других длинных дуг?). А с другой стороны, вне зависимости от системы координат их присутствие может быть сигналом о необходимости длительного хранения данных на определенном уровне иерархии, что накладывает дополнительные ограничения на эффективность реализации алгоритма. Одной из причин возникновения длинных дуг являются рассылки скалярных величин по всем итерациям какого-либо цикла: в таком виде длинные дуги не вызывают каких-либо серьезных проблем на практике.
| |
| | | | |
| − | Для проектирования специализированных процессоров или реализации алгоритма на ПЛИС представляют интерес ''компактные укладки информационного графа'' <ref name="VVVVVV" />, которые также имеет смысл привести в данном разделе.
| + | [[en:Description of algorithm properties and structure]] |
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
В данной задаче рассматривается байесовская рекуррентная модель роста надежности сложных модифицируемых информационных систем.
Так как любая впервые созданная сложная информационная система не обладает требуемой надежностью, она подвергается различным модификациям, целью которых является устранение дефектов, препятствующих правильному функционированию системы. Надежность системы зависит от соотношения параметров, интерпретируемых в теории надежности как показатели <<дефективности>> и <<эффективности>> средства, исправляющего ошибки в системе. При использовании байесовских моделей применительно к задачам теории надежности предполагается, что основные параметры системы не являются заданными, а известны только их априорные распределения. В частности данных алгоритм производит вычисления предельной надежности группы однотипных сложных модифицируемых информационных систем для случая параболического распределения параметров.
1.2 Математическое описание алгоритма
Для формализации понятия надежности системы, будем характеризовать ее в каждый момент времени t параметром p(t), при этом время
считаем непрерывным. Так как система подвергается модификациям в случайные моменты времени : [math] 0=Y_0\le~Y_1~\le Y_2~\le\ldots
[/math], параметр [math]p(t)[/math] изменяется, принимая соответственно значения [math]p(t) = p(Y_j) = p_j[/math] при [math]Y_j~\le~t\lt ~ Y_{j+1}[/math] (предполагается, что траектории процесса [math]p(t)[/math] непрерывны справа, а модификации происходят мгновенно). Причем при модификациях параметр надежности может как увеличиваться, так и уменьшаться из-за некачественных модификаций.
К числу математических моделей, описывающих изменение надежности модифицируемых информационных систем, относятся рекуррентные модели роста надежности. Рассмотрим, в частности, дискретную экспоненциальную модель, которая определяется следующим образом:
[math]p_{j+1} = \eta_{j+1}p_j + \theta_{j+1}(1-p_j).[/math]
Здесь [math]\{(\theta_j, \eta_j)\}[/math], [math]j\ge1[/math], -- последовательность независимых одинаково распределенных двумерных случайных векторов таких, что [math]0 \lt \eta_1 \lt 1[/math]; [math]0 \lt \theta_1 \lt 1[/math] почти наверное. Начальная надежность [math]p_0[/math] считается заданной, случайные величины [math]\eta_j[/math] (параметры <<дефективности>>) и [math]\theta_j[/math] (параметры <<эффективности>>) описывают соответственно возможное уменьшение и повышение надежности.
Обозначим [math]\lambda = 1 - {E}\theta_j[/math], [math]\mu = {E}\eta_j[/math].
В книге [1] доказано, что при условии [math]\lambda+\mu\neq1[/math]
[math]
p=\lim_{j\to\infty}E p_j = \frac{\mu}{\lambda+\mu}.
[/math]
Величина [math]p[/math] характеризует асимптотическое значение надежности системы в рамках некоторой рекуррентной модели, задаваемой набором [math]\{(\theta_j, \eta_j)\}[/math].
В рамках байесовского подхода в постановке задач теории надежности можно рассмотреть более сложную ситуацию, где основные параметры системы [math]\lambda [/math] и [math]\mu [/math] предполагаются случайными. В таком случае наиболее естественной и удобной для изучения характеристикой является усредненное значение предельной надежности, то есть
[math]
p_{average} = Ep = E\frac{\mu}{\lambda+\mu},
[/math]
где усреднение ведется по совместному распределению случайных величин [math]\lambda [/math] и [math]\mu [/math].
Так как случайные величины [math]\eta_1 [/math] и [math]\theta_1 [/math] удовлетворяют ограничениям [math]0 \lt \eta_1 \lt 1, 0 \lt \theta_1 \lt 1 [/math], средние значения [math]\lambda [/math] и [math]\mu [/math] величин [math]1 - E\theta_j [/math] и [math]E\eta_j [/math] соответственно также находятся на отрезке [0,1]. В частном случае, рассмотрим независимые случайные параметры [math]\lambda [/math] и [math]\mu [/math], имеющие параболические распределения на некоторых (вообще говоря, разных) отрезках, являющихся подмножествами отрезка [0,1].
Итак, пусть средний параметр <<эффективности>> [math]\lambda [/math] и средний параметр <<дефективности>> [math]\mu [/math] независимы и имеют параболическое распределение [math]P(a_\lambda, b_\lambda) [/math], [math]0\le a_\lambda\lt b_\lambda\le1 [/math], и [math]P(a_\mu, b_\mu) [/math], [math]0\le a_\mu\lt b_\mu\le1 [/math], соответственно.
Для плотности [math]f_\xi(x) [/math] некоторой случайной величины [math]\xi [/math], имеющей параболическое распределение с параметрами [math](a_\xi, b_\xi) [/math], справедливо:
[math] f_\xi(x) = \frac{6(x-a_\xi)(b_\xi-x)}{(b_\xi-a_\xi)^3},\ \ \ \ x\in[a_\xi, b_\xi]. [/math]
1.3 Вычислительное ядро алгоритма
Пусть рассматривается изменение надежности группы однотипных системы на интервале времени [0, T].
1. Для каждой системы моделируем модификации, происходящие в случайные моменты времени [math]t_j: \sum_{j}t_j \lt = T[/math], следующим образом:
- Генерируем реализацию случайных величин [math]\lambda [/math], [math]\mu [/math] с параболическим распределением на заданных интервалах [math][a_\lambda, b_\lambda], [a_\mu, b_\mu][/math] соответственно. Задаем начальную надежность системы, как реализацию случайной величины с равномерным на [0,1] распределением.
- Пока [math] \sum_{j}t_j \lt = T [/math], моделируем поступления модификаций в систему в момент времени [math]t_j[/math]: генерируем реализацию случайных величин [math]\theta_j [/math], [math]\eta_j [/math] таких, что [math]\lambda = 1 - {E}\theta_j[/math], [math]\mu = {E}\eta_j[/math], изменяем надежность системы по формуле [math] p_{j+1} = \eta_{j+1}p_j + \theta_{j+1}(1-p_j).[/math]
2. Вычисляем усредненную надежность группы однотипных систем после всех модификаций.
1.4 Макроструктура алгоритма
Основную часть алгоритма составляет расчет надежности модифицируемых объектов после каждой модификации. Могут быть рассмотрены другие априорные распределения параметров [math]\lambda[/math] и [math]\mu[/math] в рамках данной модели или совершенно другие математические модели, описывающие изменение надежности сложных модифицируемых систем.
1.5 Схема реализации последовательного алгоритма
Схема реализации последовательного алгоритма приведена в описании вычислительного ядра алгоритма.
1.6 Последовательная сложность алгоритма
- [math][0;T][/math] - рассматриваемый временной интервал;
- [math]N[/math] - количество модифицируемых систем.
Тогда для вычисления средней надежности [math]N[/math] модифицируемых объектов за время [math]T[/math] в последовательном (наиболее медленном) варианте требуется:
- [math]N(34+6T)+1[/math] сложений (вычитаний),
- [math]N(51+5T)[/math] умножений.
1.7 Информационный граф
Описание информационного графа:
- Красная вершина графа обозначает начальный блок программы, в котором задаются входные данные и вычисляются общие для всех модифицируемых объектов характеристики.
- Желтые вершины графа обозначают выполнение одной модификации для одной модифицируемой системы. Так как для разных объектов количество модификаций, вообще говоря, различно, количество желтых вершин в параллельных нитях графа различно.
- Зеленые вершины графа обозначают заключительный этап вычислений для каждого модифицируемого объекта. На этом этапе происходит вычисление надежности объекта после последней модификации.
- Синяя вершина графа обозначает заключительный участок выполнения программы, на котором происходит вычисление усредненной надежности по всем модифицируемым объектам.
1.8 Ресурс параллелизма алгоритма
Ресурс параллелизма алгоритма заключается в независимости модифицируемых объектов. Таким образом на разных процессах могут происходить вычисления для разных объектов независимо друг от друга.
1.9 Входные и выходные данные алгоритма
Входные параметры:
- [math]N[/math] - количество объектов в рассматриваемой группе;
- [math]T[/math] - временной интервал, [math]T\gt 0 ;[/math]
- [math]a_l, b_l[/math] - интервалы параболического распределения для случайной величины [math]\lambda, a_l \gt = 0, b_l \lt =1 ;[/math]
- [math]a_m, b_m[/math] - интервалы параболического распределения для случайной величины [math]\mu, a_m \gt = 0, b_m \lt =1 .[/math]
Выходные параметры: усредненная надежность группы однотипных объектов.
1.10 Свойства алгоритма
2 Программная реализация алгоритма
Алгоритм реализован на C++, код программы приведен здесь [1].
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
2.4.1 Масштабируемость алгоритма
| Количество процессов
|
Время выполнения
|
| 1
|
2.36
|
| 2
|
2.41
|
| 4
|
2.12
|
| 8
|
2.03
|
| 16
|
1.98
|
| 32
|
1.65
|
| 64
|
1.4
|
| 128
|
1.04
|
2.4.2 Характеристики программно-аппаратной среды
Результаты тестов были получены на суперкомпьютере Ломоносов (в очередях test и regular4) с использованием компилятора языка С++ GNU 4.4.6.
При запусках программы ограничений по времени и по числу процессов на узле не было.
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
Для данной постановки задачи существующих реализаций не найдено.
3 Литература
- ↑ Королев В. Ю., Соколов И. А. Основы математической теории надежности модифицируемых систем. --- М.: ИПИ РАН, 2006. 102~с.
2. Кудрявцев А. А. Байесовские модели массового обслуживания и надежности: априорные распределения с компактным носителем //
Информатика и ее применения, 2016. Т. 10. Вып. 1.
3. Кудрявцев А. А., Палионная С.И. Байесовская рекуррентная модель роста надежности: параболическое распределение параметров // Информатика и ее применения. — 2016. Т. 10, выпуск 2, страницы 80–83.
