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

од

ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ ПО ВЫСШЕМУ ОБРАЗОВАНИЮ Таганрогский государственный радиотехнические университет

На правах рукописи РЫЕАЛЬЧЕНКО Михаил Викторович

УДК 881.'323:658.512.2.ОН.5

РАЗРАБОТКА И ИССЛЕДОВАНИЕ АЛГОРИТМОВ И АППАРАТНЫХ СРЕДСТВ

для поддержки процедуры; размещения

ЭЛЕМЕНТОВ ВЫЧИСЛИТЕЛЬНЫХ УСТРОЙСТВ

Сшпиальности: 05.13.12 - системы автоматизации

проектирования;

05.13. С® - элементы и устройства вычислительной техники и систем управлзния.

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Таганрог - 1994

Работа выполнена за кафедре САПР ,Таганрогского государственного радаотажнического университета

Научные руководители: академик Международной Академик Информатизации, члвн-корр. АЕН РФ д.т.н., профессор Куреачлк В.М., д.т.н., профессор Гдушань В.М.

Официальные оппоненты: д.т.н., профессор Чернышев И.О.,

к.т.й., доцэнт Карелин В.П.

Ведущее предприятие - НИЦ ЭВТ (г.Москва)

Защита диссертации состоимся "__ 1994г.

в_часов на заседании диссертационного совета Д 083.13.02 при

Таганрогском государственном, радиотехническом университете по адресу: 347915, Ростовская обл., г. Таганрог, пер. Нэкрасовскиг, 44, ТРГУ, ауд Д-408.

0 диссерггациэа можно ознакомиться в Сиблиотэке института. Автореферат разослан "_4__1994г.

Ученый секретарь диссертационного совета Д 063.13.03, к.т.е., доцэнт

А.Н. Целых

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

Актуальность темы. В связи с ростом размерностей задач . лроеэтирования, возникают определенные трудности, обусловленные, во-мнсгом, несоответствием возможностей САП? (методов, алгоритмов, программных и аппаратных средств} требованиям автоматизированного проектирования Указанное несоответствие вызвано тем, что при средних темпах роста слотостя объектов проектирования, составляющих более двух порядков за десятилетие, темпы роста быстродействия процессоров общего назначения, реализующих прикладные программы проектирования составляют за тот же период величину около одного порядка. Это полошите усугубляется тем, что временная сложность основных алгоритмов проектирования составляет о(п2) и более. "Вцэ одной проблемой, обусловленной ростом сложности проектируемых изделия, является трудность обеспечения высокой степени интерактивно сти проектирования. Очевидно, что обеспечение. режима реального времени постоянно усложняется и требует дополнительных усилий. Наряду с повышением производительности САПР явно прослеживается тенденция к снижения нормализованной" плотности' компоновки, проектируемых СБИС. Для преодоления вышеуказанных, проблем предложен ряд подходов, одним из которых ■ является "разработка и использование в составе . технического обеспечения САПР специализированных аппаратных средств, непосредственно реализующих, либо поддерживающих алгоритмы проектирования. При этом относительно остальных, указанный подход реализует максимально возможнее повышение производительности, при росте или сохранении качества, и по различным оценкам и. тестовым- данным., обеспечивается ускорение выполнения алгоритмов проектирования до нескольких порядков. Систематически возникающей в . процессе проектирования является процедура размещения. При этом качество и трудоемкость выполнения процедуры размещения во-многом определяют и результирующие качественные показатели объекта проектирования в целом. Поскольку проблема размещения в обдам случав ' является МР-трудной, то на практике она решается, как прззиго,• с помощью * различных аврисптсеских алгоритмов,, требующих обьгёно. . полиномиального времени. Однако такие алгоритмы, обесточивающие наибоаэе качественные результаты, при больших размерностях

требуют значительного времени. В связи с.этим актуальным является разработка : алгоритмов размещения и аппаратных средств САПР, непосредственно • реализующих, -яийо поддерживающих данные алгоритмы, ■ . -

Цель диссертации. Цэлыо ■ диссертационной . работы является анализ, разработка и исследование алгоритмов и аппаратных средств САПР, позволяющих повысить эффективность решения проблемы размещения.

