logo
CanyamAI summaries for academic research
language
MobileMobile
  • Phone FeatureWeChat Mini Program
EnglishEnglish
noticeNotice
BlogBlog
delete
arrow
Return

Sequential and parallel cellular automata-based scheduling algorithms

delete2002-10-01
delete36
PRE
AI
F
Franciszek Seredyński
A
Albert Y. Zomaya
DOI：10.1109/TPDS.2002.1041877delete
deleteOriginal
deleteOriginal request for help
deleteShare
deleteSave
Abstract

Abstract

En 中文
In this paper, we present a novel approach to designing cellular automata-based multiprocessor scheduling algorithms in which extracting knowledge about the scheduling process occurs. This knowledge can potentially be used while solving new instances of the scheduling problem. We consider the simplest case when a multiprocessor system is limited to two-processors, but we do not imply any limitations on the size and parameters of parallel programs. To design cellular automata corresponding to a given program graph, we propose a generic definition of program graph neighborhood, transparent to the various kinds, sizes, and shapes of program graphs. The cellular automata-based scheduler works in two modes. In learning mode we use a genetic algorithm to discover rules of cellular automata suitable for solving instances of a scheduling problem. In operation mode, discovered rules of cellular automata are able to automatically find an optimal or suboptimal solution of the scheduling problem for any initial allocation of a program graph in two-processor system graph. Discovered rules are typically suitable for sequential cellular automata working as a scheduler, while the most interesting and promising feature of cellular automata are their massive parallelism. To overcome difficulties in evolving parallel cellular automata rules, we propose using coevolutionary genetic algorithm. Discovered this way, rules enable us to design effective parallel schedulers. We present a number of experimental results for both sequential and parallel scheduling algorithms discovered in the context of a cellular automata-based scheduling system.
Keywords:
cellular automata
coevolution
genetic algorithms
multiprocessor scheduling
two-processor systems
AI Summary

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.

Journal

IEEE Transactions on Parallel and Distributed Systems cover
IEEE Transactions on Parallel and Distributed Systems
IF:
6
Papers:
5.2K
Citations:
1.1W

Organization

No organization information available