Revision of VHDL Shared Variables (Draft Requirements) 
Author Message
 Revision of VHDL Shared Variables (Draft Requirements)

Requirements Document For VHDL Shared Variable Revision


based on comments by Rob Newshutz & Tom Dillinger

Requirements Document Group:



Outline -----------------------------------------------------
1.0 Introduction
2.0 Requirements
3.0 Glossary

1. Introduction -----------------------------------------------------

The definition of shared variables phrased in VHDL does not provide a
portable or algorithmic language definition.  In order to expedite
the acceptance of VHDL '92 by RevCon, this definition remains in the
document, however leading VHDL vendors have agreed to either defer
including shared variables in their '92 offering or are underscoring
the non-portable, volatile nature of shared variables to all of their
customers receiving an implementation of VHDL '92 shared variables.

In order to remedy the situation as quickly as possible, ISAC has

prepare a revision of the shared variable definition in VHDL '92.
This definition will be submitted by VASG to a vote by an extended

This phrases the set of requirements to which the shared variable
working group is targeting the ISAC revision.  Your comments on this
draft are requested.  Please address your comments to the authors
listed above.  

All three of the authors have voiced disagreement to the inclusion of
shared variables.  This document is an attempt to reconcile the very
divergent views by better understanding the real motivations for shared
variables.

This initial compilation is intended to embrace requirements phrased
by many members of the shared variable working group including but not
limited to:
Steve Bailey
Jean Michel Berge
Clive Charlwood
Oz Levia
Rob Newshutz
Jacques Rouillard
James H. Vellenga
John Willis
Corrections appreciated!

2. Requirements -----------------------------------------------------

This section introduces a set of requirements for shared variables.  
The lack of clearly defined requirements has substantially delayed
and complicated discussion of design alternatives.  If we can agree
on the requirements, we are well on the way to agreeing on the
definition of shared variables.  If we cannot agree on the
requirements, it is unlikely we will agree on the solution.  Thus
please review these requirements carefully, asking if they fully
address what you and your organization need from shared variables.

2.1 Suitability as a formal notation for use in all phases of the
    creation of electronic systems

Taken from the Forward to the '87 and '92 LRM, this statement must
serve as THE primary direction for all changes considered to VHDL.

While formal has a variety of technical meanings, the dictionary
definition closest to VHDL's usage reads "made in accordance with
procedures which insure validity".  While a language cannot in the
strictest sense insure validity, VHDL follows the Ada approach of
trying to maximize the validity of the design.  Manifestations of
this direction include the strong type system, use of non-zero
delay signals for inter-process communication and well-defined
initial values for all variables and signals.

A variety of less formal hardware description languages are widely
available to designers.  Requirements which seek to transform VHDL
into such a language are incompatible with this primary directive.
If a user really demands an informal language, it is better that
the user be guided to a suitable language than that the user try
to transform VHDL.

The second part of this statement emphasizes the scope of designs
for which VHDL is intended.  VHDL's mechanisms need to embrace the
full range of analog, switch, gate, RTL, behavi{*filter*}and queueing
models with a reasonable formal notation.

2.2 Ease and ability to access model state from outside model

VHDL's behavi{*filter*}modeling capability is well-suited for writing the
environment surrounding a device under test (test bench).  From
the first simulation runs on a model through final verification, it
is useful for the test bench to be able to observe and set key state
within the model.  Since this state is most effectively represented
as variables and the test bench process(es) are distinct from model
processes, the variables are thus shared.

If the device under test is in the early stages of development, the
test bench may supply key environment or functionality using external
files (e.g. instruction trace files) or behavi{*filter*}code (e.g. a
process which generates instruction addresses based on stochastic
parameters).

Even if the model for the device under test is in an advanced stage
of development, simulation performance objectives may dictate that
functionality of the original design is supplied from outside the
model (the test bench).  For example, once the initialization for
a processor is verified, it may be expedient to initialize the model
from the test bench rather than by simulation of hardware's internal
initialization code.

Models of memory or hardware registers (perhaps a program counter)
represent common, concrete examples of state susceptible to
observation and access by the test bench.  Test benchs often want
to "initialize" this state, run a simulation, observe the state,
then re-initialize with a new state to begin another simulation
cycle.  Initialize via generics is undesirable since it requires
expensive re-elaboration of the design hierarchy.  Initialization
from files local to each process containing state is infeasible
if a single file or generator is to control all initializations.

