在三維可重組態的系統中, 高能源效益的即時工作排程是一項極為複雜的議題。這項問題的困難點來自於軟硬體工作配置的複雜度、具優先順序限制的工作即時排程問題、以及工作佈置(placement) 位置議題。本論文提出了模擬退火(Simulated Annealing) 的方法來最小化系統的能源消耗, 並保證工作排程的即時性。為了減少尋找最佳解的時間, 我們提出軟硬體工作的優先權分配、截止期限分配、以及最佳分配工作佈置等方法來找到一個較佳的初始解。經過一系列的實驗評估, 論文中所提出的相關方法獲得了令人肯定的成效。

Energy-efficient real-time task scheduling is complicated in three-dimensional dynamically partially reconfigurable systems. The problem difficulty comes from the complexity in hardware/software partition, task scheduling with precedence constraint, and task placement. In this paper, a simulated annealing approach is proposed to minimize the system energy consumption without violating timing constraints. To reduce the search time, the hardware/software priority assignment, deadline assignment, and Best-Fit placement are presented to find the better fist solution. The proposed methodology is evaluated by a series of experiments, showing positive results.

[1] Communication Components Magazine, http://www.2cm.com.tw/, TSVs lead the new wave of 3D ICs, 2011.
[2] XILINX, http://www.xilinx.com/, All Programmable 3D ICs, 2012.
[3] XILINX, http://www.xilinx.com/, 7 Series FPGAs Packaging and Pinout, 2012.
[4] P.-A. Hsiung, P.-H. Lu, and C.-W. Liu, “Energy efficient co-scheduling in dynamically reconfigurable systems,” in Hardware/Software Codesign and System Synthesis (CODES+ISSS), 2007 5th IEEE/ACM/IFIP International Conference on, pp. 87–92, 30 2007-oct. 3 2007.
[5] P.-C. Chang, I.-W. Wu, J.-J. Shann, and C.-P. Chung, “Etahm: An energy-aware
task allocation algorithm for heterogeneous multiprocessor,” in Design Automation Conference, 2008. DAC 2008. 45th ACM/IEEE, pp. 776 –779, june 2008.
[6] L. Shang and N. K. Jha, “Hardware-software co-synthesis of low power real-time distributed embedded systems with dynamically reconfigurable fpgas,” in Proceedings of the 2002 Asia and South Pacific Design Automation Conference, ASP-DAC ’02, (Washington, DC, USA), pp. 345–, IEEE Computer Society, 2002.
[7] K. Siozios, V. Pavlidis, and D. Soudris, “A software-supported methodology for exploring interconnection architectures targeting 3-d fpgas,” in Design, Automation Test in Europe Conference Exhibition, 2009. DATE ’09., pp. 172 –177, april 2009.
[8] M. Lin, A. El Gamal, Y.-C. Lu, and S. Wong, “Performance benefits of monolithically stacked 3-d fpga,” Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, vol. 26, pp. 216 –229, feb. 2007.
[9] K. Siozios, K. Sotiriadis, V. Pavlidis, and D. Sondris, “Exploring alternative 3d fpga architectures: Design methodology and cad tool support,” in Field Programmable Logic and Applications, 2007. FPL 2007. International Conference on, pp. 652 – 655, aug. 2007.
[10] C. Ababei, Y. Feng, B. Goplen, H.Mogal, T. Zhang, K. Bazargan, and S. Sapatnekar, “Placement and routing in 3d integrated circuits,” Design Test of Computers, IEEE, vol. 22, pp. 520 – 531, nov.-dec. 2005.
[11] C. Ababei, H. Mogal, and K. Bazargan, “Three-dimensional place and route for fpgas,” Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, vol. 25, pp. 1132 –1140, june 2006.
[12] K. Siozios, D. Soudris, and G. Economakos, “Three dimensional fpga architectures: A shift paradigm for energy-performance efficient dsp implementations,” in Digital Signal Processing, 2009 16th International Conference on, pp. 1 –6, july 2009.
[13] S. Tanaka, N. Fujita, Y. Yanagisawa, T. Terada, and M. Tsukamoto, “Reconfigurable hardware architecture for saving power consumption on a sensor node,” in Intelligent Sensors, Sensor Networks and Information Processing, 2008. ISSNIP 2008. International Conference on, pp. 405 –410, dec. 2008.
[14] J. Islam, P. W. Chun, W. MacLean, and L. Kirischian, “Lowering power consumption using run-time reconfiguration for stereo rectification,” in Electrical and Computer Engineering, 2008. CCECE 2008. Canadian Conference on, pp. 001693 – 001698, may 2008.
[15] S. Bhandari, S. Subbaraman, and S. Pujari, “Power reduction in embedded system on fpga using on the fly partial reconfiguration,” in Electronic System Design (ISED), 2010 International Symposium on, pp. 77 –80, dec. 2010.
[16] E. McDonald, “Runtime fpga partial reconfiguration,” in Aerospace Conference, 2008 IEEE, pp. 1 –7, march 2008.
[17] R. Bonamy, D. Chillet, O. Sentieys, and S. Bilavarn, “Towards a power and energy efficient use of partial dynamic reconfiguration,” in Reconfigurable Communicationcentric Systems-on-Chip (ReCoSoC), 2011 6th International Workshop on, pp. 1 –4, june 2011.
[18] XILINX, http://www.xilinx.com/, Partial Reconfiguration of Xilinx FPGAs Using ISE Design Suite, 2012.
[19] S. Liu, R. N. Pittman, A. Form, and J.-L. Gaudiot, “On energy efficiency of reconfigurable systems with run-time partial reconfiguration,” in Application-specific Systems Architectures and Processors (ASAP), 2010 21st IEEE International Conference on, pp. 265 –272, july 2010.
[20] L. Chia and C.-S. Shih, “Template-based runtime reconfiguration scheduling for partial reconfigurable soc,” in Embedded and Real-Time Computing Systems and
Applications, 2007. RTCSA 2007. 13th IEEE International Conference on, pp. 542 –549, aug. 2007.
[21] M. Hussain andM. Rahmatullah, “Power analysis of hardware based motion estimation in a heterogeneous reconfigurable environment,” in Quality Electronic Design, 2009. ASQED 2009. 1st Asia Symposium on, pp. 325 –329, july 2009.
[22] P.-A. Hsiung, C.-H. Huang, J.-S. Shen, and C.-C. Chiang, “Scheduling and placement of hardware/software real-time relocatable tasks in dynamically partially reconfigurable systems,” ACM Transactions on Reconfigurable Technology and Systems, vol. 4, December 2010.
[23] J.-W. Hsieh, Y.-H. Chang, andW.-L. Lee, “An enhanced leakage-aware scheduler for dynamically reconfigurable fpgas,” in Proceedings of the 16th Asia and South Pacific Design Automation Conference, ASPDAC ’11, (Piscataway, NJ, USA), pp. 661–667, IEEE Press, 2011.
[24] B. Mei, P. Schaumont, and S. Vernalde, “A hardware-software partitioning and scheduling algorithm for dynamically reconfigurable embedded systems,” 2000.
[25] C.-H. Lu, H.-W. Liao, and P.-A. Hsiung, “Multi-objective placement of reconfigurable hardware tasks in real-time system,” in Computational Science and Engineering, 2009. CSE ’09. International Conference on, vol. 2, pp. 921 –925, aug. 2009.
[26] A. Mtibaa, B. Ouni, and M. Abid, “An efficient list scheduling algorithm for time placement problem,” Computers & Electrical Engineering, vol. 33, no. 4, pp. 285 – 298, 2007. !ce:title¿Hardware/Software System on Chip Co-design: Approach and Application!/ce:title¿.
[27] R. E. Korf, “Depth-first iterative-deepening: An optimal admissible tree search,” Artificial Intelligence, vol. 27, no. 1, pp. 97 – 109, 1985.
[28] R. E. Korf, “Depth-first iterative-deepening: An optimal admissible tree search,” Artificial Intelligence, vol. 27, no. 1, pp. 97 – 109, 1985.
[29] C. L. Liu and J. W. Layland, “Scheduling algorithms for multiprogramming in a hard-real-time environment,” J. ACM, vol. 20, pp. 46–61, Jan. 1973.
[30] R. P. Dick, D. L. Rhodes, and W. Wolf, “Tgff: task graphs for free,” in Proceedings of the 6th international workshop on Hardware/software codesign, CODES/CASHE ’98, (Washington, DC, USA), pp. 97–101, IEEE Computer Society, 1998.