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

Назаров Дмитрий Анатольевич

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

05.13.18. - Математическое моделирование, численные методы и комплексы

программ.

Автореферат

диссертации на соискание учёной степени кандидата технических наук

о з о:з

Владивосток 2011

4843552

Работа выполнена в лаборатории управления надёжностью сложных систем Института автоматики и процессов управления ДВО РАН

Научный руководитель:

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

Официальные оппоненты:

доктор технических наук, профессор, Киншт Николай Владимирович

кандидат технических наук, доцент, Семёнов Сергей Максимович

Ведущая организация:

Институт проблем управления имени В.А. Трапезникова РАН, г. Москва

Защита состоится « I &

е^зро/иЗ 2011 г. в 10 часов на заседании диссертационного совета Д 005.007.61 при Институте автоматики и процессов управления ДВО РАН по адресу: 690041, Владивосток, ул. Радио, д. 5

С диссертацией можно ознакомиться в библиотеке Института автоматики и процессов управления ДВО РАН.

Автореферат разослан « I?- » 2011 г.

Учёный секретарь

диссертационного совета Д 005.007.01, к.т.н.

А.В. Лебедев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Задача построения и анализа ОР рассматривалась в работах отечественных ученых, таких как Б.В. Васильев, Г.В. Дружинин, В.В. Здор, A.B. Маслов, Ю.Е. Смагин, A.B. Фомин и ряда зарубежных исследователей как Е. Buttler, R.Spence, S. Sapatnekar, N. Taylor и др.

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

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

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

моделирования не привело к широкому распространению из-за крайне высокой трудоёмкости, связанной с полным перебором. Развитие вычислительной техники, стремительный рост её мощности за последние 20 лет и развитие технологий параллельных и распределённых вычислений позволяют решать такого рода задачи за приемлемое время.

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

Задачи исследования. Для достижения поставленной цели работы были решены следующие задачи:

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

2. Разработка и программная реализация алгоритмов декомпозиции задачи построения ОР для её параллельной реализации с учётом балансировки вычислительной нагрузки между узлами несимметричной параллельной вычислительной системы.

3. Разработка и программная реализация алгоритмов снижения избыточности данных в сеточном представлении ОР путём применения алгоритмов сжатия и использования нерегулярных сеток для построения ОР.

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

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

Научная новизна.

1. Предложена оригинальная структура данных, описывающая представление ОР множеством элементарных параллелепипедов по результатам зондирования области поиска на основе ММИ. Характерным отличием предложенной структуры от матрицы несовместных ситуаций, применяемой в ММИ, является использование одномерного массива для хранения результатов зондирования на многомерной регулярной сетке. Использование одномерной структуры позволяет без особых затруднений разбивать её на блоки произвольных объёмов для решения задачи построения ОР с применением параллельных вычислений.

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

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

1. Описание структуры данных и использующие их алгоритмы построения ОР с помощью регулярных и нерегулярных детализированных сеток, а также алгоритмы уменьшения объёмов данных сеточного представления ОР.

2. Алгоритм декомпозиции задачи построения ОР с учётом балансировки вычислительной нагрузки при её параллельной реализации на несимметричной распределённой вычислительной системе.

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

4. Алгоритмы вычисления оптимальных значений параметров с использованием детерминированного критерия максимального запаса работоспособности. Достоверность результатов исследования обеспечивается корректным применением методов исследования и подтверждается результатами вычислительных экспериментов.

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

Научные результаты работы использованы в ФГУП «Центральный научно-исследовательский институт автоматики и гидравлики» (ФГУП «ЦНИИАГ») для получения характеристик областей работоспособности, назначения допусков и номинальных значений параметров при разработке технических устройств и систем специального назначения.

Решение задач диссертационной работы выполнялось в рамках следующих научных проектов и программ: РФФИ 05-08-01398-а; 06-1-ЭММПУ-054 Программа №15 отделения ЭММПУ РАН, Проекты ДВО РАН ( 06-1II-A-03-070, 09-I1I-B-03-082, 10-III-B-03-035).

Апробация результатов работы. Полученные результаты обсуждались на международных симпозиумах «Надежность и качество» (Пенза, 2005 - 2010); Азиатской международной конференции по проблемам управления (ASCC) (Бали,

2006); Международной конференции по проблемам оптимизации и оптимального управления (СООС) (Улан-Батор, 2007); Российской конференции «Дискретная оптимизация и исследование операций» (DOOR) (Владивосток, 2007); международной конференции по промышленным технологиям и управлению (IEEM) (Сингапур,

2007); Дальневосточной математической школе-семинаре им. академика Е.В. Золотова (Владивосток, Хабаровск, 2005 - 2010); Международной конференции студентов, аспирантов и молодых ученых «Интеллектуальный потенциал вузов - на развитие Дальневосточного региона России и стран АТР» (Владивосток, 2006 -2009); а также научных семинарах Института автоматики и процессов управления ДВО РАН.

Публикации. По теме диссертации опубликовано 27 работ, среди которых 3 опубликованы в изданиях, рекомендованных ВАК.

Структура и объём работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы и шести приложений. Основной объём диссертации составляет 149 страниц, в который входят: библиографический список из 119 наименований, 38 рисунков и 6 таблиц.

Личный вклад автора. Все основные результаты, представленные в диссертации получены автором лично. В опубликованных в соавторстве работах [2,3, 5, 7, 10,11] автору принадлежит описание структур данных и формул, используемых для представления ОР; в работах [6, 12] - описание способа применения структур данных представления ОР для решения задачи выбора номиналов параметров на начальных стадиях проектирования.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Объектом исследования в работе является математическая модель У(х) ист

следуемой системы, связывающая вектор у = (у\,У2>—>Ут) выходных параметров

Т

с вектором внутренних параметров х = (х\,х2,...,хп) в виде зависимостей:

у, =^(х),У/ = 1,2,...,т, (1)

которая считается «чёрным ящиком» и может быть задана как аналитически, так и в алгоритмическом виде или с помощью имитационной модели.

Внутренние параметры - это количественные характеристики условно неделимых элементов системы (величина сопротивления для резистора, ёмкость для конденсатора). Выходные параметры представляют собой показатели свойств системы, её количественные характеристики, интересующие потребителя, которые, как правило, лежат в определённых техническим заданием диапазонах значений. Эти ограничения значений выходных параметров называются условиями работоспособности (УР):

Утш - У(х) - Ушах (2)

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

Задача параметрического синтеза (ПС) технических устройств и систем состоит в выборе номинальных значений \тт = (х1тт >х2пот >—>хп пот) внутренних

параметров, обеспечивающих максимум вероятности их нахождения внутри ОР в течение заданного интервала времени:

