Volume 9 Number 1 (Jan. 2014)
Home > Archive > 2014 > Volume 9 Number 1 (Jan. 2014) >
JCP 2014 Vol.9(1): 176-182 ISSN: 1796-203X
doi: 10.4304/jcp.9.1.176-182

A List Simulated Annealing Algorithm for Task Scheduling on Network-on-Chip

Song Chai, Yubai Li, Jian Wang, Chang Wu
School of Communication and Information Engineering, University of Electronic Science and Technology of China, Chengdu, China
Abstract—In this paper, a List Simulated Anneal (LSA) algorithm is proposed for the DAG tasks scheduling on the Network-on-chip to simultaneously optimize makespan, load balance and average link load. A task list is first created for the DAG tasks, and the task-to-processor assignment is performed using Best Fit rule. Then the generated schedule is further optimized using LSA. In LSA, the task execution order is determined by the task list, and the task mapping solution is optimized using simulated annealing. By conducting series of simulation, the performance of our proposal is validated. Comparing to the list Best Fit and list random mapping algorithm, our LSA has 9% and 25.4% shorter makespan, 31.1% and 79.4% better load balance and 18% smaller average link load.

Index Terms—DAG, task scheduling, Network-on-Chip, list schedule, best fit, simulated annealing

[PDF]

Cite: Song Chai, Yubai Li, Jian Wang, Chang Wu, "A List Simulated Annealing Algorithm for Task Scheduling on Network-on-Chip," Journal of Computers vol. 9, no. 1, pp. 176-182, 2014.

General Information

ISSN: 1796-203X
Abbreviated Title: J.Comput.
Frequency: Bimonthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat,etc
E-mail: jcp@iap.org
  • Nov 14, 2019 News!

    Vol 14, No 11 has been published with online version   [Click]

  • Mar 20, 2020 News!

    Vol 15, No 2 has been published with online version   [Click]

  • Dec 16, 2019 News!

    Vol 14, No 12 has been published with online version   [Click]

  • Sep 16, 2019 News!

    Vol 14, No 9 has been published with online version   [Click]

  • Aug 16, 2019 News!

    Vol 14, No 8 has been published with online version   [Click]

  • Read more>>