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

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

Родионов Виктор Викторович

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

Специальность 05.13.12 - «Системы автоматизации проектирования»

по техническим наукам (промышленность)

Автореферат

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

Ульяновск - 2005

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

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

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

кандидат технический наук, доцент Шишкин Вадим Викторинович

доктор технический наук, профессор Семушин Иннокентий Васильевич кандидат технический наук, доцент Наместников Алексей Михайлович

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

ФГУП НПО «Марс», г. Ульяновск

Защита состоится 21 декабря 2005 г. в 15.00 на заседании диссертационного совета Д212.277.01 при Ульяновском государственном техническом университете по адресу 432027, г Ульяновск, ул Северный Венец, 32, ауд. 211.

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

Автореферат разослан 18 ноября 2005 г.

Учёный секретарь диссертационного совета д.т.н., профессор

М. К. Казаков

zwóij

3

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

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

Для встраиваемых систем характерна неэффективность при использовании мощных микропроцессорных ядер, что связано с их повышенным энергопотреблением и тепловыделением. Поэтому часто применяют функционально распределённые встраиваемые микропроцессорные системы (ФР ВМС): часть функций системы реализуется программно, на сравнительно маломощном процессоре (или процессорах), а часть - аппаратно, с применением либо заказных специализированных СБИС, либо, всё чаще, программируемых логических интегральных схем (ПЛИС). Всё более распространёнными становятся «системы на кристалле» (СнК), интегрирующие процессоры и программируемую логику. Ввиду высоких требований, предъявляемых к встраиваемым системам, существует проблема оптимального распределения функций задачи (класса задач) между программной и аппаратной частью системы, а на дальнейшем уровне детализации - по конкретным вычислительным модулям.

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

Наиболее интенсивные исследования в области ФР ВМС стали проводиться с конца 80-х и начала 90-х годов прошлого века. Основные результаты нашли отражение в работах Kalavade A., Lee Е., Gupta R., Micheli G., Ernst R., Henkel J., PengZ., Kuchcinski K., Vahid F., Gong J., Gajski D. и др. Из отечественных авторов можно отметить Балашова Е. П., Пузанкова Д. В., Костен-ко В. А,, Смелянского P. JI. Однако практически во всех используемых подходах фактор неопределённости не учитывался.

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

1. Выбор и модификация оптимизационной модели ФР ВМС.

2. Выбор способа описания неопределё мации.

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

4. Разработка метода оптимизации ФР ВМС.

5. Разработка специализированной САПР ФРВМС. Исследование и настройка метода оптимизации.

Объектом исследования в работе является автоматизация проектирования ФР ВМС, предметом исследования служат применяемые для этого модели и методы.

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

Научная новизна работы состоит в следующем:

1. Выбрана и модифицирована оптимизационная модель ФР ВМС с учётом влияния нечёткости исходных данных.

2. Разработана модель нечётких интервалов, описывающая неопределённость значений параметров ФР ВМС.

3. В рамках предложенной модели разработана алгебра нечётких интервалов и реализован способ их точного сравнения.

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

Практическая ценность работы состоит в разработке специализированной САПР на основе предложенных моделей и подходов. САПР была использована в НИР и ОКР, связанных с проектированием модуля формирования изображений для бортовых индикаторов на основе жидкокристаллических матриц для ОАО «УКБП» и разработкой семейства встраиваемых масштабируемых микропроцессорных систем синтеза и визуализации графической информации и методов их автоматизированного проектирования, проводимой в рамках научно-исследовательской программы «Научные исследования высшей школы по приоритетным направлениям науки и техники» 2003-2004 гг., подпрограмма «Электроника».

Апробация работы. Основные положения диссертационной работы докладывались на международных конференциях «Континуальные логико-алгебраические исчисления и нейроматематика в науке, технике и экономике» (Ульяновск, УлГТУ, 2001 г.), «Континуальные алгебраические логики, исчисления и нейроматематика в науке, технике и экономике» (Ульяновск, УлГТУ, 2002-2003 гг.), «Интеллектуальные системы» (Дивноморское, 20022005 гг.), «Интерактивные системы: Проблемы человеко-компьютерного взаимодействия» (Ульяновск, УлГТУ, 2003 г.), «Интерактивные системы и технологии: Проблемы человеко-компьютерного взаимодействия» (Ульяновск, УлГТУ, 2005 г.), на международном научно-практическом семинаре «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Коломна, 2005 г.), а также на НТК УлГТУ (2001-2005 гг.).

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

Структура и объём диссертации. Основное содержание работы изложено на 240 страницах машинописного текста, который включает 36 иллюстраций и 43 таблицы. Диссертационная работа состоит из введения, четырёх глав, заключения, библиографического списка из 125 наименований и двух приложений.

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

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

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

Пусть дан класс из Q задач, состоящих из множества функций F = (flv.., f0), и набор вычислительных модулей: микропроцессоров MP, специализированных СБИС ASIC и ПЛИС FPGA. Необходимо определить состав ФРВМС Uopt=MPoptuASICoptuFPGAopt, где MPoptcMP,

ASICopt с ASIC, FPGAop( с FPGA, и способ аппаратной или программной реализация функций fj так, чтобы при выполнении заданных ограничений система была бы оптимальной по некоторому критерию: f(U, X)->extr,

G = {gk(U,X)}, к = 1^т,где f- целевая функция,

U = (и,.....udi.....udi+d2,..., u„i+d2+d3) - архитектурный вектор решения, где

dj - количество микропроцессоров, d2 - специализированных СБИС, d3 -ПЛИС; переменная Uj е {0,1} задаёт включение j-ro модуля в состав ФР МВС,

X = (xj,..., хв) - функциональный вектор решения, х, e[l,d], где d = d, + d2 + d3; x, задаёт модуль, на котором будет выполняться i-я функции, G - множество ограничений на решения, ш - количество ограничений.

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

ность выполнения 1-й функции в .¡-м модуле. Остальные ш-2 ограничений специфичны для конкретной постановки задачи.

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

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

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

Конкретная частная постановка задачи формулируется следующим образом: минимизировать стоимость системы при ограничениях по времени, объему модулей ПЛИС, по массе, габаритам системы и вероятности безотказной работы.

Для расчёта характеристик ФР ВМС использованы следующие модели.

1. Время выполнения наибольшей по длительности задачи:

Т = тахСГтеРагаНеНю4)), 4 = 1,0, где ч

ИтеРагаНе! - алгоритмическая функция расчёта времени для ц-й задачи, о4 - размерность ц-й задачи.

2. Стоимость разработки системы:

д и <1 п

с=++ХЕсиги' где

Н н Н 1-1

и. - ¡-й элемент архитектурного вектора решения и, с, - стоимость ¿-го модуля, с; - стоимость ¿-го дополнительного ресурса, о - количество дополнительных ресурсов,

г. =011гу - вектор востребованных дополнительных ресурсов; строится

на основе матрицы гу, которая описывает потребности вычислительных модулей в комплектации дополнительными ресурсами, ^ е {0,1}, е {0,1}, сц - стоимость реализации функции Г, в ¿-м модуле,

