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



ЛШТНГРЛДСКМ ОРДЕНА ЛЕ1К11А К ОРДГЖ ОКТйШСКОЙ РЕВОЛОШ 'ЭЯЫПРШЖШЧЕСпИЙ Ш-ЕТИТЯ имени Б.И. УЛЫШОВА (Ла-ИНА)

РАЗВИТИЕ Я ПРШШЕШЕ ЛССОЦИЛШНЬК ВЫЧИСЛИ^! И СТГУЯТП

Специальность: 05.13.13 - Вычислительные ми^инн, комплекс и,

системы и сети

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

КОКЛЕБ ОЛЕГ ГРИГОРЬЕВ

УДК (Ж. 327.25:601.3.01:3.05

Ленинград - 1983

Работы выполнена' в Ленинградской ордена Ленина и ордена Ок'/яоръской Революция &лект;.отехничвскон институте имени

Б.Й. Ульянова (Ленина)

О Ф я ц и ь л ь и и е о н попе к г и. :

Лауреат Ленинской премии доктор технических наук профессор

Евреинов О,В.

Доктор технических наук профессор Очин Е.Ф.

Доктор технических ноук профессор Ли С.К.

Ьиушез яродпринтае - ¡¡а^чно-исслздовательоккй институт

однородных микропроцессорных вычислительных систем

Защита диссертации состоится "_" _ ■ 1389 г.

ь______часов нь заседании специализированного совета Д 0G3.36.0c

Ленинг4л<дского ордена Ленина к ордена Октябрьской Революции электротехнического институту имени .В.И.Ульянова (Ленина.) по адресу:.

1-УЮ22, Лешш:-рад, ул.Прсф.Попова, 5,.

С дассартациеН шяно ознакомиться в библиотеке института; Автореферат разделан "_" ________ ГЭ8Э г.

Учёта; секретарь

спицийлизироь&иного сонета . Зкало А,А.

ОБЩАЯ ХАРАКТЕРИСТИКА РЛЪС'Ш

Актуальность проблемы. Полишениа произгодвгвлыюсти к уровни [ктеллекгн ЭВМ является У-агистрачышм тпраяясннем разштия срьд-;тв иичис.тительной техники, -котсроку в значительной отепои»; ссот-1втствуют ассоциативный шпислзния и структур!. /АБС/ аа счьт:

- «сгественкого параллелизма, кмс-кщего место при выполнении шераций кад.ь-лссиЕеми др.нкых по принципу "одиночный поток коаднл • множественный поток данных"; - , '

независимости времени вычислений ог числа одновременно об--юбатизаемых операндов;.

- прсстотм'програширования, благодаря использования понятия функции в истинно катт.ятичсском смысла;

- свойств однородности и регулярности, приводящих к сущкст-ззнпоиу сокращении числа типов БИС прп построении ЭВ'Л;

- возможности построения оВМ о иаколлвнивм опыта решения за-1ач; . ;

расположенности ассоциативной памяти /АН/ к аппаратной ре- ' ПК361ЩИ процедур принятая решений, присущих маашябц о раз-.гитшл штеллактоы;

~ всэыиеиостк построения структур ЗШ со встроенным контрогам и диагностикой неисправности, с внутренне иитзрпретецибй 1зикоа шеокего уровня,*'

Значительный вклад в разработку принципов косгрсэнля АБС ыесли работы Д. ¡I,- Ь'нтора, Т. Кохонеиа, Л.11. Крайзмери, М.М. Лебединского, й.З.Лрак'пцшли, £.Розекблаттй., ЯЛ.Фета, К.Фостера, \С.Цейтлина и других. Однако, с точки зрении современной концеи-иш вычислона];, основанной па по.нятик/ лгиачлк, программы и инфор-» ¿еционногэ процессу, исследованы в области аВС проводились вид 2 вязи мевду соооЛ. Так, с 'моменте, перскх разработок и вониае ар-ептектура бильиаксхыа ассоциативных изиин /Ж/, иаиркыер 1Ц.1ЛК ЬТАЯлЛ/I ОКЙЛ/, отраяйла взгляд па неё как .ьа ооль:цой ьц.ифг/о-

..ie?i>, призиодящий вычисления над масивагш чисел, что привело к

- гипертрофированному развитию операционной части параллельных иШ по срашьшт с управляющей;'

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

- слабому развитии технологии параллельного программирована

- половинчатой реализации идеи однородности и регулярности структур 3UM, .

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

Плодотнорно развивались структуры All для решения задач инфор мацйонно-логическях, распознавания образов. Известно, что первоначально перцептронные системы ш»сновались ассоциативными. Однако н эти работы долгое время находились в стороне от столбовоИ дороги развитии КГ.

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

Всё это дискредитировало' идею.ассоциативности, способствовала формированию консирватиэма- у пользователей ц разработчиков. Однако с развитием интегральной технологии, когда фактор.экономичности при разработке новых структур ЭВ1А перестаёт играть с голь решающей значение, как прехде, и с публикацией отечественных и зарубежных проектов УШ пятого поколения, основными чертами которых являются параллельность и интеллектуальность, исследования в области АБС нужно объединить на позициях "единства аппаратуры я программы" при соблюдении ведущей рели программы /алгоритма/, поставив их ш Прочную практическую основу. Этим объясняется выбор теш работы и со проблематика. Её актуальность подкреплена Поста-, новлением АН СССР и Шнауаа СССР » 1473/146 от 29.12.80/31. ГЛ.80,.

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

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

Предмет исследования: структурныэ спссоби пот.иешт производительности и уровня'интеллекта УЗМ, опирающиеся на сно;!стгю ассоциативности.

.Уятодика. исследования опирается на яе^врхяческув схему "зпдз-ча-алгаритм-интерпретзция" с оценкой принятого решения на кпял'-'М иерархическом уровне.

Пути достижения поставленной, цели просматриваются в рнярпбот-

ке

- апгоритшпескнх основ., принципов про гр а.'.'ли р о в з н и л ассоциативных вычислений и способов их структурно-иикропрегршоггюй интерпретации; '

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

•- п^ципов нечисловых .'ассоциативных вычислений н способов их структурной интерпретации; .

объедини e.vitx в прикладную теорию ассоциативных вш.челений к структур, Еклчча'оцу» исследование возматиоств практической реализации АШ на современно;* элементной »Заде.

Структура работы. Диссертация состоят из зиеденея, суть которого излояена ?,шо, се.'.'л глав, загстпченил и приложения. Работа изложена на 262стр.!лаа)йгю11ис!гогз текста; иллюстрирован^ 121 ряс. и 45 табл. .

Первач гласа посвящена разработке алгоритмических основ ас-сощ'итивинх шчислениЛ, определяешь парой "сетевая схема алгоритма /ССЛ/ - и.чтсрпЪетацйя её в ЛП", чем и подчёркивается неразрывная связь аппаратуры и программ при вров;ггирования ассоциативной 'КаШЕш.

ССА предстаадяютсй аагружвтшу орвоигаровайгаи» храмом 1КХ»$),

дугн которого помечены значениями булевского вектора условных оператором l^fcA .а варшмнаи S^ t S сопоставлены линейные последовательности операторов присваивания Ар , именуемых соответственно обобщенными условным операторами и составными операторами присваивания, сокращённо J, и р операторами. Выделение из oi-оператора требуемой для корректной работы ССА совокупности условных операторов £X выполняется посредством оператора М^маскирования, располагаемого з конце каждого оператора . Упорядоченная совокупность операторов задаёт множество путей срабатывания ССА.

Интерпретация ССА в АН связывается с представлением элементарного акта работы .• лгорит«п отношением /ассоциацией/ вида t; — ' tU"

в которой<...> - J -оператор; S^, - имена £ -операторов;

r(SLls •).

I, если S; R, Sj.

