DocumentCode :
1508157
Title :
Finite state machine has unlimited concurrency
Author :
Lin, Horng-Dar ; Messerschmitt, David G.
Author_Institution :
Dept. of Electr. Eng. & Comput. Sci., California Univ., Berkeley, CA, USA
Volume :
38
Issue :
5
fYear :
1991
fDate :
5/1/1991 12:00:00 AM
Firstpage :
465
Lastpage :
475
Abstract :
General methods for introducing concurrency, by which the throughput of finite-state machines (FSM) can be improved at the expense of latency, are described. The methods are applicable to software and hardware implementation using parallelism or pipelining and demonstrate that there is no theoretical limit to concurrency in a discrete-time finite-state machine. The methods can arbitrarily improve the iteration bound of discrete-time FSMs with low hardware overhead. They are efficient when the state size is finite and moderate, as in controllers, encoders, source decoders, etc. When the state size is large and the recurrence is not a closed-form function of specific classes, the methods cannot be applied directly. Another limitation is the latency induced by the block methods. In most cases, this is not a problem because the overall cost and throughput rather than latency are at stake
Keywords :
finite automata; parallel processing; pipeline processing; block methods; concurrency; discrete-time; finite-state machines; iteration bound; latency; throughput improvement; Application software; Automata; Concurrent computing; Costs; Delay; Hardware; Magnetic heads; Parallel processing; Pipeline processing; Throughput;
fLanguage :
English
Journal_Title :
Circuits and Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
0098-4094
Type :
jour
DOI :
10.1109/31.76483
Filename :
76483
Link To Document :
بازگشت