Назначение и область применения устройства - Проектирование платы устройства управления вентиляторами компьютера через порт

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

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

В общем виде задача размещения может быть сформулирована следующим образом: в монтажном пространстве задана область, которая разбивается на множество позиций (посадочных мест) P={p1, ..., pq}, число которых должно быть не меньше числа размещаемых элементов. Очевидно, что каждый элемент может занимать не более одного посадочного места, расстояние между которыми описывается симметричной матрицей расстояний D=|di, j|. Имеющееся множество элементов X={x1, x2, ..., xn}, связанных между собой множеством электрических цепей Е={е1, е2, ..., еm}, представлены в виде графа G=(X, E) на рисунке 1. Необходимо таким образом отобразить на множестве P, чтобы обеспечился экстремум целевой функции качества размещения.

E12 E25

E15

E13 E24 E45 E56

E34

E46

Рисунок 1 - граф G

Исходными данными при решении задачи размещения являются прямоугольная конструкция (ячейка, кристалл, панель), число элементов, которое получено в результате компоновки, т. е. разбиение графа схемы на части, и граф схемы соединений элементов или его матричный (списковый) эквивалент. На прямоугольную конструкцию накладывается декартова система координат с осями s и t, определяющая граф Gr, представляющий собой координатную решетку. Расстояние di, j между узлами i и j этого графа описывается выражением:

Di, j=|si-sj|+| ti-tj|

Где si, sj и ti, tj--координаты вершин xi, xj Є X.

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

G=(X, Е)

В решетку Gr представленной на рисунке 2, таким образом, чтобы вершины множества X размещались в узлах решетки и, например, суммарная длина были наименьшими для возможных способов отождествления вершин графа и узлов решетки:

Где ci, j--вес ребра.

t

1

0

S

1 2

Рисунок 2 - Отображение графа G в Gr

Для подсчета суммарной длины L(G) ребер графа

G=(X, E),

Отображенного в решетку Gr, введем понятие матрицы геометрии Dг.

Матрица геометрии Dг представляет собой часть матрицы расстояний D, в которой исключены элементы di, j, если вершины xi, xj Є X не смежны в графе G.

Для построения матрицы геометрии Dг графа G необходимо каждый элемент матрицы D умножить на соответствующий элемент матрицы смежности R:

Dг=|ri, j, di, j|

Квадратная таблица

R=|ri, j|

Называется матрицей смежности, если ее элементы образуются по правилу

Ri, j=

Алгоритмы квадратичного назначения

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

R=(r1,r2,...,rn)

и множество связей между ними

V=(v1,v2,...,vp),

а также множество установочных мест на плате

T=(t1,t2,...,tk).

Без потери общности будем считать, что n=k. Взаимное расположение элементов на плате можно описать матрицей расстояний D=|df g|, где df g -- расстояние между позициями tf и tg (f, g =1, 2, ...,k). Произвольное размещение конструктивных элементов на позициях множества T представляет собой некоторую перестановку ш, заданную на множестве натуральных чисел

ш={ш(1), ш(2), ..., ш(k)},

где элемент перестановки ш(i) определяет номер позиции, присвоенной ri.

Геометрически в

к2 - мерном пространстве перестановка ш отображается точкой. Каждая точка соответствует матрица ш=|шi j|, в которой

Шi j=

Следовательно, в матрице ш только один элемент в каждой строке и столбце может быть отличен от нуля и равен единице (данный элемент шi j соответствует установке ri и tj), т. е.

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

Т. е к задаче квадратичного назначения.

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

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

1 Назначение и область применения устройства

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

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

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

Похожие статьи




Назначение и область применения устройства - Проектирование платы устройства управления вентиляторами компьютера через порт

Предыдущая | Следующая