Record Details

Efficient algorithms for approximate time separation of events

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Efficient algorithms for approximate time separation of events
 
Creator CHAKRABORTY, S
DILL, DL
YUN, KY
 
Subject interface timing verification
asynchronous circuits
performance analysis
systems
asynchronous systems
timing analysis and verification
approximate algorithms
convex approximation
time separation of events
bounded delay timing analysis
 
Description Finding bounds on time separation of events is a fundamental problem in the verification and analysis of asynchronous and concurrent systems. Unfortunately, even for systems without repeated events or choice, computing exact bounds on time separation of events is an intractable problem when both min and max type timing constraints are present. In this paper, we describe a method for approximating min and max type constraints, and develop a polynomial-time algorithm for computing approximate time separation bounds in choice-free systems without repeated events. Next, we develop a pseudo-polynomial time technique for analysing a class of asynchronous systems in which events repeat over time. Unlike earlier works, our algorithms can analyse systems with both min and max type timing constraints efficiently. Although the computed bounds are conservative in the worst-case, experimental results indicate that they are fairly accurate in practice. We present formal proofs of correctness of our algorithms, and demonstrate their efficiency and accuracy by applying them to a suite of benchmarks. A complete asynchronous chip has been modelled and analysed using the proposed technique, revealing potential timing problems (already known to designers) in the datapath design.
 
Publisher INDIAN ACADEMY SCIENCES
 
Date 2011-08-02T02:30:26Z
2011-12-26T12:53:38Z
2011-12-27T05:40:18Z
2011-08-02T02:30:26Z
2011-12-26T12:53:38Z
2011-12-27T05:40:18Z
2002
 
Type Article
 
Identifier SADHANA-ACADEMY PROCEEDINGS IN ENGINEERING SCIENCES, 27(), 129-162
0256-2499
http://dx.doi.org/10.1007/BF02717181
http://dspace.library.iitb.ac.in/xmlui/handle/10054/8627
http://hdl.handle.net/10054/8627
 
Language en