Abordagens baseadas em autômatos celulares síncronos para o escalonamento estático de tarefas em multiprocessadores

Abstract

The Static Task Scheduling Problem (STSP) in multiprocessors aims to allocate a set of computational tasks that compose a parallel application in the nodes of a multiprocessor architecture. An optimal solution for an instance of STSP is such that the precedence constraints are satised and the runtime - or makespan - is minimized. The problem is NPComplete, even limited to the simplest case: a parallel system with only two processors. Approaches proposed to solve it typically use heuristics, such as HLFET ( Highest Level First with Estimated Time) and MCP (Modied Critical Path), or metaheurístics, such as genetic algorithms (GA) and simulated annealing (SA) in an attempt to nd good results for the problem. However, in these approaches, a computational eort is used to solve an instance of the problem and when a new instance is presented to the algorithm, the process needs to start again from scratch. In this context, the cellular automata-based scheduling is a promising approach because its main feature is the extraction of knowledge while scheduling an application and its subsequent reuse in other instances. However some desirable features in CA-based scheduling such as: (i) massive parallelism inherent to CA, (ii) usage of an arbitrary number of processors, (iii) eective reuse of the knowledge extracted from parallel applications and others, have not been successfully exploited by previous models in the literature. This dissertation investigates new CA-based approaches for STSP. They were evaluated systematically and compared to previous approaches of CA-based scheduling and heuristic and metaheuristic methods. Some contributions of this research are three new models of schedulers (SCAS, SCAS-H and SCAS-HV) related to extraction, evaluation and reuse of knowledge, a new strategy to initialize CA lattices determined by a deterministic heuristic, a new strategy to analyze the dynamic behavior of CA rules (rule penalization) at runtime, and two new neighborhood models (Vpl-c1 e Vpl-c2) with simple structure, but able to extract information from parallel applications and use an arbitrary number of processors. The results showed it is possible to ensure the successful employment of parallelism in CAs as well as a good performance in the learning phase, in which the values found by new models are close to those of genetic algorithms (taken by reference) and superior than those obtained by heuristics and some metaheuristics. Furthermore, statistical tests were performed and proved the superiority of the new approaches in relation to other CA-based scheduling models. The reuse of knowledge was also evaluated and its performance was proved competitive in the new approaches. Finally, the methods developed showed the scheduling based on CA has great potential to eciently schedule tasks in multiprocessor systems. This potential can be better exploited when the proposed models work directly on parallel hardware architectures.