Оптимальное размещение компонентов на интегральных схемах
Минимизация выпуклой квадратичной функции при общих квадратичных и линейных ограничениях. Современные электронные устройства самых различных сфер применения. Ограничение в математической модели расположения компонентов на схеме условие непересечения.
| Рубрика | Математика |
| Вид | реферат |
| Язык | русский |
| Дата добавления | 14.06.2017 |
| Размер файла | 79,2 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Оптимальное размещение компонентов на интегральных схемах
В современных электронных устройствах самых различных сфер применения, начиная от бытовых приборов, компьютеров и заканчивая сложными научными электроприборами, сложно найти прибор, в котором бы не применялись интегральные схемы. Иногда одна микросхема выполняет практически все функции в электронном приборе. Микросхема объединяет в себе электронную схему, где все элементы (транзисторы, диоды, резисторы, конденсаторы) и электрические связи между ними конструктивно выполнены на одном кристалле. Поскольку размеры отдельных компонентов очень малы (микро- и нанометры), то на одном кристалле при современном развитии технологий, можно поместить более миллиона электронных компонентов. Наряду с поиском новых материалов для интегральных схем существует проблема оптимального размещения компонентов на ней.
Интегральную схему будем представлять в виде некоторой прямоугольной пластины, а компоненты, которые размещаются на ней - прямоугольниками. Компоненты связаны между собой. Эти связи можно представить графом G(N, V), вершины которого соответствуют компонентам, а дуги соединениям. Здесь N - множество вершин, равное количеству компонентов на схеме, а V - множество его дуг, равное количеству соединений между компонентами. Быстродействие интегральной схемы зависит от длины соединений, поэтому в качестве критерия расположения компонентов на схеме выберем суммарную длину соединений.
Обычно компонент схемы можно представить некоторым прямоугольником, который располагается на схеме таким образом, что его стороны параллельны сторонам схемы. Будем представлять прямоугольники в виде объединения квадратов c координатами (xi, yi). Тогда, если первый прямоугольник, например, состоит из четырех равных квадратов расположенных в линию, то должны выполняться следующие условия
Если же эти четыре квадрата образуют новый квадрат, то это однозначно задается условиями
где a1 - сторона каждого квадрата. Заметим, что для данного квадрата полученные квадратичные условия можно заменить линейными.
Одним из ограничений в математической модели оптимального расположения компонентов на схеме будет условие непересечения компонентов. Достаточным условием непересечения компонентов является следующая система квадратичных неравенств
где ai - сторона i-го квадрата.
Каждый компонент схемы должен полностью располагаться на схеме. Это определяется следующими неравенствами
где (p, q) - стороны схемы.
Целевая функция для этой задачи запишем в виде
Часть приведенных ограничений будут избыточными. Это зависит от набора компонент. квадратичный электронный математический
В данной постановке решение задачи заключается в минимизации выпуклой квадратичной функции при общих квадратичных и линейных ограничениях. Такая задача является многоэкстремальной.
Рассмотрим частный случай этой задачи, когда прямоугольные компоненты можно представить линейной последовательностью квадратов. В этом случае, квадратичными ограничениями будут только условия непересечения компонентов. Запишем эти условия в виде
.
Используем точную квадратичную регуляризацию для преобразования данной задачи к виду
(1)
где z = (x, y, z1), |z| = |x1|+…+|xn|+|y1|+…+|yn|+|z1|, параметр r > 0 выбирается таким, чтобы допустимое множество задачи (1) было выпуклое. Линейные условия Ax = b задают принадлежность квадратов компонентам. Значение параметра s удовлетворяет условию
где (x*, y*) - искомое решение задачи.
В задаче (1) необходимо найти минимальное значение d, при котором ее решение удовлетворяет условию r|z| = d с заданной точностью. Такое значение d находим методом дихотомии.
При фиксированном значении d задача (1) будет выпуклой, однако ее функции являются негладкими. Для решения задачи (1) при фиксированном значении dиспользовался метод последовательного раскрытия модулей [1]. Проведенные численные методы показали, что предлагаемый метод решения данного класса задач является эффективным.
Список использованных источников
1. Косолап А. И. Методы глобальной оптимизации / А. И. Косолап. - Днепропетровск : Наука и образование, 2013. - 316 с.
Размещено на Allbest.ru
...Подобные документы
Исследование видов квадратичных форм и способов приведения квадратичных форм к каноническому виду. Сфера применения и особенности данного вида уравнений: определения и доказательство основных теорем, алгоритм решения ряда задач по данной тематике.
контрольная работа [286,0 K], добавлен 29.03.2012Предикатное представление условий непересечения многоугольников. Алгоритм непересечения многоугольника и полосы. Определение направления обхода вершин многоугольника. Решение систем линейных алгебраических уравнений. Построение интерактивной оболочки.
дипломная работа [800,2 K], добавлен 10.11.2012Проектирование математической модели. Описание игры в крестики-нолики. Модель логической игры на основе булевой алгебры. Цифровые электронные устройства и разработка их математической модели. Игровой пульт, игровой контроллер, строка игрового поля.
курсовая работа [128,6 K], добавлен 28.06.2011Фундаментальные понятия теории квадратичных форм. Линейные, квадратичные и билинейные функционалы. Приведение квадратичной формы к каноническому виду. Классификация комплексных квадратичных функционалов. Определенные вещественные квадратичные функционалы.
контрольная работа [378,5 K], добавлен 24.08.2015Матричный метод решения систем линейных алгебраических уравнений с ненулевым определителем. Примеры вычисления определителя матрицы. Блок-схема программы, описание объектов. Графический интерфейс, представляющий собой стандартный набор компонентов Delphi.
курсовая работа [1,4 M], добавлен 29.06.2014Многие переменные, минимизация их функций. Точки максимума и минимума называются точками экстремума функции. Условия существования экстремумов функции многих переменных. Квадратичная форма, принимающая, как положительные, так и отрицательные значения.
реферат [70,2 K], добавлен 05.09.2010Определение МДНФ логической функции устройства различными методами (Квайна, Петрика, неопределенных коэффициентов и др.). Составление алгоритма метода минимизации функции и разработка его рабочих программ. Выполнение синтеза схемы логического устройства.
курсовая работа [60,2 K], добавлен 21.11.2010Создание математической модели движения шарика, подброшенного вертикально вверх, от начала падения до удара о землю. Компьютерная реализация математической модели в среде электронных таблиц. Определение влияния изменения скорости на дальность падения.
контрольная работа [1,7 M], добавлен 09.03.2016Структура и элементы, принципы формирования и правила разрешения систем линейных алгебраических уравнений. История развития различных методов решения: матричного, Крамера, с помощью функции Find. Особенности применения возможностей программы Mathcad.
контрольная работа [96,0 K], добавлен 09.03.2016Понятие квадратичной формы и способы ее записи. Действительные и недействительные, вырожденные и невырожденные формы, ранг матрицы. Знакоопределенность квадратичных форм, определение ее миноров. Критерии положительной и отрицательной определенностей.
контрольная работа [41,2 K], добавлен 03.08.2010Систематизация сведений о линейных и квадратичных зависимостях и связанных с ними уравнениях и неравенствах. Выделение полного квадрата, как метод решения некоторых нестандартных задач. Свойства функции |х|. Уравнения и неравенства, содержащие модули.
дипломная работа [3,0 M], добавлен 25.06.2010Уравнения, системы линейных, квадратных и третьей степени уравнений. Уравнения высших степеней сводящиеся к квадратным. Системы уравнений, три переменные. График квадратичной функции, пределы, производные. Интегральное счисление и примеры решения задач.
шпаргалка [129,6 K], добавлен 22.06.2008Уравнения Фредгольма и их свойства как классический пример интегральных уравнений с постоянными пределами интегрирования, их формы и степени, порядок формирования и решения. Некоторые приложения интегральных уравнений. Общая схема метода квадратур.
курсовая работа [97,2 K], добавлен 25.11.2011Аналитические свойства интегральных преобразований. Интеграл Коши на различных кривых. Аналитическая зависимость от параметра. Существование производных всех порядков у аналитической функции. Вывод формулы Коши и формулировка следствий из данной формулы.
курсовая работа [260,2 K], добавлен 10.04.2011Понятие и классификация кривых Безье, их разновидности и методика, основные этапы построения. Порядок и условия применения данных кривых в компьютерной графике. Преобразование квадратичных кривых в кубические. Финитные функции. В-сплайны Шёнберга.
реферат [456,6 K], добавлен 14.01.2011Основные способы приведения квадратичных форм к каноническому виду. Выделение полных квадратов по стандартной схеме метода Лагранжа. Запись матрицы перехода. Линейное и невырожденное преобразование координат. Метод ортогональных преобразований.
лекция [362,9 K], добавлен 05.09.2013Построение квадратичных двумерных стационарных систем с заданными интегралами. Выражение коэффициентов интегралов через коэффициенты системы, связь последних между собой тремя соотношениями. Необходимые и достаточные условия существования у системы.
дипломная работа [480,0 K], добавлен 07.09.2009Отражение посредством математической функции связи между какими-либо значениями. Представление числовых функций на рисунках в виде графиков. Особенности алгебраической функции и многочленов. Практическое применение линейных и квадратических функций.
презентация [251,3 K], добавлен 07.10.2014Общий вид системы линейных уравнений и ее основные понятия. Правило Крамера и особенности его применения в системе уравнений. Метод Гаусса решения общей системы линейных уравнений. Использование критерия совместности общей системы линейных уравнений.
контрольная работа [35,1 K], добавлен 24.06.2009Вычисление определителя, алгебраических дополнений. Выполнение действий над матрицами. Решение систем линейных уравнений по формулам Крамера, методом Гауса. Определение плана выпуска химикатов на заводе. Составление экономико-математической модели задачи.
контрольная работа [184,8 K], добавлен 25.03.2014
