Title :
SCAS-IS: Knowledge Extraction and Reuse in Multiprocessor Task Scheduling Based on Cellular Automata
Author :
Carneiro, Murillo G. ; Oliveira, Gina M B
Author_Institution :
Inst. of Math. Sci. & Comput., Univ. of Sao Paulo, Sao Paulo, Brazil
Abstract :
Static Task Scheduling Problem (STSP) in multiprocessors is a NP-Complete problem. Cellular Automata (CA) have been recently proposed to solve STSP. The main feature of CA-based models to STSP is the extraction of knowledge while scheduling an application and its subsequent reuse in other instances. Previous works showed this approach is promising. However some desirable features have not been successfully exploited yet, such as: (i) the usage of an arbitrary number of processors, (ii) the massive parallelism inherent to CA and (iii) the reuse of evolved rules with competitive results. This paper presents a new model called SCAS-IS (Synchronous Cellular Automata Scheduler with Initialization Strategies). Its major innovation is the employment of fixed initialization strategies to start up CA dynamics. Parallel program graphs found in literature and others randomly generated were used to test the new model. Results show SCAS-IS overcame related models both in make span obtained as computational performance. It is also competitive with meta-heuristics.
Keywords :
cellular automata; computational complexity; graph theory; knowledge acquisition; multiprocessing systems; parallel programming; processor scheduling; CA dynamics; NP-complete problem; SCAS-IS; STSP; arbitrary processor number usage; computational performance; evolved rule reusability; fixed initialization strategies; knowledge extraction; knowledge reuse; massive parallelism; multiprocessor task scheduling; parallel program graphs; static task scheduling problem; synchronous cellular automata scheduler; Computer architecture; Genetic algorithms; Lattices; Microprocessors; Processor scheduling; Program processors; Resource management; cellular automata; genetic algorithms; multiprocessor task scheduling;
Conference_Titel :
Neural Networks (SBRN), 2012 Brazilian Symposium on
Conference_Location :
Curitiba
Print_ISBN :
978-1-4673-2641-4
DOI :
10.1109/SBRN.2012.46