SCAS-IS: Knowledge Extraction and Reuse in Multiprocessor Task Scheduling Based on Cellular Automata

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.