TDTA : Topology-based Real-Time DAG Task Allocation on Identical Multiprocessor Platforms

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)2895-2909
Journal / PublicationIEEE Transactions on Parallel and Distributed Systems
Issue number11
Online published30 Aug 2023
Publication statusPublished - Nov 2023


Modern real-time systems contain complex workloads, which are usually modeled as directed acyclic graph (DAG) tasks and deployed on multiprocessor platforms. The complex execution logic of DAG tasks results in excessive schedulability analysis overhead, and the current DAG task allocation strategy cannot efficiently utilize processor resources (inner parallelization of DAG tasks). In this paper, an invalid-edge deletion (IED) method is proposed to reduce the execution complexity of the DAG tasks while guaranteeing the correctness of the execution logic. Besides, we bound the number of complete paths for DAG tasks, which re-limits the searching space of the schedulability analysis. Then, a topology-based DAG tasks allocation (TDTA) strategy is developed, which reduces the interference caused by higher-priority DAG tasks to enable the full utilization of the processor resources. The experimental results show that the IED method effectively reduces the overhead of DAG task analysis, and the performance of the TDTA strategy is better than the performance of other state-of-the-art strategies.

© 2023 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.

Research Area(s)

  • directed acyclic graph task, fixed-priority, Job shop scheduling, partitioned scheduling, Processor scheduling, Real-time system, Real-time systems, Resource management, Task analysis, tasks allocation strategy, Topology, Vehicle dynamics