автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Модели, алгоритмы и средства архитектурного трансформационного синтеза цифровых систем

РГБ ОД

1 б шш да

академия наук бшруси институт технической кибернетики

на правах рукописи

брич виктор григорьевич

удк 681.32:519.1

модели, алгоритму и средства архитектурного трансформационного синтеза цифровых систем

05.13.12 - Системы автоматизации проектирования

Автореферат диссертации на соискание ученой степени кандидата технических наук

МИНСК 1994

Работа выполнена в Институте технической кибернетики АББ

Научный руководитель - кандидат технических тук. ведущий научный сотрудник Пригожий А.А.

Официальные оппоненты:

доктор технических наук, ведущий научный

сотрудник Бибшю П.Н-:

кандидат технических наук, ведущий конструктор КБ НПО "Интеграл" Степанец В.Я.; ведущая организация БПА РБ

Зашита диссертации состоится "12" января 1995 г. в 14.30 часов на заседании специализг-рованного Совета Д 006.24.01 при Институте технической кибернетики АНБ по адресу: 220012, г.Минск. Сурганова. б, актовый зал.

С диссертацией иожно ознакошггься в библиотеке НТК АНБ

Автореферат разослан " 9" декабря 1994 г.

Ученый секретарь специализированного совета доктор технических наук

Г.И.Алексеев

ОБШАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность пшбденьи. Системы автоматизированного проектирования (САПР) цифровых ЕЖ. СЕЖ 55 устройств па их основа стали неотъемлемые инструментом, используемым при разработке цифровых схем на асег этапах, начиная с описания технического задания на проектирование и кончая получением докуйентов на изготовление изделия. Возрастание слогаости и объема работ, связанных с проектированием цифровых СЕЖ. требует дальнейшего развития систем автоматизированного проектирования. При этом особое значение гтриссретавт методы и средства, предназначенные для автоматизации проектирования на верхних уровнях: алгоритмическом, архитектурном. В систеыах. автската-зирутах верхний уровень проектирования, синтез устройства состоит в преобразовании поведенческого описания в структурное. Поведенческое описание определяет функши. которые должно выполнять устройство, а тасхе требования, предъявляемые к нему. Структурное описание определяв! части устройства и связи нехду ниии. Эффективность САПР, уровень автоматизации работ и достоверность получаемых проектных решений потенциально зависят от уровня спецификации исходного задания на проектирование. Чен выше степень абстрактности спецификации, тем лучке. Автоматизация работ на верхних уровнях позволяет существенно сократить обкее время проектирования и расширить круг пользователей САПР-Крене того, решения, принимаемые на верхних уровнях, сильно влияют на результаты последующих уровней проектирования схемы. Гее это определяет вагность рассматриваемой проблематики и актуальность связанных с ней научных задач.

Наиболее известны по данной проблеме работы Дж.Аллена, В.В. Воеводина. А.Д.Закрезского, П.Н.Бибило. Р.Каупосано. Т.Д.Ко-вальски. Х.Т.Куга, М.С.Макфарландз. Х.де Мана. В.А.Иищенко, Д.И.Молясвана. Э.С. Паркера. A.A. Прихожего и др. ученых.

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

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

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

Поставленная цель определила следующие Решаемые задами:

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

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

3. Разработка моделей и алгоритмов синтеза систолических архитектур и методики их использования-

4. Создание и апробация программного обеспечения архитектурного синтеза цифровых систем.

Мшши исследования. Теоретические исследования проводились на основе теории алгоритмов, теории графов, алгебры логики, теории вероятностей, данейной алгебры, математического моделирования, теории дискретных систем, программирования на ЭВМ. Еовш шише результаты

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

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

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

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

5. На основе предложенного алгоритма синтезирован систолический процессор для решения логических уравнений в дизъюнктивной нормальной форме.

Осшеемэ положения^ ешссшкй на закин:-

1. Поведенческая и структурная модели маршрута данных.

2. Алгоритмы редукции структурной модели маршрута данных.

3. Алгоритм перехода от поведенческого описания к систолической структуре.

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

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

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

Ешлизэдиз Рйзультатоп вабэхы- Разработанные модели, алгоритмы и структуры использованы и внедрены:

