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

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

1

Найрат Самер

ПОВЫШЕНИЕ ЭФФЕКТВНОСТИ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ САПР НА ОСНОВЕ ТЕХНОЛОГИИ РАЗРЕЖЕННЫХ МАТРИЦ

Специальность: 05. 13. 12 —Системы автоматизации проектирования

(промышленность)

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

Санкт-Петербург- 2006

Работа выполнена в Санкт-Петербургском государственном электротехническом университете "ЛЭТИ" им. В.И.Ульянова (Ленина)

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

доктор технических наук, профессор Анисимов В Л.

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

доктор технических наук, профессор Лузин С.Ю.

кандидат технических наук Фомичев П.Б.

Ведущая организация — Санкт-Петербургский государственный

университет информационных технологий, механики и оптики

_го

Защита диссертации состоится " С.Ь " 2006 г. в часов

на заседании диссертационного совета Д2 £¿>238.02^ Санкт-Петербургского государственного электротехнического университета им. В.И.Ульянова (Ленина) по адресу: 197376, Санкт-Петербург, ул. Проф. Попова, 5.

С диссертацией можно ознакомиться в библиотеке университета.

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

Ученый секретарь диссертационного совета Юрков Ю.В.

Общая характеристика работы Актуальность проблемы.

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

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

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

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

Целью диссертационной работы является исследование вопросов повышения эффективности программного обеспечения САПР при решении

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

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

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

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

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

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

Достоверность научных результатов

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

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

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

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

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

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

5. Разработана методика моделирования систем во временной области на основе компактной обработки разреженных матриц в строчно-столбцовом фиксированном формате.

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

1. Концепция двухэтапного формирования математического описания систем на основе строчно-столбцрвого фиксированного формата.

2. Алгоритмы и блок-схемы процесса формирования структурного портрета моделируемой системы.

