Multi-layer task graph clustering for mapping and scheduling onto embedded systems

Bassel R. Arafeh*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


This work is motivated by the general trend that embedded systems design has high tolerance to longer compilation time. Based on this added flexibility in compilation, this work proposes a multilevel (multi-layer) graph partitioning framework for solving the mapping and scheduling problem for distributed heterogeneous embedded systems. However, this work concentrates on developing a multi-layer task graph clustering scheme as a part of a multi-step scheduling approach. This work introduces linear clustering techniques for vertex matching in Directed Acyclic Graphs (DAGs) that enable the construction of multi-layer coarsened DAGs with different granularity levels. This paper addresses the major obstacle facing the DAG contraction process, which is the formation of cycles, and discusses this issue for direct and chained dependence cycles. Solutions are provided that establish the basis for performing cycle testing in order to avoid the formation of cycles under certain conditions. This research shows, by analysis, that the upper-bound time complexity of the proposed cycle testing method is O(|V|3), where V is the set of task nodes. Also, this research shows, by analysis, that the complexity of the proposed multi-layer DAG coarsening scheme is O(|V|6). The simulation results verify the cost-effectiveness of the proposed scheme, and show its capabilities in generating clusters at different granularities.

Original languageEnglish
Pages (from-to)187-202
Number of pages16
JournalInternational Journal of Computers and their Applications
Issue number3
Publication statusPublished - Sept 2012


  • Distributed real-time systems
  • Embedded multiprocessor systems
  • Inter-process communication
  • Mapping and scheduling
  • Multilevel graph partitioning
  • Task clustering

ASJC Scopus subject areas

  • General Computer Science


Dive into the research topics of 'Multi-layer task graph clustering for mapping and scheduling onto embedded systems'. Together they form a unique fingerprint.

Cite this