Для достижения поставленной цэли были решены следующие основные задачи:

- разработка и исследование стратегий и алгоритмов размещения и соответствующих аппаратных моделей;

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

- выявлвниэ основных требований, предъявляемых к разработка специализированных аппаратных - средств для поддержки алгоритмов размещения, и выработка рекомендаций по их удовлетворению;

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

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

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

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

- на основе анализа и классификации проектов ускорителей размещения сформулированы основные требования, предъявляемые к разработке аппаратных средств для поддержки алгоритмов размещения; '

- в ' рамках иерархического ппдюда- обосновано применение стратегии размещения, ориентированной на аппаратную поддержку; ■

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

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

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

Практическая дэнность результатов работы. Практическая ценность работы состоит в том, что использовании разработанных алгоритмов и включение разработанных аппаратных средств в состав технического обеспечения САПР, позволяет существенно ускорить (до Ю раз относительно аналогов) реализации процедуры размещения, обеспечить жизнеспособность более трудоемких, но . и более качественных .'алгоритмов проектирования, повысить стешвь интерактивности процэсса проектирования, и, таким образом, повысить качество и снизить трудоемкость и стоимость проектирования. Разработанный алгоритм и результаты его исследования могут быть самостоятельно использованы в качестве э„-8М8нтов математического обе стечения • САПР, а соответствующие программы - ка^ . инструментальное средство экспериментального исследования различных алгоритмов размэадэния.

Реализация результатов работы. Основные научные и практические результаты, подученные в диссертации, использованы в 3-х хоздоговорных (х/д NN 13420, .13117, 13119) и госбодгатрой работе К13155, выполнявшихся в соответствии с Постановлением N570/137 * "Создать новые и развить .действующие системы автоматизированного проектирования (САПР) и автоматизированные системы научных исследований (АСНИ) в народном хозяйстве", утвержденном ГКНТ АН СССР от 10.11.85., координационным планом работ по комплексной научно- технической программе Минвуза' РСФСР "Системы 'автоматизированного проектирования", утвержденном приказом Минвуза N31 от 25.02.86. Результат диссертации внедрены а Институте проблем вычислительной техники (ИПВТ) РАН (г.Ярославль), где они были использованы при разработке высокоаффективных программно- аппаратных 'средств САПР. Изготовлены и протестированы макеты ряда узлов предаюшняых устройств (универсальный формирователь перестановок, блох

. . • "б" ' введения подстановки, блок оцьнки по критерию суммарное длины дета), создана программная подсистема даю экстериментального исследования комбинаторных алгоритмов размепрния'. Кроме тоге, отдельные научные « практические результаты диссертации Использованы в учебном процэссе на кафэдре САПР ГРГУ при чтении лэкциа и в цикле лабораторных работ по курсу "Автоматизация проектирования ЭВА", при проведении дигшэмяого проектирования.

Апробация работы. Основные положения работа докладывались и обсуждались на:

- международной '. конференции и школе . молодых ученых и специалистов "САЛР-82. Новые информационные технологии в науке, образовании и бизнесе" (г.Гурзуф, 1892г.);

- Всаросеийских научно-технических конференциях с участигм зарубежных представителей "Интеллектуальные САПР" (г.Гедендаик, 1982г. и 1993г.).

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

Структура и объем диссертации.. Диссертация . состоит из введения; трех глав, заключения, списка сокращений, использованных в тексте, списка литературы и приложения. Работа содержит 199 стр., включая 36 рис., 11 табл., список литературы из 100 наименований, 50стр. щтюатшш и актов об использовании.

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

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

, В первой главе рассматривается постановка задачи, обосновывается применение стциалиэлфованныж аппаратных средств для поддержки цродедуры размещения. в. составе комплекса технических средств САПР, рассяатргаается общий подход к организации процесса обработки, проведен анализ известных проектов, на оенрэе чего сформулированы основные требования к разработке сшцщхэдэссоров размецвния, разработана ' их классификация па архитектурному признаку.

