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

рг Б о А

Государственный комитет Российской Федерации 1 б иНВ ^Ь'З по высшему образованию

САНКТ-ПЕТЕРБЛТСКШ! ГОСУДАРСТВЕННШ ТЕХНИЧЕСКИМ УНИВЕРСИТЕТ

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

РАИХЛИН Вадим Абрамович

СХЕМОТЕХНИЧЕСКИЕ МОДЕЛИ ИТЕРАТИВНЫХ СИСТЕМ

-Г ^

Специальное^ 0;#?3.13 - вычислительные малины,

-зэ системы, комплексы и сети

л* (®?13.05 - элементы и устройства Со вычислительной техники ж

систем управления

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

Санкт-Петербург - 1994

Работа выполнена в Казанском Государственном техническом университете им. А.Н.Туполева.

Официальные оппоненты: доктор технических наук,

профессор ЛЕВИН В.И.

доктор технических наук, профессор МЕЛЕХИН В.Ф.

доктор технических наук, главный научный сотрудник ПОГРЕБШСКШ С.Б.

Ведущая организация: НИИ КВАНТ.

Задага состоится 3.3 <ре&ра.ля. 1995 г. в_ часов

на заседании специализированного совета Д 063.38.04 при Санкт-Петербургском Государственном техническом университете по адресу: 195251 С.-Петербург, ул.Политехническая, 29.

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского Государственного технического университета.

Автореферат разослан <2.3 с^ена ¿ГрА 1994 г.

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

//

дурАцдда к.п.

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

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

Актуальность теш.Вопросам теории и практики итеративных систем обработки информации, в их взаимосвязи с однородными структурами, уделяется неизменное внимание во всем мире, .начиная с 60-х годов (Глушков В.М., Евреинов Э.В., Балаховский И.О., Грегори Дж., Унгер С., Слотник Д., Холланд Дж. и др.). •Определяющим моментом в данном случае является топологическая повторяемость модулей и регулярность связей мезду ниш.

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

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

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

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

Работа выполнена в соответствии с Комплексной программой НТП СЭВ (проблема 1.1.9, задание 1.6), Программой 0.80.01 ГКНТ СССР, Приказом руководителя организации п/я М-5804 от 23.04.85 223, . Постановлением СМ СССР от 16.06.87 Л 675-155,Приказом Минвуз СССР от 30.07.87 21, Приказом Минвуз РСФСР от 03.09.87 й 122, Планами работ по научно-исследовательским темам Казанского авиационного института им.А.Н.Туполева (номера госрегистрации 76047362, 77049512, 78076196, 81023621, 81103626, 01820081341, 01840036264, 01850074085, 01860070322).

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

Модели задержки строятся как однородные искусственные линии. Модели последовательностных алфавитных операторов - во введенном .в работе классе псевдоасинхронных последовательностных схем. Реализация операторов над массивами данных проводится в базисе операционных логико-запоминавдих сред (У.Х.Каутц) как морфологической основы процессора массивов. Организация работ с базами данных рассматривается в классе функционально полных машин баз данных (Л.А.Калиниченко) распределенной архитектуры.

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

ных звеньев третьего порядка (Я.С.Ицхоки, Э.М.Манукян, С.И.Евтя-нов и др.) либо на построение неоднородных линий (В.Е.Томсон, Д.Н.Матханов, Е.С.Кух и др.).

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

При синтезе операционных логико-запоминающих сред ранее применялись исключительно эвристические подходы (У.Х.Каутц, Я.И.Фет, И.В.Прангищвили). Близкие к автоматным методы были известны только для одно- и двумерных итеративных сетей (К.Шеннон, В.И.Варшавский и др.). В работе ищется разумный компромисс мезду обоими подходами как основа разработки конструктивного метода с элементами эвристики. -

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

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

Методологический аспект связывается в работе с развитием концепции модели системы как конструктивного метода (Ю.А.Щрейдер). Основой развития является соглашение о том,что проектируемое устройство должно в той или иной степени воспроизводить определенные

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

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

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

Наиболее существенные результаты и научная новизна

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

2. Разработана модель оператора задержки в пространствах ото-бражащих числовых последовательностей. Эта модель отвечает введенной аксиоматике и охватывает множество представлений системы, что отличает ее от известных методов проектирования однородных линий. Развита соответствующая аксиоматическая теория. Получены необходимые аналитические зависимости. Установлены частотные и временные свойства найденных решений. Доказана их устойчивость (реализуемость) .

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

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

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

Значение полученных результатов для теории

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

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

3. Разработаны элементы теории абстрактных автоматов и до-следовательностных схем. Найдены классы автоматов и схем без риска сбоя. Определены направления прикладных исследований в этой области.

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

Значение для практики

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

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

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

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

Реализация -результатов. По результатам исследований под руководством автора выполнен проект матричного процессора ассоциативного типа производительностью Ю8 опер/с и разработана кросс-система дай такого процессора. Эти разработки внедрены на предприятии п/я А-3821 и в ОКБ ШС Института кибернетики АН УССР. Отдельные результаты исследований использованы на предприятии п/я М-5769, Казанском заводе ЭВМ и в учебном процессе КГТУ им. А.Н.Туполева.

Апробация -работы. Основные положения диссертации докладывались и обсуждались .на Отчётных научно-технических конференциях КМ: им.А.Н.Туполева (Казань, 1965 - 1992), XXI Всесоюзной научной сес сии НТОРиЗ им.А.С.Попова (Москва, 1965), расширенном заседании ка федры ЭВМ КАИ им.А.Н.Туполева (Казань, 1968), семинаре"Импульсные устройства" ВВИОЛКА им. проф. Н.Е.Ваковского (Москва, 1968), семинаре "Переходные процессы в элементах радиоустройств" ЖШУ им. адм. С.О.Макарова (Ленинград, 1968), заседании секции теории линейных электрических цепей НТОРиЭ им. А.С.Попова (Ленинград, 1969), заседании спец. совета ЛВИМУ км. адм.С.О.Макарова (Ленинград, 1971), семинаре "Цифровые структуры БИС" КАИ ш.А.Н.Туполева (Казань, 1974 - 1989), рабочих совещаниях СКБ КЗЭВМ (Казань, 1974-1981), семинаре "Программируемые логические массивы и матрицы" Института математики СОАН СССР (Новосибирск, 1976 - 1979).семинаре "Аппаратная поддержка функций крмпиляции" ВЦ СОАН СССР(Новосибирск, 1978), Всесоюзном совещании "Проблемы создания и использования высокопроизводительных информационно-вычислительных машин" (Кишинев, 1979), областном семинаре "Математические метода в задачах исследования сложных систем и управления (Пенза, 1981, 1984), заседаниях секции НТС НИЦЭВТ (Москва, 1981 - 1988), засе-

даниях секции НТС НИИ КВАНТ (Москва, 1981 - 1984), заседаниях секции НТО СКВ ММС Института кибернетики АН УССР'(Киев, 1985-1988), заседании рабочей группы при ГКВТИ СССР по подготовке комплексной программы работ по созданию машин баз данных и баз знаний (Москва, 1987), рабочих обсуждениях в отделе 100 Института кибернетики АН УССР (Киев, 1989), расширенном заседании кафедры ЭВМ КГТУ им.А.Н.Туполева (Казань, 1993), семинаре "Математическое и архитектурное обеспечение параллельных вычислений" ВЦ СОРАН (Новосибирск, 1993), семинаре "Теория автоматов и ее приложения" Научного совета по кибернетике АЛ Украины (Киев, 1994), научном семинаре кафедры АВТ СПБГТУ (С.-Петербург, 1994).

Публикации. По теме диссертации опубликовано 45 работ, включая научно-технические отчеты. Из них 12 работ ' опубликованы в центральных журналах, 2 работы изданы в КГТУ им.А.Н.Туполева в качестве учебных пособий.

Научные результаты, выносимые на защиту

1. Концепция схемотехнического моделирования (развитие концепции модели системы как конструктивного метода).

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

3. Абстрактная модель модуля задержки.

4. Решения прикладных задач моделирования оператора задержки.

5. Абстрактная модель последовательностного алфавитного оператора (развитие подхода к синтезу автомата по неформальному заданию).

6. Элементы теории псевдоасинхронных последовательностных

схем.

7. Абстрактная модель оператора над массивами данных (подход к синтезу операционных логико-запоминающих сред). _

8. Решение задачи моделирования двумерного ассоциативного оператора.

9. Исходные гипотезы и рабочие принципы моделирования процессора массивов.

10. Оценка эффективности использования ассоциативного матричного процессора широкого применения.

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

Достоверность. Правомерность сформулированных в работе постулатов и гипотез подтверждена как оригинальными исследованиями автора, так и исследованиями других авторов. Сами конструктивные методы находятся неформально. Однако их разработка ведется в стро-

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

Квалификационный признак. В диссертации решен ряд теоретико-прикладных проблем в области моделирования итеративных систем обработки информации. Совокупность разработанных цри этом теоретических положений можно квалифицировать как новое научное достижение в развитии перспективного направления ИВТ "Однородные структуры" .

Структура и объем работы. Работа состоит из введения, трех глав, списка литературы, заключения и приложения. Общий объем работы 418 стр. Основной текст занимает 295 страниц, 60 рисунков, 33 таблицы. Список литературы включает 297 наименований.

СОДЕРЖАНИЕ РАБОТЫ Введение

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

Концепция схемотехнического моделирования

1. Система - некоторый изначально неполностью определенный объект, заданный своим оператором назначения.

2. Схемотехническое (Б) моделирование системы - процесс разработки конструктивного метода. В этом процессе концептуально вскрывается суть явления и показывается множество реализаций оператора системы с разным качеством (либо одна из них) при достаточно высокой эффективности.

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

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

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

6. Аксиоматическая S -модель - интегрированное аналитическое описание (абстрактный образ) системы, вместе с методами синтеза по нему всех компонентов модели, удовлетворяющее набору постулатов-аксиом. Этот образ считается объектом теории, если основной задачей моделирования является разработка метода его реализации.

7. Гипотетическая S-модель - совокупность базовых компонентов (рабочих принципов) и эвристических приемов, удовлетворяющая принятому набору гипотез, которые разнопланово доопределяют систему. Строится в случае, если абстрактного образа системы найти не удается. Это характерно для сложных иерархических систем.

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

9. Устойчивая компонента модели - определена на множестве представлений системы. Аксиоматическая модель устойчива в целом. Гипотетическая модель с элементэлш эвристики устойчива частично.

Глава I. ОПЕРАТОР ЗАДЕРЖКИ

Определяется проблематика искусственных линий (ИЛ). Дается сравнительный обзор работ по синтезу ИЛ задержи (ШЗ) и связанным вопросам синтеза формирующих цепей и низкочастотных(НЧ) фильтров.

Абстрактная модель звена и вопросы устойчивости. Рассматриваются НЧ однородные ИЛЗ без потерь в случае согласования по входу и выходу на нулевой частоте. Вводятся абстрактные электрическая и структурная характеристики звена задержки как полиномиальная G= = II PR(S) Pets') || , k i £ , и числовая И = II R 3 II матрицы соответственно. Здесь Р^Ф и Pg (S) - некоторые полиномы Гурвица (с нулями в левой полуплоскости комплексной переменной s), степеней к и £ , Эти полиномы определяют схему звена (через пару ре-актансных функций ij - -^j/Mj , j = k,£ ) и функцию передачи

рем и)

