ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

A reconfigurable hardware-software iteration co-synthesis algorithm based on vertex position tree

  • 1.

    School of Computer Science, University of Science and Technology of China, Hefei 230027, China

  • 2.

    Key Laboratory of Electric Restriction, Electronic Engineering Institute, Hefei 230037, China

Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2014.04.010
  • Received Date: 15 April 2013
  • Accepted Date: 28 September 2013
  • Rev Recd Date: 28 September 2013
  • Publish Date: 30 April 2014
    Abstract

  • Abstract

    In reconfigurable computing, more tasks can be executed at a higher speed in hardware by time multiplexing with the limited area resources. Meanwhile, it also brings new challenges to the traditional hardware-software codesign. For offline scheduling, centralized shared structure reconfigurable platform, the ICS-VPT (iteration co-synthesis based on vertex position tree) algorithm synthesized hardware-software partitioning, hardware placement and task scheduling to improve system performance: The VPT (vertex position tree) data structure was first proposed, which could find a placement position quickly with small storage space; The ICS (iteration co-synthesis) algorithm grouped tasks according to data dependence graph and obtained the hardware/software tasks priorities by combining the communication cost, thus obtaining a reasonable partitioning and scheduling. Experimental results show that the ICS-VPT algorithm maintains a lower level of system running time by means of efficient reconfigurable resource management and flexible communication cost handling.

    Abstract

    In reconfigurable computing, more tasks can be executed at a higher speed in hardware by time multiplexing with the limited area resources. Meanwhile, it also brings new challenges to the traditional hardware-software codesign. For offline scheduling, centralized shared structure reconfigurable platform, the ICS-VPT (iteration co-synthesis based on vertex position tree) algorithm synthesized hardware-software partitioning, hardware placement and task scheduling to improve system performance: The VPT (vertex position tree) data structure was first proposed, which could find a placement position quickly with small storage space; The ICS (iteration co-synthesis) algorithm grouped tasks according to data dependence graph and obtained the hardware/software tasks priorities by combining the communication cost, thus obtaining a reasonable partitioning and scheduling. Experimental results show that the ICS-VPT algorithm maintains a lower level of system running time by means of efficient reconfigurable resource management and flexible communication cost handling.
    • FullText(HTML)
  • loading
    • References(15)
  • [1]
    Estrin G, Bussell B, Turn R, et al. Parallel processing in a restructurable computer system[J]. IEEE Transactions on Electronic Computers, 1963, EC-12(6): 747-755.
    [2]
    Salvadeo P A, Veca A C, Lopez R C. Historic behavior of the electronic technology: The wave of Makimoto and Moores Law in the transistors age[C]// 8th Conference on Programmable. Bento Gon?alves, Brazil: IEEE Press, 2012: 1-5.
    [3]
    Huang M Q, Narayana V K, Simmler H, et al. Reconfiguration and communication-aware task scheduling for high-performance reconfigurable computing[J]. ACM Transactions on Reconfigurable Technology Systems, 2010, 3(4): 1-24.
    [4]
    Shen Yingzhe, Zhou Xuehai. A hardware-software partitioning algorithm for reconfigurable computing systems[J]. Journal of University of Science and Technology of China, 2009, 39(2): 182-188.
    沈英哲,周学海.一种用于可重构计算系统的软硬件划分算法[J].中国科学技术大学学报,2009,39(2):182-188.
    [5]
    刘彦, 李仁发, 许新达, 等. 一种异构可重构片上系统的实时任务调度算法[J]. 计算机研究与发展, 2010, 47(6): 1 116-1 124.
    [6]
    Steiger C, Walder H, Platzner M, et al. Online scheduling and placement of real-time tasks to partially reconfigurable devices[C]// Proceedings of the 24th International Real-Time Systems Symposium. Cancun, Mexico: IEEE Press, 2003: 224-225.
    [7]
    Chen Y H, Hsiung P A. Hardware task scheduling and placement in operating systems for dynamically reconfigurable SoC[C]// Embedded and Ubiquitous Computing, Lecture Notes in Computer Science. Berlin, Germany: Springer, 2005: 489-498.
    [8]
    Zhou X G, Wang Y, Huang X Z, et al. On-line scheduling of real-time tasks for reconfigurable computing system[C]// International Conference on Field Programmable Technology. Bangkok, Thailand: IEEE Press, 2006: 57-64.
    [9]
    Marconi T, Lu Y, Bertelsm K, et al. Online hardware task scheduling and placement algorithm on partially reconfigurable devices[C]// Proceedings of the 4th International Workshop on Reconfigurable Computing: Architectures, Tools and Applications. London, UK: IEEE Press, 2008: 306-311.
    [10]
    齐骥,李曦,胡楠,等.基于硬件任务顶点的可重构系统资源管理算法[J].电子学报,2006,34(11):2 094-2 098.
    [11]
    Septién J, Mozos D, Mecha H, et al. Perimeter quadrature-based metric for estimating FPGA fragmentation in 2D HW multitasking[C]// 22nd IEEE International Symposium on Parallel and Distributed Processing.Miami, USA: IEEE Press, 2008:1-8.
    [12]
    Cordone R, Redaelli F, Redaelli M A, et al. Partitioning and scheduling of task graphs on partially dynamically reconfigurable FPGAs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2009, 28(5): 662-675.
    [13]
    何琨, 黄文奇, 金燕. 基于动作空间求解二维矩形Packing问题的高效算法[J]. 软件学报, 2012, 23(5): 1 037-1 044.
    [14]
    Kwok Y K, Ahmad I. Benchmarking the task graph scheduling algorithms[C]// Proceedings of the First Merged International Patallel Processing Symposium. Orlando, USA: IEEE Press, 1998: 531-537.
    [15]
    Wu J G, Srikanthan T, Jiao T. Algorithmic aspects for functional partitioning and scheduling in hardware/software co-design[J]. Design Automation for Embedded Systems, 2008, 12(4): 345-375.
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [1]
    Estrin G, Bussell B, Turn R, et al. Parallel processing in a restructurable computer system[J]. IEEE Transactions on Electronic Computers, 1963, EC-12(6): 747-755.
    [2]
    Salvadeo P A, Veca A C, Lopez R C. Historic behavior of the electronic technology: The wave of Makimoto and Moores Law in the transistors age[C]// 8th Conference on Programmable. Bento Gon?alves, Brazil: IEEE Press, 2012: 1-5.
    [3]
    Huang M Q, Narayana V K, Simmler H, et al. Reconfiguration and communication-aware task scheduling for high-performance reconfigurable computing[J]. ACM Transactions on Reconfigurable Technology Systems, 2010, 3(4): 1-24.
    [4]
    Shen Yingzhe, Zhou Xuehai. A hardware-software partitioning algorithm for reconfigurable computing systems[J]. Journal of University of Science and Technology of China, 2009, 39(2): 182-188.
    沈英哲,周学海.一种用于可重构计算系统的软硬件划分算法[J].中国科学技术大学学报,2009,39(2):182-188.
    [5]
    刘彦, 李仁发, 许新达, 等. 一种异构可重构片上系统的实时任务调度算法[J]. 计算机研究与发展, 2010, 47(6): 1 116-1 124.
    [6]
    Steiger C, Walder H, Platzner M, et al. Online scheduling and placement of real-time tasks to partially reconfigurable devices[C]// Proceedings of the 24th International Real-Time Systems Symposium. Cancun, Mexico: IEEE Press, 2003: 224-225.
    [7]
    Chen Y H, Hsiung P A. Hardware task scheduling and placement in operating systems for dynamically reconfigurable SoC[C]// Embedded and Ubiquitous Computing, Lecture Notes in Computer Science. Berlin, Germany: Springer, 2005: 489-498.
    [8]
    Zhou X G, Wang Y, Huang X Z, et al. On-line scheduling of real-time tasks for reconfigurable computing system[C]// International Conference on Field Programmable Technology. Bangkok, Thailand: IEEE Press, 2006: 57-64.
    [9]
    Marconi T, Lu Y, Bertelsm K, et al. Online hardware task scheduling and placement algorithm on partially reconfigurable devices[C]// Proceedings of the 4th International Workshop on Reconfigurable Computing: Architectures, Tools and Applications. London, UK: IEEE Press, 2008: 306-311.
    [10]
    齐骥,李曦,胡楠,等.基于硬件任务顶点的可重构系统资源管理算法[J].电子学报,2006,34(11):2 094-2 098.
    [11]
    Septién J, Mozos D, Mecha H, et al. Perimeter quadrature-based metric for estimating FPGA fragmentation in 2D HW multitasking[C]// 22nd IEEE International Symposium on Parallel and Distributed Processing.Miami, USA: IEEE Press, 2008:1-8.
    [12]
    Cordone R, Redaelli F, Redaelli M A, et al. Partitioning and scheduling of task graphs on partially dynamically reconfigurable FPGAs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2009, 28(5): 662-675.
    [13]
    何琨, 黄文奇, 金燕. 基于动作空间求解二维矩形Packing问题的高效算法[J]. 软件学报, 2012, 23(5): 1 037-1 044.
    [14]
    Kwok Y K, Ahmad I. Benchmarking the task graph scheduling algorithms[C]// Proceedings of the First Merged International Patallel Processing Symposium. Orlando, USA: IEEE Press, 1998: 531-537.
    [15]
    Wu J G, Srikanthan T, Jiao T. Algorithmic aspects for functional partitioning and scheduling in hardware/software co-design[J]. Design Automation for Embedded Systems, 2008, 12(4): 345-375.
    Recommended articles
    TrendMD
    Volume 44 Issue 4 page: 325-332
    Cover

    Article Metrics

    Article views (12) PDF downloads(48)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return