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

Министерство общею и профессионального образования Российской Федерации

«-Г- РГБ ОД

5 3 1 МАЯ 2303

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

Оранов Александр Михайлович

КРАТЧАЙШИЕ ДОПУСТИМЫЕ РАЗБИЕНИЯ В СИНТЕЗЕ И КОМПОНОВКЕ СХЕМ ЛОГИЧЕСКОГО УПРАВЛЕНИЯ

Специальность 05.13.0) -«Управление в технических системах»

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

Томск - 1999

УДК 519.71

1'аСхуга выполнена в Томском I осударственном университете

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

- доктор технических наук, профессор Корикоп Л.М.

- докггор технических наук, профессор НогреГчгой IJ.K.

- доктор технических наук, профессор Тиердпхдебоп H.A.

Исдущая opt ашпания: Попосибнрскнн государстпенммй

к-чнический университет (ИГ1"У)

Защита состоится " " 1999г. u i1! час.

па нссдании спепиалишронанпию coucia Л 06.1.5.1.03. Томскою нкударсшешюю уннпсрситета но адресу: 634050, Томск. Ленина 36. гел. соиега 41-56-40

С диссертацией можно о шакомип.ся в научной Сиблноюке Томского rocyiiHBcpcHicia.

Лпторсфсрат разослан * /7 " 1999г.

Ученый секретарь с1!сциал1пиропаиного совета кандида! фш,-маг. наук, доцеи г А 7 Тривоженко Ь.Ь.

ь

ЪЖЛ-OteA-OLH .о ч- чт.Ш-01» ы п

ОЫЦЛЯ ХАРАКТЕРИСТИКА РАКОТЫ

Актуальное п. проблемы. Сшиеч и компоновка схем логическою управления - ео-;iaimue чает процесса проектирования yciponcm логическою управлении (УЛУ) ма юй или иной Члеменшой и коипрукгипной баче. В целом нроекчнрпилнне любою ¡оривнальною yeipoiicu<a предсчавдяе! собой сложный коммлькс рачднчною рола »¡tfioT но преобрачонапию технического чаданнч и полный комплект документации на i :l оюнлилие и -зкеплуашцию усфойсиы, мчаепчо невыполним).i.\ и сжаше сроки и о фиемлемыч качеством бсч применения системы атома мпнропашюю проокшрованим САПР) УЛУ. соч,чан;п:мой па баче ередечв iiu'iikviiiicimmh icxuhmi. CAIII' УЛУ »»-i".eien современным инефумепюм проектирования и причг.аиа обеспечить быечрое и сачесчветше проектирование конкурентоспособных устройств. Происходящие ич метения элементной и консфуктинной бачи yeipoiicitt част приводит к существенным гшепеиияч в характере и содержат!и работ по их проекччтропатпо н, как следетие, к и-обходимосчи существенной модериичации CAÍ И1 УЛУ, что чаме;ыяет процесс со ¡да-шя новых устройств на ноной »лемешной и конструктивной баче. Сшпеч а компонован схем логическою упранления. как составные част процесса проектировании УЛУ, чоисалуй, в наибольшей степени подвержены ичменеиням при ичмененин элементной и лчилрук-ткиой бачм УЛУ, Изменения мой бл;м ведут к .необходимости новых nocra-loitoK задач сишеча и компоновки схем и к необходимое!и разработки новых методов, > иортмов и компьютерных протрачм решении чшх задач. Нот почему сочданис до-'jaio'iHo общею подхода к решению чалач сиитеча и компоновки схем логического травления на сч,ч:рсмежкш мечеишон и конструктивной паче, учитывающею текдеп-чин ее развития. позволяющего быстро и "технологично" разрабатывать на его основе >ффективные алюритми решения лих чадач и обеспечивающею таким обрачом оито-лиелытую устойчивость САПР УЛУ к изменениям -ной бачы, нил.чется вполне актуальной проблемой.

J.¡ последние дссячнлсптл ->.1ементпа;1 бала устройств лотическою упранления при ччиоснтльной сгабильтюеш их конструктивной базы прошла в своем рччвити п^ть от ые.чептов малой ciencini шттстрацин, примером которых мотуч служип, 0ic4ccjiseniujc интегральные микросчсмм серий К133, К155 и т.п., до интегральных микросхем большой и сверхбольшой eieiieini ищет рации, i.e. До 1Л1С и СЬИС, с()еди которых видное место занимают программируемые лошческис ншет рхчытые схемы (ПЛИС) или, дру-I ими слонами, про! рамдшруечие пользователем логические устройства - Field Рюцг.ишиаЫс L<>(i¡c Dc\kc.v (H'LD), в юм числе ¡акие их ра:шо»шшое1И. как ii|K>-|ра\|\шр>е\ч.1е лошчеекие м.ириш-1 (ПЛМ) - Programmable I.ogic Arrays (I'I.A), про-[рамчируемые шкчпяиныс чаиомииающис упройстпа (ШПУ). или просто (ПЧУ), -l'ri>t>ianiiiiuble Kt-i.l Only Мсшог) (l'UOM) и нрицммкырусмис мафины лошки [НМЛ) - lYugrajK.iubK' Array lai«ics (I'AL).

Опюсичельиая счапнчыюсп, консчрукчивиой бача состоит в том. ччт> набор ocikturn .ix хараклериешк юю или иною сонрс.мсшюю кипсфумнвжч о учла, лссмо|рл на мшшапоричацию, сгаидарипацию и унификацию, осчасгся таким же, как и десягнле-Н1И начал, и включаеi uikNe хлракмсрисшки. как вмес|имос1ь учла, число его внешних выводов (кошакюв в рачг.еме) к номспк-чагура (члемеитый cocían) уга. Обобщающим ноюггнеч для обочначения всею многообрачня коистру1ствных учло» обычно служи i понято "ячейка". 1'ахчичаючся ячейки двух гииов: 1) ячейки ограниченной гчсстмосж п с oíраиичеииым числом гч.нюдоп и 2) ячейки с чадаппым элсмекгным ои-ынкч (». t:i.r,OHioH иоменкл.иурии) Примером ячеек первою lima Moiyi елужии.

-1-

•птопмс -»ломоты чамеиы (ТЗЧ). панели. рамы. сюнки и т.п.. а примером ячеек nropori lima - микрчсхсмы серий К1ЗЛ. К155 и i.u.. а также Ga.ioin.ic ячейки па криекыле. со cian.i4.Hin.ic in пескоммушронанных комнопеш - транше lopon. pcntciopoii. диодои i I П. Кроме ТОГО, VcYIOftHO, ЯЧСЙМЖ С ЧЛД.ИШЫМ "V1CMCUПН.!\1 СОС ГЛИОМ МОЖНО СЧНППК ЯКУ uvio площадку с посадочными шеллами различной (ь часшоаи. прямоуюлыюп) фор мы н кмлрагури. а также любое помещение с оюеками рлтлпчиой (и частости, прямо >|оЛ1.иой> формы и кчоа|уры.

Чадачл сшгк-.а схемы логического управления в -«данном vicmciiihom fvmiee со сю(п к построении hi ччеменгоп -чого Скписа наи'тучтей r то« или ином смысле с.чсмы, рсалидующей ¡аданпин операюр, исходи т юй иди иной формы его описания Ii'V.Mo;.rmi.t различные г.лрн.шп.г (частые случаи) "»той чалачи. отличающиеся друг oi jipyia и л.I оа лисом. или кри юрнем качесша схемы, или ишом ехемы. или исходной фермой списания онера юра схемы.

1адача комионоики прои шольной схемы н ячейки чадашют конструктивною 6а-■;нса cucl.nu » н.ыдччшем и юм иди ином смысле распределении зюй с.чсмы по ячейкам 't.iviniioio Схг'.иса. Оочможиы различные мришгма (частые случаи) пой члдачи. о1.1НЧ.1к»;;шс1.я .чрм о! дриа или крикрием качесП'.л распределения (компоновки), или 1Ш!лм ".:v!.4!!in.!v ячеек-.

В днеесрыпии » качестс члемешои чадаптмо о.киеа и чадаче сишеча наряду t ШП'С укачанных нише paiiioniwnooicii допуекаюкя причисляемые к иим программируемые матрицы пешилей (ИМИ), критерием качеетнл сииic.iipveMoii схемы является число .ыемсиюи « ней (чем оно мсш.шс. 1см ,i)'iuic схема), а исходной формой описа-ннч оператора схемы с/тужит система канонических Ypaniicimii. представленная системой ДМФ оулелыч функций oi раинченион параметрами оа чиспых IIJIHC сложности, Выделяемое гакнм оора-.ом мноюобра'.не парнантоп чалачи сишеча. вместе с уже ич-nccmi.lMit нарнан 1ами ной члчачи, иключае! и некотрые впервые формулируемые па-риашы. и м>1иры\. a oi.nrme 01 inneeim.ix, Ci.v.iic cvcioui ir. нескольких. « юм числе р.пнопшных И.'НК". с р.тиичпмми тначсииими cvoti.x параметров и число принимаемых но внимание парамефо» базисных ПЛИС, а ткмсс параме!ров опера юра син-тстнруемой схемы, тсорешчески не ограничено. В чл.тпе компон<т.кн в качестве ячеек Чаланнот копсфчк 1 нмнч о батнеа допчеклкчен ячейки камч о-лмоо одного Hi двух укаыимых ы-пас ишон ячеек и кршерием качеста компонопкн .¡¡и.'-ичея число '«прачечных ячеек (чем оио ченмне. юм л\Ч1Чс комноноккл) Ны.челчемое гакнм портом миоюооратс ьарм.шюи ладачи мтиоисч-.кн. иар>и> с уже и шестыми вариаша.мн той -млачи. кключаег и иектюрые пперпые формулируемые париапты. в которых, л oi;tH4MC 01 ИЧВ0СИП.1Х. консфчкнпшый o.toie 11 с-|учае кимноноикн схемы и ячейки о'.рапнченион «месшмосш и с 01 раничепным числом пыг.одог. сосюш in нескольких ячеек, различных но таченням спонх iiapaMeipoii и число принимаемых но внимание иарамсфои Gdiiictiw.x ячеек, а |акжс илра.мефин пдемешои компонуемой схемы, и общем случае IwpcniMccKH не о|р;шичеио. По cymecim- псе иыле.чеипые париашы чадач chihc'u и kumiiohoiimi схем шл,но1ся .,i.i..4.ivia равнения конечных мпожесш на минимальное число дончешмых » юм или ином смысле иодмножест.

Цс.'И, р.пниы — cortaiiMe попилч подхода к решению иееч »ылсменны.ч парнаннч! зхич кишела 11 компоновки wxc.m 11 демонаip.iiiii/i >vii».hiiioi4 применении jioio подхода к решению негторг.гх ir; них с носдсдуощей оценкой ею мрфе^птност г. кмч-дом конкретом случае.

Методы исслсч'Ч'ания. Для доегиження поставленной ноли иенодьчукггся средечка иеюды дискретом матс.машки (юории множеств, булевой аЛ1ебры, ма(ема шческой гики, комбинаторного апалнча, теории сшпеча управляющих систем), теории рсляцн-пых бач данных н чеории /V/'-»олноил.

Научная иови-'.на. Для всех выделенных варнаиюв чадач анкета и компоновки :м предлагается слипая математическая модель - оршинальпад комбипа юркая он-ми ¡анионная задача кра>чайшсго дощстмого рачбиения (ЧКДР) конечною мно-•сгаа (набора ойьскюи), ь рамках цок-рой камсдий конгрсшыА вариант формудируе!-( н|»еде»анлме|ея) как нодчлдача (частым случаи) ЧК'ДР- При •мом кп'ньнк*». бы рач-чш.и варалии ;.1дач сшне'.а и компопосьн схем шичда прсдскпиякися в нале од-н и той же нодчпдачи ЧК'ДР. ')гим ки.'шпсп.т нодгверж.члетх'Я н нроясняетоя в мско-:>их дс1алях выскачапкис и лщсртуре ¡Параной С,И., Скляров В.А.) предположение о мбпппториом сходстт.е ".аД-1Ч сшпеча и компоновки сх'ем. Среди возможных меточоп неннн ЧКДР, тдьич как мшод 110.1110111 перебора, мечоды 0-1 ир<>1 раммиронания, ме-1 ис!ьей и 1раннц и мегод сокращенною обхода дерева поиска (автры: А) ибало» I. Ьеляев НА), «р| умеитировчнно выбирается последний, начинаемый далее для пкост 7-иеюдом, н ;>ка:>.ывам1ся оршнпальние способы сю ад| оршми чаиии ири-пилельно к пекотрмм под чадачам ЧКДР, имеющий! прикладное чнлчеиие. Тем елям нре;ц:и;Ш)1с.ч, как правило, ючпые ори1 инальныо алюритмы решения :чих нодча-I ЧКДР н р.ссх сводимых к ним варнаими -«»дач ечтея и компоновки схем. ЧКДР, Т-год е.,' решения и способ сведения к Чк'ДР (представления в виде ЧКДР) тою или ою варианта надачн еишеза или компоновки схем составляют суп, нрелкн аемого нею подхода к решению широкого класса тлдач синтеча и компоновки схем. Этт чход, по сравнению с иавссшыми, позволяет шире и полнее кснолыочаи. вочмож-:И1 современной чдемеинюи и коиарукшвпои бачы для повышения качсстг.а ироск->уемых Услройст и можег служим» основой для ра<ра<м|кн »ее нотах и ношах спинных (осиоп.птыл на 7-мс1оде) одюртмо» сите и и компоновки схем ири еохра-1Ш1 современных |ендепций рачки шя члементной и консфукгимюи бпчы, в ч.чеч-лн, при сохранении н состве члемепшой бачы усфойст "РА1.-подобных" функции ii.hi.ix блоков, как ого харакюрно для рачглпня КИС СП.О-ссмейета фирмы I-1NX. Кроме того. есп. основания нолага п., 'по он применим не только н проеггнро-1ин \cipoiiciu ло1 нческою управлении. Полученные в рабо|е резулыаш но решению 1К1'е1Ш.1Х тюдчадач ЧК"Д1' и, следовательно, иссх сподн'тых к ним вариантов чадач нема и комноновки схем дсмииофирую! собой примеры успешною применения но-подхода в проектировании УЛУ. С применением среден» и методов теории Л7'-нюи.г исследу^К'Я сложноси. всех с(|юрм\'лиров1)нных /годч;илч ЧКД1' и кичссшо :;|/ЮЖс1ШМХ алюршмои их решении. В процессе чюю иссдедоч.шиа дополшпелыю исняется, чю сформулированные в диссертации подчалами ЧКД1', п гном олсрсд!,, Юржат нодчадачи, жиивалешные гаким итнестиым чадачам, как У11АКОНКА В ^ГГГ-ЙНКРЫ, .\ИШИ\Ш1ЫКЖ ПОКРЫТИИ, О МАКСИМ \.'1Н(ОМ ПАРОСОЧР-ПИИ I! ГРАФК и др.

ОСоу'.К)|,.ы1К1С)¡, Полуниных в днесср1ацШ1 ре '.уи.июи сосюш в 1и.м, чю все они ирукнея на 1сорсмах и утисрждениях. докачынасмых с исиош.чонаииом аин.чрша л.решой мшсманжн Теории множесш, булевой ал!сбрп, маиматческой лошки, (бинаюрного апалн'.а, теории сшпта управляющих усфой'.чп), теории рслипнои-х бач данных и 1сории д'/'-нолноп.!, и при чюм нскоюрые ич них еще и под)всрж,/1а-:.ч чкеперим лиадыю.

) 1|мкчт!чсскля петщостт-. В целом можно угвсрждап., чго в днссергашш преллагас с я принципиально новое м;исмд щческое и отчасти иш|юрмацно1шос обеспечение с: cicmi.i авюмагнческото сим le w и компоновки схем на современней элеменшон и ко счрукчнвной базе. опюси |ельно устойчивой к изменениям нон балл при сохранен! современных тенденций ее разни шя. Все последующее изложение результатов днссс шпиц является легальном аргументацией этого тезиса, посредством систематизации обобщения резулыаюв. опубликованных ранее в 26 печатих работах и составшнш основу данной диссертации.

