This paper describes a novel way to exploit the computation capabilities delivered by modern Field-Programmable Gate Arrays (FPGAs), not only towards a higher performance, but also towards an improved reliability. Computation-specific pieces of circuitry are dynamically scheduled and allocated to different resources on the chip based on a set of novel algorithms which are described in detail in this article. These algorithms consider most of the technological constraints existing in modern partially reconfigurable FPGAs as well as spontaneously occurring faults and emerging permanent damage in the silicon substrate of the chip. In addition, the algorithms target other important aspects such as communications and synchronization among the different computations that are carried out, either concurrently or at different times. The effectiveness of the proposed algorithms is tested by means of a wide range of synthetic simulations, and, notably, a proof-of-concept implementation of them using real FPGA hardware is outlined. 1. Introduction Dynamic Partial Reconfiguration (DPR) permits to adjust some logic resources on FPGA chips at runtime, whilst the rest are still performing active computations. During the last few years, DPR has become a hot research topic with the objective of building more reliable, efficient, and powerful electronic systems. Indeed, DPR is the enabling technology for a new computing paradigm which combines computation in time and space [1–3]. In Reconfigurable Computing (RC), a battery of computation-specific circuits (“hardware tasks”) is swapped in and out of the FPGA on demand to hold a continuous stream of input operands, computation, and output results. Multitasking, adaptation, and specialization are key properties in RC, as multiple swappable tasks can run concurrently at different positions on chip, each with custom data paths for efficient execution of specific computations. Besides task switching, DPR makes it possible to deal with the increasing fault rate currently observed in advanced electronic devices [4] in a more reliable way than ASICs do. While the latter, traditionally, simply tolerates the fault effect by using redundancy, FPGAs permit to route around damaged resources on-the-fly, keeping the system fault-free at all times [5]. However, DPR penetration in the commercial market is still testimonial, mainly due to the lack of suitable high-level design tools to exploit this technology. Indeed, currently, special skills are required to successfully develop a dynamically reconfigurable application. In light of the
References
[1]
G. J. Brebner, “A virtual hardware operating system for the Xilinx XC6200,” in Proceedings of the International Workshop on Field-Programmable Logic, Smart Applications, New Paradigms and Compilers, pp. 327–336, 1996.
[2]
K. Compton and S. Hauck, “Reconfigurable computing: a survey of systems and software,” ACM Computing Surveys, vol. 34, no. 2, pp. 171–210, 2002.
[3]
S. Hauck and A. DeHon, Reconfigurable Computing: The Theory and Practice of FPGA-Based Computation, Morgan Kaufmann, San Francisco, Calif, USA, 1st edition, 2007.
[4]
C. Constantinescu, “Trends and challenges in VLSI circuit reliability,” IEEE Micro, vol. 23, no. 4, pp. 14–19, 2003.
[5]
D. P. Montminy, R. O. Baldwin, P. D. Williams, and B. E. Mullins, “Using relocatable bitstreams for fault tolerance,” in Proceedings of the 2nd NASA/ESA Conference on Adaptive Hardware and Systems (AHS '07), pp. 701–708, August 2007.
[6]
X. Iturbe, K. Benkrid, T. Arslan, I. Martinez, M. Azkarate, and A. Morales-Reyes, “Evolutionary dynamic allocation of relocatable modules onto partially damaged Xilinx FPGAs,” in Proceedings of the International Conference on Engineering of Reconfigurable Systems and Algorithms, pp. 211–217, 2010.
[7]
X. Iturbe, K. Benkrid, T. Arslan, C. Hong, and I. Martinez, “Empty resource compaction algorithms for real-time hardware tasks placement on partially reconfigurable FPGAs subject to fault occurrence,” in Proceedings of the International Conference on ReConFigurable Computing and FPGAs, 2011.
[8]
X. Iturbe, K. Benkrid, A. Ebrahim, C. Hong, T. Arslan, and I. Martinez, “Snake: an ecient strategy for the reuse of circuitry and partial computation results in high-performance recong- urable computing,” in Proceedings of the International Conference on ReConFigurable Computing and FPGAs (ReConFig '11), 2011.
[9]
K. Danne and M. Platzner, “Periodic real-time scheduling for FPGA computers,” in 3rd International Workshop on Intelligent Solutions in Embedded Systems (WISES '05), pp. 117–127, May 2005.
[10]
. Steiger, H. Walder, and M. Platzner, “Heuristics for online scheduling real-time tasks to partially reconfigurable devices,” in Proceedings of the International Conference on Field-Programmable Logic and Applications, pp. 575–584, 2003.
[11]
Y.-H. Chen and P.-A. Hsiung, “Hardware task scheduling and placement in operating systems for dynamically reconfigurable SoC,” in Proceedings of the International Conference on Embedded and Ubiquitous Computing, pp. 489–498, 2005.
[12]
X. G. Zhou, Y. Wang, X. Z. Huang, and C. L. Peng, “On-line scheduling of real-time tasks for reconfigurable computing system,” in Proceedings of the IEEE International Conference on Field Programmable Technology (FPT '06), pp. 57–64, December 2006.
[13]
X. Zhou, Y. Wang, X. Huang, and C. Peng, “Fast on-line task placement and scheduling on reconfigurable devices,” in Proceedings of the International Conference on Field Programmable Logic and Applications (FPL '07), pp. 132–138, August 2007.
[14]
J. Cui, Z. Gu, W. Liu, and Q. Deng, “An efficient algorithm for online soft real-time task placement on reconfigurable hardware devices,” in Proceedings of the 10th IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing (ISORC '07), pp. 321–328, May 2007.
[15]
F. Dittmann and S. Frank, “Hard real-time reconfiguration port scheduling,” in Proceedings of the Design, Automation and Test in Europe Conference and Exhibition, pp. 123–128, April 2007.
[16]
Y. Lu, T. Marconi, K. Bertels, and G. Gaydadjiev, “Online task scheduling for the FPGA-based partially reconfigurable systems,” in Proceedings of the International Workshop on Reconfigurable Computing: Architectures, Tools and Applications, pp. 216–230, 2009.
[17]
T. Marconi, Y. Lu, K. Bertels, and G. Gaydadjiev, “3D compaction: a novel blocking-aware algorithm for online hardware task scheduling and placement on 2D partially reconfigurable devices,” in Proceedings of the International Symposium on Appied Reconfigurable Computing, pp. 194–206, 2010.
[18]
Y. Lu, T. Marconi, K. Bertels, and G. Gaydadjiev, “A communication aware online task scheduling algorithm for FPGA-based partially reconfigurable systems,” in Proceedings of the 18th IEEE International Symposium on Field-Programmable Custom Computing Machines (FCCM '10), pp. 65–68, May 2010.
[19]
D. Ghringer, M. Hübner, E. Nguepi Zeutebouo, and J. Becker, “Operating system for runtime reconfigurable multiprocessor systems,” International Journal of Reconfigurable Computing, vol. 2011, Article ID 121353, 16 pages, 2011.
[20]
F. Redaelli, M. D. Santambrogio, and S. O. Memik, “An ILP formulation for the task graph scheduling problem tailored to bi-dimensional reconfigurable architectures,” in Proceedings of the International Conference on Reconfigurable Computing and FPGAs (ReConFig '08), pp. 97–102, mex, December 2008.
[21]
K. Bazargan, R. Kastner, and M. Sarrafzadeh, “Fast template placement for reconfigurable computing systems,” IEEE Design and Test of Computers, vol. 17, no. 1, pp. 68–83, 2000.
[22]
H. Walder, C. Steiger, and M. Platzner, “Fast online task placement on FPGAs: free space partitioning and 2D-hashing,” in Proceedings of the International Parallel and Distributed Processing Symposium, 2003.
[23]
A. Ahmadinia, C. Bobda, M. Bednara, and J. Teich, “A new approach for on-line placement on reconfigurable devices,” in Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS '04), pp. 1825–1831, April 2004.
[24]
M. Handa and R. Vemuri, “An efficient algorithm for finding empty space for online FPGA placement,” in Proceedings of the 41st Design Automation Conference, pp. 960–965, June 2004.
[25]
M. Morandi, M. Novati, M. D. Santambrogio, and D. Sciuto, “Core allocation and relocation management for a self dynamically reconfigurable architecture,” in Proceedings of the IEEE Computer Society Annual Symposium on VLSI: Trends in VLSI Technology and Design (ISVLSI '08), pp. 286–291, April 2008.
[26]
M. Tomono, M. Nakanishi, S. Yamashita, K. Nakajima, and K. Watanabe, “A new approach to online FPGA placement,” in Proceedings of the 40th Annual Conference on Information Sciences and Systems (CISS '06), pp. 145–150, March 2006.
[27]
A. Ahmadinia, C. Bobda, S. P. Fekete, J. Teich, and J. C. van der Veen, “Optimal free-space management and routing-conscious dynamic placement for reconfigurable devices,” IEEE Transactions on Computers, vol. 56, no. 5, pp. 673–680, 2007.
[28]
J. Tabero, J. Septien, H. Mecha, and D. Mozos, “A low fragmentation heuristic for task placement in 2D RTR HW management,” in Proceedings of the International Conference on Field-Programmable Logic and Applications, pp. 241–250, 2004.
[29]
J. Tabero, J. Septién, H. Mecha, and D. Mozos, “Task placement heuristic based on 3D-adjacency and look-ahead in reconfigurable systems,” in Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC '06), pp. 396–401, January 2006.
[30]
J. Tabero, J. Septién, H. Mecha, and D. Mozos, “Allocation heuristics and defragmentation measures for reconfigurable systems management,” Integration, the VLSI Journal, vol. 41, no. 2, pp. 281–296, 2008.
[31]
C.-H. Lu, H.-W. Liao, and P.-A. Hsiung, “Multi-objective placement of reconfigurable hardware tasks in real-time system,” in Proceedings of the International Conference on Computational Science and Engineering, pp. 921–925, 2009.
[32]
Z. Li and S. Hauck, “Configuration prefetching techniques for partial reconfigurable coprocessor with relocation and defragmentation,” in Proceedings of the 10th ACM International Symposium on Field-Programmable Gate Arrays (FPGA '02), pp. 187–195, February 2002.
[33]
A. Ejnioui and R. F. DeMara, “Area reclamation strategies and metrics for SRAM-based reconfigurable devices,” in Proceedings of the 5th International Conference on Engineering of Reconfigurable Systems and Algorithms (ERSA'05), pp. 196–202, June 2005.
[34]
J. C. Van Der Veen, S. P. Fekete, M. Majer et al., “Defragmenting the module layout of a partially reconfigurable device,” in Proceedings of the 5th International Conference on Engineering of Reconfigurable Systems and Algorithms (ERSA '05), pp. 92–101, June 2005.
[35]
H. Kalte and M. Porrmann, “Context saving and restoring for multitasking in reconfigurable systems,” in Proceedings of the International Conference on Field Programmable Logic and Applications (FPL '05), pp. 223–228, August 2005.
[36]
A. A. El Farag, H. M. El-Boghdadi, and S. I. Shaheen, “Improving utilization of reconfigurable resources using two-dimensional compaction,” Journal of Supercomputing, vol. 42, no. 2, pp. 235–250, 2007.
[37]
A. Ahmadinia, C. Bobda, M. Bednara, and J. Teich, “A new approach for on-line placement on reconfigurable devices,” in Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS '04), pp. 1825–1831, April 2004.
[38]
A. Montone, F. Redaelli, M. D. Santambrogio, and S. O. Memik, “A reconfiguration-aware floorplacer for FPGAs,” in Proceedings of the International Conference on Reconfigurable Computing and FPGAs (ReConFig '08), pp. 109–114, December 2008.
[39]
S. Srinivasan, P. Mangalagiri, Y. Xie, N. Vijaykrishnan, and K. Sarpatwari, “FLAW: FPGA lifetime awareness,” in Proceedings of the Annual Design Automation Conference, pp. 630–635, 2006.
[40]
X. Iturbe, K. Benkrid, T. Arslan, C. Hong, and I. Martinez, “Enabling FPGAs for future deep space exploration missions: improving fault-tolerance and computation density with R3TOS,” in Proceedings of the NASA/ESA Conference on Adaptive Hardware and Systems, 2011.
[41]
C. Hong, K. Benkrid, X. Iturbe, A. Ebrahim, and T. Arslan, “Efficient on-chip task scheduler and allocator for reconfigurable operating systems,” Embedded Systems Letters, vol. 3, no. 3, pp. 85–88, 2011.
[42]
M. Liu, W. Kuehn, Z. Lu, and A. Jantsch, “Run-time partial reconfiguration speed investigation and architectural design space exploration,” in Proceedings of the 19th International Conference on Field Programmable Logic and Applications (FPL '09), pp. 498–502, September 2009.
