An Algorithm for Exact Bounds on the Time Separation of Events in Concurrent Systems.
AbstractDetermining the time separation of events is a fundamental problem in the analysis, synthesis, and optimization of concurrent systems. Applications range from logic optimization of asynchronous digital circuits to evaluation of execution times of programs for real-time systems. We present an efficient algorithm to find exact (tight) bounds on the separation time of events in an arbitrary process graph without conditional behavior. This result is more general than the methods presented in several previously published papers as it handles cyclic graphs and yields the tightest possible bounds on event separations. The algorithm is based on a functional decomposition technique that permits the implicit evaluation of an infinitely unfolded process graph. Examples are presented that demonstrate the utility and efficiency of the solution. The algorithm will form a basis for exploration of timing-constrained synthesis techniques.
Introduction
In this paper, we derive an exact algorithm that
determines tight upper and lower bounds on the separation
in time of an arbitrary pair of system events.
Depending on the level of abstraction in the specifica-
tion, events may represent low-level signal transitions
at a circuit interface or control flow in a more abstract
behavioral view. If we are able to determine
the bounds on the separation in time of two events
then we can use this information to: simplify combinational
and sequential logic by extracting temporal
don't care information, verify that a logic implementation
meets specified timing constraints, identify and
remove hazards from asynchronous circuits, and focus
optimization efforts in data-path synthesis by generating
useful scheduling constraints. Thus, determining
the time separation of events is a fundamental problem
in the analysis, synthesis, and optimization of concurrent
systems.
We develop an efficient solution for determining
time separation bounds and also take into account the
effects of starting the system from a specific reset or
start state. We model a concurrent system as a cyclic
connected graph. The nodes of the graph represent
events and the arcs are annotated with lower and upper
bounds on delays between events. Currently, our
solution is limited to graphs without conditional be-
havior. However, that still leaves a large and useful
class of concurrent specifications to which our analysis
applies.
Other approaches to the problem of finding bounds
on the separation in time of two events have either
been inexact or based on a more restrictive graph
topology. Loose bounds that may not enable all possible
optimizations were obtained by [8]. Both [7] and
[10] can only handle acyclic graphs, and [2] only supports
a limited form of synchronization and concurrency

This paper is composed of five sections. We follow
this introduction with a formalization of the problem,
a review of the foundation provided by the solution
for finite acyclic graphs, and some examples. Section
3 provides the details of our algorithm, which is based
on a structural decomposition of the unfolded process
graph. Some practical examples are presented in Section
4, and finally, Section 5 summarizes the contributions
of this paper.
Problem Formalization
Consider a simple concurrent system consisting of
three processes that synchronize over two channels a
and b, and do some internal computation (delay ranges
specified in brackets):
repeat f
Synchronize a;
Compute
repeat f
Synchronize a;
Compute
Synchronize b;
Compute
repeat f
Synchronize b;
Compute
We represent the system as a directed graph, called
the process graph, where the vertices represent events
(synchronizations) and the edges are annotated with
delay information. The process graph for the system
is shown in Figure 1. The initial state of the processes
is specified by marking the edges that can execute initially

To formalize the problem we use a simple modification
of the event-rule system developed in [3] 1 . Let
process graph composed of
a finite set of (repeatable) events E 0 , the vertices
of the graph.
a finite set of rule templates R 0 , the edges of the
graph.
Each edge is labelled with two objects, the delay range
[d; D] (integers with 0 - d - D), and the occurrence
index offset 2 ". For our example we have
and R
7\Gamma! a; a [1;2];0
7\Gamma! bg.
We restrict our analysis to well-formed graphs, that is,
graphs that are strongly-connected and have "(c) ? 0
for all cycles c in the graph, where "(c) is the sum of
the " values for all edges in the cycle c.
a

Figure

1: Three processes synchronizing at points a and
b. The number of lines drawn through an edge indicates
the value of the occurrence index offset.
2.1 Execution Model
We denote the k th occurrence of event
and refer to k as the occurrence index of v k . Let
E be the set of all event occurrences (infinite in one
direction, i.e., k - 0). To model the initial startup
behavior of a process, we also include in E a single
event occurrence named root. Thus,
The set R consists of the rules generated by instantiating
each rule template of R 0 at each occurrence
introduced a similarly modified system. The model can
also be viewed as an extension of [7] and [10], where we consider
cyclic max-only or type-2 graphs.
2 The occurrence index offset is used to specify how much the
occurrence index is incremented when the edge is executed-see
Section 2.1.
ae
oe
Special startup rules are included in the set R 0 , a non-empty
finite subset of froot [d;D]
We call the infinite directed graph constructed from
the vertex set E and the edge set R the unfolded process
graph. Figure 2 shows the unfolded process graph
for the example in Figure 1.
root
a3
[4, 10] [4, 10] [4, 10] [4, 10]
[5, 20] [5, 20] [5, 20] [5, 20]
[1,6]
[1,6]
[1,6] [1,6]