Реализация полученных резулыа юн. Все полученные в диссертации резулыа! можно раздели п. на дне част: 1) результаты, полученные до 1995 г. и нослужниш заделом для получения (ранга РФФИ, и 2) результаты, полученные в течение 1995-19' j л., при финансовой поддержке РФФИ (гранг 95-014)0705). Наиболее ранние резулы 1Ы по компоновке схем в ячейки с заданным ~>лемекшым составом, относящиеся к не »»•■>" чает, были реализованы и САШ1 УЛУ ЦКБ "Алмаз" (i. Москва). Следующие ними (по времени получения) результаты по сишезу одноярусных комбинзпнонш схем п различных базисах ПЛИС типов ИМИ, 1ПУ. 1U1M. тик.«с относящиеся к нерп част, реализованы в настоящее время в виде "жепернменталыюй распределен!!' ("ДПР. в котрой подидача ЗКДР решается на удаленном компьютере высокой прот нодитедьности. а сведение задачи синтеза к подзадаче ЗКДР и преобразование по; чаемого or удаленно! о компьютера равнения набора обьекмп в схему осущссгеляс! на местом компьютере меньшей производительности. I Ipoi рамча p,t ióhchhm п cocui ной САШ' (иротрамма решения подзадачи ЧКДР) неньпапа на нескольких дссиiх примеров различной сложпосш. в том числе, соответствующих примерам си теза у> ройсгя реальной сложности и так называемым "benchmarks", чю юворит о Ирак ческой пршодносги ной протраммы, Ре зуль тати, о (Носящиеся ко второй части, о rj жены (реализованы) в нромежуточных н итоговом о|че nr. по i ранiy, одобрены РФ<1 it рекомендованы им для использовании в промышленном произволе тс УЛУ.

Апробация работы. Все результаты. составившие основу диссертации. но мере получения обсуждались ца совместных семинарах кафедры матемашческой логикг проектирования. кафедры программирования Томскою юсударстиснною универсии ( П'У) н лаборатории синтеза дискретных авюиаю» Сибирскою фнзико-тсхничесм института (СФТИ) при ГГУ. Кроме mío. в разные юды они докладывались па все Ь'зпмх или международных конференциях в г.г. Риге. Киеве, Москве. Минске. Ново бщккс и Томске, чю подтверждаемся с<хт i но ici пуютими публикациями докладе»! тезисов докладов, указанными в конце автореферата. Прохождение opiciikvih по . пии РФФИ и частичное использование результатов лиесер|ации в учебном проке ирк подготовке студентов coonieiciityioinux специальностей в 'П'У также можно с тать апробацией .тиссср(анионной работы.

Структура и обьем лиссегнации. Диссертация состоит из внедения, восьми глав, ключения н списка нитрованной литерагуры. Обт.см диссертации составляет 200 ci ниц текста, набранною в Word 6.0 (lllpiujn - Times New Roman Cyr. размер тнрнф| 14 pt. межстрочный интервал- 1.5 строки), в юм числе, жтульный лис! - 1 стр., on ление - 6 стр., основной текст, включающий 6 рис. н 12 таблиц. - 183 стр., библиот фия из 76 наименований - 10 стр.

-1-

ОСНОВНОЙ СОДЕРЖАНИЕ РЛВОТЫ

Но впадении. почт дословно отраженном u автореферате, определястся место н тчтшостъ рассматриваемых в работа задач спится и компоновки схем логическою ip.-тлепия в eociaiie более общей проблемы автома зиэацни проектирования устройств л ического управления. Выделяется широкий класс задач сшиаа и компоновки схем иического управления на современной элементной и конструктивной базе посред-•ßo,\i конкретизации jюк баш, способов задания оператора схемы и самой схемы, а нокс крн ¡ериев качссгиа синтеза и компоновки схем в задачах. Кратко анализируется ютоянне решения выделенных задач. Формулируется цель работы, состоящая и созда-Iin общего подхода к решению всею выделенного класса задач и в демонстрации пеншого применения ею к решению некоторых из них. Перечисляются избранные мдетва достижения этой цели. Характеризуется научная новизна предлагаемого на rtmne избранных средств общего подхода к решению выделенного класса задач, а 1К'.;;е новизна и практическим ценное!], полученных с его применением конкретных пультатов. Приводится краткое неформальное изложение содержания работы но гла-»м.

П первой главе дастся обзор методов синтеза цифровых схем на базе ПЛИС и мсто-:т компоновки произвольных схем н ячейки указанных выше типов. Многие нз этих столов к настоящему времени системашзкрокашл (("проанализированы в нескольких опографнях. 'по в значительной мере облегчило этот обзор. Из обзора следует, что шестые вариаты задачи синтеза схем на базе ПЛИС чаще всею формулируются и лшпогся в рамках матричпою аппарата, провоженного А.Д. Закревским, как правн-

приближенно и элементный базис во всех этих вариантах состоит из одной ПЛИС :ч о или иного тина, не все параметры которой принимаются во внимание. В последнее ре.мя в литературе разрабатываются гак называемые генсгическис алгоритмы синтеза кем на базе ПЛИС (Holland JH., CioMhcrg D.E., Soldek J., Yanushkevich S.), также не фангарующие получение оптимальных решений и являющиеся но существу алгорит-и.ми локальной оптимизации. •

И шестые варилии задачи компоновки схем, как и варианты задачи синтеза схем а базе ПЛИС. i:ik>kc чаще всею решаются приближенно (Штейн М.Е., Штейн Ь.Е., 1слнхон Д.!!. Ксрппейн Л.С., Курейчик D.M., Ландау И.Я., С елку пи I В.Л., Н.панабэ I., Лсада К., К'аии К., Hpeiiep М., Фридман Л., Менон П. и др.) несмотря на принцшш-jK.hvio возможность точного решения некоторых из них методами 0-1 программировать методом «стаей и границ и т.н., связанную, однако, С большими вычислительными рудное 1ямн. а также с трудностями алгоритмизации этих методов. При этом комгто-уема.ч схема обычно рассматривается как граф, вершинами которого являются олемен-м схемы, а ребрами - связи между ними, и конструктивный базис п случае комнонов-и схем в ячейки ограниченной вместимости и с ограниченным числом выводов сосзо-I.' из одной ячейки, доя которой иногда принимается во внимание только один из двух с параметров - либо вместимость, либо число внешних выводов.

Вместе с т\:м Барановым С.И., Скляровым U.A. в их совместной монографии выека-аио предположение о комбинаторном сходепте задач синтеза и компоновки схем на опременной элемешной и конструктивной базе, послужившее в какой-то мере оитрав-ioii ючкой предпринятых в диссертации исследований по созданию общего подхода к ||'шеииго широкою класса эптх задач и разработке на его основе оригинальных, как травило точных, алюрнгмов решения некоторых из них, полнее, по сравнению с из-

несшими. использующих вотапжиояи современной элементтюй и конструктив!« базы ;ия уменьшения числа затрачиваемых ПЛИС и ячеек, а также стоимости схем.

Во второй i.i.Tpe формулируется задача кратчайшего допустимою р.пбиет ПКДР) набора объектов. ]) пен рассма1риваюгся: разбиваемое множост

AçzD-D.......... допускающее множество BçjZ-E, ■'•■■•Е„, где D и Е декартовы npov

ведения конечных множеств элементов произвольной природы, т,п> 1, бинарное otti ■некие г на Е и допускающая функция f.D—уЕ из О в Е. где 1У - множество не подмножеет множества О. Подмножество Cçz/1 называется допустимым для В, или допустимым, или просто допустимым, если 3beB(/(C)rb). Разбиение R множества называется допустимым ятя И, или //-допустимым, или просто допустимым, если ка; дый класс (блок) C.'eR являстси допустимым для В множеством. Допустимое разбиен: H множества.-! нтыпастся минимальным для В, иди Д-мипимальпым, или просто м яимальным. или кра iчаишнм, если |/i|i[/i'| для любого //-допустимою разбиения множества.-!.

С laïuncM ЧКДР следующим образом: jv 1я заданных Л cl), BcJi, fi D —>E, r пай™ , минимальное (кра piainnec) разбиение множества Л.

И приложениях множества Aç.D и Bç.E предда1 астся рассматрнпап,, в соотвстспп с реляционной моделью данных, как ошошепия и B(B\,...J3„)çE роляц

oinnu'i базы данпык, представляющие собой наборы объектов с агрибутами

В,.....Вп. определенными на доменах Dt.....D„ и E),...J''„ соогастственпо. Отошени

иредстав!:(ЯЮ1цее набор обьскюв, отождсстлястся с ним набором объектов и рлссма pni'.AcicH как таблица, строкам которой сопоставлены объекты, столбцам - атрибут >nt\ обьекгов, а >лемеп1ам — значения афибуюв, еоошстствуюшнч' столбцам, для об смон, соотетствующи.ч строкам. Таким обратим, любой тлемеш /е.-!, рассматрнва мый как объект набора A(At,...jl„). однозначно определяется (задаспл!. характеризуете

с<кчнетстуюшнмн значениями а„.....а,„ своих атрибутов ____>!„, и предстаилястся

таблице Л(Аи-.-Лт) кора-жем (строкой, вектором, дошчеекой записью, наборо;

Точно ыкже. любой элемент /еВ. рлссма 1риваемый как объект набо] Ii(Bu...JÏ„), однозначно определяется (задастся, характер»тустся) соогвстствуюпии значениями bji,...,ft,„ своих лрибуюв В\,...Jl„ 11 иредстапл.чстся в таблице В{В\,....В

кортежем bji,....bj„ -. Совокупности /(» {«и//;».....ark\ и В/ jhtl,hu.....знпчепнй а

рибуюв Ai н В/ (столбим Ai и Н) таблиц . ¡(Л,„..„!т) и Wh.....В,,)) для к / 1,...,

/! (,-I| h (¡'Щ рассма фивавнеи как множества, тлемешт.г r коюрыч- (r том числе и од

ii.ikoki.ic) различаюим кч номерами I.....р и I.....q соогвстствепно Возможны различна

приложения 'ЖДР. !i частности, к ней сиодяия mhoiuc вяриашм задачи сшпяа мин малинах по числу -.».теменюн схем па базе ПЛИС и задачи компоновки произвол,нь с\ем в минимальное количество ячеек (конструктивных узлов), различных но вмест мости и числу выводов либо но -»лемешному составу. Yinot ообразие -ник вариант« наряду с уже- известными паркингами натканных залам, содержи i некоторые их парна Ii.i, впервые форм; лнруечыс н днсссртанчонноГ) рабою. I' них варнашлч. и 01личне i большинства извес.'ных. нрнпнм;н<>1СЯ во внимание вес необходимые параметр (.tipuovii.O aJicMv.il 1ов (oûi.'.kiob). как рав'иваемо!v», гак и jn.HNCkaioiueiо множееша. допускающее множество состчт ш иеско.п.ких vieMeiuw. (обиекюи) различии^' ! типу и.1.1 1U) значениям июих нарамстров (aipnôyTOB). Примениicui.no к" еишоу с;.с на базе НЛЖ , г. качеств." »лемецюв (обьекюв) множества А обычно выступаю! ДМ булевых функции с шкнмн а|риб\тамн как номер ДПО>. множество букв в ней, чнс.1

-б-

[ъюнкдий (термов) и т.п., а в (качестве элементов (объектов) множества В - ПЛИС анного базиса с такими атрибутами как число входов ПЛИС, число выходов, число межуточных (Iоризонкиьных) шин, число макроячеек и т.п. При этом функция / шеляет сложность подмножества формул (ДНФ) С и определяет возможность реали-ии этого подмиожешва на одной ПЛИС Ь заданного базиса В в случас/[С)гЬ. Прн-гителыго к компоновке произвольных схем в заданные ячейки, в качестве элементов ьектон) множества А выступают элементы схемы с такими атрибутами как номер мен га в схеме, множество "окрасок" его полюсов, число входов, оператор и т.п., .1 в ествс элементов (объектов) множества В - заданные ячейки .с такими атрибутами вместимость ячейки, число ее внешних выводов, элементный сослан и т.п. При этом ■кция/вычисляет размер подсхемы С, число ее внешних контактов, элементный сов и т.п. и определяет возможность компоновки этой подсхемы в ячейку Ь заданного «руктшшою базиса В в случае/(С)гЬ.

Обсуждаются возможные методы решения ЗКДР такие как метод полного перебора, оды 0-1 пр01раммиропаиия, метод ветвей и 1'раниц и метод сокращенного обхода ева поиска (Г-метод), что молено рассматривать как продолжение обзора методов пвза и компоновки схем, ибо по существу рассматриваемые задачи синтеза и комгю-ки схем являю пен задачами разбиения множеств. Среди возможных методов реше-г ЗКДР аргументированно выбирается Г-метод. Применительно к ЗКДР, вершинам ева поиска в Т-методе сопоставляются подмножества У разбиваемого множества А, ¡чем само множество А сопоставляется'корню дерева, а пустое подмножество - его тьям. Ребрам дерева поиска сопоставляются допустимые подмножества множествам! иссы допустимых разбиений). Множество, сопоставленное концу ребра, являегся иоегмо между множеством, сопоставленным его началу, и множеством, сопостав-ным самому ребру. Допустимое разбиение множества А сопоставляется пути в дере-13 корня в лист. Про такой пун, говорят, что он несет разбиение, или разбиение него путем. Всевозможные пути в дереве поиска из корня в листья несут все допусти-е разбиения множеств Л. Сокращенный обход дерева поиска осуществляется в про-апстпе всех допустимых разбиений множества А, несомых всевозможными путями корня дерева поиска в его листья, и представляет собой общий алгоритм поиска с вращением и сохранением более короткого разбиения. При этом значения раження) параметров Г-метода (множество р быстродействующих алгоритмов, ис-(ьзуемых для построения начального разбиения Л0, алгоритм <р перечисления всех геимальных допустимых подмножеств в УоА, образующих множество <р(Т>, опера-[ Чу сокращения множества <р(У) и граничная функция /"¡/К) отсечения поддеревьев с нем / без потерн решения) служат средствами ускорения поиска какого-либо одного тчайшего разбиения множества А и являются по существу различными инструмен-¡и (механизмами) сокращения перебора. С помощью этих инструментов в дереве по-а выделяется (строится) то или иное достаточное поддерево, т.е. поддерево, содер-цес хота бы одно кратчайшее разбиение множества А. Остальная часть дерева поис-яз рассмотрения исключается (отсекается, не строится). Значения (выражения) пара-ров />,(/>,Т/'|//'-метода называются подходящими к ЗКДР, если в их определении и в тановкс последней условия допустимости подмножества СсУсА совпадают и, кро-того, выделяемое с их помощью поддерево в дереве поиска является достаточным. Таким образом, для решения ЗКДР 7'-методом надо подобрать подходящие к ней чения его параметров и нодегавигь их в его формулировку; полученный в результате

.1 >г оритм ('/'-.ии ори |м I и будет а.'П орщлюм решения ЧКД1\ 1л о тффегшшгостъ и вмес V ней практическая цепносп. опредсляююя. очевидно. сокращающими способности] шиобраниых'.начешш параметров 7-метода. т.о. степенью бличостп доставляемою г юрнтмами множества рачбнения 1{„ к кратчайшему рачбиенню. степенью точное оценки / 'г, и оспсцыо удаленное! и ¡'¡'(^ХГд 01 числа всех лонуежммх подмножес!В в содержащих фиксированный 'хкмеш. а также 1см. насколько быстро строится /?<,. и •л' \чяе!ся /'И'") н выполняются алюритм с/7И операции Ч'.

П диссертации решить ЧКД1' в иолом. I с. подобрать подходящие нетриштальн ".начення параметром /'-метода. п сл\чае ттроичкольных А Л/.г. не удалось. Потто <>еу шее тлено обычное и таких случаях разделение задачи на более нроеше час (ьод '.адачи). Такие подзадачи ЧКД1' можно выделяй.. накладывая те или иные отрлт ченн.ч на (фиксируя те или иные значения) А Л .Кг п ЧКД1' и выстраивая таким обрат IV или иную иерархию под'..ил ч ЧКД1\ Иначе юноря. процесс построения иерарх но.палач ЧКД1' не является одпошачиым и может (ii.ni. продиктован рачличпыми со< ражепиямн. И диссертации он диктуется приложениями к проек 1 нроианит УЛУ прежде всею, задачами сшпсча н компоновки схем на современной элементом и к< с|р\к"1Нвпой 6.по. ('начата, в предположении, что г является отношением частичш и.)()Я.(ка на выделяются две наиболее общие подзадачи Ч1СДР: Чк"; Ц' с моногони допускающей функцией / и Чк"Д1' с немонотонной /. Именно к -ним ЧКДР сводягся ! рассматриваемые в д^ееерыпни варианты чадач синтеза и компоновки схем на сов \.е)ншой элементной и конструктивной оаю. Для ЧКДР с монотонной/ирехинаю ич,-<\'".(х11111с иегршмыльные ¡тмчетшя параметров '/'-метода, Геи самым иредчагас тчнын /-а.н<<¡>111м решения эюи задачи и, следовательно, всех ее подзадач, а пн )'.ссх сводимых к ним ыд.тч ежметп н компоновки схем. ЧКДР с немонотонно подоорап. такие значении параметров У-метода и предложил. таким образом точный а.и ори 14 се решения не удалось. Чатем. дальнейшей конкретизацией А.В./.Г с цс.] подбора более зффекдштних значении параметров 7-мегода. выделяются некого^ поды.тачн чи\ лв\х МчДР. имеющие то или иное прикладное значение и т.д. В И1 нид\ чается иерархия подтадач ЧКДР, большинство и 1 коюр[,1Х ниляююя нод'.адачг Чк'ДР с моноичпюй /.

При определении шичеиии (выражений) параметров Г-меюда дли ЧКДР с ми нчшойу предварительно (:(ля ра¡решимости "ной ЧКДР) требуется чтобы каждое од ысметиное подмножество в Л было допустимым, т.е. УаеАЗЬеН(1({<1\ Элемет 4(^-1 упорядочиваются и нчмерчкися по нетипрасглннто значений ){{а}), т.е. так, Х'а„о,е.!(/ ))<!(',а,¡с,',)«/(!</,!))). 1Лс \11у о тачает, чю х и у не срашп'

но отношению те. ~<х<у) и ) Предполагается. что введенный на Л порядок

храняотсн в любом ГеЛ'о!. Из Н удаляется всякий иомеит Ь. для коюр ! >>. в рс.удыатс получасюи пснриводнмос множества В' Поскольку всякое /("-мппнм.ыыюс рл;С>нение множесша ./ является /У-мгтима.ты рачбнением пню мможсспш. в чем но1]>\дно убедиться, то ипродь множеово И сч| сюя иенрш;од|цп.1м и предио-мметси. чю ¡.юноши в В чапчмероваиы числами 1,.. Мере, ч обо-.пачается мощность наибольшего допустимою подмножества в У. ( иодьишнели подыдач ЧКД1' с имшюшюи /. рассматриваемых а диссертации, велт па и ясна ит поскшовки чадами и лы ее получения не требуется каких-либо доио: юльных татраг) При перечисленных допущениях н условиях, подходящие тачс параметров 7-меюда ,т.1я ЧКДГ с моиоюшюи/опредсляются слсдчюпшм обратом.

Алгоритмы начального разбиения. Для получения начального разбиения /?0 мно-пъаА предлагаются быстродействующие алгори гмы р\ И Рх, образующие в Г-методе эжссгво р. Ллюритм а троит разбиение множества А последовательно класс за 1ССОМ, набирая каждый новый класс из тех элементов, рассматриваемых в заданном ^ядке, которые не пошли в уже набранные классы. Формирование класса заканчн-:тся, когда исчерпываются все элеменгы в А или когда добавление к нему любою :мснта из остатка нарушает свойство допустимости этого класса. Алгоритм ^ строит (биение Н2 также последовательно, однако в огличие от р^ каждый новый класс со-шляегея из двух таких образуемых одно за другим допустимых подмножеств С и ьедннепне которых есп> допустимое множество. Первое подмножество (С) пабнрнег-с начала множества А из подряд еюящих элементов с меньшими номерами, ие во-дтпих в друше классы, а второе - с конца множества А из подряд стоящих .эле-гггов с большими номерами, оставшихся после образования первого. Построение кдого подмножества можст закончиться, ко(да исчерпаны вес элементы в Л. В пробном случае построение С закапчивается, когда добавление к нему очередного эле-нта с начала множесгаа А нарушает свойство допустимости этого подмиожесгоа, а строение когда добавление к нему очередною элемента с конца множества Я натает свойство допустимости обьеднпения С\л\\ т.е. всего класса. За /?0 принимается из разбиений которое содержит меньше классов.

Алгоритм перечисления допустимых подмножеств. Для любою А и любою г У через <ри\У) обозначается множество всех максимальных допустимых подмио-:ств в У, содержащих аь н через/!и)с>'- множество всех тех ацеУ, расположеш!ЫХ в рядке возрастания их номеров, для которых Ык и {а,.а/,} есть допустимое множество, игоритм перечисления (р) составляют следующие три правила выделения некоторых пссимальнмх допустимых подмножеств в У, применяемые в указываемом порядке.

1. Если для некоторо! о допустимого С-{ Д(,а1( }сУ справедливо соотношение

.1), то '/<Г) (С) для а, с наименьшим / и указанным свойством.

к.....(2.1)

2. Если для некоторого допустимого С~{а/,а^}сУ справедливы соотношения (2.2), .3), то <р(Г)- {С} для с наименьшими ¡,к и указанными свойствами.

/1(^4а,*0=>Уае4и,пЛ(*)-,36 еВ(ДСь»{я} )<Ь% (2.2)

УА'е /^Уб'е <р(1\У)[К^<2^ЬеВ(М.К-Ы М'ЧйЧ ((2.3)

3. Во всех остальных случаях р()')=(г)<л(}') для некоторого о,еУ. (Заметим, что такое пожество <-ДГ) может остаться после неудачного применения к множеству У правила 2 тогда / есть либо /, либо к в этом правиле.) Алгоритм построения этого множества ()'), названный алгори тмом <р2, строит множество р1Л(}') для заданного а ¡в У в процессе травленного перебора по дереву аналогично алгоритму построения всех максималь-ых независимых (внутренне устойчивых) множеств в 1рафе (Кристофндес Н.) и по су-юс1»у представляет собой предложенную в диссертации модификацию (обобщение) оследнего на случай произвольной монотонной допускающей функции/.

Операция сокращения. Для определения операции сокращения СИ) па множестве сех подмножеств в }'сАЧ4 вводится опюшение предшествования (ос) следующим об-азом. Пусть а,, ,..., а, }сУ, { а^ ,..., а^ }с Г, /а<...</я, кг<...<кТ Тогда Сое ¿"с?

|(^2r/AVre{l,...;C/}((,<t1A('r'A:,=.VA/cí'(a,( e/feyíO'Ma,, })W))]v С

[C-S- {a,} AVfe <¿'\Y)(Sr,T-0=>3b еВ(У{(.?-СМ7-{<>,} ))<!>}) I (:

и результат применении операции 4' к мтюжсству Zc<f{Y) определяется как множа Ч'(^) -4';(4'|(¿)). где есть множество, содержащее всякое такое множество ¿

для которого в 7. ие оущссшует множества CV¿.' и CccS согласно (2.4) '¡'¡('l'iCZJJcT^Z) с en, множество, содержащее всякое такое мпожсстно Se*\\(Z), которою в не существует множества CV& и Caci' согласно (2.5) или. если а;1

í'evV¡(¿) существует, ю н SccC соьзасно (2.5). При лом С (либо S) не включаете

Граничная функция F<¡ определяется формулой /•"(|(}')~гтах(<т. г), где сг-

И Г!

мощности некоторою подмножества попарно несовместимых элементов в У, т.е. та различных и.сеУ, для которых ~,3beIS(f({a,e})<b), определяемая посредством след lucro алгоригмп.

■\л,'оритм г

1.С: Г, г. 0.

2 Если С~0, то конец, г - результат: в противном случае берем любой злем <<,€(* с наименьшим пересечением ( 'rvl1-". С: -C-(A"'kj{ci,}), г.-г» I и повторяем п. 2 4 чала.

Заканчивается глава 2 доказательством допустимости алгоритма неречиелнени операции сокращения для ЧКДР с монотонной Í. г.с. доказательством достаточно vnoaccciiií Ч'(<Х>")) ,'t'w любого 5'c.V vi.

H следующих главах 3-7 1>с>тнес1илметеи дальнейшее дробление ЗКДР с монот нчй / и ЧКДР с нсмоноюнной /.' Подмдачн лих ЧКДР выделяются последователь] юнкрсттпацнен ЛЯ./,г в них с возможно меньшей потерей приложений и с цслыо г бора более "«¡и(>ектнвных выражений (значений) параметров '/'-метода и, в коноЧ! счете, с целью более эффективно)о решения всех задач еншеза и компоновки сх сводимых к ним подзадачам. При -<том значения параметров Г-мстода для подза, ЗКДР с монотонной/являюня коикрстизаниямн .значений одноименных нарамец предложенных д.чя ЧКДР с монотонной/ возможно с некоторыми дополнениями, снижающими их.эффектииноетт.. Получаемый таким образом 7-алторшм решения или иной подзадачи ЗКДР является алюришом решении всею класса задач сшп нзн компоновки схем. сводимых к этой подзадаче или, другими словами, прелста мых в виде этой пол задачи, что является принципиально новым элементом, так как нее значения параметров Т-:метода разрабатывались в известных случаях иод одну к к¡К'тную задачу. Изложение результатов в каждой из тлав 3-7 осуществляется по еди| схеме. Сначала формулируется подзадача ЧКДР, в которой множества А и В уже дополнительных оговорок рассмафиваются как вполне конкретные наборы объект конкретти.тми атрибутами, и определился подходящие для нее значения нарамстрот метода. Доказывается донуетимостт. предложенных значении (выражений) <р и Т , этой подзадачи. Дастся пример построения кратчайшего допустимого рачбиения. пример решения выделенной подзадачи ЧКДР Т-методом с предложенными для значениями его параметров. Чзгсм формулирую гея задачи синтеза или компоно! схем, сводимые к выделенной подзадаче ЧКДР и указываются способы их сведени этой подзадаче, иллюстрируемые примерам».

ti rpen.ей главе формулируемся (выделяется) подзадача 'ЖДР с монотонной лопус-атощей функцией, называемая ЗКДР-1. Б ней разбиваемым множеством является на-юр обт.екзов ¡(¡MJ-S) с атрибутами ¡МУ- Объект в iiom наборе представляет собой оргеж <iM,y¡> значений атрибутов /.A/..V соответственно. где i - номер объекта, яп-

ающийся его идентификатором, M¡y¡ - конечные множества, i 1_____т. m~i 1. Доичс-

:агощнм множеством является набор объектов J(.f,L',!'ll'). Объект в этом наборе пред-завляет собой кортеж v-,w,'* значений атрибутов ./,(/.КН' соответственно, где J -юмер обьекза, являющийся ею идентификатором, uhv^w, - натуральные числа, 1,...,«, и>1. Для разрешимости задачи предполат ается, чго

Vi е /3; еД 1 <щл |Л /,;< iy\jV, ¡ (3.1)

люботоЛ cJ вводятся обозначения

икЛМ)

к'( /о!

i множество Л называется допустимым для Л или ./-допусгимым, или просто доиуети-tuM, если

3jáJ([4\<uf-\(J(Ay)í<Wj). (3.2) -

'албиение R множесгва (набора ибьек-шв) 1 называется допустимым д:ш J, или J-(опустаммм, или просто допустимым, если каждый блок (класс) .1 еЯ ятптяегся J-|,отгус1Нмым множеством. Допустимое разбиение R множества / называется минимальном для J, или J-миннмальным, или просто минимальным, или кратчайшим, если 'í<¡/f'] для любого ,/-допустимо1 о разбиения R' множества /.

Ставится ЗКДР-] следующим образом: для зачанныч наборов объектов ¡(¡МУ)-

¡'.И") шиш ./-минимальное (кратчайшее) разбиение множссгаа 1. Нетрудно видеть, что поставленная задача является подзадачей (частным случаем) 1КДР с абстрактной монотонной допускающей функцией /, в которой Л -¡(¡¿К/Ууг.!) >,kD2xDi, ¡i Е^ЕъхКцЕ^ и, следовательно, может бы и, решена Т-

тетодом, если определи п. значения сю параметров р,<р,Ч\1\, наиболее подходящим ;пя ice обр;иом ')ю делаося конкретизацией значений /VA'P,f0, предложенных для 'ЖДР : абстрактной монотонной допускающей функцией f.

Предварительно для каждого, i el через s¡ обозначается число собственных, т.е. не тринадлежпщих другим множествам в M~{M¡,...Mm}, элементов множества Л/, и через т, - число собственных, г.е. не иринадлеаоицих' другим множествам в N- {y¡,...ym}, етеменит множесгва Л',. На/(на множестве коргсжей <|,\/í|,j,,Mj.tr,>, n\,...,m) вводится текснког-рафический порядок > и объекты r I нумсругогся в соответствии с чтим поряд-:ом. Т>ют порядок, если специально не оговаривается, сохраняется я любом YcÁ' L Из J ■даляется всякий объект/, для которого Hfce^ííjSiíyWtSv/.Wi^ii^vV/ e/d.VÍ^VjV^Vi^io)» 8 тезультзте получается неприводимый набор объектов J'c.J. Нетрудно убедиться в тот, но всякое ./'-минимальное разбиение множесгва / является У-мннималъным разбиением этою множества, поэтому далее набор J считается неприводимым. На J (па множестве кортежей Mj,v„uy,,i/--1,...,/j) вводится лексикографический порядок < и объекты I J нумеруются в соответствии с этим порядком.

Алгоритм и .начального разбиения. Для получения начального разбиения /?„ нюжества / используются алгоритмы p¡ и />,, предтоженные для ЗКДР с монотонной/, i которых А--/, B-J и свойство допустимости подмножества в / трактуется coi лаено 3.2).

. ix-'оритм перечислении допустимых подмножеств. Для любого YçzX=l и любого I е >' через >') обозначается мможесчио всех максимальных допустимых подмножеств и }'. содержащих /, и через t"c.Y - множество всех тех к с У, расположенных в порядке возрастания. для которых i*k и {:,к\ есп, допустимое подмножество в У. Кроме того, для любых BX'çY и любых i.kv К таких, что teJi и кеС, с пелыо упрощения некоторых по-с тсдующих записей., вводится 5 (й-{/})1_<С-{к)). Алгоритм перечисления (р) составляют следующие три правила выделения некоторых максимальных допустимых подмножеств в i'cAW. применяемые в указываемом порядке.

1. Кслн для некоюрою допустимого/!: {/,/,.....it(t:>' справедливо соотношение (3.3),

I о }") J для наименьшего гакот о /.

С,.....'.I Г". (3.3)

2. i-хли ;ия некоторою допустимою A справедливы соотношения (3.4), (3 5), то <р(У) - {/1} для наименьших ¡.к с укачанными свойствами.

V/ie^'^J-JV^e^'*^(3.5)

3 Во всех остальных случаях <р()~) -<р"0~) для иекоюрою /€>". (Заметим, что такое миожеспю <р( Y) может остап.ся после неудачною применения к множеству Г правила 2 и toi да I есп. либо I. либо к в > юч правиле.) Алюрнтм построения этого множества v\t). названный ал)»ритмом (fil. чочги совпадает с одноименным алюритмом, нре.тюженнмм для ЧКДР с абстрактной монотонной допускающей функцией /? Почти, поточу что в нем дополни тслыто реалнчуечея обнаруженная возможность исключения иншшжх ветвлении вершин дерева построения всех максимальных допустимых подмножеств в I.

( h ¡«рация сокращения. Для определения операции сокращения ('Р) на множестве иссх подмножеств в J'qV / вводная не транзитивное и не антисимметричное отношение предитествовання (зс) следующим образом. Пусп. Л . В ;{ku...Jcq}QY, !,■■■■•■</,.. k-_<--<k4 н S-(/t-Ay~4('-{/}). r.'ic СсУ H leC. Тотдa A ос Во

\p>qAVle {1.....ii)(iaAU, k,~\, .\/i(-A/1(i< s4 л| Л'*, -Л'1( ¡< С,, )))] (3.6)

vl.^SH'tAVCe/'O^^G^e^.^ (3.7)

и результат применения операции 4' к множеству Zcipii") определяется как множество 'I'(Z) TS(%<Z)), i.'ic есп» множество, содержащее всякое такое множество

В?/., ,чля которою в /' не существует множества А*В и Л œ H согласно (3.6), а 4'?(T,(Z»ç:4',(/0 есть множество, содержащее всякое такое множество BelV,(Z), для которого в 4'i(Z) не су шествует множестна А*В и А<хВ согласно (3.7) иди. если такое /1еЧ'|(2) сутцсств \ег, то и ВхА согласно (3.7). При этом Л (либо В) не включается в

ЧЧХ). ^

Граничная функция Fu опреде.шется формулой F0OJmax(fc,/,/>,r), где

k f |У:'кпТ /-fуДp-ï\0(Y.N)[/mas «',1 i-j j'j

и г есть мощность некоторого подмножества попарно несовместимых обьеклов в У. т.е. таких различных s.leY. для которых {s.Ii сеть недопустимое множество, определяемая посредством алгоритма т. предложенною для ЧКДР с монотонной/

Доказывается допустимость предложенных для ЗКДР-1 значений (выражений) р и 'F, т.е. достаточность множества Ч*(^(У)). Дается пример построения кратчайшего J-допуешмого разбиения множества /, т.е. пример решения ЗКДР-1 7-мсюгюм с преддо-женными для нее значениями его параметров.

Формулируются шесть отличающихся базисом или типом синтезируемой схемы задач синтеза минимальных по числу элементов одноярусных комбинационных схем в различных базисах ПЛИС чипов ИМ В, ПЗУ, ПЛМ, еводимымых к (нредетавимых в виде) ЗКДР-1. Скачала формулируются три отличающиеся базисом задачи, в которых заданную систему D из т> 1 ДНФ D\,...JJm требуется реализовать минимальной по числу м. ¡ементои одноярусной комбинационной схемой, не допускающей объединения выходок ее элементов но схеме ИЛИ, в элементном базисе Е из п>1 различных ПЛИС при условии, что каждая ДНФ D,eD реализуема хотя бы на одной ПЛИС базиса Е. Другими словами, сначала формулируются три задачи, в которых заданную систему ДНФ D требуется разбить на минимальное число подсистем, каждая из которых реализуема хотя вы на одной ПЛИС базиса Е при условии, что каждая ДНФ этой системы реализуема хотя бы на одной ПЛИС базиса Е. В первой из них базис Е состоит из различных по значениям своих параметров ШШ/jj,у=1,...,л. Во второй, базис Е наряду с 1 U\Mj(sj,tj,qj) содержит ii'iy/.yjj). В третьей базис Е состоит из различных по значениям своих параметров настраиваемых ГШМ/г,,^), j-1 Затем формулируются еще три отличающиеся базисом задачи, в которых заданную систему D т !>\ ДНФ Dly...JXi требуется реализовать минимальной но числу элементов одноярусной комбинационной схемой, допускающей объединение выходов ее элементов по схеме ИЛИ, в элементном базисе Е из n> 1 различных ПЛИС, при условии, что каждая конъюнкция множества всех т>1 конъюнкций системы D реализуема хотя бы па одной ШШС базиса Е и входит в ограниченное базисом Е число ДНФ системы D. Другими словами, далее формулируются еще три отличающиеся базисом Е задачи, в которых множество К требуется ра 161111. на минимальное число классов, каждый из которых реализуем хо!я бы на одной ПЛИС базиса Е, при условии, что каждая конъюнкция в Л'реализуема хо|я бы на одной ПЛИС базиса Е и входит п ограниченное базисом Е число ДНФ системы IX В первой из этих задач базис Е состоит из различных но значениям своих параметров ll]lM/ij,!j,(/j), f -l,...,n. Во второй базис Е состоит из различных по значениям своих параметров ПМВ/^<,),/=1,...,я. В третьей он состоит из различных по значениям своих параметров ШШ/л,,^) и В базисных ПЛИС всех шеста этих

задач s- число входов ПЛИС, Г— число ее выходов, q - число ее горизонтальных шин и г s+t - число двунаправленных шин настраиваемой IUIM(z.g). Указываются способы сведения всех шести задач к ЗКДР-1. Например, принимая D за набор объектов 1(1,К, ДО, а Е - за набор объектов J(J,U,V,W), т.е. принимая Ц для t=l,...,m за объект <i№tjjt>, где Mi - множество номеров всех букв в Д, Nt - множество номеров всех

конъюнкций в D„ а для j~ 1.....л - за объект <j,Uj,VjM'y\ где urth V/^Sj, wfty,

представляем в виде ЗКДР-1 задачу синтеза минимальной но числу элементов одноярусной комбинационной схемы, не допускающей объединения выходов ее элементов по схеме ИЛИ, в элементном базисе Е из n> 1 различных ПЛМ/^ад). Если базис Е в последней состоит из различных по значениям своих параметров настраиваемых 1 UIM/z,,^), то для сведения такой задачи к ЗКДР-1 надо для каждого /=1 ,...,т принять D, за объект <///„/>/,>, включив при этом / в А/„ и затем, принимая WlM/^q,) за объект

<?.uj.Vj,Wf> для ]- 1.....п, положить uf rn, v}~z,, wy-fy. Принимая А' за набор объектов

-13-

/(/И\/,Л0. а базис Е, состоящий из ni 1 различных ПЛМ/Sj,- за набор объекте

.XJ.U.VM"), т.е. принимая к, для i-1.....m за объект <i.MiJJ,~>, где М, - множество номере

всех букв r ir„ ,V, - множество номеров ДНФ в D, содержащих к,, а ПЛМ/SjJ^q,) дг j i,...,n - за объект ^jjtj.vj.vj^, где ну^, Vj-fy муг,, представляем в виде ЗКДР-I зада1: еннтета минимальной но числу элементов одноярусной комбинационной схемы, допу кающей объединение выходов ее элементов по схеме ИЛИ, в элементом базисе Е i п>Л различт.IX Wl\i/_Sj,thq,). Кроме того, а ЗКДР-1 ло ко просматривается задача кои попонки произвольной схемы из одногабаритных элсменюв. все полюсы которой 061 явлены внешними, в ячейки, различные по вместимости или по числу выводов.

Чамсшч, что условие (3.1), наложенное в ЧКДР-1 на наборы объектов l(lJifJJ J(./.ù'J'Jt~), являстся но существу условием разрешимости как самой ЗКДР-1, так и вс: кой сводимой к ней задачи, выступая либо условием реализуемости любой ДНФ П, ci стемы I) на пекоюрой 11J111C базиса Е. либо условием реализуемости каждой коньют ниц к, множества К на некоторой ПЛИС базиса Е.

И чеп'ерпж главе формулируется (выделяется) подзадача ЧКДР с монотонной д< пускающей функцией, называемая ЗКДР-2. 13 ней разбиваемым множеством являеи набор объекюв с атрибутами ДАДЛ'/1- Объект в этом наборе представляет ci

бон коргеж *'1,\/, Л',./', ' значений афибугов ДА I r\!J ' ctxrm ci cm е и п о, где / - номер 061 сыа, яв.ыющнйся ею идеитфикаюром. А/, - конечное множество, содержащее i,Nt luiypdLibiioc число и р, - признак (copi) ибьекта, равный 0 или 1, / \,...,т, т> 1. Дону клоним множеством является набор обьектв J(J,U,lf,U{ УА,0А-* W'.W*). Объект в тто наборе представляет собой корюж <■y^vf^j ,v>j,wj> значений атрибуте .'.С',¡'.¡'\l'lJ!",li'' cooiBciciBeiiiio, 1ДС /- номер oGbCKia, являющийся сю идеи и фикан'ром, iijMj",- натуральные числа, j I,...м, п> 1. Для разрешимо1 m палачи продно;ш астея, чю ,

ViGHp,-s^>3jeJ( 1 <u/KUr{i) vf aN,<w/)). (4.1

Для .'побого/!~(A^Ai)çz!, где A, для î 0,1 ecu, произвольное подмножество объектов lilAIJïJ') с р, ï. вводя 1ся обозначения

()(А) [J M,. h(A) m ах .

'

и множество А назывался допустимым д,1яУ, turn ./-допустимым, или просто допусп нмм. сели

D/c./(IO(.-iV<».A:C^lV,l!<v^Vi'e\M\{\A^ufM(AyA,\<.v'^h(A,)<.Wj')). (4.2 Разбиение H множества (набора объектов) I называется допустимым для J, или . допустимым. или просто допусгимым. сели каждый блок (класс) AeR является . допустимым множеством. Допустимое разбиение Я множества / называется минимал нмм для J, нлн ./-мнннмальпым. или просто минимальным, или кратчайшим, есл ¡/^''¡Я'! для любого ./-допу стимого разбиения R' множества /.

Ставится ЗКДР-2 следующим образом: 'Лля заданных наборов объектов 1(IA1JJJ ./(./, 1/,Ц°,и\V,¡".И,fi",И"1) пайги./-минимальное (кратчайшее) разбиение множества /.

Нетрудно в идеи., что поставленная задача является подзадачей (частым случае» ЧКДР с абстрактной моноюпной допускающей функциейв которой A '¡(IMJJJ'yzL />,х---хД>ч, B---J(J,U,VaJJl,l\l*',l'.tt*'MA)ci-' ifix-xf» и, следовшельно, может быть p mena 7-мстодом. если определим, значения его параметров />.çt,4V'o наиболее подход

щим для нес обратом. ')го делается конкретизацией тпачений p,<p,'i',F0, предложенных

ЗКДР с абсфакпюн монотонной допускающей функцией f.

Предварительно для каждого ¡el через s; обозначается число собственных, т.е. не принадлежащих другим множествам в А/-'{Аэлементов множества Л/„ на / (на множестве кортежей <|Ml|,sí///>, i~l,...,m) вводится лексикографический порядок > и эбьскты в / нумеруются в соответствии с этим порядком. Этот порядок, если специально не оговаривается, сохраняется в любом КсЛ'"/. Из J удаляется всякий объект _/, для которого 3¿e^(«t>ttjAvt>v/\Víе{0,1 ttufeuj'KvfevjKWt'^j'^vVieSipt^s^iuj-OvWrli}| >Vj\/>fi,I¡\>v ' \/N¡>Wj'), в результате получается неприводимый набор объектив J'cJ. Не-

Фудно убедиться в том, что всякое ./'-минимальное разбиение множества I является J-иинимальиым разбиением этого множества, поэтому далее набор./ считается неприводимым. На J (на множестве кортежей <ири/,и/,ур\>°,\>/,м>^,м>/>, /=!,...,л) вводится лек-;икографический порядок < и объекты в J нумеруются в соответствии с этим порядком.

Алгоритмы начального разбиения. Для получения начального разбиения 1<„ лножества / используются алгоритмы p¡ и предложенные для ЗКД11 с монотонной /, ) которых A-I, B=J и свойство допустимости подмножества в 1 фактуется согласно 4.2).

Алгоритм перечисления допустимых подмножеств. Для любого Ya.X-1 и любого eF через Ф"(У) обозначается множество всех максимальных допустимых подмножеств i Г, содержащих I, и через /"с>' - множество всех тех кеГ, расположенных в порядке юзрастания, для которых i*k и {/Д") есть допустимое подмножество в Y. Кроме того, для побых В,СсУ н любых i,ke Y таких, что ¡efí н кеС, с целью упрощения некоторых последующих записей, вводится S- (ZÍ-{i>XXC-{/;J). Алгоритм перечисления (<р) состав-мот следующие три правила выделения некоторых максимальных допустимых юдмножести и УсХ /. применяемые п укатываемом порядке.

1. Если для некоюрого допусшмогоЛ •-{(,/1>...,|1}сГсправедливо соошощение (4.3),

0 <р(У)--{А) ;т наименьшего такого I.

(4.3)

2. Если ;Ъ1Я некоторою допустимого A={i,k}cY справедливы соотношения (4.4), 4.5), то для наименьших i,к с указанными свойствами.

Vi е {0,1 }(¡{ ,,к,1}г\<и'л\0( {Ш}) Í {U',ib)Sw/)); (4.4)

V5e (ow(í^VC б /}(y)[5nC=0=>3/6J(|O(5)|<M/4|O(S>5|<vy\

VJS {0,1 }(K¡<«/A|C>(5)-5,j|<v/A^(S'J)<WyJ))]. (4.5)

3. Во всех остальных случаях y(Y)=qP(Y) для некоторого ieY. (Заметим, что такое тожество <f(Y) может остаться после неудачного применения к множеству Y правила 2

1 тогда i есть либо либо к в этом правиле.) Алгоритм построения этого множества ¡(У), названный алгоритмом ip2, совпадает с точностью до определения свойства ¡опустимости подмножества с одноименным алгоритмом, предложенным для ЗКДР с бстрактной монотонной допускающей'функцией f.

Операция сокращения. Для опреде.' ,чшя операции сокращения ('К) на множестве сех подмножеств в УсХ- -! вводится не транзитивное и не антисимметричное отаоше-ше предшествования (ос) следующим образом. Пусть A={il,...,ip}cY, В~{ки--Лд}сУ, ><—<1р, kj<—<kq и ,S'--(/M)w(C-{i}), /де СсУ и /еС. Тогда А°сЗ<=>

I;>>длУ«Еph -Pk¡ л| Afk/ -Mh |<л1г лNkt <Nit)))] (4.6)

Vie {0.1 W^Uj^ViSyS^j^hiS^w;))). (4.7)

и результат применения операции Ч" к множеству Zcz<p(Y) определяется как множество Ч'(Z) -4':('i'i(/f)). |де '¡'¡(/'kzZ есть миожесгво. содержащее всякое такое множество Не 7., дли которого в 2 не сушестиует множества А?В и Л х[1 согласно (4.6), a 4':(T|(Z)) с Т|(/) есть множество. содержащее всякое такое множество Be4',(Z). для которого в 4',(Z) не существует множества А*В и АссВ сотласпо (4.7) или, сели такое Aey¥,(Z) сущее i пуст, ю и В у. А согласно (4.7). При этом А (либо В) не включается в Ч'(/Г).

Граничная функция Fa определяется формулой }\i(Y)^max(k\,.k¡.l,p,t), где

k„ (>>'e|/nnix к,

ЧД, f¡)\l' max и, '1 / -Г;О0>'max м,1 р-ГЮОУП'тах у/1

j\j j j^j jij

и г есть мощность itcKoioporo подмножества попарно несовместимых объектов в Y, т.е. таких различных s.!r: >', для которых ¡s.l¡ сетт. недопустимое множестпо, определяемая посредством адюрнтма г, предложенного для ЗКДР с монотонной/

Доказывается допустимость ире.июженпых для ЗКДР-2 значений (выражений) д> и т', т.е. достаточность множества Дастся пример построения кратчайшего J-

»■•iiyeiHMoio разбиения множестна /. т.е. пример решения ЗКДР-2 Г-мегодом с предло-. .зпн тми для nee значениями ci о параметров.

Формулируется сводимая к ЗКДР-2 задача с и теза минимальной по числу эдем ем ii.ii цифроной схемы и базисе так называемых неоднородных ПМЛ. i.e. 'задача разбиения заданной системы D -{D^.-JJ*) из ш>I ДПФ структурных функций выходот г',(« ,, ...VíJTi,...^). и функций возбуждения триперовг ],...,(. s=l....,k / <><), nk-m. представляющей собой операгор некоторою цифровою устройства i

входными переменными л,....^;. внутренними переменными z,_____и выходными пере

метками у,~ <p¡....¿yup,, па миннмалт.нос число подсистем, каждая ит которых реали зусма хотя бы на одной НМЛ заданно! о базиса F. из n'¿ 1 неодно|Ч)дш.1х IJMJI. ti указы i¡лстся иллюстрируемый примером способ сведения этой задачи тс ЗКДР-2. Неоднород пая II\iJl(s.p¡.p2.p).p,.<i.,.{j¡) - тго иредлозкепиая в диссертации обобщенная структур, (модель) некоторт.тх тттпов ПМЛ, которые могут содержать, как регистровые, так и ком Оиианнонные макрояченкн. В ней: s - число входов (входных шип), p¡(pz) ~ число ре птстровмх макроячеек, допускающих (не допуекпющих) использование своих p¡(p2 выходов в качестве входов, рДр*) - число комбинационных макроячеек, донускающи (не допускающих) использование своих /М/'i) выходов в качестве входов, и qt,('l¡) ■ число горизонтальных шин peí истровой (комбинационной) макроячейки. Примеров неоднородной ПМЛ можс! сдх'жить любая ПМЛ семейства IW1.1ÓR8. в чаептоетт PAL 161,8 - ПМЛ( 10.0.0.6,2.0,7), PA1.16RX - 11МЛ(8,0,8,0,0,8,0), PAL16R6 ■ 11МЛ(8.0.6.2.0,8.7), PAI.16R4 Л1МЛ(Х.0.4.4.0.Х,7).

ГГри сведении укатанной задачи синтеза к ЗКДР-2 предполагается, что номер i к а» ' дой ДПФ lS>,eD совпадает с номером представляемой сю.функции и что каждая ДН< системы D может бы 11, реализована одной макроячейкой в составе хотя бы одно 11МЛ(.у,/'ь/';,р1,р.(/Уо,'У|) базиса Е, т.е. число конъюнкций и число букп любой Д1М представляющей функцию возбуждения (структурную функцию выходов), не пре»о< ходит величин q,, и s' p¡tprii, и .v >р\ >Рз-&) соответственно. 1де <V 0, если р2>(

иначе (í5j=0, если p4>О, иначе Считается, что подсистема системы D можеч быть реализована на одной базиса Е, если в подсистеме:

1) общее число букв и ДНФ не превосходит общего числа s+Pi+Pi^j+Pí выводов НМЛ;

2) число всех букв не превосходит числа s+p¡+p, всех выводов НМЛ, которые uoiyr быть использованы как входы;

.1) число всех ДНФ функций возбуждения не превосходит числа р\+рг всех регистровых макроячеек ПМЛ и при этом число конъюнкций в каждой такой ДНФ не больше числа qa горизонтальных тин регистровой макроячейки ПМЛ;