В общем случае при решент: задачи размещения требуется отыскать такое отображениэ ¡а множества M Елеиентов схемы" 4 аа . множество позиций Р рабочего шля, при котором: '

cost(iD)-» jBin{cost(î)>; Ptn 0, vt,j, t»»4, t.,4e{ï"pT}; ter ■

k V n ' ___

U p.=P, n pt=0, EIPJS*; PjO P,® 0, Vv«{t,r>, vieil,q};

i»± val ,

где cost() - целевая функция; T - множество допустимых реявши; Р. и р - подяножэства позиция рабочего поля, занимаемых, соответственно, элвментами а^- н о}( Ft - годаноюства заирещанных дал размещения позиция рабочего поля,, q - количество запрещэнных зон. На основе рассмотрения текущего состояния и тенденция развития -технических средств САПР делается вывод о наличии такого перспективного направления их дальнейшего совершенствования в плаве повышения производительности как разработка и использован» акселераторов, реализующих или подчеркивающих трудоемкие проектные процедуры и операции, в частности, размещения. Выигрыш по производительности достигается при этом, как правило, за счет эффективного использования различных видов параллелизма на всех уровнях обработки, электронного моделирования, особенностей аппаратной реализации. ' При этом указанные сродства обесточивает наибольший эффект, если архитектура специализированной системы я структуры ее функциональных элементов максимально соответствуют абстрактным структурам реализуемых алгоритмов. Колькестьенный рост производительности кроме непосредственно сокращэния времени решения задач, позволяет добиться и качественных эффектов -обеспечить жизнеспособность более трудоемких, во и дающих лучшие решения алгоритмов, изменить характер взаимодействия между пользозаталзм и САПР в сторояу повышения интэрактквности, т.е. обеспечить более дружественный интерфейс в сйстеме "человек-малина".

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

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

- функциональна» значимость и физическая реализуемость; '

- максимизация показателя производительность/стоимость;

- простота интеграции в среду проектирования;

- максимальная пЛкопть (шрестраиваемость процздурвых параметров);

- инваркаатаость относительно конструкторско - твяплзгичеекк ограничений я особенностей объекта проектирования.

Выработан ряд рекомендаций по удовлетворению - указанны* требований.

Авалю известных проектов ускорителей демонстрирует, яте: сложность учета совокупности Предъявляемых требований, многие да которых противоречивы, стала причиной того, что больпая часть ие сделанных с начала 80-х годов при участии ведущих в облает вычислительной техники я САПР фирм и лабораторий мира разработок специализированных . аппаратных ерэдетв, остается на стада» проектов я лабораторшх пбраацов, что ставят задачу повышаю« эф$ек?иЕаосла аппаратных ускорители* дая подцэркош и реализад» алгоритмов разаацвяяя.

На основе сделанного анализа известных проектов проведен? классификация аппаратных средств для ускорения процедуру разнещэада no архитектурночу признаку. Верхний уровень иерархи; включав! четыре основных класса араигекгур; матричную, конвейерную, с аппаратны* ядром и архитектуру на осноте нвйронныз сетей. Класс матричных архитектур дополнен подклассами полной i сокращенной архитектуры. Сущность итого признака , классифякацга определяется ссотеошвнивм числа процэссоряых идмюзтов и числг блоков памяти в той ш иной архитектуре. Дополнительно введет содкласск дхл яраггектури о аппаратным ядром, в зависимости о: степени регулярности логики аппаратного ядра. Дхя рзализацю алгоритмов ршмцмкя стгли яспольэовщля я специальные модел Мйронвых сетей, что .такнв отражено в данной классификащи.

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

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

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

Поскаику одни»! из наиболее трудоемких среди эвристически* алгоритмов размещения яахяются алгоритмы итерационного тип», они являются основными кандидатами доя ускорения. Одаако кмвство решений, позгчаемых кногзши тагами алгоритма**' ограничивается, как правило, счет быстрого попадания в лохавдш оплмум пру отсутствии кагас-либо шхашсиюв выхода ш- ш. Г^эдхягается

- ■

использовать следующий вероятностный. механизм преодоления локальных одгимумов: некоторое новое решение News, для которого cost(NewS>ic'ost(S) (имеется в ввду задача минимизации) . принимается при условии, что среди 1 предадущлх решения не содаркится ни одного такого, для которого co3t(N"ewS) cost(S). Таким образом, некоторое неулучшаюшэе решение принимается лишь в том случае, если. ограниченная последовательность попыток не приводит к отысканию-улучшающего решения. В связи с этим данный алгоритм назван алгоритмом ограниченной последовательности. Для его реализации требуется" задать специфические параметры и процэдуры: исходную длину L последовательности и процедуры модификации текущего решения S и . длины последовательности L. , Заметим, что параметр L можно . приближенно интерпретировать как величину, обратно - пропорциональную вероятности принятия неулучшающего'решэния. Процэдура модификации текущего решения S может сохранять либо произвольное, либо лучшее среди I предыдущих решений. Процедура модификации длины может быть либо пустой, .либо модифицирует, параметр L, например, как /зхЬ, или Lf/э, где ft-"коэффициэнт модификации (приращение) длины. В соответствии с данной интерпретацией цэлвсообразнс лишь наращивать L b процессе выполнения алгоритма, поскольку при этом уменьшается вероятность принятия неулучшающих решений и ' увеличивается вероятность удержания или улучшения текущего, решения, следовательно, ■

При крааниг значениях параметра L возникает два частных случая:

- при L=0 принимается всякое новое решоииа NeeS и, таким образом, работа алгоритма сводится к случайному перемещению в пространства допустимых решений;

-при достаточно больших I, скашм при J>|I(, где I -выбранная окрестность допустимых;решений, принятие решения NewS, для которые co3t(Ne»S)>cost(S)t практически не допускается, т.е. алгоритм вырождается в классическую "жадную" эвристику.

В связи с трудностью получения точных оцэнок качества, рассматривалось поведение алгоритма на мно:юстве предположительно типичных индивидуальных задач, т.е. "в ерэдвем". Аля проведения, экспериментальных исследований была . разработана программная подсистема, реализующая ряд алгоритмов "'размещения, • позволяющая > варьировать основные' параметры алгоритмов (функции генерации

рэютния, цалввыв функции, функции принятия решня») и контролировать их эффективность; подсистема реализована на яям Сич-ь дан IBM- совместимых компьютеров, содержит ' 1620 епрсж исходного кода и имеет размер выполняемого модуля 59,5 К. Проведанные исследования показывают, что при истальзовакми алгоритма ограниченной последовательности в среднем дополнатвльио достигается до БОЯ (а в отдельных случаях да 1СШ) выигрыша Ш качеству получаемых решений, оцениваемому критерием загруженности рабочего шля, относительно классической эвристики парных шрестановой. ,Однако . это может потребовать многократного увеличения числа итераций,, что обуславливает необходимость ускорения реализации подобных алгоритмов. При этом абсолютная величина выигрыша пропорциональна количеству выполненных итераций. При постоянной дайне последовательности,, т.е. при /Э—t, l=const, наибольшую эффективность предложенный алгоритм имеет дхя 10=СЗсп] при ketO,S, 2] для парных трестановок и при Jce[2,4J. для тройных циклических перестановок. При выборе к меньше минимальных значений на указанных отрезках, набладэется неустойчивое удержание хороших решений, что в большинстве случаев приводит', к существенному снижению качества цолуччемых решения. При \ использовании модификации длины последовательности, т.е. при , рост выигрыша по качеству получаемых решений относительно случая постоянной длины, достигается . лишь для "малых" исходных дяш независимо от метода формирования вариантов. Однако, поскольку при этом не было зафиксировано выигрышей, превосходящих максимальные выигрыши при L=con3t, для предложенного алгоритма цэлвсообразло использовать постоянные значения Длин. В этом случае обеспечивается также и наибольшая эффективность данного алгоритма, особенно при его аппаратной реализации.

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

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

;.г*змэцвния и ускг-рителвй размену ния с рэссирэнныки

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

. При построении , устройств для оценки размещения предложено использовать гиперграфовую модель с пословно- параллельной обрабЬткой ее .матричного представления. Структура устройства для случая стандартных элементов содержит блоки памяти и оценки перестановок, причем для. последнего разработаны варианты; обеспечивающее 'расчет критериев суммарной длины цегой, ■загруженности рабочего поля и сов1«ещвнйый расчет критериев. Сравнительная оценка разработанной структуры с одним из наиболее быстродействующих аналогов показала, что при некотором повышении быстродействия (в (Sn+log^nJ/Tn раз), упрощении формирования произвольных новых решений и сохрана шэд высокой регулярности логики, обеспечивается, сокращение аппаратной сложности не менее, чем в 4' раза, причем получаемый выигрыш увеличивается с ростом размерности задачи (при п=25в он составляет «10).

. Учет особенностей .размещения макроэлементов может быть реализован■на основе предложенных устройств для оценки размещения стандартных элементов при использовании более адекватных Матричных моделей элементов и рабочего поля. Для этого в CTpyKTjrpy устройства вводится блок модификации перестановок, обеспечивающий выборку данных из памяти в соответствии с топологическими особенностями размещаемых макроэлементов. Данная структура относительно предложенного альтернативного варианта на основе матрицы контактов обеспечивает упрощение распараллеливания за счет обработки однобитных элвментов данных при leí тает .более высокое быстродействие, где к-число каналов параллельной обработки,• I-средаее число задействованных контактов макроэлемента.

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

рамкзх которой разработана структура Многофункционального процессора размещения, обеспечивающая реализацию как алгоритмов размещения на основа полного и случайного перебора, так к широко используемых итерационных алгоритмов улучшающвго типа с возможностью задания произвольного начального размещения, ^то достигается применением блока введения подстановки, реализующем отображение п -!-> л', где п ~ „исходная перестановка "обезличенных" позиций рабочего поля, я— перестановка конкретных, элементов, X - подстановка вида (^'щ1''' щ^} •

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

Для обеспечения возможности ■> варьирования ' стегвни параллелизма обработки в зависимости от предьявляе,мых требований, имеющихся ресурсов' и.' ограничения предложено использовать секционировануто структуру данных на основе памяти с варьированием ширины доступа-и разработаны^соотватствущю модификации блоков расчета критериев, обеспечивающих функционирование при 1£к5ш.. •

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

Размещение стандартных элементов. Случай 1, к=ш:

где -частота формирования блоком организации перебора кодов перестановки. Случая 2, к<пь В этом случае потребуется использований секционированной структуры данных, и, соответственно, параллельно- последовательной . обработки. Таким обргзом: ''

- |Гс/(пПп/к1)1.

Разметенш макро элементов. Случай 1, к-т. Пусть 1 - длина (или число задействованных контактов) 1-го-макро элемента, 1=1 ,п.

п . ■

При этом илеем: Б* = Р^/ЕЗ.^.

Случай 2. к<л: S* = |Ty pa/k"! )] >.

с > = i %

Величина ускорейия относительно 1MIPS компьютера составляет до 2 -i- 4-х порядков б зависимости от размерносщ задачи и конфигураций поцэссора размещения, причем с ростом размерности она увеличивается.

. Для оденки слоншости предложенных устройств использовался метод шдсчета необходимого для их реализации приведенного числа стандартных вентилей. Проведенная оценка показывает, что наибольшей•и определяющей аппаратной сложностью обладают олок памяти - о(п2> л блок оцЗнки - o((n+k)iog2n+k(k+1 )), причем туш последнего сложность может быть изменена за счет варьирования числа к- каналов, параллельной обработки; при ' k«n. имеем o(nlo^n);-а при'к*п¿»(к2 ). Сложность остальных блоков имеет отнЬситвльно низкую скорость рцста и не превосходат о(nlog^n).

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

,.1. Анализ проектов ускорителей " размещения демонстрирует, что разрабатываются аппаратно- ориентированные методы, алгоритмы, а также 'аппаратные модели задачи размещения, однако введу наличия цэлого" ряда противорэчивых требований, предъявляемых к акселэ'раторам проектирования и, особенно, конструкторского этапа, отсутствуют достаточно аффективные разработки, обеспечивающие удоаютвораниэ всех предъявляемых требований. Проведенная классификация, учет выявленных требований к ускорителям разметания и выработанных рекомендаций -. по их удовлетворению, позволяют ■ обеспечить разработку эффективных аппаратных ускоритеJB3 для поддержки и реализации алгоритмов размэщвнил.

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

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

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

5. Варьирование ширины доступа к памяти на основе рассмотренных коделэй и структур, данных, вместе . с радом разработанных блоков оцэнки позволило обеспечить вырьированмэ параллелизма обработки, и, таким образом, предусмотреть возможаость для ее согласования с имеющимися штрэбностяш, и ресурсами. Особенности организации, модальность структуры, интенсивное использование элементов памяти • и ' регулярность хНаяЗолве сложных блоков обеспечивают удовлетворение требований Й}С я СБИС реализации.

6. "Разработана программная подсистема , исслэдовательской САПР для IBM-совместимых компьютеров для экспериментального исследования комбинаторных алгоритмов размещения, позволяющая варьировать основные параметры данных . алгоритмов '(функции генерации решений, цэлэвыо функции, функции принятия решений} ,'и контролировать их эффективность.

. ГОБЛИКАЦИИ ПО ТЕМЕ ДИХЕРТАЦИОННОЯ РАБОТЫ .

1. Рыбалъчэнко Н.В., Глушань В.М., Ярных В.В. Сравнительный анализ двух пдходов к построению аппаратных- раэмвщаггедвг // Вопросы радиоэлектроники. Сер.: Электронная вычзкштгальна'я

техэика.- 1992. Вып.1. С.18-28.

2. Рьйальченко М.В., Глушань В.М. Эвристика ограниченной последовательности для задачи размещения //-Интеллектуальные САПР. Таганрог, 1994.Вып. 4. С.117-118. .

3. Глушань В.М., Курёйчик В.М., Рыбальченко М.В. Аппаратный ускоритель линейного размещения стандартных элементов // САПР-92. Новые информационные технологии в науке, образовании и бизнесе: тезисы докладов международной конференции и школы молодах ученых. И■ специалистов. Воронеж:ВПИ, 1992.: С.171-172.

4: Йлбальченко М.В. Аппаратный ускоритель линейного размещения стандартных/макро элементов.// Интеллектуальные САПР. Таганрог,. 1994'. Вьш. 4. С.100-105.

• ■&. Рыбальченко" М.В. Аппаратный ускоритель линейного размещения ■стандартных/макро элементов с возможностью учета-загруженности рабочего поля // Тезисы 'докладов . Всероссийской 'научно-технической' конференции "Интеллектуальные- САПР-92". Таганрог,. 1992.. С.47." • .'-•„'

- б. Рыбальченко* Ц.В., Глушань В.М., Курегчик .В.М. и др. Устройство, для ' оцэнки линейного размещения элементов. Положительное решение от 24.04.92 по заявке, на патент fl?4926572/24 от 8.04.91г. ' . • ■ "

■ 7. A.c. N 1388887 СССР, МКИ G08T15/20. Устройство для перебора сочетаний, шрестановок. и размещений / Глушань З.М., Рыбальченко М.В. - Опубл, в Б.И., 1988, N14.

8. A.c. N 1305702. СССР, МКИ С06Г15/20. Устройство для перебора сочетаний / Глушань В.М., Рыбальченко М.В. - Опубл. в Б.И., 1987, N15. .

9, A.c. N 1264198 СССР, МКИ G06F15/20. Устройство для шребора сочетаний / Глушань В.М., Пупков М.И., Рыбальченко М.В., Щербаков Л.И. - Опубл. в Б.И., 1988rN38.

В работах, опубликованных в соавторстве, лично Рыбальченко М.В. принадлежат следующие результаты- в работе СИ предложены метод обработки и организация устройства для оцешси размещения, проведена сравнительная оценка его эффективности; в работе 121 разработан адаптивный алгоритм ограниченной последовательности для задачи размещения; в работе [3] предложены организация и