Functional partitioning improvements over structural partitioning for packaging constraints and synthesis: tool performance

ABSTRACT

Incorporating functional partitioning into a synthesis methodology leads to several important advantages. In functional partitioning, we first partition a functional specification into smaller subspecifications and then synthesize structure for each, in contrast to the current approach of first synthesizing structure for the entire specification and then partitioning that structure. One advantage is the improvement in I/O performance and package count, when partitioning among hardware blocks with size and I/O constraints, such as FPGAs or blocks within an ASIC. A second advantage is reduction in synthesis runtimes. We describe these important advantages, concluding that further research on functional partitioning can lead to inproved results from synthesis environments.

REFERENCES

• 1: S. Antoniazzi , A. Balboni , W. Fornaciari , D. Sciuto, A methodology for control-dominated systems codesign, Proceedings of the 3rd international workshop on Hardware/software co-design, September 22-24, 1994, Grenoble, France
• 2: BRAYTON, R., RUDELL, R., SANGIOVANNI-VINCENTELLI, A., AND WANG, A. 1987. MIS: A multiple-level logic optimization system. IEEE Trans. Comput.-Aided Des. Integr. Circuits 6 (Nov.), 1062-1080.
• 3: CAMPOSANO, R. AND BRAYTON, R. 1987. Partitioning before logic synthesis. In Proceedings of the International Conference on Computer-Aided Design (ICCAD).
• 4: CAMPOSANO, R. AND VAN EIJNDHOVEN, J. 1987. Partitioning a design in structural synthesis. In Proceedings of the International Conference on Computer Design.
• 5: CHEN, Y., HSU, Y., AND KING, C. 1992. MULTIPAR: Behavioral partitioning for synthesizing application-specific multiprocessor architectures. In Proceedings of the European Conference on Design Automation, 14-18.
• 6: CHEN, Y., HSU, Y., AND KING, C. 1994. MULTIPAR: Behavioral partition for synthesizing multiprocessor architectures. IEEE Trans. Very Large Scale Integr. Syst. 2, 1 (Mar.), 21-32.
• 7: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 8: ELES, P., PENG, Z., AND DOBOLI, A. 1992. VHDL system-level specification and partitioning in a hardware/software co-synthesis environment. In Proceedings of the International Workshop on Hardware-Software Co-Design, 49-55.
• 9: Petru Eles , Zebo Peng1 , Krzysztof Kuchcinski , Alexa Doboli, Hardware/Software Partitioning with Iterative Improvement Heuristics, Proceedings of the 9th international symposium on System synthesis, p.71, November 06-08, 1996
• 10: Rolf Ernst , Jorg Henkel , Thomas Benner, Hardware-Software Cosynthesis for Microcontrollers, IEEE Design & Test, v.10 n.4, p.64-75, October 1993 [doi>10.1109/54.245964]
• 11: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
• 12: Daniel D. Gajski , Nikil D. Dutt , Allen C.-H. Wu , Steve Y.-L. Lin, High-level synthesis: introduction to chip and system design, Kluwer Academic Publishers, Norwell, MA, 1992
• 13: Daniel D. Gajski , Frank Vahid , Sanjiv Narayan , Jie Gong, Specification and design of embedded systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 14: Pravil Gupta , Chih-Tung Chen , J. C. DeSouza-Batista , Alice C. Parker, Experience with image compression chip design using unified system construction tools, Proceedings of the 31st annual conference on Design automation, p.250-256, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196367]
• 15: Rajesh K. Gupta , Giovanni De Micheli, Hardware-Software Cosynthesis for Digital Systems, IEEE Design & Test, v.10 n.3, p.29-41, July 1993 [doi>10.1109/54.232470]
• 16: GUPTA, R. AND DEMICHELI, G. 1990. Partitioning of functional models of synchronous digital systems. In Proceedings of the International Conference on Computer-Aided Design, 216-219.
• 17: GUPTA, R. AND DEMICHELI, G. 1992. System-level synthesis using re-programmable components. In Proceedings of the European Conference on Design Automation, 2-7.
• 18: David Harel, Statecharts: A visual formalism for complex systems, Science of Computer Programming, v.8 n.3, p.231-274, June 1, 1987 [doi>10.1016/0167-6423(87)90035-9]
• 19: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
• 20: Hsu, Y., LIu, T., TSAI, F., LIN, S., AND YU, C. 1994. Digital design from concept to prototype in hours. In Proceedings of the Asia-Pacific Conference on Circuits and Systems.
• 21: HWANG, L. AND GAMAL, A. E. 1995. Min-cut replication in partitioned networks. IEEE Trans. CAD 14 (Jan.), 96-106.
• 22: ISMAIL, W. B., O'BRIEN, K., AND JERRAYA, A. 1994. Interactive system-level partitioning with PARTIF. In Proceedings of the European Conference on Design Automation (EURO-DAC '94, Grenoble, France, Sept. 19-23, 1994). IEEE Computer Society Press, Los Alamitos, CA.
• 23: Frank M. Johannes, Partitioning of VLSI circuits and systems, Proceedings of the 33rd annual conference on Design automation, p.83-87, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240535]
• 24: Asawaree Kalavade , Edward A. Lee, A global criticality/local phase driven algorithm for the constrained hardware/software partitioning problem, Proceedings of the 3rd international workshop on Hardware/software co-design, September 22-24, 1994, Grenoble, France
• 25: KERNIGHAN, B. AND LIN, S. 1970. An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. (Feb.).
• 26: KIRKPATRICK, S., GELATT, C. D., JR., AND VECCHI, M. P. 1983. Optimization by simulated annealing. Science 220, 4598 (May), 671-680.
• 27: KIRKPATRICK, Y. AND CHENG, C. 1991. Ratio cut partitioning for heirarchical designs. IEEE Trans. CAD 10, 7 (July), 911-921.
• 28: KRISHNAMURTHY, B.1984. An improved min-cut algorithm for partitioning VLSI networks. IEEE Trans. Comput. (May).
• 29: Kayhan Kükçakar , Alice C. Parker, CHOP: A constraint-driven system-level partitioner, Proceedings of the 28th conference on ACM/IEEE design automation, p.514-519, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127724]
• 30: LAGNESE, E. D. AND THOMAS, D. E. 1991. Architectural partitioning of system level synthesis of integrated circuits. IEEE Trans. CAD 10, 7 (July), 847-860.
• 31: LEE, E. AND MESSERSCHMITT, D. 1987. Synchronous data flow. Proc. IEEE 75, 9, 1235-1245.
• 32: MCFARLAND, M. AND KOWALSKI, W. 1990. Incorporating bottom-up design into hardware synthesis. IEEE Trans. CAD 9, 9 (Sept.).
• 33: L. A. Sanchis, Multiple-Way Network Partitioning, IEEE Transactions on Computers, v.38 n.1, p.62-81, January 1989 [doi>10.1109/12.8730]
• 34: SECHEN, C. AND CHEN, D. 1988. An improved objective function for mincut circuit partitioning. IEEE Trans. CAD.
• 35: TESSIER, R., BABB, J., DAHL, M., HANONO, S., AND AGARWAL, A. 1995. The virtual wires emulation system: A gate-efficient asic prototyping environment. In Proceedings of the Third International ACM Symposium on Field-Programmable Gate Arrays (FPGA '95, Monterey, CA, Feb. 12-14, 1995). ACM Press, New York, NY.
• 36: Donald E. Thomas , Jay K. Adams , Herman Schmit, A Model and Methodology for Hardware-Software Codesign, IEEE Design & Test, v.10 n.3, p.6-15, July 1993 [doi>10.1109/54.232468]
• 37: Frank Vahid, I/O and performance tradeoffs with the FunctionBus during multi-FPGA partitioning, Proceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays, p.27-34, February 09-11, 1997, Monterey, California, United States [doi>10.1145/258305.258309]
• 38: Frank Vahid, Port calling: a transformation for reducing I/O during multi-package functional partitioning, Proceedings of the 10th international symposium on System synthesis, p.107-112, September 17-19, 1997, Antwerp, Belgium
• 39: F. Vahid, Procedure cloning: a transformation for improved system-level functional partitioning, Proceedings of the 1997 European conference on Design and Test, p.487, March 17-20, 1997
• 40: Frank Vahid, Procedure exlining: a transformation for improved system and behavioral synthesis, Proceedings of the 8th international symposium on System synthesis, p.84-89, September 13-15, 1995, Cannes, France [doi>10.1145/224486.224506]
• 41: Frank Vahid , Daniel D. Gajski, Incremental hardware estimation during hardware/software functional partitioning, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.3, p.459-464, Sept. 1995 [doi>10.1109/92.407006]
• 42: F. Vahid , D. D. Gajski, SLIF: a specification-level intermediate format for system design, Proceedings of the 1995 European conference on Design and Test, p.185, March 06-09, 1995
• 43: F. Vahid , D. D. Gajski, Specification partitioning for system design, Proceedings of the 29th ACM/IEEE conference on Design automation, p.219-224, June 08-12, 1992, Anaheim, California, United States
• 44: VAHID, F. AND LE, T. 1997. Extending the Kernighan/Lin heuristic for hardware and software functional partitioning. J. Des. Autom. Embedded Syst. 2, 2, 237-261.
• 45: Frank Vahid , Thuy DM Le, Towards a Model for Hardware and Software Functional Partitioning, Proceedings of the 4th International Workshop on Hardware/Software Co-Design, p.116, March 18-20, 1996
• 46: VAHID, F., NARAYAN, S., AND GAJSKI, D. 1995. SpecCharts: A VHDL front-end for embedded systems. IEEE Trans. CAD, 694-706.
• 47: Frank Vahid , Linus Tauro, An Object-Oriented Communication Library for Hardware-Software CoDesign, Proceedings of the 5th International Workshop on Hardware/Software Co-Design, p.81, March 24-26, 1997
• 48: Xun Xiong , Edna Barros , Wolfgang Rosenstiel, A method for partitioning UNITY language in hardware and software, Proceedings of the conference on European design automation, p.220-225, September 19-23, 1994, Grenoble, France
• 49: IEEE STANDARDS OFFICE, 1988. IEEE Standard VHDL Language Reference Manual. IEEE Standards Office, New York, NY.

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; Hardware description languages

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

General Terms:
Design

Keywords:
behavioral synthesis, functional partitioning, system-level design