Machine learning approach to generate Pareto front for list-scheduling algorithms

Research output: Contribution to book/conference proceedings/anthology/reportConference contributionContributedpeer-review

Contributors

  • Nam Khanh Pham - , National University of Singapore (Author)
  • Akash Kumar - , Chair of Processor Design (cfaed) (Author)
  • Khin Mi Mi Aung - , Agency for Science, Technology and Research, Singapore (Author)

Abstract

List Scheduling is one of the most widely used techniques for scheduling due to its simplicity and efficiency. In traditional list-based schedulers, a cost/priority function is used to compute the priority of tasks/jobs and put them in an ordered list. The cost function has been becoming more and more complex to cover increasing number of constraints in the system design. However, most of the existing list-based schedulers implement a static priority function that usually provides only one schedule for each task graph input. Therefore, they may not be able to satisfy the desire of system designers, who want to examine the trade-off between a number of design requirements (performance, power, energy, reliability ...). To address this problem, we propose a framework to utilize the Genetic Algorithm (GA) for exploring the design space and obtaining Pareto-optimal design points. Furthermore, multiple regression techniques are used to build predictive models for the Pareto fronts to limit the execution time of GA. The models are built using training task graph datasets and applied on incoming task graphs. The Pareto fronts for incoming task graphs are produced in time 2 orders of magnitude faster than the traditional GA, with only 4% degradation in the quality.

Details

Original languageEnglish
Title of host publicationSCOPES '16: Proceedings of the 19th International Workshop on Software and Compilers for Embedded Systems
EditorsSander Stuijk
Pages127-134
Number of pages8
Publication statusPublished - 23 May 2016
Peer-reviewedYes

Publication series

SeriesSCOPES: Software and Compilers for Embedded Systems

Conference

Title19th International Workshop on Software and Compilers for Embedded Systems, SCOPES 2016
Duration23 - 25 May 2016
CitySt. Goar
CountryGermany

Keywords

Research priority areas of TU Dresden

ASJC Scopus subject areas

Keywords

  • Design space exploration, List-scheduling, Machine learning