[1, если функция £ будет выполняться в ¿-м модуле, 4 [О, иначе.

3. Количество используемых вентилей ПЛИС:

п __

Vj=£v.zü> j = d, +d? +l,d, где

¡=i

v, - количество вентилей для реализации функции fj на ПЛИС.

4. Масса вычислительных модулей:

d

А = Хи]аягде

И

aj масса j-ro вычислительного модуля.

5. Габариты (площадь) вычислительных модулей:

d

S = ^UjSj, где Н

Sj - площадь j-ro вычислительного модуля.

6. Вероятность безотказной работы системы:

Р = е , где

Äj - интенсивность отказов j-ro модуля.

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

Неопределённость значений параметров ФР ВМС формализуется средствами теории НИ. Форма функции принадлежности (ФП) НИ аппроксимирована функциями L и R, где L = R = max(0,1 - хр). Предусмотрены трапециевидный НИ (при р = 1); вогнутая (р = 0,5) и выпуклая ФП (р = 2).

Определяется алгебра НИ с операциями сложения, вычитания, умножения, деления и экспоненциальной функцией. Все операции, кроме последней, выполняются над двумя НИ М и N. Обозначив m и n, m и п - левые и правые границы ядер НИ М и N, аиу, ß и 5 - их коэффициенты нечёткости (КН), будем применять параметрическую запись: М = (m,m,oc,ß)LR и N = (n,n,y,5)LR.

Для определения границ ядра и КН за основу взята формула, задающая произвольную операцию f алгебры над НИ М и N:

f(M,N) = (f(m,a),f(m,n),f(m,n) - f (m - a,n - у), ^

f (m + ß, n + S) - f (m, n))LR.

В то же время, аналогом ядер НИ являются обычные чёткие интервалы, для которых в стандартной интервальной математике:

1ХМ,]Ч) = {тт(Г(т,п),Г(т,п),Г(т,п),Г(т,п)),

- — -- (2)

тахд(т,п)^(т,п\1(т,п)Л(т,п))}.

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

1. Сложение нечётких интервалов. Согласно (1) получаем:

М + N = (т + п,т + п,а + у,Р + .

Применительно к ядру НИ эта формула согласуется и с (2).

2. Вычитание нечётких интервалов. Здесь формулы (1) недостаточно для корректного определения и границ ядра нового НИ, и значений его КН.

Если |т-т|<|п-п|,то при использовании (1) результирующий НИ будет некорректным, мнимым, поскольку его левая граница будет больше правой. Предлагается подход, делающий ненужным применение формулы (2) для таких случаев. Ядро НИ рассматривается как величина, задаваемая не граничными точками, а своей протяжённостью. Проводится аналогия между величинами ядер НИ и обычными числовыми величинами. Поскольку при вычитании из меньшего числа большего результат будет отрицательной величиной, то и полученный мнимый интервал будет записан в виде сопряжённого ему, однако со знаком «минус». Использование «отрицательных» (мнимых) НИ будет влиять как вид операции, так и на знак результата согласно правилам, принятым в обычной арифметике.

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

3. Перемножение нечётких интервалов:

М • N = fmn.mn.maxfO. an + y(m - a)),max(0,pn + 5(m + р)))щ. Формула справедлива при условии, что m, т, n, п > 0. Иначе снова может быть получен мнимый интервал (если, например, m, п < 0, m>0,n<0).

4. Деление нечётких интервалов расписывается аналогично вычитанию. Причём п*0, п*0 и n*y, следовательно у>0, 5>0.

5. Экспоненциальная функция. Достаточно представить число е в виде НИ Е = (е,е,0,0), тогда получим:

(ш - n,m - n,max(0,a - у),тах(0,р - 6))LR,| m-m|>|n-n|, - (т - n,m - п,тах(0,р - 5),тах(0,а - y))nL,| т - т| < | n - n |.

eM = (e®, em, em - em-", e1"^ - en),

Для полного определения результата операции f необходимо также агрегирование ФП её операндов, которое для НИ LR-типа сведётся к определению

вида функций L и R. Функцию агрегирования определим как f

Рм.Рм =Pn.

Pf(m,N) =- 1>Pm(N) =2;Pn(M) =0>5,

max(PM.PN).PM(N) =!;PN(M) =°.5 (PN(M) = 2)-

Помимо алгебраических, необходимы операции сравнения НИ. Реализовано точное сравнение НИ на основе показателей неравенства PSE, NSE, PS, NS, описанных в известной работе Д. Дюбуа, А. Прада «Теория возможностей. Приложение к представлению знаний в информатике». Эти показатели применялись и для определения равенства НИ. Предложено использовать «мягкое равенство» с допустимой погрешностью Ç.

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

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

САПР ФР ВМС SoftCAD разработана в среде Delphi в рамках технологии объектно-ориентированного программирования в качестве MDI-приложения Windows. Архитектуру САПР образуют 1) блок ввода параметров оптимизационной модели и ГА (он связан с базой данных), 2) блок операций над НИ, 3) блок реализации ГА и механизмов эволюции, 4) блок моделирования и выдачи результатов (рис. 1). В состав блоков входят как модули форм, поддерживающие функционирование визуального интерфейса с пользователем, так и модули, не связанные с формами.

Параметры оптимизационной модели вводятся по группам: «Общие», «Номенклатура», «Интеграция», «Ресурсы», «Функции», «ПЛИС», «Стоимость и надёжность», «Время», «Популяции». Большинство параметров задаётся с помощью НИ, представляемых в виде (m,m/a,p/pL,pR), где pL, pR е («вогнутая», «прямая», «выпуклая»). Обработка НИ сосредоточена в отдельном модуле, который может быть включён в состав любого проекта.

Рис. 1. Архитектура САПР войСАБ

Во время работы САПР хранилищем данных и методов оптимизационной модели является глобальный объект 8узМо<1 класса ТвувМос!. В нём сосредоточена основная функциональность программы: от реализации ГА до вывода результатов моделирования. Загрузка данных в поля и структуры объекта Яув-Мо<1 может быть выполнена двумя способами: 1) ввод данных «с нуля», 2) загрузка из базы данных. В ходе моделирования объект вуяМо«! служит источником данных, хранит промежуточные данные, в том числе и вспомогательные, и сохраняет полученные результаты, т.е. преобразованную популяцию, имеющую в своем составе лучшее найденное решение (или решения).

Особи (закодированные решения), с которым работает ГА, состоят из хромосом двух типов: а-хромосома по назначению и составу соответствует архитектурному вектору решения, Хромосома- функциональному. К а- и Г-хромосомам применяются одни и те же операторы кроссовера и мутации, однако операторы, работающие с явным представлением генов, предназначены только для ^хромосом.

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

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

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

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

Разработанная САПР была применена для проектирования модуля формирования изображений (МФИ) для бортовых встраиваемых индикаторов на основе жидкокристаллических матриц. В составе задач, решаемых МФИ, были выделены 28 функций, в том числе для формирования и обработки видеосигнала, формирования изображения и т.д. В качестве аппаратной основы рассматривалась СнК Excalibur компании Altera с процессорными ядрами ARM922T или Nios, а также ПЛИС АРЕХ20К100Е.

Было проведено исследование эффективности ГА при различных размерах входных данных, а также его сравнение с полным перебором и методом ветвей и границ. Исследования выполнялись на компьютере AMD Athlon ХР 2000+, 256 Мб ОЗУ DDR 266 с операционной системой Windows 2000 Professional.

Сложность полного перебора составит 0(2ddI1co2), где d - количество вычислительных модулей, п - количество функций, © - количество вершин нечёткого графа задачи. Результаты оценки применимости этого метода сведены в табл. 1. В табл. 2 представлены результаты для метода ветвей и границ, полученные экспериментальным путём.