в Институте технической кибернетики АЩ при выполнении научных работ в рамках поогралыы "йнфсриатика" по теме Тазработка системы синтеза верхнего уровня с языка: ТШЗЬ для автоматизированного проектирования цифровых СЕЖ": по теме 1!62 Тазработка методов структурных интерприташй языковых описаний для САПР СБИС"; в рамках работы "Исследование методов искусственного интеллекта в процессах проектирования цифровых СБИС";

на Брестской элекг рсиеханичаскои концерне при выполнении работ по созданию программного обеспечения системы автоматизированной проектирования специализированных интегральных схем;

в Брестской политехническом институте в учебной процессе в курсе "Основы комплексной автоматизации проектирования и производства средств вычислительной техники".

ДпрпГитгия работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на XI и XII (1991) семинарах по однородный вычислительны« средствам и систолическим структура« (Львов), на I (1990) и И (1991) совещаниях-семинарах "Промышленные САПР в области электроники и вычислительной техники" (Брест), на международной аколе молодых ученых и специалистов "Новые информационные технологии в проектировании" (Гурзуф. 1991. 1992. 1993. 1994). на Республиканской школе-семинаре "Математическое и машинное моделирование в микроэлектронике" (Паланга.1991), на международной конференции "Методология проектирования в микроэлектронике и обработке сигналов" (Краков. 1993). на ряде заседаний научных семинаров КГК АНБ "Системное проектирование" и "Эргатические системы".

Пубгогеяпим. По материалам проведенных исследований опубликовано 7 статей, 7 тезисов докладов, 4 препринта.

Структура а ойьш работы. Диссертация состоит из введения, 'четырех глав, заключения, списка литературы и приложения. Объем основного текста - 150 страниц, рисунков - 36, таблиц - 29. Список литературы включает 187 наименований. Приложение содержит 51 страницу.

ССЖВШЕ СОДЕРЖАНИЕ РАБОТЫ

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

Пешая глава посвящена обзору современного состояния вопроса, выбору и обоснованию цели и задач работы.

В главе рассмотрены уровни проектирования цифровой схемы: системный, алгоритмический, архитектурный (регистровых передач), логический, схемный, топологический. Рассмотрены системы проек-

тасования цифровых СБИС по поведенческим описаниям на языке высокого уровня. Одной из основных задач, решаемых системами проектирования цифровых схем. является реализация наиболее перспективного метода автоматического проектирования цифровой СБИС по описаниям на входном языке высокого уровня - метода кремниевой компиляции. Поведенческая спецификация должна определять то, что вычисляет проектируемая система, но не то. как должно быть реализовано поведение. Поведение проекта описывается на специальном языке высокого уровня (VHBL. ISPS. ELLA и др.). Первым шагом высокоуровневого синтеза является преобразование поведенческого описания проекта на формальней языке во внутреннее представление. Во многих методах используются представления, основанные на графах, которые содержат поток данных и поток управления. Однако, в этих методах не рассмотрении комплексные модели и алгоритмы высокоуровнего синтеза ыарорута данных по сложностным параметрам в последовательно-параллельных архитектурах. В данной главе проанализированы также методы аппаратного синтеза систолических структур, которые используют графовые модели для преобразований и не ориентированы на применение в системах автоматизированного проектирования.

На основе анализа литературы сформуягрованы следующие задачи, которые необходимо решить:

разработать модели синтеза нарврута данных в последовательно-параллельных архитектурах:

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

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

исследовать алгоритм перехода к систолической структуре и оценить его характеристики:

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

Eq второй глав9 рассматривается задача синтеза маршрута данных по поведенческому описании, описывающему вычисления, которые должны быть реализованы с минимальным объемом оборудования при ограничениях на быстродействие. Быстродействие определяется стег^чьп параллелизма алгоритма, по которому

ведется синтез. Поведенческое описание записывается на языке высокого уровня УНБЬ и представляет собой систему взаимосвязанных операторов, объявляющих объекты модели и описывающие действия над этими объектами.

Алгоритм, описывающий поведение цифровой системы, записывается на язьке высокого уровня и с помощью анализатора переводится во внутреннюю форму. Строится графовая модель алгоритма, состоящая из графа потока данных (ГГШ) и графа потока управления (ГПУ). На основе ГПУ и ГГШ определяются отношения несовместимости на множестве переменных и множестве операций. Двудольный нагруженный граф является моделью для синтеза маршрута данных последовательно-параллельной архитектуры. Главная проблема, решаемая с помощью данной модели, состоит в максимальном совместном использовании аппаратуры. Элементами маршрута данных проектируемой системы являются ячейки памяти (регистры), функциональные узлы и мультиплексоры, составлявшие базис высокоуровневого синтеза. Типы Функциональных узлов, входящих в базис синтеза, реализуют все операции языка высокого уровня, который используется для описания алгоритмов.

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

