Hardware/software partitioning and pipelined scheduling on runtime reconfigurable FPGAs

Abstract

FPGAs are widely used in today's embedded systems design due to their low cost, high performance, and reconfigurability. Partially RunTime-Reconfigurable (PRTR) FPGAs, such as Virtex-2 Pro and Virtex-4 from Xilinx, allow part of the FPGA area to be reconfigured while the remainder continues to operate without interruption, so that HW tasks can be placed and removed dynamically at runtime. We address two problems related to HW task scheduling on PRTR FPGAs: (1) HW/SW partitioning. Given an application in the form of a task graph with known execution times on the HW (FPGA) and SW (CPU), and known area sizes on the FPGA, find an valid allocation of tasks to either HW or SW and a static schedule with the optimization objective of minimizing the total schedule length (makespan). (2) Pipelined scheduling. Given an input task graph, construct a pipelined schedule on a PRTR FPGA with the goal of maximizing system throughput while meeting a given end-to-end deadline. Both problems are NP-hard. Satisfiability Modulo Theories (SMT) is an extension to SAT by adding the ability to handle arithmetic and other decidable theories. We use the SMT solver Yices with Linear Integer Arithmetic (LIA) theory as the optimization engine for solving the two scheduling problems. In addition, we present an efficient heuristic algorithm based on kernel recognition for the pipelined scheduling problem, a technique borrowed from SW pipelining, to overcome the scalability problem of the SMT-based optimal solution technique.

References