4) число всех ДНФ структурных функций выходов не превосходит числа р,чрл всех комбинационных макрояческ ПМЛ и при этом число конъюнкций в каждой такой ДНФ не больше числа q{ горизонтальных шин комбинационной макроячейки ПМЛ;

5) общее число букв и ДНФ функций возбуждения не превосходит числа s iр\^рг+ръ всех выводов ПМЛ, "пригодных" для реализации ДНФ функций возбуждения; •

6) общее число буки и ДНФ структурных функций выходов не превосходит числа i t-/>]+/?3+P4 всех выводов НМЛ, "пригодных" для реализации ДНФ структурных функций выходов.

Функции <pr,f, и их аргументы Х|¿u—¿t перенумеруются согласно подстановке

<Pl.-» Я><. Л.-. fk> . х\--> xh г1.-. zk

4*1 //+1.-. /r+t. *м+Ь—» xm+h zHl>—> z<+*'

где m-t+k. Система D принимается за набор объектов /(ДА ÍJvJ'), а Е - за набор объек-чон те. D,eD принимается за <//(/>/,V.P), где Л/, -

множество номеров всех букв в Д, включающее номер i, N, - число всех конъюнкций в Д, /?,=0, если Д представляет f„ p¡=\, если Д представляет g>¡, я llMnpj,pij,p2hpy,pij,qoj,q1j)eE- за <jvjjUj\u)\vJ,vi\v¡,tf,w}>eJ{JMf'V\V¿oy№,\V*), где и^р^ргЛр^ру, u/--py+p2> Uj^pytp+j, v^sj+ptj+p,j, vf^Sj+py+py+py, v/ = b ^P^Pij^Pip -<?си, Нетрудно видеть, что условие (4.1) в ЗЬСДР-2 является

условием реализуемоста ДНФ D,eD одной макрояченкой в Ux{jíj{sj,p¡jp:j.p¡j.p.,j>qr]j,qlj) efe', а условие (4.2) - условием реализуемости подсистемы ДНФ, чьи номера образуют множество А, на одной ШЩ(^ру,рь>ру,р.<рд0^д^)еЕ.

Н пятой главе формулируется (выделяется) подзадача ЗКДР с немонотонной допускающей функцией, называемая ЗКДР-4. В ней разбиваемым множеством яв;шется набор объектов I(JrMJJ) с атрибутами /Д///. Объект в этом наборе представляет собой кортеж «М,Л> значений атрибутов IMfl соответственно, где i - номер объекта, являю (ийся его идентификатором, M¡ - конечное множество, N¡ - натуральное число, г 1 у...,т, т> 1. Допускающим множеством является набор объектов J(JJJJ'JK)- Объект II наборе j{j,u,v\w) представляет собой кортеж <j,Uj,vj,Wj> значений атрибутов J,U,V,W соответственно, где / — номер объекта, являющийся его идентификатором, Uj,Vj,Wj ~ натуральные числа, j-l,...,n, »2:1. Для разрешимости задачи предполагается, что

V¡e]3jeJ(l<u/W¡\<v/KNi<Wj). (5.1)

