SYMPOSIUM MINISYMPOSIA

ABSTRACT

A parallel task is one that can be executed by multiple processors. All the processors allotted to a task are required to execute that task in unison and simultaneously. Two types of the parallel tasks have been mostly investigated. A non-malleable parallel task requires a fixed number of processors for its execution, while a malleable task can be executed on any number of processors, with its execution time being a function of the number of processors allotted to it.

In some situations, however, neither of these two task models are congruous to the practice. Consider I/O intensive tasks in the parallel computer systems with the shared-nothing architecture. In those environments, the execution time of the task greatly depends on where the task is run on.

In this paper, we introduce another type of the parallel task which captures those aspects and also is a strict generalization of the malleable parallel task: the execution time of the task depends not only on the number of processors, but also on the processors themselves on which the task are executed.

Formally speaking, there are m processors {1,2, ¼, m} and n tasks to be scheduled {T₁, T₂, ¼, T_n}. Associated with each task T_i is a set of permissible processor assignments A_i = {A_i¹, A_i², ¼, A_i^k_i } where A_i^j, 1 £ j £ k_i, is a subset of processors on which the execution of task T_i is allowed. Depending on the underlying architecture of the parallel computer system, the processors composing an assignment has a structural property, e.g., for hypercubes, the processors form a subcube structure, while, for meshes, the processors form a submesh structure. A function t_i : A_i ® Z⁺, 1 £ i £ n, specifies the execution time of task T_i in terms of the processor assignments. We will call those tasks, for shortly, TPET (the Task with Processor-dependent Execution Time).

In fact, TPET is exactly the parallel analog of the well-known unrelated machine model of the sequential task, in which the task execution times are given as a matrix f = (f_ij), 1 £ i £ n, 1 £ j £ m, where f_ij represents the execution time of task T_i on processor j.

Our problem is also a strict generalization of the one called either ``dedicated task scheduling'' or ``scheduling tasks with simultaneous resource requirements''. In both problems, there is a set of resources, e.g., a set of processors, and each task requires a fixed subset of the resources simultaneously, i.e., in our terms, |A_i| = 1, for every i, 1 £ i £ n. In this paper, we will call this problem DTS (Dedicated Task Scheduling). The non-preemptive DTS problem for 1-dimensional mesh system is equivalent to the dynamic storage allocation problem.

Several authors considered the following sequential task scheduling problem: for each task, a subset of processors are specified and each task is allowed to be run on one of the processors in the subset. The execution time of the task remains constant on the processors in this subset. We consider the parallel analog of this problem, and call it the restricted placement problem, or shortly, RPP throughout this paper.

We first consider PRAMs, and show that it is very unlikely that there exists an efficient polynomial time approximation algorithm to solve either DTS non-preemptively or RPP preemptively. We show that, for non-preemptive DTS problem (for preemptive RPP problem, respectively), no polynomial time algorithm can achieves an approximation factor o(n^e) for some positive constant e unless NP = co-NP (P = NP, respectively). It is open whether there is a good approximation algorithm for solving DTS problem preemptively or not.

We next consider the TPET problem on one-dimensional meshes, and give non-preemptive scheduling algorithm with an approximation factor of O(logm). This algorithm is based on the technique of solving linear relaxation of the integer programming formulation and rounding the fractional solution into a nearby integer solution. We show that, as far as this framework of the algorithm is maintained, no one can yield much better solutions than the presented one. We also consider the preemptive problem, and present an algorithm with an approximation factor of 2.

Finally, we consider the non-preemptive PDET problem on two-dimensional meshes, and present an algorithm with an approximation factor of O(log² m).

Getting More Information

To obtain more information about the meeting send e-mail to: fscc98@pax.st.usm.edu.

Return to PAX
Return to USM

USM
inquire@delphi.st.usm.edu
Updated
http://pax.st.usm.edu