Task Scheduling Problems on Computers
Prof. Fl vio Keidi Miyazawa
The task scheduling problems we consider consist of determining a task assignment for processors in order to optimize the total execution time of these tasks. Some scheduling problems are closely related to packaging problems. This motivated us to consider these problems more particularly.
As VLSI technology advances, parallel computers with thousands of processors may be available soon. Since a process does not necessarily use all of these processors, we may have several processes running at the same time, each with a dedicated subset of processors.
Such problems are very important for the IT area and are directly linked to strategies used by operating systems and compilers. They are problems that need quick solutions, often in a way Online. This need makes this problem (which is NP-difficult) much more complicated because the search for optimal solutions is in most cases unacceptable (due to the long execution time involved). Thus, it is necessary to obtain algorithms that are fast but have a good guarantee of performance, approximation algorithms.
Task Scheduling Problem in Partitioned Connected Mesh Systems (PETSMC)
A set of tasks J1, J2, ..., Jn must be processed in a partitionable connected mesh system consisting of lxw connected processing elements as a rectangular mesh (see Figure {gridshed}). Each Ji task is specified by a triple Ji = (xi, yi, ti) indicating that a sub-mesh of size (xi, yi) or (yi, xi) is required by the Ji task, and ti is its processing time. The objective is to assign tasks to the sub-meshes in order to minimize the total processing time.
Mesh topology, considered in the PETSMC problem, is a very common topology in parallel computers. Other common topologies in parallel computers are: Hyper Mesh, Butterfly and Hypercube.
Hypercube Task Scheduling Problem (PEH):
A hypercube system is a network of computers (processors) where the processors are located at the vertices of the hypercube and the communications between processors are the edges of the hypercube (see Figure {hypercube}). The Scaling Problem in the Hypercube, can be defined as: Given a list of n tasks J = (J1, ..., Jn), each task Ji with execution time ti, a required sub-hypercube of dimension di, and a hypercube system H; scale the tasks of J in H in such a way that the execution time of all tasks in J is minimized. In this scheduling, if a Ji task is scheduled to be executed in a subcube H ', then the processors of H' can be scheduled for another task only when the processing of Ji is finished.