A flexible datapath allocation method for architectural synthesis

ABSTRACT

We present a robust datapath allocation method that is flexible enough to handle constraints imposed by a variety of target architectures. Key features of this method are its ability to handle accurate modeling of datapath units and the simultaneous optimization of direct objective functions. The proposed method consists of a new binding model construction scheme and an optimization technique based on simulated annealing. To illustrate the flexibility of this method, two datapath allocation procedures have been developed for two problem enviroments: (1) a procedure that incorporates interconnection area and delay estimates, where floor-planning is tightly integrated into datapath allocation; and (2) a procedure that handles registers, register files, and multiport memories for data storage, as well as random and linear topologies for interconnection architectures. Results from these two applications show our method produces competitive designs for benchmark circuits, as well as being flexible enough to be used for a variety of different domains.

REFERENCES

• 1: AHMAD, I. AND CHEN, C. Y. R. 1991. Post-processor for data path synthesis using multiport memories. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD '91, Santa Clara, CA, Nov. 11-14) IEEE Computer Society Press, Los Alamitos, CA, 276-279.
• 2: BALAKRISHNAN, M., BANERJI, D. K., MAJUMDAR, A. K., LINDERS, J. G., AND MAJITHIA, J. C. 1990. Allocation of multiport memories in data path synthesis. IEEE Trans. Comput.- Aided Des. 7, 4 (Apr. 1990), 536-540.
• 3: CHOI, K. 1995. A robust architectural synthesis method for realistic system design. Ph.D. Dissertation. Dept. of Electrical Engineering, University of Pittsburgh.
• 4: DEVADAS, S. AND NEWTON, R. 1989. Algorithms for hardware allocation in data path Synthesis. IEEE Trans. Comput.-Aided Des. 8, 7 (Jul. 1989), 768-781.
• 5: DUNLOP, A. E. AND KERNIGHAN, B. W. 1985. A procedure for placement of standard-cell VLSI circuits. IEEE Trans. Comput.-Aided Des. 4, 1 (Jan. 1985), 92-98.
• 6: Yung-Ming Fang , D. F. Wong, Simultaneous functional-unit binding and floorplanning, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.317-321, November 06-10, 1994, San Jose, California, United States
• 7: Daniel D. Gajski , Frank Vahid , Sanjiv Narayan , Jie Gong, Specification and design of embedded systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 8: GEBOTYS, C. H. AND ELMASRY, M. I. 1993. Global optimization approach for architectural synthesis. IEEE Trans. Comput.-Aided Des. 12, 9, 1266-1278.
• 9: HAROUN, B. S. AND ELMASRY, M. I. 1989. Architectural synthesis for DSP silicon compilers. IEEE Trans. Comput.-Aided Des. 8, 4 (Apr. 1989), 431-447.
• 10: HSIEH, Y.-W., LEVITAN, S. P, AND PANGRLE, B. M. 1993. Incorporating interconnection delays in VHDL behavioral synthesis. In Proceedings of the 4th on ACM/SIGDA Physical Design Workshop 175-186.
• 11: HUANG, M. D., ROMEO, F., AND SANGIOVANNI-VINCENTELLI, A. 1986. An efficient general cooling schedule for simulated annealing.In Proceedings of the International Conference on Computer-Aided Design 381-384.
• 12: Hyuk-Jae Jang , Barry M. Pangrle, A grid-based approach for connectivity binding with geometric costs, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.94-99, November 07-11, 1993, Santa Clara, California, United States
• 13: KERNIGHAN, B. AND LIN, S. 1970. An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. (Feb.).
• 14: Taewhan Kim , C. L. Liu, Utilization of multiport memories in data path synthesis, Proceedings of the 30th international conference on Design automation, p.298-302, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164900]
• 15: KIRKPATRICK, S., GELATT, C. D., JR., AND VECCHI, M. P. 1983. Optimization by simulated annealing. Science 220, 4598 (May), 671-680.
• 16: David W. Knapp, Datapath optimization using feedback, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
• 17: G. Krishnamoorthy , J. A. Nestor, Data path allocation using an extended binding model, Proceedings of the 29th ACM/IEEE conference on Design automation, p.279-284, June 08-12, 1992, Anaheim, California, United States
• 18: F. J. Kurdahi , A. C. Parker, REAL: a program for REgister ALlocation, Proceedings of the 24th ACM/IEEE conference on Design automation, p.210-215, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37920]
• 19: LINDO, 19XX. Linear interactive and discrete optimizer for linear, integer, and quadratic programming problems. LINDO Systems, Inc..
• 20: Tai A. Ly , W. Lloyd Elwood , Emil F. Girczyc, A generalized interconnect model for data path synthesis, Proceedings of the 27th ACM/IEEE conference on Design automation, p.168-173, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123248]
• 21: LY, T. AND MOWCHENKO, g. 1993. Applying simulated evolution to high level synthesis. IEEE Trans. Comput.-Aided Des. 12, 3 (Mar. 1993), 389-409.
• 22: MCFARLAND, M. C. AND KOWALSKI, T. J. 1990. Incorporating bottom-up design into hardware synthesis. IEEE Trans. Comput.-Aided Des. 9, 9 (Sept. 1990), 938-950.
• 23: MCFARLAND, M. C. AND PARKER, A. C. 1990. The high-level synthesis of digital systems. IEEE Computer 78, 2 (Feb. 1990), 301-317.
• 24: NESTOR, J. A. AND KRISHNAMOORTHY, G. 1992. SALSA: A new approach to scheduling with timing constraints. IEEE Trans. Comput.-Aided Des. 12, 8 (Aug.), 1107-1122.
• 25: PANGRLE, B. M. AND GAJSKI, D. D. 1987. Slicer: A state synthesizer for intelligent silicon compilation. In Proceedings of the International Conference on Computer-Aided Design (ICCAD) 42-45.
• 26: C. A. Papachristou , H. Konuk, A linear program driven scheduling and allocation method followed by an interconnect optimization algorithm, Proceedings of the 27th ACM/IEEE conference on Design automation, p.77-83, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123231]
• 27: P. G. Paulin , J. P. Knight , E. F. Girczyc, HAL: a multi-paradigm approach to automatic data path synthesis, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.263-270, July 1986, Las Vegas, Nevada, United States
• 28: PAULIN, P. G. AND KNIGHT, J. P. 1989. Force-directed scheduling for the behavioral synthesis of ASICs. IEEE Trans. CAD 8, 6 (June 1989), 661-679.
• 29: PAULIN, P. G. AND KNIGHT, J. P. 1989. High-level synthesis benchmark results using a global scheduling algorithm. In Logic and Architecture Synthesis for Silicon Compilers North-Holland Publishing Co., Amsterdam, The Netherlands, 211-228.
• 30: C. Ramachandran , F. J. Kurdahi , D. D. Gajski , A. C.-H. Wu , V. Chaiyakul, Accurate layout area and delay modeling for system level design, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.355-361, November 1992, Santa Clara, California, United States
• 31: RIM, M., MUJUMDAR, A., JAIN, R., AND DE LEONE, R. 1994. Optimal and heuristic algorithms for solving the binding problem. IEEE Trans. Very Large Scale Integr. Syst. 2, 2 (June 1994), 211-225.
• 32: TSAI, F. S. AND HSU, Y. C. 1992. An automatic data path allocator. IEEE Trans. Comput.-Aided Des. 11, 9 (Sep. 1992), 1053-1064.
• 33: TSENG, C. AND SIEWIOREK, D. P. 1986. Automated synthesis of data paths in digital systems. IEEE Trans. Comput.-Aided Des. 5, 3 (July 1986), 379-395.
• 34: Jen-Pin Weng , Alice C. Parker, 3D scheduling: high-level synthesis with floorplanning, Proceedings of the 28th conference on ACM/IEEE design automation, p.668-673, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127748]
• 35: WHITE, S. R. 1984. Concepts of scale in simulated annealing. In Proceedings of the International Conference on Computer Design (ICCD '84) 646-651.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Automatic synthesis

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Optimization
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

Keywords:
allocation and binding, high-level synthesis