Data path allocation based on bipartite weighted matching

ABSTRACT

We propose a graph-theoretic approach for the data path allocation problem. We decompose the problem into three subproblems: (1) register allocation, (2) operation assignment, and (3) connection allocation. The first two subproblems are modeled as two bipartite weighted matching problems and solved using the Hungarian Method [Pap82]. The third subproblem is solved using a greedy method. While previous researches suffer controversy over which one of subproblems (1) and (2) should be done first, we show that, by taking the other into consideration while performing one, equally satisfactory results can be obtained. We have implemented two programs, LYRA and ARYL, to solve the subproblems in different orders, namely, “(1), (2), then (3)” and “(2), (1), then (3)”, respectively. The matching paradigm allows us to take a more global approach toward the problem than previous researches do. For register allocation, our approach is the first one to guarantee minimal usage of registers while being able to take the interconnection cost into account. For all the benchmarks from the literature, both LYRA and ARYL produced designs as good as, if not better than, those by others in very short time. This research has demonstrated that the bipartite weighted matching algorithm is indeed a very good solution for the data path allocation problem.

REFERENCES

• Dev89: S. Devadas and A. R. Newton, "Algorithms for Hardware Allocation in Data Path Synthesis," IEEE Trans. on CAD of ICAS, vol, CAD-8, no. 7, pp. 768- 781, Jul. 1989.
• Gab82: H. Gabow and O. Kariv, SlAM J. Computer, vol. 11, pp. 117-129, Feb. 1982.
• Gaj88: D. D. Gajsik, editor, Silicon Compilation, Addison- Wesley, 1988.
• Gol80: M. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980.
• Hal35: P. Hall, "On Representatives of Subsets," lournal of London Math. Sot., pp. 26-30, Oct. 1935.
• Har88: B. S. Haroun and M. I. Elmasry, "Automatic Synthesis of a Multi-Bus Architecture for DSP," ICCAD- 88, pp. 44-47, Nov. 1988.
• Has71: Akihiro Hashimoto , James Stevens, Wire routing by optimizing channel assignment within large apertures, Proceedings of the 8th workshop on Design automation, p.155-169, June 28-30, 1971, Atlantic City, New Jersey, United States [doi>10.1145/800158.805069]
• IEE87: IEEE, "IEEE Standard VHDL Language Reference Manual," IEEE std 1076-1987, 1987.
• Kun85: S. Y. Kung , Thomas Kailath , Harper J. Whitehouse, VLSI and Modern Signal Processing, Prentice Hall Professional Technical Reference, 1984
• Kur87: 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]
• Lee89: J-H. Lee, Y-C. Hsu and Y-L. Lin, "A New Integer Linear Programming Formulation for The Scheduling Problem in Data Path Synthesis," ICCAD-89, pp. 20- 23, Nov. 1989.
• Mar86: Peter Marwedel, A new synthesis for the MIMOLA software system, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.271-277, July 1986, Las Vegas, Nevada, United States
• McF88: Michael C. McFarland , Alice C. Parker , Raul Camposano, Tutorial on high-level synthesis, Proceedings of the 25th ACM/IEEE conference on Design automation, p.330-336, June 12-15, 1988, Atlantic City, New Jersey, United States
• Pan88: Barry M. Pangre, Splicer: a heuristic approach to connectivity binding, Proceedings of the 25th ACM/IEEE conference on Design automation, p.536-541, June 12-15, 1988, Atlantic City, New Jersey, United States
• Pap82: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• Par86: Alice C. Parker , Jorge T. Pizarro , Mitch Mlinar, MAHA: a program for datapath synthesis, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.461-466, July 1986, Las Vegas, Nevada, United States
• Par86a: Nohbyung Park , Alice Parker, Sehwa: a program for synthesis of pipelines, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.454-460, July 1986, Las Vegas, Nevada, United States
• Pau86: 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
• Pau89: P. G. Paulin and J. P. Knight, "Force-Directed Scheduling for the Behavioral Synthesis of ASIC's," IEEE Trans. on CAD of ICAS, vol. CAD-8, no. 6, pp. 661-679, Jun. 1989.
• Raj86: V. K. Raj, "Another Automated Data Path Designer," ICCAD-86, pp. 214-217, Nov. 1986.
• Rei77: Edward M. Reingold , Jurg Nievergelt , Narsingh Deo, Combinatorial Algorithms: Theory and Practice, Prentice Hall College Div, 1977
• Tse86: C-J. Tseng and D. P. Siewiorek, "Automated Synthesis of Data Path in Digital Systems," IEEE Trans. on CAD of ICAS, vol. CAD-5, no. 3, pp. 379-395, Jul. 1986.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Data-path design
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

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

General Terms:
Algorithms, Design, Languages, Theory