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

На правах рукописи

Катуева Ярослава Владимировна

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

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

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

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

Работа выполнена в Институте автоматики и процессов управления Дальневосточного отделения Российской Академии Наук.

Научный руководитель: Заслуженный деятель науки РФ,

доктор технических наук, профессор Абрамов Олег Васильевич

Официальные оппоненты: доктор технических наук, профессор

Малышенко Юрий Вениаминович

кандидат технических наук Харитонов Дмитрий Иванович

Ведущая организация: Институт проблем управления РАН

им. В. А.Трапезникова

Защита состоится 2004 г. в часов на заседании дис-

сертационного совета Д.005.007.01 Института автоматики и процессов управления ДВО РАН по адресу:

690041, Владивосток, ул. Радио, 5

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

Автореферат разослан 2004 г.

И.о. ученого секретаря диссертационного совета Д.005.007.01 доктор технических наук

%

В.А. Бобков

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

Перспективной областью применения ЭВМ с массовым параллелизмом является решение задачи оптимального синтеза технических устройств и систем с учетом стохастических закономерностей вариаций их параметров и требуемой надежности. Эта задача, которую можно отнести к классу так называемых «Grand Challenges», требует колоссальных вычислительных ресурсов ЭВМ.

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

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

гис НАЦИОНАЛЬНА*

. ПАЦПиПЛМвПЛЯ .

БИБЛИОТЕКА I

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

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

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

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

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

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

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

1. Провести совместный анализ архитектуры суперкомпьютера массивно-параллельного класса на примере МВС-1000/16 и моделей параметрического синтеза (ПС). Разработать концепцию построения параллельных алгоритмов моделей ПС.

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

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

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

5. Разработать соответствующие программные средства и провести вычислительные эксперименты.

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

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

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

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

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

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

Практическая ценность и реализация результатов.

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

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

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

Представленный в работе цикл исследований был выполнен в соответствии с научно-исследовательскими планами ИАПУ ДВО РАН в рамках выполнения разделов следующих программ: Федеральная целевая программа «Интеграция науки и высшего образования России на 2002 - 2006 годы» (государственный контракт № И0103 от 01.07.2002 г.); программа фундаментальных научных исследований Президиума РАН, №17 на 20032004 гг. «Параллельные вычисления и многопроцессорные вычислительные системы»; программа фундаментальных исследований Отделения энергетики, механики, машиностроения и процессов управления РАН «Проблемы анализа и синтеза интегрированных технических и социальных систем управления».

Апробация работы. Результаты исследований докладывались и обсуждались на научных семинарах Института автоматики и процессов управления ДВО РАН в 1998-2004 гг.; на международных конференциях «Вычислительная механика и современные прикладные программные системы», Переславль-Залесский, 1999 г., Владимир, 2003 г.; на международных конференциях по проблемам управления, Москва, 2001, 2003 гг.; на международных конференциях «Параллельные вычисления и задачи управления», Москва, 2001, 2004 гг.; на международных научно-технических конференциях «Актуальные проблемы обеспечения надежности и качества приборов, устройств и систем», Пенза, 1997, 1998 гг.; на

международных симпозиумах «Надежность и качество», Пенза, 1999, 2000,

2001, 2002, 2004 гг.; на международных научно-технических конференциях «Системные проблемы надежности, математического моделирования и информационных технологий», Сочи, 1999, 2000 гг.; на международном симпозиуме по автоматизации проектирования систем управления США, Гавайи, 1999 г.; на Азиатских международных конференциях по проблемам управления («Asian Control Conference, ASCC»), Шанхай, 2000 г., Сингапур, 2002 г., Мельбурн, 2004 г.; на международной конференции по параллельным и распределенным методам вычислений («International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'2001»), Лас-Вегас, США, 2001 г.; на международной конференции «The Fourth International Conference. TOOLS FOR MATHEMATICAL MODELLLING». Санкт-Петербург, 2003 г.; на Дальневосточных математических школах-семинарах им. ак. Е.В. Золотова, Владивосток, 2001,

2002, 2003, 2004 гг.; на научной конференции «Молодежь и научно-технический прогресс», Владивосток, 1998 г.

Публикации по теме диссертации. По основным результатам, полученным в диссертационной работе, опубликовано 25 работ.

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы, включающего 117 наименований, и 3-х приложений. Работа содержит 148 страниц, 15 рисунков и 4 таблицы.

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

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

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

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

= argmaxР{Х(х„м,г)е D,,Vfе [О,Г]}, (1)

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

работоспособности; Т - заданное время эксплуатации устройства.

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

а,£у,(х)йЬ,, } = \.....т, (2)

где - вектор выходных параметров устройства, причем

- известный оператор, зависящий от топологии

исследуемого устройства.

В качестве количественного показателя надежности принимается вероятность:

