Open Access Open Access  Restricted Access Subscription or Fee Access

High Level Synthesis of Data Flow Graphs Using Integer Linear Programming

S. Anbuyazhini, D.S. Harishram

Abstract


This paper seeks to investigate integer linear programming (ILP) methodologies for power optimization during high level synthesis (HLS). There are three basic steps in high level synthesis. They are scheduling, binding and allocation. Here power aware scheduling and binding are considered. Integer linear programming has been widely investigated for solving scheduling and binding problems. The major issues encountered in ILP like scalability and use of heuristics to enhance the computational efficiency will be addressed. To devise the ILP, constraints are specified by means of matrices that are consequential from the data flow graph (DFG) and switching activity information. A data flow graph is given as the input. From that DFG, two matrices are generated based on the intra and inter iteration precedence of the nodes. Another input matrix is also derived from the data flow graph based on the switching activity information. Constraints related to time steps at which nodes in the DFG are to be executed are specified by means of inequalities. All input matrices required for the ILP Formulation are generated using C with the data flow graph as input. FICO Xpress optimization suite is used for executing the ILP.

Keywords


Design, Optimization, Integer Linear Programming (ILP), High Level Synthesis (HLS), Data Flow Graph (DFG)

Full Text:

PDF

References


Sadiq M.Sait, Habib Youssef, ―VLSI Physical Design Automation theory and practice‖, IEEE Press, New York, 1995.

Sabih H. Gerez, ―Algorithms for VLSI Design Automation‖, ohn Wiley & Sons Ltd, England, 1999.

Keshab K. Parhi, ―VLSI Digital Signal Processing Systems, Design and Implementation‖, 2008.

www.globalshiksha.com

Xiaoyong Tang, Tianyi Jiang, Alex Jones and Prith Banerjee, ―Behavioral Synthesis of Data-Dominated Circuits for Minimal Energy Implementation,‖ IEEE Conf. Comput.-Aided Design Integr. Circuits Syst., vol. 17, no. 10, pp. 974–984, 2008.

Dash Company, ―www.dashoptimization.com‖, XPRESS-MP, 2003.

K.S. Khouri, G. Lakshminarayana, and N.K. Jha, ―IMPACT: A High-Level Synthesis System for Low Power Control-Flow Intensive Circuits‖, IEEE Conf, Design Automation and Test in System, 1998.

Perry Gray, William Hart, Laura Painton, Cindy Phillips, Mike Trahan, John Wagner, ―A Survey of global optimization problems‖, Sandia national laboratories,Albuquerque,1997.

V. Raghunathan, S. Ravi, A. Raghunathan, and G. Lakshminarayana,―Transient power management through high level synthesis,‖ in Proc.Intl. Conf. Computer Aided Design, pp. 545–552, 2001.

Azadeh davoodi and Ankur srivastava, ―Effective Techniques for the Generalized Low-Power Binding problem‖, ACM Trans, Design Automation of Electronic Systems .,vol 11, no. 1, pp 52-69,2006.

W.T. Shiue and C. Chakrabarti, "Low Power Scheduling with Resources Operating at Multiple Voltages," IEEE Trans. on Circuit and Systems Part II: Analog and Digital Signal Processing, vol. 47, no. 6, pp. 536-543, June 2000.

T.C. Wilson, G. W. Grewal, and D. K, Banerji, ―An ILP Solution for Simultaneous Scheduling, Allocation, and Binding in Multiple Block Synthesis‖, ICCD, 1994.

J. Monteiro, S. Devadas, P. Ashar and A. Mauskar,―Scheduling Techniques to Enable Power Management‖, Proc. of IEEE/ACM Design Automation Conference, pp. 349—352,1996.

C. Chen and M. Sarrafzadeh, ―Power-Manageable Scheduling Technique for Control Dominated High-Level Synthesis‖, Proc. of IEEE Design, Automation, and Test in Europe Conference and Exhibition, pp. 1016—1020, 2002.

F. Gruian and K. Kuchcinski, ―Operation Binding and Scheduling for Low Power Using Constraint Logic Programming,‖ 24th Euro Micro Conf., Aug. 1998.

A. Raghunathan and N.K. Jha, ―An ILP formulation for low power based on minimizing switched capacitance during data path allocation,‖ ISCS, 1995.

[S. Chaudhuri and R. A. Walker. ILP-based scheduling with time andresource constraints in high level synthesis. In VLSI Design, pages 17–20, 1994.

W. L. Hung, X. Wu, and Y. Xie. Guaranteeing performance yield in high-level synthesis. In ICCAD, pages 303–309, 2006.

J. Jung and T. Kim. Timing variation-aware high-level synthesis. In ICCAD, 2007.

C. Guret, C. Prins, and M. Sevaux. Applications of optimization with Xpress-MP. Dash Optimization Ltd., 2000.

B. Radhakrishnan and M. Venkatesan, ―MultipleVoltage and Frequency Scheduling for Power Minimization,‖ in Proc. Euromicro Symp. on Digital System Design, pp. 279-285, Sep. 2003.

A. K. Allam and J. Ramanujam, ―Modified Force Directed Scheduling for Peak and Average Power Optimization Using Multiple Supply Voltages,‖International Conference on IC Design andTechnology (ICICDT), Padova, Italy, May 2006.

S. Gupta and S. Katkoori,―Force-Directed Scheduling for Dynamic Power Optimization,‖ in Proc. IEEE Computer Society Annual Symposium on VLSI, pp. 68-73, 2002.

A. Manzak and C. Chakrabarti, ―A Low PowerScheduling Scheme with Resources Operating at Multiple Voltages.‖ IEEE Trans. on VLSI Systems, vol.10, No 1, pp. 6-14, Feb. 2002.

N. Chabini, I. Chabini, E.-M. Aboulhamid, and Y.Savaria, ―Methods for Minimizing Dynamic Power Consumption in Synchronous Designs with Multiple Supply Voltages,‖ IEEE Trans. on CAD of Integrated Circuits and Systems, vol. 22, no. 3, pp. 346-351, Mar.2003.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.