Варианты структурной организации программно-технического комплекса для решения задачи поиска кратчайшего пути[1]

Е.И. Артамонов,

зав. лаб., д.т.н., проф.,
Институт проблем управления РАН, eiart@ipu.ru, г. Москва

Аннотация

В работе рассматриваются варианты структурной организации программно-технического комплекса (ПТК) для решения задачи автоматической трассировки соединений между элементами на плоскости. Решение задачи автоматической трассировки принадлежит к числу сложных комбинаторных задач, называемых трудно-решаемыми или NP-полными [1], поэтому целесообразно рассмотреть сравнительные характеристики вариантов структур организации ПТК, реализующие параллельно-последовательные алгоритмы с использованием процессора-ускорителя [2].

Введение

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

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

При рассмотрении вариантов структурной организации воспользуемся разработанным методом синтеза структур интерактивных систем (ИС) [3, 4]. Перечислим основные характеристики этого метода.

Особенности метода синтеза структур интерактивных систем (ИС)

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

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

На второй стадии, стадии формирования локальных структур (ЛС), проводится систематизация множества возможных вариантов реализации каждого ЛА. Для каждого ЛА строится модель ЛС, представленная в виде структурной сети, вершинами которой являются возможные формы представления информации, а дугами – значения качественных показателей соответствующих реализаций. 

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

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

Синтез структурной организации ПТК

На первой стадии синтеза структуры ПТК выполняется операция разделения общего алгоритма функционирования на локальные алгоритмы. На рис. 1 выделены ЛА, отличающиеся структурами данных.  Образованы следующие локальные алгоритмы: 

1.      Ввод описания геометрической модели трассируемого поля (ОМ). На рис.1 ИВС - алгоритмы интерпретации входных сообщений, включающие интерпретацию входного графического языка (ИВЯ) и интерпретацию интерактивных действий пользователя (ИИД).

рис.1. Первый вариант построения СТП

Структура данных ОМ представляет собой символьную таблицу  со способом кодирования и точностью представления информации:

 

 

………

                                                      (1)

где  -  - ый  оператор в таблице описаний  из общего числа  операторов,

  - идентификатор - го  оператора,

-  -ая группа параметров - го  оператора.

 

2. Редактирование описания модели трассируемого поля, запись и чтение из базы данных.  На рис.1 эти ЛА обозначены квадратами с двумя диагоналями и повторяются в структуре ПТК многократно .

3.      Преобразование (блок ПРМ) структуры описания модели ОМ в таблицу действительных чисел ОМD со структурой, аналогичной (1).

4.      Формирование геометрической части модели трассируемого поля. Эта операция выполняется геометрическим процессором ГП, реализующим переход от ОМD к структуре  :

 

…

                                               (2)

где  - координаты  - ой точки ломаной линии, порожденной  - ым оператором, -служебная информация.

5.        Второй блок  ИВС - ввод описания цепей , соединяющих между собой контакты элементов схемы. Информация на входе представляется в виде символьной таблицы:

,

…

,                                 (3)

где - номера модулей и контактов цепи,

     - признак конца описания текущей цепи,

     - признак конца описания всех цепей.

6.      Редактирование описания цепей в формате ОС, запись и чтение из базы данных.

7.      Преобразование списка цепей (блок ПРС) в целочисленную (С) таблицу со структурой аналогичной  (3).

8.      Размещение элементов на плоскости и сортировка списка цепей (ЛА средств размещения элементов СР). Вход – структура данных ОСС, выход – таблица действительных чисел координат последовательно соединяемых контактов.

9.  Редактирование, запись и чтение списка цепей из базы данных в форматах ОСС и ОСD.

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

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

 В основе растрового алгоритма положена матричная модель трассируемого поля. Результат работы этого алгоритма предполагается получать в виде целочисленной матрицы М :

,                                                                             (4)

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

11. Редактирование, запись и чтение из базы данных в формате.

12. Преобразование структуры данных  в терминальные файлы  (i) (блоки ППi) и вывод результатов трассировки. В i представлены результаты в кодах i-го устройства, на которое производится вывод информации. Структура файлов в общем виде выглядит следующим образом:

 

………

                                                      (5)

 

Информация в , как правило, представляется в символьном виде. Достаточно часто используются стандартные способы кодирования в виде форматов  или HPGL.

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

Анализ вариантов реализации ПТК после проведения операций со структурами алгоритмов

Последующими стадиями синтеза структур являются операции объединения ЛА в смысле их реализации в одной локальной структуре (ЛС). На рис.2 показан второй вариант структурной организации ПТК, в котором объединены ЛА подготовки модели трассируемого поля и описания цепей, а также геометрического процессора ГП и блока СР. При этом образовались объединенные структуры данных: ОСМ и ОСМD. ОСМ также, как и ОМ, представляет собой символьную таблицу, а ОСМС – числовую таблицу со структурой, аналогичной (1). 

Для реализации растрового алгоритма трассировки требуются преобразования геометрических структур данных в матрицу М, структура которой соответствует (4). Таким образом появляются два дополнительных ЛА: преобразователь ПР1 формирует матрицу М модели трассируемого поля на основе  файла, а ПР2 делает обратные преобразования.

Особенности алгоритма подготовки модели трассируемого поля

Алгоритм подготовки модели включает отображение описания геометрических моделей элементов на модели трассируемого поля. Предполагается, что каждой координате X и У графического изображения ставится в соответствие номер столбца i и номер строки j матрицы M. Для этих целей вполне подходит  алгоритм Брезенхейма [3].

 

 

