BFT: a placement algorithm for non-rectangle task model in reconfigurable computing system

Chaohui Wang; Weiguo Wu; Shiqiang Nie; Depei Qian

BFT: a placement algorithm for non-rectangle task model in reconfigurable computing system

View Fulltext

Author(s): Chaohui Wang ¹ ; Weiguo Wu ¹ ; Shiqiang Nie ¹ ; Depei Qian ^{1, 2}
- Affiliations: 1: Department of Computer Science and Technology, Xi'an Jiaotong University, Shaanxi, People's Republic of China ;
  2: School of Computer Science and Engineering, Beihang University, Beijing, People's Republic of China
Source: Volume 10, Issue 3, May 2016, p. 128 – 137
DOI: 10.1049/iet-cdt.2015.0095 , Print ISSN 1751-8601, Online ISSN 1751-861X

Received 16/06/2015, Accepted 16/10/2015, Revised 25/09/2015, Published 01/05/2016

Task scheduling and placement problem is one of the most significant and time-consuming parts in reconfigurable computing (RC) system. Many investigators have explored on the subject, and most of the traditional studies are concentrated on the rectangle task model, which is inconsistent with objective task shape placed in a field programmable gate array (FPGA) but simplifies the system complexity. Rectangle task model produces inner fragments which reduces utilisation of reconfigurable resources in an FPGA. In this study, a task model transformation strategy and an innovative best-fit transformation (BFT) placement algorithm are proposed for a non-rectangle task model to improve the performance of an RC system in rejection rate and total execution time. According to simulation experiments, BFT algorithm reduced the rejection rate by 15% and 7% compared with that of the first-fit algorithm and the best-fit algorithm, respectively. Multi-shape placement algorithm and 3D compaction algorithm are also cited to compare with the BFT algorithm. The result shows that the BFT algorithm has less total execution time in short laxity period and lower rejection rate in large laxity period. Compared with 3D compaction algorithm, the proposed algorithm reduced the total execution time up to 10.79%.

References

1. 1)
  - 2. Reardon, C., Holland, B., George, A., et al: ‘RCML: an environment for estimation modeling of reconfigurable computing systems’, ACM Trans. Embedded Comput. Syst. (TECS), 2012, 11, (S2), pp. 43–64.
2. 2)
  - 18. Sheng, Y., Li, R., Liu, Y.: ‘3D adjacency: a communication-aware online scheduling algorithm for 2D partially reconfigurable devices’. IEEE 16th Int. Conf. on Computational Science and Engineering (CSE), 2013, pp. 701–705.
3. 3)
  - 23. Liu, Y., Li, Q.C., Liu, J.X., et al: ‘Study on hardware software partitioning using immune algorithm and its convergence property’. Proc. IEEE Int. Conf. on Intelligent Computing and Intelligent Systems (ICIS), 2009, vol. 3, pp. 4–8.
4. 4)
  - 3. Duhem, F., Muller, F., Lorenzini, P.: ‘Reconfiguration time overhead on field programmable gate arrays: reduction and cost model’, IET Comput. Digit. Tech., 2012, 6, (2), pp. 105–113 (doi: 10.1049/iet-cdt.2011.0033).
5. 5)
  - 4. Marconi, T.: ‘Online scheduling and placement of hardware tasks with multiple variants on dynamically reconfigurable field-programmable gate arrays’, Comput. Electr. Eng., 2014, 40, (4), pp. 1215–1237 (doi: 10.1016/j.compeleceng.2013.07.004).
6. 6)
  - 21. Handa, M., Ranga, V.: ‘Area fragmentation in reconfigurable operating systems’. ERSA, 2004, pp. 77–83.
7. 7)
  - 17. Wassi, G., Benkhelifa, M.E.A., Lawday, G., et al: ‘Multi-shape tasks scheduling for online multitasking on FPGAs’. Proc. IEEE Int. Symp. on Reconfigurable and Communication-Centric Systems-on-Chip (ReCoSoC), 2014.
8. 8)
  - 16. Yang, Z., Wu, W., Wang, T., et al: ‘A double-arbiter time-sliced tasks scheduling algorithm for reconfigurable computing system’, Chin. J. Comput., 2013, 36, (9), pp. 1850–1867 (doi: 10.3724/SP.J.1016.2013.01850).
