close

Вход

Забыли?

вход по аккаунту

?

АКиТП

код для вставкиСкачать
СОДЕРЖАНИЕ
Введение2
Практическая и математическая постановка задачи4
Анализ существующих алгоритмов решения задачи7
Описание разрабатываемого алгоритма, его укрупненная схема12
Развернутая блок-схема алгоритма13
Решение контрольного примера16
Перечень идентификаторов используемых при написании программы19
Текст программы20
Листинг с результатами машинного решения27
Заключение..................................................................................28
Список литературы29
ВВЕДЕНИЕ
Процесс науки и техники приводит к расширению области применения ЭВМ, предъявляет к ним постоянно растущие требования. Технико-экономические, функциональные и структурные возможности ЭВМ и систем в большей степени определяются конструкцией. Большое число разнообразных требований, которые предъявляются к конструкции, приводит к необходимости исследования нескольких ее вариантов, их сравнительной оценки и выбора оптимального. Следовательно, конструкторское проектирование включает синтез, анализ и оптимизацию конструкции как объекта, в котором реализована электрическая схема ЭВМ. Чтобы повысить эффективность конструкторского проектирования, необходимо разработать формальное описание рангового состава конструкции и типовых сборочных единиц, знать методику их расчета, критерии для оценки соответствия типовых конструкций предъявляемым к ним требования, методы поиска решения.
Процесс создания современных ЭВМ в значительной степени автоматизирован. Внедрение в инженерную практику методов автоматизации проектирования позволяет перейти от традиционного моделирования разрабатываемой аппаратуры к ее моделированию с помощью персональных компьютеров (ПК). С помощью ПК возможно осуществить цикл сквозного проектирования, включающий в себя: синтез структуры и принципиальной схемы устройства; анализ его характеристик в различных режимах, синтез топологии, включая размещение элементов на плате или кристалле и разводку межсоединений; верификацию топологии; выпуск конструкторской документации.
В основу построения современных вычислительных комплексов положен модульный принцип. Он предполагает иерархическое построение ЭВС из модулей, разбитых на нескольких конструктивных уровнях (рис.1).
ЭлементЯчейка (ТЭЗ)ПанельШкафЭВМ К числу основных конструкторских задач для всех уровней конструктивной иерархии относятся:
- компоновка конструктивных модулей;
- размещение модулей низшего конструктивного уровня в монтажном пространстве модуля следующего уровня;
- задача трассировки монтажных соединений;
- получение конструкторской документации;
- задача тестирования аппаратуры.
ПРАКТИЧЕСКАЯ И МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ
Трассировка заключается в определении конкретной геометрии печатного или проводного монтажа, реализующего соединения между элементами схемы. Исходными данными для трассировки являются список цепей, метрические параметры и топологические свойства типовой конструкции и ее элементов и результаты решения задачи размещения, по которым находятся координаты выводов элементов. Формальная постановка задачи трассировки и методы ее решения в значительной степени зависят от вида монтажа (проводной или печатный) и конструктивно-технологических ограничений, определяющих метрические параметры и топологические свойства монтажного пространства.
В типовых конструкциях, начиная с блока и выше, довольно широко используется проводной монтаж, что объясняется высокой трудоемкостью проектирования и сложностью изготовления печатного монтажа. Изготовление печатного монтажа усложняется с увеличением размеров коммутационных плат, а надежность его падает. Проводной монтаж может осуществляться по прямым, соединяющим выводы элементов, или с помощью жгутов, которые прокладывают в специальных каналах. Основные ограничения-количество проводников, которые можно подсоединять к одному выводу (обычно не более трех), и число проводов в каждом жгуте - пропускная способность канала.
Трассировка проводного монтажа заключается в определении порядка соединения выводов в соответствии с принципиальной электрической схемой и с учетом заданных ограничений. Критерием качества, как правило, является минимум суммарной длины соединений. Нахождение порядка соединения выводов элементов внутри цепи сводится к задаче построения на фиксированных вершинах минимального покрывающего или связывающего дерева. Будем использовать модель схемы в виде графа, в котором выводам элементов сопоставлены вершины а на этих вершинах строится полный подграф. Таким образом, каждая цепь представляется отдельной компонентой связности. Необходимо построить минимальные покрывающие деревья на тех компонентах связности, число вершин в которых больше двух. Напомним, что в результате размещения элементов определены координаты их выводов в соответствующей метрике, т. е. вершины компонент связности отображены в граф решетки монтажного пространства.
Расстояние между каждой парой вершин полного подграфа для проводников, идущих по кратчайшему направлению:
для ортогональной трассировки
Здесь Si, ti и Sj, tj - координаты i-й и j-й вершин графа.
На п вершинах можно построить tn = пп-2 различных деревьев. В связи с этим точное решение задачи построения минимального дерева методом полного перебора нецелесообразно. Существуют приближенные алгоритмы решения этой задачи, дающие результаты, достаточно близкие к оптимальным.
Алгоритм Прима использует принцип соединения ближайших вершин, на каждом шаге к строящемуся дереву присоединяется ближайшая изолированная вершина. В алгоритме Прима учтем ограничение на количество линий связи, присоединяемых к каждому выводу. Исходными данными для работы алгоритма являются матрица расстояний Dr = ||djj||nxn элементы которой определяются по (1) или (2), и допустимое количество проводников, подключаемых к выводу mдоп.
Основные пункты алгоритма. 1. Находим минимальный элемент матрицы dq, p = min di,j; i, j = 1, n;i=j. Номера строки и столбца q и р, на пересечении которых он находится, определяют номера вершин, соединяемых ребром.
2. Заносим номера вершин в множество X' = {q,p}, а построенное ребро в множество U' ={Uq,p}.
3. Подсчитываем число ветвей kq и kj, принадлежащих соединяемым на данном шаге вершинам.
4. Проверяем условие kq < mдоп, kp < mдоп. Индексы вершин, для которых это условие не выполняется, заносим в множество X".
5. Находим dr,t - min di,j. Cреди еще не вошедших в дерево вершин находим вершину xi, минимально удаленную от некоторой вершины дерева xr.
6. Дополняем множества X' = X' t; U' = U' ur,t.
7. Проверяем, все ли вершины графа соединены ветвями |U'| = (п- 1).
Если условие выполняется, то переходим к п. 8, иначе - к п. 3.
8. Конец работы алгоритма.
АНАЛИЗ СУЩЕСТВУЮЩИХ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ
Задача трассировки состоит в построении для всех цепей схемы оптимальных монтажных соединений. Метрический аспект задачи предполагает учет конструктивных размеров элементов, соединений и коммутационного поля. Топологический аспект связан с выбором допустимого пространственного расположения отдельных монтажных соединений при ограничениях на число пересечений соединений, число слоев коммутационной схемы и т. п. Классификация методов трассировки представлена на рис. 3.
Алгоритмические методы трассировки печатных соединений существенно зависят от конструкции коммутационного поля и могут быть разделены на две основные группы:
1) топографические методы - в них приоритет отдается метрическому аспекту задачи;
2) графо-теоретические методы решения задач трассировки.
Топографический метод трассировки содержит следующие этапы:
1) получение списка соединений;
2) распределение соединений по слоям;
3) определение порядка прокладки соединений;
4) трассировка отдельных соединений.
Основной задачей первого этапа является предварительное определение порядка соединений выводов внутри отдельных цепей. Такое упорядочение осуществляется с помощью алгоритмов построения минимальных деревьев. При печатном монтаже соединения могут выполняться не только по выводам, но и в любой точке проводника. Поэтому построение КСД формулируется как задача Штейнера. Метод же решения задачи Штейнера требует больших затрат машинного времени.
На втором и третьем этапе решаются вопросы, на каком из слоев будет осуществляться трассировка соединений и в каком порядке. Некоторые методы расслоения основаны на анализе взаимного расположения выводов отдельных цепей, другие - на анализе совмещенной в одной плоскости топологии всех соединений, полученной с помощью применения алгоритма построения минимального дерева независимо для каждой отдельной цепи.
При последовательной трассировке отдельных соединений порядок их прокладки должен быть определен заранее. Существуют различные тактики упорядочения соединений, однако ни одна из них не может считаться вполне удовлетворительной. В связи с этим более предпочтительны динамические процессы трассировки, когда производится перетрассировка неудачно проложенных соединений или порядок прокладки определяется в зависимости от ситуации, сложившейся на ранних этапах процесса. Но использование динамических процессов трассировки должно опираться на быстрое осуществление прокладки отдельных соединений.
Для трассировки отдельных соединений предложены разные алгоритмы, различающиеся скоростью и требуемым объемом памяти при реализации на ЭВМ, а также качеством получаемого результата. Основными из них являются:
1) волновой алгоритм и его модификации;
2) алгоритмы трассировки по магистралям и каналам;
3) комбинированные алгоритмы.
Эффективность применения каждого из алгоритмов определяется рядом факторов: конструкцией коммутационного поля, ресурсами машинного времени и памяти ЭВМ, сложностью схемы соединений и другие.
Несмотря на то что волновой алгоритм был предложен Ли еще в 1961 г., он и по сей день в том или ином виде широко используется при трассировке печатных соединений. Это связано с универсальностью алгоритма и возможностью его применения для трассировки коммутационных плат различных типов.
Реализация волнового алгоритма предполагает введение дискретного рабочего поля (ДРП), являющегося моделью коммутационной платы для отображения в памяти ЭВМ. В связи с этим был предложен ряд способов эффективного сокращения объема информации при отображении процесса трассировки и его результатов в памяти ЭВМ.
Другое направление повышения эффективности алгоритма связано с увеличением средней скорости распространения волны при поиске трассы соединения. Сюда относятся такие приемы, как ограничение области распространения волны, использование метода встречной волны, задание преимущественного направления волны и др. Исследованы вопросы применения волнового алгоритма для оптимизации соединения по совокупности параметров (длине, числу пересечений, числу поворотов и т. д.), для трассировки многоконцевых и многослойных соединений.
Основными недостатками различных модификаций волнового алгоритма являются значительные затраты времени и памяти для представления ДРП, особенно ДРП больших размеров. В связи с этим определенный интерес представляют новые модификации алгоритма.
Повышение скорости трассировки может быть достигнуто при организации процесса прокладки соединений по магистралям. Так как конфигурации подавляющего числа реальных соединений, имеют простой вид, это приводит к сокращению затрат времени на трассировку соединений, особенно на слабо заполненном коммутационном поле. По мере заполнения поля эффективность алгоритма уменьшается и начинает приближаться к эффективности волнового алгоритма. Основным достоинством алгоритма является отсутствие ДРП, что снижает требования к объему памяти при реализации данного алгоритма.
К этой же группе примыкают эвристические алгоритмы построения малоповоротных путей, в которых осуществляется построение соединений простой конфигурации (до 3-4 изгибов). По имеющимся данным, подобные алгоритмы позволяют осуществить разводку до 90% всех соединений в двухслойных схемах с ортогональными соединениями. Остальные соединения трассируются с помощью волнового алгоритма.
Алгоритмы трассировки по каналам применяются в случае, когда на коммутационном поле естественным образом могут быть выделены горизонтальные и вертикальные каналы для реализации соединений. Каналы образуются между рядами регулярно расположенных на поле элементов или определяются сетью фиксированных металлизированных переходных отверстий. Наиболее эффективная стратегия трассировки в данном случае включает два этапа: распределение соединений по каналам и трассировку внутри каналов. Разновидностью трассировки по каналам является трассировка на сети укрупненных ячеек (граней), образованных на коммутационном поле между разногабаритными элементами. Основные достоинства канальной трассировки - отсутствие ДРП, возможность планирования плотности соединений на отдельных областях коммутационного поля, большая скорость построения соединений.
В ряде конструкций электронных схем параметры размещения элементов и конфигурации трасс соединений сильно взаимосвязаны, и потому расчленение общей задачи проектирования топологии схемы на два традиционных этапа: размещение элементов и трассировку соединений - неоправданно. Характерными особенностями таких конструкций являются нерегулярность расположения элементов и соединений, их разнотипность, наличие одного слоя коммутации. Примерами могут служить односторонние печатные платы с микросхемами и навесными радиодеталями, гибридные микросхемы и биполярные интегральные схемы с одним слоем коммутации.
В последнее время проводятся интенсивные исследования по применению теоретико-графовых методов к конструированию топологии схем подобного рода, поскольку другие методы трассировки в этом случае оказываются малоэффективными. Теоретико-графовый метод предполагает предварительный анализ планарности схемы, представленной в виде графовой модели, и последующую ликвидацию имеющихся пересечений с помощью возможных технологических приемов. Заключительная фаза состоит в построении эскиза топологии схемы при рациональном распределении функций между конструктором и ЭВМ.
Для проводного монтажа трассировка осуществляется с помощью алгоритмов построения минимальных деревьев соединений. Для этого используются следующие методы: алгоритм Краскала, Лобермана, Уэйнберга и алгоритм Прима. Наиболее эффективен с точки зрения реализации на ЭВМ алгоритм Прима. Он предполагает последовательное выполнение следующих принципов: всякая изолированная вершина соединяется с ближайшей; всякий изолированный фрагмент соединяется с ближайшей вершиной кратчайшим ребром. Минимальное дерево построенное по данному алгоритму обладает тем свойством, что степень любой вершине не превышает 6. ОПИСАНИЕ РАЗРАБАТЫВАЕМОГО АЛГОРИТМА, ЕГО УКРУПНЕННАЯ СХЕМА
РАЗВЕРНУТАЯ БЛОК-СХЕМА АЛГОРИТМА
Развернутая блок схема нахождения кратчайшего пути представлена (TForm1.Button2Click) на рис. 5.
Процедура (breef) записи из полей в массив
Процедура(put) вычеркивания столбца и вывод дерева. Процедура (find) поиск минимального элемента в строке.
РЕШЕНИЕ КОНТРОЛЬНОГО ПРИМЕРА
Матрица расстояний D (n=16)
045971212813610121416111540357101249468101291153044793877791112109540257549955714877420557611117791610121075502103141410841913121297520125161612106211584357101207444689713984635701111753151064791114164110468105910679111416411404610551287571012476402693141095781065862041151612117946831010640159119121416192191555911150615111081013157109535960
Множество выбранных вершин UРебро (u,v)Множество невыбранных вершин V \ U{}{}{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}{1}(1,2)=4
(1,3)=5
(1,4)=9
(1,5)=7
(1,6)=12
(1,7)=12
(1,8)=8
(1,9)=13
(1,10)=6
(1,11)=10
(1,12)=12
(1,13)=14
(1,14)=16
(1,15)=11
(1,16)=15
{2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}{1,2}(1,3)=5
(1,4)=9
(1,5)=7
(1,6)=12
(1,7)=12
(1,8)=8
(1,9)=13
(1,10)=6
(1,11)=10
(1,12)=12
(1,13)=14
(1,14)=16
(1,15)=11
(1,16)=15
(2,3)=3
(2,4)=5
(2,5)=7
(2,6)=10
(2,7)=12
(2,8)=4
(2,9)=9
(2,10)=4
(2,11)=6
(2,12)=8
(2,13)=10
(2,14)=12
(2,15)=9
(2,16)=11{3,4,5,6,7,8,9,10,11,12,13,14,15,16}Далее действия пункта 2 опустим, будем приводить только результат{1,2,3}(3,8)=3{4,5,6,7,8,9,10,11,12,13,14,15,16}{1,2,3,8}(2,10)=4{4,5,6,7,9,10,11,12,13,14,15,16}{1,2,3,8,10}(8,11)=4{4,5,6,7,9,11,12,13,14,15,16}{1,2,3,8,10,11}(4,12)=4{4,5,6,7,9,12,13,14,15,16}{1,2,3,8,10,11,12}(12,13)=2{4,5,6,7,9,13,14,15,16}{1,2,3,8,10,11,12,13}(13,14)=4{4,5,6,7,9,14,15,16}{1,2,3,8,10,11,12,13,14}(14,9)=3{4,5,6,7,9,15,16}{1,2,3,8,10,11,12,13,14,9}(9,6)=3{4,5,6,7,15,16}{1,2,3,8,10,11,12,13,14,9,6}(6,7)=2{4,5,7,15,16}{1,2,3,8,10,11,12,13,14,9,6,7}(6,5)=5{4,5,15,16}{1,2,3,8,10,11,12,13,14,9,6,7,5}(5,4)=2{4,15,16}{1,2,3,8,10,11,12,13,14,9,6,7,5,4}(12,16)=3{15,16}{1,2,3,8,10,11,12,13,14,9,6,7,5,4,16}(10,15)=6{15}{1,2,3,8,10,11,12,13,14,9,6,7,5,4,16,15}{}
ПЕРЕЧЕНЬ ИДЕНТИФИКАТОРОВ ИСПОЛЬЗУЕМЫХ ПРИ НАПИСАНИИ ПРОГРАММЫ
ИмяТипОписаниеStringGrid1.RowCountintegerЧисло ячеек по вертикалиStringGrid1.ColCountintegerЧисло ячеек по горизонталиexarray[0..20] of integerМассив хранящий кратчайший путьmasarray[0..20,0..20] of integerМассив, хранящий ячейки findintegerНомер смежной вершины с минимальным путемbintegerРазмерность матрицы cintegerМинимальный путь до смежной вершины
ТЕКСТ ПРОГРАММЫ
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, Grids, StdCtrls, ComCtrls , unit2;
const
MaxMyArray=20;
type
TValue=Integer;
TLValue=Double;
TMyArray=array [0 .. MaxMyArray - 1, 0 .. MaxMyArray - 1] of TValue;
TIndex=array[0 .. MaxMyArray - 1] of integer;
TForm1 = class(TForm)
Button1: TButton;
Button2: TButton;
Button3: TButton;
GroupBox1: TGroupBox;
Edit1: TEdit;
Label1: TLabel;
StringGrid1: TStringGrid;
Button4: TButton;
OpenDialog1: TOpenDialog;
procedure Edit1KeyUp(Sender: TObject; var Key: Word;
Shift: TShiftState);
procedure Button1Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Button4Click(Sender: TObject);
private
X: integer;
procedure breef;
procedure final;
procedure put(a:integer);
function find(a:integer):integer;
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
mas: array[0..20,0..20] of integer;
ex: array[0..20] of integer;
exc,col: integer;
implementation
{$R *.dfm}
procedure TForm1.Edit1KeyUp(Sender: TObject; var Key: Word;
Shift: TShiftState);
var
b: integer;
begin
If Edit1.Text='' then Edit1.Text:='0';
b:=StrToInt(Edit1.Text);
StringGrid1.ColCount:=b;
StringGrid1.RowCount:=b;
end;
procedure TForm1.Button1Click(Sender: TObject);
var
i,j: integer;
begin
Edit1.Text:='0';
For i:=0 to stringgrid1.ColCount-1 do
For j:=0 to stringgrid1.RowCount-1 do
StringGrid1.Cells[i,j]:='';
StringGrid1.ColCount:=1;
StringGrid1.RowCount:=1;
end;
procedure TForm1.Button3Click(Sender: TObject);
var
n,i,j:integer;
begin
Halt; // 8)
end;
procedure TForm1.breef;
var
i,j: integer;
begin
For i:=0 to Col-1 do
For j:=0 to Col-1 do
begin
mas[i,j]:=Strtoint(Stringgrid1.cells[i,j]);
if i=j then mas[i,j]:=999;
end;
end;
procedure TForm1.put(a:integer);
var
j:integer;
begin
inc(exc);
ex[exc-1]:=a;
Form2.Label1.Caption:=Form2.Label1.Caption+' - X'+inttostr(a);
For j:=0 to Col-1 do
mas[a-1,j]:=999;
end;
function TForm1.find(a:integer):integer;
var
c,i:integer;
begin
c:=mas[0,a-1];
find:=0+1;
For i:=1 to Col-1 do
If mas[i,a-1]<c then begin c:=mas[i,a-1]; find:=i+1; end;
end;
procedure TForm1.final;
var
i,j:integer;
begin
// For i:=0 to Col-1 do
// For j:=0 to Col-1 do
// Stringgrid1.cells[i,j]:='';
Form2.Label1.Caption:=Form2.Label1.Caption+' ';
Form2.Visible:=true;
end;
procedure TForm1.Button2Click(Sender: TObject);
var
el,q:integer;
begin
col:=StringGrid1.RowCount;
exc:=0;
breef;
el:=1;
For q:=2 to stringgrid1.RowCount do
begin
put(el);
el:=find(el);
end;
put(el);
final;
end;
procedure TForm1.Button4Click(Sender: TObject);
var
C: TMyArray;
F: TextFile;
E,i, j: integer;
begin
if(OpenDialog1.Execute)
then begin
try
StringGrid1.ColCount := 0;
StringGrid1.RowCount := 0;
AssignFile(F, OpenDialog1.FileName);
Reset(F);
Read(F, X);
StringGrid1.ColCount := X;
StringGrid1.RowCount := X;
for i := 0 to X - 1 do begin
for j := 0 to X - 1 do begin
Read(F, E); C[i, j]:= E;
StringGrid1.Cells[j,i] := IntToStr(C[i, j]);
end;
end;
CloseFile(F); except
// В случае ошибки подить звуковой сигнал
MessageBeep(MB_ICONHAND);
// Вывести сообщение об ошибке
MessageDlg('Ошибка!', mtError, [MBOK], MB_ICONHAND);
end;
end;
end;
end.
Подключаемый модуль.
unit Unit2;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TForm2 = class(TForm)
Button1: TButton;
Label1: TLabel;
procedure Button1Click(Sender: TObject);
procedure FormShow(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form2: TForm2;
a:string;
implementation
{$R *.dfm}
procedure TForm2.Button1Click(Sender: TObject);
begin
Form2.Visible:=false;
Label1.Caption:='';
end;
procedure TForm2.FormShow(Sender: TObject);
begin
a:=label1.Caption;
end;
end.
ЛИСТИНГ С РЕЗУЛЬТАТАМИ МАШИННОГО РЕШЕНИЯ
ЗАКЛЮЧЕНИЕ
В результате выполнения курсового проекта была создана программа, выполняющая трассировку проводного монтажа алгоритмом Прима. Программа была написана с использованием среды разработки Delphi 7 и сконфигурирована для работы под управлением операционных систем семейства Microsoft Windows.
Тестирование программы во всех доступных режимах показало ее полную работоспособность. Результаты работы программы и ручного просчета совпали.
Применение данного алгоритма дает возможность трассировки проводного монтажа, при этом данный алгоритм не требует значительных системных ресурсов (например, ресурсов памяти).
СПИСОК ЛИТЕРАТУРЫ
1. Селютин В.А. "Машинное конструирование электронных устройств", М., 1977г.
2. Савельев А.Я., Овчинников В.А. и др. "Конструирование ЭВМ и систем", М: Высш, шк, 1984
3. Конспект лекций.
29
Документ
Категория
Рефераты
Просмотров
101
Размер файла
640 Кб
Теги
акитп
1/--страниц
Пожаловаться на содержимое документа