2.3 Ease and ability to access global values within the model

Within a model, modeling and performance abstractions naturally
lead to essentially global values.  While these global values
do not and cannot have a direct manifestation in hardware,
they are an essential aspect of the design process.

Abstract modelers often want access to stochastic functions, such
as random number generators.  A package may provide a desired
generator for one or more processes.  Some designers want to be
able to acquire a countably infinite number of random values drawn
from the same seed during the same delta cycle.

Analog modelers often want to include a global definition of the
system's temperature, humidity or altitude in the analog behavior.
For example, the delay may be a function of the temperature.
Before synthesis the design process usually replaces such analog
terminal components with calls to standard cell library components
or other synthesizable terminals.

Performance modelers often want to record global aggregates of
locally generated statistics such as the total number of error
conditions encountered or the total number of instructions
fetched by a MIMD multiprocessor.  Such statistics do not reflect
actual hardware and thus are very artificial (and tedious) when
reflected in the component hierarchy.  Before manifesting the
design as actual hardware, performance monitoring information
is almost always conditionally compiled or manually extracted
from the VHDL model.

All three applications have in common the desire to reference
global values external to the port mappings of the design
hierarchy (so that the global variables will not be implicit
in the hardware design), the need to allow an arbitrary number
of references per delta cycle and the need for trivial, localized
elimination of the global state.

2.4 Ease and ability to translate from other HDL

Many users have a substantial investment in designs using other
hardware description languages (e.g. Ella, Verilog, etc.).  Many
of these languages include some form of shared variables.  Users
would like to be able to automatically or semi-automatically
translate from other languages into VHDL.  VHDL '87 signals,
with finite delay, often make such translation infeasibly complex.

Since VHDL's primary directive is to maintain what is often a
more formal description than other languages provided, all but
the most comprehensive translation is susceptible to generation
of a VHDL model in which a compliant VHDL analyzer, compiler or
runtime system will identify new errors in the translated model
or be capable of resultant behavior differing from the original
model.

Furthermore the evolution of languages requires that languages
not be required to maintain all of the features of earlier
languages (e.g. VHDL omitted the unstructured goto present in
some earlier languages).  Through this evolution, languages
gain the ability for more formal specification and improved
performance.  Language evolution is good.

Practical usage demands the ability to automatically translate
shared variables into VHDL.  Such translations should be as
simple as possible and generate as efficient code as possible
WITHOUT compromising the integrity of VHDL's formal description.

2.5 Ease and ability to dynamically size objects

VHDL's ability to determine the size (constraints) on an object
after analysis of the source code is essential to many users.
The constraints may be determined during structural elaboration,
subprogram elaboration or dynamic allocation of an object (via
new).  Shared variables must preserve this capability.

For example, the size of a memory model may be determined by
generics during elaboration or during initialization of the
memory by a test bench.  In the later case, initialization may
need to dynamically allocate an object for each line of memory
values read from a file.  The collection of dynamically
allocated objects (memory intervals) may be arranged in a hash
table, binary tree or other aggregate data structure.  Such
a data structure is typically linked together with access
values.

2.6 No transfer of dynamic objects

Algorithmic behavior effectively requires that any specific,
dynamically allocated object be accessible from exactly one,
mutually exclusive set of critical regions.  This implies
boundaries across which access values may not propagate.

Consider the counter-case in which a single object may be
referenced from more than one mutually exclusive set of
critical regions.  A thread of control running within each
of the mutually-exclusive sets of critical regions may refer
to the same object with arbitrary interleaving of load and
store accesses.  As a result, a wide range of results would
be possible, many of which are counter-intuitive (e.g.
adding one and one to get a large negative number).

2.7 Algorithmically-specified, user controllable determinism

User requirements for determinism range from an absolute
requirement that simulation of the same model with the same
input produce the same outcome ever time to users who just
need an algorithmically well-defined set of results (bounded
non-determinism).  Since embedding a specific policy for
determinism will isolate the majority of users, the revision
of shared variables must provide for a wide spectrum of
user-controllable determinism.

User controllable non-determinism must not rely on any
particular order or sequential execution of processes.  Since
execution of two processes in the same delta cycle documents
actually concurrent execution, such serialization violates the
primary directive to formally describe any electronic system.

