Algorithmic aspects for functional partitioning and scheduling in hardware/software co-design

被引:30
|
作者
Wu Jigang [1 ]
Srikanthan, Thambipillai [1 ]
Jiao, Tao [1 ]
机构
[1] Nanyang Technol Univ, Ctr High Performance Embedded Syst, Singapore 639798, Singapore
关键词
Partitioning; Scheduling; Task graph; Heuristic algorithm; Co-design;
D O I
10.1007/s10617-008-9032-0
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
Hardware/software (HW/SW) partitioning and scheduling are the crucial steps during HW/SW co-design. It has been shown that they are classical combinatorial optimization problems. Due to the possible sequential or concurrent execution of the tasks, HW/SW partitioning and scheduling has become more difficult to solve optimally. In this paper more efficient heuristic algorithms are proposed for the HW/SW partitioning and scheduling. The proposed algorithm partitions a task graph by iteratively moving the task with highest benefit-to-area ratio in higher priority. The benefit-to-area ratio is updated in each iteration step to cater for the task concurrence. The proposed algorithm for task scheduling executes the task lying in hardware-only critical path in higher priority to enhance the task forecast. A large body of experimental results conclusively shows that the proposed heuristic algorithm for partitioning is superior to the latest efficient combinatorial algorithm (Tabu search) cited in this paper. Moreover, the Tabu search for partitioning has been further improved by utilizing the proposed heuristic solution as its initial solution. In addition, the proposed scheduling algorithm obtains the improvements over the most widely used approaches by up to 10% without large increase in running time.
引用
收藏
页码:345 / 375
页数:31
相关论文
共 50 条
  • [41] Hardware/software co-design with the HMS framework
    Sheliga, M
    Sha, EHM
    JOURNAL OF VLSI SIGNAL PROCESSING SYSTEMS FOR SIGNAL IMAGE AND VIDEO TECHNOLOGY, 1996, 13 (01): : 37 - 56
  • [42] The role of flexibility in hardware/software co-design
    Ernst, R
    FOURTH INTERNATIONAL WORKSHOP ON HARDWARE/SOFTWARE CO-DESIGN (CODES/CASHE '96), PROCEEDINGS, 1996, : 114 - 114
  • [43] Hardware and Software Co-Design for Robot Arm
    Meshram, Urmila
    Harkare, R. R.
    Meshram, Devendra
    CONTEMPORARY COMPUTING, PT 2, 2010, 95 : 241 - +
  • [44] Hardware/software co-design for virtual machines
    Kent, KB
    Serra, M
    Horspool, N
    IEE PROCEEDINGS-COMPUTERS AND DIGITAL TECHNIQUES, 2005, 152 (05): : 537 - 548
  • [45] Recent advances in Hardware/Software co-design
    Gomez-Pulido, Juan A.
    JOURNAL OF SYSTEMS ARCHITECTURE, 2010, 56 (08) : 303 - 304
  • [46] GPGPU: HARDWARE/SOFTWARE CO-DESIGN FOR THE MASSES
    Mann, Zoltan Adam
    COMPUTING AND INFORMATICS, 2011, 30 (06) : 1247 - 1257
  • [47] Hardware/Software Co-design for Evolvable Hardware by Genetic Algorithm
    Shang, Qianyi
    Chen, Lijun
    Tong, Ruoxiong
    PROCEEDINGS OF 2020 IEEE INTERNATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND INFORMATION SYSTEMS (ICAIIS), 2020, : 306 - 309
  • [48] Software/hardware co-design of efficient and secure cryptographic hardware
    Nedjah, N
    Mourelle, LD
    JOURNAL OF UNIVERSAL COMPUTER SCIENCE, 2005, 11 (01) : 66 - 82
  • [49] Efficient task scheduling approach relevant to the hardware/software co-design of embedded system
    Seljak, Barbara Koroušić
    Journal of Computing and Information Technology, 2000, 8 (03) : 197 - 206
  • [50] Power reduction through specific instruction scheduling based on hardware/software co-design
    Zhao, Kang
    Bian, Jinian
    Jiang, Chenqian
    Dong, Sheqin
    Goto, Satoshi
    ASICON 2007: 2007 7TH INTERNATIONAL CONFERENCE ON ASIC, VOLS 1 AND 2, PROCEEDINGS, 2007, : 193 - 196