Порядок сложности ГА был определён как O((d + n)<o2), хотя точная связь между размером входа ГА и необходимым количеством вычислений целевой функции (ЦФ) устанавливается только экспериментально. В частности, при оптимизации МФИ с помощью ГА были получены следующие данные (табл. 3).

Таблица 1

Оценка применимости полного перебора

Количество модулей (d) Количество функций (п) Количество ихераций (вычислений ЦФ)

Задача получения конфигурации ФР ВМС «МФИ»

3 28 1,83x10й

Предельная размерность задачи, решаемой полным перебором

2 17 5,24x105

3 10 4,72x105

Таблица 2

Оценка применимости метода ветвей и границ

Количество модулей (<1) Количество функций (п) Количество итераций (вычислений ЦФ)

Задача получения конфигурации ФР ВМС «МФИ»

3 28 не было установлено

Предельная размерность задачи, решаемой методом ветвей и границ

2 21 7,44x105

3 15 8,31х105

Таблица 3

Решение задачи проектирования ФР ВМС «МФИ» с помощью ГА

Л п со Количество вычислений ЦФ Время вычисления ЦФ, сек. Время работы ГА, мин.

3 28 93 5x103 6x10-3 0,5

Сопоставление количества вычислений ЦФ, необходимых для получения оптимальной конфигурации ФР ВМС «МФИ» с помощью полного перебора, метода ветвей и границ и ГА, показывает, что для ГА это значение будет на много порядков меньше, чем для первых двух методов.

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

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

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

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

Итогом работы является получение модели и метода оптимизации функционально распределённых встраиваемых микропроцессорных систем (ФР ВМС) в условиях неопределённости проектной информации, создание на их основе специализированной САПР.

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

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

В данной работе:

1. Предложена постановка задачи оптимизации ФР ВМС на основе нечетких исходных данных, описанных средствами теории нечётких интервалов.

2. Введены критерии оценки ФР ВМС и модели их вычисления.

3. Предложена и обоснована модель нечётких интервалов для описания неопределённости значений параметров ФР ВМС.

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

5. Реализовано сравнение нечётких интервалов в рамках используемой модели.

6. Разработана реализация параллельного генетического алгоритма.

7. Создана САПР, позволяющая проводить оптимизацию ФР ВМС на основе предлагаемых подходов.

8. Исследована и подтверждена высокая эффективность САПР, в том числе по сравнению с переборными методами.

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

Основное содержание диссертации опубликовано в работах:

1. Шишкин В. В., Родионов В. В. Постановка задачи нечеткой оптимизации ФР СОД // Реляторные, непрерывнологические и нейронные сети и модели: Тр. междунар. копф. «Континуальные логико-алгебраические исчисления и нейроматематика в науке, технике и экономике» (Ульяновск, 15-17 мая 2001 г.). - Ульяновск: УлГТУ, 2001. - Том 2. - С. 107.

2. Оптимизация функционально распределенных систем обработки данных: постановка задачи и подходы к ее решению / В. В. Шишкин, В. В. Родионов; Ульяновский гос. техн. ун-т, - Ульяновск, 2002. - 21 е.: ил. -Деп. в ВИНИТИ 06.11.02, № 1913-В2002.

3. Обзор методов улучшения генетических алгоритмов / В. В. Шишкин, В. В. Родионов; Ульяновский гос. техн. ун-т. - Ульяновск, 2002. - 25 е.: ил. -Деп. в ВИНИТИ 06.11.02, № 1914-В2002.

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

B. В. Родионов; Ульяновский гос. техн. ун-т. - Ульяновск, 2002. - 49 е.: ил. -Деп. в ВИНИТИ 06.11.02, № 1915-В2002.

5. Шишкин В. В., Родионов В. В. Постановка задачи нечеткой оптимизации ФР СОД и подходы к её решению // Системы искусственного интеллекта: алгоритмы обработки и модели: Тр. междунар. конф. «Континуальные алгебраические логики, исчисления и нейроматематика в науке, технике и экономике» (Ульяновск, 14-16 мая 2002 г.). - Ульяновск: УлГТУ, 2002.- Том 4.-

C. 5-6.

6. Шишкин В. В., Родионов В. В. Определение нечеткости в задаче оптимизации функционально распределенных систем обработки данных и подходы к её решению// Тр. междунар. науч.-техн. конференций «Интеллектуальные системы» и «Интеллектуальные САПР» (Дивноморское, 3-10 сентября

2002 г.). - М.: Физматлит, 2002. - С. 79-83.

7. Шишкин В. В., Родионов В. В. Оптимальный выбор аппаратного или программного способа реализации функций класса задач с нечетко заданными критериями оценки // Системы искусственного интеллекта и нейроинформати-ка: Тр. междунар. конф. «Континуальные алгебраические логики, исчисления и нейроинформатика в науке, технике и экономике» (г.Ульяновск, 13-15 мая

2003 г.). - Ульяновск: УлГТУ, 2003. - Том 3. - С. 179-181.

8. Шишкин В. В., Родионов В. В. Оптимальный выбор аппаратного или программного способа реализации функций для функционально распределенных систем обработки данных с использованием нечетко заданных критериев оценки // Тр. междунар. науч.-техн. конференций «Интеллектуальные системы» и «Интеллектуальные САПР» (Дивноморское, 3-10 сентября 2003 г.). - М.: Физматлит,2003.-Т. 1. -С. 137-140.

9. Шишкин В. В., Родионов В. В. Выбор оптимального способа реализации функций для функционально распределенной системы обработки данных с использованием нечетко заданных критериев оценки // Вестник УлГТУ. -2003.-№ 1-2.-С. 43-45.

10. Shishkin V. V., Rodionov V. V. Functions Hardware/Software Codesign Using Fuzzy Evaluation Criteria For Functionally Distributed Computer Systems // Interactive Systems: The Problems of Human-Computer Interaction: Proceedings of International Conference (Ulyanovsk, September 23-27, 2003). - Ulyanovsk: U1STU, 2003. - P. 130-133.

11. Шишкин В. В., Родионов В. В. Оптимизационная модель проектирования последовательно-параллельных систем обработки данных с использованием нечётких интервалов // Тр. междунар. науч.-техн. конференций «Интеллектуальные системы» и «Интеллектуальные САПР» (Дивноморское, 3-10 сентября 2004 г.). - М: Физматлит, 2004. - Т. 1. - С. 409-414.

12. Разработка модуля формирования изображения для бортовых индикаторов на основе ЖК-матриц: отчет об ОКР (закточ.) / Ульяновский гос. техн. унив-т; руков. Шишкин В. В. - 12-86/01; № ГР 01200214259; Инв.

