Cтраница 1
Параллельная декомпозиция соответствует разложению абстрактного автомата в произведение или сумму двух или большего числа абстрактных автоматов, каждый из которых проще, чем исходный автомат. В зависимости от разложения автомата по операции умножения или суммирования можно говорить о параллельной одновременной и о параллельной неодновременной ( no - очередной ] декомпозиции абстрактных автоматов. [1]
Задача параллельной декомпозиции автомата может быть сведена к задаче многокомпонентной раскраски графов. [2]
Задача параллельной декомпозиции автомата, как правило, сводится к разложению графа переходов исходного автомата в частичное декартово произведение более простых по числу вершин графов переходов функционально несвязных друг с другом подавтоматов. [3]
Для построения полной параллельной декомпозиции автомата рассмотрим частичные графы переходов Gr ( S ( U, X, уг) У ( г1 - нР ( Г)), взаимно однозначно соответствующие выходным переменным, образующим вектор Y. Множества вершин и дуг графа совпадают соответственно с множествами вершин и дуг исходного графа переходов автомата, а каждая дуга взвешена входным вектором X и выходной переменной уг. [4]
При этом решается задача поиска параллельной декомпозиции автомата. [5]
Алгоритмы разложения автоматов решают проблему последовательной и параллельной декомпозиции автоматов, а общая декомпозиция автоматов приводит к декомпозиционному методу синтеза, который основные трудности структурного синтеза, связанные с кодированием состояний автомата, решает на абстрактном уровне. [6]
Знание структуры запрещенных фигур многокомпонентной раскраски графов позволяет без перебора всех эквивалентных вариантов строить параллельную декомпозицию автомата за счет отбрасывания заведомо неприемлемых решений. [7]
В этих условиях для обеспечения максимального быстродействия и надежности проектируемого управляющего устройства, реализуемого на базе микропроцессорных наборов, целесообразно строить полную параллельную декомпозицию автомата. Схема микропроцессорной реализации автомата, соответствующая полной параллельной декомпозиции, приведена на рис. 5.4, а. В результате каждой компоненте разложения соответствует микропроцессорная система ( МПС), а устройство управления в целом реализуется в виде микропроцессорной сети. [8]
Поскольку в результате разложения каждому внутреннему состоянию исходного графа переходов соответствует вектор, каждая компонента которого определяется состоянием приписанного ей подавтомата, построение параллельной декомпозиции автомата сводится к многокомпонентной раскраске графа сцепления, при которой смежным вершинам сопоставляются спектры красок, отличные друг от друга в каждой компоненте. Это объясняется тем, что когда в какой-то из компонент спектры сцепленных состояний совпадают, то при подаче на вход автомата вектора, по которому они сцеплены, в общем случае будет нарушение детерминированности перехода в подавтомате, соответствующем этой компоненте. [9]
Для получения условий функциональной несвязности элементов памяти автомата, реализованного в многозначном структурном алфавите, может использоваться тот же аппарат, что и при поиске параллельной декомпозиции автомата. [10]
Покажем теперь, что любой абстрактный автомат, разложимый по операции умножения X, разложим также и по операции умножения, иначе говоря, парал лельная декомпозиция автоматов с разделением входов является частным случаем параллельной декомпозиции автоматов с общим входом. [11]
Рассмотренный метод также позволяет эффективно использовать возможности стандартных БИС при схемной реализации управляющих устройств. При использовании программируемых логических матриц параллельная декомпозиция автомата на функционально несвязные подавтоматы с заданным числом состояний позволяет путем формирования сигналов управления памятью каждого автомата непосредственно на реализующей этот подавтомат микросхеме минимизировать число БИС. [12]
В этих условиях для обеспечения максимального быстродействия и надежности проектируемого управляющего устройства, реализуемого на базе микропроцессорных наборов, целесообразно строить полную параллельную декомпозицию автомата. Схема микропроцессорной реализации автомата, соответствующая полной параллельной декомпозиции, приведена на рис. 5.4, а. В результате каждой компоненте разложения соответствует микропроцессорная система ( МПС), а устройство управления в целом реализуется в виде микропроцессорной сети. [13]
Там, где задача раскраски усложнена дополнительными условиями одноцветности вершин, эффективным может оказаться и подход, предполагающий нахождение наибольшего пустого или полного подграфа, а затем группирование около вершин, вошедших в этот подграф, остальных вершин заданного графа. С помощью этого подхода, как показано в [26], можно решить такие задачи, как минимизация длины кода состояний асинхронного автомата, сжатие таблицы переходов автомата ( по строкам и столбцам), параллельная декомпозиция автомата, упрощение системы булевых функций, описывающих асинхронный автомат. Точно так же можно решать и все остальные задачи, перечисленные выше. Из рассмотренных здесь подходов к решению задач логического проектирования данный подход единственно пригоден для решения таких задач абстрактного синтеза автоматов, как минимизация числа состояний синхронного автомата и его декомпозиция. [14]
В ряде случаев порядок выделенного подграфа ( пустого или полного), являющегося некоторым промежуточным результатом решения любой из названных задач, может служить оценкой сложности ожидаемого результата. По величине оценки можно судить о целесообразности получения окончательного решения соответствующей оптимизационной задачи, что важно при диалоговом режиме выполнения алгоритма. Например, в случае параллельной декомпозиции автомата, которая применяется с целью сокращения размерности задач синтеза, порядок наибольшего пустого подграфа есть оценка числа состояний наиболее сложной компоненты в получаемой сети автоматов. Если эта величина незначительно отличается от числа состояний заданного автомата, то нет смысла решать задачу параллельной декомпозиции, так как указанная цель не будет достигнута. [15]