Управляющий граф алгоритма

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

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

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

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

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

Оценка вычислительной и емкостной сложности требует информации о:

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

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

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

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

1. Операторы преобразования данных, их типы, реализуемые ф-ции, вычислительная сложность их реализации.

2. Операторы вычисления условий, предикаты, реализующие проверку условий и вычислительная сложность этой проверки.

3. Управляющие связи между операциями с учетом отношений следования, а для альтернативных передач управления - соответствующие им значения предшествующих условий и вероятности реализации этих передач.

4. Исходные, промежуточные и окончательные данные, их вид, размерности и если заданы - их структуры, т.е. организация этих данных.

5. Связи «данные-операторы» и наоборот, их типы, определяющие вычислительную сложность чтения/записи данных для заданных структур.

6. связи «данные-данные», позволяющие решать вопрос об их независимости. Это важно для выполнения оптимизирующих преобразований и др.

 

Модель класса алгоритмов в виде управляющего графа.

Такая модель должна отражать события (операции) обработки данных, связи между этими событиями, типы операторов обработки данных и, если известно – их вычислительную сложность. В данной модели не отражены конкретные наборы данных, функциональная зависимость, а так же предикаты, реализующие проверку условий. Модель несет информацию необходимую для изучения св-в определенного класса алгоритмов. Рассмотрим переход к управляющему графу алгоритма на примере 2-х подпрограмм: вычисление кол-ва букв «а», определения min элемента одномерного массива.

Кроме структуры алгоритма класс определяет базис В. В={ Dв, Fв, Рв, Ов} Dв – символы переменных обл-ти определения класса алгоритма. Fв – символы ф-ций (в т.ч. логических), Рв – символы предикатов, реализующие проверку условий. Ов - символы операторов.

Управляющим называется граф с двумя выделенными вершинами p₀ и q₀. Управляющий граф называется правильным, если любая его вершина принадлежит пути из p₀ в q₀.

Переход от алгоритма к управляющему графу выполняется следующим образом:

1. Множеству операторов О поставим в соответствие множество Х, О<->X.

2. Тип t или вычислительную сложность оператора отобразим в модели, задав однозначное отображение R₁ множества Х на множество Т: X R₁ T, t Т

3. Символы множеств Fв и Рв отобразим в модели, задав однозначные отображения мн-ва Х’ вершин обработки данных и Х’’ вершин вычисления условий и передачи управления.

Х’<-> O’: Х’ R2 Fв

Х’’<->O’’: Х’’ R3 Pв

4. Управляющие связи С между операторами o_i и o_j, т.е. с_к(o_i, o_j) С с учетом отношения следования поставим во взаимно однозначное соответствие дугам Uк(x_i, x_j), т.е. с_к(o_i, o_j) Uк(x_i, x_j)

Uк(x_i, x_j) U Uк(x_j, x_i) U

Множество дуг U распадается на два подм-ва: U’ –альтернативная передача управления и U’’ – безусловная передача управления. U= U’ U’’, U’ U’’= .

5. Мн-ву дуг U’ присвоим веса из мн-ва L={true, false}и мн-ва Е –вероятностей этих передач управления

U’ Q2 E

U’ Q1 L.

 

Т.о. мы получили модель класса алгоритмов с взвешенными вершинами и частично взвешенными ребрами. Gy{<X,<T, Fв, Pв> >, <U’<L,E>>, U’’}

 

30. Граф «оператор - данные».

2 моделью алгоритма следует рассматривать двудольный граф, отображающий отношение данные-операторы и наоборот, т.к. отношение данные-данные можно определить по данному графу через прямые/обратные отображения вершин => граф отображения будет двудольным.

Вершины y сопоставлены символам переменных из области определения алгоритма.

 

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

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

Монтажное пространство конструктивных модулей средств ЭВТ обычно имеет прямоугольную форму. Для типовой конструкции, начиная с субблока и выше, характерно регулярное монтажное пространство, которое в наибольшей степени удовлетворяет требованию конструктивно-технологической унификации. Позиции установки типовых конструкций предыдущего ранга фиксированы и имеют постоянный шаг. При разработке топологии ИС и БИС и проектировании субблока на разногабаритных элементах нельзя заранее зафиксировать позиции для размещения элементов. Монтажное пространство в этом случае является нерегулярным. В качестве математической модели монтажного пространства используется неориентированный граф решетки Gr. Каждую плоскость монтажного пространства разбивают на элементарные площадки, стороны которых равны шагу проложения проводника по соответствующему направлению (для печатного монтажа элементарная площадка – квадрат). Каждой элементарной площадке ставят в соответствие вершину графа решетки. Две вершины соединены ребром, если между соответствующими элементарными площадками может быть проведено соединение с учетом метрических параметров и топологических свойств типовых конструкций, устанавливаемых в данном монтажном пространстве.

Модель монтажной плоскости фрагмента верхнего слоя печатной платы с ортогональным монтажом при запрещении проведения проводников под микросхемами:

 

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

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

Расстояние между i - ми j -м узлами графа решетки в общем случае будет

d i ,j = (| S i -Sj | k +| t i -tj | k) h; i ,j =1, m; k = (1; 2); h = (0,5; 1),

где m — число узлов графа решетки.

При ортогональной трассировке k = h = 1, выражение принимает вид

d i ,j = | S i -Sj | + | t i -tj |.

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