№ 02200502905. - Ульяновск, 2004. - 195 с. - Исполн.: Виноградов Л. Б.( Родионов В. В., Улыбин В. В.

13. Разработка семейства встраиваемых масштабируемых микропроцессорных систем синтеза и визуализации графической информации и методов их автоматизированного проектирования на основе мягких вычислений: отчет о НИР (заключ.) / Ульяновский гос. техн. унив-т; руков. Шишкин В. В. - 2-12/03; № ГР 01200312434; Инв. №02200505041,- Ульяновск, 2004. - 311 с. - Исполн.: Виноградов А. Б., Родионов В. В., Улыбин В. В.

H.Шишкин В. В., Родионов В. В. Модель нечётких интервалов для САПР функционально распределенной системы обработки данных // Интегрированные модели и мягкие вычисления в искусственном интеллекте: Сб. науч. тр. междунар. науч.-практ. сем. (Коломна, 15-17 мая 2005 г.). - М.: Физматлит, 2005.-С. 160-165.

15. Шишкин В. В., Родионов В. В. Алгебра нечётких интервалов LR-типа для автоматизированного проектирования функционально распределённых систем обработки данных// Тр. междунар. науч.-техн. конференций «Интеллектуальные системы» и «Интеллектуальные САПР (Дивноморское, 3-10 сентября 2005 г.).-М.: Физматлит,2005.-Т. 1. -С. 145-154.

16. Rodionov V. V. CAD System Of Functionally Distributed Computer Systems On The Basis Of Soft Computing // Interactive Systems and Technologies: The Problems of Human-Computer Interaction: Proceedings of International Conference (Ulyanovsk, September 26-30, 2005). - Ulyanovsk: U1STU, 2005. - P. 139-144.

Получены авторские свидетельства на программные продукты:

I. САПР функционально распределенных систем обработки данных на основе средств мягких вычислений: свидетельство об официальной регистрации программы для ЭВМ №2005611941 Федеральной службы по интеллектуальной собственности, патентам и товарным знакам / Шишкин В. В., Родионов В. В.; заяв. и правообл. Ульяновский гос. техн. ун-т. - Заявка № 2005611337; дата пост. 7.06.2005; зарег. 3.08.2005.

СПИСОК ИСПОЛЬЗОВАННЫХ СОКРАЩЕНИЙ

ГА - генетический алгоритм, КН - коэффициент нечёткости, МФИ- модуль формирования изображений, НГ - нечёткий граф, НИ - нечёткий интервал, ПЛИС- программируемая логическая интегральная схема,

СнК - система на кристалле, ФП - функция принадлежности, ФРВМС- функционально распределённая встраиваемая микропроцессорная система, ЦФ - целевая функция.

№24668

РНБ Русский фонд

2006-4 27276

Родионов Виктор Викторович

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

Специальность 05.13.12 - «Системы автоматизации проектирования» по техническим наукам (промышленность)

Подписано в печать 11.11.2005. Формат 60x84/16. Бумага офсетная. Печать трафаретная. Усл. п. л. 0,93. Уч.-изд. л. 0,90. Тираж 100 экз. Заказ//?/ Типография УлГТУ. 432027, Ульяновск, ул. Северный Венец, 32

СПИСОК ИСПОЛЬЗОВАННЫХ СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

Глава 1. АРХИТЕКТУРЫ МИКРОПРОЦЕССОРНЫХ СИСТЕМ.

МЕТОДЫ И СРЕДСТВА ПРОЕКТИРОВАНИЯ.

1.1 Анализ архитектур микропроцессорных систем. Уровни и методы проектирования систем.

1.1.1 Основные подходы к анализу архитектур.

1.1.2 Архитектуры функционально распределённых встраиваемых микропроцессорных систем.

1.1.3 Уровни и методы проектирования систем.

1.2 Существующие подходы к решению задачи аппаратно-программного разбиения системы.

1.3 Постановка задачи оптимизации в условиях неопределённости.

1.4 Анализ задачи и методов её решения.

1.5 Анализ генетических алгоритмов.

1.5.1 Общая характеристика генетических алгоритмов и проблемы, возникающие при их разработке.

1.5.2 Схемы работы генетических алгоритмов. Параллельные генетические алгоритмы.

1.5.3 Функция пригодности особей популяции.

1.5.4 Кодирование параметров решения задачи.

1.5.5 Решение проблемы ложных значений в генах.

1.5.6 Метод выбора брачных пар.

1.5.7 Оператор отбора.

1.5.8 Оператор кроссовера.

1.5.9 Оператор мутации.

1.5.10 Общие модификации операторов.

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

Глава 2. РАЗРАБОТКА МОДЕЛИ И МЕТОДА ОПТИМИЗАЦИИ

2.1 Оптимизационная модель ФР ВМС.

2.1.1 Проблема оценки времени выполнения задачи

2.1.2 Модель выполнения задачи ФР ВМС.

• 2.1.3 Расчёт характеристик ФР ВМС.

2.2 Алгебра нечётких интервалов и их сравнение.

2.2.1 Функция формы нечёткого интервала. Выбор и обоснование.

2.2.2 Алгебра нечётких интервалов.

2.2.3 Сравнение нечётких интервалов.

2.3 Разработка метода оптимизации.

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

2.3.2 Общие параметры генетического алгоритма.

2.3.3 Оператор отбора.

• 2.3.4 Метод выбора брачных пар.

2.3.5 Оператор кроссовера.

2.3.6 Оператор мутации.

2.3.7 Механизм избавления от непригодных решений

2.3.8 Миграции.

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

Глава 3. РАЗРАБОТКА ИНСТРУМЕНТАЛЬНЫХ СРЕДСТВ

АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ.

3.1 Архитектура САПР ЭойСАО.

3.2 Основные структуры данных, методы и алгоритмы.

3.2.1 Основные потоки данных в САПР воЛСАО.

3.2.2 База данных САПР ЗоЛСАй.

• 3.2.3 Классы, типы и структуры данных, используемые для реализации генетического алгоритма и оптимизационной модели.

3.2.4 Файл настроек SoftCAD.INI.

3.2.5 Реализация операторов и механизмов генетического алгоритма.

3.2.6 Классы и структуры данных, используемые для реализации операций над нечёткими m интервалами.

3.3 Порядок работы. Пользовательский интерфейс.

3.3.1 Назначение САПР SoftCAD.

3.3.2 Состав САПР SoftCAD.

3.3.3 Интерфейс САПР SoftCAD.

3.3.3.1 Обзор рабочей среды САПР SoftCAD.

3.3.3.2 Загрузка и сохранение данных.

3.3.3.3 Настройка параметров модели и популяций.

3.3.3.4 Моделирование. Получение результатов

3.3.3.5 Состав отчётности о ходе эволюции популяций и её результатах.

3.3.3.6 Получение справочных данных.

Дополнительные возможности.

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

Глава 4. ИССЛЕДОВАНИЕ МОДЕЛИ, МЕТОДА ОПТИМИЗАЦИИ

И ИНСТРУМЕНТАЛЬНЫХ СРЕДСТВ.

4.1 Параметры и условия моделирования.

4.2 Задача формирования изображений.

4.2.1 Описание ФР ВМС «Модуль формирования изображений».

4.2.2 Параметры ФР ВМС «Модуль формирование изображений».

4.2.2.1 Аппаратная конфигурация и дополнительные ресурсы.

4.2.2.2 Список функций.

4.2.2.3 Стоимостные параметры.

4.2.2.4 Временные параметры.

4.2.2.5 Ёмкостные параметры.

4.2.2.6 Надёжностные параметры.

4.2.2.7 Параметры массы.

4.2.2.8 Параметры габаритов (площади).

4.3 Результаты моделирования.

• 4.3.1 Исследование генетического алгоритма.

4.3.2 Оптимальные схемы работы генетического алгоритма.

4.3.3 Результаты моделирования для ФР ВМС

Модуль формирования изображений».

4.3.4 Оценка эффективности САПР БоЛСЛО.

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

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

Для встраиваемых систем характерна неэффективность при использовании мощных микропроцессорных ядер, что связано с их повышенным энергопотреблением и тепловыделением. Поэтому часто применяют функционально распределённые встраиваемые микропроцессорные системы (ФР ВМС): часть функций системы реализуется программно, на сравнительно маломощном процессоре (или процессорах), а часть - аппаратно, с применением либо заказных специализированных СБИС, либо, всё чаще, программируемых логических интегральных схем (ПЛИС). Всё более распространёнными становятся «системы на кристалле» (СнК), интегрирующие процессоры и программируемую логику. Ввиду высоких требований, предъявляемых к встраиваемым системам, существует проблема оптимального распределения функций задачи (класса задач) между программной и аппаратной частью системы, а на дальнейшем уровне детализации - по конкретным вычислительным модулям.

Исторически функциональное распределение использовалось не только во встраиваемых системах. В 80-е годы прошлого века для специализированных применений разрабатывались проблемно ориентированные системы (ПОС), состоящие из ЭВМ общего назначения («базовой машины») и функционально ориентированных процессоров (ФОП), предназначенных для эффективной реализации сложных функций [78]. Активные работы в этом направлении проводились на кафедре «Вычислительная техника» Ленинградского государственного электротехнического института (ныне Санкт-Петербургский государственный электротехнический университет) под руководством Балашова Е. П. и Пузанкова Д. В.

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

Наиболее интенсивные исследования в области ФР ВМС стали проводиться с конца 80-х и начала 90-х годов прошлого века. Основные результаты нашли отражение в работах Kalavade A., Lee Е., Gupta R., Micheli G., Ernst R., Henkel J., Peng Z., Kuchcinski K., Vahid F., Gong J., Gajski D. и др. [108, 110, 112, ИЗ, 115, 116, 119, 123].

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

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

Появились программные системы, поддерживающие проектирование сложных микропроцессорных архитектур с произвольной топологией внутренних соединений и произвольным сочетанием центральных процессоров и аппаратных блоков [10, 72, 82, 99, 105, 109, 111, 114, 117, 118]. Большой вклад в разработку таких систем, базирующуюся на проводимых фундаментальных и прикладных исследованиях в области анализа структур вычислительных комплексов, внесла лаборатория вычислительных комплексов МГУ в лице Смелянского Р. Л., Кос-тенко В. А. и др. [35, 37, 72, 82, 95].

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

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

1. Выбор и модификация оптимизационной модели ФР ВМС.

2. Выбор способа формализации неопределённости.

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

4. Разработка метода оптимизации ФР ВМС.

5. Разработка специализированной САПР ФР ВМС. Исследование и настройка метода оптимизации.

Объектом исследования в работе является автоматизация проектирования ФР ВМС, предметом исследования служат применяемые для этого модели и методы.

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

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

1. АРХИТЕКТУРЫ МИКРОПРОЦЕССОРНЫХ СИСТЕМ. МЕТОДЫ И СРЕДСТВА ПРОЕКТИРОВАНИЯ

Результаты работы были использованы в НИР и ОКР [65, 66], связанных с проектированием модуля формирования изображений для бортовых индикаторов на основе жидкокристаллических матриц для ОАО «УКБП» и разработкой семейства встраиваемых масштабируемых микропроцессорных систем синтеза и визуализации графической информации и методов их автоматизированного проектирования, проводимой в рамках научно-исследовательской программы «Научные исследования высшей школы по приоритетным направлениям науки и техники» 2003-2004 гг., подпрограмма «Электроника», а также в учебном процессе в рамках дисциплины «САПР».

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

ЗАКЛЮЧЕНИЕ

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

В данной работе:

1. Предложена постановка задачи оптимизации ФР ВМС на основе нечётких исходных данных, описанных средствами теории нечётких интервалов.

2. Введены критерии оценки ФР ВМС и модели их вычисления.

3. Предложена и обоснована модель нечётких интервалов для описания неопределённости значений параметров ФР ВМС.

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

5. Реализовано сравнение нечётких интервалов в рамках используемой модели.

6. Разработана реализация параллельного генетического алгоритма.

7. Создана САПР, позволяющая проводить оптимизацию ФР ВМС на основе предлагаемых подходов.

8. Исследована и подтверждена высокая эффективность САПР, в том числе по сравнению с переборными методами.

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

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

Научная новизна работы:

1. Выбрана и модифицирована оптимизационная модель ФР ВМС с учётом влияния нечёткости исходных данных.

2. Разработана модель нечётких интервалов, описывающая неопределённость значений параметров ФР ВМС.

3. В рамках предложенной модели разработана алгебра нечётких интервалов и реализован способ их точного сравнения.

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

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах [93, 94, 88, 90, 89, 121,91,86, 84, 120].

1. Международная конференция «Континуальные логико-алгебраические исчисления и нейроматематика в науке, технике и экономике» (КЛИН-2001), Ульяновск, 15-17 мая 2001 г.

2. Международная конференция «Континуальные алгебраические логики, исчисления и нейроматематика в науке, технике и экономике» (КЛИН-2002), Ульяновск, 14-16 мая 2002 г.

3. Международная научно-техническая конференция «Интеллектуальные системы» (А18'02), Дивноморское, 3-10 сентября 2002 г.

4. Международная конференция «Континуальные алгебраические логики, исчисления и нейроматематика в науке, технике и экономике» (КЛИН-2003), Ульяновск, 13-15 мая 2003 г.

5. Международная научно-техническая конференция «Интеллектуальные системы» (А18'03), Дивноморское, 3-10 сентября 2003 г.

6. Международная конференция «Интерактивные системы: Проблемы че-ловеко-компьютерного взаимодействия», Ульяновск, 23-27 сентября 2003 г.

7. Международная научно-техническая конференция «Интеллектуальные системы» (А18'04), Дивноморское, 3-10 сентября 2004 г.

8. Международный научно-практический семинар «Интегрированные модели и мягкие вычисления в искусственном интеллекте», Коломна, 15-17 мая 2005 г.

9. Международная научно-техническая конференция «Интеллектуальные системы» (А18'05), Дивноморское, 3-10 сентября 2005 г.

10. Международная конференция «Интерактивные системы и технологии: Проблемы человеко-компьютерного взаимодействия», Ульяновск, 26-30 сентября 2005 г.

11. Научно-технические конференции Ульяновского государственного технического университета, 2001-2005 гг.

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

В работах [93, 94] дана базовая постановка задачи оптимизации ФР ВМС в условиях неопределённости проектной информации. В работе [92] проведён анализ возможных методов решения оптимизационной задачи, выбран генетический алгоритм. В работе [87] проанализированы разновидности генетического алгоритма, его методов и операторов, отмечены наиболее подходящие для реализации. В работах [67, 88] рассмотрены способы формализации неопределённости, разработана и описана модель и алгебра нечётких интервалов, способ их точного сравнения. В работах [90, 89, 85, 121] описана оптимизационная задача с использованием элементной базы ПЛИС, введены новые критерии оценки проектируемой системы, выбрана и описана оптимизационная модель ФРВМС. В работе [91] расширена оптимизационная модель проектируемой системы за счёт возможности использования элементной базы систем на кристалле, предложен алгоритм расчёта времени выполнения задачи на основе нечёткого графа. В работах [86, 84] сформулирован окончательный вариант оптимизационной модели, алгебры и способа сравнения нечётких интервалов, кратко описана их реализация в разработанной САПР. В работе [120] дано описание САПР, созданной на основе на основе предложенных подходов.

На разработанную САПР получено свидетельство об официальной регистрации программы для ЭВМ №2005611941 Федеральной службы по интеллектуальной собственности, патентам и товарным знакам.

1. Алтунин, А. Е. Модели и алгоритмы принятия решений в нечетких условиях: монография / А. Е. Алтунин, М. В. Семухин. Тюмень: Издательство Тюменского государственного университета, 2000. - 352 с.

2. Антамошкин, А. Н. Гриди-алгоритмы и локальный поиск для условной псевдобулевой оптимизации Электронный ресурс. / А. Н. Антамошкин, И. С. Масич // Исследовано в России. 2003. - С. 2143-2149. - Режим доступа: http://zhurnal.gpi.ru/

3. Батищев, Д. И. Оптимизация многоэкстремальных функций с помощью генетических алгоритмов / Д. И. Батищев, С. А. Исаев // Высокие технологии в технике, медицине и образовании: межвуз. сб. науч. тр. Воронеж: ВГТУ, 1997.-С. 4-17.

4. Батыршин, И. 3. Основные операции нечёткой логики и их обобщения / И. 3. Батыршин; Казань: Отечество, 2001. — 102 с.

5. Божич, В. И. Методы генетического поиска для решений, представимых мультихромосомами / В. И. Божич, В. Б. Лебедев // Перспективные информационные технологии и интеллектуальные системы. 2002. - № 3. - С. 38-44.

6. Бондаренко, А. Н. Многоядерные процессоры: первые попытки Электронный ресурс. / А. Н. Бондаренко // Компьютеры+Программы. 2005. — № 6. - Режим доступа: http://cpp.com.ua/

7. Борисовский, П. А. О сравнении некоторых эволюционных алгоритмов / П. А. Борисовский, А. В. Еремеев // Автоматика и телемеханика. 2004. -№3.-С. 3-10.

8. Букатов, А. А. Программирование многопроцессорных вычислительных систем / А. А. Букатов, В. Н. Дацюк, А. И. Жегуло. Ростов-на-Дону: Изд-во ООО «ЦВВР», 2003. - 208 с.

9. Бухтеев, А. Методы и средства проектирования систем на кристалле Электронный ресурс. / А. Бухтев // Chip News. 2003. - № 4. - Режим доступа: http://www.chip-news.ru/

10. Бухтев, А. Системы на кристалле. Новые тенденции Электронный ресурс. / А. Бухтев, В. Немудров // Электроника НТБ. 2004. - № 3. - Режим доступа: http://www.electronics.ru/

11. Былинович, А. П. Многохромосомная оптимизация оценки качества программных средств Электронный ресурс. / А. П. Былинович // Автоматизация проектирования.- 1999. № 1. — Режим доступа: http://mirror.ustu:80/www.osp.ru/

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

13. Васильев, В. И. Интеллектуальные системы управления с использованием генетических алгоритмов: учебное пособие / В. И. Васильев, Б. Г. Ильясов. Уфа: Изд-во Уфимск. гос. авиац. техн. ун-та, 1999. - 105 с.

14. Васильева, В. А. Уравнения: учебное пособие/ В.А.Васильева, Т. Д. Кудрина, Р. Н. Молодожникова; под ред. Р.Н. Молодожниковой. М.: Изд-во МАИ, 1993. - 80 с.

15. Воеводин, Вл. В. Методы описания и классификации архитектур вычислительных систем / Вл. В. Воеводин, А. П. Капитонова. М.: Изд-во МГУ, 1994.-79 с.

16. Вощинин, А. П. Оптимизация в условиях неопределенности / А. П. Вощинин, Г. Р. Сотиров. Изд-во МЭИ (СССР); «Техника» (НРБ), 1989. -224 с.

17. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности / Г.К. Вороновкий и др.. Харьков: Основа, 1997. -112 с.

18. Герасимов, Ю. Ю. Теория принятия решений: курс лекций Электронный ресурс. / Ю. Ю. Герасимов, В. Н. Андреев. Петрозаводск: ПетрГУ, 1998. - Режим доступа: http://dims.karelia.ru/

19. Глебов, Н. И. Методы оптимизации: учебное пособие / Н. И. Глебов, Ю. А. Кочетов, А. В. Плясунов. Новосибирск, Изд-во Новосибирского государственного университета, 2000. - 105 с.

20. Глебов, С. Г. Математическое программирование в задачах химической технологии: учебное пособие / С. Г. Глебов, А. И. Мубараков. Уфа: Изд-во УГНТУ, 2002.-79 с.

21. Голубин, А. В. Определение параметров генетического алгоритма с помощью программного комплекса «вепзеагсЬ» / А. В. Голубин // Перспективные информационные технологии и интеллектуальные системы. — 2004. -№ 3. С. 42-47.

22. Гэри, М. Вычислительные машины и трудноразрешимые задачи пер. с англ. / М. Гэри, Д. Джонсон. М.: Мир, 1982. - 416 с.

23. Дарвин, Ч. Сочинения. В 12 т. Т. 3. О происхождении видов путем естественного отбора или сохранении благоприятствуемых пород в борьбе за жизнь / Ч. Дарвин. М.;Л.: Изд-во АН СССР, 1939. - 832 с.

24. Дегтярев, Ю. И. Методы оптимизации: учеб. пособие для вузов / Ю. И. Дегтярев. М.: Сов. радио, 1980. - 276 с.

25. Дилигенский, Н. В. Нечеткое моделирование и многокритериальная оптимизация производственных систем в условиях неопределенности: технология, экономика, экология / Н. В. Дилигснский, Л. Г. Дымова, П. В. Севастьянов. М.: Машиностроение-1, 2004.-401 с.

26. Дюбуа, Д. Теория возможностей. Приложение к представлению знаний в информатике пер. с фр. В. Б. Тарасова. / Д. Дюбуа, А. Прад; под ред. С. А. Орловского. -М.: Радио и связь, 1990. 286 с.

27. Евдокимов, А. В. Численное решение нечетких дифференциальных уравнений методом линеаризации / А. В. Евдокимов // Известия Челябинского научного центра. 2003. - № 4. - С. 9-14.

28. Еремеев, А. В. Генетический алгоритм для задачи о покрытии /

29. A. В. Еремеев // Дискретный анализ и исследование операций. Серия 2. -2000. - Т. 7. - № 2. - С.47-60.

30. Заде, Л. А. Понятие лингвистической переменной и его применение к принятию приближенных решений / Л. А. Заде. М.: Мир, 1976. - 165 с.

31. Калашников, А. В. Средства конструирования итерационных алгоритмов для решения задач комбинаторной оптимизации / А. В. Калашников,

32. B. А. Костенко, М. И. Маркин // Искусственный интеллект. 2004. — № 2.1. C. 91-95.

33. Компьютер и задачи выбора/ Автор предисл. Ю. И. Журавлев. — М.: Наука, 1989.-208 с.

34. Корнеев, В. Эволюция микропроцессорных архитектур Электронный ресурс. / В. Корнеев // Открытые системы. 2000. - № 4. - Режим доступа: http://www.mp.dpt.ustu.ru/

35. Костенко, В. А. Влияние способа задания целевой функции на качество работы генетического алгоритма / В. А. Костенко, А. Г. Трекин // Искусственный интеллект. 2000. - № 2. - С. 97-102.

36. Кривченко, И. Системы на кристалле: общее представление и тенденции развития Электронный ресурс. / И. Кривченко // Компоненты и технологии. 2001. - № 6. - Режим доступа: http://www.compitech.ru/

37. Крюков, В. А. Разработка параллельных программ для вычислительных кластеров и сетей / В. А. Крюков // Информационные технологии и вычислительные системы. 2003. - № 1-2. — С. 42-61.

38. Курс математического анализа: В 3 т. Т. 1. Дифференциальное и интегральное исчисления функций одной переменной: учеб. для вузов / Л. Д. Кудрявцев. М.: Дрофа, 2003. - 704 с.

39. Курейчик, В. М. Генетические алгоритмы / В. М. Курейчик // Перспективные информационные технологии и интеллектуальные системы. — 2000. — № 1. — С. 18-21.

40. Курейчик, В. М. Исследование динамических операторов в эволюционном моделировании / В. М. Курейчик, Л. А. Зинченко, И. В. Хабарова // Перспективные информационные технологии и интеллектуальные системы.— 2001.-№3.-С. 65-70.

41. Курейчик, В. М. Перспективные архитектуры генетического поиска/ В. М. Курейчик // Перспективные информационные технологии и интеллектуальные системы. 2000. — № 1. - С. 58-60.

42. Курейчик, В. В. Перспективные технологии решения оптимизационных задач/ В. В. Курейчик, Н. В. Неупокоева // Перспективные информационные технологии и интеллектуальные системы. 2003. - № 2. - С. 80-84.

43. Майника, Э. Алгоритмы оптимизации на сетях и графах пер. с англ. / Э. Майника. М.: Мир, 1981. - 323 с.

44. Малиновский, Б. Н. История вычислительной техники в лицах / Б. Н. Малиновский. Киев, фирма «КИТ», ПТОО «А.С.К», 1995. - 384 с.

45. Мальцев, А. И. Алгебраические системы / А. И. Мальцев. — М.: Наука, 1970.-392 с.

46. Малюков, С. П. Применение генетических алгоритмов при разработке магнитных головок / С. П. Малюков, С. А. Обжелянский // Перспективные информационные технологии и интеллектуальные системы. — 2002. — № 2. -С. 58-71.

47. Минаков, И. А. О выборе оптимального метода селекции для генетического алгоритма Электронный ресурс. / И. А. Минаков // Вестник СамГТУ. Серия «Технические науки». № 8. - Самара, 2000. - Режим доступа: http://www.samgtu.ru/

48. Мухлаева, И. В. Решение задачи одномерной упаковки с помощью параллельного генетического алгоритма / И. В. Мухлаева // Перспективные информационные технологии и интеллектуальные системы. 2000. — № 1. — С. 77-84.

49. Новикова, Н. М. Основы оптимизации: курс лекций Электронный ресурс. / Н. М. Новикова. М., 1998. - 65 с. - Режим доступа: http://www.ccas.ru/

50. Обобщение метода анализа иерархий Саати для использования нечётко-интервальных экспертных данных Электронный ресурс. / А. А. Ахрамейко [и др.]. — 2002. — 6 с. Режим доступа: http://sedok.narod.ru

51. Пападимитриу, X. Комбинаторная оптимизация. Алгоритмы и сложность пер. с англ. /' X. Пападимитриу, К. Стайглиц. М.: Мир, 1985. - 512 с.

52. Петров, Г. А. Модель оптимизационных задач системного этапа проектирования проблемно ориентированных вычислительных систем / Г. А. Петров, Д. В. Пузанков, В. В. Шишкин // Электронное моделирование. 1991. - Т. 13, №4.-С. 23-27.

53. Пивкин, В. Я. Нечеткие множества в системах управления: методическое пособие / В. Я. Пивкин, Е. П. Бакулин, Д. И. Кореньков. Новосибирск: Новосибирский государственный университет, 1997. — 52 с.

54. Полупанов, А. А. Адаптивная архитектура генетического поиска / А. А. Полупанов // Перспективные информационные технологии и интеллектуальные системы. 2002. - № 3. — С. 49-55.

55. Прилуцкий, М. X. Многостадийные задачи распределения и упорядочения с нечеткими характеристиками Электронный ресурс. / М. X. Прилуцкий, Д.В.Попов // Исследовано в России. — 2001. — С. 11821189. — Режим доступа: http://zhurnal.ape.relarn.ru

56. Применение распределённого генетического алгоритма при решении задачи об упаковке в контейнеры / Ю. А. Бюргер и др. // Перспективные информационные технологии и интеллектуальные системы.- 2003.— №1.-С. 11-15.

57. Ульяновск, 2004. 311 с. - Исполн.: Виноградов А.Б., Родионов В.В., Улы-бин В.В. -№ ГР 01200312434. - Инв. № 02200505041.

58. Родионов, В. В. Вычислительная модель операций над нечеткими интервалами / В. В. Родионов; Ульяновский гос. техн. ун-т. Ульяновск, 2002. -49 е.: ил. - Деп. в ВИНИТИ 06.11.02, № 1915-В2002.

59. Романовский, И. В. Алгоритмы решения экстремальных задач / И. В. Романовский. М.: Наука, 1977. - 352 с.

60. Ротштейн, А. П. Интеллектуальные технологии идентификации: нечеткие множества, генетические алгоритмы, нейронные сети / А. П. Ротштейн. -Винница: Универсум-Винница, 1999. 320 с.

61. Севастьянов, П. В. Оценка финансовых параметров и риска инвестиций с позиций теории нечетких множеств / П. В. Севастьянов, Д. П. Севастьянов // Надежные программы. — 1997. — № 1. — С. 10-18.

62. Системы параллельной обработки пер. с англ. / Ж.-Д. Баер [и др.]; под ред. Д. Ивенса. -М.: Мир, 1985.-416 с.

63. Смородинский, С. С. Оптимизация решений на основе методов и моделей математического программирования: учеб. пособие/ С. С. Смородинский, Н. В. Батин. Мн.: БГУИР, 2003. - 136 с.

64. Стасенко, Л. А. Использование «жадных» стратегий для решения графовых задач / Л. А. Стасенко // Перспективные информационные технологии и интеллектуальные системы. 2002. - № 3. - С. 88-89.

65. Стешенко, В. Проектирование СБИС. Стили и этапы проекта Электронный ресурс. / В. Стешенко // Компоненты и технологии. 2003. — № 4. — Режим доступа: http://www.compitech.ru/

66. Суворова, Е. А. Проектирование цифровых систем на VHDL / Е. А. Суворова, Ю. Е. Шейнин. СПб.: БХВ-Петербург, 2003. - 576 с.

67. Федотов, Я. Система на кристалле Электронный ресурс. / Я. Федотов, А. Щука//Электронные компоненты. 2001. - №2.- Режим доступа: http://www.elcp.ru/

68. Функционально ориентированные процессоры/ А.И. Водяхо и др.; под ред. В. Б. Смолова — JL: Машиностроение. Ленингр. отд-ние, 1988. 224 с.

69. Харчистов, Б. Ф. Методы оптимизации: учебное пособие / Б. Ф. Харчистов. Таганрог: Изд-во ТРТУ, 2004. - 140 с.

70. Хуторной, С. Система Excalibur средство разработки SoC-решений фирмы ALTERA. Часть 1. Общее описание системы Электронный ресурс. / С. Хуторной // Chip News. - 2001. - № 6. - Режим доступа: http://www.chip-news.ru/

71. Хуторной, С. Система Excalibur- средство разработки SoC-решений фирмы ALTERA. Часть 2. Процессор Nios Электронный ресурс. / С.Хуторной// Chip New. 2001. - №6.- Режим доступа: http://www.chip-news.ru/

72. Чепурин, И. Высокопроизводительные процессоры для встраиваемых систем / И. Чепурин // Электронные компоненты. 2005. - № 2. - С. 63-67.

73. Шишкин, В. В. Выбор оптимального способа реализации функций для функционально распределенной системы обработки данных с использованием нечетко заданных критериев оценки / В. В. Шишкин, В. В. Родионов // Вестник УлГТУ. 2003. - № 1-2.-С. 43-45.

74. Шишкин, В. В. Обзор методов улучшения генетических алгоритмов / В. В. Шишкин, В. В. Родионов; Ульяновский гос. техн. ун-т. Ульяновск, 2002. - 25 е.: ил. - Деп. в ВИНИТИ 06.11.02, № 1914-В2002.

75. Шишкин, В. В. Оптимизация функционально распределенных систем обработки данных: постановка задачи и подходы к ее решению / В. В. Шишкин, В.В.Родионов; Ульяновский гос. техн. ун-т. Ульяновск, 2002.- 21 е.: ил. -Деп. в ВИНИТИ 06.11.02, № 1913-В2002.

76. Шкамардин, И. А. Применение эволюционных методов при решении задач параметрического синтеза схемотехнических решений / И .А. Шкамардин // Перспективные информационные технологии и интеллектуальные системы. 2005. - № 1. - С. 23-28.

77. Юдинцев, В. Программируемые логические устройства. Что нового, что устарело, чего ждать? Электронный ресурс. / В. Юдинцев // Электроника НТБ. 2002. - № 2. - Режим доступа: http://www.electronics.ru/

78. Ющенко, Н. В. Методы оценки времени выполнения последовательных программ на современных процессорах / Н. В. Ющенко // Интеллектуальные многопроцессорные системы: тез. докл. междунар. конф., Таганрог, 1-5 сентября 1999 г. Таганрог: ТРТУ, 1999. - С. 33.

79. A Novel Codesign Approach based on Distributed Virtual Machines / Ch. Kreiner et al. // Hardware/Software Codesign: Proceedings of International Workshop, Estes Park, Colorado, May 6-8, 2002. 2002. - P. 109-114.

80. Bäck, Т. The Interaction of Mutation Rate, Selection, and Self-Adaptation within a Genetic Algoritm / T. Bäck // Parallel Problem Solving from Nature: Proceedings of Workshop, Brussels, Belgium, September 28-30, 1992.- 1992. -P. 85-94.

81. Beasley, D. An Overview of Genetic Algorithms: Part 1, Fundamentals/

82. D. Beasley, D. Bull, R. Martin // University Computing.- 1993.-№ 15 (2).-P. 59-69.

83. Beasley, D. An Overview of Genetic Algorithms: Part 2, Research Topics / D. Beasley, D. Bull, R. Martin // University Computing.- 1993.-№ 17 (4).-P. 170-181.

84. Blickle, T. System-level Synthesis, Using Evolutionary Algorithms Electronic resource. / T. Blickle, J. Teich, L. Thiele // Design Automation for Embedded Systems. 1998. -№ 1, Vol. 3. - Mode of access: ftp://flp.tik.ee.ethz.ch/

85. Cantu-Paz, E. A Survey of Parallel Genetic Algorithms: IlliGAL Report № 97003 Electronic resource. / E. Cantu-Paz- 1997. 29 p. - Mode of access: ftp://ftp-illigal.ge.uiuc.edu/

86. De Jong, K. An Analysis of the Interacting Roles of Population Size and Crossover in Genetic Algorithms / K. De Jong, W. Spears // Parallel Problem Solving from Nature: Proceedings of Workshop, Dortmund, Germany, October 1-3, 1990.-1990.-P. 38-47.

87. Deb, K. Understanding Interactions Among Genetic Algorithm Parameters / K. Deb, S. Agrawal // Foundations of Genetic Algorithms: Proceedings of Workshop, Madison, WI, USA, July 22-25, 1998. 1998. - P. 265-286.

88. Ernst, R. Hardware-Software Cosynthesis for Micro-Controllers / R. Ernst, J. Henkel, Th. Benner // IEEE Design & Test Magazine. 1993. - Vol. 10. - № 4. -P. 64-75.

89. Grattan, B. Codesign-Extended Applications/ B. Grattan, G. Stitt,

90. F. Vahid // Hardware/Software Codesign: Proceedings of International Workshop, Estes Park, Colorado, May 6-8,2002. 2002. - P. 1-6.

91. Gupta, R. K. System-Level Synthesis Using Re-programmable Components / R. K. Gupta, G. D. Micheli // European Design Automation: Proceedings of Conference, Hamburg, Germany, September 7-10, 1992. 1992. - P. 2-7.

92. Hardware/Software Partitioning of Embedded System in OCAPI-xl /

93. G. Vanmeerbeeck et al. // Hardware/Software Codesign: Proceedings of International Workshop, Copenhagen, Denmark, April 25-27, 2001.-2001. P. 30-35.

94. Henkel, J. A Hardware/Software Partitioner Using a Dynamically Determined Granularity / J. Henkel, R. Ernst // Design Automation: Proceedings of Conference, Anaheim, California, June 9-13, 1997. 1997. - P 691-696.

95. Henkel, J. The Interplay of Run-Time Estimation and Granularity in HW/SW Partitioning / J. Henkel, R. Ernst // Hardware/Software Co-Design: Proceedings of International Workshop, Pittsburgh, USA, 1996. 1996. - P. 52-58.

96. Kaplan, A. A Survey of Hardware/Software System Partitioning: Technical Report Electronic resource. / A. Kaplan, M. Sarrafzadeh, R. Kastner. — 2003.15 p. Mode of access: http://www.ece.ucsb.edu/

97. Noguera, J. Dynamic Run-Time HW/SW Scheduling Techniques for Reconfigurable Architectures / J. Noguera, R. Badia // Hardware/Software Codesign: Proceedings of International Workshop, Estes Park, Colorado, May 6-8, 2002. -2002.-P. 205-210.

98. Peng, Z. An Algorithm for Partitioning of Application Specific Systems / Z. Peng, K. Kuchcinski // European Design Automation: Proceedings of Conference, Paris, France, 1993. 1993. - P. 316-321.

99. Tomassini, M. A Survey of Genetic Algorithms / M. Tomassini // Computational Physics III: Annual Reviews. World Scientific, 1995. - P. 87-118.

100. Vahid, F. A Binary-Constraint Search Algorithm for Minimizing Hardware During Hardware-Software Partitioning / F. Vahid, J. Gong, D. Gajski // European Design Automation: Proceedings of Conference, Grenoble, France, September, 1994.-1994.-P. 214-219.

101. Wolf, W. A Decade of Hardware/Software Codesign/ W. Wolf// Computer. 2002. - № 4. - P. 38-43.

102. Zhou, T. A Probabilistic Performance Metric for Real-Time System Design / T. Zhou, X. Hu, E. Sha // Hardware/Software Codesign: Proceedings of International Workshop, Rome, Italy, May 3-5, 1999. 1999. - P. 90-94.