Keywords:-
Article Content:-
Abstract
In VLSI circuit design, graph algorithms are widely used and graph structure can model many problems. As technology continues to scale into nanometer design, the effects of process variation become more crucial and design parameters also change. Hence, taking stochastic variations into account, probability distributions are used as edge weights to form statistical graph structures. General applications in VLSI circuit design, such as timing analysis, buffer insertion, and maze routing, can be formulated as shortest path problems using a statistical graph model. The solution of any such graph problem will surely have a
statistical distribution for its cost function value. The mean and variance, square of standard deviation, values are used as a pair of weight values on a graph to represent the stochastic distribution on each edge. For the stochastic shortest path problem, we observe that the objective functions can be formulated using mean and standard deviation values of the resulting probability distribution and general cost functions are nonlinear. To solve for the nonlinear cost function, we intentionally insert a constraint on the variance. Several candidate paths will be achieved by varying the bound value on the constraint. With fixed
bound value, the Lagrangian relaxation method is applied to find the feasible solution to the constrained shortest path problem. During Lagrangian relaxation, a feasible solution close to the optimal is achieved through subgradient optimization. Among the candidate paths obtained, the best solution becomes the ultimate solution of our algorithm for the original cost function under parameter variation. The algorithm presented in this work can handle any graph structures, arbitrary edge weight distributions and general cost functions.
References:-
References
S. Borkar, T. Karnik, S. Narendra, J. Tschanz, A. Keshavarzi, and V. De, “Parameter
variations and impact on circuits and microarchitecture,” in
Proceedings of the 40th Design Automation Conference, 2003, pp. 338-342.
Incentia Design Systems, Inc., “Advanced On-chip-variation Timing Analysis for
Nanometer Designs,” Tech. Rep., Jun. 2007.
T. Karni, S. Borkar, and V. De, “Sub-90nm technologies—Challenges and
opportunities for CAD,” in Proceedings of the International Conference on Computer
Aided Design, 2002, pp. 203-206.
D. Pham, S. Asano, M. Bolliger, M. N. Day, H. P. Hofstee, C. Johns, J. Kahle, A.
Kameyama, J. Keaty, Y. Masubuchi, M. Riley, D. Shippy, D. Stasiak, M. Suzuoki, M.
Wang, J. Warnock, S. Weitzel, D. Wendel, T. Yamazaki, and K 6. Yazawa, “The design and implementation of a first-generation CELL
processor,” in Proceedings of the International Solid-State Circuits Conference,
, pp. 184-186. 7. N. H. Chang, V. Kanevsky, O. S. Nakagawa, and S. Y. Oh, “Method and system for
determining statistically based worst-case on-chip interconnect delay and crosstalk,”
U.S. Patent 6,018,623, Jan. 25, 2000.
E. W. Dijkstra, “A note on two problems in connection with graphs,” Numerische
Mathematik , vol. 1, pp. 269-271, 1959.
R. E. Bellman, “On a routing problem,” Quarterly of Applied Mathematics, vol. 16,
no. 1, pp. 87-90, 1958.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms.
nd ed. Cambridge, MA: The MIT Press, McGraw-Hill, 2001.
H. Frank, “Shortest paths in probabilistic graphs,” Operations Research, vol. 17, no. 4,
pp. 583-599, Jul.-Aug. 1969. 12. C. E. Sigal, A. A. B. Pritsker, and J. J. Solberg, “The stochastic shortest
route problem,” Operations Research Society of America, vol. 28, no. 5, pp. 1122-
, Sep.-Oct. 1980.
R. P. Loui, “Optimal paths in graphs with stochastic or multidimensional weights,”
Communications of the ACM, vol. 26, no. 9, pp. 670-676, Sep. 1983.
Murthy and S. Sarkar, “Stochastic shortest path problems with piecewise-linear
concave utility functions,” Management Science, vol. 44, no. 11, pp. S125-S136, Nov.
R. Hall, “The fastest path through a network with random time-dependent travel time,”
Transportation Science, vol. 20, no. 3, pp. 182-188, Aug. 1986. 17. L. Fu and L. R. Rilett, “Expected shortest paths in dynamic and stochastic
traffic networks,” Transportation Research, vol. 32, no. 7, pp. 499-516, Sep.
[15] X. Ji, “Models and algorithm for stochastic shortest path problem,”
Applied Mathematics and Computation, vol. 170, no. 1, pp. 503-514, Nov.
L. Deng and M. D. F. Wong, “An exact algorithm for the statistical shortest
path problem,” in Proceedings of the Asia and South Pacific Design
Automation Conference (ASP-DAC), 2006, pp. 965-970.
Y. P. Aneja and K. P. K. Nair, “The constrained shortest path problem,” 22. Naval Research Logistics Quarterly, vol. 25, no. 3, pp. 549-555, 1978.
X. Cai, T. Kloks, and C. K. Wong, “Time-varying shortest path problems with
constraints,” Networks, vol. 29, no. 3, pp. 141-150, Dec. 1998.
R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows, Theory,
Algorithms, and Applications. Upper Saddle River, NJ: Prentice Hall, 1993.
D. P. Bertsekas, Nonlinear Programming. Belmont, MA: Athena Scientific,