Scheduling is one of the most important tasks in high-level and system synthesis. Traditional time-constrained scheduling algorithms try to meet performance target while minimizing hardware cost and power consumption rate. The power metric reflects energy consumption per usage. Number of usages is not in the objective function. As energy-efficiency is getting important, we should consider total energy consumed over a product’s lifetime. We propose taking into account Total Cost of Ownership (TCO), i.e., the sum of synthesized hardware cost and the total energy cost over the hardware’s lifetime.
We show that there exists trade-off between these two and propose an ILP-based approach that optimizes TCO under a time constraint and a usage scenario. Experimental results show that sparing more hardware could lead to lower TCO when the system is to be heavily used; instead, using high energy consumption parts could leads to lower TCO when the system is to be lightly used.

1
中文摘要
針對高階系統合成，排程是最重要的工作之一。傳統在時間條件下的排程演
算法，都是以硬體成本及能源消耗最小化為排程的目標。其中能源的消耗都是以
一次為計算基本單位，沒有實際考慮到要使用的次數。當能源消耗的議題越來越
被重視，我們便希望把總次數消耗的能量全部考量進去。因此，本論文把總擁有
成本當成目標；也就是合成硬體成本和所有使用時間內總次數能源消耗成本的加
總。
我們會呈現三個有關硬體成本和總消耗能量的協調數據，並且在時間的限制
及特定使用量下，使用ILP 來找到總擁有成本的最小值。實驗結果顯示，當我們
高頻率的使用時，花比較多的硬體成本可以幫助降低總擁有成本；相對來說，低
頻率使用時，反要用比較高消耗能量的機器來幫助降低總擁有成本。

Abstract 2
Contents 3
List of Figures 4
List of Table 5
Chapter 1 Introduction 6
Chapter 2 Motivational Example 9
Chapter 3 Related Work 12
Chapter 4 Problem Formulation 15
Chapter 5 Algorithm 17
Chapter 6 Experimental Results 21
Chapter 7 Conclusion and Future Work 34
Bibliography 38
Appendix 41
ILP formulation of the illustrative example 41

[1] T. Kim, J. W. S. Liu, and C. L. Liu, “A scheduling algorithm for conditional resource sharing,” in Proc. International Conference on Computer-Aided Design (ICCAD), 1991, pp. 84-87.
[2] T. Ly, D. Knapp, R. Miller, and D. MacMillen, “Scheduling using behavioral templates,” in Proc. Design Automation Conference (DAC), 1995, pp..101-106.
[3] P. G. Paulin and J. P. Knight, “Scheduling and Binding Algorithm for High Level Synthesis,” in Proc. Design Automation Conference (DAC), 1989, pp. 1-6.
[4] R. Mehra, L. M. Guerra, and J. M. Rabaey, “Low Power Architectural Synthesis and the Impact of Exploiting Locality,” Journal of VLSI Signal Processing, 1996, Vol. 13, No. 2-3, pp. 239-258.
[5] N. K. Jha, “Low Power System Scheduling and System,” in Proc. International Conference on Computer-Aided Design (ICCAD), 2001,, pp. 259-263.
[6] A. Manzak and C. Chakrabarti, “A low power scheduling scheme with resources operating at multiple voltages,” IEEE Transactions on VLSI Systems, 2002, Vol. 10, No. 1, pp. 6–14.
[7] C.-T. Hwang, J.-H. Lee, and Y.-C. Hsu, “A formal approach to the scheduling problem in high-level synthesis,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1991, Vol. 10, No. 4, pp.464-475
[8] E. Musoll and J. Cortadella, “Sceduling and resource binding for Low Power,” in Proc. International Symposium on System Synthesis , 1995, pp. 104-109
[9] P. G. Paulin and J. P. Knight, “Force-directed scheduling for the behavioral synthesis of ASIC’s,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1989, Vol. 8, No. 6, pp.661–679.
[10] S. Raje and M. Sarrafzadeh, “Variable Voltage Scheduling,” in Proc. International Workshop on Low Power Design, 1995, pp. 9-14.
[11] J. M. Chang and M. Pedram, “How to minimize energy using multiple supply voltage,” Univ. of Southern California, Los Angeles, Tech. Rep. CHEG 96-13, 1996, pp. 157-162
[12] I. Hong, D. K. ad G. Qu, M. Potkonjak, and M. Srivastava, “Power optimization of variable-voltage core-based systems,” in Proc. International Conference on 35th Annual Design Automation Design, 1998 , pp. 176-181.
[13] M. Y. Lim and V. W. Freeh, “Determining the minimum energy consumption using dynamic voltage and frequency scaling,” in Proc. the 3rd Workshop on High-Performance, Power-Aware Computing, 2007, pp. 1-8.
[14] T. Burd and R.W. Brodersen, ”Design issue for dynamic voltage scaling,” in Proc. International Symposium on Low Power Electronics and Design (ISLPED), 2000, pp.9-14
[15] Standard Task Graph: http://www.kasahara.elec.waseda.ac.jp/schedule/index.html
[16] ILOG CPLEX User’s Guideline: http://class.ece.iastate.edu/ee458/CplexLargeUsersManual.pdf
[17] T. Ishihara and H. Yasuura, “Voltage scheduling problem for dynamically variable voltage processors,” in Proc. International Symposium on Low Power Electronics and Design (ISLPED), 1998, pp. 197-202.
[18] M. Y Lim and V. W. Freeh, “Determining the Minimum Energy Consumption using Dynamic Voltage and Frequency Scaling”, in The 3rd Workshop on High-Performance, Power-Aware Computing ,2007, pp.1 – 8.
[19] SolarLand 5W 12V http://www.solarpanelstore.com/solar-power.small-solar-panels.smallspssolarcollectors.solarland5.info.1.html
[20] Cost of Battery Power
http://corrosion-doctors.org/Batteries/cost.htm