On the complexity of parallelizing sequential circuits using the parallel-prefix method

Abstract

The parallel-prefix method uses a tree of identical processing nodes to calculate in parallel, the state and output response of a finite-state machine (FSM) to a finite-length input sequence. Traditionally, each computing node in the tree has been required to perform multiplication of binary matrices. In this paper, we show that under appropriate modifications of the input-output mappings at the leaf nodes of the tree, the operation of each node can be reduced to the operation of the unique finite semigroup that is associated with the given FSM. In terms of this view, previous parallel-prefix approaches for sequential circuits have treated the worst case scenario, in which the order of the associated semigroup is exponential in the number of states of the given FSM.