Task graph scheduling for reconfigurable architectures driven by reconfigurations hiding and resources reuse

ABSTRACT

This paper is focused on the scheduling of tasks on partially dynamically reconfigurable FPGA s in order to minimize the overall latency of the application. We propose a novel approach to the partitioning of a system specification by detecting recurrent structures in the specification itself. This technique has the objective of identifying modules that can be used more than once during the system lifetime. In such a scenario the reconfiguration overhead is minimized via both the device resource reuse, due to the partitioner, and the reconfiguration time hiding, due to the scheduler. A model of reconfigurable hardware, both for the device and the application, will also be defined and presented.

REFERENCES

• 1: Cardoso, J.M.P.: On combining temporal partitioning and sharing of functional units in compilation for reconfigurable architectures. IEEE Trans. Comp. 52(10) (2003) 1362--1375
• 2: João M. P. Cardoso , Horácio C. Neto, Compilation for FPGA-Based Reconfigurable Hardware, IEEE Design & Test, v.20 n.2, p.65-75, March 2003 [doi>10.1109/MDT.2003.1188264]
• 3: João M. P. Cardoso, Loop Dissevering: A Technique for Temporally Partitioning Loops in Dynamically Reconfigurable Computing Platforms, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.181.2, April 22-26, 2003
• 4: Sudarshan Banerjee , Elaheh Bozorgzadeh , Nikil Dutt, Physically-aware HW-SW partitioning for reconfigurable architectures with partial dynamic reconfiguration, Proceedings of the 42nd annual Design Automation Conference, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065667]
• 5: Banerjee, S., Bozorgzadeh, E., Dutt, N.: Integrating physical constraints in hw-sw partitioning for architectures with partial dynamic reconfiguration. In IEEE T-VLSI 14(11) (November 2006) 1189--1202.
• 6: Jafri, K., Jafri, N., Khan, S.: Constraint based temporal partitioning model for partial reconfigurable architectures. In Proceedings of IEEE INIMIC (2003) 242--246.
• 7: Sudarshan Banerjee , Elaheh Bozorgzadeh , Nikil Dutt, Considering Run-Time Reconfiguration Overhead in Task Graph Transformations for Dynamically Reconfigurable Architectures, Proceedings of the 13th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.273-274, April 18-20, 2005 [doi>10.1109/FCCM.2005.28]
• 8: Sudarshan Banerjee , Elaheh Bozorgzadeh , Nikil Dutt, PARLGRAN: parallelism granularity selection for scheduling task chains on dynamically reconfigurable architectures, Proceedings of the 2006 Asia and South Pacific Design Automation Conference, January 24-27, 2006, Yokohama, Japan [doi>10.1145/1118299.1118419]
• 9: Soheil Ghiasi , Majid Sarrafzadeh, Optimal reconfiguration sequence management, Proceedings of the 2003 Asia and South Pacific Design Automation Conference, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119843]
• 10: Javier Resano , Daniel Mozos, Specific scheduling support to minimize the reconfiguration overhead of dynamically reconfigurable hardware, Proceedings of the 41st annual Design Automation Conference, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996604]
• 11: Elena Moscu Panainte , Koen Bertels , Stamatis Vassiliadis, Compiler-driven FPGA-area allocation for reconfigurable computing, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 12: Giani, M., Redaelli, M., Santambrogio, M., Sciuto, D.: Task partitioning for the scheduling on reconfigurable systems driven by specification self-similarity. In: Proceedings of the International Conference on Engineering of Reconfigurable Systems and Algorithms (ERSA), CSREA Press, Las Vegas. (2007) 78--84.
• 13: Chaitin, G.J., Auslander, M.A., Chandra, A.K., Cocke, J., Hopkins, M.E., Markstein, P.W.: Register allocation via coloring. In: Computer Languages. Volume 6. (1981) 47--57.
• 14: Gregory Chaitin, Register allocation and spilling via graph coloring, ACM SIGPLAN Notices, v.39 n.4, April 2004 [doi>10.1145/989393.989403]
• 15: Ferrandi, F., Redaelli, M., Santambrogio, M.D., Sciuto, D.: Solving the coloring problem to schedule on partially dynamically reconfigurable hardware. In: IFIP VLSI-SOC 2005. (2005).
• 16: Bowen, L.: Introduction to contemporary mathematics. In http://www.ctl.ua.edu/math103/scheduling/scheduling\_algorithms.htm.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

Additional Classification:
  B. Hardware
  B.0 GENERAL
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
dynamic reconfiguration, fpga, scheduling