Для любого AaJ вводятся обозначения

0(Л>- (J A/,, h(A)=max.N,,

фиксируется некоторое множество Ос<9(/) и множество А называется допустимым для J, или ./-допустимым. или просто допустимым, если

3;е^(Ц|<м/,ех1<:<Л)<р^Л(Л)<и:',), (5.2)

)де сх(,(А)-p{Ay~4C\j()(!-A))!. Разбиение К множества (набора объектов) / называется допустимым для J, или ./-допустимым, или просто допустимым, если каждый блок (класс) Лек является ./-допустимым множеством. Допустимое разбиение R множества j тгпывается минимальным ,%чя J, или J-минимальным, или просто минимальным, или кратчайшим. если |/ii<iW'l для любого ./-допустимого разбиения Я' множества/.

Ставится ЗКДГ-! следующим образом: для заданных наборов объектов l(lJifJJ) ./(./, i7,F,if) найти ./-минимальное (кратчайшее) разбиение множества /.

Нетрудно видеть, что поставленная задача являстея подзадачей (частным случаем ЧКДР с абстрактной немонотонной допускающей функцией/ в которой Л=1{1М№)оР~' / В ■-J(J,t/,l''.HJcz&-*l''ixKixEsxEi и немонотонность функции /обусловлена не

- монотонностью функции ек1с{А) для любого CczO(l). Как н всякая подзадача ЗКДР -пг задача может быть решена /'-методом, если определить значения ею параметрот i\tp,4'J-~u подходящим для нее образом. Однако из-за немонотонности функции ехТ,{Л сделан, что не удалось пи при каком фиксированном CczO(l). А вот при C-O(I) нолуча с 1ся подзадача поставленной задачи, называем;« ЗКДР-4.1, с монотонной доиус nmmeii фуикнней. так как в тгоч слу чае функция cxt<-(/i)-10(/!)[, очевидно, монотонна Дли »той подзадачи удалось определил, подходящие значения параметров р,</>Л'^а Т метода. Сделано ло опять же конкретизацией значений /Xip.'YJ-^ предложенных дл: ЗКДР с аОстрактнон монотонной допускающей функцией f.

Предварительно для каждою те/ через л, обозначается число соботиенных, т.о. m п;»шл.иежашн\ .трут им множествам в М JAэлементов множества Mi, на / (и;

множестве кортежей -'^Л!аЛ'Г'> ' '....."О вводится лекспкотрафичсский порядок > 1

обьекты н / нумеруются в соответствии с :иим порядком. Этот порядок, если специаль по не от онартшасгся. сохраняется в любом YqX.-I. Из J удаляется всякий объект/ дл которою 3/;cJ(i.t;ii/,r4>\'/.iii>Ti;l)vV;e/(^)',j>v/vJV1>iri), в результате получается непрн водимый набор обтлктов J'cJ. Нетрудно убедиться в том, что всякое ./'-минимально разбиение множества /я1|.тистея/-минимальным разбиением лото множества, поэтом; далее набор J считается неприводимым. На / (па множестве кортежей 'Tij.^.v.j,-

j I.....п) вводится jickchkoiрлфнчеекнй порядок < и объекты и ./ нумеруются в еоот

IIГСТТЧТН С НИМ порядком.

Аг'оршпмы иачачииъо pujtnteituя. Для получения начального разбиения R множества/ используются алт оритмы и />, предложенные для 1КДР с монотонной , г. которых А /, В J и сьонсшо допустимости подмножества в / трактуется оиласи

А.чгоритм перечисления сдопустимых поамнолсести. Для любою YcX-'l и любот к.)' через <J"k)') обозначается множество всех максимальных допустимых подмножест п содержащих г. и через f'ciY - множество всех тех keY, расположенных в порядк взрастания. для ко юпых ¡*к и {i.k} ес:ь допустим»« подмножество п К Кроме того, дл любых B,C<zY и любых ¡.кеУ г.т.их. что ieB и /,еС, с целью упрощения некоторых пс езедующич мнноей, вьодшея S \3-{i}y.j(C-[i}\ Ллюригм перечислении < р) coerai ляют следующие три правила вт.1::е;1ет1ия некоторых максимальных дото.стт'мы подмножеств в )'ci,V /, применяемые в указываемом порядке.

-IS-

1. Если Лля некоторого допустимого A~{i,ii,...,ii}cY справедливо соотношение (5.3). для наименьшего такого

{(.,..Л}-/'- (5.3)

'2. Если для некоторого допустимого /i={i,¿}cK справедливы соотношения (5.4), ,5), то p(í}=(A} для наименьшихi.kс указанными свойствами.

rW*,*0^V/6/Wí)-13/eJ(3<M/4|O({a-,/}|5v/,/;({/,^/})<H'j); (5.4)

(5.5)

3. 13o всех остальных случаях <rf,Y)^<pu'(Y) дня некоторого in У. (Заметим, что такое пожеспю (А Y) может остаться после неудачного применения к множеству У правила 2 тогда ( есть либо í, либо к в этом правиле.) Алгоритм построения этого множества [Г), названный алгоритмом tp2, совпадает с точностью до определения свойства Miyciимости подмножества с одноименным алгоритмом, предложенным для ЗКДР с кпгракшой монотонной допускающей функцией/.'

Операция сокращения. Для определения операции сокращения (f) на множестве :сх подмножеств в УсХ-l вводится'не транзитивное и не антисимметричное отноше-

■1с предшествования (ос) следующим образом. Пусп, Л::{(ь..„/^|с)', B=[k¡.....kq}cY,

<--<tp. ki<—<kq и S^(B-A}u(C-{i)% где Ce У и ieC. Тогда А к So

Ir^AV/efl.....q}(i,<k,a(i,'~k,=>(\ Mk¡- A/(( aN^ <iV(¡ )))]v (5.6)

\A-B < (¡ лVCe ^'\)O№r^>0=^3yeJ(P|<!//\|C>(5)!<v;AA(S)<w,))] (5.7) результат применения операции 'P к множеству Zcz<p(Y) определяется как множество '(/Г) 'I'íCI'^'O). где "Pi(Z)cZ есть множество, содержащее всякое такое множество с/, ,тля которого в Z не существует множества А*В wAozB согласно (5.6), а 'P;|"P[(Z)) :Ч'|(/Г) есть множество, содержащее всякое такое множество Be4'\(Z), для которого в 'i(Z) не сушсавует множеава A¿B и Av. В согласно (5.7) или, если такое sle'F^Z) /тсстауег, то и Вес A coi.таено (5.7). При этому! (либо В) не включается в 4'(Z).

Граничная функция !•'» определяется формулой /*'1|(/)= тгтх(А',/, г), где

t-f |Г|/мД /--f|0(0/max v/1 JU

г ecu. мощносп> некоторого подмножества попарно несовместимых объектов в У, т.е. лкчх различных s.tmY. для которых f.í,?} еетт. недопустимое множество, определяемая « осредсп>ом алгоритма г, предложенного для ЗКДР с монотонной/

Доказывается допустимость предложенных для ЗКДР-4.1 значений (выражений) <р Т, т.е. достаточность множества хУ(<р(У)). Дается пример построения кратчайшего ./-оиустимого разбиения множества /, т.е. пример решения ЗКДР-4.1 7-методом с приложенными для нее значениями сю параметров.

Формулируется сводимая к ЗКДР-4 задача синтеза минимальной по числу чдемен-ов цифровой схемы в бачисе так называемых однородных НМЛ с универсальными такроячейками, i.e. задача разбиения заданной системы D'{/Ji....J\¡ из 1 ДНФ

труктурнмх функций вы.ходов _____и функций во-буждения три//cfn>íi

,(гь...А'/~Л)> í A,.,.,k, t,k>0, 11 i m, "представляющей собой оператор некию-

юго цифрового устройства с входными переменными x¡,...jí~i. внутренними переменпы-

tи _____;t. выходными переменными y¡ '<pl,....yr tpí и с множеством внешних нерсмен-

i„iv (' ¡í........г,С JB. Ь'е _____?>}. на минимальное число подсисгем. каждая

из которых реализуема хотя бы на одной ПМЛ заданного базиса Е из п>\ однородн НМЛ с универсальными макроячейками, и указывается иллюстрируемый пример способ сведения этой задачи к ЗКДР-4. Однородная ПМЛ0,р,<7,) с универсальны макроячейками или ПЛИС(.г,/?,<?,) - это известная обобщенная структура (модель) не] торых типов ПМЛ фирмы Altera. В ней: s - число входов (входных шин), р - число t ходов v выходных шин), равное числу ее макроячеек, и q - число горизонтальных ш одной макроячейки. Макроячейка - основной элемент структуры ILVUl(.s,/>,<j). Она ■ стоит из программируемой пользователем матрицы И, образованной нересечениел входных,;? выходных шин и р шин обратных связей ПМЛ с q горизонтальными шш ми макроячейки, отдельного элемента ИЛИ, объединяющего q выходов матрицы триггера, подключенного к выходу элемента ИЛИ, и переключателя, позволяющею i ходить этот триггер. Выход каждой макроячейки образует шину обратной связи, ко рая пересекает все горизонтальные шины всех р макроячеек и через еще один перекл чатель может быть подключена к выходу ПМЛ(х,р,д). Каждый выход 1ШЛ(л\р/Д i подключенный с помощью переключателя к шине обратной связи, может быть испо. зоиан как вход этой ПМЛ. Все триггеры и все мякроячейки ПМЛ(s,p,q) одинаковы все ее вертикальные шины раздвоены (парафазны), т.е. каждая такая шина, начина) точки раздвоения, представляет собой две шины, по одной из которых передается ci нал, по другой - его инверсия. Таким образом любой макрояченкой в соста ПМЛ(s,p,q) может быть тривиальна реализована любая ДНФ системы D, содержат но более q конъюнкций и не более s+p-S букв, гдг 0, если ДНФ представляет фу| цию возбуждения и содержит внутреннюю переменную Zj или ее отрицание, иначе 8-При этом в ДНФ, в силу раздвоенности вертикальных шик в ПМЛ(s,p,q), буква и ее г версия не различаются, триггер на выходе макроячейки задействуется для получен с-фуктурной функции переходов, если ДНФ представляет функцию возбуждения, ина - обходится, а минус единица в выражении s+p-i означает, что один из выход 11МЛ(л',р,<?) резервируется для вывода функции, получаемой на выходе макроячеш

I ¡виду одинаковости макроячеек и наличия в их составе игнорируемых при необхо; мости триггеров, ПМЛ(*,р,д) названа в диссертации однородной ПМЛ с универсальн ми макроячейкями.

При сведении указанной задачи синтеза к ЗКДР-4 или к ЗКДР-4.1 предполагает чю номер ( каждой ДНФ D,eD совпадает с номером представляемой ею функции каждая Де£> может быть реализована макроячейкой в составе хотя бы одн

II \U\(s,p,q) базиса Е, т.е. число букв любой ДНФ в D не превосходит величины s ip-c число конъюнкций - величины q хотя бы для одной ПМЛ(,?,/у?) базиса Е. Функц !P,f. и их аргумеиты перенумеруются согласно подстановке

скюв Г,(Г)> т.е. ДеЛ принимается за где М, - множество ;

меров всех б\тсв в Д„ включающее номер /, - число всех конъюнкций в Д \\\\Пр.1.р).,Ъ)&Е - за ^у^еЩЦУМ >Де Щ-Рр *>Г<Ь- Полагая

(I. ,.,|.га. 1,..:.;»где £с{/)!,..,в случае Вс{г +1,..,г+£} получаем ЗКДР-4, с |\<1яе И \п\...,пк\ - ее подзадачу ЗКДР-4.1. В них условие (5.1) является у с лот |ч.им 1\ечос1И ДНФ и,е.и одной макроячейкой в ПМЛ/^.,о„у,)еЬ', а условие (5.2

-20-

товием реализуемости подсистемы ДНФ, чьи номера образуют множество At на од-i 11МеЕ. Множество С задает перечень внешних полюсов (connector) буду-й схемы, посредством перечисления номеров всех входных и выходных переменных, пкже номеров некоторых внутренних переменных цифрового устройства, выдслен-х здесь в отдельное множество В, которое задается разработчиком схемы этою ует-¡ства из прагматических соображений. Включением в В номера какой-лнбо внутреп-т переменной (равно функции возбуждения, равно структурной функции переходов) ктуеттся необходимость выво/'з этой переменной на выход ГШЛ и далее на выход ;мы, например, с целью контроля, и одновременно запрещается использование сопо-твляемого этой переменной выхода ПМЛ в качестве входа. Значением функции С(А) является число "внешних" (external) переменных подсистемы А, причем и ext^/)-]^. Поскольку нетривиальные значения параметров 7-метода ределепы в диссертации Лишь для ЗКДР-4.1, в которой С OtJ) и функция :,{Л )-|0(Л)| монотонна, то реально решение рассматриваемой задачи синтеза сисдс-ем ее к ЗКДР-4 возможно лишь в случае B сведением к ЗКДР-4.1. Заметим,

нако, что решение задачи сшпсла, полученное для B^{zь—сведением к ЗКДР-4,1, 1ЖИО рассматривать как приближенное решение згой задачи в случае Bc(zt,...^}. В мом деле, равенством В как уже отмечалось, диктуется необходимость при-

тепшя па выводах ПМЛ будущей схемы всех внутренних переменных что ис

егдя целесообразно. Так в случае ослабленной функциональной зависимости, когда которые функции (ДНФ системы D) зависят не от всех внутренних переменных, воз->жна ситуация, в которой все зависящие от некоторой внутренней переменной функ-[и реализуются на одной ПМЛ, как попавшие в один класс разбиения. В указанной туанни выводить эту внутреннюю переменную (структурную функцию переходов) на тход ПМЛ нет необходимости и можно было бы использовать этот выход как вход, о, по ¡можно, улучшило бы качество решения в целом, т.е. уменьшило бы число ПМЛ :хеме. Таким обр:пом. искусственно полагая и, следовательно, С-0([), мы

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

учае Bcz{:...... При этом потеря качестна решения (если она имеет место) объяс-

<егся ослабленной функциональной зависимостью.

В шестой главе формулируется (выделяется) подзадача ЗКДР с немонотонной дотекающей функцией, называемая ЗКДР-5. В ней разбиваемым множеством является тбор объектов HJM-N) с атрибутами IM.N- Объект в этом наборе представляет собой >ртвж <iMiJJi> значений атрибутов IMJf соответственно, где i - номер объекта, яв-котцийся его идентификатором, М, - конечное множество, N/ - натуральное число, l....,m, т>1. Допускающим множеством является набор объектов J(J,V.1V,). Обт.ект в (боре J(J,V,IV) представляет собой кортеж </,Vj,wJ> значений атрибутов ./Д'й'соотаег-тенно, где / - номер объекта, являющийся его идентификатором, Vj,Wj - натуральные пела, п>\. Для разрешимости задачи предполагается, что

Vi e Bj<sJ(yU,\<v/J.',<,Wj). . (6.1)

дя любог о AcJ вводят ея обозначения

|сА I сА

иксируетея некоторое множество СсО(Г) и множество/i называется допустимым для . или ./-допустимым, или просто допустимым, если

D/eJ^xt^/OSv/^yl)^), (6.2)

где ext({/l)1 \0(АуЫ,С^О(1-А))¡. Разбиение/? множества (набора объектов) / называет допустимым для J, или ^-допустимым, или просто допустимым, если каждый бл (класс) А еЯ является-/-допустимым множеством. Донусгимое разбиение Л множеств; называется минимальным для J, или -/-минимальным, или просто минимальным, и. кра тчайшим, если |Я|<|Й'| для любого J-допустимого разбиения R' множества I.

Ci .лштся ЗКДР-5 следующим образом: для заданных наборов объектов I(IMJ J(J,V,W) найти ./-минимальное (кратчайшее) разбиение множества I.

Нетрудно вндет-ь, что поставленная задача является подзадачей (частым случае ЗКДР с абстрактной немонотонной допускающей функцией/ в которой A^-I(!¿\f,N)cl xD2y.D}, B"--J(J,V,Hry^E=K\f.E-íy.Ey и немонотонность функции/обусловлена немон тонпоегью функции ехИ/О для любого СсО(/). Как и всякая подзадача ЗКДР эта зал ча может быть решена Т-методом, если определить значения его параметров р,<рЛ\ подходящим для нее образом. Однако из-за немонотонности функции ext<-{/!) сдела 'но не удалось ни при каком фиксированном Сс.О{1). А вот при С= 0(Г) получается по задача поставленной задачи, называемая ЗКДР-5.1, с монотонной допускающей фун цией, так как в этом случае функция ext¿{/})^|6>(/!)|, очевидно, монотонна. Для этой по задачи удалось определить подходящие значения параметров p><p,4'J<0 /'-метода. Сд лано это конкретизацией значений p,<p,yYJ''o, предложенных для ЗКДР с абстрактш монотонной допускающей функцией/ .

Предварительно для каждого i él через s¡ обозначается число собственных, т.е. i принадлежащих другим множествам в Л/ ;{Л/ь---Л/т}, элементов множестваА/ь на / (i множестве кортежей i~\,—,m) вводится лексикографический порядок >

объекты в 1 нумеруются в соответствии с этим порядком. Этот порядок, если специал по не оговаривается, сохраняется в любом УсХ-1. Из J удаляется всякий объект j, д которого 3d"e./(vjt>iy\H'jt>H'J)vV/6/(|'V/([>VjVjV,>w^), в результате получается непрнводимь набор объектов J'cJ. Нетрудно убедиться в том,, что всякое J'-минимальное разбиеш множества I является ./-минимальным разбиением этого множества, поэтому далее н бор У считается неприводимым. На J (на множестве кортежей <Vj,Wj,>,j=\,...,n) вводит лексикографический порядок > н объекты в./ нумеруются в соответствии с этим поря ком. Ввиду неприводимости набора объектов J получается vi>--->v„ и h,1<-"<w„.

Алгоритмы начального разбиени,/. Для получения начального разбиения i множества / используются алгоритмы p¡ и pi, предложенные для ЗКДР с монотонной в которых A=¡, B-J и свойство допустимости подмножества в I трактуется согла« (6.2).

Л.сг 'оритм перечисления допустимых подмножеств. Для любого УсХ-I и любо! к. У мереi ¿"{У) обозначается множество всех максимальных допустимых иодмножес в )', содержащих /, и через f'cY - множество всех тех keY, расположенных в поряд: нотрцепшия. для которых i*k н [i,к) есть допустимое подмножество в У. Кроме того, д. любых 11,Сg.У и любых /ДеУ таких, что ieB и кеС, с целью упрощения некоторых п следующих записей, вйодится S-=(B-{/}V(C-{fc}). Алгоритм перечисления (<р) сосга лч№1 следующие три правила выделения некоторых максимальных допустнмь 11>х(множсс|11 в YcX'-J, применяемые в указываемом порячке.

I. Гели для некотрого до11угшмого.-1={),/ь...,|4}с)'сиравед;шво соотношение (6.3 !<> <у !"> { ! ¡ длч наименьшего такого г.

{/„..., !*)=/". (б.: -22-

2 Ксли для некоторого допустимого /!-{/,£ | с Г справедливы соотношения (6.4), г>.5), то <fiY) {.-!} для наименьших с укатанными свойствами.

(6.4)

VBe/^^VCe^'^ni/yrxC-O^a/e^lO^lSv^ACS)«^)!. (6.5)

3 По всех остальных случаях <р(.У)^<!^\У) для некоторого ieY. (Заметим, что такое нтожесгео <я()") может остаться после неудачного применения к множеству У правила 2

тогда i есть либо /, либо к в этом правиле.) Алгоритм построения этого множества i(F), названный алгоритмом <pl, совпадает с точностью до определения свойства оиустнмости подмножества с одноименным алгоритмом, предложенным для ЗКДР с бе фаып(оft монотонной допускающей функцией /

Операция сокращения. Для определения операции сокращения (4*) на множестве еех подмножеств в i'cX'-J вводи гея не транзитивное и не антисимметричное отноше-ие предшссгвования (ос) следующим образом. Пусть si{iu...,ip}c:Y, В {kt,...,ke}^Y, ■ <-<tp, кг<-<кч и S~(ll-A)u(C-{i}), где СсУ и /еС'. Тогда/i ас До

(,>>7*V/6{1.....q\(i,<k,A.{h--kt^i\Mki -Mit )))]v (6.6)

(6.7)

резул!.т!тт применения операции Ч' к множеству ZczqiY) определяется как множество Ч':(Ч',(л)), где xV\(7.)qZ еегь множество, содержащее всякое такое множество ■eZ, для которого в У, Не существует множества А*В и А о:В согласно (6.6), а ':('''(( '))c4',(Z) есть множество, содержащее всякое такое множество Be4'l(Z), для оюрою в Т,(/) не существует множества АфВ и А<сВ согласно (6.7) или, если такое с;>К|(/Т) смцестует, то и Вое А согласно (6.7). При этом А (либо Я) не включается в

1 'рчнишюч функция 1-о определяется формулой FJYy \xiax(k,l,i), где

г есть мощность некоторою подмножества попарно несовместимых объектов в К, т.е. аких различных s.mY. для которых {j.f} есть недопустимое множество, определяемая осредством алторитма г, предложенного для ЗКДР с монотонной/

Доказывается допустимость предложенных для ЗКДР-5.1 значений (выражений) <р Ч', т.е. достаточность множества Ч'(<р(У)). Дается пример построения кратчайшего J-опуаимою разбиения множества/, т.е. пример решения ЗКДР-5.1 Г-мётодом с пред-ожениыми для псе значениями его параметров.

Формулируется сводимая к ЗКДР-5 задача компоновки произвольной схемы в мп-имяльное количество ячеек, различных по вместимости или по числу выводов. В пей ассмлтрипяется схема S из ю>1 хчемептов, множество С ее внешних полюсов .oimector) и конструктивный базис Т из ri2.1 ячеек, различных по вместимости или по пс.ту выводов. Предполагаегся, что каждый элемент e,(A/j,Vi) схемы S характеризуется омером (, множеством Mt "окрасок" его полюсов и размером iV/, где Ni - натуральное пело, а каждая ячейка i/.\>hwj) базиса Т— номером j, числом выводов Vj и вместимостью •„ где w, - также натуральное число. Кроме того, предполагается, что каждый элемент ,(.U,. V,) схемы S в отдельности может быть скомпонован (размещен) хотя бы в одной чейке t{y,.wi) базиса Т, i.e. ¡A/jfSvy и Ni<m>j. В этом случае схема S однозначно опреде-яегся (задается, характеризуется) множеством S всех своих элементов и множеством С еех своих внептник полюсов, а задача компоновки может быть сформулирована как

задача разбиения схемы (множества) Sua минимальное число подсхем (подмможес реализуемых ячейками базиса Т. При этом подсхема считается реализуемой некото; одной ячейкой базиса Т, если число внешних контактов подсхемы и сумма размере! элементов не превышают числа выводов и вместимости этой ячейки соответствен внешними контактами подсхемы считаются "окраски" полюсов ее элементов, содер тцнеся л С или среди "окрасок" полюсов элементов других подсхем, а условие ком ковки каждого элемента схемы S в некоторой ячейке базиса Т, сформулированное в де неравенств и являемся, очевидно, необходимым и достаточным уелс

см разрешимости задачи компоновки (разбиения), если С содержит "окраски" nneini полюсов всех элементов схемы S (все полюсы (цепи) схемы S), иначе - только до< точным. •

При сделанных предположениях рассматриваемая задача компоновки (разбие схемы) решается сведением к ЗКДР-5 или к ЗКДР-5.1. В самом деле, пусть 0(А)= (J

i

для любого AqS. Тогда, принимая S за набор объектов /,<V), а Т - за набор объех J(J,V>Hт.е. принимая элемент e,(h1i,N,) за объект <iMj.N,>el([.MJf). а ячейку t/vj.Wj - за объект <j,Vj,Wj>eJ(J,V,ll'), в случае CcO(S) получаем ЗКДР-5, а в случае С-0(' се подзадачу ЗКДР-5.1. В них условие (6.1) является условием компоновки элеме e,(KiiJJ,)eS в ячейке t/,Vj,wj)eT н, одновременно, условием разрешимости задачи — с галочным в случае CcO(S) и необходимым и достаточным в случае С -0(S), а уело (С.2) - условием компоновки подсхемы AcS в ячейке t/\'j,Wj)eT. Множество С заг перечень внешних полюсов (connector) схемы S посредством перечисления их номе ("окрасок"), а значением функции exl^vl) является число внешних (external) полте (контактов) подсхемы AaS, причем еxt<_4{i})<J.\н extL</) [C|. Поскольку истривит пие значения параметров 7-метода определены в диссертации лишь для ЗКДР-5. которой С -0(1) и функция ext<^)-|0(/l)| монотонна, то реально решение рассмат пасмой задачи компоновки сведением ее к ЗКДР-5 возможно здесь лишь в слу С (сведением к ЗКДР-5.1. Заметим, однако, что решение задачи компоновки, лученное для С 0(S) сведением к ЗКДР-5.1, можно рассматривать как приближен решение этой задачи в случае CcO(S). В самом деле, подлая С=0(Х) в случае, кс ('c:0(,S'). мы объявляем внешними in—' пол/осы (цени) схемы S и, тем самым, Ksccuiumo отраштчиваем возможность компоновки (размещения) той или иной т схемы. loV в топ или иной ячейке t базиса Т, что, очевидно, ведет к увеличению чт л.нрачивасмых ячеек. Способ сведения этой задачи компоновки к ЗКДР-5 иллккчрт стся примером.

Н седьмой I лаве формулируется (выделяется) подзадача ЗКДР с монотонной до! kaiouicit функцией, называемая ЗКДР-З. В ней разбиваемым множеством является бор объектов 1(1,S) с атрибутами l,S. Объект в этом наборе представляет собой кор «',-• значений атрибутов Iß соответственно, где i - номер объекта, являющийся идентификатором, с, - элемент произвольной природы, г-1 ,...,m, m> 1. Допускают множеством является набор объектов J(J„\(). Объект в этом наборе представляет со К1Ч>тсж значений атрибутов JM соответственно, где j - номер объекта, яы

тцнйся сто идентификатором, Л/у - конечное семейство (комплект) элеметпов тон

••p»i|v:u.». что и исменты ,-„ j I.....п, и21. Элементы e,z.S рассматриваются как о;

> »емеижые подмножества некоторого множества Е или как одноэлементные семей.

-2-1-

Е, т.е. e,-{e¡}cE, а семейства Л^еЛ/ - как произвольные конечные семейства над Е, íenibi которых (в 'юм числе и одинаковые) различаются их номерами. Преднолага-l, чгона множестве £ задан квазицорядок (частичный порядок) - рефлексивное, ан-мметричнос и транзитивное бинарное отношение, обозначаемое символом t>, паяемое отношением покрытия* н распространяемое на множество Е всех семейств Е следующим образом: для щобых A Ji е É говорим, ч то А покрывает В, или В по-вастся . !, и пишем A i> В, если каждому элементу ЬеВ можно сопоставить взаимно означно элемент аеЛ так, чю ¡jt-Ь. В случае А~М} для некоторого jeJ и fí e, для тгорого te! пишем Kfjt> с, и говорим, что Kíj покрывает e¡, или объект j покрывает ект i. Для разрешимости задачи предполагается, что

V¡eBjeJ{Mjt>e,), (7.1)

любой объект i в наборе / покрывается хотя бы одним объектом j набора J. Для лю-> Ас.1 вводи 1ся обозначение 001)-- [ J e¡, и А называется допустимым для J, или J-

уетимым, или просто допустимым, если

Э /е./(Л(,о <?(/})). (7.2)

тучас допустимого Ас! говорим также, что 0(А) покрывается M¡ или А покрывается ектом Разбиение/? множества (набора объектов) / называется допустимым для ли ./-допустимым, или просто допустимым, если каждый блок (класс) А ей является шусгичмм ■множеством. Допустимое разбиение R множества I называется мнни-ii.iii.im тля./. или ./-чнинчальным. или просто минимальным, или кратчайшим, если

для любою ./-допустимою разбиения R' множества/. Оавится ЗКДР-З следующим образом: для заданных наборов объектов ¡(fJS), ти ./-минимальное (кра 1Чайшео) разбиение множества /.

И. фудпо нндсть. чп) поставленная задача является подзадачей (частным случаем) с абстрактной монотонной допускающей функцией f, в которой A~l(!,S)cD-■I)2. Я Ji.lAlyrJ-; h',xh'2 и, следовательно, может быть решена Г-методом, если опре-итъ значения ею нарамстрои /».^р/Р/'о наиболее подходящим для пес образом. От ается конкретизацией значений p,<p,yYf,'0, предложенных для ЗКДР с абстрактной Юдиной допускающей функцией/

Предвари iv-льно объекты в I упорядочиваются и нумеруются так, что !ге/(/<А™(е,г> etvt',t-'et)), где e,tiek означает, что e¡ и ек не сравнимы по отношению г>, ->(<"|(>с»)л—i>(«лГ> Введенный на / порядок, еелн это специально не оговаривается, раняется в любом ГсА"~/. Вводятся в рассмотрение множество x?~E(S)cE всех эле-1тов в Я, входящих в множество (семейство) S^[eb...,em) и множество Е{М)сЕ всех чеirme в К, входящих в семейства множества (семейства) М"{М\,...М„}. На Е(М) >сделяется отношение квязипорядка t>* следующим образом: а>*Ь, если для любого сиз bl>е следует аое. Это отношение называется поглощением нах и / спорится, что о> лощает b на х, или Ь поглощастся на х элементом а, если а>"Ь. Легко проверить, > если ai>Ь, ю at>' b для любого множества хсЕ, т.е. ai> Ь. Для любых двух

1сйс1в ЛftMjGM говорится, что Л4 hoi лощает Mj на х, юи kfj поглощается на х се-Зством (множеством) Л/* и пишется Mt>*Afp если каждому элементу éeAf, можно лавип. во взаимно однозначное соответствие элемент aeM¡ так, что at>'b. Очепнд-

по, из Mki>MjCnünyci híti>xMj для любого xçE, и Mk>xMj тот да и только тогда, ког; для любого J'oV из MjP Y следует\ltt> Y. Из J удаляется всякий объект/, для которо HkeJ(A{t>xÁfj)vViel-,(\/j(>e¡), в результате получается неприводимый по (для) x-' t\ набор объектов J'çJ, в котором для любых двух различных семейств KitJ^i¡eKi снраве лнво с>*A/j)A-.(A/jt> х A-Zj, ). Нетрудно убедиться в том, что всякое J'-минимальн разбиение множества I является /-минимальным разбиением этою множества, поэто» впредь набор J полагается неприводимым. Объекты в J упорядочиваются по не убыв пию |A/j| н нумеруются в соответствии с этим порядком, т.е. \/j,keJ(j<k=>\Mj\<\Mt\). Д •заданного упорядоченного множества /-{!,....л}, любою упорядоченною множест Y~{it,...,ip\çiX=I и любых /е/, /je Y определяется множество Y(JJi)çY при помощи ci дующей простой процедуры:

1. Л:=0,1:~к-\.

2. Если 1=р, то н.З; иначе /:=/+1 и, если ueMjt>0(Au{it}), то п.2; в противном случ А: и п.2.

3. Y(jJt):~A.

Иначе говоря, индуктивно Y(j\u) определяется так: если AçYQJt) и i¡ есть наймет! ншй номер в Y-A со свойством {/,}), то i/e Y(j,i¡,).

По определению A/y>0(}'(/,íj)), т.е. Y(JJ¿) допустимо.

Алгоритм начального реппиепия. Начальное допустимое разбиение Rü множест Л' 1 строится последовательно (блок за блоком) по следующему правилу: если разнос множества X и объединения уже построенных блоков есть Y{i\,...jp}, то в качест очередного блока в /?0 берется подмножество в У наибольшей мощности среди подмг жести Y(J,i) для j~l,...,n и i~it,...,if. Именно это правило принимается в диссертации алгоритм Pu образующий в '/'-методе множествор' {р\\.

А/и-оритм перечисления допустимых подмножеств. Для любого YçX-I и любо /1У через ql'\Y) обозначается множество всех максимальных допустимых нодмножес н Y, содержащих /, и через /"сУ - множество всех тех keY, расположенных в поряд возрастания, для когортах lïk и {i,k} есть допустимое подмножество в Y. .Алгоритм i |>ечнсле»ня (<р) составляют следующие три правила выделения некоторых максима; пых допустимых подмножеств в YçX~I применяемые в указываемом порядке.

I. Если для некоторого допустимого Л={т',ть...,!*}£)'справедливо соотношение (7. то «^У)1"!/!} для наименьшего такого i.

{'„...A>=JW. (7.

2 Если для некоторого допустимою A{i,k}cY справедливы соотношения (7. (7.5), то ip( Г){А} для наименьших i,к с указанными свойствами.

/•W'VO^V/e/W'^a/eJíA/^Oaa,/())',

va е <р° '( Y)\/C е /'(У)[£г/>0^3/ eJ(X /, i, О«//- {i} )U)(C-{k) )))]. (7

3. Но всех остальных случаях ^У) чр'\У) для некоторого те К (Заметим, что таи множество <д У) может остаться после неудачного применения к множеству Г правил; и lui да i есть .шГю i, либо к в этом правиле.) Ашоритм построения этого множест названный алгоритмом (¡Ü, совпадает с точностью до определения свойст .iOiivciiiMiviH подмножества с одноименным алгоритмом, предложенным для ЗКД1

,<бсфаК llloii МОНОТОННОЙ ДОПуСКаЮЩСЙ фу'НКЦНСН f.

Операция сокращения. Имея ввиду, что E(hf) естъ множество всех элементов в Е, вводящих в семейства множества А/=[А/ь...у1/„длялгобыхЛ.бе.Ё' пишем А 1> д^В, если каждому элементу Ь<еВ можно поставит!» по взаимно однозначное соответствие некоторый элемент asA гак, что всякий элемент в Е(М). покрывающий а. покрывает и Ь. Очевидно, что если А>В, ю А>у В. Дли определения операции сокращения ('(') па множестве всех подмножеств в YçX~l вводится не транзитивное и не антисимметричное omoirieiw- предшествования (ос) следующим образом. Пусть A={ii,...,ip}çiY, В [ki,....kq}çY, i1<---<tp,k-!<-~<kq. Тогда/4 ce/?»

[/)>дл\/(е{I.....q)(i,<k,A(jl<kl^>c,i t>M ек) ))]v (7.6)

| Л-.В={/}лУСе ^QyBrïC^^ljeAMjb.OUB-AMC-ii}))))] (7.7) и результат применения операции Ч' к множеству Zc^F) определяется как множество Т(К) Ч'гСГ^Я)), где vP,(Z)ç:Z есть множество, содержащее всякое такое множество H с /.. для которого в У. не существует множества Ан А а: В согласно (7.6). а 4'2('I'i(Z))c4'i(/0 естъ множество, содержащее всякое такое множество Be'l'JZ), для которого в не существует множества А?В и АхВ согласно (7.7) или, если такое .1 t Ч'¡(/.') существует, то н ВссА согласно (7.7). При этом А (либо В) не включается в

Гриничная функция Еп определяется формулой /■«(>') - max(fc, г), где k--\\Y\i\Si„\~\ и г сстт, мощность некоторого подмножества попарно несовместимых объектов в У, т.е. )аких различных s.teï, для которых f.v./j еетт. недопустимое множество, определяемая посредством алгоритма г, предложенного для ЗКДР с монотонной f.

Доказывается допустимостъ предложенных для ЗКДР-З значений (выражений) ip и 'Р. т.е. достаточность множества Ч'^ДУ)). Дастся пример построения кратчайшего J-доиустимон) разбиения множества /, î.e. пример решения ЗКДР-З 7-мстодом с предложенными Дзз нее значениями сто параметров.

Далее в 1лаве 7 формулируются (выделяются) подзадачи ЗКДР-З, называемые ЧКДР-1.1 и ЧКДР-3.2, в которых, допускающий набор объектов линейно упорядочен и специален соответственно. В ЗКДР-З. 1, в свою очередь, выделяются подзадачи ЗКДР-3.1.1 и ЧКДР-3.1.2, в которых допускающий линейно упорядоченный набор объектов двухэлементен и состоит из однородных объектов соответственно. Для всех выделенных в ЧКДР-3 подзадач предлагаются более эффективные, чем для ЗКДР-З, (в том числе для ЧКДР-3.1.1, ЧКДР-3.1.2 и ЗКДР-З.2 беспереборные) алгоритмы их решения, иллюстрируемые примерами. Наконец, указывается способ решения ЗКДР-З в случае разделимого допускающею набора объектов.

Множество (семейство) Л/,еЛ/-{Д/ь...J/„{ в допускающем наборе объектов , «А/„>} называется линейно упорядоченным но (для) д.", если племенш в •'} занумерованы (если возможно) так, что

е\ 14* e7J -t4* гг/ ■ Объект <jJbfj>eJ(JJ,i) называется линейно упорядоченным по

(для) х, если множество А/, линейно упорядочено по х. Множество А/ называется линейно упорядоченным по (для) х, если в нем каждое множество А1) линейно упорядочено по .г. а сами множества Mj занумерованы (если возможно) так, что для любого/ последний элемент в Л/, поглощает над: первый элемент в Л//(1. Набор

обьектов JÇM) называется линейно упорядоченным по (для) х, если множество

(семейство) А/ линейно упорадочено по х. Очевидно, если элеметы множеств (семейств) А/у линейно упорядочении!о по* набора объектов ДДА-0 расположить в ряд слеиз направо в порядке возрастания номеров ], а внутри каждого семейства А^ в порядке возрастания их номеров в Мр то получится цепь, в которой, в силу транзитивности отношения каждый зле мент цепи поглощается на х любым аномеыом, сюящим в цепи левее этого элемента. Множество А/^еА/ и объекг ^eJ. множество И и набор объектов J называются линейно упорядоченными, если они линейно упорядочены по Е. т.е. по любому хсД. Если в определениях линейно упорядоченного по х множества А/, (объекта /) н линейно упорядоченною но х множества И (набора объектов ./) опюшнеие поглощения на х заменить отношение».: покрытия, то получится частый случай линейно упорядоченного множества А/ (оПьскта ¡) н линейно упорядоченного шюжестиа А/ (набора обектов ,/). Множеств М,еМ называется однородным длях, если Уа,ЬеК{/а>"ЬлЬ>*а). Объект называется однородным для х, если множество ^{J однородно дня х. Множество Л^еЛ/1 объект <j,^fj>eJ(Jj^f) однородные для Е называются однородными. Очевидно множество А/усЛ/ и объект </Л/,1-еД.ЛА/) однородны всегда, когда \/а,ЬеА/Даь> ЬлЬь а) Всякое однородное (для г) множество Л/,еА/ и всякий однородный (/утя .г) объек-•^Л/у'еДДЛ/) являются одновременно линейно упорядоченными (по х) и можн< 1 оворить, в частности, о линейно .упорядоченном (по х) множестве А/ однородны, множеств и о линейно упорядоченном (по х) наборе ДДЛ/) однородных (для х объектов. В случае линейно упорядоченного (по х) допускающего набора Д.ЛА/ объекш набора /(/,5) мотаю записать в ряд следующим образом: сначала выписаг объекты <1,е,>, покрываемые объектом ^'Му" и не покрываемые объектом дл

]>\, затем объекты, покрываемые ^Мг> и не покрываемые объектом для/>2,

1ак долее, пока не будуг выписаны объекты, покрываемые <пМ„'~", среди объект о '"/.О. покрываемых объектом с И не покрываемых объектом

для первыми в ряду выписал» объекты <>,е/>, для которых е, покрывается ех и н покр!.шас1ся с* для к>1, вторыми объекты <1,е,>, для коюры.ч е, покрывается и и покрывается ек для к>2, и так далее, пока не будут выписаны объекты •П'.е,"», да ычорых покрывается е,. Эют ряд называйся соответствующим заданном допускающему линейно упорядоченному набору объектов ДУД/). Если ДДА/) линейно упорядоченный допускающий набор объектов, объекты в з;

писаны в порядке их вхождения в ряд, соответствующий набору ДДА/) и ] - наибол! ший номер объекта в ДУД/), покрывающего обьект <ь то определяются:

• ] если у=1 или Гада/,!,

Ф7(/ ) = <

({К(2,!,)5 в противном случае

> )-{%</>!•

Тсор 1) м а 7.1. Если ЗКД1' 1 - задача о кратчайшем разбиении набора объект АЛлЧ допустимом для линейно упорядоченною набора объектов Д,/Д/), ю

ФКП-

{ГО,',».

{КО-1,1,),/(/,»,)},

если /"!, если у>1;

[ф2, q>3, 1ф1

(<р2, если ■ <р < (рЗ, если объекты в ./(./Д {) однородны для в остальных случаях

одходит (допустим) для ЭКДР / в качестве алгоритма перечисления в 7-методс при /.

Набор объектов J(JJ/}"{<'lJiii>,...<n/'f„>} (множество М={М\,...Мп}) начинается некиальным для x--h\S)cH, сели для некоторою натурального /, 2<1<п множества есмсйства) Л/Ь...Д/М одноэлементны, А/ы, и A/j двухэлементны и линейно упорядочена, r.e. A//.i-(o,i>}, Mf-{c,d), av>b и со с/, /^п} ~ линейно упорядоченное шожество однородных множеств и лля любого евх-~E(S) выполнены следующие усло-:ия - свойства множесша А/;

\)Ьь e=i>A!/+1t> е;

?)at>eAdl> e^>h t> е:

3) /)1> елс1> кЗ(А/,1> е);

5) —i(cr> e)=?V/>/ t-3(-i(A/jt> е));

f>) г I-. 1> 1/=>-.(A-/yt> e));

7) с I» ел-,(«/(> <0 ~'V;>/(-,(A /,ь с)), '(ля заданного специального набора объектов ./(JJ^-t) в любом подмножестве YcX^f нцюяс.чтпх'я подмножества объектов /^гУ для как

e/,-tx>) е >а(Л/д^ е,)лУ^>Х-.(Л/41><?0). Кроме того, вводятся в рассмотрение множества: !и {г. 1с/,лЛ-е,Ь ¡u'lrh^

!,',/ {с iefw.vjl>i',}, V«*"Uj-U°<b

h'\ 1/: и- /,,Л(И-!i''e hr U"с,

h>\b "f|:"]'ил'«><,||. и подмиожссто Lg /, "j, удовлешоряющее условию: если liac~0 или | //"rf |<| Дяс то |Л( 0; в противном случае |L|> 1. Строится последовательность классов .....Л'„.3) (/,./2,...Ла, с ¡i"j-LJi^J^Ji t ц-, J,tb...J„) и объекты в К

тлнигыпя/отся я ряд /(.....!р в порядке вхождения в классы к^Ж;,---^^;, рассматриваемые

в данной последовательное!и, а именно: сначала выписываются объекты изЛ.'|, затем из Л'2 и т.д. до Л'„(5. Через ,V обозначается множество всех тех номеров /,еГ={)u...,ip}, для которых а> 1 и Л/,., r> {,е^ ) или А/(о {etj ). Находится/ из условия: е/) н определяется ) как

[{{',. '}}. сели /--/. №¿0 и emin №

| (}'(/,',)} в остальных случаях Теорема 7.2. Если ЗКДР-З.2 - задача о кратчайтем разбиении набора объектов ЩЛ), донус|имом для специального допускающего множества ДЛАО» го подхо-

ди! (допустим) для ЧКДР-3.2 в качестве алгоритма перечисления в Г-мстоде при Х-1.

11еприводимый но (для) х набор объектов М.1М) называется разделимым по (для) х. если сущее|вует ратбиение множества-/ на подмножества для г> I так, что для

любого элемента еех и любых двух объектов а и Ь с номерами из разных подмножесп не а>е или не Ь>е. Набор, разделимый по£', называется разделимым. В соответствии I разбиением множества 3 разделимою по Л' набора объектов ДЛЛ/) на подмножеств;

множество / в ЗКДР-З разбивается следующим образом на подмножеств.

/ е/^о/е/л 3/е/4)0Це> е,). ')(" разбиение обладает следующим очевидным свойством: если {<!/, - кратчайшее допустимое разбиение множества

к— 1.....г, - кратчайшее ./-допустимо

разбиение всею множества I. При этом, в зависимости от рассмотренных выше воз можных свойств множества (набора объектов ./''(/'М^')) » ЗКДР-З, разбиение Д для а 1,...,/■ может Сыть найдено соответствующим Г-адтортимом, как решение какой либо нз задач: ЗКДР-З, ЗКДР-З.I, ЗКДР-З.Е1, ЗКДР-З.Е2, ЗКДР-З.2.

Формулируется сводимая к ЗКДР-З задача компоновки произвольной схемы в ми тшмальиое количество ячеек с заданным элементным составом. И ней рассматриваете! конструктивный базис Т из я>1 ячеек, составленных из нескоммугировапнмх элементе! некоторых ттшов, и схема £ из т> 1 элементов в базисе элементов ячеек в Т. Требуете» скомпоновать схему 5 в минимальное число ячеек базиса Т, т.е. разбить ее на минимальное число подсхем, каждая из которых может быть "набрана" из элементов некоторой ячейки в Т. Демонстрируется способ сведения этой задачи к ЗКДР-З в случае, когда компонуемая схема и ячейки конструктивного базиса состоят из элементов типов И, И-ПК, И-ИЛИ-НЕ и триггеров того или иного типа. При этом элементы схемы 5 принимаются за объекты набора а ячейки базиса Т - за объекты набора ./(.ЛАО, всякий элемент И-ПЕ рассматривается как частный случай элемента И-ИЛИ-НЕ, т.е. как элемент И-ИЛИ-НЕ с одним элементом И в его структуре. Иначе говоря, элемен ты И-НЕ и И-ИЛП-ПЕ считаются одпопшнымн элементами типа 1. Элементы И считаются элементами типа 2, различные триггеры - элементами типов 3,4 и т.д. В каждом элементе И-ИЛИ-НЕ, как в схеме & так и в ячейках базиса Т, элементы И нумеруются числами 2,3,... в порядке невозрастания числа ¡«входов, если элемент И-ИЛИ-НЕ иркиаддежит ячейке в 7', и в порядке невозрастания числа задействованных переменными входов, если он принадлежит схеме В ячейках базиса Т выбирается элемент И-ИЛИ-НЕ с наибольшим числом I элементов И в его структуре. Каждый элемент в и в ячейках базиса 7' представляется кортежем вида <а\,а-х,...,ар- длины к-1 КЗ, где - натуральные числа, имеющие в зависимости от типа элемента и ею принадлежности схеме .V либо ячейке в Г следующий смысл:

1) для любою элемента в 5 и в ячейках базиса 7'. отлично! о от триггера, а, - тип члеметиа, ак - коэффициент разветвления выхода элемента, если элемент принадлежит ячейке, и и4 - число полюсов элементов схемы, подключенных к выходу элемента, если ч. темен г принадлежит схеме:

2) дли любо] о элемента Н в 5 и в ячейках базиса 7' а1 и4'= -0, аг - число входов элемента, если он принадлежит ячейке, и сь - число задейсчиопанных переменными >'\одо». если элемент принадлежит схеме;

3) .ия любою элемента И-ИЛИ-НЕ (И-НЕ), как в схеме так и в ячейках базиса Т, имеющею в своей структуре члемешов И, ач,2 ~-а,г,у .,.-~а1,г-0, а, для |-2„..,д+-1 -число входов |-ю '.темента И, если элемент И-ИЛИ-НЕ принадлежит ячейке, и о, - чис-|.| .и.1<.ис1В1'Ваш1ых переменными входов ;-ю элемента И, если элемент И-ИЛИ-НЕ

1шютгсжиг схеме: oVii^fft.i" l, если имеется возможность расширения члемсита И-ЛИ-I и; но ИЛИ. иначе a,., a,., G, -1) для любого трип ера в S и в .ячейках базиса Т, a¡ - тин триггера и а2-~ciy -...--et,2 я< i(í7í) - коэффициент разветвления прямого (инверсного) выхода триггера, если он шнадлежит ячейке, и Ом(я») — число полюсов элементов схемы, подключенных к тямому (инверсному) выходу трш гера, если триггер принадлежит схеме.

Кортеж ' (7|.....я(>. представляющий элемент е, называется информационным чкри-

uienioM элемента е и обозначается символом е, т.е. так же. как и элемент. (Заметим, ю информационный эквивалент элемента с может быть определен (введен) лосрсд-ном учета любого друтого енектрл параметров (атрибутов) элемента е, п частности, vice широкою, чем здесь.) Пусть Е — множество всевозможных кортежей вида iu...,ci¡ ■. Ошошепис частичного порядка на Е, называемое отношением покрытия и назначаемое символом т>, определяется на К следующим образом: для любых е.е'еЕ торим, что е покрывает <>', или е' покрывается й. и пишем el> е\ если (Т1'лсь>.а2'л...ли1.>(!1.\ Это отношение распространяется на множество И всех ее-ейств над Е следующим образом: для любы аЛ,ВсЕ говорим, что Л покрывает/?, или покрывается Л. и пишем Л^В, если каждому кортежу he. В можно сопоставить етпим-т однозначно кортеж чпА так. чго ш>Ь.

Примениle.n.no к рассматриваемой задаче комиоиоики, т.е. в случае, когда каждый >ртеж в Н является информационным эквивалентом какого-либо элемента, эзгт отно-енио, как нетрудно видеть, имеет следующий смысл: если ет>е'. то в любой схеме, со-.ржашеи с', элемент е' может быть заменен элементом е (возможно предварительно троенным на с' путем отождествления некоторых его полюсов или подачи констант i некоторые ею входы) так, чю но нарушается правильность организации схемы и fie (меняются реализуемые со ф\ пкцни. 1>олее того, если Л.В a Е, представляют, соотнет-пеппо. множество э.тсмеиюв некоторой ячейки в 7', мпож'сспю элементов некоторой "дсчемы в .V и . Ii-В. н> подсхема /'. очевидно, может бытт, "набрана" из элементов в ,1, е. покрыв.теня ячейкой.!.

С'-.сдснис иллюстрируется примером, в котором в родтт ячеек базиса Г выступают хкр.ч v.-mi.т серии КПЗ Указывается б»чес двух десятков промышленных серий тпе-идьпых микросхем, ирсдстаиимых в ЗКДР-З в виде допускающих наборов объектов, 1- кмччич зцЛо па линейно упоря/ючсннЫс подмножества. част« даже одпо-■л ч> leMi'ii тш.те и;ти с однородными объектами,'либо на подмножества, являющиеся i-eII.то некоторою специальною набора обт.скюг.. Таким образом, компоновка схем R niiHii.'ijii.'KV кол и често микросхем этих серий лет ко может быть оеушеептдеиа с при-л1етчтем предложенных в диссертации а гп ритмов решения элдач: ЗКДР-З, ЗКДГ-З.1, •СДР-Э 1 1.3КДР-? 1.2, ЧКДР-3.2.

[> wvci.Mon i.i.iiii. е применением средств и методой теории ///■'-полноты (Г:.ри М., жопсои Д. Пычнсдп1С.||.ш,10 машины и трудпорсшаемыс задачи. - М.: Мпр, -

¡6 с.) нес ic.iyeiCH с южносп. всех еформунирои.пп-.ых (выделенных) ткщзата i '.'К'ДР и .Ч-Х ТС.о 1|;>еД.<".т;еН1 ЫХ алюритмов их решения. Результаты НССЛСДОти.ПН Т l¡)0,,M>.Uipy-ivя г термитч и обозначениях чтй irop-пт г. р.г.;с пяти зеорем, устаиагл»;«-»' .' лднооь в ей тыюм смысле ЧКДР-1,2,4 1,5.1.3 сошветстие .но. Нее чти л опомы докатаются методом сужения. При чтом для первых четырех' ты чпт\ 31СДГ v чей. .11,(чипу cooiнегепоз<ччих теорем ч Качестве мзнеерюи W-no 1:1 ч'< чпичи (w>t-u. I

задача УПАКОВКА П КОНТЕЙНЕРЫ, а да пятой - ЯР-ишшая зада МИНИМАЛЬНОЕ ПОКРЫТИЕ. Тем самим устанавливается, ч ю и ли известит ■идами ягллтотся подзадачами ЗКДР. Кроме тою, в каждой на ЗКДР-1,2,4.1,5.1 ноере оном доказываемых утверждений укачиваются две полиномиальные нодчя.чачп, одт тн которых эквивалентна известной задаче О МАКСИМАЛЬНОМ ПАРОСОЧГЛ'АНП И ГРАФЕ. Констатируется, что fi ЗКДР-З полиномиальными подзадачами яичякп ЗКДР-3.1.1,3.1.2,3.2. ЗКДР-З.1 остается открытой (в смысле сложности). С докалате.'! сиюм этих пяти теорем молено также считать установленной и сильную Л'Я-трудиос ЧКДР с монотонной/ ЗКДР с немонотонной / и самой ЗКДР, так кик они содержат качестве подзадач те или иные из ЗКДР-1,2,4.1,5.1,3.

Установление сильной М'-чрудности ЗКДР и некоторых из рассмотренных ее по задач отнюдь не делает безнадежным построение кратчайших допустимых разбиений приложениях. Во-первых, в ходе проведенною эксперимента па Э13М но испытанию алюригми решения ЗКДР-1, тшдннидуалытые задачи массовой ЗКДР-1, требуют (KcíioiiCTTíuixTbHOT о времени решения, появлялись по так уж часто, что весьма верой i и ,'тля других ЗКДР с монотонной / Во-втортах, предложенные '/'-алгоритмы решен Ы'-трудных ЗКДР таковы, что »сетда можно задать приемлемым ресурс времени на [ шение задачи и.по истечении ею иметь наилучшее на этот момент времени решети От» вполне может оказаться и точным, так как опыт района е различными алгоритА ми, основанными на 7-меюде, показывает, чю часто точное решение находится вольно быстро (путем построения небольшой части дерева поиска), а все осгальн иремя тратится на доказательство (путем построения оставшейся части дерева тюис» тот о, чю найденное решение является точным.

Посредством етие двух теорем устанавливаются оценки потрешноети предлатаемт и дпссср|ацнп алюршмов начальною разбиения. Этими теоремами для любой шт, 1:и.чуалыюй чад.ччн / массовой ЗКДР с произвольной монотонно/} допускающей фут пней J устанавливаются неравенства: /^(/)<ОРТ(/)'Г(ш t)/2l и ¿*(/)<(ОРТ(/)-1)-м> 1. тш\. !(/)с {/>т(/),/^(/)} - число классов допустимою разбиения множества (набора о( силон /), доставляемою алюригмом .1, ОРТ(/) - число классов оптимально (кратчайшею) разбиения множества (набора обьекюв /) и и - мощность нанболыти допустмот о подмножества в I.

Потучоипые опенки погрешности тфиблпжепных алгоритмов />т./Ъ казалось бы оставляю) надежды на исчгольипичше этих алюрнгмои на практике, так как решен отличающееся от оптимального на 50'"!« н более, часто ие может считаться jдовлетво| те.тьиым Однако это вовсе не исключает использование алюригмов в '/'-мен д 1я получения начально! о разбиения, улучшаемого далее и процессе обхода дерена т паа Не исключается совсем н возможность самостоятельною использования '.чих юрт мои, гак как в ходе эксперимента на ЭВМ они вели себя гораздо лучше, чем мо но нредпол.п ать па основе оценок их потрешноети, рассчитанных на худший слу чай.

ЗАКЛЮЧЕНИЕ

1 i диссертации разработан общий подход к решению широкою класса задач синь и юмп.чьч'ки схем лотнческою управления на современной элементной и копстр iHHHOii блie. Под еокремеипиой элементной базой понимаются протраммируемт.те по ч-fia. к.м л.ч! ичсские устройства (FielJ Pio¡>,¡.immabie Logic Devices) ил«, друтн.мп с i им и п[ичр:1ч*ч1р\емые лот нчоекие инк-тральные схемы (ПЛИС) такие, как нротр v 4t .е ..'эгрм-.о.ст т' матрицы (11JIM). программируемые постоянные •.атыминаюн

тройства (П1ПУ). протр.зммирусмые матрицы логики (HMJI). я также программируете матрицы вентилей (ИМИ) Под современной конструктивной базой понимаются ейки отрапнчепной вместимости и с ограниченным числом выводов, а также ячейки !танным элементным составом (номенклатурой). В роли первых мотут выступай, ¡новые элементы замены, панели, раны, стойки и т.н., а в роли вторых - шист радьные ткросхсмы отечественных промышленных серий таких, как К) 33, К) 55 и т.п., базовт те (ейки на KpHciUjTJie, составленные из пескоттутнронатншх компонент таких, как pele горы. транзисторы, диоды и т п., а также любые площадки с посадочными гнездами пличной формы и квадратуры и любые помещения с отсеками различной формы и гбатуры. Подход ориентирован на автоматический сшпез и компоновку схем лоптче-гого управления и включает три основных элемента: !) общую математическую Móvil. всех рассматриваемых в работе вариантов задач синтеза н компоновки схем — ори-нталытую комбинаторную оптимизационную задачу кратчайшего допустимою раз-теиня (ЗКДР) конечною множества (набора обьекго»), 2) известий метод сокращенно обхода дерева поиска (У'-меюд) - как метод решения ЗКДР, 3) оригинальный спо->б сведения к ЗКДР различных вариантов задач синтеза и компоновки схем. В отличие I друт их подходов к решению этпх задач, он обеспечивает более широкое использона-не возможностей современной элементной и коиструюптгой базы для уменьшения нота затрачиваемых на синтез н компоновку схем ПЛИС и ячеек, допуская наличие в л тисе сшпе'.а иеькольких (в том числе разнотипных) ПЛИС с несравнимыми набора-к значений их параметров и допуская п конструктивном базисе задачи компоновки есколько ячеек с несравнимыми парами значений вместимости и числа выводов. При том не ограничивается число принимаемых во внимание параметров фигурирующих в ьчлчах обьскюв (оператора синтезируемой схемы, представляемою системой ДПФ фуктхриыч функций выходов и функций по",б\*.кдепня триггеров, базисных ГТЛПС, чем, ччеменпч! схем ячеек) и к'орепнь-еки веет да гарантируется минимум числа закачиваемых ПЛИС и ячеек. Решение юй или иной конкретной задачи синтеза пли очиоповки схем па основе данною подхода, те. разработка алгоритма решения эгой мячи, спсннн п выделении подзадачи (частою случая) ЗКДР, алгоритмизации '/'-(сюла применительно к этой подзадаче посредством подходящего определения зтгаче-ии (рырмжений) его параметров (множества алгоритмов начального рязбиегчю, плroui ми неречислепия. операции сокращения, граничной функции) и в указании способа ведения решаемой задачи к выделенной подзадаче ЗКДР, а также способа преобразо-аиия получаемою допустимою разбиения и схему. Подход может служить основой ,»i ра-.работки все новых и новых стандартных (основанных на Г-мстоде) алгоритмов тпеча и компоновки схем при сохранении современных тенденций развития элемент-юн и конструктивной базы. в частости, при сохранении в составе элементной базы шфроных устройств "PAI.-подобных" функциональных блоков, как это характерно для мннкия 1;ИС СР1.1)-ссмсистна фирмы XH,li\W Кроме тою. есть основания полатать. тто он применим не только в проектировании устройств логического управления.

* IjLiamgry выносится:

1. Прс/ыожснпмн общий подход к решению различных задач синтеза и кохиимюг?-и схем ло! ическо! о управления тта современной элементной и конструктивной б:ге.

¡1. Разработанные па ст о основе ;Ы1 ори i ми решения следующих задач:

1 ) построена:! кратчайших моиоюппо-допустимых разбиений наборов обьсьтив;

2) cKHicia минимальных но числу элементов одноярусных комбннлционнь схем, как допускающих, так и не допускающих объединение выходок своих элсмепи но схеме ИЛИ. в некоторых базисах ПЛИС типов ПМИ. ППЗУ. 1 l.'lSi;

3) синтеза минимальных по числу элементов цифровых схем в базисе так ни и наемых неоднородных ПМЛ (неоднородная НМЛ - это предложенная в диссергаци обобщенная структура (модель) некоторых реальных ПМЛ таких, как ПМЛ ссмейсп PAL16R8);-

■I) синтеза цифровых схем в базисе так называемых однородных ПМЛ с упиг.С} сальными макроячейками (однородная ПМЛ (ПЛИС) с универсальными макроячейк ми - эю известная обобщенная структура (модель) реальных ПМЛ, выпускаемых фи| мой .Мата)',

5) компоновки схем в ячейки отраниченной вместимости и е ограниченным чи лом выводов;

6) кодтпоновки схем в минимальное количество ячеек с заданным элементны составом.

Ш. Результаты исследования сложности рассмотренных в диссертации задач, иол; ченные с применением теории ///'-полноты.

IV. Оценки погрешности двухалюригмов начального разбиения. Каждый из алгоритмов решении задач 2-й изложен как подробная инструкция /и программистов, предусматривающая разделение труда между программистами раню квалификации. Так программирование алгоритма решения задачи разбиения (той ил ииой подзадачи ЗКД1') не требует от программист знаний в прикладной области ( данном случае в области проектирования схем логического управления), а программ! ронанис алгоритма сведения прикладной задачи к ЗКДР и ашориша прообразован« разбиения в схему требует в той или иной мере наличия таких знаний.

М целом, «се полученные в работе результаты предлагается рассматривать как новс математическое и отчасти информационное обеспечение ,чля построения системы авк магическою сшпс'.а и компоновки преимущественно минимальных по числу злеме! юн или ячеек схем логическою управления на современной элементной и конструт шиной базе, а целостность и единообразие подходов к решению задач синтеза н ко.\ пононкн сч'ем - как проявление свойственных электронике в целом тенденций унифт кащш и ешггдар г и глцгш lia уровне создания информационною, ма темагическит о iipoi рлммиог о обеспечений САПР устройств логлчсско! о управления.

ПУЬЛИКЛ! ЩИ ПО Tl'.MK ДИССЕРТАЦИИ По ic.\u¡hkc диссертации опубликовано 26 печатных научных работ, в юм числе: м>л.гсктнвнаи монографии, I учебное пособие, 10 статей в центральных изданиях, 2 сп ил. депчшгроьангых в ШПШТП, 1 статья ь местном сборнике, 6 докладов и 5 íc.meo доклат'Ч! в грудах всесоюзных и международных конференций.

i. 4.i».peni-.xnrt АД., Лиишенко Л.П., Ьалаклей Л.И.. ('Елисеева П.Л., Орано» ЛЛ1 Hi'vwd.t Л.Д . Погюсин Ю.В . Янковская Д.К,, Торонов И Р. (СССР) Система ашом; Гнл'еского спит;- а, дискретны y автоматом - ЛНТОМЛТ-3 - В кн.: "Дискрстные си AVtwu ', >.!,жди1.ц.одиый снмпошчм, Рига, СССР, 30 cchi;»"(»i - 4 октября 1У74 i., 'I'oi И! P¡¡ia."3mur.ic'\ 1У7 К С. 84-92

i.iK|ieiiOKi<M Л.Д .3>а.чаклей Л И.. Елисеева П.Л., Орано» Л.М. и др. Синтез acw v(-<v.iu.tN jfcio\uiOi*i на ЗИМ Под обшей ред. Закревског о Л.Д. Минск. Паука и техник; I""' - 11'4 е

3 Атибалпв Г.П.. 1>еляев Н А., Оранов A.M. Некоторые алгоритмы разбиения, iront и и размещения ло| ических схем// Управляющие системы и машины. — ¡974. -- С. КС,-92.

•1. Лы'балчв 1MI.. Oparrón A.M. Алгоритмы покрытия схем свободными модулями// омагнка и вычисли |ельная техника. - 1977. -.№>4.-С. 15-} 6.

5. Лг ибадой Г.П., Оранов Л.М. О покритни схем модулями'' В сб.: Вопросы автотипии проектирования интегральных схем. - ИК АН УССР. - Киев. - 1978. - С. ¡7.

6. Лг иб;иов Г.Н., Оранов Л.М. Лекции по теории конечных автоматов. - Томск: -во Томск, vu-ra. I9K4. - 1Н5 с.

7. Оранов A.M. Алгориш кодирования состояний автомат, реализуемого на HJIM// П1ТИ. № 2149-85 Доп. oí 28.03.55. - 7 с.

X. Агибалов Г.П., Оранов AM. Покрыже лог ичсских схем модулями некоторых се-ных систем,. ВИНИ ТИ, № 5860-85 Дси. oí 07.0S.85. - 19 с.

9. At ибалов Г.И., Орппоп А.М. Покрытие логических схем модулям» некоторых cent, IX систем// Кибернетика. - 19X6. - №2. - С. 34-38.43.

10. Панираюва И.Д.. Быкова C.B.. Оранов A.M.. Ильлчепко Н.Л. Автоматический гез комбинационных схем на мини-ЭВМ. Автоматизация. математические методы и тление народным хозяйством: Сборник статен/ Под ред. A.M. Корикова. - Томск: -во Томск, у к-1 а» 1990. - С. 65-67.

11. Панкратова И.Д.. Кыкова C.B., Николаева Л.А., Оранов Л.М. Система автмл-:екою синтеза комбинационных схем СИПТЕЗ-Ф.'/ Управляющие системы н маши- !991.-№1.-С. 3-9.

1 ? Оранов A.M.. Андреева Л.Н. Алгоритм стпезз и компоновки одноярусных схем коюрых базисах'/ Контроль. измерение. диагностика, ремонт и 1с.хпнческое обеду-анне радиоэлектронных систем: Тез. докл. нпуч.-техтг. копф. 23-25 октября 1991 i. -Межведомственный координационный совет rio методам и средствам измерений и ipo.u. МГИ СССР, концерн 'Транш". ЦКБ "Мередиаи", 1991.-С. 194-195. И. Оранов AM . .Андреева Л.Н. .Алгоритм минимального разбиения системы мно-|п / Авюм.инка и вычислительная 1ехника. - 1992. -№2. - С. 37-44.

14. Оранов .Ч.М., Андреева Л.Н. Ал! орнтм синтеза и компоновки одноярусных схем которых базисах / Автоматика и вычпелгггелпная техника. - 1992. — №5, - С. 57-63.

15. Орапин A.M., Андреева Л.II. «Хлторшм минимального разбиения некоторою >ра обьемон, ' Авнш.инка и вычисли юльная техника. - 1993. 2. - С. 27-35.

In Oranov A.M.. Andrecva L.N. Complexity of some snbproMems of pavilioning objects problem. - Proceedings ol' the International CoiTferenee "Computer- .»Vided Design of :rcle Device*" (CAD DD'95), vl, Minsk. 1995, p. !S.

17, Oranov Д.М. On synthesis of sequential PLD circuits. - Proceedings of the national Coiiietence "Computer- Aided Design of Discrete Devices" (CAD DD"95). vl,

.4. 199 3. p.49.

IS Oparrón A.M. К синтезу комбинационных схем в базисе ПЛИС// Автоматика и ис-ииедкная техника. - 1996. -№1. - С. 27-35.

19 Оранов A.M. Допустимые разбиения в проектировании 1")С" Тгудм третьей •д\ народной на>чно-те.\ничсской KomjiepeimriH "Актуальные проблемы элекзрочгю-рибчрое(роения" (АГПН-96). - 1.6. - ч.2. - Новосибирск. - 1996. - С. 49-52.

20. Ораноп /V.M. О сложности задачи кратчайшего допустимого разбиения// Ni дународиая кош|л;рсШ|Ця "Псееибирекие чтения но математике и механике": Тез. д i.l. Математика. - Томск: Изд-uo Том. ун-ia. - 1997. - С. 161-162.

21. Оранов Л.М. О комбинаторном сходстве задач еитпеча и компоновки схем,'/ томатизация проектирования дискретных систем. Материхил второй международ конференции (12-14 ноября 1997 года, Минск. Том 2). - Минск: Институт техничен кибернетики HAH Беларуси. 1997. - С. 113-118.

22. Оранов А.М. Атгоритм построения кратчайших монотонно-допустимых биений конечных множеств / Автоматизация проектирования дискретных систем, териалы второй международной конференции (12-14 ноября 1997 года, Минек. Тол - Минск: Институт технической кибернетики П.VII Беларуси, 1997. - С. 221-227.

23. Андреева Jl.ll., Оранов A.M. Оценки погрешности двух приближенных а ритмов разбиения// Автоматизация проектирования дискретных систем. Матери второй международной конференции (12-14 ноября 1997 года. Минск. Том 3). - Ми Институт технической кибернетики HAH Беларуси, 1997.-С. 228-231.

24. Андреева J1.H., Оранов AM. О сложности некоторых задач разбиения// Из тия РАН. Теория и системы управления. - 1997. - №2. - С. 114-116.

25. Андреева JI.H., Оранов А.М. Оценки погрешности двух приближенных а ритмов разбиения// Известия РАН. Теории и системы управления. - 1999. - Kai. - С

26. Оранов .V.M. Алгоритм синтеза цифровых схем в базисе неоднородных Ш Моделирование интеллектуальных процессов проектирования и производства. М ри.иы шорой международной научно-технической конференции (10-12 ноября 199 Минск). - Минск: Институт технической кибернетики HAH Беларуси. 1998. - С. '. 215. '

Из результатов, полученных в соавторстве в диссертацию вошли: значь (выражения) параметров Т-метода для задачи синтеза одноярусных комбинацнон с\см в базисах ИМП, ГПУ, 11J1M /12-16/. теоремы о сложности мой задачи и каче г< иоритмов ее решения /23-25/, а также значения (выражения) параметров Г-метода задач компоновки схем в ячейки с заданным членен i ним составом, составляющие Heimo упорядоченные и специальные допускающие наборы объектов /4,5,8,9/.

Заказ Í3 7. Тираж Y00 экз. УОП ТГУ, Томск, 29, Никитина, 4

Введение.

1. Обзор методов синтеза и компоновки схем на современной элементной и конструктивной базе.

1.1. Обзор методов синтеза цифровых схем на базе ПЛИС.

1.2. Обзор методов компоновки схем в заданные ячейки.

2. Допустимые разбиения и проектирование схем на современной элементной и конструктивной базе.

2 1. ЗКДР, ее приложения и метод решения.

2.1.1. ЗКДР и ее приложения.

2 1.2. Возможные методы решения ЗКДР.

2.1.2.1. Метод полного перебора.

2.1.2.2. Методы 0-1 программирования.

2.1.2.3. Метод ветвей и границ.

2.1.2.4. Метод сокращенного обхода дерева поиска.

2.1.3. Обоснование выбора метода решения ЗКДР.

2.1.4. Особенности построения иерархии подзадач ЗКДР и изложения алгоритмов их решения.

2.2. Построение кратчайших монотонно-допустимых разбиений.

2.2.1. Постановка задачи.

2.2.2. Параметры метода.

2.2.2.1. Алгоритмы начального разбиения.

2.2.2.2. Алгоритм перечисления допустимых подмножеств.

2.2.2.3. Операция сокращения.

2.2.2.4. Граничная функция.

2.2.2.5. Доказательство допустимости алгоритма перечисления и операции сокращения.

Допустимые разбиения и синтез одноярусных комбинационных схем в базисах ПМВ, ПЗУ, ПЛМ.

3.1. Построение допустимых разбиений.

3.1.1. Постановка задачи.

3.1.2. Параметры метода.

3.1.2.1. Алгоритмы начального разбиения.

3.1.2.2. Алгоритм перечисления допустимых подмножеств.

3.1.2.3. Операция сокращения.

3.1.2.4. Граничная функция.

3.1.2.5. Доказательство допустимости алгоритма перечисления и операции сокращения.

3.1.3. Пример построения кратчайшего допустимого разбиения.

3.2. Синтез одноярусных комбинационных схем в базисах

П.МВ, ПЗУ, ПЛМ.

3.2.1. Постановка задали.

3.2.2. Метод решения.

Допустимые разбиения и синтез цифровых схем в базисе неоднородных НМЛ.

4,1. Построение допустимых разбиений.

4.1.1. Постановка задачи.-.

4.1.2. Параметры метода.

4.1.2.1. Алгоритмы начального разбиения.

4.1.2.2. Алгоритм перечисления допустимых

I ¡одмножеств. 7В

4.1.2.3. Операция сокращения.

4.1.2.4. Граничная функция.

4.1.2.5. Доказательство допустимости алгоритма перечисления и операции сокращения.

4,13, Пример построения кратчайшего допустимого разбиения.

Л 2. Синтез цифровых схем в базисе неоднородных ПМЛ.

4.2.1. Постановка задачи.

4.2.2. Метод решения.

5. Допустимые разбиения и синтез цифровых схем в базисе однородных ПМЛ с универсальными макроячейками.

5.1. Построение допустимых разбиений.

5.1.1. Постановка задачи.

5.1.2. Параметры метода.

5,1.2.1. Алгоритмы начального разбиения.

5.! 2.2. Алгоритм перечисления допустимых подмножеств.

5 1.2.3. Операция сокращения.

5.1.2.4. Граничная функция.

5.1.2.5. Доказательство допустимости алгоритма перечисления и операции сокращения.

5.1.3. Пример построения кратчайшего допустимого раз биения. —.

5.2. Синтез цифровых схем в базисе однородных ПМЛ с универсальными макроячейками.

5.2.1. Постановка задачи.

5.2.2. Метод решения.

6. Допустимые разбиения и компоновка схем в ячейки, различные по вместимости или по числу выводов.

6 .1. Построение допустимых разбиений.

6.1.1. Постановка задачи.

6 « 2. Параметры метода.

6.1.2.1. Алгоритмы начального разбиения.

6.1.2.2. Алгоритм перечисления допустимых подмножеств.

6.1.2.3. Операция сокращения.

6.1.2.4. Граничная функция.

6.1.2.5. Доказательство допустимости алгоритма перечисления и операции сокращения.

6Л.З. Пример построения кратчайшего допустимого разбиения.

6.2. Компоновка схем в ячейки, различные по вместимости или по числу выводов.

6.2.1. Постановка задачи.

6.2.2. Метод решения.

7. Допустимые разбиения и компоновка схем в ячейки с заданным элементным составом.Л

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

7,1 1. Постановка задачи.

7.1.2. Параметры метода.

7.1.2.1. Алгоритм начального разбиения.

7.1.2.2. Алгоритм перечисления допустимых подмножеств.

7.1.2.3. Операция сокращения.

7.1.2.4. Граничная функция.

7.1.2.5. Доказательство допустимости алгоритма перечисления к операции сокращения.

7.1.3. Пример построения кратчайшего разбиения, допустимого д.,н частично упорядоченного допускающего множества.

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

7.2.1. Постановка задачи. 2.2. Параметры метода.

7:2.2.1. Алгоритм начального разбиения.

7.2.2.2. Алгоритм перечисления допустимых подмножеств.

72 2.3. Операция сокращения.

7.2.2-4. Граничная функция.

7.2.2.5. Доказательство допустимости алгоритма перечисления и операции сокращения.

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

73.1. Постановка задачи.

7.3.2. Параметры метода.

7.3.2.1. Алгоритм начального разбиения.

7.3.2.2. Алгоритм перечисления допустимых подмножеств.

13.23. Операция сокращения.

7-3-2.4. Граничная. Функция.

• • • I А л

7,3.2.5. Доказательство допустимости алгоритма перечисления и операции сокращения.

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

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

7.5. Компоновка схем в ячейки с заданным элементным составом.

7.5.1. Постановка задачи.

7.5.2. Метод решения.

8. Сложность задач разбиения, и качество алгоритмов их решения.

8 1. Сложность задач.

8,2. Оценки погрешности алгоритмов начального разбиения.

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

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

За последние десятилетия элементная база УЛУ при относительной стабильности конструктивной базы УЛУ прошла в своем развитии путь от элементов малой степени интеграции, примером которых могут служить интегральные микросхемы серий К133, К155 и т.п. [1,2], до интегральных микросхем большой и сверхбольшой степени интеграции, т.е. до БИС и СБИС, среди которых видное место занимают программируемые логические интегральные схемы (ПЛИС) [3-7] или, другими словами, программируемые логические устройства (ПЛУ) - Programmable Logic Devices (PLD), в том числе такие их разновидности, как программируемые логические матрицы (Г1ЛМ) - Programmable Logic Arrays (PLA), программируемые постоянные запоминающие устройства (ППЗУ), или просто (ПЗУ), - Programmable Read Gnly Memory (PROM) и программируемые матрицы логики (ПМЛ) -Programmable Array Logics (PAL).

Относительная стабильность конструктивной базы УЛУ состоит в том, что набор основных характеристик того или иного современного конструктивного узла, несмотря на миниатюризацию, стандартизацию и унификацию, остается таким же, как и десятилетия назад, и включает такие характеристики, как вместимость узла, число его внешних выводов (контактов в разъеме) и номенклатура (элементный состав) узла. Обобщающим понятием для обозначения всего многообразия конструктивных узлов обычно служит понятие "ячейка". Различаются ячейки двух типов: 1) ячейки ограниченной вместимости и с ограниченным числом выводов и 2) ячейки с заданным элементным составом (с заданной номенклатурой). Примером ячеек первого типа могут служить типовые элементы замены (ТЭЗ), панели, рамы, стойки и т.п., а примером ячеек второго типа - микросхемы серий К133, К155 и т.п. [1,2], а также базовые ячейки на кристалле, составленные из нескоммутированных компонент - транзисторов, резисторов, диодов и т.п. [8-10]. Кроме того, условно, ячейкой с заданным элементным составом можно считать любую площадку с посадочными гнездами различной (в частности, прямоугольной) формы и квадратуры, а также любое помещение с отсеками различной (в частности, прямоугольной) формы и кубатуры.

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

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

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

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

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

Научная новизна. Для всего многообразия выделенных вариантов задач синтеза и компоновки схем предлагается единая математическая модель - комбинаторная оптимизационная задача кратчайшего допустимого разбиения (ЗКДР) конечного множества (набора объектов), в рамках которой каждый конкретный вариант формулируется как подзадача ЗКДР. При этом казалось бы различные варианты задач синтеза и компоновки схем иногда сводятся к одной и той же подзадаче ЗКДР. Этим полностью подтверждается и проясняется в некоторых деталях высказанное в [11] предположение о комбинаторном сходстве задач синтеза и компоновки схем. Обсуждаются возможные методы решения ЗКДР, среди которых аргументированно выбирается метод сокращенного обхода дерева поиска [12-14], называемый далее для краткости Г-методом, и указываются способы его алгоритмизации применительно к различным подзадачам ЗКДР, имеющим прикладное значение. Тем самым предлагаются, как правило, точные алгоритмы решения этих подзадач ЗКДР и всех сводимых к ним вариантов задач синтеза и компоновки схем. ЗКДР, Г-метод ее решения и способ сведения к

ЗКДР того или иного варианта задачи синтеза или компоновки схем составляют суть предлагаемого общего подхода к решению обширного многообразия вариантов задач синтеза и компоновки схем. Этот подход, по сравнению с известными, позволяет шире и полнее использовать возможности современной элементной и конструктивной базы УЛУ для повышения качества проектируемых устройств и может служить основой для разработки все новых и новых стандартных (основанных на Г-методе) алгоритмов синтеза и компоновки схем при сохранении современных тенденций развития элементной и конструктивной базы УЛУ, в частности, при сохранении в составе элементной базы УЛУ "РАЬ-подобных" функциональных блоков, как это характерно для развития БИС СРЬО-семейства фирмы ХИЛЫХ [7]. Кроме того, есть основания полагать, что он применим не только в разработке УЛУ. Полученные в работе результаты по решению конкретных подзадач ЗКДР и, следовательно, всех сводимых к ним вариантов задач синтеза и компоновки схем демонстрируют собой примеры успешного применения этого подхода в проектировании УЛУ. С применением средств и методов теории ЫР-полноты [15] исследуется сложность всех сформулированных подзадач ЗКДР и качество предложенных алгоритмов их решения. В процессе этого исследования дополнительно выясняется, что сформулированные в данной работе подзадачи ЗКДР, в свою очередь, содержат подзадачи, эквивалентные таким известным задачам, как УПАКОВКА В КОНТЕЙНЕРЫ, МИНИМАЛЬНОЕ ПОКРЫТИЕ [15], О МАКСИМАЛЬНОМ ПАРОСОЧЕТАНИИ В ГРАФЕ [16] и др.

Практическая ценность. В целом можно утверждать, что в данной работе предлагается принципиально новое математическое и отчасти информационное обеспечение системы автоматического синтеза и компоновки схем на современной элементной и конструктивной базе, как части потенциальной САПР, обладающей в должной мере всеми перечисленными выше свойствами, в том числе высокоустойчивой к изменениям элементной и конструктивной базы УЛУ при сохранении современных тенденций ее развития. Все последующее изложение является детальной аргументацией этого тезиса, посредством систематизации и обобщения результатов, опубликованных ранее в [51-76] и составивших основу данной работы.

Реализация полученных результатов. Все полученные в диссертационной работе результаты можно разделить на две части: 1) результаты, полученные до 1995 г. и послужившие заделом для получения гранта РФФИ, и 2) результаты, полученные в течение 1995-1997 г.г., при финансовой поддержке РФФИ (грант 95-0100705). Наиболее ранние результаты по компоновке схем в ячейки с заданным элементным составом, относящиеся к первой части, были реализованы в САПР УЛУ ЦКБ "Алмаз" (г. Москва). Следующие за ними (по времени получения) результаты по синтезу одноярусных комбинационных схем в различных базисах ПЛИС типов ПМВ, ПЗУ, ПЛМ, также относящиеся к первой части, реализованы в настоящее время в виде экспериментальной распределенной САПР, в которой подзадача ЗКДР решается на удаленном компьютере высокой производительности, а сведение задачи синтеза к подзадаче ЗКДР и преобразование получаемого от удаленного компьютера разбиения набора объектов в схему осуществляется на местном компьютере меньшей производительности. Программа разбиения в составе этой САПР (программа решения подзадачи ЗКДР) испытана на нескольких десятках примеров различной сложности, в том числе, соответствующих примерам синтеза реальных устройств (так называемых "benchmarks"), что говорит о практической пригодности этой программы. Результаты, относящиеся ко второй части, отражены (реализованы) в промежуточных и итоговом отчетах по гранту, одобрены РФФИ и рекомендованы им для использования в промышленном производстве УЛУ.

Апробация работы. Все результаты [51-76], составившие основу данной работы, по мере их получения обсуждались на совместных семинарах кафедры математической логики и проектирования, кафедры программирования Томского государственного университета (ТГУ) и лаборатории синтеза дискретных автоматов Сибирского физико-технического института (СФТИ) при ТГУ. Кроме того, в разные годы они докладывались на всесоюзных или международных конференциях в г.г. Риге, Киеве, Москве, Минске, Новосибирске и Томске, что подтверждается соответствующими публикациями докладов [51,55,60,69,71-73] и тезисов докладов [62,66,67,70,76]. Прохождение отчетности по линии РФФИ и частичное использование результатов диссертации в учебном процессе при подготовке студентов соответствующих специальностей в ТГУ также можно считать апробацией диссертационной работы.

Структура и объем диссертации. Диссертация состоит из введения, восьми глав, заключения и списка цитированной литературы. Объем диссертации составляет 200 страниц текста, набранного в Word 6.0 (Шрифт - Times New Roman Суг, размер шрифта - 14 pi, межстрочный интервал - 1.5 строки), в том числе, титульный лист - 1 стр., оглавление - 6 стр., основной текст, включающий 6 рис. и 12 таблиц, - 183 стр., библиография из 76 наименований - 10 стр.

III. Результаты исследования сложности рассмотренных в работе задач, полученные с применением теории ЛУ-полноты [15] и сформулированные в главе 8 в виде пяти теорем о сильной МР~ трудности задач 2-6 и девяти утверждений о полиномиальной сложности одиннадцати частных случаев (подзадач [15]) задач 2-6.

IV. Оценки погрешности двух алгоритмов начального разбиения, установленные в главе 8 посредством двух теорем.

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

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

-186-ЗАКЛЮЧЕНИЕ

В диссертации разработан общий подход к решению широкого класса задач синтеза и компоновки схем логического управления на современной элементной и конструктивной базе. Под современнной элементной базой понимаются программируемые пользователем логические устройства (Eield Programmable Logic Devices) или, другими словами, программируемые логические интегральные схемы (ПЛИС) такие, как программируемые логические матрицы (ПЛМ), программируемые постоянные запоминающие устройства (ППЗУ), программируемые матрицы логики (ПМЛ), а также программируемые матрицы вентилей (ПМВ). Под современной конструктивной базой понимаются ячейки ограниченной вместимости и с ограниченным числом выводов, а также ячейки с заданным элементным составом (номенклатурой). В роли первых могут выступать типовые элементы замены, панели, рамы, стойки и т.п., а в роли вторых - интегральные микросхемы отечественных промышленных серий таких, как К133, К155 и т.п. [1,2], базовые ячейки на кристалле, составленные из нескоммутированных компонент таких, как резисторы, транзисторы, диоды и т.п. [8-10], а также любые площадки с посадочными гнездами различной формы и квадратуры и любые помещения с отсеками различной формы и кубатуры. Подход ориентирован на автоматический синтез и компоновку схем логического управления и включает три основных элемента: 1 ) оригинальную общую математическую модель всех рассматриваемых в работе задач синтеза и компоновки схем - комбинаторную оптимизационную [15] задачу кратчайшего допустимого разбиения (ЗКДР) набора объектов, 2) известный метод сокращенного обхода дерева поиска [12-14], называемый здесь для краткости Г-методом, - как метод решения

ЗК'ДР; 3) оригинальный способ представления в виде ЗКДР различных задач синтеза и компоновки схем. В отличие от других подходов к решению этих задач, он обеспечивает более широкое использование возможностей современной элементной и конструктивной базы для уменьшения числа затрачиваемых на синтез и компоновку схем ПЛИС и ячеек, допуская наличие в базисе синтеза нескольких (в том числе разнотипных) ПЛИС с несравнимыми наборами значений их параметров и допуская в конструктивном базисе задачи компоновки несколько ячеек с несравнимыми парами значений вместимости и числа выводов. При этом не ограничивается число принимаемых во внимание параметров фигурирующих в задачах объектов (оператора синтезируемой схемы, представляемого системой ДНФ структурных функций выходов и функций возбуждения триггеров, базисных ПЛИС, схем, элементов схем, ячеек) и теоретически всегда гарантируется минимум числа затрачиваемых ПЛИС и ячеек. Решение той или иной конкретной задачи синтеза или компоновки схем на основе данного подхода, т.е. разработка алгоритма ее решения, состоит в выделении частного случая (подзадачи [15]) ЗКДР, алгоритмизации Г-метода применительно к этому частному случаю посредством подходящего определения значений (выражений) его параметров (множества алгоритмов начального разбиения, алгоритма перечисления, операции сокращения, граничной функции) и в указании способа представления решаемой задачи в виде выделенного частного случая ЗКДР, а также способа преобразования получаемого допустимого разбиения в схему. Подход может служить основой для разработки все новых и новых стандартных (основанных на /-методе) алгоритмов синтеза и компоновки схем при сохранении современных тенденций развития элементной и конструктивной базы, в частности, при сохранении в составе элементной базы цифровых устройств "РАЬ-подобных" функциональных блоков, как это характерно для развития БИС СРЬВ-семейства фирмы ХИЛЫХ [7]. Кроме того, есть основания г гола гать, что он применим не только в проектировании устройств логического управления.

На защиту выносятся:

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

II. Разработанные на его основе алгоритмы решения следующих задач:

1) построения кратчайших монотонно-допустимых разбиений наборов объектов;

2) синтеза минимальных по числу элементов одноярусных комбинационных схем, как допускающих, так и не допускающих объединение выходов своих элементов по схеме ИЛИ, в некоторых базисах ПЛИС типов ПМВ, ППЗУ, ПЛМ;

3) синтеза минимальных по числу элементов цифровых схем в базисе так называемых неоднородных ПМЛ (неоднородная ПМЛ -это предложенная в данной работе обобщенная структура (модель) некоторых реальных ПМЛ таких, как ПМЛ семейства РА1Л6К8 [6]);

4) синтеза цифровых схем в базисе гак называемых однородных ПМЛ с универсальными макроячейками (однородная НМЛ (ПЛИС) с универсальными макроячейками - это предложенная в [23] обобщенная структура (модель) реальных ПМЛ, выпускаемых фирмой АНега [3,4]);

-1895) компоновки схем в ячейки ограниченной вместимости и с ограниченным числом выводов;

6) компоновки схем в минимальное количество ячеек с заданным элементным составом.

1. Справочник по интегральным микросхемам/ В.В. Тарабрин, С В. Якубовский, Н.А Барканов и др. - 2-е изд., нерераб. и доп. - М.: Энергия, 1981. - 816 с.

2. Интегральные микросхемы: Справочник/ Б.В. Тарабрин, Л.Ф. Лунин, Ю.Н. Смирнов и др. М.: Радио и связь, 1983. - 528 с.

3. Коул Б.К. Второе поколение программируемых логических интегральных схем// Электроника. 1988. - №10. - С. 18-22.

4. Коул Б.К. Фирма А Нега готовит производство стираемых ПЛИС на 5000 логических вентилей 60 Мщ/У Электроника. 1988. - №10. -С 22-25.

5. Шипулин С. ПЛИС ~ новый класс микросхем// Радио. 1993. -№11.-С. 2Д13.

6. Соловьев В.В. Проектирование функциональных узлов цифровых систем на программируемых логических устройствах. ~ Мн.: ПКООО "Бестпринт", 1996.-252 с.

7. XILINX. The Programmable Logic Date Book. 2100 Logic Drive San Jose, California 95124 Unated States of America. 1998.

8. Ватанабэ M,., Асада К., Кани К. Проектирование СБИС. М.: Мшх, 1988.-304 с.9, Киносита К., Асада К., Карацу О. Логическое проектирование СБИС. М.: Мир, 1988. - 309 с.

9. Мурога С. Системное проектирование сверхбольших интегральных схем. В двух книгах. М.: Мир, .1985. -- Кн.1 288 с. -Ки.2 290 с.

10. П. Баранов С.Н., Скляров В.А. Цифровые устройства на программируемых БИС с матричной структурой. М.: Радио и связь, 1986. - 272 с.

11. J 2. Агибалов Г.П., Беляев В.А. Метод сокращенного обхода дерева поиска, и его применение в синтезе интегральных схем// Управляющие системы и машины. 1977. - №6. - С. 99-103.

12. Агибалов Г.Г1., Беляев В.А. Технология решения комбинаторно-логических задач методом сокращенного обхода дерева поиска. Томск: Изд-во Томск, ун-та, 1981. 125 с.

13. Агибалов Г.П. Дискретные автоматы на. полурешетках. -Томск: Изд-во Томск, ун-та, 1993. 227 с.

14. Гэри М., Джонсон Д. Вычислительные машины и fруднорешаемые задачи. М.: Мир, 1982. - 416 с.

15. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. - 512 с.

16. Закревский А.Д. Логический синтез каскадных схем. М.: Наука, 1981.-414 с.

17. Бибило П.Н. Синтез комбинационных ПЛМ-структур для СБИС. Мн.: Навука i тэхшка, 1992. - 232 с.

18. Дудкин A.A. Логический синтез одноярусных комбинационных схем в базисе Г1ЛМ/У Теория и методы автоматизации проектирования. Минск: Ин-т техн. кибернетики АН БССР, 1984. - Вып.4. - С. 135-140.

19. Бибило П.й. Анализ и классификация декомпозиционных методов синтеза комбинационных схем на ПЛМ и ПЗУ// Автоматика и вычислительная техника. 1990. -Xsl. - С. 95.

20. Палаше A.B., Баркалов A.A., Юсифов С.И., Стародубов К.Е., Швец А.Г. Реализация микропрограммных автоматов на ПЛИС/7 Управляющие системы и машины. 1991. - №8. - С. 18-22.

21. Палагин A.B., Опанасенко В.Н., Чигирик Л.Г. К синтезу адаптивных структур на ПЛИС// Управляющие системы и машины. -1993.-№5.- С. 1247.

22. Соловьев В.В. Использование программируемых матриц логики при синтезе комбинационных схем// Управляющие системы и машины. 1995. - №4/5. - С. 53-56.

23. Я. Соловьев В.В. Сложность реализации устройств логического управления на ПЛИС// Известия РАН. Теория и системы управления. . 1995. №5. -- С. 248-256.

24. Holland J.H. Adaptation in natural, and Artificial Systems. A Bradford Book The MIT Press Cambridge, Massachusetts London England, 1994. -21 Ip.

25. Goldberg D.E. Genetic Algorithms in Search, Optimization & Machine Learning. Addison-Wesley Publishing Company, Inc., 1989. -4 i 2p.

26. Soldek J., Yanushkevich S. Genetic Algorithms in Logic Design// Proceedings of the International Conference on Computer-Aided Design of Discrete Devices (CAD'95)* v2, Minsk-Szeczcin, 1995. P. 17-25.

27. Doiidkm A.A., Shcstakov E.A. Construction of multilevel PLA networks by using one-level synthesis methods// Proceedings of the Second International Conference on Computer-Aided Design of Discrete Devices (CAD DD'97), vi, Minsk, 1997. P. 86-93.

28. Штейн M.E., Штейн Б.Е. Методы машинного проектирования цифровой аппаратуры. ~ М.: Советское радио, 1973. 296 с.

29. Мелихов А.Ы., Берштейн Л.С., Курейчик В.М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974. - 304 с.

30. Ландау И,Я. Применение ЦВМ для проектирования ЦВМ. -М.: Энергия, 1974. 152. с.

31. Селютин В .А. Машинное конструирование электронных устройств. M.I Радио и связь, 1977. - 383 с.

32. Теория и методы автоматизации проектирования вычислительных систем/ Под ред. М. Брейера. М.: Мир, 1977. -284 с.

33. Фридман А., Менон П. Теория и проектирование переключательных схем. М.: Мир, 1978. - 582 с.

34. Geoffrion A.M., Marsten R.E. Integer programming: a framework rid state-of-the-art survey// Management Science, 1972. vol.18. - №9.

35. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. М.: Наука, 1987. - 248 с.

36. Михалевич B.C., Сергиенко И.В. и др. Пакет прикладных программ для решения задач дискретной и нелинейной оптимизации (пакет ДИСНЭЛ)// Кибернетика. 1991. - №3. - С. 36-45.

37. Корбут A.A., Финкелыптейн Ю.Ю. Дискретное программирование. М.: Наука, 1969. - 368 с.

38. Литтл ДЖ., Мурти К., Суини Д., Кэрел К. Алгоритм для решения задачи коммивояжера// Экономика и математические методы. М.: Наука, 1965. -№1.~ С. 94-107.

39. Кристофидес Н. Теория графов. Алгоритмический подход. -М.: Мир, 1978.-432 с.

40. Рейнгольд, Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. - 476 с.

41. Закревский А.Д., Анищенко А.Н., Балаклей Л.И., Елисеева H.A., Оранов А.М. и др. Синтез асинхронных автоматов на ЭВМ/ Под общей ред. Закревского А.Д. Минск, Наука и техника, 1975. - 184 с.

42. Агибалов Г.П., Оранов А.М. Лекции по теории конечных автоматов. Томск: Изд-во Томск, ун-та, 1984. - 185 с.

43. Оранов A.M. Алгоритм кодирования состояний автомата, реализуемого на 11ЛМ// ВИНИТИ, №2149-85 Деп. от28.03.85. -7 с.

44. Агибалов Т.П., Оранов A.M. Покрытие логических схем модулями некоторых серийных систем// ВИНИТИ, № 5860-85 Деп. от 07.08.85. 19 с.

45. Агибалов Т.П., Оранов A.M. Покрытие логических схем модулями некоторых серийных систему/ Кибернетика. 1986. - №2. -С. 34-38,43.

46. Панкратова И.А., Быкова C.B., Николаева Л.А., Оранов А.М. Система автоматического синтеза комбинационных схем СИНТЕЗ-Ф/У Управляющие системы и машины. 1991, №1. - С. 3-9.

47. Оранов А.М., Андреева JI.H. Алгоритм минимального разбиения системы множеств// Автоматика и вычислительная техника. 1992. - №2. - С. 37-44.

48. Оранов A.M., Андреева Л.Н. Алгоритм синтеза и компоновки одноярусных схем в некоторых базисах// Автоматика и вычислительная техника. 1992. - №5. - С. 57-63.

49. Оранов А.М., Андреева Л.Н. Алгоритм минимального разбиения некоторого набора объектов// Автоматика и вычислительная техника. 1993. - №2. - С. 27-35.

50. Oranov А.М., Andreeva L.N. Complexity of some subproblems of partitioning objects set problem. Proceedings of the International Conference "Computer- Aided Design of Discrete Devices" (CAD DD'95), vl, Minsk, 1995, p.48.

51. Oranov A.M. On synthesis of sequential PLD circuits. -Proceedings of the International Conference "Computer- Aided Design of Discrete Devices" (CAD DD'95), vl, Minsk, 1995, p.49.

52. Оранов A.M. К синтезу комбинационных схем в базисе ПЛИС// Автоматика и вычислительная техника. 1996. - №1. - С. 2735.

53. Оранов A.M. Допустимые разбиения в проектировании РЭС// Труды третьей международной научно-технической конференции feАктуальные проблемы электронного приборостроения" (АПЭП-96). -т.6. 4.2. - Новосибирск. - 1996. - С. 49-52.

54. Оранов A.M. О сложности задачи кратчайшего допустимого разбиения// Международная конференция "Всесибирские чтения поматематике и механике": Тез. докл. т. 1. Математика. Томск: Изд-во Том. ун-та. - 1997. - С. 161-162.

55. Андреева Л.Н., Оранов A.M. О сложности некоторых задач разбиения// Известия РАН. Теория и системы управления. 1997. -№2. - С. 114-116.

56. Андреева Л.Н., Оранов A.M. Оценки погрешности двух приближенных алгоритмов разбиения// Известия РАН. Теория и системы управления. 1999. - №1. - С. 85-33.