хпот =аг8тах^>(Жхлояг> где Х(х„оте,/) - случайный процесс изменения параметров; Ох - область работоспособности; Т - заданное время эксплуатации устройства.

Областью работоспособности называется область Ох в пространстве внутренних параметров, в каждой точке которой выполняются УР:

£Л.=(хеЭТ"|утш <у(х)<ут;1Ч) (4)

Часто характеристики области Ох неизвестны, поэтому в выражении (3) проверка Х(хпот,!)е Ох заменяется на УР ут|п <у(Х(х„от,0) <Утах> что требует значительно больших вычислительных затрат. Построение ОР позволит существенно снизить время вычисления статистических характеристик, а также применять детерминированные критерии оптимизации номинальных значений параметров.

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

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

В качестве области поиска используется «-мерный ортогональный гиперпараллелепипед:

Bx={xe,¡Sl"\af <х,- 5 = 1,2,...,«}, (5)

рёбра которого параллельны координатным осям варьируемых параметров и координаты их вершин определяются границами интервалов допустимых значений по соответствующим параметрам:

а- <х^Ь?,\/1 = \,2,...,п. (6)

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

Наложение регулярной и-мерной сетки на гиперпараллелепипед Вх заключается в квантовании каждого /-го варьируемого параметра внутри заданных интер-

валов (6) на q¡ равных отрезков так, что в результате параллелепипед Вх разбивается на

Я = {[ч, (7)

/=1

элементарных параллелепипедов.

Каждый из этих элементарных параллелепипедов задаётся набором п индексов, увеличивающихся в направлениях соответствующих координатных осей варьируемых внутренних параметров: (¿1Д2.—Дл), = V/ = 1,2,...,и. Таким образом, исходный гиперпараллелепипед Вх является их объединением:

<71 42 Чп

вх = и II- \}ек1к2...к„ ■ (8)

=1*2=1 к„=\

С другой стороны, множество элементарных параллелепипедов рассматривается как множество элементов (ячеек) наложенной на Вх «-мерной сетки, поэтому в дальнейшем изложении вместо термина «элементарный параллелепипед» используется термин «элемент сетки» или «ячейка сеггки».

В геометрическом центре каждого элемента е^2...к„ сетки выбирается точка-

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

с*' =а- +АДЛ,- -1) + /г,/2, = 1,2,...,?,-, У/ = 1,2,...,и, (9)

где А,- = (Ь* - а*)1 q^,i = \,2,...,n - длина кванта на /-й координатной оси. В каждой такой точке вычисляются значения выходных параметров (1) и проверяются УР (2). Главной особенностью использования точки-представителя является принятие допущения, что выполнение УР во всех точках внутри каждого элемента сетки е^г

определяется их выполнением в его точке-представителе. Функция проверки УР в

к

точках с-', V; = 1,2,...,« всех элементов сетки задаёт разбиение множества этих элементов Д| = {ек^2...к„ I = 1,2,...,д, = 1,2,...,«} на два непересекающихся подмножества:

в!=в+ив;. (ю)

где Вх - подмножество элементов сетки, внутри которых выполняются УР, д. В~ -подмножество элементов, в которых УР не выполняются.

Подмножество Вх элементарных параллелепипедов является геометрическим представлением ОР Пх. Модель такого представления задаётся четвёркой Сц:

Сй =(«,£,&£), (11)

где:

• п - размерность пространства внутренних параметров,

• В = {(а*,Ь*)\~а = \,2,...,п} - множество пар, задающих ограничения (6) по всем параметрам (границы параллелепипеда Вх),

• 2 = (<71><72>—>9л) " набор показателей количества квантов для каждого параметра,

• Б = - массив состояний всех элементов сетки. Структура йд называется сеточным представлением ОР (СПОР).

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

Массив состояний (МС) представляет собой набор индикаторов принадлежности соответствующих элементов сетки

подмножеству или В^.

Соответствие индекса р каждого элемента одномерного МС определённому элементу сетки с индексами (А[, ) задаётся выражением:

п Г (-1

р = р{кьк2,...,к„) = к1 + ^ {кп- 1)-П?у • (12)

На рис. 1 элементы сетки пронумерованы индексами соответствующих им элементов МС. Выражение (12) перехода от индексов элемента сетки к индексу соответствующего элемента МС р = р{к\,к2,—,кп) называется прямым преобразованием индексов. В некоторых алгоритмах построения и анализа СПОР требуется обратная операция: по индексу р элемента МС получить набор индексов (к\,к2,...,кп) соответствующего ему элемента сетки. Для этого необходимо последовательно вычислять индексы: кп(р), кп_\{р,кп), ..., к\(р,к2,к2>—,кп)ш-

Рнс.1. Соответствие индексов элементов МС индексам элементов трёхмерной сетки.

*И =

(р-о/Ш/ /=1

*и-1 =

+ 1,

п-2

(Р-(*„-!)-П 9/) / П 9/

/=1 /=1

+ 1,

(13)

1=2{ ]=\ . Выражения (13) называются обратным преобразованием индексов.

По своей структуре МС является конечным множеством из Я элементов = .....5я)> имеющих следующие значения и интерпретацию:

ад*! ,...,*„)]=

'' Утт

О, (у(хс(£1,..Д^)<УтщМу(хс(£ь...,^)>утах) '

(14)

0 / —.у ■ Г; 0

Ч. 1 1 Г<,

0 0 ч.. ■■'о

к\ к-> к Т

где запись \с(к1,к2,—,к„) означает вычисление координат хс ,с2 ,—,с„") точки-представителя (9) элемента сетки е^ Другими словами, состояние

элемента подмножества В% равно 1, а элемента подмножества - О (рис. 2).

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

О Построение ОР выполняется путём

ь; -«г—— перебора элементов сетки и проверкой УР

в точках-представителях каждого из них. Результат проверки УР фиксируется в соответствующих элементах МС согласно выражению (14). В работе предлагаются три алгоритма выполнения перебора элементов сетки:

1. Перебор элементов МС с обратным преобразованием (13) индексов.

2. Рекурсивный перебор элементов сетки по индексам (к\,¿2.....кп).

3. Перебор значений одного из п индексов с генерацией всех комбинаций остальных п-1 индексов.

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

Наиболее алгоритмически сложным яв- —

ляется метод перебора элементов МС с обратным преобразованием индексов, которое по предложенному в работе алгоритму требует 2

(п -и)/2-3 операций умножения. Оценка сложности этого преобразования принимается 0(п ) (рис. 3). Тогда сложность алгоритма построения ОР оценивается как 0(0"п1), где 0 - усреднённое или равное количество квантов <7;-,\// = 1,2,...,«. При высокой алгоритмической сложности он имеет наивысший

5 [12 ] = (0,0,1,0, 1,1,1,1,0,1,1,0)

Рис. 2. Запись состояний элементов сетки в случае двумерного пространства параметров.

Рис. 3. Сравнение времени выполнения 5 млн. операций прямого и обратного преобразования индексов в зависимости от количества параметров.

из указанных алгоритмов потенциал параллелизма: цикл перебора элементов МС можно разбить от двух до R независимых циклов. Этот алгоритм используется для параллельной реализации задачи построения ОР.

Третья глава посвящена снижению избыточности данных СПОР. Предлагаются два направления, одно из которых связано с устранением избыточности данных в МС при сохранении структуры регулярной сетки, другое - с устранением избыточности в геометрическом представлении на основе регулярных сеток путём использования нерегулярных детализированных сеток.

Первый способ снижения избыточности данных в МС основан на алгоритме кодирования длин серий повторяющихся элементов. Поскольку нормированный МС состоит из элементов двух типов (0 и 1), а представление области подразумевает достаточно длинные фрагменты из элементов одинакового типа, то для уменьшения объёма данных МС применяется алгоритм сжатия типа RLE (run-length encoding), суть которого заключается в последовательном кодировании длин фрагментов массива, состоящих из элементов одного типа. Например, для МС на рис. 2 применение этого алгоритма даст следующий результат: ((2,0),(1,1),(1,0),(4,1),(1,0),(2,1),(1,0)).

Другой предлагаемый в работе алгоритм снижения избыточности данных МС позволяет построить его представление на основе кодирования каждого его элемента одним двоичным разрядом, что даёт гарантированное 8-кратное сжатие. Трудность реализации такого подхода заключается в том, что в современных х86-совмес-тимых компьютерах наименьшей адресуемой единицей является байт, состоящий из 8 разрядов, и для работы с ними требуются дополнительные операции двоичной арифметики. На примере МС на рис.2 его двоичное представление будет иметь вид (с применением 8-битного выравнивания последней группы элементов): (0,0,1Д1,ЦЩЦ0)-К(0,0,1,0,Ц1,1),(0,иД0,0Д0))->(4^9^, в результате чего МС сократится с 12 до 2 байт. Важно отметить, что алгоритмы сжатия МС должны обеспечивать чтение и запись элементов в сжатом виде.

Проблема снижения избыточности данных СПОР на уровне структуры сетки возникает при повышении точности приближения ОР множеством параллелепипедов, заданных этой сеткой. Очевидно, что для повышения точности приближения необходимо увеличивать количество элементов сетки, измельчая её шаг, что требует больше ресурсов для хранения и обработки данных. При этом с увеличением количества элементов сетки увеличивается доля её внутренних элементов (рис. 4), что и порождает избыточность на уровне структуры сетки.

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

Рис. 4. Уменьшение доли граничных элементов регулярной сетки с увеличением количества её квантов.

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

• двухуровневая детализация элементов основной сетки при помощи регулярных сеток с произвольным шагом квантования (рис. 5.а),

• многоуровневая двоичная детализация элементов сетки любого уровня детализирующими сетками, с количеством квантов по каждому параметру <7, = 2, V/ == 1,2,...,« (рис. 5.6).

Детализация элемента сетки выполняется согласно описанному алгоритму построения ОР на основе регулярной сетки, при этом в качестве параллелепипеда Вх выступает детализируемый её элемент.

а) б)

Рис 5. Детализация элементов сетки а) двухуровневая, б) двоичная многоуровневая.

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

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

частоте щхкг...к„ -1 выполнения УР для случайных точек метода Монте-Карло с

равномерным распределением внутри этого элемента. Целесообразность детализации задаётся пороговыми значениями:

^шт <71к\к2—кл <?7тах> (I5)

а количество квантов детализирующей сетки для всех параметров устанавливается одинаковым и вычисляется по эвристической формуле:

<2к{кг...кп =[0 ~ ^Ькг...кп + Чтт )' бшах]> О6)

где 0тах - ограничение сверху на количество квантов детализирующей сетки.

Критерием целесообразности разбиения элемента сетки в случае двоичной многоуровневой детализации является наличие внутри этого элемента хотя бы двух

случайных точек метода Монте-Карло, в одной из которых выполняются УР, а в другой не выполняются.

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

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

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

С точки зрения СПОР эта задача сводится к поиску оптимальных элементов сетки, являющихся центрами выпуклой симметричной фигуры, состоящей из эле-

Рис 6. Максимальный минимум запаса работоспособности.

ментов этой же сетки. Тогда целевой функцией является объём V(e,

:,г) впи-

санной фигуры, зависящий от расположения её центрального элемента с индексами

и расстояния г е N от этого элемента до границы ОР, измеряющееся

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

= тш У(ек1к2-к„'г) ' первый этап оптимизации. Полученная фигура с объёмом

уг{ек1к2-.кп)> зависящим от расположения её центрального элемента, является вписанной в ОР. Тогда второй этап оптимизации состоит в максимизации этого объёма по всем элементам ^к]к2. к„ • Критерий максимального запаса работоспособности выбора оптимальных элементов СПОР является двухэтапной процедурой, заключающейся в отыскании множества Вгор( с В* элементов сетки, для которых

выполняется:

max +mmV(ek]klkii,r) (17)

ekik2...k„eBx r

Алгоритмическая реализация первого этапа оптимизации состоит в проверке принадлежности множеству Вх элементов сетки, находящихся в определённой некоторым образом окрестности центрального элемента е^ ¿n е Вх > в качестве

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

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

состоит в поиске элементов Вх с максимальным весом и их маркировки (рис. 7).

Один из предложенных способов задания окрестности элемента сетки - это п-мерный куб с длиной ребра 2 • г + 1, симметричный относительно центрального элемента, заданного индексами kf ,i = 1,2,...,л. Множество Вгс образующих этот куб, имеют индексы из диапазона:

kf -r< ki < kf + г, V/ = 1,2,...,п. Тогда множество В'с элементов, образующих куб:

В с = {ек]к2...кп eBl \ к?-г < kt < kf + г, Vi = 1,2,...,«}. Алгоритм проверки окрестности элемента е с ,с I с начинается с обхода элементов с

к\ ,к2 ,...,к„

индексами, удовлетворяющими (18) при r = 1. В случае, если по результатам этой проверки

все элементы сетки множеству Вх , то обход повторяется при г = 2. Процедура выполняется до тех пор, пока не будет обнаружен элемент

из множества В~ (Вгс г\В~ *0) или какой-либо из индексов не выйдет за диапазон допустимых значений kf =1,2,...,д,. Элементу е

if элементов сетки, (18)

(19)

Рис. 7. Результат работы алгоритма поиска оптимальных элементов сетки методом вписывания куба максимального объёма.

,с присваивается вес, равный мак-

симальному г, при котором все элементы Вгс принадлежат Вх или Вгс (~\ВХ = 0.

Другой способ описания окрестности элемента сетки основан на введённом понятии г-окрестности. Будем называть г-окрестностью элемента ¿2 с

индексами (к\,к2,-..,кп) такое множество элементов сетки, в котором для каждого

-т\т2...т„

с индексами (т\,mj ,...,тп) справедливо:

ЁК N.

(=1

Рис. 8. Результат работы алгоритма поиска оптимальных элементов сетки методом проверки максимальной г-окрестности.

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

Алгоритм построения такой фигуры максимального объёма, вписанной в СПОР, аналогичен рассмотренному алгоритму построения вписанного куба максимального объёма. Результатом его работы также являются присвоенные элементам сетки из подмножества В* весов, из которых на втором этапе оптимизации выбирается максимальное значение, а из элементов с максимальным весом формируется множество Вгор, с (рис. 8).

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

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

обхода и выделения связных областей. Если назвать предельным элементом *

ек{к2...к„ с индексами {к\,к2,—,кп) множества элементов сетки такой, что

V/- е N

Зе б В8 ■

(21)

т, - к[\<г, V / = 1,2,...,/?,

/=1

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

На основе понятия г-окрестности вводится понятие соседних или сопряжённых элементов сетки (рис. 9), которое используется в алгоритме проверки области на связность. Элементы е^ д ^ и ещт2 сетки являются соседними

(сопряжёнными) если для их индексов выполняется:

| = 1. (22)

\

\

;=1

Рис. 9. Соседние элементы сетки в двумерном случае.

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

алгоритмы визуализации отдельных сечений СПОР.

Визуализация сечений СПОР заключается в графическом отображении множества параллелепипедов с индексами, удовлетворяющими условию:

¿у =сои5/,У/'е

где - множество номеров свободных параметров (координат отображения), 1 I г1Х - множество значений индексов фиксированных параметров. При этом и 1 являются частями разбиения множества {1,2,3,...,«}, а именно:

Л/и с{1,2,3,...,«},/с{1,2,3,...,«},/¿и П=0,/<& и//и = {1,2,3,...,«}. |

Пятая глава содержит описание параллельного алгоритма построения ОР на I

основе регулярной сетки с возможностью его реализации на несимметричной рас- (

пределённой вычислительной системе с учётом балансировки вычислительной на- I грузки между её узлами.

Для выполнения перебора элементов сетки взят алгоритм перебора элементов (

МС с обратным преобразованием индексов (13), в виду тривиальности разбиения '

одного цикла на определённое количество непересекающихся циклов. Параллельное | выполнение инициализации элементов МС в К независимых процессах осуществляется указанием каждому /-му процессу диапазона значений индексов МС:

*? = <, Ь? < Я, / = 1,2,..., К, (24)

с с. V

согласно которого этот процесс выполняет перебор индексов е {а; ,а+1 } с последующим обратным преобразованием в набор индексов элемента сетки (/¡] и нахождением координат (9) его точки-представителя. Инициализа-

ция части МС, заданной диапазоном (24), осуществляется согласно выражению (14). После выполнения расчётов /-й вычислительный процесс отправляет главному про- | цессу готовую г-ю часть МС. Главный процесс помимо раздачи заданий выполняет сбор и объединение результатов работы всех вычислительных процессов.

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

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

при которой МС разбивается на части с длинами 5,, пропорциональными 1 времени /( выполнения тестового задания каждым из вычислительных узлов | (статичная балансировка): ■

Рис. 10. Топология связи вычислительных узлов с главным.

В, =Д/(1 + ^ + 4-+... + -^-), Bj - В\—, i = 2,3,..., К (25)

h h 1к li

2. Автобалансировка, относящаяся к типу динамической балансировки и заключающаяся в разбиении МС на большое количество небольших по объёму заданий, при этом их диспетчеризация между вычислительными узлами организуется динамически по принципу FCFS (First Came First Served) / FIFO (First In First Out). При этом каждый вычислительный узел за общее время решения задачи выполняет столько заданий, сколько позволяют доступные ему ресурсы. Использование в качестве аппаратной базы пользовательских рабочих станций, объединённых в локальную сеть типа Ethernet, объясняется высокой распространённостью последних при достаточно высоких вычислительных возможностях современных компьютеров и их низкой среднестатистической вычислительной загруженности типовым набором приложений.

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

Ускорение при параллельном построении ОР с динамической автобалансировкой нагру»ок и балансировкой по мощностям на распределённой ВС пользовательских рабочих станций

Время решения 800 задачи (сек.)

g 5. Количество заданий

5 о при автобалансировке

0 Балансировка по

^ НОСТЯМ

□ 80 □ 120 Ш160 0200 в 240 □ 280 в 320 вЗБО □ 400

Кол-во вычислительных

Рис. 11. Диаграмма времени построения ОР для схемы ждущего мультивибратора с использованием параллельных вычислений на несимметричной вычислительной распределённой системе, состоящей из сети пользовательских рабочих станций со статичной балансировкой по мощностям и динамической автобалансировкой с кол-вом заданий от 40 до 400.

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

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

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

3. Разработаны и программно реализованы методы снижения избыточности данных в сеточном представлении ОР на основе алгоритмов сжатия данных и использования нерегулярных сеток для построения ОР.

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

5. Разработаны и программно реализованы алгоритмы выбора оптимальных значений номиналов параметров по критерию запаса работоспособности.

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

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

1. Назаров Д.А. Методы аппроксимации области работоспособности в задаче параметрического синтеза // Региональная научно-техническая конференция «Молодежь и научно-технический прогресс»: сб. докл. конф. - Владивосток. -2004. - 1 часть. - С. 179-181.

2. Катуева Я.В., Назаров Д.А Аппроксимация и построение областей работоспособности в задаче параметрического синтеза // Международный симпозиум «Надежность и качество»: сб. науч. тр. - Пенза: ПГУ. - 2005. - С. 130- 134.

3. Катуева Я.В., Назаров Д.А. Алгоритмы анализа области работоспособности, заданной в матричной форме // Информатика и системы управления. - 2005. -№2(10).-С. 118-128.

4. Назаров Д.А. Детализация матричного представления области работоспособности в задаче параметрического синтеза // Международный симпозиум «Надежность и качество»: сб. науч. тр. - Пенза: ПГУ, 2006. - С. 218 - 220.

5. O.V. Abramov, Y.V. Katueva and D.A.Nazarov The Definition of Acceptability Region for Parametric Synthesis Problem // Proceeding of the 6-th Asian Control Conference ASCC2006. - Bali, Indonesia. - 2006. - Pp. 780 - 786.

6. Абрамов О.В., Катуева Я.В. Назаров Д.А. Оптимальный параметрический синтез по критерию запаса работоспособности // Проблемы управления. -2007. - №6. - С. 64 - 69.

7. Abramov O.V., Katueva Y.V. and Nazarov D.A. Reliability-Directed Distributed Computer-Aided Design System // Proc. Of the IEEE International Conference on Industrial Engineering and Engineering Management. - Singapore. - 2007. - Pp. 1171-1175.

8. Назаров Д.А. Использование распределенных вычислений при построении области работоспособности. // Информатика и системы управления. - 2008. -№1(15). -С. 142-151.

9. Назаров Д.А. Технология распределенных вычислений в задаче построения областей работоспособности // «Интеллектуальный потенциал вузов - на развитие Дальневосточного региона России»: материалы X международной конференции студентов, аспирантов и молодых ученых. - Владивосток: ВГУЭС. - 2008. - кн. 2 - С. 57 - 60.

10. Abramov О., Katueva Y., Nazarov D. Construction of acceptability region for parametric reliability optimization // Reliability & Risk: Analysis: Theory & Applications. - 2008. - vol.1. - № 3. - Pp. 20 - 28.

11. O.V. Abramov, Y.V.Katueva and D.A.Nazarov Distributed computing environment for reliability-oriented design // Reliability & Risk: Analysis: Theory & Applications. - 2009. - vol.2. - No.l(12). - Pp. 39 - 46.

12. Абрамов O.B., Диго Г.Б., Диго Н.Б., Катуева Я.В., Назаров Д.А. Параметрический синтез технических систем в неопределенных средах. // Информатика и системы управления. - 2009. - №1(19). - с. 55 - 65.

13. Назаров Д.А. Алгоритм построения области работоспособности с детализированным квантованием области поиска // Надежность и качество: труды международного симпозиума в 2-х т./ под ред. Н.К. Юркова. - Пенза: Информационно-издательский центр ПензГУ. - 2009. - 2 т. - С. 18-22.

14. Назаров Д.А. Декомпозиция задачи построения области работоспособности сложных систем при использовании технологии распределенных вычислений // «Интеллектуальный потенциал вузов - на развитие Дальневосточного региона России и стран АТР»: материалы XI Международной конференции студентов, аспирантов и молодых ученых,- Владивосток: ВГУЭС. - 2009. - кн. 1.-С.43 -47.

15. Назаров Д.А. Двоичная многоуровневая детализация элементов сеточного представления области работоспособности // «Надежность и качество-2010»: труды Международного симпозиума в 2-х т. / под ред. Н. К. Юркова. - Пенза: ПГУ. - 2010. -1 т. - с. 337 — 341.

16. Назаров Д.А. Реализация критерия запаса работоспособности методом вписывания куба максимального объема // XXXV Дальневосточная математическая школа-семинар имени академика Е.В. Золотова: сб.докл. [Электронный ресурс]. - Владивосток: ИАПУ ДВО РАН. -2010.-е. 772 - 781.

ч

Назаров Дмитрий Анатольевич

Разработка алгоритмических и программных средств построения и анализа областей работоспособности аналоговых технических систем

Автореферат

Усл.пл. 1,0 Тираж 100 экз.

Подписано к печати 11.01.2011 Формат 60x84/16_

Издано ИАПУ ДВО РАН. 690041, г. Владивосток, Радио, 5. Отпечатано участком оперативной печати ИАПУ ДВО РАН 690041, Владивосток, Радио, 5

Уч.-изд.л. 0,8 Заказ 1

Введение.

Глава 1. Постановка задачи построения области работоспособности.

1.1. Основные понятия и определения.

1.2. Задача параметрического синтеза.

1.3. Постановка задачи построения области работоспособности.

1.4. Выводы по главе.

Глава 2. Алгоритм построения области работоспособности с помощью регулярной сетки.

2.1 Сеточное представление области поиска.

2.1.1. Использование регулярной сетки.

2.1.2. Структуры данных сеточного представления области поиска.

2.1.3. Алгоритмы инициализации массива состояний элементов сеточного представления области поиска.

2.1.4. Оценка сложности алгоритмов инициализации массива состояний.

2.2. Алгоритм сужения области поиска описанным. параллелепипедом.

2.2.1. Построение описанного параллелепипеда методом статистических испытаний (Монте-Карло).

2.3. Выводы по главе.

Глава 3. Алгоритмы уменьшения объёмов данных сеточного представления области работоспособности.

3.1. Применение алгоритмов сжатия к массиву состояний сеточного представления области работоспособности.

3.1.1. Двоичное (битовое) представление массива со стояний.

3.1.2. Кодирование длин серий элементов массива состояний.

3.1.3. Инициализация массива состояний в сжатом виде.

3.1.4. Сравнительные характеристики алгоритмов сжатия массива состояний.

3.2. Снижение избыточности данных геометрического представления области работоспособности.

3.2.1. Проблема точности построения области работоспособности помощью регулярной сетки.

3.2.2. Алгоритмы построения области работоспособности с использованием нерегулярных сеток.

3.2.3. Двухуровневая детализация.

3.2.4. Многоуровневая двоичная детализация.

3.3. Выводы по главе.

Глава 4. Алгоритмы анализа и оптимизации с использованием сеточного представления области работоспособности.

4.1. Алгоритмы выбора оптимальных элементов сетки по критерию запаса работоспособности.

4.1.1. Алгоритм расчёта наименьшего расстояния до границы области работоспособности с помощью построения вписанного куба.

4.1.2. Алгоритм расчёта наименьшего расстояния до границы области работоспособности методом проверки г-окрестности.

4.1.3. Алгоритм выбора элементов сетки, максимально удалённых от границы области работоспособности.

4.2. Алгоритм проверки связности сеточного представления области.

4.3. Алгоритм визуализации сечений сеточного представления области работоспособности.

4.4. Выводы по главе.

Глава 5. Параллельный алгоритм построения области работоспособности для реализации на распределённой вычислительной системе.

5.1. Сокращение времени построения области работоспособности с помощью параллельных вычислений.

5.2. Параллельный алгоритм построения области работоспособности с помощью регулярной сетки.

5.2.1. Декомпозиция с учётом балансировки вычислительной нагрузки между процессами.

5.2.2. Взаимодействие вычислительных процессов с главным процессом.

5.3. Применение распределённой несимметричной архитектуры вычислительной системы для решения задачи построения области работоспособности.

5.4. Анализ эффективности параллельного алгоритма построения области работоспособности с использованием распределённой вычислительной системы.

5.5. Выводы по главе.

Актуальность темы и предмет исследования

Переход на инновационный путь развития связан с необходимостью создания технических устройств и систем, обладающих необходимыми характеристиками качества и надёжности. Отечественный и зарубежный опыт проектирования и эксплуатации систем различного назначения показывает, что значительную часть отказов составляют постепенные (параметрические) отказы, а задача учёта отклонений параметров от расчётных значений и обеспечение требуемого качества допуска при наличии таких отклонений является одной из наиболее сложных и трудоёмких задач проектирования. При этом по мере усложнения технических объектов, повышения требований к их надёжности и увеличения ответственности выполняемых ими функций необходимость и важность решения этой задачи постоянно возрастает [27, 77].

Задача обеспечения надёжности сложных систем весьма многогранна, и существуют различные направления исследований в данной области [1, 46, 60, 77, 108, 113]. Эффективное решение проблемы обеспечения надёжности в определённой мере зависит от правильного понимания состояния и тенденции развития теории надёжности, в которой можно выделить три методологически различных направления [1]:

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

• физико-статистическое (причинно-следственное) основывается на исследовании и моделировании внутренних физико-химических процесс-сов (причин) в составных элементах системы, чувствительность выходных характеристик к изменениям в этих элементах и построении модели отказов, основанной на изученных взаимосвязях;

• направление, связанное с анализом и обеспечением надёжности по постепенным (параметрическим) отказам.

Классическим математическим аппаратом исследований в теории надёжности являются вероятностные методы [17, 19, 27, 34, 46, 49, 52, 108, 113, 116], использующие статистические характеристики, такие как среднее время наработки до отказа, средняя наработка между отказами, средняя частота отказов и др. [26, 46]. При этом во многих работах также уделяется внимание детерминированным методам, связанным с исследованием области допустимой вариации параметров, которая определяется топологией исследуемой системы и требованиями к выходным характеристикам [1-8, 11, 12, 15-17, 19, 24, 25, 31-37, 39-43, 52-62, 69, 79-82, 84-90, 96, 98, 108, 112-116, 118]. Целью исследования этой области является оптимизация значений параметров с учётом их дрейфа.

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

Далее в работе область допустимой совместной вариации параметров сложного технического объекта (системы) будет называться областью работоспособности (ОР) и в главе 1 будет дано строгое её определение.

Задача построения и анализа ОР занимает важное место в процессе создания технических устройств и систем и часто рассматривается как отдельная задача [40, 52]. Её разновидностью является задача построения областей устойчивости и областей качества [25, 33], широко распространённая в теории автоматического управления. Особую важность эта задача приобретает при решении проблемы оптимального проектирования технических систем с учётом изменений параметров и требований надёжности. Решение этой задачи позволяет оценить запас работоспособности при выбранной структуре системы и сравнивать потенциальные возможности различных структур, осуществлять назначение допусков и выбор номинальных значений параметров элементов проектируемых систем.

В ряде работ, посвященных выбору номинальных значений параметров и допусков, используются различные методы исследования области допустимой вариации параметров. Один из подходов связан с зондированием пространства параметров. Примером такого подхода являются сеточные методы поиска в работах Батищева Д.И. [15, 16], различные методы поиска в работе Беккера П. и Йенсена Ф. [17], построение многомерных сеток с помощью ЛПТ -последовательностей в работе Соболя И.М. и Статникова Р.Б. [72], реализация метода Монте-Карло [71] в работах ряда отечественных и зарубежных авторов [1, 17, 39 41, 60, 85, 116], использование генетических алгоритмов в работе коллектива авторов Dhanwada N.R., Nunez-Aldana A., Vemuri R. [90] и эволюционных методов в публикации авторов Р. Jantos, J. Rutkowski [96]. Другой подход связан с построением геометрической аппроксимации ОР фигурами известной конфигурации. Наиболее распространённой для этой цели фигурой является гиперпараллелепипед. В работах Абрамова O.B. [1, 2, 4, 5, 7], Антушева Г.С. [11, 12], Здора В.В. [24, 35, 36], Маслова АЛ. [52, 53], Bandler J.W., Abdel-Malek H.L. [84], Spence R., Soin R.S. [113], Taylor N.H. [118] и других авторов [33, 39, 69] рассматривается задача построения вписанных и описанных гиперпараллелепипедов (брусов). Помимо представления ОР с помощью гиперпараллелепипедов в некоторых работах для этой цели используются эллипсоиды, например в работе Горячева JI.B. и Здора В.В. [25], Диго Г.Б. и Диго Н.Б. [31], Дзенскевич Е.А. [32], Sapatnekar S.S. [112] а также в работах [98, 114]. Для описания ОР также применяют методы обхода её контура [37, 87] и построения более сложных фигур, например многоугольников[89]. Недостатком большинства методов, в частности обхода границы ОР, является отсутствие информации о внутрен-ности этой области. Для получения информации о внутренности ОР исполь-зуются методы сканирования области поиска.

Для данной работы особый интерес представляют методы построения ОР по результатам сканирования, основанном на переборе комбинаций значений параметров на некоторой сетке с вычислением выходных характеристик, т.е. многовариантном анализе [19, 60, 54, 70]. Аналогичной задачей является построение поверхности отклика для выбора оптимальных значений параметров [17, 49]. Примером реализации такого метода является модуль оптимизации в программном комплексе «Универсальный механизм» [66] для исследования поведения сложных механических систем при различных режимах их функционирования и выбора их оптимальных параметров.

Геометрическая аппроксимация ОР дискретным множеством параллелепипедов на основе результатов зондирования пространства параметров рассматривается в работах [86, 98], причём в последней используется дополнительно рекуррентное разбиение граничных параллелепипедов. Стоит отметить, что в этих работах не описываются используемые структуры данных и алгоритмы, реализующие эти методы, а также возникающие при этом трудности.

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

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

В основу алгоритмов построения ОР в данной работе положен метод матричных испытаний (ММИ)[19, 54, 70], суть которого состоит в переборе вариантов значений параметров системы на регулярной сетке, и метод аппроксимации ОР множеством непересекающихся гиперпараллелепипедов.

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

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

Описанные в работе методы и алгоритмы ориентированы, в первую очередь, на решение задачи параметрического синтеза первого уровня (ПС-1) [1], когда информация о закономерностях изменения значений параметров элементов полностью отсутствует, а модель системы задана в алгоритмическом виде и представляет собой «чёрный ящик», что не позволяет применять аналитические методы исследования. Стоит также отметить возможность применения предложенных в работе методов построения и анализа ОР к моделям объектов, не имеющих отношения к техническим, но которые достаточно сложны для аналитического описания и анализа.

Цель работы

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

Задачи исследования

Для достижения поставленной цели работы были решены следующие задачи:

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

2. Разработка и программная реализация алгоритмов декомпозиции задачи построения ОР для её параллельной реализации с учётом балансировки вычислительной нагрузки между узлами несимметричной параллельной вычислительной системы.

3. Разработка и программная реализация алгоритмов снижения избыточности данных в сеточном представлении ОР путём применения алгоритмов сжатия и использования нерегулярных сеток для построения ОР.

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

5. Разработка и программная реализация алгоритмов выбора оптимальных значений номиналов параметров по критерию запаса работоспособности.

Методы исследования основываются на применении основ теории надёжности и схемотехнического проектирования, методов оптимизации, численных методов, основ дискретной математики, а также технологий параллельных и распределённых вычислений.

Научная новизна

1. Предложена оригинальная структура данных, описывающая представление ОР множеством элементарных параллелепипедов по результатам зондирования области поиска на основе ММИ. Характерным отличием предложенной структуры от матрицы несовместных ситуаций, применяемой в ММИ, является использование одномерного массива для хранения результатов зондирования на многомерной регулярной сетке. Использование одномерной структуры позволяет без особых затруднений разбивать её на блоки произвольных объёмов для решения задачи построения ОР с применением параллельных вычислений.

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

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

На защиту выносятся

1. Описание структур данных и использующие их алгоритмы построения ОР с помощью регулярных и нерегулярных детализированных сеток, а также алгоритмы уменьшения объёмов данных сеточного представления ОР.

2. Алгоритм декомпозиции задачи построения ОР с учётом балансировки вычислительной нагрузки при её параллельной реализации на несимметричной распределённой вычислительной системе.

3. Алгоритмы анализа OP, состоящие из алгоритма проверки связности сеточного представления области и визуализации сечений.

4. Алгоритмы вычисления оптимальных значений параметров с использованием детерминированного критерия максимального запаса работоспособности.

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

Практическая ценность работы

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

Научные результаты работы использованы в ФГУП «Центральный научно-исследовательский институт автоматики и гидравлики» (ФГУП «ЦНИИАГ») для получения характеристик областей работоспособности, назначения допусков и номинальных значений параметров при разработке технических устройств и систем специального назначения.

Апробация результатов работы

Полученные результаты обсуждались на международных симпозиумах «Надежность и качество» (Пенза, 2005 - 2010); Азиатской международной конференции по проблемам управления (ASCC) (Бали, 2006); Международной конференции по проблемам оптимизации и оптимального управления (СООС) (Улан-Батор, 2007); Российской конференции «Дискретная оптимизация и исследование операций» (DOOR) (Владивосток, 2007); международной конференции по промышленным технологиям и управлению (IEEM) (Сингапур, 2007); Дальневосточной математической школе-семинаре им. академика Е.В.

Золотова (Владивосток, Хабаровск, 2005 - 2010); Международной конференции студентов, аспирантов и молодых ученых «Интеллектуальный потенциал вузов - на развитие Дальневосточного региона России и стран АТР» (Владивосток, 2006 - 2009); а также научных семинарах Института автоматики и процессов управления ДВО РАН.

Публикации

По теме диссертации опубликовано 27 работ, среди которых 3 из списка изданий, рекомендованных ВАК.

Научные программы

Решение задач диссертационной работы выполнялось в рамках следующих научных проектов и программ:

1. Проект РФФИ 05-08-01398-а: «Оптимальное проектирование технических систем с учетом вариаций параметров и требований надежности»;

2. 06-1-ЭММПУ-054 Программа №15 отделения ЭММПУ РАН: «Разработка методов, алгоритмов и программных средств параметрического синтеза стохастических систем»;

3. Проекты ДВО РАН:

• 06-III-A-03-070: «Разработка комплекса алгоритмов и программ параметрического синтеза по критерию надежности»;

• 09-III-B-03-082: «Разработка программного комплекса построения и анализа областей работоспособности аналоговых технических систем на основе технологии распределенных вычислений»;

• 10-III-B-03-035: «Разработка алгоритмических и программных средств оптимального выбора номиналов параметров в условиях неопределённости».

Структура диссертации

Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы и шести приложений. Основной объём диссертации составляет 150 страниц, в который входят: библиографический список из 119 наименований, 38 рисунков и 6 таблиц.

5.5 Выводы по главе

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

Для балансировки вычислительных нагрузок предлагается два метода: балансировка по вычислительным мощностям узлов и автобалансировка, основанная на декомпозиции задачи на достаточно большое количество небольших по объёму подзадач и организации их раздачи в режиме FCFS / FIFO, когда каждый вычислительный узел по мере завершения работы с текущей подзадачей и отправки результатов главному процессу получает следующее задание из очереди. В результате такой декомпозиции вычислительные узлы, имеющие наибольшую вычислительную мощность, обработают большее количество заданий, а узлы с более низкими вычислительными показателями — меньшее. Кроме этого, при автобалансировке достигается асинхронность обмена данными между управляющим узлом и различными вычислительными узлами, что исключает пиковую нагрузку на коммуникационную среду. Балансировка вычислительных нагрузок по мощностям узлов заключается в предварительном получении сведений о вычислительных возможностях узлов путём измерения времени, потраченного на выполнение тестового задания каждым из них.

Реализация рассмотренных методов параллельного построения ОР рассматривается на РВС, узлами которой являются рабочие станции, объединённые в локальную компьютерную сеть. Топология РВС, состоящей из узлов двух типов: одного управляющего и нескольких (количество теоретически не ограничено) вычислительных, имеет централизованный тип «звезда», а взаимодействие узлов в рамках этой топологии имеет характер клиент-серверного, при котором управляющий узел находится в состоянии ожидания запросов от вычислительных узлов, а жизненный цикл приложения на вычислительном узле состоит из периодических запросов к управляющему узлу (наиболее частым и основным является запрос задания для обработки).

На примере решения задачи построения ОР с использованием РВС из рабочих станций локальной компьютерной сети типа Ethernet / Fast Ethernet показано, что балансировка вычислительных нагрузок на узлы РВС достигается с одинаковой эффективностью для обоих рассмотренных алгоритмов декомпозиции с учётом балансировки в указанных пределах, программная реализация рассмотренных алгоритмов позволяет создать «самодостаточные» программные модули РВС, работающие с функциями операционной системы, что позволяет использовать для расчётов практически любую сеть пользовательских компьютеров и рабочих станций, поддерживающую протокол ТСРЛР, без установки дополнительного программного обеспечения и привлечения дополнительного оборудования.

137

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

Разработаны и программно реализованы алгоритмы анализа сеточного представления ОР, выполняющие визуализацию сечений СПОР и проверку связности области с выделением её связных подобластей. Разработаны и программно реализованы алгоритмы выбора оптимальных значений номиналов параметров по детерминированному критерию запаса работоспособности.

1. Абрамов O.B. Параметрический синтез стохастических систем с учетом требований надежности. — М.: Наука, 1992. - 176 с.

2. Абрамов О.В., Бернацкий Ф.И., Здор В.В. Параметрическая коррекция систем управления. -М.: Энергоиздат, 1982. — 176 е., ил.

3. Абрамов О.В., Диго Г.Б, Диго Н.Б., Катуева Я.В. Параллельные алгоритмы построения области работоспособности // Информатика и системы управления. -2004. №2(8). - с. 121 - 133.

4. Абрамов О.В., Здор В.В., Супоня A.A. Допуски и номиналы систем управления. -М.: Наука, 1976. 160 с.

5. Абрамов О.В., Инберг С.П. Параметрический синтез настраиваемых технических систем. -М.: Наука, 1986. — 125 с.

6. Абрамов О.В., Катуева Я.В., Назаров Д.А. Оптимальный параметрический синтез по критерию запаса работоспособности // Проблемы управления, №6, 2007, С 64-69.

7. Абрамов О.В., Розенбаум А.Н. Выбор номинальных значений параметров элементов корректирующих звеньев / Качество и надежность систем управления. Сборник научных трудов. Владивосток: ДВНЦ АН СССР, 1977. сЗ-14.

8. Авхач М.Я., Краснов И.А., Светликов Ю.А. Настройка технических объектов на основе метода областей работоспособности // Управление качеством и надежностью сложных систем. Владивосток: ДВНЦ АН СССР, 1978. с. 66-75.

9. Амосов A.A., Дубинский Ю.А., Копченова Н.П. Вычислительные методы для инженеров. М.: Мир, 1998.

10. Андреев А., Воеводин В., Журматий С. Кластеры и суперкомпьютеры -близнецы или братья? // Открытые системы — URL: http://\vwvv.osp.ru/os/2000/05-06/178019/ . Дата обращения: 13.07.2010.

11. Антушев Г.С. Методы параметрического синтеза сложных технических систем. -М.: Наука, 1989.

12. Баканов В.М. Параллельные вычисления: Учебное пособие / В.М.Баканов. М.: МГУПИ, 2006. 124 с.

13. Батшцев Д.И. Методы оптимального проектирования: Учеб. пособие для вузов. М: Радио и связь, 1984. — 248 е., ил.

14. Батшцев Д.И. Поисковые методы оптимального проектирования. М.: Сов. радио, 1975.-216 е., ил.

15. Беккер П., Йенсен Ф. Проектирование надежных электронных схем. Пер. с англ. Под ред. И. А. Ушакова, М.: Сов. радио, 1977. 256 с.

16. Бусленко Н.П., Голенко Д.И., Соболь И.М., Срагович В.Г., Шрейдер Ю.А. Метод статистических испытаний (метод Монте-Карло). М.: ФизМатГИз, 1962. 332 с.

17. Васильев Б.В., Козлов Б.А., Ткаченко Л.Г. Надежность и эффективность радиоэлектронных устройств. М.: Сов. радио, 1964. - 368 с.

18. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. М.: ДИАЛОГ-МИФИ, 2002. 384 с.

19. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. М.: Мир, 1989. -360 е., ил.

20. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. — СПб.: БХВ-Петербург, 2002. 608 е., ил.

21. Гатчин Ю.А., Коробейников А.Г. Основы криптографических алгоритмов: Учебное пособие. СПб: ГИТМО (ТУ), 2002. 29 с.

22. Горелова Г.В., Здор В.В., Свечарник Д.В. Метод оптимума номинала и его применение. М.: Энергия, 1970.-200 с.

23. Горячев Л.В., Здор В.В. Построение областей качества по результатам наблюдений / Качество и надежность систем управления. Сборник научных трудов. Владивосток: ДВНЦ АН СССР, 1977. с 104 - 110.

24. ГОСТ 27.002-89. Надежность в технике. Основные понятия. Термины и определения. М.: Государственный комитет СССР по стандартам, 1989.

25. Гродзенский С.Я. Статистические методы контроля и управления качеством: учебное пособие. М.: Московский государственный институт радиотехники, электроники и автоматики (технический университет), 2006. - 84 с.

26. Грэхэм Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики: Пер. с англ. — М.: Мир, 1998. 703 е., ил.

27. Данскин Дж. М. Теория максимина и ее приложение к задачам распределения вооружения. Берлин, Нью-Йорк, 1967. Пер. с англ. М. В. Воронова, под ред. И. Н. Коваленко. М.: Сов. радио, 1970, 200 с.

28. Дианов В.Н. Сбои в технических системах. — М.: Машиностроение, 1999. -69 с.

29. Диго Г.Б., Диго Н.Б. Использование эллипсоидов для описания области работоспособности // Информатика и системы управления. 2008. №1(15).-с. 22-28.

30. Диго Г.Б., Диго Н.Б., Катуева Я.В. Применение детерминированных критериев в задачах стохастической оптимизации // Информатика и системы управления. 2006. №2(12). - с. 82 - 88.

31. Дзенскевич Е.А. Аппроксимация областей допустимого качества областями стандартного вида / Параметрическая оптимизация технических систем. Сборник научных трудов. Владивосток: ДВНЦ АН СССР, 1983. с 29-33.

32. Дружинин Г.В. Надежность автоматизированных производственных систем. — М.: Энергоатомиздат, 1986. —480 е.: ил.

33. Здор В.В. Исследование и разработка методов параметрического управления качеством технических систем: Дис. докт. техн. наук. Владивосток: Институт автоматики и процессов управления ДВНЦ АН СССР. 1979. - 305 с.

34. Здор В.В. Параметрическое управление серийнопригодностью технических систем / Параметрическая оптимизация технических систем. Сборник научных трудов. Владивосток: ДВНЦ АН СССР, 1983. с 3 - 16.

35. Здор В.В., Кочубиевский И.Д. Об одном методе определения областей допустимых вариаций параметров автоматических систем. // Изв. АН СССР: Техническая кибернетика, №6, 1966. с. 52 56.

36. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие. — Владивосток: ДВГТУ, 2000.-288 с.

37. Иншаков А.Н., Иншаков С.А. Допусковый анализ при проектировании сложных технических систем // Информационные технологии. 1997. -№ 1.-е. 34-39

38. Катуева Я.В. Разработка и анализ параллельных алгоритмов параметрического синтеза для массивно-параллельных суперкомпьютеров: Дис. канд. техн. наук /Я.В. Катуева Владивосток: Институт автоматики и процессов управления ДВО РАН, 2004. - 146 с.

39. Катуева Я.В., Назаров Д.А. Алгоритмы анализа области работоспособности, заданной в матричной форме // Информатика и системы управления. №2(10), 2005. с. 118 128.

40. Катуева Я.В., Назаров Д.А. Аппроксимация и построение областей работоспособности в задаче параметрического синтеза // Международный симпозиум «Надежность и качество», Пенза: ПГУ, 2005. с. 130 — 134

41. Кнут Д. Э. Искусство программирования для ЭВМ т.1. Основные алгоритмы. -М.: Мир, 1976. 736 с.

42. Кнут Д. Э. Искусство программирования, том 4., выпуск 2. Генерация всех кортежей и перестановок.: Пер. с англ. М.: ООО «О.Д. Вильяме», 2008 -160 с.

43. Козлов Б.А., Ушаков И.А. Справочник по расчету надежности аппаратуры радиоэлектроники и автоматики. М.: Сов. радио, 1975. - 472 с.

44. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. Изд. четвертое, пер. со второго американского перераб. изд. -М.: Наука, 1978. 832 с.

45. Лебедев A.C., Лисейкин В.Д., Хакимзянов Г.С. Разработка методов построения адаптивных сеток // Вычислительные технологии. 2002. Т.7. № 3. — с. 29-43.

46. Ллойд Д.К., Липов М. Надежность. Организация исследования, методы, математический аппарат. Пер. с англ. Под ред. Бусленко Н.П. — М.: Сов. радио, 1964. 686 с.

47. Любченко В. О борьбе с рекурсией // Открытые системы URL: http://vnvw.osp.ru/pcworld/2002/l 1/164417/. Дата обращения: 31.07.2010.

48. Мартыненко С.И. Программное обеспечение для универсальной многосеточной технологии // Математическое моделирование, том 14, № 9, 2002.-е. 87-90.

49. Маслов АЛ. Оптимизация параметрической надежности радиоэлектронной аппаратуры при ее проектировании // Управление и информация, выпуск 6: Параметрическая надежность и чувствительность. Владивосток: ДВНЦ АН СССР, 1973. с. 73 - 97.

50. Маслов А.Я., Татарский В.Ю. Повышение надежности радиоэлектронной аппаратуры. -М.: Сов. радио, 1972. —264 с.

51. Михайлов А.В., Савин С.К. Точность радиоэлектронных устройств. М.: Машиностроение, 1976.-214 с.

52. Назаров Д.А. Двоичная многоуровневая детализация элементов сеточного представления области работоспособности // Надежность и качество — 2010: труды Международного симпозиума: 2 т./ под ред. Н.К. Юркова. -Пенза: Изд-во ПТУ, 2010. 1 т., с. 337-341.

53. Назаров Д.А. Детализация матричного представления области работоспособности в задаче параметрического синтеза // Международный симпозиум «Надежность и качество», Пенза: ИГУ, 2006, С. 218 220.

54. Назаров Д.А. Использование распределенных вычислений при построении области работоспособности // Информатика и системы управления -2008 -№1(15)-с. 142-151.

55. Норенков И.П. Основы автоматизированного проектирования. М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. 336 с.

56. Норенков И.П., Маничев В.Б. Основы теории и проектирования САПР: Учеб для втузов по спец. «Вычислительные маш., компл., сист. и сети». -М.: Высш. шк., 1990. 335 е.: ил.

57. Норенков И.П., Мулярчик С.Г., Иванов С.Р. Экстремальные задачи при схемотехническом проектировании в электронике Минск, 1976. - 240 с.63.