کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419119 | 681743 | 2007 | 11 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: The delay of circuits whose inputs have specified arrival times The delay of circuits whose inputs have specified arrival times](/preview/png/419119.png)
Let C be a circuit representing a straight-line program on n inputs x1,x2,…,xnx1,x2,…,xn. If for 1⩽i⩽n1⩽i⩽n an arrival time ti∈N0ti∈N0 for xixi is given, we define the delay of xixi in C as the sum of titi and the maximum number of gates on a directed path in C starting in xixi. The delay of C is defined as the maximum delay of one of its inputs.The notion of delay is a natural generalization of the notion of depth. It is of practical interest because it corresponds exactly to the static timing analysis used throughout the industry for the analysis of the timing behaviour of a chip. We prove a lower bound on the delay and construct circuits of close-to-optimal delay for several classes of functions. We describe circuits solving the prefix problem on n inputs that are of essentially optimal delay and of size O(nlog(logn))O(nlog(logn)). Finally, we relate delay to formula size.
Journal: Discrete Applied Mathematics - Volume 155, Issue 10, 15 May 2007, Pages 1233–1243