рис.2. Второй вариант построения ПТК

Алгоритм определения кратчайшего пути

В основу алгоритма автоматической трассировки соединений между элементами на плоскости положен широко применяемый в различных приложениях алгоритм определения кратчайшего пути в ориентированных сетях. Рассмотрим его более подробно.

Пусть имеется сеть G(B, A), где B - множество вершин сети, A - множество ориентированных дуг сети, соединяющих в любом порядке i - ую вершину с j - ой. На рис. 3 приведен пример сети, вершины на рисунке обозначены кругами и пронумерованы цифрами на темном фоне, на дугах цифрами в разрыве указаны веса дуг.

рис.3

Все вершины пронумерованы от 1 до N (общее число вершин сети). Всем дугам присваиваются значения . Требуется найти кратчайший путь от вершины 1 до вершины N.

Алгоритм состоит из двух частей: вычисление минимального веса последней вершины сети и фиксация кратчайшего пути.

Вычисление минимального веса последней вершины сети:

1.     i = 1, j = 1,

2.     Вершине b1 присваивается вес 0. Остальным вершинам b2,…bN  присваивается .

3.      j = j + 1.

4.      Вычисляется вес вершины bj = bi + a(i, j). Определяется bj min. Если j = N, то j = 1 и переход на п.5, иначе переход на п.3.

5.     Вершина j min помечается специальным маркером и в дальнейших расчетах в качестве конца дуги не используется, если j min = N, то переход на п.6, иначе i = j min и переход на п.3.

6.     Конец. Таким образом, вершина N имеет минимальный вес bN min, соответствующий кратчайшему пути.

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

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

 

 

 

 

 

 

 

Таблица 1

Реализация ПТК

Моделирование различных вариантов построения ПТК проводилось на программном обеспечении. Была создана программная система «Графика – 01-Т» [4,5], позволяющая описывать схемную документацию, формировать электронные модели устройств на разных этапах проектирования, решать задачи автоматической трассировки соединений между элементами на плоскости с использованием алгоритма определения кратчайшего пути.

В системе вычислительная модель автоматической трассировки соединений для любой конфигурации проектируемой схемы представлена в виде матрицы М (рис. 4), соответствующей сети G(B, A). Множество вершин В (на рисунке обозначено квадратами) соответствуют точкам подсоединения связей между элементами, множество дуг А (на рисунке обозначено стрелками) показывают направления расчета кратчайшего пути.  Ортогональные дуги имеют вес 1, диагональные дуги - 1.42. Общее число вершин сети равно N. В процессе расчета пути каждая из вершин bi принимает следующие значения:

0 – начало трассы,

р – препятствие,

              *- первоначальные значения не подсчитанных вершин.

          Остальные вершины в процессе расчета принимают значения между 0 и .

Началом трассы является вершина С, концом трассы – вершина D. На первом шаге алгоритма последовательно рассчитываются веса вершин, прилегающих к вершине С. На рис.4 эти вершины обозначены цифрой 1, в таблице 1 это соответствует строке 1 «шага алгоритма». Затем последовательно рассчитываются вершины с номерами 2 и т.д., пока на    - ом шаге не будет определен вес вершины D.

Программно реализованная система «Графика – 01-Т» используется для обучения студентов процессу создания электронной документации.

Вычислительная сложность  операций алгоритма на однопроцессорном компьютере определяется:

 

                                                       (6)

где   - количество операций по вычислению веса одной вершины,

       -  общее количество вершин,

      - количество вершин занятое препятствиями р.

рис.4

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

 

 ,                                             (7)

 

где   йХщ - означает целое число от  Х.

Последовательность работы СП показана на рис.4. Цифрами обозначена последовательность срабатывания СП. Наличие препятствий нарушает параллельность работы СП и тем самым увеличивает время его работы. Однако, сравнивая выражения (6) и (7), можно видеть, что реализация алгоритма поиска кратчайшего пути на базе СП существенно сокращает время поиска.

 

Литература

1.     Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. М.:  Мир, 1982. — 584 с.

2.     Артамонов Е.И., Правильщиков П.А.  Проблема трассировки и параллельно-последовательные D-алгоритмы на платформе механизма гипермассового параллелизма.  / Материалы 6-й Международной конференции СAD/CAM/PDM ― 2006.М.: Институт проблем управления РАН им. В.А. Трапезникова, 2006.Стр.17-20.

3.     Artamonov E.I. Automation of digital device structure design. B-215, ACTA IMEKO, 1973, p. 561-570.

4.     Артамонов Е.И., Высоких В.Ю. Варианты структурной организации систем проектирования РЭА.  Материалы  6-й международной конференции CAD/CAM/PDM – 2006. М.: Институт проблем управления РАН. - 2006 г.

5.     Херн Дональд, Бейкер М. Паулин. Компьютерная графика и стандарт OpenGL, 3-е издание. : Пер. с англ. – М. : Издательский дом «Вильямс». 2005.

6.     Артамонов Е.И., Сизова Л.Н. Автоматическая трассировка соединений (АТС). Свидетельство о государственной регистрации N2008613903 от 15 августа 2008г.


[1] Работа частично финансируется по проекту РФФИ 08-07-00067-а «Теоретическое обоснование и разработка макета процессора – ускорителя на основе механизма гипермассового параллелизма для решения труднорешаемых (NP-полных) задач»