3. Методика формирования частных матриц компонентов моделируемой системы на основе (прочно-столбцового фиксированного формата.

4. Виртуальная обработка компактных матриц с целью выполнения ИЛ-факторизации и решения систем уравнений.

Практическая денность.

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

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

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

3. Разработана и реализована методика построения систем автоматизации проектирования на основе компактного представления разреженных матриц в строчно-сшлбцовом фиксированном формате.

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

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

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

Основные теоретические результаты диссертационной работы докладывались на конференциях:

1. Международная конференция по мягким вычислениям и измерениям, 8СМ*2005. Санкт - Петербургский государственный электротехнический университет «ЛЭТИ».

2. Международная конференция "Современные технологии обучения: международный опыт и российские традиции", Санкт-Петербург, 2005 .

3. Конференция профессорско-преподавательского состава СПбГЭТУ, Санкт-Петербургский государственный электротехнический университет 2005г.

4. Конференция профессорско-преподавательского состава СПб! ЭТУ, Санкт-Петербургский Государственный , электротехнический университет 2006г.

Публикации

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

Структура и объем диссертации

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

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

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

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

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

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

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

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

типа char. В работе устанавливается методика формирования индексной матрицы С на основе функций для типовых компонентов систем. Устанавливается методика построения на основе индексной матрицы координатных массивов WJI, ERC, SI. Показывается, что на основе построенных массивов оказывается возможным провести формирование численных массивов WD, WU, WL. При этом индексная матрица в начале ' этого этапа может быть удалена в целях экономии памяти.

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

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

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

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

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

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

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

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

В третьей главе диссертационной работы рассматривается вопрос реализации численного этапа компактной обработки разреженных матриц в строчно-столбцовом фиксированном формате. Исходными данными для численного этапа формирования компактного описания являются целочисленные массивы, описывающие включение компонентов в моделируемой системе, н вещественные массивы, содержащие значения параметров компонентов. Поскольку структурная матрица на этапе численного формирования удаляется из памяти, то для отображения описания в компактных массивах WD, WU, WL, SZ необходимо использовать координатные массивы WJI, ERC, SI.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основные результаты работы.

1. Разработана методика построения структурного портрета и реализованы функции формирования координатного описания для компактного представления математического описания систем в строчно-столбцовом фиксированном формате,

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

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

массивов, отображающих полное математическое описание моделируемой системы.

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

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

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

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

Список опубликованных работ по теме анссеогацин

1. Найрат С амер. Моделирование систем на основе методов диакоптики //Изв. СПбГЭТУ «ЛЭТИ». Сер. Информатика, управление и компьютерные технологаи.-2005.-вып. -с.44-48

2. Найрат Самер. Методы повышения эффективности программного обеспечения систем моделирования. Сборник докладов //Международная конференция по мягким вычислениям и измерениям 5СМ '2005.-с.217-219

3. Найрат Самер. Сравнительная оценка и методика изучения процессов моделирования больших систем на основе диакоптического подхода. Материалы XI Международной конференции «Современные технологии обучения: международный опыт и российские традиции», Санкт-Петербург, 2005г. -с. 112-113.

Подписано в печать 16.11.06. Формат 60*84 1/16. Бумага офсетная. Печать офсетная. Печ. л. 1,0. Тираж 100 экз. Заказ 123.

Отпечатано с готового оригинал-макета в типографии Издательства СПбГЭТУ "ЛЭТИ"

Издательство СПбГЭТУ "ЛЭТИ" 197376, С.-Петербург, ул. Проф. Попова, 5

Введение.

Глава 1. Методы повышения эффективности программного обеспечения систем автоматизации схемотехнического проектирования

1.1. Математическое описание систем.

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

1.3. Обобщенная блок-схема алгоритма реализации строчно-столбцового фиксированного формата.

Глава 2. Символьный этап метода строчно-столбцового фиксированного формата

2.1. Символьный этап формирования частных матриц типовых компонентов.

2.2. Символьный этап Ш-факторизации и оптимального упорядочивания.

2.3. Формирование координатного описания.

Глава 3. Численный этап компактной обработки разреженных матриц

3.1. Численный этап формирования компактного описания в строчно-столбцовом фиксированном формате.

3.2. Численный этап компактной формы Ш-факторизации.

3.3. Численный этап расчета переменных с учетом преобразования базиса.

Глава 4. Реализации методов компактной обработки на основе строчно-столбцового фиксированного формата.

4.1. Компактные методы моделирования линейных систем в частотной области

4.1.1. Общие принципы моделирования систем в частотной области.

4.1.2. Формирование компактной формы математического описания систем на основе комплексных частных матриц.

4.1.3. Моделирование систем в частотной области на основе частотно-независимых вещественных матриц.

4.2. Расчет стационарного режима нелинейных систем на основе компактной обработки разреженных матриц.

4.2.1. Математическое описание нелинейных систем.

4.2.2. Схемотехническая интерпретация методов решения уравнений нелинейных систем.

4.2.3. Моделирование стационарного режима на основе компактной обработки разреженных матриц.

4.3. Компактные методы моделирования систем во временной области

4.3.1. Математическое описание систем во временной области.

4.3.2. Дискретные модели компонентов.

4.3.3. Алгоритм и блок-схема моделирования во временной области на основе дискретных моделей компонентов.

4.4. Моделирование систем на основе методов диакоптики.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основные теоретические результаты диссертационной работы докладывались на конференциях:

1. Международная конференция по мягким вычислениям и измерениям, 8СМ'2005. Санкт - Петербургский государственный электротехнический университет «ЛЭТИ».

2. Международная конференция "Современные технологии обучения: международный опыт и российские традиции", Санкт-Петербург, 2005 .

3. Конференция профессорско-преподавательского состава СПбГЭТУ, Санкт-Петербургский государственный электротехнический университет 2005г.

4. Конференция профессорско-преподавательского состава СПбГЭТУ, Санкт-Петербургский Государственный электротехнический университет 2006г.

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

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

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

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

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

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

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

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

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

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

114

Заключение

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

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

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

1. Анисимов В.И. Топологический расчет электронных схем. М.:Энергия, 1977.

2. Анисимов В.И. Обобщенные уравнения электронных схем. М.: Радиотехника и электроника, 1967.

3. Анисимов В. И., Дмитревич Г. Д., Ежов С. Н., под ред. В. И. Анисимова. Автоматизация схемотехнического проектирования на мини-ЭВМ. JL: Изд-во Ленингр. Ун-та, 1983. -199с.

4. Анисимов В. И., Дмитревич Г. Д., Никитин А. В. Иерархические методы моделирования сложных объектов САПР.

5. Анисимов В. И., Скобельцын К.Б., Никитин А. В. Комплекс диалоговых пакетов моделирования аналоговых и цифровых электронных схем на IBM/PC. -. Автоматизированное проектирование в радиоэлектронике и приборостроении. ЛЭТИ, 1991.

6. Анисимов В. И., Дмитревич Г.Д., Скобельцын К.Б. Диалоговые системы схемотехнического проектирования. М.: Радио и связь, 1988.

7. Анисимов В.И., Никитин А.В, Скобельцын К.Б. Программное обеспечение САПР для сетей ЭВМ. СПб.: ЛЭТИ, 1988.

8. Арайс Е., Дмитриев В. М. Моделирование неоднородных цепей и систем на ЭВМ. М.: Радио и Связь, 1982. - 157с.

9. Арайс Е., Арайс Л. Автоматизация расчета сложных технических устройств. М.: Рига, 1987.- 79с.

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

11. Вавилов А. А., Имаев Д. X., Плескунин В. И., Фомин Б. Ф. Имитационное моделирование производственных систем. Киев: Техника, 1983. - 415с.

12. М.Влах И., Сингхал К. Машинные методы анализа и проектирования электронных схем. М.: Радио и связь, 1988. -560 с.

13. Глориозова E.JL, Ссорин В.Г., Сыпгук П.П. Введение в автоматизацию схемотехнического проектирования. М.: Советское радио, 1976.

14. Гарнаев А. Ю. Самоучитель Visual Studio.Net 2003. СПб.: БХВ -Петербург, 2003. - 688с.

15. Гамма Э., Хелм Р. Приемы объектно-ориентированного проектирования. — СПб.: Питер, 2001.

16. Грегори К. Использование Visual С++ 6. Специальное издание. СПб.: Вильяме, 1999.

17. Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений. -М.:Мир, 1984.

18. Райс Дж. Матричные вычисления и математическое обеспечение. М.: Мир, 1984.-264с.

19. Джеймс О., Венер Р. Итерационные методы решения нелинейных систем уравнений. М.: Мир, 1975.

20. Ильин В.Н. Основы автоматизации схемотехнического проектирования. -М.: Энергия, 1979.

21. Икрамов X. Д. Численное решение матричных уравнений. М.: Наука. -190с.

22. Ильинский Н. Ф., Цацеинкин В. К. Приложение теории графов к задачам электромеханики. М.: Энергия, 1968. - 199с.

23. Касаткин А.И. Профессиональное программирование на языке С.

24. Калиткин Н. Н. Численные методы. М.: Наука, 1978. - 512с.

25. Кнут Д. Искусство программирования для ЭВМ. — М.: Мир, 1976.

26. Кознов Д. В. Проблемы разработки компонентного программного

27. Кузьмин П. К., Манигев В. Б. Автоматизация функционального проектирования. М.: Высшая школа, 1986.

28. Керниган Б., Ритчи Д. Язык программирования С. — М.: Финансы и статистика, 1992.

29. Кениг Г., Блекуэлл В. Теория электромеханических систем. М.: Энергия, 1965.

30. Лейнекер Р. Энциклопедия Visual С++. СПб.: Питер, 1999. -1152с.

31. Марк J1. Visual С++6. М.: Лаборатория базовых знаний, 1999. - 720с.

32. Мешков А., Тихомиров Ю. Visual С++ и MFC. Программирование для Window NT и Window 95. СПб.:ВНУ-Санкт-Петербург. - 415с.

33. Майкл Дж. Visual С++6 полное руководство. Киев: BHV, 1999. - 543с.

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

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

36. Норенков И. П., Манигев В. Б. Основы теории и проектирования САПР. -М.: Высшая школа, 1990. -335с.

37. Новгородцев А.Б. 30 лекций по теории электрических цепей: учебник для вузов. СПб.: Политехника, 1995. - 519с.43.0ре О. Графы и их применение. М.: Мир, 1965.

38. Писсанецкий С. Технология разреженных матриц. М.: Мир, 1988.

39. Петренко А. И. Основы автоматизации проектирования. Киев: Техника, 1982.-295с.

40. Реза Ф., Сили С. Современный анализ электрических цепей. М.: Энергия, 1964.

41. Рихтер Дж. Windows для профессионалов: создание эффективных Win32 приложений.— 4-е изд. — СПб.: Питер, 2001 . — 752с.

42. Роббинс Дж. Отладка Windows-приложений. — М.:ДМК, 2001. —448 с.

43. Саймон P. Microsoft Windows 2000 API. Энциклопедия программиста.— СПб.: ДиаСофт, 2002. — 1088 с.

44. Сигорский В.П., Петренко А.И. Алгоритмы анализа электронных схем. -М.: Советское радио, 1976.

45. Сигорский В.П. Математический Аппарат инженера. Киев: Техника, 1976.

46. Советов Б.Я.,. Яковлев С. А. Моделирование систем. М.: Высшая школа, 1985.-271с.

47. Сольницев Р. И. Вычислительные машины в судовой гироскопии. JL: Судостроение, 1977. - 312с.

48. Страуструп Б. Язык программирования С++. 3-е изд. СПб.: М.: Невский Диалект. - «Издательство БИНОМ», 1995. - 991с.

49. Слипченко В.Г., Елизаренко Г.Н. Методы диакоптики в электронике.- Киев: Высшая школа, 1981.-208с.

50. Слипченко В.Г., Табарный В.Г. Машинные алгоритмы и программы моделирования электронных схем. Киев: Техника, 1976. - 157с.

51. Секунов Н. Самоучитель С#. — СПб.: BHV-Петербург, 2001.

52. Сешу С., Балабанян. Н. Анализ линейных цепей. Госэнергоиздат,1963.

53. Степаненко И. П. Основы микроэлектроники: Учебное пособие для вузов. -М.: Советское радио, 1980.

54. Трудономин В. А., Пивоварова Н. В. Математические модели технических объектов. М.: Высшая школа, 1986. - 157с.

55. Страуструп Б. Язык программирования С++. — Киев: ДиаСофт, 1993.

56. Тьюарсон Ф. Р. Разреженные матрицы. М.: Мир, 1977. - 189с.

57. Трауб. ДЖ. Итерационные методы решения уравнений. М.: Мир, 1985. -264с.

58. Фадеев Д. К., Фадеева В. Н. Вычислительные методы линейной алгебры. -М.: Издательство Физико-математической литературы, 1963. 734 с.

59. Фролов A.B. , Фролов Г.В. Библиотека системного программиста. — М.: Диалог-Мифи, 1991.

60. Холзнер С. Visual С++, учебный курс. СПб.: Питер, 2000.

61. Чуа JI.O., Пеи-Миллин. Машинный анализ электронных схем. -М.: Энергия, 1980.

62. Черносвитов A. Visual С++7 учебный Курс. Санкт-Петербург. Москва. Харьков. Минск, 2001. -522с.

63. Чеппел Д. Технологии ActiveX и OLE. — М.: Издательский отдел "Русская редакция", 1997.

64. Шакиров М.А Теоретические основы электротехники. Новые идеи и принципы. Схемоанализ и диакоптики. СПб.: Изд-во СПбГТУ, 2001. -212с.

65. Gear C.W. the automatic integration jf ordinary differential equations«comm. Of the ACM», 1971, v.14, N3.

66. Gear C. W. simultaneous numerical solution of differential algebraic equations-«Trans. IEEE, 1971, v.ct-18, N1