 |
 |
 |
|
|
INTRODUCTION
Sequential optimization techniques are needed at several points within a digital system design flow. Earlier in the process, the sequential circuits are modeled using the formalism of finite state machines (FSMs). Such state-based models express sets of sequential functions, mapping a sequence of inputs to a sequence of outputs. The FSMs are either specified directly by the designer using a hardware description language, or realized via high-level synthesis tools from a more abstract description. Given a behavioral algorithmic specification and a library of functional units, high level synthesis constructs a data path by scheduling operations in the algorithm onto specific time steps and binds them onto appropriate functional units. An FSM (controller) that controls the data path is then automatically constructed.
We should emphasize the
fact that the machine decomposition is the organic part of synthesis process.
A large FSM must be decomposed into ones for more efficient implementations.
The task of decomposition has been a classic problem of discrete system theory
for many years. The decomposition of FSM is a topic that waxes and wanes in
importance. The fundamental works were done in the 1960s, became less interesting
during the era of VLSI, and is becoming more important again with pervasive
use of programmable logic and low power applications in digital design. A large
hardware behavioral description is decomposed into several smaller ones. One
goal is to make the synthesis problem more tractable by providing smaller sub-problems
that can be solved efficiently. Another goal is to create descriptions that
can be synthesized into a structure that meets the design constraints. In the
past, the synthesis focused on quality measures based on area and performance.
The continuing decrease in feature size and increase in chip density in recent
years have given rise to consider decomposition theory for low power as new
dimension of the design process.
Various techniques of FSM decomposition fall broadly into next categories: multiplicative
decomposition, wherein the graph of the FSM is embedded into a product of smaller
graphs, and additive decomposition, wherein the graph of the FSM is partitioned
into node disjoint subsets.
Let’s we have an FSM which need to decompose in a network. The individual
(component) machines that make up the overall realization are referred to as
sub-machines. The prototype machine corresponds to the machine that was used
to define the terminal behavior to be realized. The machine that results as
a consequence of the decomposition is called the decomposed machine. Informally,
the essence of the decomposition task could be described as follows. Given a
prototype FSM description of a desired terminal behavior, the decomposition
problem is to find sub-FSMs which, when interconnected in a prescribed way,
will display that terminal behavior.
We distinguish three methods of decomposition.
In the first
method, each sub-machine corresponds to a partition on the set of states
(a partition 
on the set
of states, S, in a machine is a collection of disjoint subsets of states whose
set union is S). All the states belonging to a single block in a submachine
are given the same code in that submachine. Therefore, there is no way of distinguishing
between two states belonging to a single block in a submachine without recourse
to information from other sub-machines. A block of states in a partition effectively
corresponds to a state in the submachine associated with that partition. The
functionality of the prototype machine is maintained in the decomposed machine
if the partitions associated with the decomposition are such that their product
is the zero-partition on S (every block of partition consists exactly of one
state).
The idea of the second method is to introduce additional “idle” states into the sub FSMs. The network of FSMs consists of components working alternatively in time, i.e. all components except one are suspended in one of extra state (the “wait” state). The network of interacting sub-FSMs corresponds to a given partition on the set of states of prototype FSM. The number of sub-FSM in the network is equal to the number of blocks and the number of states of sub-FSM is equal to the number of states in corresponding block of given partition plus 1 (wait state).
The third method of decomposition proceeds from a given cover (not a partition) on the set of states of prototype FSM. Each sub-machine corresponds to a subset of the set of states of prototype FSM. This method is generalization of the previous one (more than of machines could be active executing a computation at any given time while the other sub-FSMs are idle).
SELECTED PUBLICATIONS:
WARNING: This page contains links to PDF files of articles that may be covered by copyright. You may browse the articles at your convenience. (in the same spirit as you may read a journal or a proceeding article in a public library). Retrieving, copying, or distributing these files, however, may violate the copyright protection law. We recommend that the user abides international law in accessing this directory.
TEXTBOOKS:
 |
 |
Last update: 3 August, 2004