| 摘要: |
| 针对异构信号处理平台中通信密集型任务并行复杂度高、通信延迟大等问题，提出了一种基于二阶聚簇和任务复制的混合优化调度算法。该算法对经典调度算法中任务最早开始时间的计算方法进行改进；通过改进传统聚簇方法，有效避免了任务的重复聚簇；结合任务复制连锁效应，设计了基于关键前驱节点的多任务复制方法；利用二阶聚簇法进一步减小调度长度，同时解决了处理器资源浪费的问题。通过随机生成的有向无环图进行仿真实验，结果表明，该算法在通信量较大的情况下具有更小的调度长度和更大的加速比，对于通信密集型任务具有良好的调度结果。 |
| 关键词: 异构平台 通信密集型任务 混合优化调度 二阶聚簇 关键前驱路径 任务复制 |
| DOI：10.20079/j.issn.1001-893x.230325001 |
|
| 基金项目: |
|
| A Hybrid Optimal Scheduling Algorithm for Heterogeneous Signal Processing Platform |
| LI Yudong,MA Jinquan,YUE Chunsheng,JI Yawei,ZHANG Kun,SHEN Xiaolong |
| (1.College of Information Systems Engineering,PLA Strategic Force Information Engineering University,Zhengzhou 450001,China;2.Unit 65022 of PLA,Shenyang 110000,China) |
| Abstract: |
| To address the problems of high parallel complexity of communication-intensive tasks and large communication delays in heterogeneous signal processing platforms,a hybrid optimal scheduling algorithm based on second-order clustering and task duplication is proposed.This algorithm improves the method of calculating the earliest start time of a task in the classical scheduling algorithm.The repeated clustering of tasks is effectively avoided by improving the traditional clustering methods.A multi-task duplication method based on critical precursor paths is designed in combination with the task duplication chain effect.The second-order clustering method is used to further reduce the scheduling length,while solving the problem of wasted processor resources.Randomly generated directed acyclic graphs are used for simulation experiments and the results show that the algorithm can achieve efficient scheduling at large communication traffic.It also achieves good scheduling results for communication-intensive tasks. |
| Key words: heterogeneous platform communication-intensive task hybrid optimal scheduling second-order clustering critical precursor path task duplication |