In order to provide user-controllable determinism, revision
of shared variables must provide for the grouping of one or
more primitive operations such that the operations appear
to side effect a shared object in an all or nothing fashion
(atomically).  The user may employ this mechanism to denote
the desired level of determinism (user education is key).

2.8 Concurrent access to the same variable in one delta cycle

Many valid modeling styles and parallel algorithms imply the
potential for access to the same object from more than one
VHDL process during the same delta cycle.  Obtaining a
countably infinite number of random numbers, drawn from a
single seed, during the same delta cycle effectively requires
this capability.  Monitoring system temperature or other global
properties (e.g. analog modeling) naturally leads to concurrent
access.

If all accesses during the same delta cycle read the shared
object, the order of access does not matter and thus there is
little problem.  Problems come about when there is more than
one access and at least one of the accesses is a write to the
shared object.  The user-controllable determinism mechanisms
described above must permit and embrace concurrent access during
the same delta cycle.

2.9 Minimal syntactic overhead consistent with above requirements

As a formal description language, VHDL sometimes is more explicit
and thus verbose than other languages.  For example, flow analysis
may distinguish impure functions from pure functions, yet VHDL
'92 explicitly provides impure and pure keywords to make the usage
clear to the reader.

Provided the documentation objectives are met, it is desirable that
shared variables not impose undue syntactic overhead.  Since they
are intrinsically more complex than variables local to a process,
some syntactic overhead is inevitable.  This overhead should not
be any more onerous than that required to formally document the
intended behavior and usage.

2.10 Minimal runtime overhead consistent with above requirements

If the elaborated usage or simulation platform permits simplification
of runtime implementation, such simplification should be allowed but
not required by the language design.

If a shared variable is actually referenced from only one process,
access to the shared variable should take no more time during
simulation execution than if the variable were local to a single
process.  The overhead of locking and unlocking such a shared
variable should not be required by the revised shared variable
definition.

If an implementation can assure that requirements for shared variables
are otherwise met, perhaps because the simulation is running without
suspension on a uniprocessor, there is no explicit need to lock or
unlock shared variables.

2.11 Portability across uniprocessor and parallel VHDL implementations