Р№)е йу ,Уге [0,Г]) = Р(у(Х(0)€ ,Угб[0,Г]) =

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

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

Каждый шаг оптимизации требует проведения статистического анализа для получения оценки критерия оптимальности. При этом на основе метода статистических испытаний (Монте-Карло) многократно рассчитывается исследуемая система (устройство) для различных значений случайных параметров элементов. Если условия работоспособности выполняются, то реализация относится к числу хороших, в противном случае - плохих. Оценкой служит отношение числа хороших реализаций к общему числу реализаций случайных параметров элементов. Число расчетов Ы, равное числу реализаций случайного вектора параметров, определяется из условия обеспечения необходимой точности оценки критерия. Обычно для этого на каждом шаге поиска проводится полный расчет системы от нескольких сотен до тысячи раз. Заметим, что в процессе статистических ис-

пытаний и на каждом шаге поиска экстремума приходится проверять выполнение условий работоспособности (2).

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

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

Если реализация процесса обладает вышеописанным свойством, то

Р(Т)=Р{[а <У(ц)£Ьг\а£У(и)<Ъ п ...г\а<У(1к)<Ь]},

где а, Ъ - заданные границы допуска; ¡о, и,..., ¡к - точки локальных экстремумов реализации на интервале [О, Т] (критические сечения), /о=0, ¡к=Т.

Для монотонных случайных процессов изменения выходных параметров системы У(г) вероятность невыхода У(г) за пределы [а;Ь], в течение заданного времени определится следующим образом: Р(Т)=Р([а<У(0)<Ь п а<У(Т)<Ь]}.

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

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

Во второй главе на примере МВС-1000/16 проведен анализ вычислительных возможностей комплекса МВС-1000 как типичного представителя систем с массовым параллелизмом. Приведены характеристики вычислительной системы МВС-1000/16.

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

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

1) медленная скорость межпроцессорного обмена;

2) высокая латентность.

Сформулированы общие факторы, снижающие производительность параллельных алгоритмов:

1) разбалансировка нагрузки процессоров;

2) синхронизация процессоров;

3) коммуникации между процессорами;

4) параллельный ввод-вывод в общий для нескольких процессоров

файл;

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

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

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

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

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

Таблица 1

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

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

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

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

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

Задача построения области работоспособности в общем виде может быть сформулирована следующим образом. Пусть известна система, свойства (качество работы) которой зависят от значений параметров ее элементов х = (xi,...,x„), и заданы условия ее работоспособности (2). Необходимо определить такую область в пространстве внутренних параметров

хе R" , в каждой точке которой выполняются условия (2).

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

Для представления области работоспособности и ограничения пространства поиска задачи (1) предлагается двухэтапная параллельная процедура. Первый этап состоит в ограничении области работоспособности Dx в брусе допусков описанным параллелепипедом (брусом) Во и вычислении оценки объема области работоспособности с использованием метода Монте-Карло.

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

■*/min - xi — Xim&x >г" = 1»п •

Область в пространстве внутренних параметров, задаваемая соотношениями (3), представляет собой я-мерный ортогональный параллелепипед, или брус допусков Вj:

Bd ={xeÄ"Uimin<xi<A:imax,i = l,n}

с объемом

Описанным брусом для области работоспособности называют область в пространстве внутренних параметров, представляющую собой п -мерный ортогональный параллелепипед [2]

В0 = {хб Rn\afüXi<bf Vi=iü},

с объемом У0 = -а?), где а® = лип хх; Ь® = тах дг,-.

¿=1

ХбД.

ж=£>г

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

Параллельный алгоритм построения описанного параллелепипеда методом статистических испытаний позволяет добиться ускорения, близкого к линейному. Число испытаний N не зависит от размерности пространства параметров (по аналогии с кратностью интеграла), поэтому данный метод выгодно применять для построения описанных параллелепипедов большой размерности. Помимо этого, метод Монте-Карло позволяет получить существенную характеристику области работоспособности -оценку соотношения объемов описанного бруса Уд к объему области

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

На втором этапе процедуры построения области работоспособности производится ее зондирование в описанном брусе.

Параллельный метод зондирования области работоспособности заключается в том, что описанный брус Во разбивается рассечением плоскостями, параллельными его граням на 1=(11,...1„) частей по каждому координатному направлению и представляет собой объединение дискретного множества брусков-ячеек

