BDSYN Users' Manual
Version 1.1
Russell B. Segal
University of California
Berkeley
May 22, 1987
Sep 30, 1994 (html)
Tables and Figures
Table 1: Bdsyn Reserved Words
Table 2: Keywords Ignored by Bdsyn
Figure 1: Traffic Light Controller
Figure 2: Count1
Figure 3: Count2
Figure 4: Count3
Figure 5: Register file decoder
1 Introduction
Bdsyn is a hardware description translator. It takes as
input a textual description of a block of combinational
logic and produces a collection of logic functions which
implement the described function. Bdsyn was written
to be a front end to the Berkeley Synthesis System.
Work on bdsyn was begun in the spring of 1986 as a
class project for Berkeley's synthesis class. For the
synthesis class, we were given permission to use Digital
Equipment Corporation's proprietary multi-level simulator
decsim. The functional simulation language bds is used
for high level simulation in decsim. We have chosen to
use a subset of the bds language as the input language
to bdsyn. The output of bdsyn is a multiple-level logic
representation of the described function. The output
created is in blif (Berkeley Logic Interchange Format).
This output is suitable input for mis which is the
multiple level logic minimizer in the Berkeley Synthesis
System.
1.1 What Bdsyn Is
Bdsyn is a tool for quickly describing and implementing
combinational logic. It allows the user to describe a
circuit function and produce an implementation of that
circuit automatically. Bdsyn's output is given in a
"multiple-level" format. This means that bdsyn is capable
of translating many types of logic configurations that
would be impractical to represent in a two-level pla
form. Bdsyn supports many high-level language constructs:
subroutines, if--then--else, select, constant bounded for
loops, multiple assignment to variable, and multiple
returns from a single routine. In addition, bdsyn
supports complex operators such as addition, and shifts by
a variable amount. (Note that complex operators may imply
a large number of gates.)
When bdsyn is used in conjunction with mis, it can be
used to describe logic in standard cell, pla, or a more
complicated module generated form.
1.2 What Bdsyn Is Not
It is very important to keep in mind that bdsyn can be
used for describing combinational logic blocks only. We
define combinational logic to be any block of logic which
does not use system clocks or signal latching of any kind.
Combinational logic does not hold state information. In
particular, describing a finite state machine in bdsyn
requires the logic designer (or a program) to add external
latches to the described combinational logic block that
hold the current state of the machine.
The limitation of describing only combinational logic
is common to pla description programs as well as bdsyn.
(Although there may be provisions for automatically adding
the required external latches.) The reason we find it
necessary to describe this limitation in such detail here,
however, is that some of the bdsyn constructs (e.g. for
loops and multiple assignment) appear very sequential in
nature. In reality, they are merely interpreted as a
short hand for describing parallel structure. There are
many examples of the use of sequential-like descriptions
in the last section of this guide.
2 Using Bdsyn
2.1 Describing Logic in Bdsyn
Bdsyn descriptions are very similar to standard procedural
programming languages (Pascal, C, etc.) Describing logic
in bdsyn amounts to writing a program that accomplishes
the desired function. Each flow-of-control structure and
operation corresponds roughly to a small block of logic.
Each variable corresponds to "bit vector," which is a
group of single bit signals in the hardware.
At the top of the bdsyn description it is necessary to
define input and output "ports." In a programming point
of view, these ports can be viewed as external variable
declarations. In a hardware point of view, these ports
represent primary input and outputs of the combinational
logic block. Once the ports are declared, the logic
designer should define a set of values for the input ports
for which he wishes the hardware to operate. If he
then writes a program that will generate desired output
values for each of the interesting input combinations,
this constitutes a legal description.
To say it in a different way, suppose a bdsyn "program"
has been written. Bdsyn will create logic that will act
in an identical manner to that program. If a set of
inputs were to be introduced to the bdsyn program and
the program were executed (run in a software sense), a
particular set of outputs would be generated. If these
same inputs were introduced to the combinational logic
block created by bdsyn, the same set of outputs would
result.
2.2 Running Bdsyn
Once a hardware description has been written, it can
be converted to logic by running bdsyn. The input
description is read from the file given on the command
line. The blif output is returned to standard output.
There are several command line options for bdsyn which are
outlined in the bdsyn manual page. Two of the options,
however, will be discussed here.
The -b option tells bdsyn not to do its cleanup
evaluation. This cleanup evaluation process in
bdsyn eliminates redundant and unnecessary logic.
Unfortunately, it may also have the undesired effect
of eliminating user specified intermediate variables that
bdsyn considers unimportant. The -b makes sure that the
variable are preserved, at the price of extra logic.
[The extra logic could easily be reduced by MIS at a later
time]
The -c option is followed by a number which tells
bdsyn how much "collapsing" of logic that it should do.
Collapsing is done in order to decrease the amount of
output which bdsyn creates. Although quite rare, it
is possible to create an input description which causes
bdsyn to collapse too much logic and run for inordinate
amounts of time. The option -c1 will limit the amount of
collapsing that is done, and will alleviate the problem.
Bdsyn uses mis do to logic collapsing for it. The actual
communication with mis is accomplished through the use of
unix pipes. On non-unix systems or on a system where mis
is not available, the option -c0 should be used to turn
off collapsing altogether.
2.3 What is New in Version 1.1
There are two main changes in bdsyn since version 1.0
that users may notice. The first change is that the
intermediate variable names created by bdsyn are shorter.
Each variable is followed by two numbers. The first
number is the block in the description in which the
variable is set. The second number represents how many
times the variable has been revised in the block.
The second change is that bdsyn will create its own
intermediate variables corresponding to routine return
values and condition expressions from if and select
statements. These variables are good candidates for
having a large fanout. They are created in the hope that
it will save mis some work in extracting common factors.
On occasion, bdsyn may create an internal variable which
does not fan out. mis will give a warning when such
a variable is created. In general, it is safe to
ignore these warnings for variables whose name begin with
"$$COND."
3 Language Constructs
3.1 Names and Numbers
Bdsyn accepts a subset of the bds language as input.
bds is a Pascal-like language. The input consists of
names, numbers, and reserved keywords separated by white
space. White space is spaces, tabs, and carriage returns.
Any characters following a `!' (exclamation point) are
interpreted as comments by bdsyn. Legal names may contain
the characters a-z, A-Z, 0-9, `' (underscore), and `%'.
Other characters are legal in the name as long as the
name is quoted with double quotes ("). Names may not be
any of the reserved keywords (given below) unless they are
quoted. Names that begin with `$' are illegal. Bdsyn,
like decsim, is case insensitive, so the name "signal" is
the same as the name "SIGNAL."
Numbers in bdsyn must be positive and may be given in
any one of base 2, 4, 8, 10, or 16. Decimal numbers
are represented as a simple integer (e.g. 511). Other
base numbers are represented as an integer followed by a
`#' and the base (e.g. 1FF#16). The width, in bits, of
a decimal number is the minimum number of bits required
to represent that number. The width of a number with a
`#' is equal to the number of bits required to represent
a number in that base with the given number of digits.
For example 001#2 has width three, 123#8 has width nine,
and 12345678#16 has width thirty-two. Bdsyn has the
limitation that numbers in the input must be thirty-two
bits or fewer. This limitation may be overcome by the use
of the concatenation operator. (e.g. 12#16 & 34567890#16
is a forty bit constant.)
Table 1: Bdsyn Reserved Words
and begin buf by constant
do downto else end endmodel
endroutine endselect endselectall endselectone eql
eqv for from geq gtr
if leave leq lss macro
mod model nand neq nor
not or otherwise oxt require
return routine select selectall selectone
sl0 sl1 slr sr0 sr1
srr state sxt synonym then
to width xor zxt
Table 2: Keywords Ignored by Bdsyn
behavior endbehavior endmodule entry forward
fourstate halt inform input invalid
module noentry output port repeat
revision static twostate until while
3.2 Reserved Keywords
Table 1 gives a list of reserved words for bdsyn. These
may not be used as names unless they are quoted. In
addition to the reserved words there are several keywords
which bdsyn explicitly ignores but are included so that
complete bds descriptions (not just our subset) may be
parsed. They are listed in table 2
3.3 Variables
Bdsyn has two types of variables which it understands.
The first, "logic variables," imply actual logic and can
be thought of as wires in the actual layout. Logic
variables are declared with bit subscripts that define
their width. The lower bit numbers correspond to the less
significant bits, and bdsyn requires that the high bit be
first.
STATE name1<7:0>;
If the bit range of a variable is omitted in its
declaration,
STATE name2;
bdsyn will assume a single bit vector (name2<0>).
When using a logic variable (as opposed to specifying
one), the bit subscript is used to choose certain bits
from the bit vector. If the bit vector is left out, the
the entire bit vector is used.
In addition to logic variables, bdsyn defines "meta-
variables." Their main application is as the index
variable for for loops. Loop index variables are required
to be meta-variables. Meta-variables are declared with
null bit subscripts:
STATE name3<>;
Meta-variables do not imply any logic, and are used
for temporary storage of constants. When meta-variables
appear on the left hand side of an assignment, the right
hand side is evaluated and assigned to the meta-variable.
The right hand side of this assignment must be a
meta-variable expression (i.e., an expression written from
meta-variables and constants). When meta-variables appear
on the right hand of an assignment, they are treated
exactly like constants. This means that meta-variables
may be used in places where logic variables are disallowed
by bdsyn. Section 6 covers more about meta-variables.
3.4 Input Format
The following is a bnf description of a typical input
program for bdsyn. Keywords are given in capital letters,
and user names and productions are given in small letters.
Optional phrases are given in square brackets `[ ]'.
Phrases in curly braces `{ }' many be repeated zero or
more times in the input. The character `|' (vertical bar)
represents a choice of many lines.
The basic bdsyn input file consists of a "model":
MODEL model_name [output_var {, output_var}] =
[input_var {, input_var}]
;
{global_declaration ;}
{routine}
ENDMODEL [model_name];
A "globaldeclaration" is defined as the following:
| STATE global_var {, global_var}
| CONSTANT constant_name = number {, constant_name =
number}
| SYNONYM var_name = var_name {, var_name =
var_name}
A "routine" is defined as the following:
ROUTINE routine_name [bit_subscripts] [( var_param {,
var_param} )] ;
{ local_declaration ;}
{ [ label_name: ] statement ;}
ENDROUTINE [routine_name];
A "localdeclaration" is defined as the following:
| STATE local_var {, local_var}
| CONSTANT constant_name = number {, constant_name =
number}
| SYNONYM var_name = var_name {, var_name =
var_name}
A statement of a routine is defined below. Note: The
square brackets in the select statements represent actual
brackets in the input.
| BEGIN {statement ;} END
| variable = expression
| IF expression THEN statement [ELSE statement]
| FOR meta_var FROM const_expr TO const_expr
[BY const_expr] DO statement
| FOR meta_var FROM const_expr DOWNTO const_expr
[BY const_expr] DO statement
| SELECT expression FROM {[expression {,
expression}]: statement;}
{[OTHERWISE]: statement ;}
ENDSELECT
| SELECTALL expression FROM {[expression {,
expression}]: statement;}
{[OTHERWISE]: statement ;}
ENDSELECTALL
| SELECTONE expression FROM {[expression {,
expression}]: statement;}
{[OTHERWISE]: statement ;}
ENDSELECTONE
| RETURN [expression]
| LEAVE label_name
Note that these tables imply that a semicolon `;'
separates every statement. As in Pascal, there is
no semicolon before else, but unlike Pascal there is
a semicolon before end. Expressions and const-expr's
(constant expressions) will be described in later
sections.
3.5 Declaration Statements
The model statement defines the primary inputs and outputs
to the combinational logic block being described. The
declared "ports" may not be meta-variables.
The state, constant, and synonym may be used as either
global declarations, applying to all routines, or local
declarations, applying to only one routine. The state
statement is for declaration of variables. All variables
must be declared prior to use. Local variables can be
used only within the scope of a routine and their values
are lost between consecutive calls to a routine. Constant
declarations are used to assign a name to a constant.
Declared constants can be used anywhere a constant can.
Synonyms are used to create an alternate name for a
previously defined variable. They are particularly useful
for defining subfields of a variable:
SYNONYM opcode<6:0> = instruction<31:25>;
3.6 Flow-of-control Statements
Bdsyn offers a rich selection of flow-of-control
statements. They are if, select, selectone, selectall,
for, return, and leave. The if statement implements
optional execution of a statement. If the least
significant bit of the if expression evaluates to one,
the then clause is used. If the low bit evaluates to
zero, the else clause (if present) is used. The select
statement is used to execute one statement out of many.
If the expression following the select keyword is equal
to the expression appearing in the square brackets, the
corresponding statement is executed.
selectone and selectall are simply a shorthand for
several if statements. selectone implies nested if
statements:
SELECTONE expr FROM
[expr1, expr2]: statement1;
[expr3]: statement2;
[OTHERWISE]: statement3;
ENDSELECTONE;
is equivalent to:
IF (expr EQL expr1) OR (expr EQL expr2) THEN
statement1
ELSE IF expr EQL expr3 THEN
statement2
ELSE
statement3;
selectall is equivalent to sequential if statements:
SELECTALL expr FROM
[expr1, expr2]: statement1;
[expr3]: statement2;
[OTHERWISE]: statement3;
ENDSELECTALL;
is equivalent to:
IF (expr EQL expr1) OR (expr EQL expr2) THEN
statement1;
IF expr EQL expr3 THEN
statement2;
IF (expr NEQ expr1) AND (expr NEQ expr2) AND (expr NEQ
expr3) THEN
statement3;
selectall is different than select in that selectall
implies sequentiality in its case evaluation. The select
statement can be viewed as having all of its cases
evaluated in parallel. A selectall allows two cases to
evaluate to true. If two cases are true in a select,
incorrect logic may be produced. select generally implies
much less logic, however, because there is no implied
ordering of the cases.
for statements are used to iterate a single piece of
code several times. As a hardware description language,
bdsyn must enforce several rules on the for statement.
The expressions which specify the start, end, and step
values for the loop index must be either constants, or
constant expressions. This is because the number of
iterations must be fixed. Bdsyn also requires that the
index variable of the for statement is a meta-variable.
for loops may be nested, and since meta-variables are
treated as constants by bdsyn, the inner loop may depend
on the outer loop.
FOR i FROM 0 TO 7 DO
FOR j FROM i TO 7 DO
statement;
The return statement is used to break out of a
subroutine and return to the calling routine. If the
subroutine returns a value (as described below) the return
statement must be followed by an expression which is the
return value. The leave statement is similar to return in
that can be used to break out of a block of statements.
When a leave statement is encountered, control will break
out of a labeled statement. The leave must occur within
the labeled statement to which it points. For example:
loop: FOR i FROM 1 TO 10 DO BEGIN
statement1;
IF condition THEN LEAVE loop;
statement2;
END;
Notice that by using the leave it is possible to describe
a loop whose number of iterations depends on a logic
variable (condition in this case). It is only important
that the for statement itself have extents which are
constants or meta-variables.
3.7 Routines and Routine Calls
Bdsyn has no concept of a main routine, per se. At
runtime, bdsyn routines are classified as main routines
or subroutines depending on whether or not they called by
another routine. Bdsyn allows many main routines in the
same model, and these routines can be viewed as running
in parallel. It is an error in bdsyn for two disjoint
routines (one is not called by the other) to set the same
global variable or primary output of the block. Two
disjoint routines may call the same subroutine, however.
It is illegal to have recursive routine calls.
Subroutines may return a single variable (regular or
meta) to the calling routine. A subroutine that returns
a value is declared by placing a bit subscript after
the routine name in the routine declaration. The bit
subscript specifies the width of the return value or if
the value is a meta-variable. If the subscript is
missing, the routine returns no value. Parameters passed
to subroutines must be declared as part of the routine
declaration. Parameter passing has the same semantics as
assignment statements (described below).
A common error in bdsyn is to have a subroutine which is
not called by another routine. This causes bdsyn to treat
the subroutine as a main routine.
3.8 Assignment Statements
Assignment statements are written in the form:
variable = expression
They result is that the variable receives the value of
the expression. If the width of the variable is wider
than the width of the evaluated expression, extra zeros
will be added to pad the high bits of the variable.
If the expression is wider than the variable, the high
bits are truncated. If the variable is a meta-variable
the expression may contain only constants and other
meta-variables.
It is possible to assign a value to the same variable
twice in the same program. Bdsyn will treat this
situation in the same manner as any sequential programming
language. In particular the following works correctly.
x = 1; y = x; x = 0;
IF x NEQ y THEN is_ok = 1;
Section 4 contains further details on multiple assignment.
3.9 Expressions
Legal expressions are of the following form. They are
listed in order of precedence, and expressions higher on
the list are evaluated first. The curly braces in the
zxt, oxt, and sxt expressions represent actual characters
in the input, not a repeatable phrase.
| number ! number as described above
| constant ! a declared constant
| meta_variable
| regular_variable
| (expression) ! parenthesized expression
| expression ! choose a bit
| expression ! choose several bits
| expression & expression ! concatenation
| expression SR0 expression ! shift right filling with zeros
| expression SR1 expression ! shift right filling with ones
| expression SRR expression ! rotate right
| expression SL0 expression ! shift left filling with zeros
| expression SL1 expression ! shift left filling with ones
| expression SLR expression ! rotate left
| expression * expression ! multiplication
| const_expr / const_expr ! integer division
| const_expr MOD const_expr ! mod operation
| expression + expression ! addition
| expression - expression ! subtraction
| expression EQL expression ! Equal comparison
| expression NEQ expression ! Not equal comparison
| expression LSS expression ! Less than comparison
| expression LEQ expression ! Less than equal comparison
| expression GTR expression ! Greater than comparison
| expression GEQ expression ! Greater than equal comparison
| BUF expression ! null operation
| NOT expression ! bitwise NOT
| expression AND expression ! bitwise AND
| expression NAND expression ! bitwise NAND
| expression OR expression ! bitwise OR
| expression NOR expression ! bitwise NOR
| expression XOR expression ! bitwise XOR
| expression EQV expression ! bitwise XNOR
| WIDTH expression ! return number of bits
| ZXT {WIDTH = const_expr} expression ! zero extend
| OXT {WIDTH = const_expr} expression ! one extend
| SXT {WIDTH = const_expr} expression ! sign extend
In the above "constexpr" represents a constant expression.
A constant expression is an expression that contains only
numbers, declared constants, and meta-variables. It may
not contain regular variables.
The single bit selection operator, <0>, may take an
arbitrary expression as the bit selector. When the bit
selector is not a constant, a multiplexor is implied.
The multiple bit selection operator, <31:0>, requires that
both expressions be a constant expression and that the
first number is larger than the second. The concatenation
operator `&' joins two bit vectors into one. The
expression before the `&' becomes the high order bits, the
trailing expression becomes the low order bits.
The shift operations shift the first expression by an
amount given by the second expression. When the shift
amount is a variable expression, a barrel shifter is
thelwidth ofothe shiftedshexpression.on Thiss means itanis
possible to shift bits off the end of the expression
accidentally. Care should be taken to extend the
expression (using zxt) so no bits are lost.
`+', `-', `*', `/', and mod implement integer arithmetic
and are supported for constant expressions. In addition,
`+', `-', and `*' are supported for variable expressions.
`+' and `-' imply a combinational adder in this case, and
`*' implies a full combinational multiplier. The `*'
operation should be used sparingly on variable expressions
since it implies so much logic. In particular, `*' should
not be used where a shift would be sufficient.
The comparison operators evaluate to a single bit 1 if
the condition is true and a single bit 0 if the condition
is false. If an expression in the comparison is a
variable, a comparator is implied. The bitwise boolean
operators take two bit vectors and perform the desired
operation bit by bit. If one of the expressions is
smaller than the other, it will be automatically zero
extended. The width operator returns a constant which is
the number of bits in the given expression. zxt, oxt, and
sxt will add more significant bits to the given expression
to make it the given width. It is an error to specify a
width that is smaller than the given expression.
3.10 Macro Definitions and Required Files
Bdsyn has the facility for defining macro definitions
in the input description. Macro definitions may appear
anywhere in the input description and have the following
format:
MACRO macro_name = macro_body $ENDMACRO
Following a macro definition, any use of macroname will
be replaced by the macrobody. The macrobody is expanded
exactly as typed (including comments). It may span
more than one line and may contain uses of other macro
definitions.
Bdsyn also allows distinct input files to be included
within other files. This is done using the require
command. A require may occur anywhere in a bdsyn file and
has the syntax:
REQUIRE 'filename.ext';
The text of the required file will be inserted in place of
the require command.
4 Multiple Assignment
As mentioned in the introduction, bdsyn's input
descriptions appear very sequential in nature yet are
intended to describe combinational logic. We feel that
our form of sequential description gives the user a great
deal of power and flexibility in specifying logic. The
translation of sequential description to combinational
logic is accomplished by correctly handling "multiple
assignment."
Our definition of multiple assignment is the correct and
consistent handling of many sequential assignments to the
same variable. For example:
x = default_value;
IF condition THEN x = new_value;
describes a multiplexer which is controlled by "condi-
tion." The above example could be rewritten in a more
conventional way:
IF condition THEN
x = new_value
ELSE
x = default_value;
At first glance, one might think that multiple assignment
is not particularly useful. In fact, multiple assignment
is the heart of bdsyn's ability to process sequential
descriptions. Several examples of this can be found in
the "Examples" section at the end of this guide.
5 Unspecified Variables
In bdsyn input descriptions, as in any programming
language, it is possible to have variables which are not
always defined. For instance, in the following code:
IF cond THEN
x = expr;
the variable x, if it has not previously been assigned to,
is unspecified when cond is false.
Under normal circumstances bdsyn will assume that when
variables are unspecified, they should have the value
zero. This assumption is probably not a good one. In
some cases, the unspecified variables could be caused by
a mistake in the user specification. In other cases the
user may not care about a variable value under certain
conditions. In this case the user should probably specify
DONTCARE conditions as discussed in section 8.
In general, it is very difficult for bdsyn to detect
the use of unspecified variables. However, unspecified
variables may be detected by using mis. First, bdsyn
should be run using the -n flag. This will cause bdsyn to
create a group of variables that end with the characters
"**". (Also, the ".inputs" line in the blif output will
not be printed.) The blif file containing the "**"
variables should then be read into mis and minimized.
After minimization, if any of the "**" variables fan
out to any gates, this corresponds to the use of an
unspecified variable.
6 Meta-variables
Meta-variables have a very separate use from logic
variables. They can be used within constant expressions
because they represent constant values. Unlike logic
variables, they are guaranteed to always assume the
same particular value. The value of a logic variable
may change based on the primary inputs to the bdsyn
combinational block.
Because bdsyn is able to statically evaluate the value
of meta-variables, it is able to perform some simple
logic minimization when meta-variables are involved. In
the following example, function1 and function2 are complex
functions. (i is a meta-variable.)
FOR i FOR 0 TO 5 DO
IF i MOD 2 EQL 0 THEN
x = function1(x)
ELSE
x = function2(x);
After bdsyn minimization this becomes:
x = function1(x);
x = function2(x);
x = function1(x);
x = function2(x);
x = function1(x);
x = function2(x);
Had the condition in the if statement above depended on
a logic variable, no such minimization would have been
possible inside of bdsyn. This is because the value of a
logic variable is generally unpredictable.
One non-obvious problem with meta-variables is the
following. A meta-variable is defined within a branching
structure (i.e. if, select, etc.). If the condition of
the branching structure depends on a logic variable, the
meta-variable is not correctly defined upon exit from that
structure. For example:
meta = 3;
IF x EQL 1 THEN BEGIN
meta = 4;
a<0> = w; ! This works correctly
END
a<1> = w; ! This uses meta = 4 even if ( x NEQ 1 )
This problem stems from indirectly trying to define the
meta-variable meta in terms of the logic variable x. For
similar reasons, meta-variables that are used for loop
counts are not necessarily correct upon exit from the
loop. For example:
loop: FOR i FROM 1 TO 10 DO BEGIN
x = function(x);
IF x EQL 1 THEN LEAVE loop;
END;
y = i; ! y gets the value 10 regardless of the function
7 Complex Operators
Bdsyn supports several operations which can not be
implemented by just one or two gates. These include
`+', `-', `*', leq, geq, lss, gtr, shifts, and
single bit selection when they are operating on non-
constants. The operations imply complex structures such
as adders, multipliers, comparators, barrel shifters, and
multiplexors. The complex operators are implemented
through a set of library routines found in the file
"bdsyn.lib". The macros in the library are used to create
routines of an appropriate size (a 3 bit adder, or a 4 bit
comparator, etc) which are then inserted into the code.
8 Don't Care Conditions
It is often the case that it makes no difference what the
value of an output is. For example, in a finite state
machine with seven states encoded in three state bits,
state 7 never occurs:
SELECT state<2:0> FROM
[0,1,2,3]: output = 0;
[4,5,6]: output = 1;
ENDSELECT;
Here, the output for state 7 would be unspecified. To
resolve this, a default value for output might be added.
output = 0;
SELECT state<2:0> FROM
[0,1,2,3]: output = 0;
[4,5,6]: output = 1;
ENDSELECT;
The problem is that this is unnecessarily restrictive,
and does not allow for all of the potential logic
simplification. In actuality, it may make no difference
whether "output = 0" or "output = 1" in state 7, because
state 7 never occurs. For this reason, bdsyn has
the special variable DONTCARE, which will allow logic
optimization tools to choose the optimal value for output.
DONTCARE is used as any other variable:
output = DONT_CARE;
SELECT state<2:0> FROM
[0,1,2,3]: output = 0;
[4,5,6]: output = 1;
ENDSELECT;
Inside of bdsyn, assignments from this variable will
automatically be extended to fit the size of the
destination. When DONTCARE is used, it will automatically
be added to the input port list in bdsyn's blif output.
There is no need to declare the DONTCARE variable.
The current version of mis can not process the don't
care conditions produced by bdsyn. This is because don't
care specifications in multiple level descriptions can be
ambiguous in their meaning. Until a uniform method for
handling multiple level don't cares is implemented, it is
still possible to use espresso to make partial use of the
don't care specification. This can be accomplished by the
following (in unix):
bdsyn input_descr | mis -c clp -T pla | \
espresso -Dmapdc | espresso > output.pla
The resulting pla can then be read into mis.
If a description has been written that includes a
don't care specification and the use of the don't care
specification is not desired, the -z option should be
used. The -z option maps every use of DONT-CARE to
zero. The effect will be that in places where DONTCARE is
specified, the result will be forced to the value zero.
9 Examples
Figures 1 through 5 contain five examples of various
bdsyn descriptions. The first is a generic finite
state machine. It merely generates the next state and
control signals based on the present state. The next
three descriptions implement the exact same piece of
logic. They are included to demonstrate the flexibility
of bdsyn. Note that the second implementation (COUNT2)
uses intermediate variables seenZero and seenTrailing as
state holders. The variables do not really imply latches
to hold the state. They are simply a convenient way to
describe an idea.
The fifth example is a complicated decoder circuit.
Particular attention should be given to the last statement
of bdsyn.in TheudecoderItisidescribedsasn ambarrelt shifter
which shifts a single bit 1 onto the correct word line.
This is obviously a very inefficient way to build a
decoder. It is important to note, however, that bdsyn
and mis are capable of reducing the hardware to a more
sensible implementation. There is generally no penalty
associated with a quick and dirty shortcut description.
The logic that is generated is the same.
10 Acknowledgments
The parser, inline routine expansion, and macro expansion
inside of bdsyn were implemented by Richard Rudell.
The for loops, return and leave processing, multiple
assignment, and mapping to blif were implemented by
Russell Segal. To do logic collapsing, bdsyn uses mis,
which was implemented by Albert Wang and Richard Rudell.
We would like to thank the students and industrial
visitors who participated in the Spring 1986 synthesis
class for running bdsyn through its paces. We also
would like to thank Professors Richard Newton, Alberto
Sangiovanni-Vincentelli, and Carlo Sequin for organizing
the synthesis project and given bdsyn a reason to exist.
Example: Traffic Light Controller
! The classic traffic light controller finite state machine
! from Mead and Conway, Introduction to VLSI Technology,
! page 85
MODEL traffic_light
hl<1:0>, ! control for highway light
fl<1:0>, ! control for farm light
st<0>, ! to start the interval timer
nextState<1:0> =
c<0>, ! indicating a car on the farm road
ts<0>, ! timeout of short interval timer
tl<0>, ! timeout of long interval timer
presentState<1:0> ;
! state assignments
CONSTANT HG = 0, HY = 2, FG = 3, FY = 1;
! symbolic output assignments
CONSTANT GREEN = 0, RED = 1, YELLOW = 2;
ROUTINE traffic_light_controller;
! set up default outputs (use of multiple assignment)
nextState = presentState;
st = 0;
SELECT presentState FROM
[HG]: BEGIN
hl = GREEN; fl = RED;
IF c AND tl THEN BEGIN
nextState = HY;
st = 1;
END;
[HY]:;BEGIN
hl = YELLOW; fl = RED;
IF ts THEN BEGIN
nextState = FG;
st = 1;
END;
END;
[FG]: BEGIN
hl = RED; fl = GREEN;
IF NOT c or tl THEN BEGIN
nextState = FY;
st = 1;
END;
[FY]:;BEGIN
hl = RED; fl = YELLOW;
IF ts THEN BEGIN
nextState = HG;
st = 1;
END;
END;
ENDSELECT;
ENDROUTINE;
ENDMODEL;
Figure 1: Traffic Light Controller
Example: Count1
! COUNT1 (Count Zeros):
! The input is an 8 bit binary string expected to consist of
! a string of 1's, a string of 0's, and a string of 1's. Any
! of these strings may be zero length.
! For example, `11000111', `10000001', and `11110000' are all
! valid strings, and `10001100' is a mal-formed string.
! The problem is to design a circuit which, given the 8 bit
! string, returns the count of number of consecutive zeros in
! the string, or returns an error condition if the string is
! mal-formed. The output is undefined if the input string is
! mal-formed.
MODEL count1 error<0>, out<3:0> = in<7:0>;
! find first bit matching 'val' (return index of the bit)
ROUTINE ff<3:0>(x<7:0>, val<0>);
STATE index<>;
FOR index FROM 0 TO 7 DO
IF x EQL val THEN
RETURN index;
RETURN 8;
ENDROUTINE;
ROUTINE main;
STATE x<7:0>;
! Shift off the first string of 1's
x = in SR1 ff(in, 0);
! Count is where the first 1 is
out = ff(x, 1);
! Check for a mal-formed string:
! shift off 0's, and check for any more 0's
x = x SR1 out;
error = ff(x, 0) NEQ 8;
IF error THEN
out = DONT_CARE;
ENDROUTINE;
ENDMODEL;
Figure 2: Count1
Example: Count2
! COUNT2 (Count Zeros)
! A different implementation for the last example.
MODEL count2 error<0>, out<3:0> = in<7:0>;
CONSTANT TRUE = 1, FALSE = 0;
ROUTINE legal<0>(x<7:0>);
STATE index<>;
STATE seenZero; ! there has been a zero
STATE seenTrailing; ! we have hit the trailing ones field
seenZero = FALSE;
seenTrailing = FALSE;
FOR index FROM 0 TO 7 DO
IF seenTrailing AND (x EQL 0) THEN
RETURN FALSE ! Illegal string
ELSE IF seenZero AND (x EQL 1) THEN
seenTrailing = TRUE
ELSE IF x EQL 0 THEN
seenZero = TRUE;
! If we made it to here then the input is legal
RETURN TRUE;
ENDROUTINE;
ROUTINE zeros<3:0>(x<7:0>);
STATE index<>, count<3:0>;
count = 0;
FOR index FROM 0 TO 7 DO
IF x EQL 0 THEN
count = count + 1;
RETURN count;
ENDROUTINE;
ROUTINE main;
IF legal(in) THEN BEGIN
error = FALSE;
out = zeros(in);
END ELSE BEGIN
error = TRUE;
out = DONT_CARE;
END;
ENDROUTINE;
ENDMODEL;
Figure 3: Count2
Example: Count3
! COUNT3 (Count Zeros)
! Yet another implementation
MODEL count3 error<0>, out<3:0> = in<7:0>;
CONSTANT TRUE = 1, FALSE = 0;
! check for a legal string
ROUTINE legal<0>(x<7:0>);
STATE index1<>, index2<>, index3<>;
! Look for a ...0...1...0...
FOR index1 FROM 0 to 5 DO
FOR index2 FROM index1+1 to 6 DO
FOR index3 FROM index2+1 to 7 DO
IF (x EQL 0) AND (x EQL 1) AND
(x EQL 0) THEN
! The input is illegal
RETURN FALSE;
! If we made it to here then the input is legal
RETURN TRUE;
ENDROUTINE;
ROUTINE zeros<3:0>(x<7:0>);
STATE index<>, count<3:0>;
count = 0;
FOR index FROM 0 TO 7 DO
IF x EQL 0 THEN
count = count + 1;
RETURN count;
ENDROUTINE;
ROUTINE main;
IF legal(in) THEN BEGIN
error = FALSE;
out = zeros(in);
END ELSE BEGIN
error = TRUE;
out = DONT_CARE;
END;
ENDROUTINE;
ENDMODEL;
Figure 4: Count3
Example: Register file decoder
! Register decoder for the SPUR cpu chip.
! The register file of the SPUR cpu uses a Berkeley RISC
! type register windowing scheme. The register file is
! divided into 8 overlapping register "windows". Each
! register window can access 32 of SPUR's 138 registers.
! The first 10 registers of all of the windows point to
! the same 10 "global" registers. The next 6 registers
! are shared with the top six registers of the previous
! window. The 6 top registers of each window are similarly
! shared with the next window. The last window wraps
! around and shares registers with the first window.
MODEL reg_decode
addr<137:0> ! one-hot decoded output (word lines)
=
cwp<2:0>, ! Current window pointer
reg<4:0>; ! Current register in the window
CONSTANT
NUMREGS = 138, ! total number of registers
NUMGLOBALS = 10; ! number of global registers
ROUTINE REG_DECODE();
STATE
sum<7:0>, ! temporary variable
decAddr<7:0>; ! decoded address (number of the word line)
! calculate the correct register number
IF (reg LSS NUMGLOBALS) THEN
! point to the global registers
decAddr = regSpec
ELSE BEGIN
sum = (cwp & 0000#2) + regSpec;
! Check for wrap around. If so, need to subtract an offset
IF (sum GTR (NUMREGS - 1)) THEN
sum = sum - (NUMREGS - NUMGLOBALS);
decAddr = sum;
END;
! Do the actual decoding (*** See main text for details ***)
addr = (ZXT {width=138} 1) SL0 decAddr;
ENDROUTINE;
ENDMODEL;
Figure 5: Register file decoder