Figure

2: A portion of the unfolded process graph for
the process graph in Figure 1. Two startup edges have
been added, specifying that both a 0 and b 0 must occur
after root .
An execution of a process graph is the consistent assignment
of time values to event occurrences. A timing
assignment, - , maps event occurrences to global
time, thus - (v k ) is the time of the k th occurrence of
event v. The delay information in R restricts the set of
possible timing assignments. Formally, we define constraints
on the time values introduced by each event
occurrence:
ae
oe
ae
oe
The constraints on - (v k ) embody the underlying semantics
of a process graph's execution, i.e., events
correspond to synchronizations and an event can occur
only when all of its incident events have occurred.
Each incident event is delayed by some number in a
bounded interval ([d; D]). Thus, the earliest time at
which v k can occur is constrained by d values, the latest
by D values.
2.2 Problem Definition
The problem we address in this paper is: given two
events s and t in E 0 and a separation in occurrence
index fi, what are the strongest bounds ffi and \Delta such
that
for all ff - max(0; fi)? For example, to determine the
bounds on the time separation between two consecutive
a events, we would set
consider the bounds on - (a ff We address
only the problem of finding the maximum separation,
since ffi can be obtained from - (s ff
2.3 Algorithm for a Finite Unfolded Process
Graph
We build our solution to this problem on a variation
of a graph algorithm developed by McMillan and
Dill [7] that applies only to finite unfolded graphs. In
Section 3 we will generalize this algorithm to infinite
unfolded graphs.
Let \Delta ff be the strongest bound for the separation
problem given an ff, i.e.,
We can determine \Delta ff by analyzing a finite acyclic
graph created by only including the vertices in our
unfolded process graph for which there is a path to
either t ff or s ff\Gammafi . Name the resulting graph hE   ; R   i.
The algorithm consists of two simple steps. First,
we compute m-values backwards from s ff\Gammafi for all
event occurrences,
where d(h) is sum of the d values of the edges on the
path h. We can compute these values in linear time in
the size of R   by a reverse topological traversal from
s ff\Gammafi . If there is no path from v k to s ff\Gammafi , denoted by
, we can assign an arbitrary constant value
to m(v k )-we use m(v k
We then compute \Delta assigning
and then for all other occurrences in
(normal) topological order
(1)
If v k 6; s ff\Gammafi , the minimization with 0 is omitted.
root
root411 104 0110100
6
(a) (b)

Figure

3: Finite acyclic graph, hE   ; R   i for obtaining
for the process graph in Figure 1 given the parameters
In (a), the edges are labeled with the d values, and the
vertices are labelled with the m-values obtained in the
first step of the algorithm. In (b), the edges are labeled
with the D values, and the vertices are labelled with
the M-values obtained in the second step. We obtain
Applying the algorithm to the example in Figure 1
(see

Figure

3 for the computation of yields the
following maximum separations:
To compute \Delta, the maximum separation in time
over all occurrences of s and t, separated in occurrence
by fi, we maximize \Delta ff over all values of ff:
The problem, of course, is that this requires an infinite
number of applications of the algorithm. Before we
present an algebraic solution that allows us to analyze
the infinite unfolded graph, we illustrate the difficulties
of this analysis with a few examples.
2.4 Examples
Our first example, in Figure 4, is a process graph
that represents two coupled pipelines. If the pipelines
were not coupled at c, the maximum separation between
a and e would be unbounded. This is because
the first pipeline (choosing the delay between consecutive
a's as being 2) could be arbitrarily slower than
the second pipeline (choosing the delay between consecutive
e's as being 1). The coupling of the pipelines
forces one pipeline to wait for the other if it gets too
far ahead.
a
e d
c

Figure

4: A process graph that represents two coupled
pipelines. All unspecified delay ranges are [0; 0].
We start the pipeline by rooting all of the initial
occurrences at zero, e.g., root [0;0]
7\Gamma! a 0 . For all ff - 0,
it can be shown that - (a ff
Our second example, in Figure 5, exhibits interesting
behavior. We root all of the initial occurrences at
zero. If
f
e [-]
d
c
b a
[3; 3]
[3; 3]
[3; 3]
[3; 3]

Figure

5: A process graph with unusual timing behavior.
All unspecified delay ranges are [1; 1].
If we change
a
d
e
c
[10; 10] [10; 10]

Figure

Two processes synchronizing at c.
Our final example, in Figure 6, corresponds to
two simple processes that synchronize at the event
c. Clearly, the startup rules can affect the initial
timing behavior of the processes. However, this example
demonstrates that the initial startup rules also
can determine the maximum separation at every point
in the infinite execution. We have two startup rules:
root
7\Gamma! d 0 and they determine
every \Delta ff for - (e ff
As the process graph is a repetitive system, presumably
the \Delta ff values will eventually reach a steady
state, for example, large ff. Unfortu-
nately, as our examples illustrate, the behavior of the
ff values can be non-monotonic and periodic, and
might even start out periodic and then later stabilize
to a constant value. Thus, no simple criteria for determining
when steady state has been reached can be
derived based on the behavior of the \Delta ff values.
3 Functional Solution
Our solution to the problem is based on a structural
decomposition of the unfolded process graph that exploits
its repetitive nature. By dividing the unfolded
process graph up into segments and representing the
computation of the finite graph algorithm in a symbolic
manner we can reuse the computations for each
segment.
3.1 Introducing Functions
We introduce a symbolic execution of the acyclic algorithm
presented in Section 2.3. Instead of computing
the numeric M-values in (1), we compute functions
that relate M-values with one another. We present an
algebra for representing and manipulating these functions

Functions are represented as sets of pairs. A singleton
set, fhl; wig, represents the function
In general, the set
wn ig (2)
corresponds to the function
We associate two operators with functions: function
maximization, f max g, and function composi-
g. It follows from (3) that function maximization
is defined as set union: f g. The
following observation leads to an important efficiency
optimization:
Pruning Rule In (2), if l i - l j and w , we can
prune the pair hl since for all x, min(x+ l
Thus, a function (2) can always be represented such
that
Function composition, h, is defined as
Notice that we use left-to-right
function composition [4]. For
(g
If g or h contain more than one pair then
where g i and h i are singleton sets. Function composition
is performed using distributivity, i.e.,
We can now express the M-values using functions.
We associate a function, f , to each edge u k\Gamma"
in the unfolded process
f
ae
The function f incorporates the min-part of (1), and
the max-part of (1) corresponds to function maximization
of the functions for the incoming edges. Using
function composition and function maximization,
we can create a function F v k that relates M (root) to
F
f
root

Figure

7: Fragment of unfolded process graph annotated
with functions corresponding to each edge (the m-values
are given in Figure 3 (a)).
For the example in Figure 3 (see Figure 7), we
relate M (root) to M (b 0 ) with the function F
0ig. Evaluating the function at
yields \Gamma1, which is exactly the value
obtained for M (b 0 ) in Figure 3 (b). The functions F b0
and F a0 are then used to relate M (root) to M (a 1 ),
etc., until a function that relates M (root) to M (t ff ) is
created. In our example, t ff = a 2 and the construction
produces F
We can find the separation between s ff\Gammafi and t ff as
F t ff (0). For our example, we get
where F a2 is evaluated using (3).
3.2 Decomposition
Instead of forming a single function relating
M (root) to M (t ff ), we can perform this construction
in segments, that is, determine the functional relationship
between M (root) and the M-values at some
interior nodes, and compose those functions with the
functions relating the M-values at the interior nodes
with M (t ff ). We will see that this process is akin to
matrix multiplication.
Consider an unfolded process graph used to determine
We decompose the graph into three seg-
ments: an initial segment, R, containing the root
event, a terminal segment, T, containing s ff\Gammafi and
t ff , and an interior segment, S (see Figure 8 (a)).
root
(a)
root
(b)
s
ff\Gammafi+\Omega
ff+\Omega vk
vk
R

Figure

8: Decomposing an unfolded process graph into
segments.
A cutset is a set of event occurrences such that
every path from the root to t ff goes through an element
of the cutset. Let X and Y be two cutsets such that
We say that Y is X shifted to the right by \Omega\Gamma We can
construct a square matrix S that maps the M-values of
the events in X to the M-values of the events in Y , i.e.,
to the same
events\Omega occurrences
later(\Omega ? 0). Simi-
larly, we can construct a matrix R that maps M (root)
to the M-values of the events in X, and a matrix T
that maps the M-values of the events in Y to M (t ff ).
We can now restate the maximum separation problem
in matrix form. Using (
tion, that is, function maximization for scalar addi-
tion, and function composition for scalar multiplica-
tion, we can form RST, a 1 \Theta 1 matrix containing
a single function relating M (root) to M (t ff ), which is
used to obtain \Delta ff .
For the graph in Figure 7, a possible decomposition
is yielding
f 9
Now consider finding
ff+\Omega . We add another S
segment to the graph, defined by the cutsets Y and
Z, where Z is Y shifted to the right
by\Omega (see Figure
8 (b)). We get the matrix product R 0 S 0 ST where
S and T are the same as above, but R 0 and S 0 may differ
from R and S since the m-values are now computed
from s
ff\Gammafi+\Omega instead of s ff\Gammafi . This decomposition is
only useful if we can arrange the symbolic computation
such that R i.e., such that
adding an S segment will not change the functional
representation. The next section characterizes the behavior
of the m-values that allows us to utilize this
decomposition effectively.
3.3 Repetition of the m-values
Since the m-values are constructed from a repetitive
system (the process graph) the values eventually
are determined by the maximum ratio cycles in the
process graph (see [5]). A maximum ratio cycle c is a
cycle with ratio d(c)="(c) equal to that of the maximum
c a simple cycle in G 0
d(c)
"(c)
The m-values repeat precisely when the values for all
events are determined repetitively using maximum ratio
cycles. Formally, there exists integers k ? and " ?
such that for all
is the number of unfoldings of the process
graph (relative to s ff\Gammafi ) before all of the m-values repeat
is the occurrence period of this repetition.
If there are multiple cycles with maximum ratio then
the m-values computed for different events may use
different maximum ratio cycles. Thus, a simple upper
bound on " ? is the least common multiple of "(c) for
each maximum ratio cycle c.

Figure

9 illustrates the behavior of the m-values for
the process graph in Figure 1. Both k ? and " ? are values
specific to a particular process graph. For exam-
ple, changing the delays [4; 10] and [5; 20] to [999,1000]
and [1000,1000], respectively, changes k ? from 3 to
998. Note that only the lower delay bounds affect k ? .
b522

Figure

9: A portion of the unfoldedprocess graph for the
process graph in Figure 1 labeled with m-values (s
which occurs after three unfoldings relative to a 10 , thus
3. The occurrence period of the repetition is one,
making
3.4 Matrices
unfoldings of the process graph, the m-values
are repeating. Let T be the matrix obtained
from the cutsets
the property that the m-values for the vertices topologically
left of X k ? repeat (with an occurrence period
implies that for all edges
topologically left of
This makes the M-values independent of k. There-
fore, after k ? unfolding of the process graph (relative
to s ff\Gammafi ), the functional representations of R and S
remain the same independently of the number of unfoldings

Let the matrix product RT solve \Delta ff ? . We can
find by adding an S segment, i.e., RST. By
repeatedly adding S segments to the graph, we can
compute
T. The
maximum over all n - 0 can be found from
which by matrix algebra can be rewritten as
R (I
where I is the identity matrix. The elements of I,
and 1, are the identity elements for function maximization
and composition, respectively. We have
(note that 0 is
an annihilator for function composition).
A matrix closure algorithm [1] can be used to compute
S   , the middle part of (6), because in this con-
text, function maximization and composition form a
closed semi-ring. This is the key observation that allows
us to implicitly compute an infinite number of
values.
To compute S   we need to be able to compute
the closure of the diagonal elements of S. For
wn ig, the scalar closure operation
can be
efficiently computed by:
ae
where the pairs are ordered as in (4) and w q corresponds
to the first positive l, i.e., l q ? 0 and if q ? 1
then l We can form the closure of an n \Theta n matrix
in O(n 3 ) scalar semi-ring operations
RS   T is used to compute the maximum of the \Delta ff
values for only a subset of the integers ff - max(0; fi).
need only compute the maximum of
a finite number of additional \Delta ff , precisely for those
since RT is used to compute \Delta ff ? . This is
done by applying the finite graph algorithm for each
ff such that max(0; fi) - ff
we need to also compute those ff such that
does not divide ff\Gammaff ? . This can be accomplished by
choosing " ? different initial matrices, named R 0 , R 1 ,
corresponding to 0;
unfoldings of the process graph. Thus we can compute
the maximum of \Delta ff for all ff - ff ? by creating the
function
(R 0
3.5 Example
We now apply the details of the decomposition
method to the example in Figure 1. We decompose
the unfolded process graph into matrices R, S, and T
as shown in Figure 10. The size of the T segment is
determined as k unfoldings relative to the s ff\Gammafi
node, and the size of the S segment is "
ings. The functions in S relate M (a 0 ) and M (b 0 ) to
(b 1 ). For this example
root
R

Figure

10: A decomposed unfolded process graph corresponding
to the process graph in Figure 1.
The closure of S is:
yielding the final product
The maximum separation between a ff\Gamma1 and a ff for
is computed from the function
i.e., yielding
25.
3.6 Efficiency Considerations
There are two potential inefficiencies associated
with this algorithm.
1. depend on the delay ranges and
are not polynomial in the size of the process
graph.
2. The size of the representation of a particular function
may be as large as the number of paths between
the two events related by the function.
Point 1 is potentially serious, however in most process
graphs derived from circuits, "
is more of a concern because it can be large if there exists
a cycle c such that d(c)="(c) is almost equal to r ? .
Although of theoretical interest, point 2 is not likely
to be of practical concern. In practice the functions
can be efficiently pruned and the size of the functions
seems to be linear with respect to the size of the process
graph.
Applications
This section describes two applications demonstrating
the practicality of the algorithm for realistic examples

4.1 Memory Management Unit
Consider an edge u k\Gamma"
in an arbitrary process
graph. If the minimum time separation between
u k\Gamma" and v k is larger than D, event u k\Gamma" will never
constrain the time of event v k , i.e., v k must always
wait for some other event to occur, and the edge from
u k\Gamma" can be removed from the process graph without
changing the behavior of the system.
This idea can be used to remove redundant circuitry
in asynchronous circuits given (conservative) bounds
on the actual delays of a speed-independent design.
Superfluous edges can be removed by analyzing the
process graph corresponding to the circuit. This approach
has been taken by Myers and Meng [8] who use
an inexact timing analysis algorithm, i.e., the algorithm
doesn't necessarily give tight bounds on separation
times. Clearly, being able to obtain tight bounds
potentially enables the removal of more edges.
One of the examples in [8] is a memory management
unit (MMU) designed to interface to the Caltech
Asynchronous Microprocessor [6]. The process
graph (for one of the possible execution modes of the
MMU) consists of 16 events and 23 edges. For the
chosen delay intervals, k Analyzing
the 23 edges using our exact algorithm takes on average
CPU seconds on a SPARC 2 for each edge.
The analysis results in the removal of six edges from
the process graph or equivalently, the removal of six
transistors from the circuit. This is the same result as
in [8].
4.2 Asynchronous Microprocessor
A subset of the Caltech Asynchronous Microprocessor
[6] has been modelled and analyzed using the
techniques described in this paper. The process graph
for this simplified model consists of 60 events and 127
edges, and has " Using our implementation
of the techniques described in the paper,
computations of the instruction fetch cycle period and
the pipeline latency can be performed in under 2 CPU
seconds on a SPARC 2.
These and similar computations can be used to determine
the real-time properties of the asynchronous
microprocessor. For example, to bound the execution
time of a code fragment, we can use the minimum and
maximum separation in cycle period of each instruction
type [9]. Furthermore, this information is useful
when interfacing the microprocessor to an external
synchronous component, especially in cases where the
synchronous component is clocked using a signal produced
by the microprocessor.
5 Conclusion
We have presented an efficient exact solution to
a fundamental problem in circuit synthesis and opti-
mization, namely, the determination of bounds on the
separation in time of events in concurrent systems.
The major contribution of this paper is the structural
decomposition of the infinitely unfolded process graph
that enables it to be implicitly analyzed to obtain the
tightest possible bounds. This aspect of our algorithm
and its algebraic formulation enables it to be efficient
enough for practical use. Furthermore, our algorithm
handles a wide range of process graphs and is thus
useful in a variety of domains.
We are looking into adaptations of this technique to
graphs that include conditional behavior and thus process
an ever-larger class of graphs. This may require
the exploration of tradeoffs between the tightness of
the bounds and computation time that has not been a
concern up to now because of the high efficiency of the
algorithm in practice. In concert with this effort, we
are also investigating other problem domains such as
high-level synthesis and hardware/software co-design
as potential application areas.

Acknowledgments

This work was supported by an NSF PYI Award
(MIP-8858782), an NSF YI Award (MIP-9257987), by
the DARPA/CSTO Microsystems Program under an
ONR monitored contract (N00014-91-J-4041), by an
IBM Graduate Fellowship, and by the Technical University
of Denmark. The authors wish to thank Chris
Myers for several stimulating technical discussions.



--R

The Design and Analysis of Computer Algorithms.
An approach to symbolic timing verification.
Performance Analysis and Optimization of Asynchronous Circuits.
Topics in Algebra.
Combinatorial Optimization: Networks and Matroids.
The design of an asynchronous mi- croprocessor
Algorithms for interface timing verification.
Synthesis of timed asynchronous circuits.
Experiments with a program timing tool based on source-level timing schema
Specification and analysis of timing constraints in signal transition graphs.
--TR

--CTR
Dinesh Ramanathan , Ravindra Jejurikar , Rajesh K. Gupta, Timing driven co-design of networked embedded systems, Proceedings of the 2000 conference on Asia South Pacific design automation, p.117-122, January 2000, Yokohama, Japan
Nicholas H. Zamora , Xiaoping Hu , Radu Marculescu, System-level performance/power analysis for platform-based design of multimedia applications, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.12 n.1, p.2-es, January 2007
Steve Haynal , Forrest Brewer, A model for scheduling protocol-constrained components and environments, Proceedings of the 36th ACM/IEEE conference on Design automation, p.292-295, June 21-25, 1999, New Orleans, Louisiana, United States
Sangyun Kim , Sunan Tugsinavisut , Peter Beerel, Reducing probabilistic timed petri nets for asynchronous architectural analysis, Proceedings of the 8th ACM/IEEE international workshop on Timing issues in the specification and synthesis of digital systems, December 02-03, 2002, Monterey, California, USA
Ali Dasdan , Anmol Mathur , Rajesh K. Gupta, RATAN: A Tool for Rate Analysis and Rate Constraint Debugging for Embedded Systems, Proceedings of the 1997 European conference on Design and Test, p.2, March 17-20, 1997
Anmol Mathur , Ali Dasdan , Rajesh K. Gupta, Rate analysis for embedded systems, Readings in hardware/software co-design, Kluwer Academic Publishers, Norwell, MA, 2001
Anmol Mathur , Ali Dasdan , Rajesh K. Gupta, Rate analysis for embedded systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.3 n.3, p.408-436, July 1998
Tod Amon , Gaetano Borriello , Taokuan Hu , Jiwen Liu, Symbolic timing verification of timing diagrams using Presburger formulas, Proceedings of the 34th annual conference on Design automation, p.226-231, June 09-13, 1997, Anaheim, California, United States
Vijay K. Madisetti , Lan Shen, Interface Design for Core-Based Systems, IEEE Design & Test, v.14 n.4, p.42-51, October 1997
Abhijit Davare , Kelvin Lwin , Alex Kondratyev , Alberto Sangiovanni-Vincentelli, The best of both worlds: the efficient asynchronous implementation of synchronous specifications, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
Peggy B. McGee , Steven M. Nowick , E. G. Coffman, Jr., Efficient performance analysis of asynchronous systems based on periodicity, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 19-21, 2005, Jersey City, NJ, USA
Michael Kishinevsky , Jordi Cortadella , Alex Kondratyev, Asynchronous interface specification, analysis and synthesis, Proceedings of the 35th annual conference on Design automation, p.2-7, June 15-19, 1998, San Francisco, California, United States
Ali Dasdan , Sandy S. Irani , Rajesh K. Gupta, Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems, Proceedings of the 36th ACM/IEEE conference on Design automation, p.37-42, June 21-25, 1999, New Orleans, Louisiana, United States
Yiping Cheng , Da-Zhong Zheng, Min-Max Inequalities and the Timing Verification Problem with Max and Linear Constraints, Discrete Event Dynamic Systems, v.15 n.2, p.119-143, June      2005
R. Marculescu , A. Nandi, Probabilistic application modeling for system-level perfromance analysis, Proceedings of the conference on Design, automation and test in Europe, p.572-579, March 2001, Munich, Germany
Ali Dasdan, Experimental analysis of the fastest optimum cycle ratio and mean algorithms, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.9 n.4, p.385-418, October 2004
Henrik Hulgaard , Steven M. Burns, Bounded Delay Timing Analysis of a Class of CSP Programs, Formal Methods in System Design, v.11 n.3, p.265-294, Oct. 1997
Jeremy Gunawardena, From max-plus algebra to nonexpansive mappings: a nonlinear theory for discrete event systems, Theoretical Computer Science, v.293 n.1, p.141-167, 3 February
discrete event systems;asynchronous systems;concurrent systems;time separation of events;abstract algebra;timing verification