ИЛЗ в целом, согласно рекуррентным соотношениям

меи> ^ад р -р

Л к СО Мк1о Ими)

Здесь М^, в ^ - четная (содержит только четные степени з ) и нечетная части полинома Р^ , = В . Элементы Н матрицы:

- порядок звена, 1 = 1 к-£1 - его индекс. Переменная 5 = р^о/2я » Р - оператор Лапласа, - задержка ШЕЗ, П -число звеньев. Показывается, что Ш линиям отвечают нечетные Н-ма трицы (как Й , так ж 0 нечетны).

Полиному Р^а^ = Кк(и."> + 5 > Ч = Э2 , ставятся в соответствие две функции

9КМ/Ми> = - о^и + ...+ НУо^и1-»-...,

Теорема I. Полином Рк является полиномом Гурвица тогда и только тогда, когда «

- при к четном, бесконечная ганкелева матрща Го1=

вполне положительна ранга щ- к/2 ;

-при к нечетном, матрица Г^ = 1 11 0 вполне положительна ранга пг - [А/21 и дополнительно > 0.

Теорема 2. С точностью до постоянного множителя, может существовать самое большее один полином Гурвица Рк(5)= Ь.к(а')+ §9к(и), и. = Ь2 , степени не более к , для которого справедливо

дк(а)/Нк(и) - *>(и) = о(ик"'), (2)

где $(и) допускает разложение

Если такой полином существует, то он является и единственным полиномом, удовлетворяющим условию (2).

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

а2<г, = ± НУ ¿4 я. * 0 ... ; (3)

Q0=const') а„.= 0 , и> к => 1.

Таким образом, можно установить взаимо однозначное соответ-

0 »

ствие мевду полиномом З^урвица Рк (S") и элементом o¿ = / o¿ o¿¡ , ..., кч /к к верного цроотранства отображающих числовых последовательностей. Это пространство полагается евклидовым. Тем самым задача моделирования оператора задержки сводится к

определению в совокупном пространстве элементов o¿K+ = (к, de)t для любых R и П. , области QK+ оптшальных решений как искомой абстрактной модели. Решение называется оптимальным,если переходная характеристика линии /г „(i) , для данных Rh П .имеет минимальное значение некоторой функции величин выброса 5, относительной длительности фронта Тф = "t<p/"t-o и погрешности задержки A10 = At.o/t0 • Это - следствие известной(Ланнэ A.A.) постановки задачи оптимального синтеза электрической цепи.

Для НЧ однородных ИЛЗ и любых R и И вводится следующая аксиоматика.

Аксиома I. Оптимальным решениям отвечает минимальное значение индекса = I.

Аксиома 2. Оптимальные решения характерны тем, что для них все временные параметры kn(i) - § , Тф , дТ0 - одновременно близки к их минимальным значениям, для данных Rh п .

Именно так трактуется далее минимальность . Это не исключает возможность вариаций в 0^*5. с целью некоторого снижения Тер ценой ограничешого роста О ^ при неизменном At0 •

Аксиома 3. Элементы U *е 6 Q * удовлетворяют условие сходимости по расстоянию

¿Ш fU*"*, ck+í)=0, с**г=<с*,сг>, ¿=k*i.

Здесь cv= (с0 , С,, . . . , С i.,') , i 6 {кД}„ Cj - коэффициенты разложения функции ih S .

Как установлено,

co=i, ^^¿с^с,.,, ¿-1...И. u)

При этом предельный элемент с = # tim С1 6 , что показывает

л L ОО

корректность аксиомы 3.

Сформулированным аксиомам удовлетворяет предлагаемая абстрактная модель звена в виде однопараметрической дуги <56 (tt*) во введенных пространствах

ÍR)

i/t2s = о (uk*1), о* «Г-:

Здесь - минимальное значение V, , при котором в (3) =

= 0. Если У, задано, то решение всегда единственно.

Новый тип НЧ Фильтра. Согласно (5), при X, =0 получаем решение о

¿S^^ViV^k-iC^,/с*2,

где все Q-2\ удовлетворяют (3) и Cj - (4).

Теорема 3. Для любых R , решение (6) реализуемо, т.е. определяемые им полиномы Рк , Р^ всегда являются полиномами Гур-вица.

За основные частотные характеристики однородной ИЛЗ принимаются: F„ (и.) - амшштудно-квадратичная функция и dn (и) - функция замедления (групповой задержки).

Теорема 4. Для любых R и /I Ч- I, если ИЛЗ согласована по входу и выходу, то решение (6) удовлетворяет оценке:

- \ = о(и**У, dn^-2/i = о{ик).

Таким образом, при П. = I рассматриваемое решение представля ет собой новый тип фильтра Бесселя - Баттерворта.Исследованы его частотные и временные свойства. Все характеристики оказываются в данном случае наиболее монотонными на ^(У^) .Рассмотрены схемные реализации звена порядка вплоть до R =9. Найдены значения полиномиальных коэффициентов и величины элементов схем.

Аналогичное исследование проведено и при = "У* . В частности, установлено, что характеристика групповой задержки имеет здесь значительный выброс вблизи частоты среза, характерный для оптимальных Ш фильтров (Ланнэ A.A.). Полоса заметно расширяется, в сравнении со случаем - О, что несколько снижает Т<р при практически неизменном § . С ростом л. различия в § проявляются более сильно. Эти решения интересны и тем, что допускают, при четных k < £ , реализацию в виде к /2 различных звеньев с матрицей Н = I! 5 I }\, соединенных каскадно. Рассмотрена процедура такой реализации.

Установлено, что использование звеньев высоких порядков дает выигрыш в суммарной сложности линии И R , необходимой для получения заданного Тер . Значение ДТ0 на ^ (Й7) , для любых П i R , исчезающе мало. Однако величина" 5 всегда значительна, §" ~ ~ 0,1. Последнее характерно для однородных ИЛЗ в целом.

Полиномиальные цепи. Построенная модель распространяется на случай полиномиальных цепей (ПШ с функцией передачи

"mW

Р/77 = Рк(пГ , где полиномы Рмл1 и Рг(п) определены(I),

;з) - (6). При этом фазовая характеристика оказывается той же, гто и для однородных Ш13. Эти цепи штересны тем, что дон них ¡начения 5" исчезаице малы. Правда, величина Тг<р значительно вы-ие, чем в предыдущем случае, при тех же Я и П .Реализация це-щ - лестничная, т.е. морфологически неоднородная. Сравнение по-сазывает, что рассматриваемый метод, при Уд = У Г и данном й [П. = I) обеспечивает для ПЦ лучшее качество , чем другие

1звестные методы (Сканлан Дж., Иуллик С., Матханов П.Н.). Приме-штельно к ПЦ, рассматривается расширение предложенной модели,что юзволяет снизить значения Тер ценой приемлемого увеличения 5• 1олучены решения и конкретные временные оценки при Й = 5-9. Зна-шния 5 варьируются в пределах 0,01 - 0,05.

Однотзодные ИДЗ на Фазовых контурах. Найдены аналитические заражения переходных характеристик однородных ИЛЗ на основе фазо-зых контуров (случай Рк = Ре), удобных для активной ЯО-реализации, при к = 2, 3, 4 и любых П. . Показана целесообразность исто ль зования полученных для НЧ звеньев ( = У*) решений и в этом случае. Проведено детальное исследование переходных процессов з таких ИЛЗ при к - 2.

Простейшие корректированные НЧ звенья. Это - наиболее важный цля практики случай. Для него Н = Ц 5 I }| . Выделяются основные юдклассы таких звеньев (различные виды коррекции) и детально ис-зледуются. Для большинства из них это делается впервые. Достаточно сказать, что до сих пор в теоретических исследованиях и практических разработках не идут дальше класса Н = || 3 I \1 , заведомо ленее экономичного. Результаты проведенных экспериментальных ис~ зледований подтверждают правильность введенной аксиоматики и близость к глобальному оптимуму решений в области £6 (У^. Экспериментально устанавливается справедливость строго доказанной (Ману-кян Э.М.) для простого-ячеечного НЧ фильтра формулы

Т^^п"2'3, (7)

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

Гибридные линии. Решение задачи синтеза ИЛЗ с высоким качеством переходной характеристики ищется на пути построения гибридных линий. При этом основной вклад в задержку вносят однородные ИЛЗ, а для получения достаточно монотонной ЬШ при заданной дли-

тельности фронта, выходной сигнал этой ИЛЗ пропускается через НЧ фильтр полиномиального типа. За основу его реализации может быть взято любое из известных монотонных решений для полинома. Рт (5) . Выбор Рт я Р^* Р^ наиболее целесообразен. ЛЦ реали-

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

Рассматривается случай использования в однородной части звеньев с матрицей Н = ^ 5 11| . Задача синтеза гибрвдной линии сводится к отысканию в данном классе полиномов Рт , при известном П , определенном формулой (7), таких значений т и 10, (задержка ПЦ), которые обеспечивают получение требуемых Ту , дТ0 и 5 с заданной погрешностью. Это определяет схему линии в целом, т.к. задержка однородной части 102 = "Ь 0 - ± 0< . Решение задачи ищется вариацией значений "Ь 01 / 10 при условии равенства длительности фронта переходной характеристики ПЦ (условного входного сигнала однородной ИЛЗ) заданному значению "¿<р . Результаты проведенного вычислительного эксперимента говорят о том, что для полного класса звеньев Н =Цб 11| , выбор > 0,1 ^ дает погрешность по Т^ не более 10% и значение 8 не более 0,03. При выборе 4:01 =0,2"Ьо названная погрешность снижается до 5% при практически неизменном выбросе. Величина ДТ0 не превышает 0,010,02. Это определяет соответствующую расчетную процедуру.

Рассмотрено обобщение метода на случай гибридных линий на основе фазовых контуров (ФК). Концевое звено реализуется здесь как лестничная цепь на входе линии, что более удобно. Полином Р ЦпЛ четной степени, I = чет /к, {/, определяющий ФК,находится по (I) с использованием решений при = У* для к =2, 3, 4. Реализация ФК выполняется известным образом. Расчет остается прежним. При этом устраняются процедурные сложности, свойственные одному из наиболее развитых для гибридных линий на основе ФК подходу (КухЕ.С.).

Формирующие .пинии. Проведено натурное экспериментальное исследование известных канонических схем включения однородной ИЛЗ в формирующую цепь при й = 3- 9, П. = I -10, Оптимальность решений (определяется аналогично ИЛЗ) в .области (У4) установлена и для таких схем. При этом наилучшие результаты, по всем параметрам формируемого импульса, дает выбор' - • ® случае Н = = |15 1Ц экспериментально найдены оптимальные решения для всех вариантов коррекции. Установлено, что для рассматриваемых схем значение выброса на вершине формируемого импульса всегда не менее 0,3. Это делает необходимым применение концевых звеньев.

За основу синтеза формирующих линий с концевым звеном принимается метод, использованный ранее для гибридных ИЛЗ.Вычислительный эксперимент, проведенный для полного класса звеньев Н = = Ц5 X || , показывает, что предложенный метод гарантирует получение задержанных на время ■Ь т симметричных импульсов с практически плоской вершиной и отсутствием заметных послеимпульсных колебаний. Для этого метода: расчетная задержка Щ -Ь04 = 0,25где Н: н - длительность формируемого импульса; расчетная задержка однородной ИЛЗ = 0,5 ±ц; необходимое число звеньев П = 0,5 х [Кв(1-*То0/'с<р13/2 » та0 ^ а ^ф"* заданная дли-

тельность фронта, имеет те же значения, что и для однород-

ной ИЛЗ; расчетная длительность фронта для ПЦ равна "Ьф .Погреш-зость реальных временных оценок - не хуже 10%. Вполне удовлетворительные результаты (§ =0,04) дает выбор = 0,125 .Разработанная процедура распространяется на случай двухполюсной реализации формирующего элемента.

Глава 2.1. ШСЛЕДОВАТЕЛЬНОСТНЫЕ ОПЕРАТОРЫ

В соответствии с принятой концепцией схемотехнического моделирования, процесс проектирования цифрового устройства связывается триадой: исходное описание (последоватвльностный алфавитный эператор) - абстрактный автомат (объект аксиоматической теории) -госледовательностная схема (конструктивный метод, или модель). 3 данном случае оператор системы задан тройкой {X , . Здесь

£ - отображение О г^ ^ { 0а} определенного множества зходных слов I г , ъ = I, '2, ...,в алфавите X во множество вы-содных слов 0г в алфавите г* . Отображение считается автолатным. Поэтому для заданного ¿_ всегда существует аботрактный автомат вида {X , 2., 5 , ^ , ^ "V • Здесь $ - множество внутренних состояний автомата, включая начальное, £ и ^ - функции тереходов и выходов.

Основной задачей абстрактной теории автоматов (по Глушко-зу В.М.) является установление связей мезду отображениями и автолатами. Поэтому автомат - объект такой теории. Ее же саму можно рассматривать как аксиоматическую теорию цифровых устройств постольку, поскольку для них приняты известные аксиомы автоматности. Гот факт, что, по своей сути, указанная теория неформальна,не противоречит сказанному.

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

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

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

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

Предлагается универсальный способ определения множества состояний синтезируемого автомата Мили, синхронного или асинхронного, непосредственно по исходному описанию. Понятие асинхронного автомата не связывается со способом реализации. Само устройство может быть как синхронным, так и асинхронным. Отображение называ-. ется асинхронным, если для любых к и Д » I, из 0г сле-

дует

(*'-.. . и1-.. • •, (8)

т.е. п - кратное повторение к -входа вызывает такое же повторение- к -выхода с сохранением соответствия в целом. Здесь X и г. 6 1. - входной и выходной символы, к - номер такта, £ - длина слова.

Утверждение I. Если и только если /. асинхронно, то для автомата Мили и любых к > 1 ' . . , ' ■ ''

Здесь 5 6 5 - символ внутреннего состояния.

Автомат (и его таблица переходов), который удовлетворяет(9), называется асинхронным. Отображения, автоматы и таблицы, для которых условия (8) и (9) не выполняются, называются синхронными. Синтез автомата Мили, синхронного или асинхронного, сводится к построению таблицы переходов, строки которой отмечены символами внутренних состояний ь1*^ =1, 2, ..., а столбцы - значениями входов . В каждой клетке таблицы слева обозначается следующее состояние = , через запятую справа - значение выхода а*3 ^ Б*"1).

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

Состав группы ограничивается требованием, чтобы переход в любое состояние автомата происходил только при одном изменении входа -X. = <Х4 . . . , • € {о, 1} . Вместе с условием ут-

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

Внутреннее состояние автомата определяется как объект,специфицированный кортежем ^ иаг Я , 2 > ИНДЕКС > . В общем случае атрибут ИНДЕКС рассматривается как вектор. Он учитывае-г значения некоторых параметров (признаков), задаваемых исходным описанием непосредственно либо получаемых из него дедуктивно. Задача синтеза автомата сводится к определению перечня спецификаций (разметка состояний) и организации переходов между выделенными состояниями (испытание состояний), согласно исходному заданию. Разметка называется полной, если указанный перечень учитывает все условия задачи. Исходное описание полагается корректным. Это означает, что получаемая из него полная разметка должна быть правильной. Разметка называется правильной, если она обеспечивает замкнутость покрытия (Ангер С.). Способ получения полной разметки перечислением всевозможных значений специфицирующих кортежей называется каноническим способом полной разметки.. Полная разметка называется компактной, если число состояний автомата близко к минимальному.

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

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

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

3. Осуществляется переход к полной компактной разметке. При этом могут быть использованы развитые споообы минимизации(Ангер).

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

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

Псевдоасинхронные последовательностные схемы. За основу развития принимается классический способ прямой реализации синхронного устройства с однофазной синхронизацией. При этом в схеме явно выражены три регистра - входной » выходной Й&И. и внутрен-

них состояний Й& У - со своим управлением. Этот способ может обеспечить надежное функционирование устройства,если автомат асинхронен. Для синхронных автоматов таких гарантий дать уже нельзя. В качестве альтернативы прямому способу предлагается класс псевдоасинхронных схем. Вместе с прототипом, он образует множество моделей, на котором ищется оптимальное решение. Критерием оптимальности считается реализуемость схемы заданного быстродействия при минимальной сложности, определяемой числом эквивалентных вентилей на кристалле.

Псевдоасинхронными называются синхронные последовательност-ные схемы с однофазной синхронизацией и динамическим управлением, в которых..синхронный регистр У отсутствует, а функции переходов и выходов реализуются асинхронной схемой (АС).При этом схема с явно выраженными регистрами ЯЭХ .и Я& 2 называется асинхронной регистровой. Схема с явно выраженным 2. и включением сигнала синхронизации в число входов АС называется С-асинхронной регистровой. Если же функции Я&Х и Я&И. совмещены с АС, имеем С-асинхронную безрегистровую схему.

Для асинхронной регистровой схемы вводятся следующие ограничения.

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

Тта* < 2Т т1п , <*>)

где ТГ таЖ и ТГ- максимальная и минимальная задержи элементов. Задержки в соединениях отсутствуют. Во время действия синхроимпульсов входы -схем полагаются неизменными. Параметры синхросигналов

Ъс^ю + т^е+г,,; "VI с (п)

Здесь Тс и "Ьс - период и длительность синхроимпульсов, -

задержка регистров, "1:дс - задержка АС, т ъ 1 - число внутренних тактов схемы, "Ь п - время подготовки "2 , ДТ* - время формирования значения входа для очередного такта.

Ограничение 2. Комбинационная часть схемы представляет собой 2-уровневую реализацию ДШ. Перегрузка по входам элементов первого уровня- отсутствует. Перегрузка по выходам устраняется дублированием элементов.

Ограничение 3. Кодирование внутренних состояний схемы правильно (по Ангеру С.).

Ограничение 4. Регистр X строится на основе 1} -триггеров с прямым потенциальным управлением на элементах И-ИЛИ-НЕ. Для формирования сигналов состояний используются асинхронные Я 5 -триггеры с прямым управлением в составе АС.

Утверждение 3. Если отображение асинхронно и выполнены ограничения I - 4, то асинхронная регистровая модель реализуема.

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

Для С-асинхронных схем характерно использование сигнала синхронизации как дополнительного входа асинхронной схемы, реализую-

19

щей заданные функции переходов и выходов автомата. Тем самым каждый такт разделяется на два полутакта. Первому полутакту отвечает изменение синхросигнала из 0 в I. Второму - из I в 0. При этом каждый переход исходной автоматной таблицы преобразуется в два перехода С-асинхронной. За исходную для построения С-асинхронных таблиц принимается минимизированная таблица переходов автомата »синхронного или асинхронного. Для обоих случаев, разрабатывается алгоритмический метод, который охватывает как регистровую, так и безрегистровую реализации. Он сохраняет свойство минимальности таблицы в процессе ее преобразования.

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

Утверждение 4. Если отображение 1_ асинхронно, в ограничении I снято условие (10) и учтено отсутствие Й&Х в (II),в ограничении 2 оставлено только условие 2-уровневой реализации ДНФ, удовлетворены ограничение 3 и часть ограничения 4 - для ЙВУ , выявлены все простые импликанты для выходов по путям второго полутакта, то С-асинхронная регистровая модель реализуема.

Выполнение всех условий утверздения 4 не вызывает затруднений. Эти условия однозначно определяют процедуру синтеза С-асинхронных регистровых схем любой сложности по заданной С-асинхронной таблице. И, главное, С-асинхронная схема для асинхронного ав-■ томата некритична к разбросу задержек элементов.Это выделяет рассматриваемый случай из всех других.

Утверждение 5. Если отображение синхронно, введен асинхронный В -триггер (регистр) на элементах ИЛИ-НЕ для синхросигнала, удовлетворены ограничения I - 4 (с коррекцией последнего на отсутствие Я&Х) и выявлены указанные ранее простые импликанты, то С-асинхронная регистровая модель реализуема. При этом, если отсутствует необходимость разгрузки выходов введенного Л -триггера, то условие (10) в ограничении I снимайтся.

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

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

Сопоставление с прямой реализацией. Достижимость реализуемости в условиях практики (риск сбоя возможен, но не проявляется) рассматривается как наиболее объективный критерий пригодности той или иной модели. Анализ реализуемости в таком смысле требует учета задержек в соединениях и процессов в регистре состояний. Эти задержи, будучи ассоциированы со временем нарастания и спада синхросигналов, могут оказаться значительными. Они проявляются либо в эквивалентном росте задержек элементов, либо аналогично включению повторителей на их входах. Сопоставление двух выделенных ранее моделей проводится с учетом указанных факторов и по отдельности - для случаев синхронного и асинхронного автоматов.

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

, Глава 2.2. ОПЕРАТОРЫ НАД МАССИВАМИ ДАННЫХ

Рассматривается реализация операторов обработки однородных массивов данных на основе. операционных логико-запоминающих сред (ЛЗС). Понятие таких сред вводится как результат естественного развития идеи преобразования тактности для последовательностных схем, когда таблица переходов автомата реализуется итеративной цепью. При определенных соотношениях медду временами обменов с памятью и обработки в цепочках ограниченной-длины, такие структуры дают существенный выигрыш не только в производительности, но и в эффективности массовой обработки по критерию ПРОИЗВОДИТЕЛЬНОСТЬ/ ОБЪЕМ ЬБОРУДОВАНИЯ.

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

Вопросы итеративной реализации арифметико-логической обработки средствами АДУ и аккумуляторов достаточно изучены и в работе не рассматриваются. Основой развиваемого подхода к синтезу операционных ЛЗС по заданному набору операторов над массивами является гипотеза о существовании абстрактной модели системы обработки массивов данных, если ее оператор удовлетворяет определенному условию. Конструктивность подхода показывается на множестве операторов числового поиска, над булевыми матрицами, операторов символьной обработки. Особо выделен двумерный ассоциативный оператор, в связи с распознаванием абстрактных двоичных образов.

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

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

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

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

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

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

Операторы над булевыми матрицами. Операторы обработки булевых матриц достаточно сложны и специфичны. Однако операционные ЛЗС вполне адекватны, в смысле реализуемости требований декомпозиции, и таким операторам. Чтобы это показать, для целей исследования выбраны неординарные операторы нахождения матрицы совместимости и поиска минимального покрытия (Закревский А.Д.), выполнение которых занимает основное время в процессе минимизации на ЭВМ полностью определенных булевых функций. Показывается разнообразие ассоциативных подходов при решении логических задач, специфика функционирования и синтеза регистров обрамления. ■

Операторы символьной обработки. Рассматривается реализация на основе ЛЗС множества операторов, выявленных из анализа операторов языка СН0Б0Л-4 и опыта работ с таблицами в процессе трансляции, - т.н. символьных операторов. Это - операторы сжатия элементов массива с исключением заданного символа,' байтовых сдвигов до совпадения в определенном байте с указанным символом,побайтной перекодировки до или после заданного символа и т.д. При выполнении всех этих процедур широко используется аппарат ассоциативного поиска в пределах байта, маскирования и активизации байта.

Двумерный ассоциативный оператор. Двумерный ассоциативный по иск связывается с построением систем обработки структуризованных двоичных изображений как упорядоченной совокупности абстрактных образов. Вопросам генерации и эффективной обработки изображений такого рода уделяется серьезное внимание в концептуальных проек тах ЭВМ будущих поколений (Мото-Ока Т.).

Задача распознавания абстрактных двоичных образов в терминах ОБЪЕКТЫ - КООРДИНАТЫ первоначально формулируется следующим образом. Задана троичная матрица

Х=11хрг)|, Хрг€{0,1,->, р=1...т, Я=1...л.

Требуется определить все ее вхождения в двоичный массив

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

Формулируется общая задача идентификации: Для данного троичного эталона X , = I ... $ , $ - число типов объектов .найти координаты всех покрываемых им объектов двоичного изображения А =■ II С*¿1. , ^ = I ... К , 1 = 1... Л . Размеры матриц А и Xе1 полагаются достаточно большими. Решение задачи предлагается искать путем анализа изображения последовательно по кадрам к х-8(к<К, ж многотактно - фрагментами по (I х , ГЦ » 2, - для кавдого эталона. . .

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

; = 1 , 1... С, 1=1...а.

Результаты распознавания соседних по горизонтали фрагментов сцепляются. Аналогично сцепляются результаты распознавания соседних горизонтальных слоев. Реализация алгоритма ищется на комплексе СПЕЦПРОЦЕССОР - БАЗОВАЯ ЭВМ. Строится морфологическая модель спец-цроцессора-ддентификатора. Синтезируются элементы операционных матриц.

Разрабатываются алгоритмы полного решения задачи идентифика-ш на комплексе и на универсальной ЭВМ. С учетом состава команд структурных особенностей устройств, получены оценки числа машин-к тактов, требуемых для реализации алгоритмов в том и другом ¡учаях. В итоге показано, что использование спецпроцессора поз->ляет повысить скорость идентификации примерно на два порядка, сравнении с универсальной ЭВМ с той же длительностью такта. Негодование проведено при К = L = 512 ... 1024, т* = ^=16 ... . 24, tf =32 ... 64 и "шашечном" расположении объектов.

Получены оценки аппаратных затрат. При к = •£ =128 и П { = 2 обрабатывающая часть спецпроцессора занимает 2294 корпусов БИС i 60 выводов, что требует для своего размещения 406 ТЭЗ на 264 гналъных выводов каздый. Установлено, что эффективность исполь->вания спецпроцессора растет с уменьшением размеров объектов.Раз-ры изображения в целом и параметр У слабо влияют на эффектив-

iCTb.

Глава 3. ПРОЦЕССОР МАССИВОВ

Процессор массивов (ИМ) рассматривается как достаточно уни-рсальное аппаратно-программное средство параллельной обработки юсивов данных. Он функционирует в комплексе с базовой ЭВМ сред-¡й производительности как своеобразный акселератор при решении ;ожества задач проблемной ориентации, указанных ранее. За осново-'лагающий принцип моделирования ПМ принимается ориентация процес-ра на эффективное выполнение всех основных видов массовой образки (арифметической, логической и т.д.), а не на узкую предмет-то область. В ряде давних прогнозов (Глушков В.М.,Ершов А.П.,Ат-нсон Т.Д., Гальярди У.О. и др.) предпочтение отдавалось проблем->й ориентации. Однако время вносит свои коррективы.

Предпосылки эффективности. Отличительной особенностью ассо-[ативной обработки (она принята для ПМ) является сравнительно вы-окий удельный вес поисковых операций, реализованных аппаратно, юраций над масками и т.н. манипуляторных процедур. Сравнение iex основных способов реализации ассоциативных принципов обработ-[ массивов данных - многофункциональные запоминающие устройства ©У (Балашов Е.П., Кноль А.И.), ассоциативные параллельные про-юсоры АПП (Фостер К., Прангишвили И.В., §ет Я.И.), операционные (С - позволяет заключить, что последние занимают промежуточное 1Ложение медцу первыми двумя. Обработка массивов данных выполня-•ся в них не последовательно по словам (как в случае МФЗУ) и не раллельно-последовательно по битовым срезам матрицы памяти в це-

лом ^случаи аш; , а параллельно-последовательно по слоям буфера (размер слоя совпадает с матричным). То, что производительность здесь будет выше, чем в первом случае, вполне очевидно. Проводя сравнение со вторым вариантом, полезно учитывать критерий эффективности.

Операции АЛЛ'достаточно элементарны (сравнение, чтение, запись). Поэтому, чтобы получить, например,производительность(в пересчете на один операнд) Ю8 опер/с, надо одновременно обрабатывать до Ю4 операндов. Для известных вариантов АЛЛ (Прангишви-ли И.В., Фет Я.И.) реализация ассоциативной матрицы 8К х 32 бит потребует до 32К корпусов БИС на 40 выводов. Необходимое быстродействие операционных-матриц ограниченных размеров достигается соответствующим выбором состава матричных операций, реализуемых однотактно. В работе показано, что производительность Ю8 опер/с достижима на матрице ЮС 32 х 32 бит. Для ее реализации потребуется 128 корпусов БИС типа секционного микропроцессора на 48 выводов. Если к этой матрице добавить буфер глубиной 2К и объемом слоя 1К бит, то потребуется еще 128 микросхем памяти 2К х 8. Выигрыш по объему оборудования, в сравнении с АЛЛ получается значительным, при неизменном объеме памяти данных..

Обработка массивов по фрагментам, характерная для матриц ограниченных размеров, существенно замедляет процесс. Но это компенсируется ростом быстродействия базового модуля и совмещением процессов обработки и обменов с базовой ЭВМ. В условиях АПП, такое совмещение требует использования специальных средств ортогонали-зации. Поэтому операционные ЛЗС, потенциально, могут обеспечить более высокую эффективность процессора массивов по критерию ПРО-ИЗВОДИТЕЛЬНОСТЬ/ОБЪШ ОБОРУДОВАНИИ, чем классическая ассоциативная матрица.

Показывается, что использование операционных ЛЗС в качестве морфологической основы процессора массивов естественным образом приводит к построению микропроцессорных матричных систем ассоциативного типа класса Б!МБ (единый поток команд и множественный поток данных). Дается характеристика состояния работ по матричным процессорам в целом. Устанавливается, что именно универсальность процессора массивов делает его разработку и применение экономически оправданными.

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

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

Гипотеза 2. Использование ассоциативных принципов для целей массовой обработки предпочтительно.

Гипотеза 3. Усложнение базового модуля-операционной матрицы в разумных пределах целесообразно.

■Гипотеза 4. Итеративная обработка по строкам операционной матрицы в каждом такте способствует росту эффективности обработки массивов. ; .

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

Принципиальными для организации обработки на комплексе БАЗОВАЯ ЭВМ - ПРОЦЕССОР МАССИВОВ считаются следующие положения (рабочие принципы), которые формируются на основе накопленного опыта моделирования.

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

2. Базовый модуль операционной матрицы представляет собой байтный секционный микропроцессор, состав операций которого выявляется из анализа адаптированных к ЛЗС алгоритмов микропрограммного выполнения принятых матричных команд ПМ. Каждый такой модуль регулярно связан по горизонтали и вертикали с 4 ближайшими соседями. 3 его состав обязательно входит триггер активности.

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

4. Память программ ПМ отделена от памяти данных и входит в состав устройства управления (скалярный процессор в составе ПМ). Операции управления совмещены во времени с операциями матричной обработки и обменов с базовой ЭВМ.

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

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

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

В процессе моделирования 11М решаются следующие задачи.

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

2. Исследование эффективности ПМ в составе комплекса.

3. Развитие методов нечисловых применений ПМ на задачах лексического распознавания и организации работ с базами данных.

Модель процессора. Приводится краткая характеристика разработанной и исследованной под руководством автора модели (проекта) ПМ. При этом основное внимание уделено регистровой структуре,принятому составу команд, особенностям обработки по полям, устройству и функционированию ПМ в составе комплекса. По своим функционально -топологическим признакам, построенная модель относится к классу матричных процессоров ассоциативного типа. Наиболее близки к ней матричный процессор ПАР (Англия) и МРР (США).

В качестве базовой условно принималась ЭВМ ЕС-1045. Соответственно, проект был выполнен из условия размещения ПМ в стандартной стойке ЕС. Это предопределило выбор элементной базы, размеры обрабатывающей части (матрица 32 х 32, глубина буфера Ш), разработку всех принципиальных схем и времена выполнения команд ПМ. Решение двух первых задач моделирования проводилось путем модельного эксперимента по выполненному проекту ПМ на специально разработанной кросс-системе. Генерация системы осуществлялась по параметрам проекта.

Результаты проведенного кросс-эксперимента таковы. Производительность ПМ на множестве команд структурной, символьной, логической обработки и команд арифметики с фиксированной запятой оценивается в ТО8 опер/с. Для команд с плавающей запятой оценка на порядок ниже. Однако и здесь полученные результаты вполне удовлетворительны. На это, в частности, указывает сопоставление оценок производительности на базовом множестве команд спецпроцессора ЕС

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

Производительность комплекса оценивалась на ряде задач проемной ориентации: транспонирование булевой матрицы 512 х 320; ртировка массива 4К 32-разрядных кодов; минимизация СБФ, задан-й на 64 интервалах; программа Р01 I Пакета матфизики ЕС ЭВМ, ласть 16000 точек, точность 0,1; программа обработки карт сло-ря внешних символов Редактора связей ОС ЕС, объем 64 записи; общение текстовых команд для строк произвольной длины,128 строк 80 символов; распознавание абстрактных двоичных образов.размер цра 896 х 1024 бит. Полученные данные показывают, что подключе-е ПМ к базовой ЭВМ должно приводить к повышению производительно-я при решении рассмотренных задач в среднем на порядок. Обсуж-ются причины снижения системной производительности комплекса, в авнении с быстродействием ПМ. Это - влияние канала, ограничен-х размеров матрицы, несовершенства использованных параллельных горитмов. Анализируется.влияние пропускной способности канала, танавливается, что проблема внешних обменов для разработанной дели ПМ полностью решается при быстродействии канала IM ... . ЗМ байт/о.

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

Работы с базами данных. Уяснение места и роли ПМ в системах формационного обеспечения проводится одновременно с установлени-

эффективности предлагаемого для машин баз данных (МВД) дерева работки запросов (рисунок) как исходной - гипотезы моделирования. , рисунке: R t , L = I ... С , - отношения базы данных, участ-щие в обработке данного запроса, (Г - операция селекции, 3£ -ерация проекции, X - операция декартова произведения. В 'Слу-,е следования схеме СЕЛЕКЦИЯ - ПРОЕКЦИЯ - СОЕДИНЕНИЕ(Ульман Дж.),

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

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

Второй (и основной) вариант представляет систему с большей глубиной распределения, в случае предварительной сортировки отношении перед их соединением. Функции программного процессора-транслятора, системного монитора и управляющего процессора комплекса БАЗОВАЯ ЭВМ - ПРОЦЕССОР МАССИВОВ реализуются на отдельных МЭВМ. При ^этом указанный комплекс рассматривается как спецпроцессор ТО IN . предназначенный для выполнения операции соединения. Эффективность предложенного дерева обработки показывается путем разработки и моделирования алгоритмов специализированной операционной системы МБД. В данном случае параллельная работа всех процессоров синхронизируется путем обмена сообщениями. Именно это обеспечивает функционирование машины баз данных по потоково-конвейер-ному принципу с исключением коллизий.

Приложение. Дается перечень научно-технических отчетов по НИР (19 отчетов), выполненным под руководством автора, материалы которых использованы в работе в соответствии с его личным научным вкладом. Указанные НИР проводились по договорам с Казанским заводом ЭВМ, Институтом математики СОАН СССР, ШЦЭВТ, НИИ КВАНТ, СКВ ММС Института кибернетики АЛ УССР и по госбюджетной тематике.Приводятся акты об использовании материалов (5 актов) и внедрении результатов (3 акта) этих НИР, официальные документы по методике проведения и результатам испытаний кросс-системы, а также отзывы семинаров СО РАН и АН Украины о работе в целом.

ЗАКЛЮЧЕНИЕ

В диссертации выполнено исследование методологических и тео-)етико-прикладных вопросов моделирования итеративных систем обра-¡отки информации. В процессе исследования:

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

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

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

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

Полученные результаты в целом представляют решение комплекс-юй научно-технической проблемы моделирования систем, обработки [ассивов данных на избранном множестве задач. Вместе с тем, зна-лмость вопросов моделирования рассмотренных операторов- выходит ;алеко за рамки указанной предметной области. Разработанные в дис-;ертации теоретические положения являются новым научным вкладом в >азвитие перспективного направления "Однородные структуры".

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

1. Райхлин В. А. Анализ симметричных структур задерж-;и //Радиотехника, т.24, 1969, 1в 2, с.98-100.

2. Райхлин В. А. Анализ переходных процессов в линиях вдержки на основе простейшего Т-мостового звена //ИВУЗ-Радиоэлек-роника, т.13, 1970, № II, с.1313-1319.

3. Райхлин В. А. Простейшие корректированные линии за-;ержки с высоким качеством переходной характеристики //Радиотехни-:а, т.25, 1970, й 12, с.59-69.

4. Райхлин В. А. Об одном классе прецизионных искус-;твенных линий задержки //Радиотехника и электроника, т.15,1970, г 8, с.1613-1621.

5. Р а й х л и н В. А. Синтез искусственных линий в прО' странствах отображающих числовых последовательностей //Радиотех' ника и электроника, т.17, 1972, Л 5, с.989-995.

6. Райхлин В. А. Однородные искусственные линии задержки как формирующие линии //Радиотехника, т.29, 1974, № ! с.64-70.

7. Р, айхлин В. А. Асинхронные цифровые схемы и модул] ные структуры. Казань: Казанский авиационный институт, 1980,102

8. Райхлин.В. А. Псевдоасинхронные последовательное, ные схемы //Управляющие системы и машины, 1993, гё 5, с.33-41.

9. Р а й х л и н В. А. К синтезу автомата по неформально! заданию //Кибернетика и системный анализ, 1994, $ 4, с.29—41.

10. Райхлин В. А. Операционные логико-заломикащие с] ды. Вопросы применения и синтеза //Автоматика и телемеханика, 1983, Л II, с.161-171.

11. Райхлин В. А. Об использовании аппарата двумерни .ассоциативного поиска в процессе распознавания //Межвуз. сб. Прс блемно-ориентированныо сродства повышения эффективности вычисл! тельных систем. Казань, 1991, с.38-54.

12. Р а й х л и н В. А., М е д в е д е в А. С., М о т яг и н В. Г. О задачах матричной компиляции //Мелевуз. сб. Вычис лительные и управляющие системы летательных аппаратов.Казань,19с с.56-61.

13. Райхлин В. А., М е д в е д е в А. С., М о т яг и н В.-- Г. Вопросы разработки матричных компиляторов //Вычис лительные системы, вып.89, 1981, с.69-83.

14. Р а й х л и н В. А., М о т я г и н В. Г., Медведев А. С., И л ь и н А. В., Ш в а р ц м а н М. И. К исследованию эффективности комплектования универсальных ЭВМ средней производительности матричными процессорами ассоциативного типа //Управляющие системы и машины, 1985, й 3, с.23-28.

Формат 60x84 1/16. Бумага Об(р>>?<?й#?#Печать офсетная. Печ.л. 2,0. Усл.печ.л. 1,86. Усл.кр.-отт.1,91. Уч.-изд.л. 2,0.

Тираж 100 . Заказ Ч/Ц/р Ц38,,

Санкт-Петербургский государственный технический университет

Ротапринт Казанского государственного технического университета им.А.Н.Туполева.

420111, Казань, К.Маркса, 10.