10
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Simple Algorithms for Scheduling Monotonic Moldable Tasks

      Preprint

      Read this article at

          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          We study simple yet efficient algorithms for scheduling n independent monotonic moldable tasks on \(m\) identical processors; the objective is to: (1) minimize the makespan, or (2) maximize the sum of values of tasks completed by a deadline.The workload of a monotonic task is non-decreasing with the number of assigned processors. In this paper, we propose a scheduling algorithm who achieves a processor utilization of r when the number of processors assigned to a task j is the minimal number of processors needed to complete j by a time d. Here, r equals (1-k/m)/2 in the general setting where k is the maximum number of processors allocated to the tasks (in large computing clusters, m>>k and k/m approaches 0). More importantly, in many real applications, when a parallel task is executed on a small set of f processors, the speedup is linearly proportional to f. This is to be proved to be powerful in designing more efficient algorithms than the existing algorithms which is illustrated in a typical case where f=5; we propose an algorithm who can achieve a utilization of r=3(1-(k+3)/m)/4 and the extension of this algorithm to the case with an arbitrary f is also discussed. Based on the above schedule, we propose an r(1+\epsilon)-approximation algorithm with a complexity of O(nlog(n/\epsilon)) for the first scheduling objective. We also propose a generic greedy algorithm for the second scheduling objective, and, by analyzing it, give an r-approximation algorithm with a complexity of O(n). So far, for the first scheduling objective, the algorithm proposed in the typical setting is simpler and has a better performance than most of the existing algorithms given m>>k; the second objective is considered for the first time.

          Related collections

          Author and article information

          Journal
          1609.08588
          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          Data structures & Algorithms
          Data structures & Algorithms

          Comments

          Comment on this article