Abstract -- For a given control program different control unit (CU) architectures can result in very different sizes of the implementation. In this paper an algorithm will be presented that exploits common subsequences in a state transition graph by mapping onto one of four different target architecture, thereby potentially reducing the CU area.

I. Introduction

Automatic synthesis of datapath architectures from a program description is possible today and a whole range of solutions can be generated depending on performance constraints. For control unit (CU) synthesis there is no corresponding architectural synthesis. The general approach for CU synthesis has been to generate and optimize logic for given, fixed control architectures. For a given control program different control architectures can, however, result in very different size and speed of the implementation. Therefore, in the context of silicon compilation, CU synthesis should be able to automatically map a single CU program onto a number of architectures and eventually automatically choose an architecture, optimal for the particular control program at hand and driven by performance constraints.

In this paper an algorithm will be presented that finds common subsequences in a STG (state transition graph). The algorithm exploits these subsequences by mapping the STG onto four different CU architectures. These architectures are aimed at reducing CU area by exploiting such sequences. It will be shown that the presented algorithm thereby significantly can reduce the area of a CU.

II. Target architectures

In many CU programs it is possible to find subsequences that occur in several places in the STG. Two sequences are identical iff they produce the same output sequences for all possible input sequences. In figure 1 the state sequence a1...d1 and a2...d2 are identical.

The basic idea of a number of architectures is to somehow reuse these state sequences so that only one copy is needed in the implementation, thereby reducing the area of the CU.

STACK architecture

Subroutines in microprogrammed CUs is one example of how common subsequences can be reused. The subroutine calling mechanism can be implemented in many ways. Saving the calling state on a stack is one possibility. The traditional FSM built with a PLA and D-flipflops can easily be extended with a subroutine mechanism by replacing the state registers with a stack of state registers (figure 2).

The return operation in this subroutine mechanism differs from the usual microprocessor type of subroutines in that it returns the FSM to the calling state, not the state after the calling state. Traversing the STG in figure 2 would therefore lead to the sequence

Figure 1: Identical sequences found in one STG.

2 a2

8 9

3b 2 c2 d2

a1 b1 c1 d1

-/1 -/2 -/3 -/4 -/5 -/6

-/7 -/2 -/3 -/4 -/5 -/8

Figure 2: FSM with subroutine mechanism.

C

d

q+
q

push

pop

1 2 3

a

b c

d

call return

An Algorithm for Control Unit Architecture Optimization Exploiting Common

Subsequences in State Transition Graphs

Kenny Ranerup

Department of Computer Engineering

Lund University

P.O. Box 118, S-221 00 Lund, Sweden

email: [email protected]