.0, в противном случае, -'условие наполнения перехода в алгоритме /условие срабатывания ССА/, Шшеслво последовательностей срабатываний однозначно определяет ССА. Совокупность пар («¿м S;) образует ассоциативную /к/, а совокупность нар (Sj><.■•>) - информационную /И/ часть, а множество значений ^ s_j.) - линейку индикаторов All.

Утверждение I.I. В базисе В, состоящем из об и J, .операторов может быть построена любая микропрограмма.

От структурированных схем микропрограмм ССА отличаются минимальностью базиса В, программированием без операторов ^о "to , tlo и Ij. , более, чем в два раза меньшим количеством искусственных-переменно вводимых'для структуризации микропрограммы.

Для автоматизации процесса построения ССА по операторной схеме формулируется к конструктивно доказывается следующая теорема.

Теорема 1.1. Класс схем Яноьа транслируем в класс сетевых схем.алгоритмов.

Доказательство строится на понятии взвешенной отмеченной фор^-цулы перехода j ^ , когда каждому оператору ...> сопоставляется вес (О -I, а каждому оператору - вес а) = n, + I, где ft -

число одновременно выполняемых условных операторов схему Яяова со значением ИСТИНА. '

Условие окончания процесса трансляции имеет еид;

Разработкзаютсн такие эквивалентные преобразования СОЛ, как уменьшение чис.ла операторов кикуопрогражы, функционильио-времсн-нне совмещения г.'лкрапрогр'^л., отмечается целесообразность использования ССА iij.ii доказательстве изомор! ииьи микропрограмм.

Производится расширение ССА на случай параллельных вычислений. Операторный базис параллельких ССА /иССА/ дополнительно вють-чает оператор распараллеливания Я, и оператор соединения Ь ■ Аналогично исследуются свойства корректности, полноты и связр с другими схемами алгоритмов. Формулируются и конструктуивно доказываются соответствушие теоремн трансляции с использованием техники построения систем взвешенных отмеченных форг/ул перехода.

Если } -оператор представить оператором цикла с нулевым значением параметра, то структура ПССА оказывается близкой ~ структуре р -алгоритмов Евреинова-Косарева, описывающих г,роцесс распараллеливания алгоритмов по циклам.

Для последующего перехода к структурам микропрограммное автоматов управления с ассоциативной выборкой последовательностей микрокоманд /КЖСЛ/ разрабатывается алгоритмическая модель и обобщённая структура.ассоциативной мащинк. Лента памяти машины разделена на три части. В первой запоминается список ассоциаций вида ,(!}, колинд работы АМ, во вторсн; - признак текущей ассоцкппии, определяема парой (¿„.^ > в третьей - входные символы оск£Х .

Аналогично строится модель параллельно! ЛМ. Отличие её от предыдущей заключается в разделении значения ассоциации на безусловное и условное, задаваемое операторами Я и Ь . Алгоритмическая модель этой ЛМ соответствует модели гкчнслительноЛ систеьм с общей памятью и общим управлением.

Отмечаются такие особенности достроенных моделей ДМ, как управление данными, табличный характер обработки и."4эрыацик, возможность оперативного контроля и диагностики неисправностей, что выгодно отличает'её от ЭВМ фен-неИвановской архитектуры.

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

Алгоритмическую основу языка параллельного ассоциативного

кккронрогрйШирой£Ийя /ПАЙ/ образуют ДССА, морфологическую - линейная .[лрма-оаписи ПССА, наилучший образом соответствующая линейной структуре большинства современных ЭВМ, являющихся инструмент та шюй поддержкой технологии ПАМ.

Описание синтаксиса яьика представлено в бекусо-науровской Структура язькв 11Ш определяется скобочным терминалами /СТ/, относящимися к классу нерегулярных СТ, которым соответствует ивтомит с лентой памяти с ассоциативным доступом. Ставится задача построения таких привил работы этого автомата, чтобы время контроля пари/мельнои микропрограммы линейно зависело от её длины. Ггиение плавленной задачи связивается с разработкой метаязыка ¡10 -гралгатик.

Определение 2■ Г■ Я&-грам.удтикой ланка I (&) называемся упо~' ] /Ушчанная четверка конечных непустых шокеств вида

V - [ , £ » I, Ь } -^вспомогательный_ал4®вят /алфавит внутренний памяти автомата/; 51 ~Ь I.Т ^ - синтермальний алфавит; '¿о & & - аксиома ^-грамматики /имя начального комплекса правил/; [I - Ц 1;,- схеш -грамдатики.

Правило е^т.'.еет вид:

«Л. о К Ь)

Ь пг.

где ^- пин комплекса правил-преемников; М^ С. . ) - п,-арное отношение, определяющее вид операции1 над внутренней памятью ь зависимости от « -[0,1,2} .

Определение '¿.'¿. Цепочка ^ »о, СЦ .'.-(X,. называется выводом и. из а, и обозначается'а . ес!н для любого •

суцветвуят 'I^И ■г££$1та1ше,'•что а^. ^

(а <:

-вывод называется законченным и обозначается ес-

ли й-ь порождается прьшлом с в правой части. 1 'I-

Распознавание принадлежности некоторой цепочки языку Ь(б-), заданному Яй -грамматикой, сводится к проварке принадлежности первого шлеола цепочки какому лиоо правилу комплекса с именем

>1 , последующие символы принадлежат текущему комплексу правил-Преемников, а последний символ контролируемой цепочки - правилу с пустил преемником. Применение правил.сопровождается соответствуй-

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

(з)

где 6 - длина контролируемо» цепочки, С - кино гак га рейлкашги г;л-горитна, учитывающая число команд, затрачиваемое на лрогерк;/ одного символа.

'Мощность класса обнаруживаемых ошбок равна с, тогда как алгебраические и логические методы охватывают только 3, а метода СМ и И -грамматик - 4 класса, имея при этом квадратичную крещенную характеристику, вместо лине>.лоп (3).

Мощнисть построенного чгетачзька определяется слоду»циы утверждением.

Утведаение ¿Л. Класс языков, пиедегавимых в &Ь--граи,аги-ке, совпадает с классом языков типа и по классификации Томского.

-'»етаязык иг носится такке к классу Л -метаязыков Еель-бкцкиго, но отличается от него наличием средств контроля языков с нерегулярными СТ.

Единая с ¡¡ССА графическая ,орул задания Я-грамматики приводит к одинаковости ;орм записи команды работы АМ /соотношение (!)/>' ЯЦ--анализатора /соотношение^}/, на основании чего резрабаты-вается структура -анализатора с ассоциативной организацией.

.'Греты глава посвящена структурно-микропрограммной интерпретации ассоциативных вычислении. Модель А,'л положена в основу обобщённо;! структуры 1ишТ/. ¡1 ее псетро'.шни ииесто горизонтального, как в алгьркткическо»: («'.одели АХ, еспсльзовмлосъ. вертикальное расположение списка ассоциаций, ки;.анд вида С Г). В состав устройства включены также два регистра: один для заполнения признака теку-'-¡цен ассоциации, другой для записи из ¡¡-части'значения ассоциации. Предусмотрена также шина передачи'значения имени ассоциации из И-части в А-часть устройства. • ■

Опираясь на обобщенную структуру АЦ1УУ, разрабатываются структуры автоматов с унитарны« кодированием микрокоманд, состоять:, с'заменой, переменных, с сокращением.избыточности при хранении кедов касок, с функциональным совмещением микропро^ш'мы, с внутренним маскированием зиачен/й <к, -операторов, а также ассоциативно-адресные АМОТ..

Оценка сложности АШ1УУ на олгорипте-скоы агаяе проектирова--Iii;ji получается из следующего определения. ' |

Определенна S.I. Порядок отличенной формулы перехода назыьа-. не:;) шириной & ОСА, а порвдоя сиетеш отмеченных формул - её Euccrcii iv .

