How to represent & document pipelined FSM?

Newsletter · Original Contribution Joined: Dec 08, 2003 Posts: 1107

(Originally from Issue 3.10, Item 9.0)

From: Adam Krolnik

I am looking for techniques to present a pipelined FSM design in a
document. An unpipelined FSM is the common (degenerate) case where the
FSM controls the aspects of the local machine. A pipelined FSM can
handle multiple operations that must operate in the same manner
(sequence) but separated in time.

The actual design was built as pipelined logic. But this style is very
difficult to review/analyze/etc. Has anyone been able to create a
representation and a reasonable (FSM like) coding style to support
this kind of a design?

Newsletter · Original Contribution Joined: Dec 08, 2003 Posts: 1107

(Originally from Issue 3.11, Item 4.0)

From: Illan Glasner

How about using excel spread-sheet. here an example of pipeline using
CAM and two conscutive ZBT.

0 0
1 0 search 0
2 1
3 1 search 1 AGGP
4 2
5 2 search 2
6 3 rbus has result 0
7 3 search 3 rbus has result 0
8 4 rbus has result 1
9 4 rbus has result 1 DLUT,0
10 5 rbus has result 2
11 5 rbus has result 2 NLUT,0
12 6 rbus has result 3 NLUT,1
13 6 rbus has result 3
14 7 rbus_reg3 has result0 GLUT
15 7 rbus_reg3 has result0 PLCR
...

Basicly each line is the fast clock than another colomn might show a
slower clock or the sequence and then each device at that particular
sequence what it get or send out etc.

Newsletter · Original Contribution Joined: Dec 08, 2003 Posts: 1107

(Originally from Issue 3.12, Item 3.0)

From: Thomas C. Jones

The classic text "Computer Architecture A Quantitative Approach" by
Hennessy and Patterson shows a pretty standard way of representing
pipelines and pipeline behavior that I have also seen used in
industry. Repeated here, without permission, is an example of their
pipelined DLX architecture with 5 stages (Fig 6.1, pg 259 of my
edition):

1) IF - instruction fetch
2) ID - instruction decode
3) EX - execution (effective address calc)
4) MEM - memory access
5) WB - write back

In this example time flows left to right. A new instruction enters
the pipe each cycle (best viewed in courier or other fixed font)

Clock
Inst 1 2 3 4 5 6 7 8 9
i IF ID EX MEM WB
i+1 IF ID EX MEM WB
i+2 IF ID EX MEM WB
i+3 IF ID EX MEM WB
i+4 IF ID EX MEM WB
^
|
At this point the pipe is full.

There are further examples showing hazards, etc. where specific
instruction types (ADD, MOV, etc) interact and hazards must be
detected and corrected by bypass or pipeline stall.

An alternative is to transpose it such that time flows from top to
bottom. It may work better depending on your paper size and
orientation.

Anyway, get the book (ISBN 1-55860-069-8) - it's worth whatever
they're charging for it these days.