Определение I. Поведенческой моделью маршрута данных называется двудольный ориентированный граф А=(г,Б). обладающий следующими свойствами:

1) множество вершн графа 2 является объединением двух непересекающихся подмножеств: подмножества вершин-переменных X и подмножества вершин-операций У. то есть г^ХиТ и

2) на множестве X задано бинарное отношение Р несовместимости переменных, которое описывается одноименной бинарной треугольной матрицей размерность»} п*п. Элемент матрицы

р,ке{0.1) и Рп=1 для 3.1с«1.....п и КгЗ. Если переменная х

несовместима с переменной хк. то р]к-1. Если переменная х. совместима с переменной хк, то Р)к=0. Совместимость переменных устанавливается на основании анализа путей на графе потока управ пения, по которым передаются значения переменных. Эти пути определяют времена жизни переменных. Две переменные могут находится в отношении совместимости лишь в тон случае, если их времена жизни не пересекаются. В противном случае переменные

находятся в отношении несовместимости.

3) на множестве У задано бинарное отношение В несовместимости операций, которое описывается одноименной бинарной треугольной матрицей размерностью ш»т. Матрица В стрслтся путем анализа графа штока данных в отношении расгтараллеленности операций с учетом лх однотипности ям разнотипности. Две операции и Ук находятся в отношении несовместимости (Ь^к-1), если выполнено хотя бы одно условие:

a) операции Ук и Уг разного типа;

b) ук и 7Х выполнятся параллельно. В противной случае операции находятся в отношении совместимости (Ь1к=0).

4) множество Б дуг графа разбито на два подмножества: подмножество о дуг. направленных из вершин множества X в вершина множества У. и подмножество « дуг. направленных из вершин множества Т в вершины множества X. при этом .

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

1) зп=0, если пара (ц.Ук)ея и пара (ук,х1)«4;

2) за=1. если пара и переменная х1 - первый операнд операции Ук;

3) эк1=£, если пара (х1,Ук)«п и переменная ^ - второй операнд операции Ук:

4) эн=3» если пара (х1.Ук)<=о и переменная х1 - первый и второй операнд операции Ук:

5) 3^=4, если пара

6) зк1=5. если пара (х1.Ук)«л, переменная х1 - первый операнд операции и пара СУк.х1)=»:

7) эк1=6. если пара (х1,ук)«л. переменная х1 - второй операнд операции у( и пара

8) зк1=7. если пара (х1.ук)<=л. лерененнэя х, - второй операнд операции У, и пара (Ук )<=■».

В отличие от поведенческой структурная модель наритагти данных описывает состав и соединения элементов структуры цифровой системы последовательно-параллельной архитектуры и строится на основании поведенческой аодели.

Определение 2. Структурной моделью маршрута данных (рис. 1)

называется двудольный ориентированный взвешенный граф С= С7.Е), обладающий следующими свойствами:

1) множество вершин графа У=ймТ является объединением двух непересекающихся подмножеств: подмножества И вершин-регистров и подмножества Т вершин-функииональных узлов;

2) на множестве Я задано бинарное отношение О несовместимости регистров, которое описьается одноименной бинарной иатргохей размерностью и*и. где ) и для

З.к-1.....и и къЗ- Если регистр г, несовместим с регистром гк,

та . Если регистр совместим с регистром гк, то Ч)к=0. Два регистра находятся в отношении совместимости лишь в том случае, если времена жизни хранимых в них значений не пересекаются. В противном случае, регистры находятся в отношении несовместимости:

3) на множестве Т задано бинарное отношение И несовместимости Функциональных узлов, которое определяется одноименной бинарной матрицей размерностью где да, ¡.=£0, 1} и

для 1Л-1.....V и 1в1. Если функциональный узел ^

несовместим с функциональнш узлом . то т^ к =1. Если функциональный узел совместим с функциональным узлом ^, то «11с-<3. Два Функциональных узла ^ и ^ находятся в отношении несовместимости если выполнено хотя бы одно условие:

