Scholarlink

In multicore real-time systems, handling complex task allocation, especially in the form of Directed Acyclic Graphs (DAGs), within specific time constraints is essential. Numerous studies have focused on core allocation and scheduling of multi-DAG tasks on multicore systems, most of which propose tight timing analyses. Considering the NP-Hard nature of this problem, optimization methods provide a viable solution. This paper introduces LWAO, an allocation optimization method based on a Genetic Algorithm (GA) and layer workload analysis of DAG tasks. To evaluate the effectiveness of the candidate core allocation schemes, LWAO constructs a simulation method for DAG task execution that allows multi-DAG tasks to run on multicore systems according to the core allocation scheme. Additionally, LWAO proposes a crossover operation based on the layered node structures, which accounts for both the task dependencies and parallelism. The crossover operation takes different actions based on the layer workload scenario, classified according to the simulation results, to achieve improved core allocation schemes with each optimization. Experimental results show that in terms of the ratio of makespan to workload, LWAO outperforms the baseline scheduling methods by an average of 11.9%–45.8%.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

An Optimization Framework for DAG Task Allocation on Symmetric Multicore Systems: Exploiting the Layered Node Structures

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Haoran Chen,
  • Huixuan Yi,
  • Jingxi Lin,
  • Lu Lin,
  • Hao Xiong,
  • Shuai Zhao

摘要

In multicore real-time systems, handling complex task allocation, especially in the form of Directed Acyclic Graphs (DAGs), within specific time constraints is essential. Numerous studies have focused on core allocation and scheduling of multi-DAG tasks on multicore systems, most of which propose tight timing analyses. Considering the NP-Hard nature of this problem, optimization methods provide a viable solution. This paper introduces LWAO, an allocation optimization method based on a Genetic Algorithm (GA) and layer workload analysis of DAG tasks. To evaluate the effectiveness of the candidate core allocation schemes, LWAO constructs a simulation method for DAG task execution that allows multi-DAG tasks to run on multicore systems according to the core allocation scheme. Additionally, LWAO proposes a crossover operation based on the layered node structures, which accounts for both the task dependencies and parallelism. The crossover operation takes different actions based on the layer workload scenario, classified according to the simulation results, to achieve improved core allocation schemes with each optimization. Experimental results show that in terms of the ratio of makespan to workload, LWAO outperforms the baseline scheduling methods by an average of 11.9%–45.8%.