Тогда ьерхиди оценка площади % , а вместе с нею и емкостная

си(ч-:алиакр5'вдш функция ССА /еьтом&та/, определяется соотношением'

» I»,- KUXX' cl; ,

4" i

buwrpii.) fi 0истроле;1стнии и ъ затратах оборудования по срав-■цечя» с УУ ¡и 11йУ при числе микрокодом rt,> 150 и числе условий к > [0 получается почти в дьа разы.

U качестве критериев оценки сложности АШУУ на структурном йтане лроактиролшмд »кстунеют тип i/ерехода, реализация перехода а тип !.ШУ. 1кзкболее эфректиши те ШШ из 'числа разработанных, ь которых испопьвуется более, чем один тип адресации микрокоманд, iio oroli нричипз сл они ость реализации последовательности микрокоманд I» ьссоциагивни-адресаих А1;£УУ равна 0, условного' перехода -2. Все остальные А№УУ тлеют худаяе оценки по этому критерию.

и^шмаеиие AUL/}*- ь^ективно

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

- ь качестве аппаратной. поддержки логического и функционачь»«

и ого п1>огрим).;ирс1в£л4и;

- при аппаратной реализации операционных систем;

- при структурной интерпретации языков высокого уровня; .•

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

Чсль'сЦггая глава посвящена разработке раэрядно-параллельньх " ассоциатияшс аряфаетйческих вычислении и структур. При этом обобщенная структура АШУУ ацстунаст в качестве модели разрявдо-гшра-ллелыюго арифметического устро«отьа с табличко-алгоритыическим способом обработки потока чисел с фиксированной запятой. В её А-частл заиоу/лкеласи значения разрядных-срезов /ГС/ и переноса, а в ki-4bcvA - значения цирр результата и переноса. С целью повыше--ьш j чиdлх 1 тгалъiiоii гвОко&ти ycTjolicTBo предлагается использовать •• -не одну, а комплекс систем счисления. Практическое воплощение

эТой идеи связывается о использование!/. концепция ядра комплекса СС: алгоритмического и структурного. Им случит двоичная СС. Комплекс СС пклтает, помимо двоичной, 2-10-л СС к СС остаточнкх классов /СС01</, широко применяема н тактику шшчшцх янчкслокиЯ.

Определение ■!.[. Кортеж А.. двоичных рсзичдоь чисел из множества Р , якеюких один и тот же разгяд!ш1'. вес <0^ ь {¡^ называется разрядным срезом мнакество чисел Р по весу .

Определение 1.2.'Арифметическим лесок разрядного.среза А^ называется суыкэ его единичных элементов: ,

Алгоритм раэрндио-цяраллелъкого N -арного сложения в двоичной СС представляется следующими рекуррентными соотношениями

1' I

' V 0, р0 = 0;

4= Чн^'^о^Ср-.,^ ); _ _

1«л ср-м ♦ я>о/г ^;

» при

где слагаете с номерам от N до N +- К учитывав? э^екг распространения переноса ; (» ) - наименьшее целое, не меньшее, чем (•)•■■

Временны! сложность алгоритма оценивается неравенством И ^ Г^ 4 1 * ¡,пД; 6о<| ^С/У- Г)) где 1г - количество двоичных.разрядив операнда ^ 6 .

¿мкостнач сложность ассоциативного Н -арного сумлатори с естественным кодированием значений оценивается величиной