- они относятся к разным типам:

- на них осуществляется параллельное выполнение операций. В противнем случае функциональные узлы находятся в отношении совместимости (ш^-О).

- множество Е дуг графа разбито на два подмножества: подмножество г дуг, направленных из вераин множества Н в вершины множества Т. и подмножество * дуг, направленных из вершин множества Т в вершины множества Н. при этом Е-гш-;

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

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

1

; ; ; •

. |. •

. ...д ..а

Г I"

I1

гт

Г

1 * . .11

11 11 IV

»=1 * . . .. .я

11 ... V V

У 1» . . . ?? . ■ *

VI VI Wj

н = 3

• 1

Л, ...Ь ...11.

^ л

Л ....11 ...,й

VI VI VII

Рис. 1. Структурная нодет изршрута данных

которые имеют два входа и один выход. Элементы матрицы Н принимают в этом случае следующие значения:

1) Ь.-О - нет связи между регистром и функциональным узлом. и (Г}.1 )«г;

2) 1x^1 - выход регистра г соединен с перьиы входом Функционального узла (г.,^)«*":

3) Ь -2 - выход регистра г. соединен со вторьы входом Функционального узла и. (г.,1)ег-

4) Ь. -3 - выход регистра г. соединен с первым и вторым входом функционального узла 1, )ег;

5) - выход функционального узла г. соединен с входом регистра г. , а. ,г.)<=*;