Общее число брусков , шаг по каждому из параметров (длина

бруска по 1-му направлению) равен /г,=(/>(0-Д(0,)/?/, 1=1,П, в качестве представителя каждой ячейки назначается ее центр с координатами

+ /ггки, 1=1,и.

Если условия работоспособности выполняются в точке-представителе бруска-ячейки то предполагается, что они выпол-

няются для всех точек внутри данного бруска, брусок относим к числу хороших, если нет - плохих. Отметим также, что

НгаЛ^/Д = У0_/У„а,

где Л/^ - число хороших брусков, Я - число брусков при разбиении описанного бруса Во, А^ 1Л = УВ1 IV^ - соотношение оценки объема области работоспособности к объему описанного бруса, полученное методом Монте-Карло. Результаты разбиения описанного бруса на подбрусья (1, если брусок хороший и 0 в противном случае) хранятся в массиве А[Я] представления бруса В0. Бруску В^ ^ { соответствует элемент массива с номером

Процедура заполнения массива А[Я] представления бруса 50заклю-чается в последовательном переборе всех представителей брусков-ячеек, проверке для них выполнения условий работоспособности и формировании соответствующих элементов массива А[Я].

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

По формуле (3) находится номер элемента массива представления описанного бруса, если Л(р)=0, реализация относится к числу плохих, при А(р) = 1 - хороших.

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

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

В пятой главе рассматривается параллельная реализация метода дискретной оптимизации на множестве возможных вариаций типономина-лов параметров, представляющая собой аналог параллельного метода сканирования пространства поиска. Особенностью параметрической оптимизации в задаче (1) является невозможность использования методов оптимизации порядка выше нулевого. Кроме того, процедура нахождения значений целевой функции, основанная на методе статистических испытаний и методе критических сечений, имеет разную вычислительную трудоемкость, так как необходимость проведения вычисления выходных параметров системы и проверки условий работоспособности на каждом последующем временной сечении зависит от результатов аналогичной процедуры на предыдущем временном сечении. Поскольку номинальные значения параметров схемных элементов х„ должны принадлежать ряду стандартных значений, регламентированных техническими условиями или ГОСТами, иногда предпочтительнее искать оптимальный вектор номиналов параметров на дискретном множестве номиналов , соответствующем стандартным значениям и ограниченном описанным брусом допусков Во-Формирование множества номиналов О*' предлагается осуществить как предварительную процедуру, построив описанный брус в брусе допусков и найдя пересечение данного бруса с дискретным множеством ти-пономиналов параметров.

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

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

В Приложении 1 приведены основные характеристики эффективности параллельных алгоритмов.

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

В Приложение 3 включены документы по внедрению результатов работы.

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

В работе получены следующие основные научные результаты:

1. Проведен совместный анализ задачи параметрического синтеза с учетом стохастических отклонений характеристик параметров исследуемых систем и архитектуры массивно-параллельного суперкомпьютера на примере МВС-1000/16.

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

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

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

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

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

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

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

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

1. Абрамов О.В., Катуева Я.В. Система автоматизированного проектирования аналоговой радиоэлектронной аппаратуры // Информационные технологии в проектировании и производстве, №3, 1999. С. 52-55.

2. Абрамов О.В., Катуева Я.В. Использование технологии параллельных вычислений в задачах анализа и оптимизации. // Проблемы управления, №4, 2003. С. 11-15.

3. Катуева Я.В. Параллельные алгоритмы моделей параметрического синтеза для вычислительного комплекса МВС-1000/16.//Математическое моделирование, 2004, том 16, №6 с. 18-22.

4. Абрамов О.В., Катуева Я.В. Параллельные вычисления в задачах стохастической оптимизации РЭА с учетом требований надежности // Институт автоматики и процессов управления: Юбилейный сборник: К тридцатилетию ИАПУ ДВО РАН / Под общ. Ред. В.П.Мясникова. - Владивосток: ИАПУ ДВО РАН. 2001, с. 104-110.

5. Абрамов О.В., Катуева Я.В. Методы решения задач оптимизации с вероятностным критерием // Дальневосточная математическая школа-семинар имени академика Е.В. Золотова. - Владивосток, 1997. С.39-40

6. Катуева Я.В. Метод быстрой оценки серийнопригодности // 1-я Дальневосточная конференция студентов и аспирантов по математическому моделированию. - Владивосток, Дальнаука, 1997. С.27.

7. Абрамов О.В., Розенбаум А.Н., Климченко В.В., Катуева Я.В. Реализация минимаксных алгоритмов прогноза состояния технических объектов //Актуальные проблемы анализа и обеспечения надежности и качества приборов, устройств и систем / Сб. докл. международной научно-технической конференции. - Пенза: Изд-во Пензенского государственного технического университета, 1998. С. 123-124.

8. Абрамов О.В., Катуева Я.В. Принципы и задачи создания систем надежностного проектирования // Молодежь и научно-технический прогресс. Материалы научной конференции. - Владивосток, ДВГТУ, 1998. С. 152159.

9. Абрамов О.В., Катуева Я.В., Супоня А.А. Эффективные методы параметрической оптимизации по стохастическим критериям // Труды международной конференции по проблемам управления. - М.: ИПУ, 1999. Т. 2. С. 130-132.

10. Катуева Я.В. Способы уменьшения вычислительной трудоемкости решения оптимизационных задач в системе надежностного проектирования // Доклады Международного симпозиума "Надежность и качество. Инновационные технологии производству XXI века". - Пенза: ПГУ, 1999. С. 231-232.

11. O.V. Abramov, Y.V. Katueva, G.I. Lazarev, A.A. Suponya. Reliability Directed Computer Aided Design System // Proc. IEEE Int. Symposium on Computer Aided Control System Design, Hawai'i, USA, 1999, pp. 375-380.

12. Абрамов О.В., Катуева Я.В. Распределенные параллельные вычисления в задачах стохастической оптимизации. // Материалы Международной конференции "Системные проблемы качества, математического моделирования и информационных технологий". Часть 1. - Москва: НИИ "Автоэлектроника", 2000. С. 54-56.

13. Abramov O.V., Katueva Y.V., Syponya A.A., Lazarev G.I. Computer aided design system for optimal parametric synthesis. // Proceedings of the 3-rd Asian Control Conference (ASCC2000), Shanhai, 2000, pp.2047-2050.

14. Катуева Я.В. Параллельные вычисления в задачах параметрического синтеза РЭА по критериям надежности // Труды Международного симпозиума "Надежность и качество 2001". - Пенза: ПТУ, 2001. С. 118-120.

15. Катуева Я.В. Распределенные параллельные вычисления в задачах стохастической оптимизации РЭА с учетом требований надежности // Труды Международной конференции "Параллельные вычисления и задачи управления" (РАСО'2001.). - Москва, 2001. С.106-112.

16. О. Abramov, Y. Katueva, A. Suponya. Applications of Distributed and Parallel Proceeding Techniques for stochastic optimization problems // Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications. PDPTA'2001, Las Vegas, Nevada, USA, 2001 pp. 894-900.

17. Абрамов О.В., Катуева Я.В. Параллельные алгоритмы анализа и оптимизации параметрической надежности // Труды Международного симпозиума "Надежность и качество", - Пенза: ПТУ, 2002. С. 60-62.

18. Катуева Я.В. Характеристики производительности параллельного алгоритма метода Монте-Карло в задаче стохастической оптимизации РЭА // Дальневосточная математическая школа-семинар имени академика Е.В. Золотова. Тезисы докладов. - Владивосток: Дальнаука, 2002. С. 99-100.

19. О. Abramov, Y. Katueva, and A. Suponya. Parallel and Distributed Algorithms for Optimal Parametric Synthesis // Proceedings of the 4th Asian Control Conference, Singapore, 2002, pp. 1573-1577.

20. Катуева Я.В. Использование параллельных алгоритмов прямого моделирования Монте-Карло в моделях параметрического синтеза // Вторая международная конференция по проблемам управления. Избранные труды в двух томах. Том 2. - М.: Институт проблем управления, 2003. С. 167-173.

21. Абрамов О.В., Елисеева Е.Г., Катуева Я.В. Об использовании технологии параллельных и распределенных вычислений в задачах проектирования. // Труды Международного симпозиума "Надежность и качество", -Пенза: ПТУ, 2004, часть 1, С. 15-17.

22. Катуева Я.В. Параллельный алгоритм дискретной оптимизации в задаче параметрического синтеза // Дальневосточная математическая школа-

семинар имени академика Е.В. Золотова. - Владивосток: Издательство дальневосточного университета, 2004. С. 127.

23. О. Abramov, Y. Katueva. Application of Parallel Computing Techniques for Stochastic Optimization Problems// Proceedings of the 5 th Asian Control Conference, Melbourne, 2004, pp. 1573-1577.

24. Катуева Я.В. Параллельные алгоритмы метода многомерного зондирования в задаче оптимального параметрического синтеза //Труды Международной конференции "Параллельные вычисления и задачи управления" (РАСО'2004.). - Москва, 2004. С.202-212.

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

Личный вклад автора. Все результаты, составляющие основное содержание диссертационной работы, получены автором самостоятельно. В опубликованных в соавторстве работах автору принадлежат следующие научные и практические результаты: в работах [1, 2, 4, 5, 7-9, 11] - алгоритмы общей декомпозиции задачи параметрического синтеза; [12, 13, 16, 17]-централизованный параллельный метода статистических испытаний для оценки серийнопригодности; [19,23] параллельный метод статистического анализа для типовых процедур различной трудоемкости. В работах [2, 21, 23]- автором предложен и исследован параллельный метод дискретной оптимизации. В работах [2, 25] автором предложены параллельный метод статистических испытаний для построения описанного бруса и метод многомерного зондирования области работоспособности.

«221 О 4 в

КАТУЕВ А Ярослава Владимировна

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

Автореферат

Подписано к печати 26.10.04. Усл. п. л. 1.0. Уч-изд. л. 0.8. Формат 60x84/16. Тираж 100. Заказ 44.

Издано ИАПУ ДВО РАН. г. Владивосток, Радио, 5.

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

ВВЕДЕНИЕ

Глава 1. ПОСТАНОВКА ЗАДАЧИ ПАРАМЕТРИЧЕСКОГО СИНТЕЗА И АНАЛИЗ ИЗВЕСТНЫХ МЕТОДОВ ЕЕ РЕШЕНИЯ.

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

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

1.3. Методы решения задач параметрического синтеза по критериям надежности.

1.3.1. Методы оценки серийнопригодности.

1.3.2. Оценка точности метода статистического анализа.

1.3.3. Метод расчета вероятности безотказной работы.

1.4. Методы снижения трудоемкости задач параметрического синтеза.

1.5. Постановка и формулировка задач исследований.

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

Глава 2. АНАЛИЗ ВЫЧИСЛИТЕЛЬНЫХ ВОЗМОЖНОСТЕЙ

МВС-1000/16 КАК ПРЕДСТАВИТЕЛЯ КЛАССА МАССИВНО-ПАРАЛЛЕЛЬНЫХ

СУПЕРКОМПЬЮТЕРОВ.

2.1. Параллельные вычислительные системы и алгоритмы.

2.2. Вычислительные возможности системы МВС-1000/16.

2.2.1. Архитектура МВС-1000/16.

2.2.2. Характеристики вычислительных модулей.'.

2.2.3. Межпроцессорный обмен.

2.3. Концепция построения параллельных структур вычислительного алгоритма.

2.4. Характеристики производительности параллельного алгоритма.

2.5. Факторы, снижающие производительность алгоритма.

2.6. Концепция отображения алгоритмов параметрического синтеза на вычислительную систему МВС-1000/16 с учетом ее архитектуры.

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

Глава 3. ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ МЕТОДА СТАТИСТИЧЕСКОГО ОЦЕНИВАНИЯ ПАРАМЕТРИЧЕСКОЙ НАДЕЖНОСТИ.

3.1. Свойства и особенности метода Монте-Карло.

3.2. Задача моделирования случайных чисел с заданными законами распределения.

3.3. Централизованный параллельный метод Монте-Карло.

3.4. Распределенный параллельный метод Монте-Карло.

3.4.1. Требования к параллельным датчикам случайных чисел.

3.4.2. Параллельные распределенные алгоритмы оценки параметрической надежности /серийнопригодности.

3.5. Сравнительные характеристики централизованного и распределенного подходов.

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

Глава 4. ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ ПОСТРОЕНИЯ

ОБЛАСТИ РАБОТОСПОСОБНОСТИ

4.1. Задача построения области работоспособности.

4.2. Методы построения области работоспособности.

4.3. Посроение описанного бруса методом статистических испытаний.

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

4.5. Параллельный метод многомерного зондирования области работоспособности.

4.5.1.Представление разбиения описанного бруса.

4.5.2.Параллельная процедура представления описанного бруса.

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

Глава 5. ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ДИСКРЕТНОЙ

ОПТИМИЗАЦИИ В ЗАДАЧЕ ПАРАМЕТРИЧЕСКОГО

СИНТЕЗА.

5.1. Особенности алгоритмов оптимизации параметрической надежности.

5.2 Параллельный метод сканирования дискретного множества номиналов параметров.

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

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

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

Перспективной областью применения ЭВМ с массовым параллелизмом является решение задачи оптимального синтеза технических устройств и систем с учетом стохастических закономерностей вариаций их параметров и требуемой надежности. Эта задача, которую можно отнести к классу так называемых «Grand Challenges», требует колоссальных вычислительных ресурсов ЭВМ.

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

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

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

Высокая вычислительная трудоемкость оптимизации по стохастическим критериям заставляет принимать различные меры для получения результатов за приемлемое время. Классическими подходами уменьшения вычислительных затрат в задаче параметрического синтеза являются замена исходного стохастического критерия более «легким» детерминированным, уменьшение точности вычислений за счет сокращения числа итераций и другие. Применение таких приемов и методов позволяет в 3-5 раз уменьшить вычислительную трудоемкость задачи [1, 7, 8, 10-12, 18, 62, 84].

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

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

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

Решение задач, поставленных в диссертации, проводилось в соответствии с научно-исследовательскими планами ИАПУ ДВО РАН в рамках выполнения разделов следующих программ:

1. Федеральная целевая программа «Интеграция». Проекты № 728 А0026, И0103 на 1997-2001 гг.

2. Федеральная целевая программа «Интеграция науки и высшего образования России на 2002 - 2006 годы» (государственный контракт № И0103 от 01.07.2002 г.). Проект «Развитие фундаментальных и прикладных исследований на базе информационно-вычислительного комплекса науки и образования Приморского края».

3. Проект «Разработка эффективных методов принятия решений на основе параллельных вычислений в условиях неопределенности» в рамках темы «Разработка методов и средств повышения эффективности управления техническими системами» (2002-2004гг.).

4. Проект «Разработка алгоритмических и программных средств параметрической оптимизации по стохастическим критериям» в рамках темы «Разработка методов оценивания и управления состоянием технических систем» (1999-2001гг.).

5. Программа фундаментальных научных исследований Президиума РАН, №17 на 2003-2004 гг.; программа «Параллельные вычисления и многопроцессорные вычислительные системы». Проект «Параллельные вычисления в создании инструментальных и проблемно-ориентированных средств для решения вычислительно-сложных задач управления процессами формирования полей напряжения и деформации в материалах, оптимизации в условиях неопределенности, построения интеллектуальных систем и моделирования динамики океана и атмосферы с использованием спутниковой информации». 6. Программа фундаментальных исследований Отделения энергетики, механики, машиностроения и процессов управления РАН №16 на 20032004 гг. «Проблемы анализа и синтеза интегрированных технических и социальных систем управления». Проект «Разработка методов и алгоритмов параметрического синтеза стохастических систем».

Цель работы

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

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

1. Провести совместный анализ архитектуры суперкомпьютера массивно-параллельного класса на примере МВС-1000/16 и задач параметрического синтеза (ПС). Разработать концепцию построения параллельных алгоритмов параметрического синтеза.

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

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

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

5. Разработать соответствующие программные средства и провести вычислительные эксперименты.

Основные методы исследований

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

Научная новизна работы и положения, выносимые на защиту

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

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

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

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

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

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

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

Апробация работы

Основные результаты, полученные в диссертационной работе, докладывались и обсуждались:

1. На научных семинарах Института автоматики и процессов управления ДВО РАН в 1998-2004 гг.

2. На международных конференциях «Вычислительная механика и современные прикладные программные системы», Переславль-Залесский, 1999 г., Владимир, 2003 г.

3. На международных конференциях по проблемам управления, Москва, 2001, 2003 гг.

4. На международных конференциях «Параллельные вычисления и задачи управления», Москва, 2001, 2004 гг.

5. На международных научно-технических конференциях «Актуальные проблемы обеспечения надежности и качества приборов, устройств и систем», Пенза, 1997, 1998 гг.

6. На международных симпозиумах «Надежность и качество», Пенза, 1999, 2000, 2001, 2002, 2004 гг.

7. На международных научно-технических конференциях «Системные проблемы надежности, математического моделирования и информационных технологий». Сочи, 1999, 2000 гг.

8. На международном симпозиуме по автоматизации проектирования систем управления. США, Гавайи, 1999 г.

9. На Азиатских международных конференциях по проблемам управления («Asian Control Conference, ASCC»), Шанхай, 2000, Сингапур, 2002, Мельбурн, 2004.

Ю.На международной конференции по параллельным и распределенным методам вычислений («International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'2001»), Лас-Вегас, США, 2001.

11 .На международной конференции «The Fourth International Conference. TOOLS FOR MATHEMATICAL MODELLLING». Санкт-Петербург, 2003.

12.Ha Дальневосточных математических школах-семинарах им. ак. Е.В. Золотова, Владивосток, 2001, 2002, 2003, 2004 гг.

13.На научной конференции «Молодежь и научно-технический прогресс», Владивосток, 1998 г.

Публикации

По материалам диссертации опубликовано 30 работ.

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ.

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

1. Проведен совместный анализ задачи параметрического синтеза с учетом стохастических отклонений характеристик параметров исследуемых систем и архитектуры массивно-параллельного суперкомпьютера на примере МВС-1000/16.

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

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

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

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

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

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

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

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

2. Абрамов О.В. Расчет параметрической надежности технических устройств при нелинейных изменениях параметров // Управление качеством функционирования технических систем. Владивосток: ДВНЦ АН СССР, 1980. С. 30-35.

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

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

5. Абрамов О.В., Катуева Я.В. Использование технологии параллельных вычислений в задачах анализа и оптимизации // Проблемы управления, №4, 2003. С. 11-15.

6. Абрамов О.В., Катуева Я.В. Методы решения задач оптимизации с вероятностным критерием // Дальневосточная математическая школа-семинар имени академика Е.В. Золотова. Владивосток: Даль-наука, 1997. С.39-40.

7. Абрамов О.В., Катуева Я.В. Принципы и задачи создания систем надежностного проектирования // Молодежь и научно-технический прогресс. Материалы научной конференции. Владивосток: ДВГТУ, 1998. С.152-159.

8. Абрамов О.В., Катуева Я.В. Распределенные параллельные вычисления в задачах стохастической оптимизации // Системные проблемыf

9. Абрамов О.В., Катуева Я.В. Система автоматизированного проектирования аналоговой радиоэлектронной аппаратуры // Информационные технологии в проектировании и производстве, №3, 1999. С. 5255.

10. Абрамов О.В., Катуева Я.В., Супоня А.А. Эффективные методы параметрической оптимизации по стохастическим критериям // Труды международной конференции по проблемам управления. М.: ИЛУ, 1999. Т. 2. С. 130-132.

11. Абрамов О.В., Супоня А.А. Учет нелинейных изменений параметров при проектировании технических устройств. // АиТ, №2, 1977. С. 144-152.

12. Автоматизация схемотехнического проектирования. Учеб. пособие для вузов / Ильин В.Н., Фролкин В.Т., Бутко А.И. и др. Под ред. В.Н. Ильина. М.: Радио и связь, 1987. - 368 с.

13. Амелина Н.И., Жак С.В. Применение адаптивного случайного поиска в оптимальном проектировании // Вопросы кибернетики, 1978. Вып.45. С. 73-76.

14. Анисимов Б.В., Белов Б.И., Норенков И.П. Машинный расчет элементов ЭВМ. М.: Высшая школа, 1976. - 336 с.

15. Анненков В.А., Нурминский Е.А., Смирнов С.В. Исследование производительности ЭВМ с иерархической организацией памяти на подпрограммах библиотеки BLAS. // Информатика и системы управления, № 2, 2001. С. 3-12.

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

17. Астафьев А.В. Окружающая среда и надежность радиоэлектронной аппаратуры. М.: Энергия, 1965. - 360 с.

18. Барский А. Б. Параллельные технологии решения оптимизационных задач. М.: Машиностроение, 2001. - 25с.

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

20. Баранов Г.Г. О выборе допусков, обеспечивающих заданную точность механизма и наименьшую стоимость его изготовления. // Труды Института машиноведения. М.: АН СССР, 1957. вып.11. Семинар по точности в машиностроении и приборостроении, С. 3-17.

21. Баталов Б.В. и др. Основы математического моделирования больших интегральных схем на ЭВМ / Б.В. Баталов, Ю.Б. Егоров, С.Г. Русаков. М.: Радио и связь, 1982. - 167 с.

22. Батищев Д.И., Львович Я.Е., Фролов В.Н. Оптимизация в САПР: Учеб. для вузов по направлению «Информатика и вычисл. техника» и спец. «Системы автоматизированного проектирования». Воронеж: Изд-во Воронежского ун-та, 1997. - 416 с.

23. Бахвалов Н.С. Численные методы. М.: Наука, 1973. - 632 с.

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

25. Белов Б.И. Норенков И.П. Расчет электронных схем на ЦВМ. М.: Машиностроение, 1971. - 143 с.

26. Беляков Ю.Н. и др. Методы статистических расчетов микросхем на ЭВМ / Ю.Н. Беляков, Ф.А. Курмаев, Б.В. Баталов. М.: Радио и связь, 1985.-232 с.

27. Бернацкий Ф.И., Гладков В.И., Деркач Г.К. и др. Автоматизированное управление процессами химической технологии. М.: Наука, 1981.-216с.

28. Бородачев Н.А. Обоснование методики расчета допусков и ошибок кинематических цепей. 4.1, M.-JL: АН СССР, 1942. - 86 с.

29. Бородачев Н.А. Обоснование методики расчета допусков и ошибок кинематических цепей. 4.2, M.-JL: АН СССР, 1946. - 225 с.

30. Бородачев Н.А. Основные вопросы теории точности производства. -M.-JL: АН СССР, 1950. 416 с.

31. Брейтон Р.К., Хечтел Г.Д., Санджованни-Винчентелли A.J1. Обзор методов оптимального проектирования интегральных схем // ТИИЭР. № 10, т. 69, 1981. С. 180-215.

32. Бруевич Н.Г. Надежность, долговечность, точность. // Надежность сложных технических систем. М.: Советское Радио, 1966. С. 7-26.

33. Бусленко Н.П., Шрейдер Ю.А. Метод статистических испытаний. -М.: Наука, 1961.-227 с.

34. Быховский M.JI. Основы динамической точности электрических и механических цепей. М.: АН СССР, 1958. - 157 с.

35. Валях Е. Последовательно-параллельные вычисления. / Пер. англ. М.: Мир, 1985. - 456 с.

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

37. Вентцель Е.С., Овчаров JI.A. Теория вероятности и ее инженерные приложения. М.: Наука, 1988. - 480 с.

38. Воеводин В.В. Математические модели и методы в параллельных процессах. М.: Наука, 1986. - 296 с.

39. Воеводин В.В. Параллельные структуры алгоритмов и программ. -М.: ОВМ, 1987. 144 с.

40. Воеводин В.В. Особенности параллельных вычислений. // Математическое моделирование. Современные проблемы математической физики и вычислительной математики. М.: Наука, 1989. С. 63-71.

41. Воеводин В.В. Лекция об архитектуре массивно-параллельных компьютеров на примере CRAY T3D. // Computer World, N22, 1999. С. 40-41.

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

43. Вульф М. Оптимизация программного обеспечения для суперЭВМ. // СуперЭВМ. Аппаратная и программная реализация. Под ред. С. Фернбаха: Пер. с англ. М.: Радио и связь, 1991. С. 266290.

44. Голенко Д.И. Моделирование и статистический анализ псевдослучайных чисел на ЭВМ. М.: Наука, 1965. - 228 с.

45. Головкин Б.А. Вычислительные системы с большим числом процессоров. М.: Радио и связь, 1995.

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

47. ГОСТ 27.002-83. Надежность в технике. Термины и определения.

48. Гусев А.В., Жуков В.Т., Забродин и др. Реализация вычислительных алгоритмов для некоторых классов задач на многопроцессорных системах. Препринт №83, М.: ИПМ им. М.В. Келдыша АН СССР, 1992.

49. Дружинин Г.В. Надежность систем автоматики. М.: Энергия, 1966.-528 с.

50. Джордан T.JI. Руководство по параллельным вычислениям и опыт программирования на ЭВМ CRAY-1. // Параллельные вычисления. Под ред. Г. Родрига. М.: Наука, 1986. С. 11-55.

51. Ермаков С.М., Михайлов Г.А. Статистическое моделирование. 2-е изд., доп. М.: Наука, 1982. - 296 с.

52. В. В. Захаров, Г. А. Лукьянов. Параллельные алгоритмы прямого моделирования Монте-Карло в молекулярной газовой динамике, http://www.csa.ru/mclab/parallel/guide/guide.html

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

54. Иванов А.Г. Параллельный алгоритм прямого поиска минимума функции многих переменных. // Алгоритмы и программные средства параллельных вычислений. Вып. 2, Екатеринбург, 1998. С. 110-122.

55. Иванов С.Р., Мулячик С.Г., Норенков И.П. Расчет оптимальных значений параметров электронных схем // Радиотехника, № 22, т. 26, 1971. С. 79-83.

56. Ильин В.Н. Машинное проектирование электронных схем. М.: Энергия, 1972. - 280 с.

57. Иыуду К.А. Оптимизация устройств автоматики по критерию надежности. М.: Энергия, 1966. - 194 с.

58. Катуев К.С. Эффективный алгоритм оценки серийнопригодности электронных схем // Автоматизация проектирования и параметрический синтез технических систем. Владивосток: ДВО АН СССР, 1990. С. 22-27.

59. Катуева Я.В. Метод быстрой оценки серийнопригодности // 1-я Дальневосточная конференция студентов и аспирантов по математическому моделированию. Владивосток, Дальнаука, 1997. С.27.

60. Катуева Я.В. Параллельный алгоритм дискретной оптимизации в задаче параметрического синтеза // Дальневосточная математическая школа-семинар имени академика Е.В. Золотова. Владивосток: Издательство дальневосточного университета, 2004. С. 127.

61. Катуева Я.В. Параллельные алгоритмы метода многомерного зондирования в задаче оптимального параметрического синтеза //Труды Международной конференции "Параллельные вычисления и задачи управления" (РАСО'2004.). Москва, 2004. С.202-212.

62. Катуева Я.В. Параллельные алгоритмы моделей параметрического синтеза для вычислительного комплекса МВС-1000/16 //Математическое моделирование, 2004, том 16, №6 с. 18-22.

63. Катуева Я.В. Параллельные вычисления в задачах параметрического синтеза РЭА по критериям надежности // Труды Между народного симпозиума "Надежность и качество 2001", Пенза: ПГУ, 2001. С. 118-120.

64. Катуева Я.В. Распределенные параллельные вычисления в задачах стохастической оптимизации РЭА с учетом требований надежности // Труды Международной конференции "Параллельные вычисления и задачи управления" (РАСО'2001.). Москва, 2001. С.106-112.

65. Климченко В.В. Модификация метода критических сечений для расчета надежности устройств с немонотонно изменяющимисяф параметрами // Анализ технических систем с учетом параметрических возмущений. Владивосток: ДВО РАН, 1987. С. 106-111.

66. Кнут Д. Искусство программирования для ЭВМ. Т.2. Получисленные алгоритмы. М.: Мир. 1977. - 724 с.

67. Корнеев В.В. Параллельные вычислительные системы. М.: 1999-320с.

68. Корнеев В.В. Параллельное программирование в MPI. Новоси-^ бирск: Изд-во СО РАН, 2000. - 213 с.

69. Кочубиевский И.Д. К расчету автоматических систем при ограниченных сведениях о случайных воздействиях. // АиТ, t.XXVI, № 1, 1965. С. 107-116.

70. Кочубиевский И.Д. К рациональному выбору точности систем автоматического управления. // Изв. АН СССР, Сер. ОТН энергетика и автоматика, №5, 1962. С. 118-122.

71. Кочубиевский И.Д. Эффективность систем автоматического управления. // Изв. АН СССР, Сер. Техническая кибернетика, №3, 1964. С. 134-140.

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

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

74. Михайлов А.В. Эксплуатационные допуски и надежность в радиоэлектронной аппаратуре. М.: Сов. Радио, 1970. - 215 с.

75. Михайлов Г.А., Марченко М.А. Параллельная реализация статистического моделирования и генераторов случайных чисел. Новосибирск, Препринт / РАН. СО ИВМиМГ, 2001. - 21 с.

76. Норенков И.П. Введение в автоматизированное проектирование технических устройств и систем. М.: Высшая школа, 1986. - 304 с.

77. Норенков И.П., Иванов С.Р., Мулярчик С.Г. Оптимизация параметров электронных схем по критерию запаса работоспособности. Вест. БГУ им. В.И. Ленина. Сер.1. Математика, Физика, Механика. №3, 1970. С. 65-69.

78. Норенков И.П., Маничев В.Б. Системы автоматизированного проектирования электронной и вычислительной аппаратуры. М.: Высшая школа, 1983.-272 с.

79. Норенков И.П., Мулярчик С.Г., Иванов С.Р. Экстремальные задачи при схемотехническом проектировании в электронике. Минск: БГУим. В.И. Ленина, 1976. 240 с.

80. Норенков И.П. Разработка систем автоматизированного проектирования. М.: Изд-во МГТУ, 1994. - 203 с.

81. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. / Пер. с англ. М.: Мир, 1991. - 367 с.

82. Пампуро В.И., Мартынов Г.К. Прогнозирование стабильности и оценка серийнопригодности радиоэлектронной аппаратуры. М.: Знание, 1976. - 136 с.

83. Полляк Ю.Г. Вероятностное моделирование на ЭВМ. М.:, Сов. Радио, 1971.-400 с.

84. Половко A.M. Основы теории надежности. М.: Наука, 1964. -466с.

85. Проников А.С. Надежность машин. М.: Машиностроение, 1978. -592с.

86. Проников А.С. Прогнозирование и расчет надежности машин. // Методы количественной оценки и обеспечения надежности: Материалы XV конференции ЕОКК. М.: Изд-во Стандартов, 1972. С. 27-42.

87. Растригин Л.А. Статистические методы поиска. М.: Наука, 1968. -376с.

88. Системы параллельной обработки. / Пер. с англ. Под ред. Д. Ивенса. М.: Мир, 1985.-416 с.

89. Смагин Ю.Е. Матричные испытания радиоэлектронных устройств с помощью ЭВМ. М.: Энергия, 1979. - 152 с.

90. Смагин Ю.Е. Оптимизация элементов устройств передачи информации по результатам матричных испытаний. // Управление, передача, преобразование и отображение информации. Рязань: вып.2. 1975. С. 30-37.

91. Соболь И.М. Численные методы Монте-Карло. М.: Наука, 1973. -311с.

92. Соболь И.М. Об одном подходе к вычислению многомерных интегралов // Вопросы вычислительной и прикладной математики. Ташкент: № 38, 1970. С. 100-111.

93. Туркельтауб P.M. Методы исследования точности и надежности схем аппаратуры. М.: Энергия, 1966. - 160 с.

94. Фомин А.В., Борисов В.Ф., Чермошенский В.В. Допуски в радиоэлектронной аппаратуре. М.: Сов. Радио, 1973. - 128 с.

95. Фомин А.В. и др. Надежность полупроводниковых радиоустройств летательных аппаратов. М.: Машиностроение, 1968. - 267 с.

96. Элементы параллельного программирования // Васильковский В.А., Котов В.Е., Марчук А.Г., Миренков Н.Н. Под ред. В.Е.Котова. М.: Радио и связь, 1983. - 240 с.

97. Эрцеговак М.Д., Ланг Т. Общие принципы организации высокопроизводительных ЭВМ и высокоскоростных вычислений. // СуперЭВМ: Аппаратная и программная реализация. Под ред. С. Фернбаха. М.: Радио и связь, 1991. С. 11-37.

98. Эрцеговак М.Д., Ланг Т. Векторная обработка. // СуперЭВМ: Аппаратная и программная реализация. Под ред. С. Фернбаха. М.: Радио и связь, 1991. С. 40-71.

99. О. Abramov, Y. Katueva. Application of Parallel Computing Techniquesth •for Stochastic Optimization Problems// Proceedings of the 5 Asian Control Conference, Melbourne, 2004, pp. 1573-1577.

100. О. Abramov, Y. Katueva, and A. Suponya. Parallel and Distributed Algorithms for Optimal Parametric Synthesis // Proceedings of the 4th Asian Control Conference, Singapore, 2002, pp. 1573-1577.

101. Coddington P. Random number generators for parallel computers. NHSE Review, Volume, Second Issue, 1996.

102. Chuanyi D., Haskin E. Monte Carlo Methods in Parallel Computing. Copyright by UNM/ARC, November 1995.

103. Flynn M. Some computer organizations and their effectiveness // IEEE Trans. Сотр. C-21, №9,1972. P. 948-960.

104. Foster Ian. Designing and Building Parallel Programs. Addison-Wesley, 1995.

105. INTEL Random number generator. Intel Corporation, 1999.

106. Marsaglia G. Random numbers fall mainly in the planes // Proc. Nat. Acad. Sci. USA, Vol.61, 1968.P. 23-25.

107. Marsaglia G. A current view of random number generators. // Computing Science and Statistics: Proseeding of the XVIth Symposium on the Interface, 1985. P. 3-10.

108. Mascagni M., Srinivasan A. Algorithm 806. SPRNG: A scalable library for pseudorandom number generation Source ACM Transactions on Mathematical Software (TOMS). Volume 26, Issue 3. September 2000. P. 436-461.

109. Wagner W. Monte Carlo evaluation of functional of solutions of stochastic differential equations. Variance reduction. // Stochastic analysis and applications, Vol.6, №4, 1988. P. 447-468.