Modeling Clustered Task Graphs for Scheduling Large Parallel Programs in Distributed Systems

Concepció Roig, Ana Ripoll, Emilio Luque

    Research output: Contribution to journalArticleResearchpeer-review


    The recent development of distributed processing platforms, such as clusters of workstations, makes the use of distributed applications more extensive. A fundamental issue affecting performance in distributed systems is the scheduling of tasks to processors. The problem of solving the scheduling of parallel programs modelled with a task precedence graph (TPG) has been extensively studied. Scheduling algorithms of TPGs can be solved by a one-step method when a fixed number of processors is considered or through a two-step method by first creating an unbounded number of groups of tasks (clusters) and subsequently assigning these clusters to a bounded number of processors. The goal of this work is to present a new mapping algorithm called TASC (Task ASsignment exploiting Concurrency) to solve this second step of assigning clusters to processors. The effectiveness of TASC is established through simulation for a set of synthetic graphs that model real applications. © 2004, Sage Publications. All rights reserved.
    Original languageEnglish
    Pages (from-to)243-254
    Publication statusPublished - 1 Jan 2004


    • Static mapping
    • cluster-mapping heuristics
    • message-passing computation model
    • modelling parallel programs
    • scheduling algorithms


    Dive into the research topics of 'Modeling Clustered Task Graphs for Scheduling Large Parallel Programs in Distributed Systems'. Together they form a unique fingerprint.

    Cite this