Содержание к диссертации
Введение
Глава 1. Постановка задачи построения области работоспособности 16
1.1. Основные понятия и определения 16
1.2. Задача параметрического синтеза 21
1.3. Постановка задачи построения области работоспособности 21
1.4. Выводы по главе 22
Глава 2. Алгоритм построения области работоспособности с помощью регулярной сетки 23
2.1 Сеточное представление области поиска 25
2.1.1. Использование регулярной сетки 25
2.1.2. Структуры данных сеточного представления области поиска 27
2.1.3. Алгоритмы инициализации массива состояний элементов сеточного представления области поиска 34
2.1.4. Оценка сложности алгоритмов инициализации массива состояний 40
2.2. Алгоритм сужения области поиска описанным. параллелепипедом 45
2.2.1. Построение описанного параллелепипеда методом статистических испытаний (Монте-Карло) 47
2.3. Выводы по главе 50
Глава 3. Алгоритмы уменьшения объёмов данных сеточного представления области работоспособности 52
3.1. Применение алгоритмов сжатия к массиву состояний сеточного представления области работоспособности 52
3.1.1. Двоичное (битовое) представление массива состояний 53
3.1.2. Кодирование длин серий элементов массива состояний 60
3.1.3. Инициализация массива состояний в сжатом виде 64
3.1.4. Сравнительные характеристики алгоритмов сжатия массива состояний 65
3.2. Снижение избыточности данных геометрического
представления области работоспособности 67
3.2.1. Проблема точности построения области работоспособности помощью регулярной сетки 67
3.2.2. Алгоритмы построения области работоспособности с использованием нерегулярных сеток 71
3.2.3. Двухуровневая детализация 72
3.2.4. Многоуровневая двоичная детализация 75
3.3. Выводы по главе 82
Глава 4. Алгоритмы анализа и оптимизации с использованием сеточного представления области работоспособности 83
4.1. Алгоритмы выбора оптимальных элементов сетки по критерию запаса работоспособности 83
4.1.1. Алгоритм расчёта наименьшего расстояния до границы области работоспособности с помощью построения вписанного куба 85
4.1.2. Алгоритм расчёта наименьшего расстояния до границы области работоспособности методом проверки r-окрестности 91
4.1.3. Алгоритм выбора элементов сетки, максимально удалённых от границы области работоспособности 95
4.2. Алгоритм проверки связности сеточного представления области 97
4.3. Алгоритм визуализации сечений сеточного представления области работоспособности 106
4.4. Выводы по главе 110
Глава 5. Параллельный алгоритм построения области работоспособности для реализации на распределённой вычислительной системе 111
5.1. Сокращение времени построения области работоспособности с помощью параллельных вычислений 111
5.2. Параллельный алгоритм построения области работоспособности с помощью регулярной сетки 114
5.2.1. Декомпозиция с учётом балансировки вычислительной нагрузки между процессами 115
5.2.2. Взаимодействие вычислительных процессов с главным процессом 121
5.3. Применение распределённой несимметричной архитектуры вычислительной системы для решения задачи построения области работоспособности 128
5.4. Анализ эффективности параллельного алгоритма построения области работоспособности с использованием распределённой вычислительной системы 130
5.5. Выводы по главе 135
Заключение 137
Литература 139
Приложения 150
- Структуры данных сеточного представления области поиска
- Кодирование длин серий элементов массива состояний
- Алгоритм расчёта наименьшего расстояния до границы области работоспособности методом проверки r-окрестности
- Декомпозиция с учётом балансировки вычислительной нагрузки между процессами
Введение к работе
Актуальность работы. Переход на инновационный путь развития связан с необходимостью создания технических устройств и систем, обладающих требуемыми характеристиками качества и надёжности.
Отечественный и зарубежный опыт проектирования и эксплуатации систем различного назначения показывает, что значительную часть отказов составляют постепенные (параметрические) отказы, а задача учёта отклонений параметров от расчётных значений и обеспечение требуемого качества допуска при наличии таких отклонений является одной из наиболее сложных и трудоёмких задач проектирования. По мере усложнения технических объектов, повышения требований к их надёжности и увеличения ответственности выполняемых ими функций необходимость и важность решения этой задачи постоянно возрастает.
Важное место в процессе проектирования занимает задача построения области, в пределах которой система остаётся устойчивой по отношению к параметрическим возмущениям. Эта область называется областью работоспособности (ОР) системы.
Решение задачи построения ОР позволяет оценить способность системы сохранять работоспособность при отклонениях параметров её элементов от расчётных значений, вызванных различными технологическими и эксплуатационными факторами, назначать допуски на параметры элементов, выбирать оптимальные в том или ином смысле номинальные значения параметров.
Задача построения и анализа ОР рассматривалась в работах отечественных ученых, таких как Б.В. Васильев, Г.В. Дружинин, В.В. Здор, А.В. Маслов, Ю.Е. Смагин, А.В. Фомин и ряда зарубежных исследователей как Е. Buttler, R.Spence, S. Sapatnekar, N. Taylor и др.
Основные трудности, возникающие при решении задач построения, анализа и интерпретации ОР, связаны с высокой размерностью пространства исследуемых параметров и отсутствием априорной информации о конфигурации областей. Для получения конструктивных сведений об ОР необходимо иметь эффективные методы и алгоритмы их построения и представления в виде, позволяющем оценивать особенности их конфигурации и осуществлять оптимальный выбор номиналов параметров и допусков.
Существующие алгоритмы оценивания и приближения ОР основаны на использовании известных фигур, таких как многомерные эллипсоиды, гиперпараллелепипеды (вписанные или описанные), различные комбинации и объединения этих фигур.
В основу алгоритмов построения ОР в данной работе положен аппарат компьютерного имитационного моделирования процессов функционирования исследуемых сложных систем и метода многомерного зондирования на регулярной сетке -компьютерная реализация метода матричных испытаний (ММИ). Изначально ММИ был ориентирован на физическое моделирование радиоэлектронных устройств путём включения в схемы элементов с различными номинальными значениями, однако привлечение в дальнейшем для его реализации компьютерного
моделирования не привело к широкому распространению из-за крайне высокой трудоёмкости, связанной с полным перебором. Развитие вычислительной техники, стремительный рост её мощности за последние 20 лет и развитие технологий параллельных и распределённых вычислений позволяют решать такого рода задачи за приемлемое время.
Целью работы является разработка и исследование алгоритмических методов построения ОР, основанных на многовариантном анализе с представлением области дискретным множеством параллелепипедов и ориентированных на технологии параллельных вычислений, а также методов анализа ОР в таком представлении.
Задачи исследования. Для достижения поставленной цели работы были решены следующие задачи:
Разработка и программная реализация эффективных методов построения многомерных ОР с помощью дискретного множества параллелепипедов, заданных регулярной сеткой (сеточное представление ОР).
Разработка и программная реализация алгоритмов декомпозиции задачи построения ОР для её параллельной реализации с учётом балансировки вычислительной нагрузки между узлами несимметричной параллельной вычислительной системы.
Разработка и программная реализация алгоритмов снижения избыточности данных в сеточном представлении ОР путём применения алгоритмов сжатия и использования нерегулярных сеток для построения ОР.
Разработка и программная реализация алгоритмов анализа сеточного представления ОР, реализующих проверку связности области и выделение её связных подобластей, а также визуализацию сечений ОР.
5. Разработка и программная реализация алгоритмов выбора оптимальных зна
чений номиналов параметров по критерию запаса работоспособности.
Методы исследования основываются на применении основ теории надёж
ности и схемотехнического проектирования, методов оптимизации, численных
методов, основ дискретной математики, а также технологий параллельных и распре
делённых вычислений.
Научная новизна.
Предложена оригинальная структура данных, описывающая представление ОР множеством элементарных параллелепипедов по результатам зондирования области поиска на основе ММИ. Характерным отличием предложенной структуры от матрицы несовместных ситуаций, применяемой в ММИ, является использование одномерного массива для хранения результатов зондирования на многомерной регулярной сетке. Использование одномерной структуры позволяет без особых затруднений разбивать её на блоки произвольных объёмов для решения задачи построения ОР с применением параллельных вычислений.
Разработаны методы декомпозиции задачи построения ОР по данным, описанным предложенной структурой, с возможностью статичной или динамической балансировки вычислительной нагрузки между узлами параллельной разнородной вычислительной системы.
З. Разработанные на основе предложенного представления OP алгоритмы уменьшения избыточности информации на уровне данных массива состояний и на уровне структуры сетки позволяют снизить объёмы используемых ресурсов при хранении и передаче данных представления ОР. На защиту выносятся.
Описание структуры данных и использующие их алгоритмы построения ОР с помощью регулярных и нерегулярных детализированных сеток, а также алгоритмы уменьшения объёмов данных сеточного представления ОР.
Алгоритм декомпозиции задачи построения ОР с учётом балансировки вычислительной нагрузки при её параллельной реализации на несимметричной распределённой вычислительной системе.
Алгоритмы анализа ОР, выполняющие проверку связности сеточного представления области и визуализацию сечений.
4. Алгоритмы вычисления оптимальных значений параметров с использованием
детерминированного критерия максимального запаса работоспособности.
Достоверность результатов исследования обеспечивается корректным при
менением методов исследования и подтверждается результатами вычислительных
экспериментов.
Практическая ценность работы. Результаты работы направлены, в первую очередь, на их применение на начальных стадиях проектирования сложных технических систем с заданной топологией для нахождения оптимальных значений параметров их элементов, а также для назначения или коррекции значений допусков.
Научные результаты работы использованы в ФГУП «Центральный научно-исследовательский институт автоматики и гидравлики» (ФГУП «ЦНИИАГ») для получения характеристик областей работоспособности, назначения допусков и номинальных значений параметров при разработке технических устройств и систем специального назначения.
Решение задач диссертационной работы выполнялось в рамках следующих научных проектов и программ: РФФИ 05-08-01398-а; 06-1-ЭММПУ-054 Программа №15 отделения ЭММПУ РАН, Проекты ДВО РАН ( 06-Ш-А-03-070, 09-Ш-В-03-082, 10-Ш-В-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] - описание способа применения структур данных представления ОР для решения задачи выбора номиналов параметров на начальных стадиях проектирования.
Структуры данных сеточного представления области поиска
Построение ОР позволяет избежать трудоёмких расчётов значений выходных параметров с целью проверки выполнения УР, а также даёт возможность решать задачу ПС путём выбора оптимального вектора параметров с использованием детерминированных критериев, например, критерия максимального запаса работоспособности [1, 6, 12, 32, 62].
Задача построения ОР формулируется следующим образом. Пусть задана модель (1.1) сложной аналоговой системы, связывающая параметры составляющих её элементов с её выходными характеристиками. Также заданы ограничения (1.8) на значения выходных параметров - условия работоспособности, и ограничения на значения внутренних параметров - допуски (1.5). Требуется в пространстве внутренних параметров построить фигуру с известной конфигурацией и характеристиками, которая бы являлась приближением к неизвестной истинной области Dx.
В главе изложены основные понятия теории надёжности, в качестве рассматриваемой предметной области приведена задача параметрического синтеза, являющаяся одним из этапов проектирования сложных технических систем. Дано определение ОР и показаны преимущества, которые даёт её построение при решении задачи оптимального параметрического синтеза с использованием стохастических критериев, а также иной путь решения этой задачи с использованием детерминированных критериев. Поставлена задача построения ОР.
Решение задачи параметрического синтеза с использованием вероятностного критерия (1.10) зачастую сопровождается большими вычислительными затратами в силу многократного расчёта модели методом статистических испытаний, а также в силу большого количества внутренних параметров системы и сложности модели (1.1). Основным фактором общей высокой вычислительной трудоёмкости метода является отсутствие априорной информации об области Dx в выражении (1.10) и, как следствие, замена проверки xeDx проверкой выходных параметров на соответствие требованиям УР (1.8).
В случае, когда задана область Dx так, что можно проверить принадлежность реализации вектора x внутренних параметров этой области, устраняется необходимость в трудоёмких расчетах выходных параметров y j (x), и проверке выполнения УР, что существенно облегчает, например, расчёт надёжности по стохастическому критерию методом Монте-Карло или позволяет использовать детерминированные критерии типа запаса работоспособности [1, 6, 12, 32, 62].
В данной работе предлагаются алгоритмы построения ОР, в основе которых лежит идея аппроксимации фигуры множеством непересекающихся n-мерных параллелепипедов. В данном случае под словом «аппроксимация» подразумевается приближение, однако точные параметры области Dx неизвестны, что заставляет искать несколько иные методы оценки точности приближения. В основе такого представления области поиска лежит метод матричных испытаний (ММИ) [19, 54, 70]. Этот метод можно рассматривать как расширение на произвольное число варьируемых параметров широко распространённого метода граничных испытаний [19, 118]. Своё название он получил в связи с тем, что перебор состояний в системе здесь осуществляется в соответствии с неслучайной программой (матрицей ситуаций). Следует отметить, что ММИ изначально был ориентирован на комплексирование с системами физического моделирования. Реализация этого метода с привлечением компьютерного моделирования не получила широкого распространения в связи с его крайне высокой трудоёмкостью. Интенсивное развитие и распространение технологии параллельных и распределённых вычислений на сегодняшний день позволяют применить такого рода методы для решения задачи построения ОР.
Рассматриваемый алгоритм состоит из двух шагов. На первом шаге выполняется построение описанного вокруг неизвестной области Dx п -мерного параллелепипеда, что позволяет сузить область поиска и отбросить из рассмотрения те её части, в которых точки ОР отсутствуют (или образуют множества, которыми можно пренебречь). На втором шаге на этот п -мерный параллелепипед накладывается сетка, которая разбивает параллелепипед на множество непересекающихся элементарных параллелепипедов. В специально выбранной «точке-представителе» каждого из элементарных параллелепипедов вычисляются выходные параметры, проверяются УР, что выделяет из множества элементарных параллелепипедов подмножество, которое является аппроксимацией искомой ОР [42, 43].
Кодирование длин серий элементов массива состояний
В данной главе рассматривается проблема уменьшения избыточности данных СПОР. Предлагаются два подхода, один из которых направлен на снижение избыточности данных в МС регулярной сетки путём сжатия данных, а второй подход направлен на уменьшение избыточности на уровне сеточного представления, который основан на использовании нерегулярных сеток с различной степенью детализации области поиска. Построение таких сеток основано на концепции многосеточных методов [51, 119].
Из описанных компонентов структуры данных СПОР (2.10) наибольший объём для хранения требует МС. В главе 2 было показано, что МС представляет собой набор из R = q1 Ц2 ... Чп (2.3) элементов. При программной реализации алгоритмов 2.1 - 2.4 в качестве МС для быстрого доступа к его элементам удобно использовать массив байт, поскольку в большинстве архитектур современных компьютеров байт является наименьшим адресуемым элементом. Для достаточно сложных моделей (1.1) исследуемых систем этот подход требует больших ресурсов для хранения МС в таком формате. Например, для модели, состоящей из 7 параметров в случае разбиения каждого параметра на 20 квантов qt = 20, V/ = 1,2,...,w, потребуется 20 =1 280 000 000 байт памяти, а в случае 8 параметров - уже 25 600 000 000 байт. Если объёмом данных в первом случае в состоянии оперировать среднестатистический современный пользовательский компьютер (по результатам исследований DRAMeXchange [91]), то во втором случае наверняка потребуется вычислительная техника из класса суперкомпьютеров [22]. Помимо хранения МС в оперативной памяти немаловажным является хранение его на различного рода накопителях и передача его данных по сети, в том числе при решении задачи построения ОР с использованием распределённых вычислений, о чём пойдёт речь в пятой главе. В такой ситуации возникает проблема поиска путей уменьшения объёма данных, используемых для хранения МС. При этом необходимо использовать методы сжатия без потери информации [111], и дополнительным требованием является возможность доступа к элементам МС в сжатом виде, т.е. без его полной распаковки.
Рассматриваемые далее алгоритмы сжатия применяются только к нормированному МС. Напомним, что это условие означает наличие в МС только элементов, принимающих значения из ножества {0,1}: S[р] є {0,1}, \/p = 1,2,...,R. Помимо МС далее в рассмотрении также будет фигурировать упакованный массив состояний (УМС) Sc =(s?,S2,...,scR ), структура элементов sf, і = 1,2,...,Rc которого зависит от используемого метода сжатия и описывается отдельно. Количество элементов в УМС Rc также зависит от метода сжатия. Для обозначения отдельного /-го элемента УМС sf ,i = 1,2,...,Rc будет использоваться запись Sc [і].
Использование одного байта для хранения элемента МС является удобным при практической реализации, однако такой подход предопределяет избыточность данных, поскольку для представления значений из множества {0,1} достаточно только одного бита. Удобство использования байтов и трудность доступа к отдельным битам состоит в том, что в большинстве архитектур ЭВМ минимально адресуемым элементом памяти является байт (в самых распространённых компьютерах семейства x86 IBM PC байт состоит из 8 бит [67, 99]), а для считывания и записи значений отдельного бита требуются дополнительные операции двоичной арифметики.
В рассматриваемом случае термин «избыточность» относится не к самим данным МС, а к их внутреннему представлению в памяти ЭВМ. С точки зрения внутреннего (двоичного) представления МС уместнее было бы говорить о «разреженности» значимых данных, когда из каждых восьми бит (двоичных разрядов) информацию несёт только один, а оставшиеся семь бит остаются неиспользованными. В связи с этим задача уменьшения объёма данных МС заключается в их «уплотнении» посредством использования всех двоичных разрядов в некоторой последовательности байтов, являющейся УМС. Таким образом, УМС в данном случае представляет собой непрерывный байт-массив
Scbit , в котором каждый бит содержит информацию о соответствующем элементе МС. Далее этот байт-массив будет называться двоичным (битовым) представлением МС. Для доступа к определённому элементу МС с целью чтения или записи нет необходимости конвертировать битовое представление МС в «удобный» формат, когда каждый его элемент представляется одним байтом. Организации возможности такого доступа посвящён данный раздел.
Задача, которую необходимо решить в рамках реализации механизмов доступа к элементам двоичного представления МС, состоит в разработке алгоритмов чтения и записи значений определённого его двоичного разряда, соответствующего индексу p МС. Требуется установить взаимосвязь между индексом p элемента МС и p-м разрядом (битом) в УМС. Порядок расположения элементов УМС строго соответствует расположению элементов МС, и нумерация осуществляется в порядке старшинства двоичных разрядов во всей непрерывной последовательности байт УМС. Например, значение первого элемента МС записано в младшем разряде первого байта УМС, значение восьмого элемента МС содержится в самом старшем разряде первого байта УМС, а значение девятого элемента МС - в младшем разряде второго байта УМС. Поскольку минимальным адресуемым элементом является байт, то доступ к p-му двоичному разряду УМС осуществляется путём вычисления номера соответствующего байта в УМС, а затем – номера двоичного разряда в этом байте. Считывание значения разряда или запись осуществляется путём т.н. маскирования, т.е. наложения битовой маски – выполнения поразрядных операций двоичной арифметики над группами разрядов (байтов) [94].
Алгоритм расчёта наименьшего расстояния до границы области работоспособности методом проверки r-окрестности
Примечания к алгоритму 4.13: каждая итерация внешнего цикла осуществляет обход одной связной подобласти, поэтому в случае, если исследуемая область m является несвязной и состоит из m связных подобластей Bx = IJ Bi , установка i=1 счётчика итераций в теле цикла позволит определить количество m связных подобластей. В случае несложной доработки алгоритмов 4.10 и 4.11 (передача в качестве параметра нужного значения маркера) можно выполнять маркировку элементов сетки подобластей Bi различными значениями. Выполнять обход можно не только по однотипным элементам подмножества Bx , но и по Bx . В этом случае необходимо ввести дополнительные обозначения маркеров для пройденных элементов подмножества Bx (в рассмотренном выше алгоритме использовался обход только элементов подмножества Bx , а элементы подмножества B имели значение 0 в массиве состояний S[R]). Практическая польза от поиска связных подмножеств Bx ={J Bi заключается в возможности отыскания такого подмножества B7 с Bx , ни один элемент которого не имеет общей границы с гиперпараллелепипедом Bx, т.е. Vek 1 k 2. kn єBІ: 1 ki qi, Vi = 1,2,...,n, что позволяет сделать предположение, что область, представленная множеством B не является односвязной. Алгоритмическую сложность процедуры обхода однотипных элементов сетки оценить затруднительно из-за необходимости знать количество этих элементов. Приблизительную оценку сложности алгоритма можно выполнить из следующих соображений. Внешний цикл в алгоритме 4.13 выполняется по всем элементам сетки (поиск элемента, имеющего состояние «1»), оценка его сложности составляет 0(R)=0(Qn). Внутри этого цикла выполняется обход области, представленной множеством В% (одним связным или несколькими связными). Из алгоритма 4.10 видно, что проход каждого элемента сетки состоит в поиске маршрута по всем сопряжённым 2п элементам c обратным преобразованием индексов по алгоритму 2.6, имеющему сложность порядка 0(п ). Если знать количество N„ элементов сетки, принадлежащих подмножеству В% , то получим сложность обхода этих элементов: 0(N„-2n-n ) = = 0(Ngti ). Значение N„ может быть получено прямым подсчётом либо с М „ помощью оценки г\„ =—— 1 методом Монте-Карло, где М„- количество точек, попавших в область В% , из общего их количества М в области Вх., где R - количество элементов сетки (2.3). Таким образом, алгоритмическая сложность процедуры обхода составляет 0(Ng п ) = = 0Внешнего цикла алгоритма 4.13, внутри которого выполняется обход элементов сетки, не усложняет общий алгоритм, поскольку вызов процедуры обхода однотипных элементов сетки вызывается лишь на небольшом количестве раз (количество связных подмножеств), гораздо меньшем количества его итераций. Тогда с учётом этого внешнего цикла итоговая оценка алгоритмической сложности процедуры 4.13 составляет Алгоритм визуализации сечений сеточного представления области работоспособности Для возможности анализировать конфигурацию ОР по отдельным сечениям, а также отслеживать результаты автоматического выбора номинальных значений параметров, допусков с их возможной последующей коррекцией необходимы алгоритмы визуализации отдельных сечений СПОР. Визуализация сечений СПОР заключается в графическом отображении множества В% параллелепипедов е у- ь- є В% , удовлетворяющих условию где IrfjS - множество значений индексов свободных координат (координат отображения), I лх - множество значений индексов фиксированных координат. При этом Irfis и I Ах - вполне упорядоченные множества с линейным порядком, являются частями разбиения множества значений индексов {1,2,3,...,п}, а именно IrfiS z {1,2,3,...,п},1 fix z{1,2,3,...,n},IrfiS Г\1 fix = 0,Icfis U J fix = {1,2,3,...,n} [47]. Задаются, как правило, индексы фиксированных координат I flx с их значениями, а множество I s значений индексов свободных координат определяется вычитанием множества: I s ={1,2,3,...,п}\1 flx. Поскольку практический интерес имеет визуализация двух- и трёхмерных сечений w-мерного сеточного представления, то, очевидно, количество d элементов во множестве IdiS не превышает трёх, а в / лх - не менее г = п — d п-3. Суть алгоритма визуализации заключается в переборе всех возможных комбинаций значений индексов ki, і є I s . Для отображения двух- и трёхмерных сечений без особых затруднений можно составить отдельные алгоритмы, состоящие из, соответственно, двух и трёх вложенных циклов, меняющих значения индексов элементов сетки в позициях, заданных множеством I is. Ниже рассматривается общая процедура визуализации, применимая как для отображения двумерных сечений, так и для трёхмерных. В приведённом ниже алгоритме 4.14 не описываются операции, связанные непосредственно с графическим отображением элементов сетки, масштабированием и другими связанными с этим действия. Выполнение перебора комбинаций свободных индексов kt, / є I is выполняется рассмотренным ранее методом, описанном в алгоритме 2.3 с генерацией возможных комбинаций методом, основанном на алгоритме 2.4. Для инициализации фиксированных индексов kj,jelfix заданными значениями (f1,f2,...,fr),r= I fix необходимо наличие взаимнооднозначного соответствия между элементами множества I flx и элементами (f1,f2,...,fr). Для этого достаточно пронумеровать элементы множества I flx так что Iях =(a1,ci2,...,ar), тогда ка . = Л,у =1,2...,г, а,є/лх. В предложенном ниже алгоритме 4.14 множества I s и / лх представлены нумерованными массивами D и F соответственно, т.е. указанная выше необходимость вводить нумерацию элементов множества I flx при практической реализации снимается. Порядок следования элементов массива F совпадает с порядком следования элементов в массиве I = (f1,f2,...,fr) значений фиксированных индексов.
Декомпозиция с учётом балансировки вычислительной нагрузки между процессами
Как было показано, алгоритмы построения ОР на основе сеточного представления демонстрируют экспоненциальную O(Qn ) вычислительную сложность в зависимости от количества n параметров исследуемой системы. Это связано с необходимостью полного перебора вариаций значений внутренних параметров. На каждой итерации перебора комбинаций значений параметров на сетке выполняется расчёт модели (1.1) и инициализация МС, что значительно увеличивает время решения всей задачи построения ОР. В связи с этим встаёт вопрос о возможности инициализации состояний элементов сетки по частям в параллельно выполняемых процессах.
В разделе 2.1.3 главы 2 при рассмотрении различных алгоритмов, относящихся к построению ОР, также отмечалась возможность их параллельной реализуемости. Способ декомпозиции w-мерной сетки и возможность выполнять инициализацию состояний её элементов в параллельных процессах зависит от выбора алгоритма перебора этих элементов. Как было показано, наибольшей приспособленностью к параллельной реализации обладает алгоритм 2.1, основанный на переборе элементов МС с вычислением индексов (2.17) соответствующих элементов сетки и последующим переходом к значениям внутренних параметров на сетке. Этот алгоритм и будет далее использоваться для параллельной реализации процесса перебора вариаций внутренних параметров. Удобство его использования заключается в возможности разбить цикл перебора элементов одномерного МС на отдельные независимые друг от друга циклы. В каждом отдельном цикле выполняется инициализация указанной ему части МС путём перехода к наборам индексов соответствующих элементов сетки, вычисления координат их точек-представителей xс( Д2,...ДИ) и значения функции Fy(xc(k1,к2,...,кп)) (2.7). Каждый независимый цикл инициализации части МС представляет собой процесс, который выполняется независимо от процессов инициализации остальных частей МС. Для вычисления индексов элемента сетки, его точки-представителя (2.5) и состояния каждый процесс должен обладать следующей информацией: параметры сетки (компоненты n,B и Q структуры G (2.10)), модель исследуемой системы (1.1). Метод декомпозиции задачи по данным, проводимой на одномерном массиве, а не на многомерной сетке, является более гибким и менее сложным. Гибкость такого метода декомпозиции заключается в возможности разбивать массив на неравные по длине блоки, например, в заданной пропорции. Простота разбиения одномерного массива очевидна по сравнению с задачей разбиения многомерной сетки на заданное количество хотя бы равных по объёму частей. Примером геометрического разбиения (w-мерной сетки) является алгоритм, описанный в работах [3, 41]. Алгоритм такой декомпозиции заключается в разбиении сетки только по одному из параметров і = 1,2,...,п (в указанных работах предлагается по последнему параметру: / = п) на q блоков (количество квантов по /-му параметру). Эти блоки являются (п -1) -мерными сечениями сетки по /-му параметру. Каждому у -му параллельному процессу назначается сечение к j const сетки для инициализации состояний её элементов. Недостатками такой декомпозиции сетки является то, что максимальное количество параллельных процессов, которое можно задействовать, равно количеству q квантов /-го параметра, невозможность скорректировать вычислительную нагрузку точнее, чем на количество Qn элементов в сечении, в случае несимметричной (разнородной) вычислительной системы [22, 102, 117], большие блоки данных для обработки в случае сбоя в одном или нескольких параллельных процессах могут значительно снизить эффект ускорения от параллельных вычислений. Последние два замечания скорее относятся к проблеме невозможности декомпозиции данных для обработки на более мелкие по объёму блоки. К положительным сторонам описанного выше метода декомпозиции можно отнести тот факт, что механизм перебора элементов сетки осуществляется с помощью набора индексов (k1,k2,...,kn) с прямым преобразованием (2.14) этих индексов в индекс р = р(к1 ,к2,...,кп) элемента массива состояний, алгоритм которого имеет линейную сложность, как показано в разделе 2.1.4. Это позволит параллельным подзадачам выполняться быстрее, чем при переборе элементов МС с обратным преобразованием индексов. Распараллеливание процесса инициализации МС путём разбиения цикла перебора квантов только одного параметра применяется при параллельной реализации алгоритма 2.3 перебора элементов сетки с генерацией комбинаций индексов (&2 ,к3,...,кп) для всех сечений по к1 = 1,2,...,q1. Поскольку параллельные процедуры алгоритма перебора элементов сетки описываются алгоритмом 2.1 (перебор элементов МС с обратным преобразованием индексов сетки), то основной упор в описании параллельного построения ОР далее делается на методы декомпозиции данных и объединение результатов работы параллельных процедур. Параллельное выполнение перебора элементов МС S[R] = (S1,S2,...,SR) в К независимых процессах осуществляется указанием каждому /-му процессу диапазона значений индексов: (5.1) согласно которого в нём выполняется перебор всех значений Рі є {аІ ,at +1,...,bj }, і = 1,2,...,К, с последующим обратным преобразованием pj в набор индексов элемента сетки (к1,к2,...,кп)і по выражениям (2.17) и нахождением точки-представителя xс =(с11 ,с22 ,...,спп) по формуле (2.5). Состояние S[pi] элемента сетки с индексами (k1,k2,...,kn)i определяется значением функции Fy (xс). Как видно, в целом описанные выше действия в отдельном /-м процессе инициализации блока МС полностью повторяют алгоритм 2.1. Разбиение МС для параллельной обработки можно проводить как на одинаковые по количеству элементов массива блоки, так и на части, соотношение размеров которых находятся в заданной пропорции. Пропорциональное разбиение МС используется для балансировки нагрузок с целью уравнивания времени выполнения задачи каждым отдельным процессом при параллельной реализации алгоритма в случае несимметричной параллельной вычислительной системы [22, 10].
Для дальнейшего рассмотрения будем считать, что параллельная вычислительная система состоит из компонентов двух типов: вычислительного узла и управляющего узла. На компонентах этих типов выполняются параллельно соответственно вычислительные и главный координирующий процессы. Более подробное описание архитектуры параллельной вычислительной системы будет приведено позже, но на данном этапе рассмотрения достаточно интуитивного понимания разделения функций между этими типами компонентов и процессов. Стоит лишь добавить, что задачами декомпозиции и объединения результатов вычислений занимается управляющий процесс.
