Файл: kursovaya_2014Optimizatsia.doc

Пусть исходная схема представляется мультиграфом ; здесь множество вершин V соответствует множеству конструктивных модулей, а множество ребер R — связям между ними. Требуется разрезать (разбить) граф на n частей , … , c N_i , i =1,n, вершинами в каждой части так, чтобы число ребер, соединяющих вершины различных частей, было минимальным, т. Е. критерий оптимальности имеет вид:

(1.3.1)

где — мощность множества ребер , инцидентных частям и .

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

1. Число вершин в каждой части должно быть задано, т. е.

(1.3.2)

2. Одна вершина должна принадлежать лишь одной части, т. е.

(1.3.3)

3. Объединение всех частей должно быть равно исходному графу, т. е.

(1.3.4)

4. Максимально допустимое число внешних связей каждой части не должно превышать допустимой величины S_i:

. (1.3.5)

5. Раздельная компоновка отдельных вершин υ_к в различных частях графа:

. (1.3.6)

---

6. Некоторые вершины υ_р, υ_q должны быть жестко закреплены за определенными частями V_hV_j. Такие вершины называются закрепленными, т. Е.

. (1.3.7)

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

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

Обычно задача размещения формулируется как задача оптимизации. Исходными данными для решения задачи являются: множество конструктивных элементов, множество связей между ними и множество установочных мест (позиций) на коммутационной плате причем . Указываются конфигурация монтажного пространства, ограничения на расположение отдельных элементов по установочным местам и друг относительно друга, а также на тепловой и электрический режимы платы (блока). Схема соединений элементов может задаваться графом , матрицей цепей или списком. Кроме того, задается целевая функция Q. Наиболее часто в задачах размещения минимизируется суммарная длина соединений

---

(1.3.8)

суммарное число внутрисхемных пересечений

(1.3.9)

а также число соединений, длина которых превышает задаваемую величину l₃,

, (1.3.10)

где l_i — расстояние между i-м и j-м установочными местами, в которых расположены соответствующие конструктивные элементы;

— расстояния превышающие l₃;

— число кратных связей (ребер графа G), соединяющих элементы в i-м и j-м установочных местах;

p(r_ij) — число пересечений ребра r_ij графа G.

При размещении элементов на плоскости расстояние определяется по приближенной формуле

или точной

где x_i , y_i— координаты i-ой установочной позиции.

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

, (1.3.11)

где c_i — весовой коэффициент, учитывающий важность j-гo критерия.

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

---

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

Математически задача трассировки элементов проводящего рисунка на ПП формулируется следующим образом. На коммутационной поверхности задано координатами (х, у) множество конструктивных элементов . Выводы (контакты) этих элементов образуют некоторое множество из L связанных подмножеств, , причем каждое подмножество C_l объединяет N_l выводов конструктивных элементов из множества Z в соответствии с электрической принципиальной схемой. Кроме того, заданы расположение групп контактных площадок разъемов и монтажных отверстий, а также ряд требований, предъявляемых к топологии платы: минимальная ширина проводников и зазора между ними, размеры контактных площадок, число слоев металлизации и способы перехода с одного слоя на другой и т. п. Требуется, с учетом заданных конструкторско-технологических ограничений соединить выводы конструктивных элементов внутри каждого подмножества так, чтобы выбранный критерий качества Q печатного монтажа достигал экстремального значения.

На практике при оптимизации топологии печатного монтажа часто используют следующие критерии качества:

1) минимум суммарной длины всех соединений;

2) минимум числа пересечений проводников;

3) равномерность распределения трасс на печатной плате;

4) минимальная протяженность параллельных участков соседних трасс;

5) минимум числа изгибов проводников;

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

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

---

2 Практическая часть

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

---