1. Ahn, M., Yoon, J. W., Pae, K. Y., Kim, Y., Kiemb, M., and Choi, K. 2006. A spatial mapping algorithm for heterogeneous coarse-grained reconfigurable architectures. In Proceedings of the Conference and Exhibition on Design, Automation and Test in Europe (DATE'06). G. G. E. Gielen Ed., European Design and Automation Association, 363--368.
2. Aiken, A., Nicolau, A., and Novack, S. 1995. Resource-Constrained software pipelining. IEEE Trans. Parall. Distrib. Syst. 6, 12, 1248--1270.
3. Allan, V. H., Jones, R. B., Lee, R. M., and Allan, S. 1995. Software pipelining. ACM Comput. Surv. 27, 3, 367--432.
4. Banerjee, S., Bozorgzadeh, E., and Dutt, N. D. 2005. Physically-Aware HW-SW partitioning for reconfigurable architectures with partial dynamic reconfiguration. In Proceedings of the ACM IEEE Design Automation Conference (DAC'05). 335--340.
5. Banerjee, S., Bozorgzadeh, E., and Dutt, N. D. 2006. Integrating physical constraints in hw-sw partitioning for architectures with partial dynamic reconfiguration. IEEE Trans. VLSI Syst. 14, 11, 1189--1202.
6. Cabodi, G., Kondratyev, A., Lavagno, L., Nocco, S., Quer, S., and Watanabe, Y. 2005. A bmc- based formulation for the scheduling problem of hardware systems. Int. J. Softw. Tools. Technol. Transfer. 7, 2, 102--117.
7. Carpenter, J., Funk, S., Holman, P., Srinivasan, A., Anderson, J., and Baruah, S. 2004. A Categorization of Real-Time Multiprocessor Scheduling Problems and Algorithms. Chapman and Hall/CRC, 30--1--30--19.
8. Claus, C., Muller, F. H., Zeppenfeld, J., and Stechele, W. 2007. A new framework to accelerate virtex-ii pro dynamic partial self-reconfiguration. In Proceedings of the 14th Reconfigurable Architectures Workshop.
9. Cuoccio, A., Grassi, P. R., Rana, V., Santambrogio, M. D., and Sciuto, D. 2008. A generation flow for self-reconfiguration controllers customization. In Proceedings of the IEEE International Symposium on Electronic Design, Test and Applications (DELTA'08). IEEE Computer Society, 279--284.
10. Davis, M., Logemann, G., and Loveland, D. 1962. A machine program for theorem-proving. Comm. ACM 5, 7, 394--397.
11. DeHon, A., Markoviskiy, Y., Caspi, E., Chu, M., Huang, R., Perissakis, S., Pozzi, L., Yeh, J., and Wawrzynek, J. 2006. Stream computations organized for reconfigurable execution. Microprocess. Microsyst. 30, 6, 334--354.
12. Dick, R. P., Rhodes, D. L., and Wolf, W. 1998. TGFF: Task graphs for free. In Proceedings of the International Workshop on Hardware/Software Codesign (CODES'98), G. Borriello, A. A. Jerraya, and L. Lavagno Eds., IEEE Computer Society, Los Alamitos, CA, 97--101.
13. Dittmann, F. 2007. Methods to exploit reconfigurable fabrics. Ph.D. dissertation, University of Paderborn, Germany.
14. Dutertre, B. and de Moura, L. M. 2006. A DPLL(T). In Proceedings of the International Conference on Computer Aided Verification (CAV'06). T. Ball and R. B. Jones, Eds. Lecture Notes in Computer Science, vol. 4144. Springer, 81--94.
15. Fekete, S. P., Köhler, E., and Teich, J. 2001. Optimal FPGA module placement with temporal precedence constraints. In Proceedings of the Conference and Exhibition on Design, Automation and Test in Europe (DATE'01). 658--667.
16. Goldstein, S. C., Schmit, H., Budiu, M., Cadambi, S., Moe, M., and Taylor, R. R. 2000. Piperench: A reconfigurable architecture and compiler. IEEE Comput. 33, 4, 70--77.
17. Jin, Y., Satish, N., Ravindran, K., and Keutzer, K. 2005. An automated exploration framework for fpga-based soft multiprocessor systems. In Proceedings of the International Workshop on Hardware/Software Codesign (CODES+ISSS'05). P. Eles, A. Jantsch, and R. A. Bergamaschi Eds., ACM Press, New York, 273--278.
18. Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. 1983. Optimization by simulated annealing. Science 220, 4598, 671--680.
19. Klein, M., Ralya, T., Pollak, B., Obenza, R., and Harbour, M. G. 1993. A Practitioner's Handbook for Real-Time Analysis: Guide to Rate Monotonic Analysis for Real-Time Systems. Springer.
20. Kudlur, M. and Mahlke, S. A. 2008. Orchestrating the execution of stream programs on multicore platforms. In Proceedings of the Conference on Programming Language Design and Implementation (PLDI'08). R. Gupta and S. P. Amarasinghe Eds., ACM Press, New York, 114--124.
21. Li, Z. and Hauck, S. 2002. Configuration prefetching techniques for partial reconfigurable coprocessor with relocation and defragmentation. In Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays (FPGA'02). 187--195.
22. Lin, Y., Kudlur, M., Mahlke, S. A., and Mudge, T. N. 2007. Hierarchical coarse-grained stream compilation for software defined radio. In Proceedings of the International Conference on Compilers, Architecture and Synthesis for Embedded Systems (CASES'07), T. Kim, P. Sainrat, S. S. Lumetta, and N. Navarro Eds., ACM Press, New York, 115--124.
23. Liu, M., Kuehn, W., Lu, Z., and Jantsch, A. 2009. Run-Time partial reconfiguration speed investigation and architectural design space exploration. In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL'09).
24. Memik, S. O. and Fallah, F. 2002. Accelerated SAT-based scheduling of control/data flow graphs. In Proceedings of the IEEE International Conference on Computer Design (ICCD'02). IEEE Computer Society, Los Alamitos, CA, 395.
25. Moskewicz, M. W., Madigan, C. F., Zhao, y., Zhang, L., and Malik, S. 2001. Chaff: Engineering an efficient sat solver. In Proceedings of the IEEE/ACM Design Automation Conference (DAC'01). ACM Press, New York, 530--535.
26. Noguera, J. and Badia, R. M. 2005. Performance and energy analysis of task-level graph transformation techniques for dynamically reconfigurable architectures. In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL'05). T. Rissa, S. J. E. Wilton, and P. H. W. Leong Eds., IEEE Press, 563--567.
27. Noguera, J. and Badia, R. M. 2006. System-Level power-performance tradeoffs for reconfigurable computing. IEEE Trans. VLSI Syst. 14, 7, 730--739.
28. Papadimitriou, C. H. and Steiglitz, K. 1998. Combinatorial Optimization: Algorithms and Complexity. Dover Publications.
29. Shang, L., Dick, R. P., and Jha, N. K. 2007. Slopes: Hardwarecsoftware cosynthesis of low-power real-time distributed embedded systems with dynamically reconfigurable fpgas. IEEE Trans. VLSI 26, 3.
30. Suhendra, V., Raghavan, C., and Mitra, T. 2006. Integrated scratchpad memory optimization and task scheduling for mpsoc architectures. In Proceedings of the International Conference on Compilers, Architecture and Synthesis for Embedded Systems (CASES'06). S. Hong, W. Wolf, K. Flautner, and T. Kim Eds., ACM Press, New York, 401--410.
31. Xilinx. 2005. Xilinx virtex-4 family overview. preliminary specification ds112. Tech. rep., Xilinx Inc.
32. Yuan, M, He, X., and Gu, Z. 2008. Hardware/Software partitioning and static task scheduling on runtime reconfigurable fpgas using a smt solver. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium. IEEE Computer Society, 295--304.

Index Terms

• Applied computing

  • Arts and humanities

    • Architecture (buildings)

      • Computer-aided design

  • Physical sciences and engineering

    • Engineering

      • Computer-aided design

• Computer systems organization

  • Embedded and cyber-physical systems

  • Real-time systems