学位论文简介
面向嵌入式与实时系统等并行应用，调度算法的客观评估需要结构多样、参数可控的有向无环图（DAG）测试任务集。现有随机生成方法难以保证拓扑覆盖，枚举方法则受搜索空间膨胀与同构冗余限制，多维参数联合控制和覆盖验证也不充分。本文以目标拓扑空间的刻画、生成与验证为主线，研究全拓扑覆盖并关键参数可控的DAG生成技术。主要研究内容与贡献如下：
建立DAG拓扑参数描述体系。统一量化规模、长度、宽度、形状参数（shape）、入度及出度等结构特征，从搜索空间、生成效率和样本均匀性评价现有方法，为目标空间界定与生成约束设计提供依据。
提出基于shape分解与逐层递归的全拓扑覆盖生成算法。针对拓扑枚举中的同构冗余，采用组合、排列与连接三阶段构造，结合反链机制、冗余消除与连接编码，系统生成给定约束下的非同构DAG。
构建基于可满足性模理论（SMT）的形式化验证框架。将遗漏拓扑检测转化为反例搜索，在模型与目标空间等价且求解结果为不可满足时，确认相应空间的覆盖完备性。
设计实现高效DAG生成器FT-DAG。针对规模增长带来的生成开销，结合结构分类、规范化形式计算优化、分解递归与数据复用，减少冗余搜索和重复计算，支持多维参数联合控制。
构建DAG生成器综合测试平台。集成传递约简、参数计算、同构判定、覆盖及均匀性分析，在统一实验条件下验证所提方法并比较不同生成器，为调度测试基准构建提供工具支持。
主要学术成果
Fang Y, Zhao S, Guo Y, et al. Brief industry paper: A DAG generator with full topology coverage[C]//2023 IEEE Real-Time Systems Symposium (RTSS). IEEE, 2023: 506-511. (CCF A，第一作者)
Fang Y, Yang L, Liu W, et al. FT-DAG: An efficient full-topology DAG generator with controllable parameters[J]. ACM Transactions on Embedded Computing Systems, 2025, 24(5s): 1-25. (CCF B，第一作者)
Fang Y, Li H, Chang W. Directed Acyclic Graph Topology Generators: A Survey[J]. ACM Transactions on Embedded Computing Systems, 2026, 25(5): 1-25. (CCF B，第一作者)
Zhao S, Chen N, Fang Y, et al. A universal method for task allocation on FP-FPS multiprocessor systems with spin locks[C]//2023 60th ACM/IEEE Design Automation Conference (DAC). IEEE, 2023: 1-6. (CCF A，第三作者)
Chang W, Guo Y, Wang W, et al. Resource Management on Heterogeneous Chiplets Systems[C]//2025 IEEE/ACM International Conference On Computer Aided Design (ICCAD). IEEE, 2025: 1-8. (CCF B，第六作者)
Shuai Zhao, Jieyu Jiang, Shenlin Cai, Yaowei Liang, Chen Jie, Yinjie Fang, et al. Tight Cache Contention Analysis for WCET Estimation on Multicore Systems[C]//2025 IEEE Real-Time Systems Symposium (RTSS). IEEE, 2025: 487-499. (CCF A，第六作者)
