Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 48
Текст из файла (страница 48)
Проиллюстрируем зто на следующем примере. Пусть нмеется устройство с входным каналом х, каналом обратной связи г н выходным каневом р, реавкзуюшее отобраненне Хо~ -+ о У, заданное в виде табднцы (табп. 4.1), Т а 6 пк к а 4.1 Опредевнм выходную последовательность, если входная последоватедьность имеет внд 101001 н начавьное аначенне вектора л т равно О. В начальный момент времени вектор Хат, равный 10, опредепяет о У = 01 (третья строка таблицы). Череа промокуток времени, равный т, условие Хо+ = 00 опредеднт о У = 11 (первая строка) и т. д. Запишем окредеденне выходной последоватевьностн в виде табл.
4.2. х, е Следовательно, 101001 — — + 110100. Прн уст = 1 согласно заданному автоматному етобраненню входная последоватедьность 101001 преобразуется в выходную последовательность 010100. Таким образом, автоматное отображение ХЯ+ -+ 2 У однозначно определяет выходную последовательность (У;) по заданной б 4.2. Основные этапы проектирования автоматов 267 входной последовательности (Х;) и начальному внутреннему состоянию Ко+: (Х;) — '+ (Щ. Одной из основных характеристик автомата является объем его памяти.
Число внутренних состояний автомата называется объемом помят»и автомата. Как известно, преобразование информации является результатом выполнения некоторого алгоритма, лри зтом операииокныб автомат» реализует шаги алгоритма, а управляюи4иб автомат — порядок выполнения шагов. Операционный и управляющий автоматы различаются не только своими назначениями, но и объемами памяти.
В операционном автомате происходит преобразование информации, которая задана в виде некоторого множества чисел, записанных в регистрах. Практически объем памяти операционного автомата бесконечен. Так, например, блок регистров современной ЭВМ, входящий в операционной автомат и состоящий из 22 16-разрядных двоичных регистров, имеет объем памяти 2збт > 10100 бит. Объем памяти управляющих автоматов обычно составляет от нескольких десятков до нескольких десятков тысяч бит, т.
е. является небольшим по сравнению с объемом памяти операционных автоматов. Рассмотрим взаимодействие операционного и управляющего автоматов (рис. 4.6). На вход операционного автомата (канал 1) поступает преобразуемая информация; с выхода операционного ав- томата (канал Я) снимаются результаты преобразований; по каналу 8 поступают управляющие воздействия, соответствующие реализуемому алгоритму; по каналу 4 на вход управляющего автомата поступают признаки, характеризующие преобразуемую информацию; по каналу 5 — сигнал, определяющий выполняемое преобразование и его начало, "по каналу 6 — сигнал окончания операции. Каналы 1 и У называются ин(рормаиионными, каналы 3-6 — управляющими. Рассмотрим, например, выполнение операции сложения в арифметическом устройстве (АУ) ЭВМ.
В данном случае операционным автоматом является арифметическое устройство, т. е. регистры, сумматор и связи между ними, а управляющим автоматом — устройство управления АУ. При выполнении алгоритма сложения по каналу 1 пз запоминающего устройства (ЗУ) машины в соответствующие регистры 268 Гл.4. Теория формольныг грамматик и евтомотое 14.2.
Основные эталы лроектированил оел1оматое 269 АУ записываются первое и второе слагаемые; по каналу 5 из центрального устройства управления (ЦУУ) машины поступает код операции (сложение); по каналу Я из управляющего устройства АУ согласно алгоритму сложения посылаются управляющие сигналы: сдвиг регистров, возбуждение соответствующих шин в сумматоре, зались суммы в регистр результата и другие сигналы. По каналу 4' поступают признаки (например, содержание знаковых разрядов в сумматоре, используемое для обнаружения нарушения нормализации), определяющие ход дальнейшего управления.
По каналу 6 в ЦУУ передается сигнал окончания выполнения операции. По каналу 2 в ЗУ посылается результат операции. ЭВМ вЂ” сложный преобразователь информации, и ее целесообразно рассматривать, следуя В.М. Глушкову, как комлозицию лар автомал1ог, каждая из которых состоит из операционного и управляющего автоматов. При этом каждое устройство ЭВМ (ввода, вывода, ЗУ, ЦУУ) представляется аналогично арифметическому устройству в виде пары или нескольких пар таких автоматов. Такое представление ЭВМ диктуется не только удобством анализа и синтеза ЭВМ, но и является естественным развитием 'структуры современных ЭВМ. В настоящее время как один из методов увеличения производительности ЭВМ используется мультнпрограммный режим, что, в частности, уменьшает задержки, вызываемые низкой скоростью внешних устройств и несоответствием скоростей работы внешних и арифметических устройств.
Для реализации мультипрограммного режима ЭВМ необходима некоторая "самостоятельность" отдельных устройств, т. е. возможность хранения, преобразования информации н управления этим преобразованием внутри устройства; другими словами, необходимо, чтобы каждое устройство представляло собой композицию операционного и управляющего автоматов. В настоящее время на основе нейротранспьютерных технологий, создаются мощные вычислительные сети; примером таких сетей являются Соппппп1саг1оп МасЫпеа (СМ-1, СМ-2), имеющие кластерно-гиперкубовую архитектуру. Транспьютерная сеть СМ-1 состоит из 65536 (2ге) транспьютеров, СМ-2 — нз 4194304 (2тт) транспьютеров.
В кластерах реализуются связи "каждый с каждым", каждый кластер соответствует вершине гиперкуба. Геометрически сеть СМ-1 представляет собой куб, длина ребра которого равна 120 сы, сеть СМ-2 — куб с ребром 480 см. При проектировании ЭВМ можно выделить три основных этапа: системный, логический и технический. На этапе системного лроектироганил строится композиция пар автоматов — операционных н управляющих (общая блок-схема ЭВМ); определяются необходимый объем памяти автоматов, их взаимодействие на основе выбора системы команд, внешние и внутренние языки машины и т. д.
Исходной информацией на си- стемном этапе является совокупность классов задач, для решения которых предназначена проектируемая машина, и ее параметров (быстродействия, стоимости, габаритных размеров и т. д.). Рассматриваемые на этапе системного проектирования автоматы имеют большой объем памяти, превышающий, как уже отмечалось, 10мю бит. Поэтому в настоящее время задачи системного этапа решаются с помощью программного моделирования. Процесс решения задачи системного этапа методом программного моделирования обычно состоит из следующих шагов: а) составление математической модели, отражающей важные свойства моделируемого устройства или машины в целом; 6) построение моделирующего алгоритма, запись его на некотором языке, предназначенном для описания моделей ЭВМ; в) реализация моделирующего алгоритма на ЭВМ; г) анализ результатов н корректировка модели устройства или машины.
Программное моделирование позволяет определить основные характеристики проектируемой машины, "узкие места" ее структуры. На этапе логического проектирования ЭВМ синтезируются непосредственно логические (функциональные) схемы всех блоков машины. Исходной информацией для этого этапа являются алгоритмы функционирования блоков. На этапе технического лроектированил на основе логических схем строятся принципиальные монтажные схемы и готовится техническая документация для производства ЭВМ. Логическое проектирование заключается в синтезе как операционных, так и управляющих автоматов.
В силу практически бесконечного объема памяти операционных автоматов последние в настоящее время синтезируются с помощью программного моделирования. И если для формализованного синтеза операционных автоматов необходимо развитие теории бесконечных автоматов, то для формализации синтеза управляющих автоматов возможно применение теории конечных автоматов. Согласно этой теории при проектировании управляющих автоматов будем различать два основных этапа: построения автоматного оператора и структурного синтеза автомата. 1. Этап построения автоматного оператора.
На этом этапе производится построение сисл1емы выгодныг функций У = у(Х, Я+) и системы функций возбуждения о = у(Х, У+). Автоматное отображение, записанное в виде системы выходных функций и функций возбуждения, будем называть автоматным олератором. Этап построения автоматного оператора в свою очередь состоит из трех подэтапов: алгоритмического, абстрактного и этапа кодирования (размешения) внутренних состояний автомата. 271 270 Гл.4. Теория формальнмг грамматик и аетоматое 14.3. Алгоритмический этак лроектироеания На этапе алгоритмического проектирования заданный оператор А оформляется в виде алгоритма исходя из поставленных требований (простоты выполнения операций, быстродействия, максимального уменьшения аппаратурных затрат и др.).
Поиск оптимального алгоритма по заданному оператору А можно представить в виде дерева, каждая висячая вершина которого соответствует определенному алгоритму, т. е. определенной композиции операционного и управляющего автоматов. Для поиска оптимального алгоритма необходим перебор всех висячих вершин, число которых не известна и определяется степенью развития рассматриваемых преобразований.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
