Введение к работе
Итеративными называются системы, операторы назначения которых допускают абстрактное представление последовательностью повторяющихся действий.
Актуальность темы.Вопросам теории и практики итеративных систем обработки информации, в их взаимосвязи с однородными структурами, уделяется неизменное внимание во всем мире, .начиная с 60-х годов (Глушков В.М., Евреинов Э.В., Балаховский И.О., Грегори Дж., Унгер С, Слотник Д., Холланд Дж. и др.). Определяющим моментом в данном случае является топологическая повторяемость модулей и регулярность связей между ними.
Однородные структуры хорошо адаптируются к обработке массивов данных. Повышение эффективности такой обработки - одно из важнейших направлений развития компьютерной архитектуры. Это определено высоким удельным весом таких задач, как обработка изображений и цифровая обработка сигналов, распознавание образов, задачи линейной алгебры и математической физики, автоматизации проектирования, компиляции языков программирования, управления базами данных и т.д.
Необходимые предпосылки к повышению производительности информационно-вычислительных систем при решении перечисленных задач создает широкое использование ассоциативных принципов. Теория классических ассоциативных параллельных процессоров достаточно развита (Фостер К., Дрангишзили И.В., Фет Я.И. и др.). Имеются и промышленные образцы. Однако получение высокой производительности связано в них с чрезмерными аппаратурными затратами. Это ограничивает рынок сбыта и уровень финансирования работ по ассоциативным процессорам в целом (Тербер К.).
Новый промышленный интерес к ассоциативным процессорам пробудился с развитием архитектур ЭВМ пятого поколения (Мото-Ока Т., Симоне Г.) и особенно - машин баз данных (Мартин Г., Шустер С, Озкарахан Э., Майерс Г. и др.). Но указанное ранее затруднение остается. В этой связи, серьезного внимания заслуживают ассоциативные матричные процессоры (типа Ь АР > МРР и ДР-) как компактная альтернатива классическому варианту. Однако до сих пор это - сугубо инженерные разработки, уникальные в своей основе. Создание общих конструктивных методов проектирования таких процессоров представляет актуальную задачу. Она определяет избранное в работе направление исследований.
Цели работы. Методологической целью работы является развитие концептуального подхода к моделированию систем в условиях неполной определенности. Разработка необходимых теоретических представлений и конструктивных методов на избранном множестве задач моделирования итеративных систем, связанном с проектированием матричных процессоров ассоциативного типа (моделированием процессора массивов) составляет теоретико-прикладную цель исследований.
Работа выполнена в соответствии с Комплексной программой НТП СЭВ (проблема I.I.9, задание 1.6), Программой 0.80.01 ГКНТ СССР, Приказом руководителя организации п/я М-5804 от 23.04.85 J* 223, . Постановлением СМ СССР от 16.06.87 Ш 675-155,Приказом Минвуз СССР от 30.07.87 В 21, Приказом Минвуз РСФСР от 03.09.87 JC» 122, Планами работ по научно-исследовательским темам Казанского авиационного института им.А.Н.Туполева (номера госрегистрации 76047362, 77049512, 78076196, 8I02362I, 8II03626, 0I82008I34I, 01840036264, 01850074085, 01860070322).
Основные задачи исследования. В трех основных подсистемах процессора массивов - синхронизации, управления и обработки - выделяются фундаментальные проблемы моделирования операторов задержки, последовательностных алфавитных и над массивами данных. Это -рассматриваемый схемотехнический уровень. Затем, уже на системном уровне, строятся модели процессора в целом и машин баз данных на его основе как важной перспективе применений. Тем самым предметно охватываются различные классы моделей итеративных систем обработки информации: строго регулярные, рекурсивные, однородные сети как морфологическая основа модели системы, структурно однородные при функциональном различии компонентов.
Модели задержки строятся как однородные искусственные линии. Модели последовательностных алфавитных операторов - во введенном .в работе классе псевдоасинхронных последовательностных схем. Реализация операторов над массивами данных проводится в базисе операционных логико-запоминащих сред (У.Х.Каутц) как морфологической основы процессора массивов. Организация работ с базами данных рассматривается в классе функционально полных машин баз данных (Л.А.Калиниченко) распределенной архитектуры.
Моделирование оператора задержки проводится из условия получения заданного качества переходной характеристики при минимальной сложности линии в целом. Поиск решений- ведется на множестве базовых модулей произвольных порядков (случай пассивной Z.C -реализации) , что обуславливает новизну постановки задачи. Разработанные ранее методы ориентированы на использование недостаточно экономич-
ных звеньев третьего порядка (Я.С.Ицхоки, Э.М.Манукян, С.И.Евтя-нов и др.) либо на построение неоднородных линий (В.Е.Томсон, П.Н.Матханов, Е.С.Кух и др.).
Рассмотрение последовательностных алфавитных операторов связывается с развитием неформальных подходов к синтезу автомата и реализующей его последовательностной схемы. При этом риск сбоя, по возможности, исключается в процессе проектирования. Большинство известных методов абстрактного синтеза (В.М.Глушков, Б.А.Трах-тенброт, АЛерч и др.) ориентировано на использование формальных языков. Это затрудняет процесс синтеза, т.к. исходное описание проектируемого устройства обычно не формализовано. Классический подход к реализации автомата не снимает проблемы состязаний.
При синтезе операционных логико-запоминающих сред ранее применялись исключительно эвристические подходы (У.Х.Каутц, Я.И.Фет, И.В.Прангидшили). Близкие к автоматным методы были известны только для одно- и двумерных итеративных сетей (К.Шеннон, В.И.Варшавский и др.). В работе ищется разумный компромисс между обоими подходами как основа разработки конструктивного метода с элементами эвристики. .
Задача моделирования процессора массивов как сложной системы рассматривается во взаимосвязи множества факторов. Примеры проведения подобных исследований, до разработки опытного образца процессора, автору неизвестны. Исследование выполнялось силами научного коллектива под руководством и при непосредственном участии автора. Это участие состояло в формулировке исходных посылок моделирования и постановке его задач, в разработке алгоритмов и сравнительной оценке эффективности комплекса при решении задач распознавания и управления базами данных.
Моделирование машин баз данных (МВД) ведется из условия обеспечения потоково-конвейерного способа обработки с исключением коллизий. Известные до сих пор рекомендащш по использованию ассоциативного процессора в составе МБД (Дж.Мартин, Г.Симоне и др.)не были достаточно конструктивными. Необходимым условием высокой эффективности МБД в данном случае считается правильный выбор дерева обработки запросов. Задача решается путем разработки алгоритмов специализированной операционной системы МБД для реализации предложенного дерева.
Методологический аспект связывается в работе с развитием концепции модели системы как конструктивного метода (Ю.А.Шрейдер). Основой развития является соглашение о том,что проектируемое устройство должно в той или иной степени воспроизводить определенные
свойства некоторой гипотетической системы. Задача проектирования связывается с построением конструктивного описания системы, которое допускает эффективную реализацию такого устройства.Это - одна из задач моделирования систем. Ее решением являются аппаратно-ориентированные, или схемотехнические модели.
Любая из выделенных задач рассматривается в работе как новая проблема со свойственной ей изначально неполной определенностью. Ее дополнение некоторыми постулатами или гипотезами служит целям обоснования неформально найденной модели системы.Безусловно,главное в данном случае - интуиция и опыт исследователя. Хороший неформальный метод ценен сам по себе. Но к пониманию того,насколько он адекватен решаемой задаче и каковы его потенциальные возможности, нельзя приблизиться иначе, как в процессе объяснений. В условиях неопределенности, это достигается только концептуально.
Методы исследований. Методологическая цель работы достигается путем формулировки концепции схемотехнического моделирования и ее конкретизации на множестве рассматриваемых теоретико-прикладных задач. При решении этих задач используется математический аппарат линейной алгебры, теории аналитических функций,функционального анализа и теории автоматов. В процессе исследований широко применяется натурный, вычислительный и кросс-эксперимент.
Наиболее существенные результаты и научная новизна
-
Предложена концепция схемотехнического моделирования сие- , тем как методологическая база обоснования неформально найденных методов в условиях неполной определенности. Ее отличие от известной концепции модели системы как конструктивного метода состоит в привлечении, наряду с аксиоматическим, гипотетического начала и в детализации применительно к задачам проектирования.
-
Разработана модель оператора задержки в пространствах отображающих числовых последовательностей. Эта модель отвечает введенной аксиоматике и охватывает множество представлений системы, что отличает ее от известных методов проектирования однородных линий. Развита соответствующая аксиоматическая теория. Получены необходимые аналитические зависимости. Установлены частотные и временные свойства найденных решений. Доказана их устойчивость (реализуемость) .
-
Введено понятие псевдоасинхронных последовательностных схем как возможных моделей последовательностного алфавитного оператора. Новизна этого понятия в том, что асинхронная последова-тельностная схема рассматривается как основа реализации синхрон-
ного устройства. Это создает определенные предпосылки к исключению риска сбоя. Предложена классификация таких схем. Дано теоретическое обоснование областей их применения. Разработаны соответствующие им методы синтеза и элементы абстрактной теории.
4. Сформулированы гипотезы и рабочие принципы моделирования процессора массивов для реализации операторов над массивами данных. Модели строятся в виде матричных процессоров ассоциативного типа, широкого применения либо специализированных. От известных разработок они отличаются выбором морфологической базы и более детальным учетом взаимосвязи всех компонентов модели. Предлагается подход к синтезу их операционной основы, более детерминированный в сравнении с известным. Получены оценки эффективности и разработаны рекомендации по использованию таких процессоров при решении различных задач.
Значение полученных результатов для теории
-
Расширено представление о модели системы как конструктивном методе. Использование развитого в работе методологического подхода помогает концептуально вскрыть суть явления и на этой основе показать адекватность неформально найденного метода решаемой задаче.
-
Построена аксиоматическая теория однородных искусственных линий задерики. Эта теория обобщена на случаи полиномиальных цепей, гибридных и формирующих линий. Показано направление дальнейшего развития предложенной модели.
-
Разработаны элементы теории абстрактных автоматов и до-следовательностных схем. Найдены классы автоматов и схем без риска сбоя. Определены направления прикладных исследований в этой области.
-
Сформулирован подход к синтезу операционных логико-запоминающих сред как морфологической основы матричных процессоров ассоциативного типа. Установлено место таких процессоров в ряду других высокопроизводительных систем. Показано перспективное направление исследований в области машин баз данных.
Значение для практики
I. Упрощение процедуры синтеза и повышение технологичности изготовления искусственных линий разного применения с заданным качеством переходной характеристики, в сравнении с неоднородным вариантом. Снижение необходимых "размеров" линии и повышение дости-
жимого качества, в сравнении с использованием цростейших базовых модулей.
-
Уменьшение влияния разброса задержек в элементах и расфа-зировки синхросигналов на функционирование заказных БИС. Детализация процедуры синтеза таких схем. Достижимость автоматизации вы полнения этой процедуры в диалоговом режиме непосредственно по ис ходному заданию.
-
Повышение эффективности информационно-вычислительных систем при решении множества задач проблемной ориентации, связанных с обработкой массивов данных. Детерминизация процедуры и повышение достоверности выбора необходимых архитектурных, структурных, функциональных и др. решений для матричных процессоров ассоциативного типа.
Реализация -результатов. По результатам исследований под руководством автора выполнен проект матричного процессора ассоциативного типа производительностью 10 опер/с и разработана кросс-система для такого процессора. Эти разработки внедрены на предприятии п/я A-382I и в ОКБ МЖ Института кибернетики АН УССР. Отдельные результаты исследований использованы на предприятии п/я Ы-5769, Казанском заводе ЭВМ и в учебном процессе КГТУ им. А.Н.Туполева.
Апробация работы. Основные положения диссертации докладывались и обсуждались .на Отчётных научно-технических конференциях Кй: им.А.Н.Туполева (Казань, 1965 - 1992), XXI Всесоюзной научной сес сии НТОРиЭ им.А.С.Попова (Москва, 1965), расширенном заседании ка федры ЭВМ КАИ им.А.Н.Туполева (Казань, 1968), семинаре"Импульсные устройства" ВВИОЛКА им. проф. Н.Е.ЇЇуковского (Москва, 1968), семинаре "Переходные процессы в элементах радиоустройств" ЛВИМУ им. адм. С.О.Макарова (Ленинград, 1968), заседании секции теории линейных электрических цепей НТОРиЭ им. А.С.Попова (Ленинград, 1969), заседании спец. совета ЛВИМУ км. адм.С.О.Макарова (Ленинград, 1971), семинаре "Цифровые структуры БИС" КАИ ш.А.Н.Туполева (Казань, 1974 - 1989), рабочих совещаниях СКВ КЗЭВМ (Казань, І974-І98І), семинаре "Программируемые логические массивы и матрицы" Института математики СОАН СССР (Новосибирск, 1976 - 1979),семинаре "Аппаратная поддержка функций компиляции" ВЦ СОАН СССР(Новосибирск, 1978), Всесоюзном совещании "Проблемы создания и использования высокопроизводительных информационно-вычислительных машин" (Кишинев, 1979), областном семинаре "Математические метода в задачах исследования сложных систем и управления (Пенза, 1981, 1984), заседаниях секции НТО НЩЭВТ (Москва, 1981 - 1988), засе-
даниях секции НТС НИИ КВАНТ (Москва, 1981 - 1984), заседаниях секции НТО СКВ ММС Института кибернетики АН УССР'(Киев, 1985-1988), заседании рабочей группы при ГКВТИ СССР по подготовке комплексной программы работ по созданию машин баз данных и баз знаний (Москва, 1987), рабочих обсуждениях в отделе 100 Института кибернетики АН УССР (Киев, 1989), расширенном заседании кафедры ЭВМ КГТУ им.А.Н.Туполева (Казань, 1993), семинаре "Математическое и архитектурное обеспечение параллельных вычислений" ВЦ СОРАН (Новосибирск, 1993), семинаре "Теория автоматов и ее приложения" Научного совета по кибернетике АН Украины (Киев, 1994), научном семинаре кафедры АВТ СПБГТУ (С.-Петербург, 1994).
Публикации. По теме диссертации опубликовано 45 работ, включая научно-технические отчеты. Из них 12 работ ' опубликованы в центральных журналах, 2 работы изданы в КГТУ им.А.Н.Туполева в качестве учебных пособий.
Научные результаты, выносимые на защиту
-
Концепция схемотехнического моделирования (развитие концепции модели системы как конструктивного метода).
-
Аксиоматика однородных искусственных линий.
-
Абстрактная модель модуля задержки.
-
Решения прикладных задач моделирования оператора задержки.
-
Абстрактная модель последовательностного алфавитного оператора (развитие подхода к синтезу автомата по неформальному заданию).
-
Элементы теории псевдоасинхронных последовательностных схем.
-
Абстрактная модель оператора над массивами данных (подход к синтезу операционных логико-запоминающих сред). _
-
Решение задачи моделирования двумерного ассоциативного оператора.
-
Исходные гипотезы и рабочие принципы моделирования процессора массивов.
-
Оценка эффективности использования ассоциативного матричного процессора широкого применения.
-
Решение задачи внешнего моделирования машины баз данных распределенной архитектуры с применением сортирующего процессора.
Достоверность. Правомерность сформулированных в работе постулатов и гипотез подтверадена как оригинальными исследованиями автора, так и исследованиями других авторов. Сами конструктивные методы находятся неформально. Однако их разработка ведется в стро-
гом соответствии с принятыми посылками на основе развитого математического аппарата с-обоснованным привлечением элементов эвристики. Достоверность получаемых при этом результатов определяется правомерностью базовых положений, подтверждается строгими до-т казательствами, экспериментально, программным моделированием, сопоставлением с известными результатами.
Квалификационный признак. В диссертации решен ряд теоретико-прикладных проблем в области моделирования итеративных систем обработки информации. Совокупность разработанных при этом теоретических положений можно квалифицировать как новое научное достижение в развитии перспективного направления ИВТ "Однородные структуры" .
Структура и объем работы. Работа состоит из введения, трех глав, списка литературы, заключения и приложения. Общий объем работы 418 стр. Основной текст занимает 295 страниц, 60 рисунков, 33 таблицы. Список литературы включает 297 наименований.