6) 1^-5 - выхо! регистра г. соединен с первьы входоы функционального узла г. и выхш функционального узла 1 соединен с входом регистра г}, и (з^.г^ег:

7) 11^=6 - выход регистра г соединен со вторьа входом функционального узла 1 и выход функционального узла \ соелинен с входом регистра г, (1 и {г,1)ег;

8) Ь^-7 - выход регистра г соединен с первым и вторым входом функционального узла \ и выход функционального узла 1:. соединен с входом регистра г, (^.г.)«* и (г^г^ег;

Для 1-й вершины из множества И весовая функция имеет вид Г" = с"+К* п* (и*,я*),

Ь I Ь I I I

где с* - свободный коэффициент, величина которого зависит от типа используемых регистра и мультиплексора, ¡с* - сложность одного разряда регистра, п* - разрядность регистра. &л (у*.п") -функция сложности мультиплексора, стоящего на входе регистра, в которой - число информационных входов мультиплексора, л* -разрядность мультиплексора, стоящего на входе регистра. Для 3-й вершины множества Т весовая функция имеет вид

где с* - свободный коэффициент, который зависит от типов используемых функционального узла и мультиплексоров; кТ

сложность одного разряда линейного функшональчого узла; -

сложность одного разряда матричного функционального узла; и1* -разрядность Функционального узла; ¿т (ь^ .т*) - функция сложности мультиплексоров, стоящих на входах функционального узла, в которой . - количество информационных входов мультиплексоров, стоящих на первой и втором входе Функционального узла. -разрядность этих мультиплексоров.

Совокупная аппаратурная сложность маршрута данных описывается функцией

и т

в которой и -число регистров, V - число функциональных узлов.

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

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

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

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

Задача оптимального синтеза устройства принадлежит к КР-трудным задачам. Для ее практического решения необходимо применение эвристических алгоритмов, которые просматривают вершины начиная с корня и кончая первым достигаемые ¿истом.

Эвриспческий алгоритм АП2 при переходе от одной вершины дерева поиска к другой осуществляет редуцирование маршрута данных по результате« локального перебора. Выбирается такая пара совместимых вершин графа маршрута данных, которая максимально уменьшает сложность редуцированного иаршрута данных по сравнении со сложностью маршрута данных до редуцированния. Если текущее значение весовой функции редуцируемого графа (I, то значение весовой Функции Р^, графа ^ т 1, полученного в результате редукции, уменьшается на максимальную величину

К достоинству алгоритма АНТ относится возможность учета совокупного эффекта, получаемого от склеивания вершин и склеивания дуг графа маршрута данных. Следует однако отнетить. что при большом числе пар в списке Ь1 время работы алгоритма мехет оказаться достаточно большим.

Эвристический алгоритм АНЗ редуцирования маршрута данных осуществляв- поиск пары совместимых вершин из списка с максимальной суммой хачвний соотвествувших вершинам весовых Функций. Достоинство алгоритма заключается в его быстродействии.

Следующий эвристический алгоритм АЙ4 редуцирует маршрут данных посредством выбора такой пары совместимых вершин графа из списка Ьк при склеивании элементов которой функция

дР дх

тг-К^г-

принимает максимальное значение, гае кх ,К2 - коэффициенты, сунна которых равна единице; \ - число пар в списке К; д\. =\.-х. ^ -уменьшение числа пар в списке. Функция р учитывает изменение сложности и числа элементов в списке совместимых пар. Если требуется максимальное уменьшение сложности при склеивании одной пары, то к1>>к1. Если необходимо обеспечить большое число вариантов и широкие возможности последующего редуцирования графа, то Кг»1с4.

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

В главе рассмотрены также алгоритмы раздельного редуцирования по регистрам и Функциональным узлам. Задача редукции по регистра« и функциональным узлам сводится к задаче раскраски взвешенных неориентированных графов 0Ж и 0т соотвественно.

Задачу раскраски взвешенного графа . состоящую в минимизации суммы весов красок, сформулируем в следущем виде:

Н=т1п ^ шах ),

*** Зе|К(у)! Г1е«'"1<1>

где Функция *:11-»К ставит в соотвествие множеству Н вершин

множество К красок таким образом, что *>(г у*-(г.), если -1 *

(г..г.)вО; у :К-*И - функция, обратная функции V! Д -множество возможных функций раскраски; К (у) - мощность множества К: ) - вес вершины г. -

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

При раскраске вершин И графа 0, алгоритмом на каждом « *

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

подмножество ¡^ я его вершинам назначается один цвет. Вес краски опрос*пявтся согласно Формуле. Весом подмножества й. является сугоа весов входящих в него вершин. Вес вершины, являющийся максимальным из всех весов вершин подмножества Л. , не включается в сумму

&= 7 «(г,)- пахк(г ).

Лн.

J I

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

Алгоритм ТК52 выполняет раскраску вершин Н графа по следуюыей схеме: осуществляется сортировка вершин по убыванию весов: очередная краска присваивается первой нераскрзыенной вершине в отсортированном списке и всем совместимым с ней и друг с другом в порядке следования вершинам; вес краски раеен весу первой нераскрэшенной вершины.

Алгоритм ИСЗ используют следующую стратегию раскраски: при назначении краски из множества вершин-кандидатов на раскраску выбирается такая вершина, пс^пе раскраски которой число вершин-кандидатов на раскраску в этот же цвет остается наибольшим: при этом веса вершин, раскрашиваемых в один цвет, должны быть приблизительно одинаковы. Если существующая краска использована быть не может, то вводится новая, которая назначается очередной нераскрашенной вершине.

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

В рассматриваемом ниже алгоритме преобразования поведенческих описаний будем полагать, что ¿'(и)^-^ либо ¿'(и^Т^-Сц-с.), где 01 - максимальное значение переменной и^;

1-й индекс в векторе и; натуральная констшта-

Алгоритм перехода о.- заданного поведенческого описания к систолической структуре включает следующие шаги:

1. Добавление индексов к переменньм с целью уменьшения времени обработки при заданном ограничении на разнерность процессора. Для добавления индексов используется правило:

хи:=«; {хц:=Г(хц)}<»зи.0:=«: {^д^^^.,)].

2. Анализ направления транспортировки значений переменных и внешних данных. Методика анализа состоит в следующем. Если в

А А

алгоритме имеется оператор хи:=1(2^ и и, у - множества индексных переменных, входящих в и и у, то транзит значений переменных можно вести только по индексам упц. Для сокращения времени работы систолического процессора транзит значений sv необходимо вести по индексам, по которым ведется транзит значений \.

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

4. Сведение приращений -с^ в индексных выражениях к приращения -1 путей введения дополнительных переменных в алгоритм. После этого все вычисляемые переменные информационно связаны с соседними переменньми в выбранной системе координат. На этапе сведения приращений к -1, при с>1 используется правило:

I-1.Г 1г1.Х

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

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

{—Vii="s V^tz&u,.,-^—) "

f...xul:=o; а,^Пх^д)...}. i=i*« 1

при этом имеет место

{...х :=v(x о (...х :=у(х .)...!.

^ u,l u.l-i J U.l U,lTl J

1-1 . г . = t . z

где (...) - цикл с приращением -1 по перенашой 1.

6. ВЕЭдение транспортных операторов и переменных с целью доставки необходимых значений из одной точки пространства вычислений в другую. Индексация транспортных переменных осуществляется в соответствии с индексацией переменных, несущих результаты вычислений, по критерию минимума времени работы проектируемого систолического процессора. На этапе введения транзитных переменных используется следующее правило. учитывающее результаты анализа направления транзита:

{...х :=Г(а )...} в (,..ts :=з itt* :=t*. «х* :=r(t* )...!.

^ u, I V J ^ и,О V V.l V.x-l U.l V» J

1=1.1 i S1.I

А А

при l«fw. где w - множество индексов, входящих в я. Это преобразование вводит новую переменную t^. добавляет к алгоритму два выполняющихся парггпельно оператора присваивания, осуществляющих транзит, заменяет переменную в вычисляющем операторе.

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

разбивается на Ь фаз. разделяемых операшей последовательного выполнения. Длительность фазы определяется выражением

где I- верхнее значение индексной переменной (предполагается, что для всех циклов оно одинаково); к. - число индексов, по которым ведется транспортировка данных, плюс единица, если нет транспортировки значения вычисляемой переменной. Время

I.

выполнения алгоритма Т=7 й .

8. Построение общей структуры системы систолических вычислителей и структуры каждого систолического вычислителя.

9. Синтез схем процессорных элементов систолических вычислителей.

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

Структура синтезированного процессора представлена на рис. 2. Она состоит из процессорных элементов первого (КЗ*. ,5 и второго (ПЭ*) типа, триггеров (Б), счетчика, устройства управления (Н") и линий связи.

Функциональное назначение процессорного элемента первого типа состоит в определении ортогональности элемента вектора х элементу строки матрицы М, описывающей ДНФ булевой Функции. Число ПЗ*, определяется числом строк и столбцов этой матрицы и равно т«п.

Процессорный элемент второго типа выполняет логическую функцию И над результатами проверки ортогональности. Число процессорных элементов второго типа равно числу строк троичной матрицы И или числу конъюнкций в ДНФ. т. е. равно п.

На первой фазе работы в каждый процессорный элемент первого типа загружается соответствующий элемент матрицы М. Порядок поступления элементов матрицы показан на рис. 2. Посла 2я тактов функционирования процессора матрица М загружена в процессорные элементы и запускается вторая Фаза работы профессора.

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

! г

м.

пг—! I ■<» I

Эг> - I

-1-

1 ...ПП-"1

J i 'I

гтг—1 I I

"г

!

-го:., =...= г<,

згатгг-

-1

i

С1оск!

77

1

ЕеаЛу

т

1 !

'В 11 1 I 1

¡^т I Г*

».п., 1с-1 1

I 1

17) 1 Г««-1 1 п > Iй«.-. 1

1 1

1 Т) 1 1 1 1 1

-...-иэ„ нпэ

'я i

.¡V !

7» , <1р=гг

1

I корень уравнения

Рис. 2. Общая структура систолического процессора

На 2п так;е работы процессора счетчиком генерируются набора вектора х. Сгенерированный набор со счетчика поступает на входы Б-триггеров. а затеи, в зависимости от номера элемента, на процессорные элементы . 3=2 .п. Перваг компонента набора \ сразу поступает на в? од ПЭ* 1, так как в первом столбце процессорных элементове не содержится И-триггеров.

Через Зп тактов результат вычислений из процессорно! о элемента ИЭ* подгется на вход ПЭ*. При этом на втором входе процессорнго элемента ТВ* должна находится логическая единица. В ГСЭ* (1>1) поступают танние из процессорного элемента ПЭ*П и из

и

я

ГО*.,« Информация с IB* регистрируется системой управления.

При поступлении ка вюд устройства управления сигнала и=0 набор вектора х не регистрируется и процессор продолжает работу по определению корня логического уравнения. Если на входе устройства управления находится сигнал u=1, то на выходах

триггеров Dj .n»Dj ,n-i'^s.n-z.....D„.» корень. Сигнал u=1

является сигналом остановки работы систолического процессора по определению ортогональности набора строкам матрицы. В таком случае, на выходе пошляется сигнал Reacty. совпадающий с входным сигналом и и информирующий об определении корня. Предполагается, что логическое уравнение имеет не менее одного корня, т.е. случай, когда матрица тождественно равна 1. не рассматривается. Общее число тактов работы процессора при прохождении одного набора равно t=2n+m.

Четвертая гп^а посвящена рассмотрению структуры системы архитектурного синтеза цифровых схем. которая отображает распараллеленный алгоритм, описанный на входном языке высокого уровня, в архитектуру цифровой схемы, проектируемой в виде СЕЖ. В ней были использованы программные средства созданные на базе алгоритмов редуцирования маршрута данных: анализу качественных и временных характеристики алгоритмов редукции маршрута данных (AR1-AR4) и раздельной редукции маршрута данных по регистрам и функциональным узлам (RG1-RG4). Определены области предпочтительного использования алгоритмов и точность получаемых результатов.

Исследование алгоритмов редукции маршрута данных, описанных . во второй »-лаве диссертационной работы, проведено на структурных моделях маршрута данных, построенных на основании алгоритмов решения стандартных математических задач. Наиболее точным по из эвристических алгоритмов является алгоритм AR4. Его результаты в трех случаях совпали с результатами работы точного алгоритма и в десяти случаях лучше или такие же как у алгоритмов AR2 или AR4. Исходя из быстродествия алгоритмов и основной цели редукции маршрута данных - получение минимальной сложности маршрута данных в системе синтеза архитектур цифровых схем лучшим является алгоритм AR4, Достоинство алгоритма AR2 заключается в максимальном быстродействии. Алгоритм AR3 позволяет получить хорошие результаты при возможности варьирования параметрами

синтеза. Процент отклонения результатов работы по параметру сложности синтезированного маршрута данных эвристических алгоритмов от результатов точного алгоритма для рассмотренных примеров следующий: AR2 - 13.73:5. AR3 - 8,673. AR4 - 4.61S. Использование точного алгоритма ограничено временен его работы.

Проведено исследование алгоритмов RGT-RG4 редуцирования по регистрам и функциональным узла«. Результаты элгоритна RG1 в 80S случаях совпали с результатами других или оказс)лись лучшими. а результаты алгоритма RG2 - в 65%, а алгоритма RG4 - всего в 20л. В результате исследований можно заключить, что по точноти решения алгоритм RG1 превосходит другие алгоритмы. Но. если рассматривать временные затраты и точность работы алгоритма одновременно, то, нессмненно. выигрывает алгоритм RG2.

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

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

тактсв Т вычисли« по формуле:

П X П 1 П 1

Т=4" > ГЕп-на+г"* (1 -р" )=2п+пн-> (1-p")=2n+m+2n- | pN.

w к- 1 Nil

1

Разлагая р" в бесконечный ряд для величины Т. получим другое соотношение:

га 2П 1

Т=2п+т-2п-(р+г% f lajp I —

Из формул следует, что сре.^нее число тактов зависит от значений переменных п, m и вероятности р. Величина 1-р обозначает вероягность того, что в вредней потребуется не более Т тактов для нахождения корня. Например, при размерности матрицы

21

равной 12x64 и р=0.001 потребуется не более 109 тактов для определения корня уравнения.

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

<5 =3п ^ | гГЧзт-гвгш-п.

*"Д9 г=1огг (п+2) .

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

1. Предложена модель маршрута данных структуры уровня регистровых передач для параллельно-последовательных архитектур в виде двудольного графа. ' нагруженного отношениями несовместимости элементов поведенческого, отношениями несовместимости элементов структурного описаний цифровой системы, а также параметрами этих элементов.

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

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

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

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

6. Предложен алгоритм синтеза систолических архитектур в

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

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

8. Реализованы программные средства на IEM PO в операционной системе HS LOS для решения определенных задач архитектурного синтеза цифровых систем. Выполнены вычислительные эксперименты. оценены характеристики разработанных алгоритмов и программ, показана их эффективность по качеству получаемых проектных решений, характеризуемых количеством вводимых в структуру Функциональных узлов, регистров, мультиплексоров•

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

публикации го теме диссерташ

1. Брич В.Г. Синтез регистровой памяти цифровой СБИС методом раскраски взвешенного графа//Проблеыы построения САПР CEE. -Минск. 1990. с.74-63.

2. Пригожий A.A., Брич В.Г. Оптимизация паи ятя цифровых СБИС при архитектурно« синтезе в САПР. - Тезисы докладов III совещания-семинара "Промышленные САПР в области электроники и вычислительной техники".- Минск: НТК АН БССР. 1990.

3. Брич В.Г. Автоматизация перехода от графовой модели алгоритма к архитектуре цифровой СБИС//Система

"автоматизированного проектирования СБИС Сфункционально-логический уровень). - Минск , 1991. - с. 118-128.

4. Брич В.Г. Синтез архитектуры цифровой СБИС по распарал-ленному алгоритму. - Брест. Тезисы докл. 2 совешакия-се;г.я-:арз "Промышленные САПР в области электроники и вычислительной техники". -Минск: НТК АН БССР. 1991. с.

5. Мищенко В.А-. Прихожий A.A.. Брич В.Г. и др. Система автоматизированного иерархического проектирования цифровых СБИС- Новые информационные технологии в САПР. - М.. 1991. с.12.

б. Прихожий A.A.. Брич ú.T-, Гусгозскэя Я.И. Программа синтеза архитектуры цифровой СБИС. - Тезисы докл. 2 совещания-семинара "Промышленные САПР в области электроники и вычислительной техники". -Минск: НТК АН БССР, 1991, с.

Т. Прихожий A.A., Брич В.Г. Оптимизация памяти цифровых СБИС при архитектурном синтезе в САПР. - Тезисы докл. 1 совешашя-семннара "Промышленные САПР в области электроники и вычислительной техники". -Минск: НТК АН ЕССР. 1991.

б. Прихожий A.A., Брич В.Г.. Густовская Я.И. Синтез систолической структуры из алгоритма. - Тезисы докл. 2 совещания-семинара "Промышленные САПР в области электроники и вычислительной техники". -Минск: НТК АН БССР, 1991.

9. Прихожий A.A., Брич В.Г. Синтез систолических вычислителей по алгоритмическая описаниям. - Тезисы докл. Г Всесоюзной конференции "Распознавание образов и анализ изображений, новые инфор. технологии (РОАИ-1-91). - Минск: ИГК АЯБ, 1991.

10. Прихожий A.A., Брич В.Г. Синтез системы систолических вычислителей. - Минск. 1991. (Препринт НТК АН БССР, N22. 24 е.).

11. Прихожий A.A., Брич В.Г. Оптимизация регистозой памяти в САПР СБИС. - Вопросы повышения производительности и надежности вычислительных систем- - Львов. 1991. (Препринт ШТ1. "Интеграл").

12. Прихожий A.A., Брич В.Г. Теория и средства алгоритмического и архитектурного проектирования цифровых СЕЖ. //Радиоэлектроника. - 1992. -Том 35, №6. - С. 14-28.

13. Прихожий A.A.. Брич В.Г.. Густовская Л.И. Эквивалентные -преобразования логического алгоритма в цифровую схему. -

Минск. 1992. (Препринт ИГК АН БССР. 114. - 48 е.).

14. Прихожий A.A.. Брич В.Г. Систолический вычислитель для решения системы логических уравнений. - Минск: ИГК АН БССР. 1992. (Препринт N5. - 42 е.).

15. Прихожий A.A.. Маньшин Г.Г.. Брич В.Г. Архитектурный синтез цифровых схем методом логического вывода в системе AHILES. -Тезисы докладов международной конференции и школы молодых ученых и специалистов "САПР-93:Новке информационные технологии в науке, образования и бизнесе". - Крым. Гурзуф. 1993. с.28-29.

16. Системы автоматизированного проектирования СБИС (материалы

по математическому обеспечению) /1 .А.Пригожий. А.А .Душам. М.М. Розов. Г.Я. Муравьев. В.Г. Брич и др./.- Минск:И1К ¿ЕБ 1992.

1Т. Prlkhozhy A.A., Brlch 7.G. Parallel Computations Synthesis 1л Digital 7LSI CAD System. - High-Speed Architectures Design. - Minsk. IEC. 1992. pp.184-193.

18. Prlkhozhy A.A.. Brlch 7.G. Logical equation solving systolic processor design. - Wcrcshop on Design Methodologies for Microelectronics and Signal Processing Gllwlce-Cracov, Poland. 1993. c.ai-88.