We extend the time separations of events (TSE) timing analysis algorithm into the symbolic domain, that is, we allow symbolic variables to be used to specify unknown parameters of the model (essentially, unknown delays) and verification algorithms which are capable of identifying not just failure or success, but also the constraints on these symbolic variables which will ensure successful verification. The two contributions are (1) an iterative algorithm which continuously narrows down the domain of interest and (2) a practical method for reducing the representation of symbolic expressions containing minimizations and maximizations defined for a given domain. The algorithm applies to asynchronous circuits without conditional behavior. Although this may seem a severe restriction, this is a large and useful subclass which includes, e,g,, pipeline structures. We report experimental results for several asynchronous circuits to demonstrate that symbolic analysis is feasible and that the output provided is what a designer (or perhaps a synthesis tool) would often want to know.

Solutions to timing relationship analysis problems are often reported using symbolic variables and inequalities which specify linear relationships between the variables. Complex relationships can be expressed using Presburger formulas which allow Boolean relations to be specified between the inequalities. This paper develops and applies a highly effective simplification approach for Presburger formulas based on logic minimization techniques.

We present a novel set of tools for performing symbolic timing verificationof timing diagrams. The tools are multi-purpose with usesin verification, derivation of synthesis constraints, and design evaluation.Our methodology is based on using techniques for manipulatingPresburger formulas. We demonstrate using several interestingexamples that the method is efficient in practice and should beconsidered for inclusion in commercial tools.

Determining 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.>

Determining the time separation of events is a fundamental problem in the analysis, synthesis, and optimization of concurrent systems. We present results of applying an efficient algorithm to solve this problem of three different application domains. These are: analysis of instruction execution times of an asynchronous multiprocessor, analysis of a high-performance mixed asynchronous/synchronous communication interface, and isochronic fork analysis in asynchronous circuit synthesis. The algorithm we use yields exact (tight) bounds on the separation time of events in an arbitrary process graph without conditional behavior. This class of graphs is quite large and includes graphs that are not strongly connected. The algorithm is based on a functional decomposition technique that permits the implicit evaluation of an infinitely unfolded process graph.

Determining 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. The algorithm is based on a functional decomposition technique that permits the implicit evaluation of an infinitely unfolded process graph.>

Article Free Access Share on OEsim: a simulator for timing behavior Authors: Tod Amon Department of Computer Science and Engineering, University of Washington, Seattle, WA Department of Computer Science and Engineering, University of Washington, Seattle, WAView Profile , Gaetano Borriello Department of Computer Science and Engineering, University of Washington, Seattle, WA Department of Computer Science and Engineering, University of Washington, Seattle, WAView Profile Authors Info & Claims DAC '91: Proceedings of the 28th ACM/IEEE Design Automation ConferenceJune 1991 Pages 656–661https://doi.org/10.1145/127601.127746Published:01 June 1991Publication History 7citation138DownloadsMetricsTotal Citations7Total Downloads138Last 12 Months2Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In synthesizing a circuit from its description in a concurrent programming language, it is necessary to make decisions about how to implement synchronization constructs such as send and receive statements.The semantic model of these constructs is an infinite length FIFO queue that can handle all send events until they are paired up with corresponding receive events.In this paper, we describe an algorithm to size these synchronization queues while permitting the maximum parallelism between the communicating processes (circuits).It is an example of higher level synthesis in that the user does not include an explicit description of the queue in the specification as is necessary in current high level synthesis systems.I.