ПОВЫШЕНИЕ УСТОЙЧИВОСТИ ФУНКЦИОНИРОВАНИЯ БОРТОВЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ ПО РЕЗУЛЬТАТАМ КОСМИЧЕСКИХ ЭКСПЕРИМЕНТОВ
70 А. Г. Басыров, В. А. Гончаренко, В. С. Забузов, Г. В. Кремез, К. А. Эсаулов
УДК 629.7
А. Г. БАСЫРОВ, В. А. ГОНЧАРЕНКО, В. С. ЗАБУЗОВ, Г. В. КРЕМЕЗ, К. А. ЭСАУЛОВ
ПОВЫШЕНИЕ УСТОЙЧИВОСТИ ФУНКЦИОНИРОВАНИЯ БОРТОВЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ
ПО РЕЗУЛЬТАТАМ КОСМИЧЕСКИХ ЭКСПЕРИМЕНТОВ
Исследованы результаты натурных экспериментов, проведенных на космических аппаратах „Можаец-3“ и „Можаец-4“. Обосновывается целесообразность многомодульного подхода к построению бортовых вычислительных систем с адаптивной организацией обслуживания. Рассматриваются возможности обеспечения заданной производительности в условиях воздействия дестабилизирующих факторов.
Ключевые слова: бортовые вычислительные системы, многомодульность, адаптивность, производительность, натурные эксперименты, алгоритм планирования.
Введение. Одной из проблем организации управления малыми космическими аппаратами (МКА) является обеспечение устойчивого функционирования бортовых вычислительных систем (БВС) МКА в течение длительного времени (7—10 лет). Существующие подходы к решению данной проблемы основаны на выборе элементной базы с высокими показателями надежности и стойкости к воздействию внешних факторов, а также на применении архитектурных решений, связанных с различными видами резервирования (структурного, временного, информационного и т.д.). При этом важнейшим этапом в разработке, реализации и оценивании эффективности использования технических решений являются моделирование и натурные эксперименты.
Проводимые на близких к круговым орбитах высотой около 700 км эксперименты на борту МКА серии „Можаец“ по исследованию работоспособности электронных компонентов в условиях воздействия неблагоприятных факторов космического пространства (в том числе космической радиации) направлены на разработку предложений по увеличению технического ресурса бортовых систем космических аппаратов. Испытываются интегральные микросхемы генераторов тактовых импульсов и статического оперативного запоминающего устройства 537РУ16 [1, 2]. Тестирование микросхем проводится на основе сравнения с эталонными значениями амплитуды сигнала с выходов генераторов тактовых импульсов и считанных кодов из ячеек модулей памяти. Определение фактов отказов и их статистическая обработка для КА „Можаец-3“ проводились по результатам телеметрии наземными средствами, для „Можаец-4“ — бортовым микропроцессором. Элементы установлены в негерметичных алюминиевых корпусах различной толщины на поверхности МКА. Полученные экспериментальные данные показали, что БВС МКА должна быть защищена алюминиевым корпусом толщиной не менее 1 мм. Парирование отказов модулей оперативной памяти должно обеспечиваться путем различных видов резервирования, причем избыточность должна составлять не менее 60 % аппаратных и/или временных затрат на реализацию нерезервированного варианта.
Применение архитектурных подходов способствует повышению устойчивости функционирования БВС. Хотя избыточность оборудования при реализации данных подходов затрудняет удовлетворение массогабаритным требованиям к МКА, тем не менее существует перспектива миниатюризации бортовой цифровой техники. В результате можно получить более гибкие решения, позволяющие существенно повысить производительность, надежность, живучесть, и как следствие — эффективность функционирования МКА в целом.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 4
Повышение устойчивости функционирования бортовых вычислительных систем
71
Методика многомодульного построения БВС. Одним из архитектурных подходов яв-
ляется многомодульное построение БВС с адаптивной организацией обслуживания вычисли-
тельной нагрузки в соответствии со складывающейся ситуацией. В результате использования
адаптивных многомодульных БВС
— повышается отказоустойчивость за счет дублирования вычислений;
— обеспечивается перераспределение нагрузки;
— обеспечиваются высокопроизводительные параллельные вычисления.
Характеристики адаптивной БВС (в частности, кратность резервирования) выбираются
исходя из описанных выше результатов космических экспериментов.
Рассмотрим модель многомодульной БВС, в которой распределение задач между вы-
числительными модулями (ВМ) осуществляется аппаратным или программным диспетчером
(коммутационным процессором). Каждый модуль имеет необходимые средства для организа-
ции очереди заданий.
Адаптивные алгоритмы диспетчеризации, в отличие от детерминированных и стохасти-
ческих, обладают рядом преимуществ [3], но требуют дополнительной оперативной инфор-
мации. Диспетчер распределяет очередное поступившее задание исходя из динамически из-
меняющейся информации, например, сведений о длине очередей к модулям, о соотношении
производительности модулей и их исправности. В случае сбоя или отказа производитель-
ность модуля может считаться равной нулю.
Пусть модель массового обслуживания с диспетчеризацией состоит из п узлов обслужи-
вания, диспетчера заданий и п входящих потоков к диспетчеру. Назовем данную модель сис-
темой с присоединением к кратчайшей очереди и переходами между очередями.
Диспетчер включает анализаторы очередей и коммутаторы. Информация о соотноше-
нии длины очередей ∆L используется для распределения очередного задания. Суммарный
входной поток заданий с интенсивностью λ будет распределяться таким образом, чтобы наи-
лучшим образом загрузить все модули, так как любое задание, поступившее в систему, будет
присоединяться к наиболее короткой очереди. Если кратчайших очередей несколько, посту-
пающее задание направляется в модуль с большей интенсивностью обслуживания µ, при равенстве или неизвестном соотношении значений интенсивности — в модуль с соответствую-
щим номером. Для уменьшения разницы длины очередей, возникающей в процессе ожидания
обслуживания из-за случайного характера процесса обслуживания, используется механизм
перехода заданий между очередями. В этом случае последнее задание из наиболее длинной
очереди переходит в кратчайшую очередь при разности очередей больше некоторого порога
чувствительности. В простейшем случае переход осуществляется при |∆L|>1.
Структурная схема, алгоритм функционирования и основные вероятностно-временные
характеристики данной системы описаны в [4].
Для двухмодульной БВС вероятность незанятого состояния БВС составляет
P0
=
⎡⎢1+ ⎢⎣
1−ρ2K 1−ρ
ρ(ρ+r + s−2rs) (1+2ρ)(s−s2 )
⎤ ⎥ ⎦⎥
−1
,
где K — емкость буферов очереди ВМ, ρ = λ/µ — коэффициент загрузки БВС, λ=λ1+λ2, µ=µ1 +µ2, r = λ1/λ, s = µ1/µ.
Среднее время решения задачи T в рассматриваемой системе соответствует
T
=
P0
ρ+r −2rs+ s µ(1+2ρ)(s+ s2
)
⎡1−ρ2K
⎢ ⎢⎣
(1−
ρ)2
−
2Kρ2K 1−ρ
⎤ ⎥ ⎦⎥
.
Методика выбора алгоритма планирования. Одним из перспективных путей дости-
жения высокой производительности БВС является внедрение в процесс ее функционирования
методов параллельной обработки информации. Одной из проблем, с которыми приходится
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 4
72 А. Г. Басыров, В. А. Гончаренко, В. С. Забузов, Г. В. Кремез, К. А. Эсаулов
сталкиваться при организации параллельных вычислений, является сложность планирования
параллельного функционирования модулей БВС. Решать эту проблему можно с помощью
эвристических алгоритмов планирования, дающих близкий к оптимальному результат за прием-
лемое время. Выбрать требуемый алгоритм можно на основании результатов имитационного
моделирования.
Вместе с тем в зависимости от ограничений на время планирования можно применить
не один, а несколько эвристических алгоритмов и, реализовав каждый из них, выбрать наи-
лучший план параллельных вычислений. Такой подход позволяет повысить вероятность дос-
тижения требуемой производительности в условиях ограничений на время планирования.
Для оперативного выбора требуемых алгоритмов необходима заранее рассчитанная
функция F (t) = (x1, x2 , ..., xm ) , определяющая в зависимости от времени t, отведенного на по-
лучение плана, вектор (x1, x2 , ..., xm ) применяемых алгоритмов, где xi =1, если алгоритм i
используется в комбинации алгоритмов, и xi = 0 — в противном случае, m — общее число
рассматриваемых алгоритмов.
Основой для расчета данной функции являются, во-первых, результаты статистических
испытаний моделей применяемых алгоритмов в виде зависимости G( y1, y2 , ..., ym ) , опреде-
ляющей частоту выборки лучшего результата комбинацией алгоритмов ( y1, y2 , ..., ym ) , где
yi =1, если результат применения алгоритма i совпал с наилучшим, и yi = 0 — в противном
случае, и, во-вторых, время ti , затрачиваемое на реализацию i-го алгоритма.
Так как вероятность того, что хотя бы один из алгоритмов комбинации (x1, x2 , ..., xm )
обеспечит наибольшую производительность, составляет
∑ ( )∪P(x1,
x2 ,
...,
xm
)
=
k⎛ j =1 ⎜⎝⎜
G
y1 j , y2 j , ..., ymj
m i=1
yij
xi
⎞ ⎠⎟⎟
,
(1)
где k — размер области значений функции G( y1, y2 , ..., ym ) , а временные затраты на синтез
расписания составляют
m
∑T (x1, x2 , ..., xm ) = xiti , i=1
то искомая функция F (t) может быть записана в виде
(2)
∑ ( )∪F
(t
)
=
⎧ ⎪arg ⎪ ⎨
max
⎪⎧ ⎨ ⎩⎪
k j=1
⎛ ⎜⎝⎜
G
y1 j , y2 j , ..., ymj
m i=1
yij
xi
⎟⎠⎟⎞⎪⎫⎪⎬⎭;
∑⎪
⎪
m
xi ti
≤ t.
⎩ i=1
(3)
Данная функция рассчитывается до начала оперативного планирования параллельных
вычислений. В режиме реального времени на ее вход поступает значение временного интер-
вала Tз , в течение которого необходимо получить результат, на выходе получается значение
вектора F (Tз ) = (x1, x2 , ..., xm ) , определяющего комбинацию алгоритмов, которые следует ис-
пользовать для получения плана, с наибольшей вероятностью являющегося наилучшим из
результатов планирования всеми рассматриваемыми алгоритмами. При этом суммарное вре-
мя реализации найденной комбинации алгоритмов не будет превышать требуемого.
Рассмотрим работу данной методики на примере.
Пример. Известны четыре эвристических алгоритма планирования параллельных вы-
числений, условно называемые A, B, C и D. Известно также множество временных затрат
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 4
Повышение устойчивости функционирования бортовых вычислительных систем
73
(в секундах), каждого алгоритма на синтез расписания параллельных вычислений:
{10, 8, 5, 2}. Требуется синтезировать расписание параллельных вычислений за время Tз ≤15 с.
Пусть в результате статистических испытаний получена представленная в табл. 1 функция
G( y1, y2 , ..., ym ) , определяющая ненулевые значения частоты выборки различных комбина-
ций алгоритмов.
Таблица 1
Значения G( y1 , y2 , ..., ym )
№ комбинации
Алгоритм A BCD
Частота выборки
1
1100
0,15
2
1010
0,15
3
1000
0,13
4
0001
0,04
5
1101
0,08
6
0010
0,05
7
0011
0,05
8
1110
0,12
9
0110
0,18
10
0111
0,05
Из соотношения (1) определим статистическую вероятность P получения наилучшего
расписания с использованием каждой комбинации алгоритмов, а из соотношения (2) — сум-
марные временные затраты T на планирование. Эти значения представлены в табл. 2.
Из приведенных данных видно, что наибольшая вероятность (0,96) синтеза наилучшего
расписания за время (15 с), не превосходящее Tз , достигается комбинацией алгоритмов A и С.
Таблица 2
Значения P(x1 , x2 , ..., xm ) и T
Комбинация (x1 , x2 , ..., xm )
P(x1 , x2 , ..., xm )
T, с
A 0,63 10
B 0,58 8
C 0,6 5
D 0,22 2
A, B 0,86 18
A, C 0,96 15 A, D 0,77 12 B, C 0,83 13
B, D 0,67 10
C, D 0,72 7
A, B, C
0,96 23
A, B, D
0,95 20
A, C, D
1 17
B, C, D
0,87 15
A, B, C, D
1 25
Практика использования данной методики для решения задач планирования параллельных вычислений в режиме реального времени позволила повысить вероятность синтеза оптимальных расписаний параллельных вычислительных процессов на 25—30 %.
Заключение. Испытания элементной базы радиоэлектронной аппаратуры с использованием МКА „Можаец-3“ и „Можаец-4“ показали возможность длительной работы типовых электронных компонентов на борту МКА в негерметизированных приборных отсеках. Полученные экспериментальные оценки необходимой избыточности учитываются в предложен-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 4
74 А. Г. Басыров, В. А. Гончаренко, В. С. Забузов, Г. В. Кремез, К. А. Эсаулов
ных методиках диспетчеризации задач в адаптивных многомодульных вычислительных системах и методике параллельной обработки информации БВС. Данные методики позволяют, как следует из приведенных выше математических соотношений, повысить устойчивость функционирования бортовых вычислительных систем.
СПИСОК ЛИТЕРАТУРЫ
1. Фатеев В. Ф., Кремез Г. В., Фролков Е. В. Исследование работоспособности электронных компонентов бортовой аппаратуры космических аппаратов посредством экспериментальных комплексов „Призма-1“ и „Призма-2“ // Изв. вузов. Приборостроение. 2005. Т. 48, № 6. С. 78—81.
2. Захаров И. В., Иваненко А. Ю., Кремез Г. В., Фролков Е. В., Шпак А. В. Повышение функциональной устойчивости бортовых вычислительных систем малых космических // Изв. вузов. Приборостроение. 2007. Т. 50, № 6. С. 65—67.
3. Донианц В. Н., Удалова Т. В. Перераспределение вычислительной нагрузки в локальных сетях ЭВМ // Управление процессами и ресурсами в распределенных системах. М.: Наука, 1989. С. 57—64.
4. Гончаренко В. А. Модели адаптивного перераспределения нагрузки в кластерных вычислительных системах // Изв. вузов. Приборостроение. 1993. Т. 41, № 7. С. 34—39.
Александр Геннадьевич Басыров Владимир Анатольевич Гончаренко Вячеслав Сергеевич Забузов Георгий Вальтерович Кремез Константин Андреевич Эсаулов
Сведения об авторах — канд. техн. наук; Военно-космическая академия им. А. Ф. Мо-
жайского, кафедра электронно-вычислительной техники, СанктПетербург; E-mail: alexanderbas@mail.ru — канд. техн. наук; Военно-космическая академия им. А. Ф. Можайского, кафедра электронно-вычислительной техники, СанктПетербург; E-mail: vlango@mail.ru — адъюнкт; Военно-космическая академия им. А. Ф. Можайского, кафедра электронно-вычислительной техники, Санкт-Петербург; E-mail: teskatlitpoka@yandex.ru — канд. техн. наук; Военно-космическая академия им. А. Ф. Можайского, кафедра электронно-вычислительной техники, СанктПетербург; E-mail: gvkremez@mail.ru — адъюнкт; Военно-космическая академия им. А. Ф. Можайского, кафедра электронно-вычислительной техники, Санкт-Петербург; E-mail: home5263@yandex.ru
Рекомендована Ученым советом ВКА им. А. Ф. Можайского
Поступила в редакцию 20.10.08 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 4
УДК 629.7
А. Г. БАСЫРОВ, В. А. ГОНЧАРЕНКО, В. С. ЗАБУЗОВ, Г. В. КРЕМЕЗ, К. А. ЭСАУЛОВ
ПОВЫШЕНИЕ УСТОЙЧИВОСТИ ФУНКЦИОНИРОВАНИЯ БОРТОВЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ
ПО РЕЗУЛЬТАТАМ КОСМИЧЕСКИХ ЭКСПЕРИМЕНТОВ
Исследованы результаты натурных экспериментов, проведенных на космических аппаратах „Можаец-3“ и „Можаец-4“. Обосновывается целесообразность многомодульного подхода к построению бортовых вычислительных систем с адаптивной организацией обслуживания. Рассматриваются возможности обеспечения заданной производительности в условиях воздействия дестабилизирующих факторов.
Ключевые слова: бортовые вычислительные системы, многомодульность, адаптивность, производительность, натурные эксперименты, алгоритм планирования.
Введение. Одной из проблем организации управления малыми космическими аппаратами (МКА) является обеспечение устойчивого функционирования бортовых вычислительных систем (БВС) МКА в течение длительного времени (7—10 лет). Существующие подходы к решению данной проблемы основаны на выборе элементной базы с высокими показателями надежности и стойкости к воздействию внешних факторов, а также на применении архитектурных решений, связанных с различными видами резервирования (структурного, временного, информационного и т.д.). При этом важнейшим этапом в разработке, реализации и оценивании эффективности использования технических решений являются моделирование и натурные эксперименты.
Проводимые на близких к круговым орбитах высотой около 700 км эксперименты на борту МКА серии „Можаец“ по исследованию работоспособности электронных компонентов в условиях воздействия неблагоприятных факторов космического пространства (в том числе космической радиации) направлены на разработку предложений по увеличению технического ресурса бортовых систем космических аппаратов. Испытываются интегральные микросхемы генераторов тактовых импульсов и статического оперативного запоминающего устройства 537РУ16 [1, 2]. Тестирование микросхем проводится на основе сравнения с эталонными значениями амплитуды сигнала с выходов генераторов тактовых импульсов и считанных кодов из ячеек модулей памяти. Определение фактов отказов и их статистическая обработка для КА „Можаец-3“ проводились по результатам телеметрии наземными средствами, для „Можаец-4“ — бортовым микропроцессором. Элементы установлены в негерметичных алюминиевых корпусах различной толщины на поверхности МКА. Полученные экспериментальные данные показали, что БВС МКА должна быть защищена алюминиевым корпусом толщиной не менее 1 мм. Парирование отказов модулей оперативной памяти должно обеспечиваться путем различных видов резервирования, причем избыточность должна составлять не менее 60 % аппаратных и/или временных затрат на реализацию нерезервированного варианта.
Применение архитектурных подходов способствует повышению устойчивости функционирования БВС. Хотя избыточность оборудования при реализации данных подходов затрудняет удовлетворение массогабаритным требованиям к МКА, тем не менее существует перспектива миниатюризации бортовой цифровой техники. В результате можно получить более гибкие решения, позволяющие существенно повысить производительность, надежность, живучесть, и как следствие — эффективность функционирования МКА в целом.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 4
Повышение устойчивости функционирования бортовых вычислительных систем
71
Методика многомодульного построения БВС. Одним из архитектурных подходов яв-
ляется многомодульное построение БВС с адаптивной организацией обслуживания вычисли-
тельной нагрузки в соответствии со складывающейся ситуацией. В результате использования
адаптивных многомодульных БВС
— повышается отказоустойчивость за счет дублирования вычислений;
— обеспечивается перераспределение нагрузки;
— обеспечиваются высокопроизводительные параллельные вычисления.
Характеристики адаптивной БВС (в частности, кратность резервирования) выбираются
исходя из описанных выше результатов космических экспериментов.
Рассмотрим модель многомодульной БВС, в которой распределение задач между вы-
числительными модулями (ВМ) осуществляется аппаратным или программным диспетчером
(коммутационным процессором). Каждый модуль имеет необходимые средства для организа-
ции очереди заданий.
Адаптивные алгоритмы диспетчеризации, в отличие от детерминированных и стохасти-
ческих, обладают рядом преимуществ [3], но требуют дополнительной оперативной инфор-
мации. Диспетчер распределяет очередное поступившее задание исходя из динамически из-
меняющейся информации, например, сведений о длине очередей к модулям, о соотношении
производительности модулей и их исправности. В случае сбоя или отказа производитель-
ность модуля может считаться равной нулю.
Пусть модель массового обслуживания с диспетчеризацией состоит из п узлов обслужи-
вания, диспетчера заданий и п входящих потоков к диспетчеру. Назовем данную модель сис-
темой с присоединением к кратчайшей очереди и переходами между очередями.
Диспетчер включает анализаторы очередей и коммутаторы. Информация о соотноше-
нии длины очередей ∆L используется для распределения очередного задания. Суммарный
входной поток заданий с интенсивностью λ будет распределяться таким образом, чтобы наи-
лучшим образом загрузить все модули, так как любое задание, поступившее в систему, будет
присоединяться к наиболее короткой очереди. Если кратчайших очередей несколько, посту-
пающее задание направляется в модуль с большей интенсивностью обслуживания µ, при равенстве или неизвестном соотношении значений интенсивности — в модуль с соответствую-
щим номером. Для уменьшения разницы длины очередей, возникающей в процессе ожидания
обслуживания из-за случайного характера процесса обслуживания, используется механизм
перехода заданий между очередями. В этом случае последнее задание из наиболее длинной
очереди переходит в кратчайшую очередь при разности очередей больше некоторого порога
чувствительности. В простейшем случае переход осуществляется при |∆L|>1.
Структурная схема, алгоритм функционирования и основные вероятностно-временные
характеристики данной системы описаны в [4].
Для двухмодульной БВС вероятность незанятого состояния БВС составляет
P0
=
⎡⎢1+ ⎢⎣
1−ρ2K 1−ρ
ρ(ρ+r + s−2rs) (1+2ρ)(s−s2 )
⎤ ⎥ ⎦⎥
−1
,
где K — емкость буферов очереди ВМ, ρ = λ/µ — коэффициент загрузки БВС, λ=λ1+λ2, µ=µ1 +µ2, r = λ1/λ, s = µ1/µ.
Среднее время решения задачи T в рассматриваемой системе соответствует
T
=
P0
ρ+r −2rs+ s µ(1+2ρ)(s+ s2
)
⎡1−ρ2K
⎢ ⎢⎣
(1−
ρ)2
−
2Kρ2K 1−ρ
⎤ ⎥ ⎦⎥
.
Методика выбора алгоритма планирования. Одним из перспективных путей дости-
жения высокой производительности БВС является внедрение в процесс ее функционирования
методов параллельной обработки информации. Одной из проблем, с которыми приходится
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 4
72 А. Г. Басыров, В. А. Гончаренко, В. С. Забузов, Г. В. Кремез, К. А. Эсаулов
сталкиваться при организации параллельных вычислений, является сложность планирования
параллельного функционирования модулей БВС. Решать эту проблему можно с помощью
эвристических алгоритмов планирования, дающих близкий к оптимальному результат за прием-
лемое время. Выбрать требуемый алгоритм можно на основании результатов имитационного
моделирования.
Вместе с тем в зависимости от ограничений на время планирования можно применить
не один, а несколько эвристических алгоритмов и, реализовав каждый из них, выбрать наи-
лучший план параллельных вычислений. Такой подход позволяет повысить вероятность дос-
тижения требуемой производительности в условиях ограничений на время планирования.
Для оперативного выбора требуемых алгоритмов необходима заранее рассчитанная
функция F (t) = (x1, x2 , ..., xm ) , определяющая в зависимости от времени t, отведенного на по-
лучение плана, вектор (x1, x2 , ..., xm ) применяемых алгоритмов, где xi =1, если алгоритм i
используется в комбинации алгоритмов, и xi = 0 — в противном случае, m — общее число
рассматриваемых алгоритмов.
Основой для расчета данной функции являются, во-первых, результаты статистических
испытаний моделей применяемых алгоритмов в виде зависимости G( y1, y2 , ..., ym ) , опреде-
ляющей частоту выборки лучшего результата комбинацией алгоритмов ( y1, y2 , ..., ym ) , где
yi =1, если результат применения алгоритма i совпал с наилучшим, и yi = 0 — в противном
случае, и, во-вторых, время ti , затрачиваемое на реализацию i-го алгоритма.
Так как вероятность того, что хотя бы один из алгоритмов комбинации (x1, x2 , ..., xm )
обеспечит наибольшую производительность, составляет
∑ ( )∪P(x1,
x2 ,
...,
xm
)
=
k⎛ j =1 ⎜⎝⎜
G
y1 j , y2 j , ..., ymj
m i=1
yij
xi
⎞ ⎠⎟⎟
,
(1)
где k — размер области значений функции G( y1, y2 , ..., ym ) , а временные затраты на синтез
расписания составляют
m
∑T (x1, x2 , ..., xm ) = xiti , i=1
то искомая функция F (t) может быть записана в виде
(2)
∑ ( )∪F
(t
)
=
⎧ ⎪arg ⎪ ⎨
max
⎪⎧ ⎨ ⎩⎪
k j=1
⎛ ⎜⎝⎜
G
y1 j , y2 j , ..., ymj
m i=1
yij
xi
⎟⎠⎟⎞⎪⎫⎪⎬⎭;
∑⎪
⎪
m
xi ti
≤ t.
⎩ i=1
(3)
Данная функция рассчитывается до начала оперативного планирования параллельных
вычислений. В режиме реального времени на ее вход поступает значение временного интер-
вала Tз , в течение которого необходимо получить результат, на выходе получается значение
вектора F (Tз ) = (x1, x2 , ..., xm ) , определяющего комбинацию алгоритмов, которые следует ис-
пользовать для получения плана, с наибольшей вероятностью являющегося наилучшим из
результатов планирования всеми рассматриваемыми алгоритмами. При этом суммарное вре-
мя реализации найденной комбинации алгоритмов не будет превышать требуемого.
Рассмотрим работу данной методики на примере.
Пример. Известны четыре эвристических алгоритма планирования параллельных вы-
числений, условно называемые A, B, C и D. Известно также множество временных затрат
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 4
Повышение устойчивости функционирования бортовых вычислительных систем
73
(в секундах), каждого алгоритма на синтез расписания параллельных вычислений:
{10, 8, 5, 2}. Требуется синтезировать расписание параллельных вычислений за время Tз ≤15 с.
Пусть в результате статистических испытаний получена представленная в табл. 1 функция
G( y1, y2 , ..., ym ) , определяющая ненулевые значения частоты выборки различных комбина-
ций алгоритмов.
Таблица 1
Значения G( y1 , y2 , ..., ym )
№ комбинации
Алгоритм A BCD
Частота выборки
1
1100
0,15
2
1010
0,15
3
1000
0,13
4
0001
0,04
5
1101
0,08
6
0010
0,05
7
0011
0,05
8
1110
0,12
9
0110
0,18
10
0111
0,05
Из соотношения (1) определим статистическую вероятность P получения наилучшего
расписания с использованием каждой комбинации алгоритмов, а из соотношения (2) — сум-
марные временные затраты T на планирование. Эти значения представлены в табл. 2.
Из приведенных данных видно, что наибольшая вероятность (0,96) синтеза наилучшего
расписания за время (15 с), не превосходящее Tз , достигается комбинацией алгоритмов A и С.
Таблица 2
Значения P(x1 , x2 , ..., xm ) и T
Комбинация (x1 , x2 , ..., xm )
P(x1 , x2 , ..., xm )
T, с
A 0,63 10
B 0,58 8
C 0,6 5
D 0,22 2
A, B 0,86 18
A, C 0,96 15 A, D 0,77 12 B, C 0,83 13
B, D 0,67 10
C, D 0,72 7
A, B, C
0,96 23
A, B, D
0,95 20
A, C, D
1 17
B, C, D
0,87 15
A, B, C, D
1 25
Практика использования данной методики для решения задач планирования параллельных вычислений в режиме реального времени позволила повысить вероятность синтеза оптимальных расписаний параллельных вычислительных процессов на 25—30 %.
Заключение. Испытания элементной базы радиоэлектронной аппаратуры с использованием МКА „Можаец-3“ и „Можаец-4“ показали возможность длительной работы типовых электронных компонентов на борту МКА в негерметизированных приборных отсеках. Полученные экспериментальные оценки необходимой избыточности учитываются в предложен-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 4
74 А. Г. Басыров, В. А. Гончаренко, В. С. Забузов, Г. В. Кремез, К. А. Эсаулов
ных методиках диспетчеризации задач в адаптивных многомодульных вычислительных системах и методике параллельной обработки информации БВС. Данные методики позволяют, как следует из приведенных выше математических соотношений, повысить устойчивость функционирования бортовых вычислительных систем.
СПИСОК ЛИТЕРАТУРЫ
1. Фатеев В. Ф., Кремез Г. В., Фролков Е. В. Исследование работоспособности электронных компонентов бортовой аппаратуры космических аппаратов посредством экспериментальных комплексов „Призма-1“ и „Призма-2“ // Изв. вузов. Приборостроение. 2005. Т. 48, № 6. С. 78—81.
2. Захаров И. В., Иваненко А. Ю., Кремез Г. В., Фролков Е. В., Шпак А. В. Повышение функциональной устойчивости бортовых вычислительных систем малых космических // Изв. вузов. Приборостроение. 2007. Т. 50, № 6. С. 65—67.
3. Донианц В. Н., Удалова Т. В. Перераспределение вычислительной нагрузки в локальных сетях ЭВМ // Управление процессами и ресурсами в распределенных системах. М.: Наука, 1989. С. 57—64.
4. Гончаренко В. А. Модели адаптивного перераспределения нагрузки в кластерных вычислительных системах // Изв. вузов. Приборостроение. 1993. Т. 41, № 7. С. 34—39.
Александр Геннадьевич Басыров Владимир Анатольевич Гончаренко Вячеслав Сергеевич Забузов Георгий Вальтерович Кремез Константин Андреевич Эсаулов
Сведения об авторах — канд. техн. наук; Военно-космическая академия им. А. Ф. Мо-
жайского, кафедра электронно-вычислительной техники, СанктПетербург; E-mail: alexanderbas@mail.ru — канд. техн. наук; Военно-космическая академия им. А. Ф. Можайского, кафедра электронно-вычислительной техники, СанктПетербург; E-mail: vlango@mail.ru — адъюнкт; Военно-космическая академия им. А. Ф. Можайского, кафедра электронно-вычислительной техники, Санкт-Петербург; E-mail: teskatlitpoka@yandex.ru — канд. техн. наук; Военно-космическая академия им. А. Ф. Можайского, кафедра электронно-вычислительной техники, СанктПетербург; E-mail: gvkremez@mail.ru — адъюнкт; Военно-космическая академия им. А. Ф. Можайского, кафедра электронно-вычислительной техники, Санкт-Петербург; E-mail: home5263@yandex.ru
Рекомендована Ученым советом ВКА им. А. Ф. Можайского
Поступила в редакцию 20.10.08 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 4