As an industry standard language independent of any vendor, any change
to VHDL should not presume a particular hardware implementation.  This
requirement is already manifest in the range of intrinsic data types
(e.g. integer'left).  In particular, the language should not imply the
implicit semantics of implementations in which process execution is
either serialized or in which processes are allowed to run concurrently.

Portability requires that simulation of any legal VHDL model attain a
result compliant with the standard.  Note that lack of determinism may
result in a model which does not get the SAME result on distinct runs
of the same simulator or on different simulators, only that the results
are within the domain permitted by algorithmic definition within the
language.

3. Glossary ------------------------------------------------------

This section proposes working definitions for concepts which are key
to the specification of requirements for VHDL shared variables.

3.1 Concurrent access

Concurrent access governs the ability of two or more VHDL processes
to read and/or write the same subelement of a shared variable during
the same delta cycle.  Concurrent reading is not a problem, however
if one or more processes write the subelement during the same delta
cycle when other processes read the subelement, more than one model
state may be legitimate at the end of the delta cycle (leading to
interleaving, non-determinism, atomicity and deadlock problems).

If VHDL were to disallow allow reading and writing by distinct
processes during the same delta cycle, how is the inhibition to be
manifest.  In general, the conflict is not detectable during either
analysis or elaboration.  Should a runtime check be in place, and
if so how should a failure be signaled.  Does each check need a
user-defined severity level and message?  Does a conflicting access
quietly defer to the next delta cycle?

3.2 Interleaving

If at least one VHDL process may read a subelement during the same
delta cycle in which another VHDL process may write the subelement,
the specification either needs to specify how the accesses will
be interleaved or sacrifice determinism.  

Implementations of VHDL simulators using singly-threaded processing
allow a single process to execute until it blocks, then the processor
begins execution of another thread.  For multiply-threaded processors
and parallel processors, this paradigm is unacceptably restrictive.

In general, specification of interleaving is very difficult to do
without imposing performance penalties.  Most modern parallel
languages (such as VHDL) which allow the sharing of variables handle
the specification of interleaving by denoting a set of instructions
which retain exclusive access to a set of data objects while the
execution of a single thread of control advances between machine
instructions contained within the set.

3.3 Determinism

A deterministic mechanism insures that simulation of a given VHDL
model with the same inputs will always produce the same outputs each
time the simulation runs.  Determinism optionally may extend across
successive runs on the same simulator version, simulator platform,
or simulators from distinct vendors (related to portability issue).

Determinism is key for both implementors and users.  When a user
reports an apparent bug to an implementor, the inability to replicate
the apparent bug greatly complicates documentation or repair, leading
to user frustration and greatly increased support costs.  Production
users often run models against known output (from a specification or
golden model).  Miscomparisons indicate a failure needing expensive
interpretation by a human.  Non-determinism GREATLY increases the
frequency and cost of human intervention.

3.4 Bounded Non-Determinism

Identifying a single end state of a model given a fixed input is often
not feasible (absolute determinism).  However it is often practical
and very useful to specify the language such that a bounded set of end
states may be reached (e.g. a variable of integer type is either one,
two or three but not any representable integer).

3.5 Atomicity

The integrity of aggregate data structures is often dependent on the
relationship between more than one sub-element of a data value having
aggregate type.  For example, a shared data structure containing a
doubly-linked list requires consistent pairs of cross-linked indicies,
pointers (access values).

In order to maintain consistent values between subelements, a set of
read and write operations must often occur in their entirity or not
at all.  Such a set of read and write operations is said to occur
atomically.  A useful parallel language must provide some mechanism
by which the VHDL author may denote the required atomicity.

Even within the machine representation of a primitive subelement, a
multiprocessor may interleave read and write operations referencing
part of the primitive subelement representation at a time.  For
example, a processor with 32-bit buses may reference the upper and
lower halves of a 64-bit integer as distinct operations.

3.6 Deadlock

If two or more processes interact through a shared variable so that
one or more processes cannot advance to the next delay or finite
time step given an infinite duration simulation, the processes (and
simulation) is said to be deadlocked.

For example, consider Process A and Process B referencing two shared
variables, Variable C and Variable D.  If Process C acquires exclusive
access to Variable C, then proceeds to acquire exclusive access to
Variable D at the same time Process B has acquired exclusive access
to Variable D and is proceeding to acquire exclusive access to Variable
C, deadlock may occur.

3.7 Algorithmic Behavior

Simulation behavior is defined by a precisely stated algorithm such
that the step of legitimate end results of a simulation can (in theory)
be predicted before simulation runs.

3.8 Semaphores (P & V)

Two independently instantiated operators which regulate entry (P) and
exit from (V) a critical section.  Once the P operation executes with
a specific semaphore as its operand, no other P operation on the same
semaphore will succeed until there is a corresponding V operation on
the same semaphore.  Normally a failure of the P operation results in
the process (thread of control) blocking or looping on the P operator.

Dijkstra formulated P (pass) and V (vrij - Dutch for free) in the early
days of parallel programming.  While P and V is sufficient to control
atomic access to data, explicit programming of P and V often leads to
programs in which P is not matched with V, resulting in deadlock.

3.9 Critical Region

A critical region is one in which at most one thread of control (VHDL
process) may execute at a time.  The statements spanning the critical
region may be denoted by declarative regions, explicit syntax or
implicitly.

3.10 Monitor

A monitor is a collection of data fields coupled with subprogram which
provide access to the data fields.  The monitor may be instantiated as
with a type.  For a single instance of the monitor, only one thread of
control (VHDL process) may execute any of the subprograms providing
access to the data fields of the specific monitor instance.



Wed, 31 Jan 1996 04:47:51 GMT  
 
 [ 1 post ] 

 Relevant Pages 

1. Shared Variable Requirements The Shared Variable Working Group of the IEEE DASC is developing a

2. 1076a VHDL Language Revision Ballot for Shared Variables - svwg_bal.inv (0/1)

3. Draft B of VHDL LRM - Shared Variables

4. VHDL '92 Draft B Shared Variables

5. Pragma SHARED, tasks and shared variables

6. Shared Variables in VHDL/1992 Draft B (Status & Request)

7. Proposed revisions to std_logic package for VHDL'93

8. DoD requirement about VHDL-models

9. Deliverable VHDL - Defense contract requirements

10. RAM Requirement of local variables in DEC-Fortran

11. VHDL 2000 Draft LRM Review

12. VHDL Synthesis draft Standard (Birds-of-a-feather at VIUF)

 

 
Powered by phpBB® Forum Software