Provably efficient algorithms for resolving temporal and spatial difference constraint violations

ABSTRACT

A system of difference constraints is a formal model of temporal and spatial constraints in many areas such as scheduling, constraint satisfaction, and layout compaction. During construction of such a system, constraint violations often arise, and they need to be resolved. Previous algorithms for this task fall into two groups: those algorithms that are fast but cannot resolve all violations, and those algorithms that can resolve all violations but are exponentially slow. We propose the first algorithms that are fast as well as able to resolve all violations. Moreover, unlike the previous algorithms, our algorithms support the ordering of violations using their inherent criticality or user-defined priority. We provably and experimentally justify the efficiency and efficacy of our algorithms.

REFERENCES

• 1: Charles J. Alpert, The ISPD98 circuit benchmark suite, Proceedings of the 1998 international symposium on Physical design, p.80-85, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274546]
• 2: Bacelli, F., Cohen, G., Olsder, G. J., and Quadrat, J.-P. 1992. Synchronization and Linearity. John Wiley & Sons, New York, NY.
• 3: Borriello, G. 1991. Specification and synthesis of interface logic. In High-Level VLSI Synthesis, R. Camposano and W. Wolf, Eds. Kluwer Academic Publ., Chapter 7, 153--176.
• 4: Brzozowski, J. A., Gahlinger, T., and Mavaddat, F. 1991. Consistency and satisfiability of waveform timing specifications. Networks 21, 91--107.
• 5: Candan, K. S., Prahjakaran, B., and Subrahmanian, V. S. 1998. Collaborative multimedia documents: Authoring and presentation. Int. J. Intell. Syst. Multimedia Comput. Syst. 13, 12.
• 6: Boris V. Cherkassky , Andrew V. Goldberg, Negative-Cycle Detection Algorithms, Proceedings of the Fourth Annual European Symposium on Algorithms, p.349-363, September 25-27, 1996
• 7: Boris V. Cherkassky , Andrew V. Goldberg , Tomasz Radzik, Shortest paths algorithms: theory and experimental evaluation, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.516-525, January 23-25, 1994, Arlington, Virginia, United States
• 8: Pai Chou , Gaetano Borriello, Software scheduling in the co-synthesis of reactive real-time systems, Proceedings of the 31st annual conference on Design automation, p.1-4, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196247]
• 9: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 10: Ali Dasdan , Rajesh K. Gupta, Timing analysis of embedded real-time systems, University of Illinois at Urbana-Champaign, Champaign, IL, 1999
• 11: Ali Dasdan, Efficient algorithms for debugging timing constraint violations, Proceedings of the 8th ACM/IEEE international workshop on Timing issues in the specification and synthesis of digital systems, December 02-03, 2002, Monterey, California, USA [doi>10.1145/589411.589423]
• 12: Ali Dasdan, A strongly polynomial-time algorithm for over-constraint resolution: efficient debugging of timing constraint violations, Proceedings of the tenth international symposium on Hardware/software codesign, May 06-08, 2002, Estes Park, Colorado [doi>10.1145/774789.774816]
• 13: Ali Dasdan, Experimental analysis of the fastest optimum cycle ratio and mean algorithms, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.9 n.4, p.385-418, October 2004 [doi>10.1145/1027084.1027085]
• 14: Dasdan, A. and Gupta, R. K. 1998. Faster maximum and minimum mean cycle algorithms for system performance analysis. IEEE Trans. Comput.-Aid. Des. 17, 10, 889--899.
• 15: Rina Dechter , Itay Meiri , Judea Pearl, Temporal constraint networks, Artificial Intelligence, v.49 n.1-3, p.61-95, May 1991 [doi>10.1016/0004-3702(91)90006-6]
• 16: Do, J. and Dawson, W. 1985. SPACER II: A well-behaved IC layout compactor. In Proceedings of VLSI International Conference 283--291.
• 17: Peter Eades , Xuemin Lin , W. F. Smyth, A fast and effective heuristic for the feedback arc set problem, Information Processing Letters, v.47 n.6, p.319-323, Oct. 18, 1993 [doi>10.1016/0020-0190(93)90079-O]
• 18: Festa, P., Pardalos, P. M., and Resende, M. G. C. 2001. Feedback set problems. In Encyclopedia of Optimization. Vol. 2. Kluwer Academic Publishers, Chapter 7, 94--106.
• 19: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 20: Sabih H. Gerez, Algorithms for VLSI Design Automation, John Wiley & Sons, Inc., New York, NY, 1999
• 21: Ishima, K., Tsukiyama, S., and Shinoda, S. 1990. An algorithm to detect positive cycles in a constraint graph for layout compaction. In Proceedings of the IEEE International Symposium on Circuits and Systems. 2853--2856.
• 22: F Jahanian , A K Mok, Safety analysis of timing properties in real-time systems, IEEE Transactions on Software Engineering, v.12 n.9, p.890-904, Sept. 1986
• 23: Johnson, D. B. 1975. Finding all the elementary circuits of a directed graph. SIAM J. Comput. 4, 1, 77--84.
• 24: Christopher Kingsley, A hiererachical, error-tolerant compactor, Proceedings of the 21st conference on Design automation, p.126-132, June 25-27, 1984, Albuquerque, New Mexico, United States
• 25: Ku, D. C. and Micheli, D. D. 1992. Relative scheduling under timing constraints: Algorithms for high-level synthesis of digital circuits. IEEE Trans. Comput.-Aid. Des. 11, 6, 696--718.
• 26: Liao, Y.-Z. and Wong, C. K. 1983. An algorithm to compact a VLSI symbolic layout with mixed constraints. IEEE Trans. Comput.-Aid. Des. 2, 2, 62--69.
• 27: Jinfeng Liu , Pai H. Chou , Nader Bagherzadeh , Fadi Kurdahi, A constraint-based application model and scheduling techniques for power-aware systems, Proceedings of the ninth international symposium on Hardware/software codesign, p.153-158, April 2001, Copenhagen, Denmark [doi>10.1145/371636.371707]
• 28: Tai Ly , David Knapp , Ron Miller , Don MacMillen, Scheduling using behavioral templates, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.101-106, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217514]
• 29: Mateti, P. and Deo, N. 1976. On algorithms for enumerating all circuits of a graph. SIAM J. Comput. 5, 1, 90--98.
• 30: Anmol Mathur , Ali Dasdan , Rajesh K. Gupta, Rate analysis for embedded systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.3 n.3, p.408-436, July 1998 [doi>10.1145/293625.293631]
• 31: Mlynski, D. A. and Sung, C.-H. 1986. Layout compaction. In Layout Design and Verification, T. Ohtsuki, Ed. Elsevier Science, Chapter 6, 199--235.
• 32: A. K. Mok , Duu-Chung Tsou , R. C. M. de Rooij, The MSP.RTL real-time scheduler synthesis tool, Proceedings of the 17th IEEE Real-Time Systems Symposium, p.118, December 04-06, 1996
• 33: Nestor, J. A. and Krishnamoorthy, G. 1993. SALSA: A new approach to scheduling with timing constraints. IEEE Trans. Comput.-Aid. Des. 12, 8, 1107--1122.
• 34: Raju, S. C. V., Rajkumar, R., and Jahanian, F. 1992. Monitoring timing constraints in distributed real-time systems. In Proceedings of the IEEE Real-Time Systems Symposium. 57--67.
• 35: Sarikaya, B. 2000. Notes on multimedia synchronization. Unpublished, Univ. of Northern British Columbia.
• 36: W. L. Schiele, Compaction with incremental over-constraint resolution, Proceedings of the 25th ACM/IEEE conference on Design automation, p.390-395, June 12-15, 1988, Atlantic City, New Jersey, United States
• 37: Jian-Feng Shi , Liang-Fang Chao, Resource-Constrained Algebraic Transformation for Loop Pipelining, Proceedings of the 6th Great Lakes Symposium on VLSI, p.14, March 22-23, 1996
• 38: Tsang, E. 1993. Foundations of Constraint Satisfaction. Academic Press, San Diego, CA.
• 39: Ti-Yen Yen , Wayne Wolf, An efficient graph algorithm for FSM scheduling, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.4 n.1, p.98-112, March 1996 [doi>10.1109/92.486084]
• 40: Young, N. E., Tarjan, R. E., and Orlin, J. B. 1991. Faster parametric shortest path and minimum-balance algorithms. Networks 21, 205--221.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Automatic synthesis; Optimization
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis; Optimization

General Terms:
Algorithms, Performance

Keywords:
Behavioral synthesis, constraint satisfaction, interface timing, layout compaction, multimedia synchronization, rate analysis, real-time systems, scheduling, timing constraints