9. 9)
  - 11. Walder, H., Christoph, S., Platzner, M.: ‘Fast online task placement on FPGAs: free space partitioning and 2D-hashing’. Proc. IEEE Int. Parallel and Distributed Processing Symp., 2003.
10. 10)
  - 12. Lu, Y., Marconi, T., Gaydadjiev, G., et al: ‘An efficient algorithm for free resources management on the FPGA’. In Proc. ACM Proc. of the Conf. on Design, Automation and Test in Europe, March 2008, pp. 1095–1098.
11. 11)
  - 9. Huang, M.H., Narayana, V.K., Bakhouya, M., et al: ‘Efficient mapping of task graphs onto reconfigurable hardware using architectural variants’, IEEE Trans. Comput., 2012, 61, (9), pp. 1354–1360 (doi: 10.1109/TC.2011.153).
12. 12)
  - 5. Guan, N., Deng, Q., Gu, Z., et al: ‘Schedulability analysis of preemptive and nonpreemptive EDF on partial runtime-reconfigurable FPGAs’, ACM Trans. Des. Autom. Electron. Syst. (TODAES), 2008, 13, (4), pp. 56–99.
13. 13)
  - 19. Marconi, T., Liu, Y., Bertels, K., et al: ‘3D compaction: a novel blocking-aware algorithm for online hardware task scheduling and placement on 2D partially reconfigurable devices’. Reconfigurable Computing: Architectures, Tools and Applications, Berlin, Heidelberg, 2010, pp. 194–206.
14. 14)
  - 6. Bsoul, A.A.M., Manjikian, N., Shang, L.: ‘Reliability-and process variation-aware placement for FPGAs’. Proc. of the Conf. on Design, Automation and Test in Europe, March 2010, pp. 1809–1814.
15. 15)
  - 10. Huang, M.Q., Narayana, V.K., Bakhouya, M.: ‘Reconfiguration and communication-aware task scheduling for high-performance reconfigurable computing’, ACM Trans. Reconfigurable Technol. Syst. (TRETS), 2010, 3, (4), pp. 20–44.
16. 16)
  - 20. Wu, W., Wang, T., Wang, C., et al: ‘A task scheduling and placement strategy based on task's aspect ratio’. Proc. IEEE Int. Conf. on Computational Science and Engineering (CSE), 2014, pp. 476–482.
17. 17)
  - 1. Kulkarni, A., Davidson, T., Heyse, K., et al: ‘Improving reconfiguration speed for dynamic circuit specialization using placement constraints’. Int. Conf. on ReConFigurable Computing and FPGAs (ReConfig 2014), 2014, pp. 1–6.
18. 18)
  - 7. Belaid, I., Muller, F., Benjemaa, M.: ‘Off-line placement of hardware tasks on FPGA’. Int. Conf. on Field Programmable Logic and Applications, August 2009, pp. 591–595.
19. 19)
  - 15. Bassiri, M.M., Shahhoseini, H.S.: ‘A new approach in on-line task scheduling for reconfigurable computing systems’. 2010 21st IEEE Int. Conf. on Application-specific Systems Architectures and Processors (ASAP), 2010, pp. 321–324.
20. 20)
  - 22. Esmaeildoust, M., Fazlali, M., Zakerolhosseini, A., et al: ‘Fragmentation aware placement algorithm for a reconfigurable computing system’. Proc. IEEE Second Int. Conf. on Electrical Engineering (ICEE), 2008, pp. 1–5.
21. 21)
  - 8. Bazargan, K., Ryan, K., Majid, K.: ‘Fast template placement for reconfigurable computing systems’, IEEE Des. Test Comput., 2000, 17, (1), pp. 68–83 (doi: 10.1109/54.825678).
22. 22)
  - 14. Olakkenghil, S.H., Baskaran, K.: ‘An FPGA task placement algorithm using reflected binary gray space filling curve’, Int. J. Reconfigurable Comput., 2014, (5), pp. 1–7 (doi: 10.1155/2014/495080).
23. 23)
  - 13. Lu, Y., Marconi, T., Gaydadjiev, G., et al: ‘A self-adaptive on-line task placement algorithm for partially reconfigurable computing systems’. Proc. IEEE Int. Symp. on Parallel and Distributed Processing, 2008, pp. 1–8.

Login

Not registered yet?

Share

Tools

Login to add to favourites

Key

BFT: a placement algorithm for non-rectangle task model in reconfigurable computing system

References

Related content