Graph metrics for predicting speedup in static multiprocessor scheduling

Alan Sheahan, Conor Ryan

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

This paper presents a set of metrics for estimating the speedup achievable in static multiprocessor scheduling using a previously introduced Genetic Algorithm (GA) approach. This is of major importance because, although conventional wisdom suggests that metaheuristics such as GAs have the potential to improve over standard heuristics, little research has been conducted on characterizing the sorts of graphs that they should excel at. We describe several metrics and illustrate that four of them can predict the speed up with an accuracy of almost 90%.

Original languageEnglish
Title of host publicationConvergence and Hybrid Information Technology - 5th International Conference, ICHIT 2011, Proceedings
Pages391-398
Number of pages8
DOIs
Publication statusPublished - 2011
Event5th International Conference on Convergence and Hybrid Information Technology, ICHIT 2011 - Daejeon, Korea, Republic of
Duration: 22 Sep 201124 Sep 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6935 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference5th International Conference on Convergence and Hybrid Information Technology, ICHIT 2011
Country/TerritoryKorea, Republic of
CityDaejeon
Period22/09/1124/09/11

Keywords

  • Genetic Algorithms
  • Graph Partitioning
  • Scheduling

Fingerprint

Dive into the research topics of 'Graph metrics for predicting speedup in static multiprocessor scheduling'. Together they form a unique fingerprint.

Cite this