V = V \/1И ~ /V. ( V Ы- ип.

Уменьшение аппаратурных'-затрат производится зв счет понижения размерности пространств ягачешц! р- и ^посредством:

а/ перехода ¡; ддокчпоцу кздироиам» значения и разбиения значения р^ на основное II ^ и дипэляитульног? Ц , определяемые как

б/ конвейерного распространения. переноса, силжолическое представление одного ¿ага алгоритма сличения в этом случае тлеет вид:

М; х'Ь .а- ,,

о о. « <■ (

где Ц* - булева ыатииа, каждая строка которой соответствует РС; I*, - первая проекция единично»: матрицы; ^ - вектор-столбец размерностью П/ , кахдая компонента которого определяет величину соответствущего РС; - означает операцию поразрядного взвешивания величин ; диагснализированная матрица.

Если Изъявляется диагональной, то ее первая проекция является результатом выполнения операции /V -арного сложения, в против-' иоьд случае осуществляется ев транспонирование и последовательность вычислений повторяется.

Следуя концепции ядра комплекса СС, /V -арное сложение чисел в 2-Ю-й СС, представленных кодом "а-4или в ССОК производится тетрадными или модульным срезами в N -арном двоичном сумматоре с последующим преобразованием двоичного результата в 2-10 код с целью получения цифры результата и определения переноса в следующий тетрадный срез, или приведения результата сложения к аьданному иодулв.

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

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

¿IV Ц - 1

2 = А X в =» •

где 1 = А =(0^,0.^,,.;.,а.,),

причем •

^ __ (I, если I и 1+] = К,

ЧО, если.а^б-= 0 и 1 + 1 ^ К.

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

но-параллелып« умножителей. Она возрастает примерно в N раз при одновременном умножении /V чисел. Разрабатывается алгоритм N -арного умножения и соответствующая ему структура раарлдно-параллелъного конвейерного умножителя. . .

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

Эффективность применения комплекса СС напрямую зависит от эффективности аппаратной реализации преобразований СС.

Утверждение 4.Г. Набор преобразований П =■■ [¿^ ССОК, .2^2-10^ в принятом комплексе систем счисления является достаточным и минимальным.

Таблица преобразования чисел "2-*СС0К" представляется матрицей

К

^Сок."

med Р, ^ vi

где

мое двоичное число - в виде *Чок = [X

lUoil . . nu>d Р^,

'•Чг (4)

-

, ' t = ГТк , , а преобразуй

Ч Ч

(5)"

где X; = marl Р; дх ; .

J d w —1 ■

логда структура преобразовятеля "й--» ССОК" оказывается состоящей из ассоциативной памяти,.содержимое Ji-части которой образует матрица (4) а преобразуемое двоичное число записано л линейке индикаторов, и л/-врного сумматора чисел в ССОК,' необходимость в котором определяется вира-кениек (5). Время преобразования определяется преимущественно временем работы сумматора.

Совершенно аналогично задаётся преобразование" "2~ч~ 2-10", строится структура-преобразователя «.'оценивается время его работы!

Обратное преобразование чисел из. ССОК в позиционную СС зап-' лючается в нахождении- тагшх'коэффициентов Б^ представления иско-

кого числа в сыв'лашюй СС, чтобы *!ц tr • d--, равнялась искомому^ числу, заданному остатнаш 1[ 1 , - 7Для этого строится к 4;азреашетск систег/а модульких уравнений

Чг.^м

i n^-V^Jbip^- i i- P4 с e. ^ P^ í - • • . Jlfiv

где <y = í, + + ... • ПГ"\\- - представление искового аде-

1 ¿ 1 fV <J 1

,na 'э в вычетах.

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

В сравнении с известными структуры разработанных преобразователей в 3,5 раз". /ССОК-^2/ и более, чей в 20 раз /2-^ССОК/ . производительнее при одинаковых аппаратурных затратах.

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

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

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

Рекуррентные записи алгоритмов нелинейных вычислений имеют

инд:

а/ деления

^Y-yC - У' 2 * _ -t и

^КМ ~ ^ к +

где J- - значение делимого, 9 - значеннз делителя, 't частное / - 0/, t - минимальное из чисел /lit tv i 1/,ддя которых выполняется условие у-.f + ru - разрядность опораи— дов;

б/ извлечения квадратного корня

f 1 . nZ(t"<i

I = - ~ i ,

где i - минимальное из чисел, маньднх а- , для которого выполняется условие >> начальные условия: х1 ~ & ,

Ъ, « 0; '

в/ логарирмрованин f =

где t - параметр операции поиска, шиьыее из чисел, для котерн* справедливо либо х^< • ¿'4 ;• начеГонне условия: х -

логарифмируемое число в обратном коде, - это же число в п"нг.ом коде, - ноль в,обратное коде; ■

г/потенцирования , • '

где "t - наименьшее из чисел, меньших гь , для которых выпотаяег-ся условие i Eoij,, }, Х:Г ~ X € (р, i] - приведенное зяачзнне аргумента;

д/ вычисления фунтхкД a.'lct<j Ъ , й.гс г j ■

(. ^¿-н А з ~ \ v Wn ~ ifi, - К j

начальные условия работы: Oi * I - a/ut<j c /,' yjj = Ir^*";

1 , => п/2 /для atcctd Ь /; b'^ 5 , /для ¿исЦ

- 14 -

По скорости вычисления элементарных функций 32-х разрядных аргументов ассоциативные процессоры; разработанные в этой главе, айактиыша линейных а матричных соответственно в 2,5 и 1,25 раза. По аппаратурным затратам - экономичнее матричных в 1,25 раза и уступают линейным цочта в 4 раза.

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

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

Разрабатывается обобщенная структура безадресной памяти, в которой выделяется с^гак управляющей. логики, служащий дня определения подвижной границы межцу занятой и свободной зонами накопителя /Н/. Ни её основе затем раарабативантся структуры памяти с :рекимьш работы "первы'л-иервыГ', "первый-яоследнии" и комбинацией их. . », ■

Функции возбуждения ляшти с двухсторонним доступом /"вагон11/

•имеют вид: . .••■•'

0) А (за 2 *>>

. itи Цч 3 *> л (зп % »' i>i

= I) л (tfTM23l),

где 1)1 0) -. единичное и нулевое состояния I -того

элемента памяти; Ш MpAiL,/, ЧТ М^/г.^/ - сигналы записи, чтения.

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

- 15 -

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

Б базисе Жегалкйна производится синтез структуры ассоциативного операционного элемента /ЛОУ/, внполчяюдьго полннй набор' Функций алгебры логики двух переменных. Булевская интерпретация {у/1-кции возбуждения АОЭ на основе мультиплексора имеет вид:

Ъ = V (х л у л к ¡г,)^ (амЗл. дослал

где % 2 3 4 " компоненты Оулегского вектора управляющих сигналов.

Для'запоминания графических структур данных разрабатывается структура списочного ЗУ, в состав которого входят три адресных регистра и регистр числа. Основное условие его работ» где X - длительность паузи незду импульсами считывания и регенерации, tf, - время переключения блока вентилей.

Разрабатываются алгоритмы .¿армирования различных списочных структур. В сравнений с типовой адресной памятью списочная обладает в среднем вдЕое большим быстродействием.'Ота хорактеристика тедет быть значительно улучшена, особенно, яри поиске требуемого указателя списка, посредством использования структурной организации пашти /иМПУУ, для которой разрабатываются процедур« редг.чтиро-эания графических структур данных..

¿¡ля улучшения врекешмг, характеристик ляроко применяемых на 1рактике. алгоритмов внутренней сортировки информации методами включения и слияния, посредствог,г устранения пересилок Элементов сортируемого массива в буферные зоны паилтк расширяются функциональна. возможности списочного ЗУ зэ счет .выполнения операция ссртп->овкй в нём. Смысл сортировки в этим случае заключается в устано-¡леняя связей между неподвижным элементами сортируемого массива".

Аналитические оценки времени сортировки информации в списке !етодоы включения определяются следующими соотношения/«:

а/ Гцепн * + лриЕ.м^е .

я® '^цепн' Тпосл " ЕРемена сортирован в цепном и последовательном писках; ^р.^р - времена выполнения операций -равнения и обра-екия к ЗУ; размёры элементов сортируемого массива и та-

- 16 -

вариационной части ячейки Н; Ц - число элементов массива;

б/ ¿М- ^ХР с М-Р 4 ^ег СМ * я) , в , р

1 'тел эм ич

В случае а/ выигрыш по времени сортировки составляет 20-25/5 при ¡¿^50, в случае б/ - В0-ЭС$ при £Эм>. 10. Ещё -больший выигрыш доётся алгоритмом слияния предварительно упорядоченных массивов. Строится экспериментальная характеристика Т где 1а-числс разбиений исходного массива на части, из которой следует, что Т—1-иш при 1>г, = 8-16,

Корреляционная, обработка строк /массивов/, сш.шолов связывается с вычислением значений функций сходства В зависимости от способа их вычисления разрабатываются два класса ассоциативных процессоров, названных в работе соответственно постоянными •; ассоциативными 37 /ПАЗУ/ и ассоциативными динамическими процессорам /АДП/.

Команда работы ПАЗУ аналогична команде работы АМ, определяемой соотношением /I/..Конъюнктивная функция(Д^) имеет вид;

Ну 3

Р ) « тАГ >Сд, (У;),

№ -•А' если Чг '

-^"ЗС^ИР ~ 1.0, в противном случае. (б)

Производится микро- и ыакроструктурний синтез ПАЗУ. Формально его работа представляется правилами работы инициал-нога автомата , в смысле Хомского. Особенностью работы ПАЗУ является независимость её от направления сканирования матрица АОЭ. В случае выдачи многозначного ответа ь процессе определения степени корреляции строк символов работа ПАЗУ может быть продолжена посредством обратного сканирования А-чести устройства, что соответствует, например, просмотру эталонного дерева описаний строк.в направлении от листьев к корню. Такая реализация процедуры вычисления вечичины корреляции строк символов во многом напоминает идею синтаксического двухстороннего анализа цепочек символов алгоритмического языка, предложенную Юшенко Е.Л..'

Структурная организация АД11 опирается на идею моделирования значения величиной Т временной задеркки. распространения

сигнала в однородной вычислительной, среде. Величина

где единичная задержка (зе,^ ч^) определяется соотношением ("б) и запоминается в максимизаторе, предназначенном для вычисления экстремальных значении • Разрабатывается два варианта его структурной организации. В первом максимизатор представляет собой схему, выделения первого импульса /". оракула"/, поступавшего из однородной вычислительной среды, во.втором его структура строится, исходя из необходимости выполнения ыаксиминных операций, и состоит из счётчиков, в которых запоминаются значения (X;,) .

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

А = Кг2° ^ К2-21 + К^'Л2 + ,...+ 1,

в котором К;,- двоичное значение множимого, г""1 - двоично взвешенная единичная-компонента множителя; К^ = Ю, =» . . . = К^. Устранив ограничение равенства коэффициентов- К между собой и видя в них .значения РС складываемых чисел или значения арифметических . весов.РС, приходим к структуре Ы -арного сумматора на основе матричного умножителя с внутренней памятью регистрового или счётчикового типа.

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

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

а/ определение соответствия типа "1-0": ..

ОЙь-о 3 М1 А Щ • ^ = ^ [%]1-0 - V-'.!д4]1-о •

где все элементы матрицы М^ /или Щ/. равны прямому /или инверсному/значению I -того столбца /или строки/ матрицы М| /или Г^/; ' б/ определение соответствия типа "0-1":

Й0-1 = ( в/ определение результирующей матрицы: . .

М- ЫюИ^0-1;

г/ определение искомой матрицы соответствия: Мд ? [Из^Л^д]. ««•[Ид)! - матричное задание константы "I".

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

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

Для повыыенин достоверности'корреляционной обработки строк и массивов символов при использовании простых в вычислительном отношении решающих правил /ГО/ в работе ставится задача объединения в коллектив. Разрабатывается алгоритм взвешенного голосования с априорно известными весами РП..Выводятся соотношения для коллектива из трёх РП

«ли+

если О^РаРз/^-^р^р^

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

; Б разработанном алгоритме принятия решений не требуется определять области компетентности РП,/которые непросто однозначно определить/ как это имеет место в коллективе РП Растригина-Эренште-' Ёна, основоположников этого направления в методах принятия рейхе-

- хэ -

ний.

Седылця глава посвящена разработке наиболее часто встречающихся на практике таких крупноблочных ассоциативных вычислений и структур, как вычисление свёрток, взаиыш-коррелнционных функций /ВКФ/, сложных арифметических выражений, прямых и обратных преобразований Уолж», обработка размытых графических структур данных," управления подвижными объектами, построение машин с накоплением опыта решения задач.

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

Т = 2«, - IV

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

Вычисление ВКФ выполняется по формуле:-VI

к(0- 1/Тв (7)

где X - 0,Тв-1, Ь = ОИ^ГХ, Тв - обьём выборки входных сигналов, ~ число значений ВКФ. Величина (т.Л«.'гп3) постоянна и не влияет на положение максимума функции К<и) . Следуя выражению (7), основу-структуры коррелятора составляют такие множительно-сумми-рующив устройства разрядно-параллельного типа. Она удовлетворяет всем требованиям СБИС-технологии: обратные связи имеют локальный характер, минимальное число шин для входных,, выходных и управляющих сигналов, однородность структуры.

! В лучшем из известных алгоритме Винограда вычисления сложных арифметических выражений по обобщённой схеме Горнера получена логарифмическая зависимость времени от числа скобок в выражении. Применение разрядно-параллельннх' Ы -арных. умножителей и сумматоров делает эту характеристику постоянной и равной суше длительностей одной операции /V -арного умножения и л/ -арного сложения Структура процессора мало чем'отличается от предыдущей. .

Разрядно-параллельное вычисление коэффициентов Р разлояе-

- ио -

нил произвольного цифрового сигнала 1, определённого на интервале /V , е ряд лнгегрылыцчХ' рушсцип Уолша опирается на формулу

Г - (

* где Н^ - иатркца функций ЗЧшш, 0, - тешшцева всрхиетреуголь-ноя матрица, и производите}! в два этапа. На первом вычисляется вектор

в котором

У,(1) с к и)

х\г) +

т

X Сл/"0 + X (/V) »• К (А/--1) + *

Х(Л'-А) + Х(^) X О)

н«' и .

(8)

на втором - значения вектора

Порядок расположения компонент Х(,о)в (В.* таков, что вычисления организуются по конвейркой схеме внутри -того РС отсчётов сигнала, г.олучая на каждом шаге РС вектора (-С . разрядно-парал-лельный процессор,'реализующий указанные действгл состоит из ди-яайжческой иамяти счйтчккового типа, регистра, преобразователя прямого кода ?С в обратный,•паьята для хранения матрицы коэффициентов Уолша, суклнрукщего нолч и динамической паштЕ для запогань ния значений коэффициентов спектрального разложения сигнала по функциям Уолша. Время работы процессора оценивается затратами на формирование и обработку одного БС отсчетов сигнала.

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

"и. Со) -- 1А.СО

х «я" ^

ьи(У-2)- и,(лМ)

^ СС (А/ )

с учётом того, что и. «

Е; разработке размытых графических структур данных выделяются три атаса: устранение неопределённости исходного представления, определение структурных свойств, идентификация. Их рассмотрение.

„ - 21 -г ,

производится на примере обработки графических изображений /ИЗБ/.

Разрабатываются параллельно-коньейериие алгоритм» в булевском операционном базисе фильтрации контурных и фоновых искажении, устранения пустот и разрывов внутри штрихов линий, шделсшм контуров, угояьшонкя методом последовательного вычитания контуром, преобразования многогродационных графических ИЗБ в бинарные. Алгоритм утоньиепия штрихов линий имеет вид: а/ выделение контурны;: точг-к,' приводящих, к нарушению связности ИЗБ в процессе утольшеяия

[х,ы;х]* CLtxivutx]), [x2i= [хзл ед/cxj vwui), [Х43- tX3^(«.<WCx]v LCWÍXJ»,

• ГХцЬ ГX] H(wi'x']»,

СХЧ- СХа.1 ^ CK^l;

б/ исключение их из контурных

' (УЫХ1л [X1].; .

в/ устранение эффекта' двойственности линий утоньшенного ИЗБ:

[хиш* ЦГ^а7х1~77Щ) ' или. си i a [Tu а ,'

где [х] - фрагмент дискретизиропаннога ИЗБ, L! R., /V, W -операции сдвига влево, вправо, вверх и вниз. Работа алгоритма завершается-при условии- [X1! = ü. Его нрешшая сложность определяется величиной .

. Т - vr„a.x]'4/¿ [ t

Míe tbj - толщина j -той линии КЬБ. 1

Разностно-итерационний алгоритм кусочно-линейной структур»-¡ации графических ЙЗь представляется функциональной схемой машины : магазинными паглятяа: с ассоциативным доступом к ним /МП-машина/» 5абота алгоритма заключается в выполнении трёх основных действий,! I. Вычисление элементарного ориентированного отрезка прямой

дз —». 4 - означает поворот dyneнекого доктора на 180°, исходя на-, принятого условия симметричности графа ПЖ, реализуемый операцией

О'Ч —

— «¿о —

сдвига на четыре разряда двоичного кода .

?,. Получение разности векторов Хс, и сЦх^о^; х-

4 = Л

х- » х; А

3. Запись в требуемом строчной разверткой ИЗБ порядке промежуточных результатов операции I в магазины МИ-машинк. Число мага- • зинов равно числу штрихоъ линии ИЗБ. Информационная связь между магазинами организована через ассоциативную память, в'которой запоминаются номера вершин ИЗБ в процессе.его структуризации.

Временная сложность построенной МП-машины является линейной. зависимостью от числа точек ИЗБ, аппаратурная - линейно зависит от числа линий ИЗБ. Этим разработанный алгоритм выгодно отличается от изьестьшх, использующих преимущественно следящую развёртку. ИЗБ.

Улучшение качества структурированного ИЗБ и уменьшение затрат на его хранение достигается посредством разработки параллельного алгоритма аппроксимации кусочно-линейного представления ИЗБ, математическую основу которого определяет известная из векторного исчисления теорема Шаля. Геометрический стасл алгоритма следующий.

1. Прямоугольная системе координат ХОУ помещается в начало Первого вектора Ъц суммы, а направление оси абсцисс совмещается с его направлением.

2. Задаются значения порога ^ аппроксимации и операции параллельного переноса и поворота системы ХОУ,.выполняемые, если

|г,Р0У ^ (9)

3. Некоторые сумли векторов-слагаемых заменяются одним век-, тором, если, (9^'меньше или равно Л . Иначе вычисляются координаты начала того вектора-слагаемого,' для которого выполняется услс-рие/ТЭ},-' Б эту точку переносится начало системы ХОУ и последовательность действий повторяется, пока не будут просмотрены все векторы-слагаемые, запоминаете в к ¿газике Щ-шикнн. ' •

Разработанный алгоритм выгодно отдичаегся от гистерезисного тем, что качество аппроксимация линий не зависит от их наклона, обработке подвергается структурное описание ИЗБ,. благодаря чему - ; двумерное. преобразование "аппроксимация" заменяется рядом одномер-

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

Решение задачи управления подвижным объектом расчленяется на две последовательно связанные меяду codait, - определение вели-чини отклонения' объекта от заданного курса и вывод его на' курс по оптимальной траектории. Вторая из перечисленных задач решается посредством разработки табличного алгоритма управления, опирающегося на логико-лингвистическую модель управления и на разработанные структуры АДП для 'обработки размытых строк симеолоб.

В обще** плане построение табличного алгоритма управления заключается в разбиения пространства ситуации S на nv эквивалентных по управлении классов. Каждому классу ситуаций ставится в соответствие некоторая логическая переменная Т^ /например, самый мальм ход, малый, средний и т.д./ и за нею закрепляется соответствующее управляющее воздействие на объект управления. Множество 'I подмножеств логических переменных и соответствующих им упрввле-ний образуют эталонную ин формацию, _представляемую таблицами принятая решений. На множестве пар (fv, ) текущих и эталонных ситуаций определяется мера сходства p^r^S^) . » зависимости от значения которой осуществляется отнесение текущей ситуации к одной из эталонных. Решающее правило имеет вид:

>с <Ц.К, , гплх ,пих пшх "<*)},

I'imh логической переменной, наиболее близкой к эталонной ситуации, для которой заранее определены управляющие воздействия, определяются по формуле

Tj f>ta.x jvc^y (St).

е-

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

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

блгаайишго меньшего по значении, максимального и совпадающего элемента. '

Построение структур ЭШ с накоплением опыта решения задач саяэыааетсч о проблематикой синтеза алгоритма по формализованному описании задачи. Это описание образует модель предметной среды и служит источником накопления опыта. Отмечается, что рассматриваемая проблема,не имеет общего решивши Поэтому построение процессора с накоплением опт- .решения задач осуществляется на примере синтеза алгоритма анализа связности графического 113Б. Смысл решения поставленной задачи заключается в том, что но заданным струи-, туре и начальной конфигурации И1-маашни, модели графического ИЗБ • и целевым функциям автоматически строится функция переходов и вы-' ходов машины. Эта задача решается методом ветвей и границ с использованием стратегии полного перебора возможных действий машины в незнакомой для неё ситуации. Разрабатывается обобщённая структура малины с накоплением опита решения задач,' приводятся форма- . ты команд её работы. . -

В приложении приводятся доказательства теорем трансляции ССА, сводная таблица оценок эффективности разработанных ЛВС,-соображении по их (фактической реализации на 1Ш! и ПЗУ, методика проектирования раэрядпо-параллельных процессоров на одном типе БИС-АЗУ, рабитащкх в комплексе СС, результаты обработки некоторых ' размытых графических структур доииих, интервалы по внедрении.результатов диссертации подкрепленные соответствующими актами

Обработка размытых графических'структур данных рассматривается с позиция лоаьиешю уровня интеллекта ОЗМ. Структура ЭЬЙ Представляется состоящей из-двух основных компонент: устройств взаимодействия с внеаней средой и вычислитель-, в соответствия с чцм "'интеллектуализацию" Э31Й предлагается проводить в двух направлениях, одним из ксторцх латается построение интеллектуальных графических читающих терминалов.

I Определение ПЛ. Устройства, ирелиишшче^гив для оьтоштичес-г кого восприятия графических ¡"Ж, способные преодолевать избыточность и разнообразие их представления и внлолшивщие функции интерфейса мекду человеком и ЭШ, цдзыкимся кнтеляектуальнл'Д графическими читающими терминалами /Й1ЧТ/.

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

(хизация программирования, построение 'аршч-лглшх анализаторов интеллектуальных роботов, системы обраоогки ИЗБ. | Определение П.2. Набор Функциональных и управляющих програкц, .инструментальную и информационную среду и связи _мекцу ними называются реализационной структурой ИГЧТ.

Она является конкретизации;! понятия машины Глуикоьа.

Функциональные программы шшмшодт действия, предписываемы» алгоритмами ввода, предварительной обработки, структурного анализа, классификации символьных и идеити^икицчл графических 1'ос. построение опиралось на разработанную в главе 2 технику ассоциативного микропрограммирования, согласно которой шшши программный' модуль представлялся програы.ашм сссоциативнш процессором. Его А-часть соответствовала предикатной, о И-часть - исполнительной компонентам обработки ИЗБ.

Организация взаимодействия управляющих программ с фуякцпона-' ЛЫНШ1 татке опиралось на технику ассоциативного микропрограммирования. Программный процессор управления представлен. кои.'ьозлци-ЬЛ А- и И-частеИ АЬШУУ, Его входом являлись значения вектора зада-нин'работ,,параметры, передаваемые'из связанных с ним функциои&яь-рнх модулей, и управляющие данные. Рассматривались два способа, программной реализации процессора - ассоциатигно-алрзсноЛ органи-, рации-размещения и поиска'управляющей информации, последователь-Мая инициализация функциональных модулей,с использованием механизм на работы ПАЗУ. . При построении управляющих программ применялись также жесткое и гибкое закрепление за ними функциональных'модулей и виртуальная организация памяти.

Список литературы содержит' 342 наименования.

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

- ассоциативно-ориентированный способ представления ангорат-мов: '

'- алгоритмическая модель ассоциативной машины:

- ассоциативно-ориентированный способ контроля корректности параллельных микропрограмм;

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

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

- ассоциативно-ориентированный способ ускорения разностно-итерацнонных вычислений элементарных пункций:

- способ построения структур магазинных к ассоциативных УУ для хранения'графических структур данных:

' - способ ускорения операции сирти] оьки 'истодами включения и слияния:'

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

- методика обработки рнзшткх графических структур данных:

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

Практическую значимость работы.определяют:

- элементы технологии параллельного ассоциативного микропрограммирования: -•■

- структуры ассоциативных микропрограммных устройств управления:

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

- структуры ассоциативных процессоров вычисления эчементар-ннх функций:

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

- структуры ассоциативных сроцессоров корреляционной обработки строк и массивов символов: ■

- алгоритмы списочной сортировки информации методами включения к слияния: • .

- параллельно-конвейерные алгоритмы обработки размытых графических структур данных: '.•''.

- структуры ассоциативных процессоров крупноблочной арифметико-логической обработки информации:

- методика построения интеллектуальных графических читающих ¡терминалов. .

Внедрение результатов. Результаты проведённых исследований нашли практическое применение.£ следущях разработках, выполнен-. '

, - '¿Ч -

ных под научным руководством и при участии автора в соответствии с тематическими планами работ кафедры Вычислительной техники ЛЭТИ им. В.И.Ульянова (Ленина):

- алгоритмы и устройства автоматического ввода и дешифрации графической информации, содержащейся а изображениях конструктор- . ско-технолсгйческой документации .для производства РЭА /разработка выполнена по заданию ПО "Электронмаш", г.Киев, в 1976-1982 гг./:

- структуры микропрограммных-устройств управления, разрядно-параллельных процессоров обработки числовой и символьной информации на основе ассоциативной памяти в интегральном исполнении для систем внутриобъектной связи /разработка внполенна по заданию НПО "Волна", г.Москва, в 1Э85-Г38? гг./:

- интеллектуальный графический читающий терминал на базе ЭВМ ,"3лектроника-60". и алгоритмы разрядно-параллельных арифметических вычислений и ускоренного вычисления элементарных функций /разработка -выполнена по заданию ВШ1Ш, г.Ленинград, в 197G-I978 гг./:

- ассоциативный процессор изображений /разработка выполнена по заданию НПО "Красная Заря, г.Ленинград, в I976-IS78 гг./:

■ - структура-специализированного ассоциативного процессора для ввода, первично обработки и отображения радиолокационной информации в реальном масштабе времени /разработка выполнена по заданию .C3F11, г.Ленинград, в 1906-1309 гг./.

Во всех указанных разработках применены новые технические решения, защищенные авторскими свидетельствами СССР. Пнтеллектуа™-льный графический'читающий терминал на'базе ЭВМ "Электроника-СО" экспонировался на двух международных выставках, отмечен благодарностями, а на ВДНХ он удостоин серебряной медали. Аосоциативный процессор изображений отмечен дипломом второй степени НТО РЗС им. A.C. Попова.

Подтверждённый актами годовой экономический эффект от внедре--ния результатов работы составляет I 3tfI-,7 тыс.руб. ■

Апробация работы. В период с 1971 по I9tJ8 гг. основные научные положения и результаты диссертации докладывались и обсуждались на 24-х Всесоюзных научно-технических конференциях.

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

ПУБЛИКАЦКИ АВТОРА ПО ТИЛЕ ДИССЕРТАЦИИ

:t. Контроль информации в системах автоглатизации проектирования/ Л.Н. Афанасьев, A.A. Гукавкн, О.Г. Кокаев и др.- Саратов: СГУ, 1985,- 13£ с. . ■ •

2. Ассоциативное микропрограммирование/ О.Г. Кокаев, А.Н. Афанасьев, A.A. Гукавин - Саратов: СГУ, 1989.- 138 с.

3. Процессоры'обработки нечёткой информации/ Соснин П.И,, О.Г. Кокаев, А.Н. Афанасьев- Саратов: СГ/, 1388.- 136 с.

4.-Казак А.Ф., Кокаев О.Г., Петров Г.А. микропрограммные системы ЭВМ.- ЛЭТИ, л.; 1979,- 100 с. -

5. Казак А.Ф., Кокаев О.Г,, Папков В.Й., Степашин Г.И., '!>&-дин А.Л. Диалоговые системы обучения,- ЛЭТИ, Л., 1982.- 64 с.

6. Параллельное выполнение логических операций в ассоциативных вычислительных структурах// Кислекко B.C., Кокаев О.Г., Амехо-Д, ; ЛЭТИ - Л., 1986.- 1С-е.: ил.- Библиогр.4 назв.- Рус.- Дел.ь ШШТй от 23.С4.86, № 2975-1186.

V. газрядко-параллельные арифметические устройства// Кокаев О.Г.j ЛЭ'ГЙ - Л., 1989.- 47'е.: ил. 19,- Библиогр.32 назв.- Рус.-деп.в шд;та от хэ.об.цэ, п шэ~в аэ.

Ь. Аыехо Д., Кокаев О.Г.Ккслекко B.C. Алгебраический подход к синтезу ассоциативных вычислительных структур// Архитектура схемотехника и математическое обеспечение микропроцессорных систем управления: Меявуз.сб.- М.: ШЭй, I986.-.C.I09-II7, . . '

9. Балаьов S.D., Кокаев О.Г. Запоминающие устройства со списочной организацией хранения информации.- Е кн.Запоминающие устройства. Вып. 4. Под ед.Л.П. Крэйзмера.-Л.:-Энергия, 1974.- С.5-13. .

10. Кокаев О.Г., Гужавин A.A., Афанасьев А.Н. Преобразований и реализация алгоритмов управления в ассоциативных вычислительных структурах// Архитектура, схемотехника я математическое обеспечение-ЭЖ: ¡¿еавуэ.сб.- Ы,: JtöföT,' 1983.- С. 5-15.

11. Балашов S.U., Кокаев О.Г., Петров Г.А., Пузанков Д.В., Смагин A.A. Операционные устройства к процессоры с табличным методом обработки информации.- УСИМ, St 5,. 1975.-'С. 16-21,12. Балашов Б.П.Кокаев О,Г., Чиркова А.П. Сортировка информации з ЗУ со списочной организацией// АСУ,- Bun.2, Л., ЛГУ, I9Vb-- С. 67-73.

' 13. Барааюнков В.В., Кокаоэ О'.Г., 'ftipncûB Б.Г., Тешрхаиов Т.Э. Способ ускорения арифметических вычислений // Известия вузов. Приборостроение, 1203.- Т.¡¿6.- 1« 9.- С.26-30.

14. Груман Л.П., Конаев O.P., Попов Л.П. Малогабаритное запоминающее устройство// Приборы и системы управления, № 7.- К.: 19 69.- С.27-31.,

15. Кокаев O.P., Казак А.Ф. Преобразование алгоритмов к виду, удобному для аппаратной реализации в A Li/// Технология программирования.- К.: 1978,- С.33-42^

.16. Кокаев O.P. Эффективно-вычислимые процедуры анализа и распознавания графических изображений// Вычислительная техника. ' Ьып.7.- Л. : ЛГУ, Г/73.- C.44-5Û.

17. Кокаев O.P. Структуры внутренней памяти синтаксических анализаторов// Операционные системы и технология программирования К.: ИК АН УССР, ^970.~ С.52-59. .

10.^Кокаев С.Р., Темирханов Т.Э. Ассоциативные ЗУ и попроси аппаратной реализации математического обеспечения.- В кн.: Запоми-шыщие устройства. Вып.5. Под ред.Л.П.Крайзмера,- Л.: Энергия, [9SO'.- С.64-78.

19. Кокаев О.Г., Тойбпна М.И. Теоретико-множественный подход : определении процедур выделения скелета и контура изображения// ¡звестия JD'W: сб.научи.тр./ ЛУЖ- Л.,1979,- Бип.253. С.8-13.

20. Кокаев O.P., Кудряшв Б.И., Магомедов И.А. Применение теории нечётких множеств к задачам управления нестационарными процессами// ¡/.етоды и смете;,:ы принятия решений. Информационное и алгоритмическое обеспечение прилития решений.- Рига, 1304,- С.60-65.

21. Кокаев O.P., Писанов М.Б. Некоторые вопросы проектирова-:ия постоянных ассоциативных ЗУ// Вычислительная техника. Вып. 7,:.; ЛГУ, 19V«.- С. 49-55.

22. Кокаев О.Г., Смолов Б.Б., Темирхаков Т.Э. Зффектиьно-ди-пюстяруемые ассоциативные вычислительные структуры// Методы и рограммы решения оптимизационных задач на графах и сетях.- Ново-ибирск, 1902.- C.I80-I93. • .

23. Кокаев'О.Г, Интеллектуальные графические читающие терми-алы// Проектирование, контроль и диагностика микропроцессорных истем: ¡«ежвуз.сб,- Саратов: CI7, 1983.- С.14-18.

24. Кокаев O.P., Кислешсо B.C., Амехо Д. Специализированный множитель д/ операндов// Известия ЛЗТ'й; Сб.иаучн.тр./ЛЭТИ,- Л,,

1938.- Dun.334: структура и математическое обеспечение специализированных комплексов.' С.3-7. '

2Ь. Кокаев О.Г., Керцер С.Л., ToilfUiim U.U. К вопросу об алгоритмах п±иннтия pOuieKJii; колпёктявсм решамгцих правил// Известия ЛЭТИ: Cd.ноучн.тр./ JTJTli.- Л., I3UI.- Вып.221. С.53-63.

26. Кокаев О.Г., Тарасов Ь.Г. Быстрое выполнение арифметических операций в ассоциативных процессорах// Вычислителыше гроцес— сы и структуры. Вып.154. • Л.: ЯКАЛ, 1963.- СЛ.28-132.

27. Грелл i., Кокаев О.Г., Яковлев A.B. Фрагменты, теории и применение регуллрмэовашшх /ассоциативных/ схем алгоритмов// Известия ЖГИ: CÖ.научи.тр./ЛУТК.-Л..19.Ю.- Вып.27В. С. ¿14-92.

20. Барншенков B.'fl,, Гршвкн A.A., Кокаев О.Г. Контроль синтаксической корректности операторных схем алгоритмов// Вычислительная технике. Выи.б.-Л.: ЛГУ, 1077.-С.64-71.

29. Кокаеь О.Г., Яковлев A.B., Лтанасов А.Д. Структуры ассоциативных устройств клосси ;i;K<'ii;i;n /изображений/// Дискретные системы обработки информации,- Ияеаск, 1979.- C.5I-56.

30. Ассоциативные вычислительные устройства// Кисленко B.C., Кокаев О.Г., Исмаилсв Щ.-М.А., Петухова Н.В.; ЛЭТИ.- Л., 1987,13 е.:ил,- Бв0лиогр.2 назв.- Рус.- Деп.э ВИ!51ТИ от Ü.09.Ö7, i? 65 75- Е87.

31. Кокаев О.Г., Стеыпень Э. Автоматный подход-и проектированию ycTpoLcTB, ориентированных на выполнение аналитических преобразовании// Известия ЛШ: Сб.ка;,чн.тр./ЛЭТР,.- Л., IS79.- шя.262. С.39-13. •

32. Кокаев О.Г., Ьксанов У.В., Балашов Е.11. Проектирование устройств автоматического ввода письменных знаков в ш^ормециои-ные п вычислительные систе;л1 на основе гшогофуккцнокальнцх ЗУ со списочной организацией хранения кЦоркшки// АСУ. Бкп.З,- Л.: ЛГУ, 1976.- С.61-70.

83, Балаыов Е.П., Смолов В.Б., Кокаев О.Г., Смагш; A.A., Уланов В.Н. К вопросу применения с о краденных таблиц функций д.т.-i построения высокопроизводительных однородных процессоров.-.УС'.',;,!, К.: ВШ1.3, 1975.- С.41-45. ,

34. Кокаев О.Г. Некоторые вопросы построения зкакомичаых читающих автема-юв ekcokoü производительности// Известия ЛЗТг*: Сб. ,Нвучи.тр,/Л5ТИ.- Л., ID73.- Ьып.121. .С.7-15.

35. Афанасьев А.'Л., Кокаев О.Г. , Панов О.В. метод предельной

структуризации программ для микропроцессор»!« систем// Микропроцессорные системы.- Челябинск, ЧПЙ, 1934,- С,58-61'.

3G. Кокаев О.Г. Об одном подходе к построеншо окономичннх универсальных читающих автоматов для автоматизированных систем управления// АСУ. Вып.2.- Л.: ЛГУ, 1975.- С.37-42.

37. A.c. 429467 /СССР/. Ма'газнкное запоминающее устройство/ О.Г.Кокаев и др./СССР/ - Опубл.в БИ А 19,. 1974.

ЗУ. A.c. 947'ЯI /СССР/. Одноразрядное стековое запоминающее устройство/ О.Г. Кокаев и др./СССР./- Опубл. в БИ № 28, 1932.

39. А.С.Л049Э75 /СССР/.' Постоянное ассоциативное запоминающее устройство/ О.Г. Кокаев и др./СССР/- Опубл.в БИ ii 39, ШЗ.

40. Л.о. 705521 /СССР/. Постоянное запоминающее устройство/ О.Г. Кокаев и др./СССР/- Опубл.в БИ .47, 1979.

41. A.c. I233IÜ4 /СССР/. Ассоциативное суммирующее устройство N (г -разрядных д: оичных и двоично-десятичных чисел/ О.Г. Кокаев и др./СССР/- Опубл.в БИ МЭ, 1986.

42. A.c. 1043650 /СССР/. Микропрограммное устройство управления/ О.Г.Кокаев и др./СССР/- Опубл.в БК № 35, 1983. ■

43. A.c. 951307 /СССР/. Микропрограммное устройство управления/ О.Г. Кокаев и др../СССР/- Опубл.в БИ Ä.30, 1982,

44. A.c. I164706 /СССР/. Микропрограммное устройство управления/ О.Г. Кокаев и др./СССР/- Опубл.в БИ1& 24, £985.

45. A.c. 752484 /СССР/. Запоминающее 'устройство параллельного типа/ О.Г.Кокаев и др./СССР/- Опубл.в БИ JS 28, 1980.

46.. A.c. II37479 /СССР/. Устройство преобразования по функциям Уолша/ О.Г.Кокаев и др./СССР/- Опубл.в БИ » 4, 1985. :

47. A.c. 1249546 /СССР/. Устройство для воспроизведения запаздывающих функций/ О.Г.Кокаев и др./СССР/- Опубл.в БИ № 29, I93G.

48. A.c. d07299 /СССР/. Устройство для синтаксического контроля программ/ О.Г. Кокаев и др./СССР/- Опубл.в БИ й-7, 1931.

49. A.c. П04527 /СССР/. Устройство для ортогонального преобразования по Уолшу/ О.Г.Кокаев и др./СССР/- Опубл.в БИ Ji 27, ' 1934. •

50. A.c. 957272 /СССР/. Многоканальное запоминающее устройство/' О.Г. Кокаев и др./СССР/- Опубл.в БИ № 33, IS82.

51. A.C. 1062689 /СССР/..Суммирующее устройство/ 07Г.Кокаев И др./СССР/- Спубл.в БИ Й 47, 1983. .

52. A.c. I267625 /СССР/. Устройство преобразования чисел из

- 32 » -

систем« счисления остаточных классов в позициошыУ код/ О.Г. Кока-1 ев и др./СССР/- Опубл.в Ы1 № 40, 1966.

63. л. с. 73ЛШ /СССР/. Мллропрограданое устройство управления/ О.Г.Кокаев и др./СССР/- Опубл.в БИ Л> 17, I9Ö0.

54. A.c. V23ü?2 /СССР/. Дй:кроирогражние устройство управления/ и. Г, Кока ев и др./СССР/-Опубл.в ЬИ ». II., i960.

55. A.c. 537310 /СССР/, ыикрипрограьашое устройство.управления/ О.Г.Кокаев .и Др./СССГ/- Опубл. в W № 44, 1976.

■ 56. A.c. 1253975 /СССР/. Формирователь кодов радйалыю-кру-говой разЕёртки для индикатора кругового ооаора/ О.Г.Кокаев и др. /СССР/- Опубл.в ЬИ К- 33, 1386.

57. A.c. 1262372 /СССР/. Стеково-ассоциативиое запоминающее устройство/ О.Г.Кокаев и дг./СССР/~ Опубл.в БИ » 37, 1986.

5ö. A.c. 1247926 /СССР/. Запоминающее устройство/ О.Г.Кокеев и др./СССР/- Опубл.з ЬИ й 23, I9uG. '.

59. A.c. 1304078 /СССР/. Стековое запоминающее устройство/' О.Г.Кокаев и др./СССР/-.Опубл.в БИ № [4, 1.987.

СО. A.c. 1353Ш? /СССР/. Ассоциативное арифметическое устройство/ О.Г,Кокаев й др./СССГ/- Опубл.в БИ » 48, 1937.

61. А с. 13Ш7В /СССР/. Запоминающее устройство/ О.Г.Кокнев и др./СССГ/- Опубл.в БИ Д 23, .1937. . ' "" .;'

62. A.c." 13Э6133 /СССР/. Суммирующее устройство/ О.Г.Кокаев и др./СССР/- Опубл.в БИ Л 10, 1Э60.

63. A.c. 1444752 /СССР/. Суммирующее устройство/ О.Г.Кокаев и др./СССР/- Опубл.ь БИ Л 46, 1933. .

04. Афанасьев. А.И., Кокаев О.Г., ¡»'дтраранов Н.Б. Программа контроля языков параллельных схем алгоритмов.- i«.: Гос ФАП, № ¡<! 8G0B6 orI6.I0.6G. 59 с. ' : . . ,

65. Ймакутдииов АЛ., Кокаев-О.Г., Яковлев A.B. Программный комплекс: Анализ и первичное описание графических из'обракений.-М.: Ш АСУ, вып.З, № 7319.- IL, 1932.

; 66. -Имаыутди.чов И.*., Кокйев О.Г. Комплекс программ: Сэкагке структурнач описаний графических: изображений,- М.: МосФАП, 1903, ВЫП.I, I« 7353; ' -

67. G-seEe F., Konaev 0-G-., TemiicJvüaüv Т.Е. TkeozitibtU

'cles Aaj„£<iu,ei a$$c.b£a.i;u'Cz. halten, stг^кЬиле^Ц ■ . teeKtio^31 (iS.gi), Hejt 6, s.ÄJ't-m