Browse Prior Art Database

Fast General-Purpose State Machine

IP.com Disclosure Number: IPCOM000036318D
Original Publication Date: 1989-Sep-01
Included in the Prior Art Database: 2005-Jan-28
Document File: 4 page(s) / 17K

Publishing Venue

IBM

Related People

Taylor, JL: AUTHOR

Abstract

This disclosure describes a scheme which simplifies channel interface state rules and translates them into tabular form. All information is inferred only from the rules, in particular, tag polarity, significance and priority. Tags are all handled and tested in parallel by table look-up suitable for RISC architecture. A fast compact solution resulted. Alternatives would require either special hardware such as PLA or more code space.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 42% of the total text.

Page 1 of 4

Fast General-Purpose State Machine

This disclosure describes a scheme which simplifies channel interface state rules and translates them into tabular form. All information is inferred only from the rules, in particular, tag polarity, significance and priority. Tags are all handled and tested in parallel by table look-up suitable for RISC architecture. A fast compact solution resulted. Alternatives would require either special hardware such as PLA or more code space.

The object of the scheme is to interface a transputer network to an IBM S/370 channel by means of a sequencer for converting bit level tag traffic on the S/370 channel to/from more meaningful high level transactions such as initial selection and data transfer sequences. The channel sequencer needs to be fast, mathematically complete (i.e., without blind alleys, runs non-stop), easily maintained and changed, and compact.

Tag out lines from the S/370 CPU that must be sampled simultaneously and in parallel within the same byte location are: Address out, Command out, Service out, Data out, Operational out, Hold out, Select out and Suppress out. The task is to build a fast state machine, conforming to these requirements, to process these tags as input and to respond with an appropriate sequence of states and actions. A conventional solution is to write a large amount of inline code that performs tests on individual bits and responds, as appropriate. An example given in the appendix fails to meet any of the listed objectives. Notably, it will run slowly as it tests the tag bits singly. The highest priority test (operational out low) will very rarely be satisfied, but wasteful testing at highest priority in every state occurs. Structure

A state machine is completely described by an ordered set of rules. A rule is an ordered quartet (current.state, tag.test, action, new.state). A typical example of a rule is (State a, tag.x.low, action, State b).

The rules are tested in strict order, and the first one whose input conditions are satisfied will be executed. This produces a new state, and testing starts again from the top of the rule list. Without loss of generality, rules are restricted to having a tag test which is either "A simple tag test on one tag" or "Always true" (the else condition), because a compound tag test can be broken down into a sequence of simple tag tests, as shown below.

Another technique is to test the falsehood of the compound test with simultaneous simple tests. (State a, tag.x.low & tag.y.high, action, State c)

(State a, true , else.action, State d)

is equivalent to

(State a, tag.x.low, NOP, State b)

(State b, tag.y.high, action, State c) * x low, y

high *

(State a, true , else.action, State d)

(State b, true , else.action, State d)

is equivalent to

(State a, tag.x.high, else.action, State d)

1

Page 2 of 4

(State a, tag.y.low , else.action, State d)

(State a, true, , action, State c)

Furthermore, without loss of generality, rules are constrained for any st...