کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
424192 685354 2008 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Time Separation of Events: An Inverse Method
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Time Separation of Events: An Inverse Method
چکیده انگلیسی

The problem of “time separation” can be stated as follows: Given a system made of several connected components, each one entailing a local delay known with uncertainty, what is the maximum time for traversing the global system? This problem is useful, e.g. in the domain of digital circuits, for determining the global traversal time of a signal from the knowledge of bounds on the component propagation delays. The uncertainty on each component delay is given under the form of an interval. The general problem is NP-complete. We focus here on the inverse problem: we seek intervals for component delays for which the global traversal time is guaranteed to be no greater than a specified maximum. We give a polynomial time method to solve it. As a typical application, we show how to use the method in order to relax some specified local delays while preserving the maximum traversal time. This is especially useful, in the area of digital circuits, for optimizing “setup” timings of input signals (minimum timings required for stability).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Theoretical Computer Science - Volume 209, 24 April 2008, Pages 135-148