题目来自 CCSP2025 T5，评测使用官方数据。我们承认原始题面、大样例、官方数据版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

本题复原了场上选手在各测试点的性能分排名。由于判分系统需要，本题实际得分为本题原本得分的 2 倍，仅需正确完成调度即视为通过本题。

时间限制： 1.0 秒

空间限制： 512 MiB

题目描述

为了应对 AI 时代的计算挑战，公司设计了一款新型的 XPU 芯片，用于运行自研的 AI 模型。你需要帮助小新来完成这款 XPU 芯片设计优化工作。

芯片微架构

该芯片的微架构中总共有 5 个队列，分别为队列 A、队列 B、队列 C、队列 D、队列 E。其中队列 A 和队列 B 为计算队列，队列 C、队列 D、队列 E 为通信队列。自研 AI 模型的运行由一系列计算/通讯任务组成。这些任务已经被分配到了不同的计算/通讯队列：

• 队列 A：{任务 1 (A_task1)，任务 2 (A_task2)，任务 3 (A_task3)...}
• 队列 B：{任务 1 (B_task1)，任务 2 (B_task2)，任务 3 (B_task3)...}
• 队列 C：{任务 1 (C_task1)，任务 2 (C_task2)，任务 3 (C_task3)...}
• 队列 D：{任务 1 (D_task1)，任务 2 (D_task2)，任务 3 (D_task3)...}
• 队列 E：{任务 1 (E_task1)，任务 2 (E_task2)，任务 3 (E_task3)...}

除了队列之外，芯片上还有 5 个存储区域，分别为 Buffer1、Buffer2、Buffer3、Buffer4 和 Buffer5。这 5 个存储区域用于保存任务的输出结果。由于这 5 个存储区域在芯片之上，任务将输出结果保存在这些存储区域的时间可以忽略不计；任务从这些存储区域读取数据的时间也可以忽略不计。

任务也可以将输出结果保存在芯片外的公共内存（用 Out 表示）中，但这会带来额外的时间开销（不论数据大小，将输出结果保存到公共内存的时间为 100ns）。公共内存的空间可认为有无限大。

任务一：微架构的流水编排

你需要根据分配到不同队列的具体任务进行微架构的流水编排，使得 AI 模型能够尽可能快的完成执行。每个计算/通讯任务都有执行时长、存储位置和使用资源的大小。

• 执行时长指任务从开始到结束所需要的时间，单位为 ns。
• 存储位置为 Buffer1 到 Buffer5 之一，用于保存该任务的输出数据。编排时，也可以选择将该任务的输出保存在公共内存 Out 中，但这会额外增加 100ns 的执行时间。
• 使用资源大小是指任务的输出数据大小，单位为 B。

任务的执行需要满足以下约束：

• 同一队列中的任务只能串行执行；不同队列中的任务可以并行执行；
• 任务之间的执行可能存在依赖关系，即后继任务依赖于前序任务的输出数据。例如：在队列 A 中，若 A_task2 任务依赖 A_task1 任务，则 A_task2 任务必须在 A_task1 任务完成后执行；不同队列间的任务也可能存在依赖。例如 B_task2 任务依赖 A_task1 任务，E_task3 任务依赖 B_task2 任务，则 B_task2 任务必须等 A_task1 任务执行完成之后才能开始执行，同理，E_task3 任务必须等 B_task2 任务执行完成之后才能开始执行。
• 若 A_task1 任务的输出数据保存在公共内存中，后继任务 A_task2 和 B_task2 都依赖 A_task1 任务的输出数据，则 A_task2 和 B_task2 各自执行时间均需要增加 100ns 用于从公共内存中读取数据。
• 若 A_task2 同时依赖 A_task1 和 B_task1，且 A_task1 和 B_task1 均将数据输出至 Out 中，那么 A_task2 需要花费 200ns 从 Out 中读取数据。
• 当 B_task2 任务依赖 A_task1 任务，且 A_task1 任务的输出大小为 0 时（即 A_task1 无任务输出），因而 A_task1 没有额外的数据输出时间。
• 在同一时刻，正在使用的资源总和不能超过对应资源的上限。例如，同时执行的所有任务中，对 Buffer1 的空间占用不应超过 Buffer1 的大小。虽然存储空间只用来保存输出数据，但该空间在任务开始执行时即被占用。
• 当任务执行完成并且依赖它的所有其他任务也已执行完，占用资源才可释放。例如：队列 A 中任务 A_task1 正在执行，占用资源 3072B(3KB)，执行完成后，由于依赖它的 A_task2、B_task2 和 E_task2 任务均在执行，所以资源暂时无法释放，当这三个任务都执行完成后，任务 A_task1 资源释放，对应资源减少 3072B(3KB)。

在本任务中，你将负责进行任务在微架构的流水编排，也就是每个队列中各任务的执行顺序和时间。在输入文件中，会给出该模型执行所涉及的各个队列中的任务及其属性（task_info）、片上存储资源上限（memory）和任务依赖关系（dependency）。调度器将会根据这些信息和约束条件，给出每个队列里最佳的任务执行顺序，使得模型图整体执行时间最短，并且，计算队列的时间利用率相对最高。

任务二：芯片性能与面积的权衡

假如芯片上的存储空间分配还可以调整，为了在芯片性能和面积之间取得权衡，需要在每个片上存储资源的存储大小上找到一个最佳值，使得在最小成本（面积）下获得最佳的性能。

芯片的面积一般分为逻辑单元的面积和存储资源的面积，在本题中假设逻辑单元已经固定，你主要考虑对片上存储资源大小的设计来达成芯片性能与面积的平衡。其中片上存储资源的面积计算公式为：

$$\begin{aligned} \mathrm{Area}=\max\Bigl\{&2\,\mathrm{mm}^2,\ (\mathrm{Size}_{\mathrm{1}}+\mathrm{Size}_{\mathrm{2}})\times(1.2\,\mathrm{mm}^2/\mathrm{Mbit}) +(\mathrm{Size}_{\mathrm{3}}+\mathrm{Size}_{\mathrm{4}}+\mathrm{Size}_{\mathrm{5}})\times(1.8\,\mathrm{mm}^2/\mathrm{Mbit})\Bigr\}. \end{aligned}$$

其中，总面积 $\mathrm{Area}$ 的单位是 $\mathrm{mm}^2$，$\mathrm{Size}_{\mathrm{1,2,3,4,5}}$ 分别是 Buffer1、Buffer2、Buffer3、Buffer4 和 Buffer5 的存储容量大小。其中 $1\,\mathrm{Mbit}=1024\times1024\,\mathrm{bits}$。由于芯片限制，$\mathrm{Area}$ 至少为 $2\,\mathrm{mm}^2$，哪怕所有 Buffer 存储容量为 0。

在此任务中，输入内容中的 memory 中的五个整数均为 $-1$，表示各类资源的大小是可以灵活调整的。你需要找到最佳的硬件资源大小配置，使得推理任务执行时间更短，同时资源大小最优。

输入格式

从标准输入读入数据。

输入的第一行为一个整数，表示测试点编号。

此后包含三部分内容：

第一部分为各个任务的名称及其对应属性。

此部分以一行 --- task_info --- 开头。每个任务占一行，分别其所在队列（单个字符，A 到 E）、任务名称（不含空格的字符串）、执行时间（整数）、资源位置（整数 1 到 5 对应 Buffer1 到 Buffer5）、使用资源大小（整数）。

例如：

--- task_info ---
A A_task1 2300 1 6144
B B_task2 1300 2 3072

说明名称为 A_task1 的任务在队列 A 中，执行时间是 2300ns，对应的存储资源是 Buffer1，使用资源大小是 6144B(6KB)。

注意：这里是指任务 A_task1 的输出数据如果放在芯片存储区域中，则只能放在 Buffer1 中，但也可以放在内存 Out 中。

第二部分为片上存储资源的容量。

此部分以一行 --- memory --- 开头。之后一行为 5 个空格隔开的整数，分别对应 Buffer1 到 Buffer5 这五个存储资源的容量上限，单位为 B。

例如：

--- memory ---
65536 65536 262144 262144 65536

说明 Buffer1 资源上限是 65536B(64KB)，Buffer2 是 65536B(64KB)，Buffer3 是 262144B(256KB)，Buffer4 是 262144B(256KB)，Buffer5 是 65536B(64KB)。

注意：任务可能使用的资源有 Buffer1、Buffer2、Buffer3、Buffer4、Buffer5 和 Out，但 Out 在输入数据中不给出，在任务 2 中也不纳入面积计算公式。

第三部分为任务之间的依赖关系。

此部分以一行 --- dependency --- 开头。此后每一行包含一对空格隔开的任务名，表示后者任务依赖于前者任务。

例如：

--- dependency ---
A_task1 A_task2
A_task1 B_task2
B_task2 E_task3

说明 A_task2 任务依赖 A_task1 任务，B_task2 任务依赖 A_task1 任务，E_task3 任务依赖 B_task2 任务。

输出格式

输出到标准输出。

输出结果应包含 3 方面内容：

1. task_order：任务编排方案。在 --- task_order --- 行后，应该包含五行输出，分别对应队列 A 到队列 E 中的任务序列。每一行包含由 , 隔开的所有任务名称，顺序与执行顺序严格对应。
2. task_info：每个任务及其具体信息。在 --- task_info --- 行后，有若干行。每行表示一个任务的执行信息。任务之间的顺序与其在输入中的顺序相同。每行首先打印任务的名称和一个 : ，之后为空格隔开的 4 个整数，分别表示任务开始时间、任务实际执行时间（如果有涉及到 Out 中读取数据和输出数据，需要包含在此时间中）、片上存储资源占用量（单位：B）、Out 空间占用量（单位：B）。两个占用量中一定有一个为 0。
3. hardware_info：硬件资源信息。在 --- task_info --- 行后，有一行五个空格隔开的整数。按顺序分别是 Buffer1、Buffer2、Buffer3、Buffer4 和 Buffer5 这五类资源。对于任务 1 可以沿用原有输入；对于任务 2 必须输出不受约束下的最佳资源配置（单位：B）。

格式示例如下：

--- task_order ---
A_task1, A_task3, A_task2
B_task1, B_task2, B_task3
C_task1, C_task2, C_task3
D_task1, D_task2, D_task3
E_task1, E_task2, E_task3
--- task_info ---
A_task1: 0 2300 6144 0
B_task2: 2300 1300 0 3072
--- hardware_info ---
65536 65536 262144 262144 65536

0
--- task_info ---
B B_task0 55 1 12288
B B_task1 16 1 3072
B B_task10 6 1 256
B B_task11 27 1 3
B B_task12 12 1 256
B B_task13 6 1 256
B B_task2 46 1 256
B B_task3 8 1 768
B B_task4 55 1 12288
B B_task5 101 1 12288
B B_task6 85 1 12288
B B_task7 27 1 6144
B B_task8 11 1 1536
B B_task9 48 1 256
D D_task0 1286 1 12288
--- memory ---
262144 65536 65536 262144 1048576
--- dependency ---
B_task10 B_task11
B_task4 B_task6
B_task3 B_task10
B_task11 B_task9
B_task9 B_task12
B_task9 B_task2
B_task5 B_task7
B_task7 B_task12
B_task10 B_task9
B_task3 B_task13
D_task0 B_task4
D_task0 B_task0
B_task5 B_task12
B_task1 B_task8
B_task12 B_task2
B_task13 B_task10
B_task0 B_task5
B_task8 B_task3
B_task0 B_task4
B_task7 B_task1

--- task_order ---

B_task0, B_task5, B_task7, B_task1, B_task8, B_task3, B_task13, B_task10, B_task11, B_task9, B_task12, B_task2, B_task4, B_task6

D_task0

--- task_info ---
B_task0: 1286 55 12288 0
B_task1: 1471 16 3072 0
B_task10: 1514 6 256 0
B_task11: 1520 27 3 0
B_task12: 1595 12 256 0
B_task13: 1507 6 256 0
B_task2: 1607 46 256 0
B_task3: 1499 8 768 0
B_task4: 1657 55 12288 0
B_task5: 1342 101 12288 0
B_task6: 1712 85 12288 0
B_task7: 1443 27 6144 0
B_task8: 1488 11 1536 0
B_task9: 1547 48 256 0
D_task0: 0 1286 12288 0
--- hardware_info ---
262144 65536 65536 262144 1048576

样例 1 解释

在样例中，各个 task 之间的依赖关系如下图所示。此样例中只包含了 B 和 D 两个队列。

根据已知的依赖关系，在重排流水线时，D_task0 任务应首先执行，完成之后再执行 B_task0 任务，之后再依次执行其他任务。（样例为简单化，没有列举出不同队列间并行执行任务的情况，但实际用例中存在），如下图所示：

根据重排后的流水线执行顺序，可以分别计算出各个 Buffer 所需的内存大小，进而计算出面积。

评分规则

任务 1 的评分规则

时间基线是 100000 ns，你求解结果的整体执行时间是 $T_{\mathrm{total}}$（ns），队列 A 和队列 B 的时间分别是 $T_A$ 和 $T_B$（ns），评分通过以下公式计算：

$$Score_{\mathrm{Perf}}=\frac{100000}{T_{\mathrm{total}}}\times80\%+\frac{T_A+T_B}{T_{\mathrm{total}}}\times20\%$$

注意，只有在通过正确性检测之后，才能参与排名拿到分数。

为保证通过正确性测试，按照题目要求，并保证：

1. 输出文件中的内容格式应符合要求；
2. 每个队列需要执行的任务数量在重排前后应该相同；
3. 同一队列内的任务必须能串行执行；
4. 有依赖关系的两个任务必须能正确执行；
5. 同一时刻，片上资源的使用大小不能超出资源上限；
6. 若某任务使用了内存 Out，则该任务的实际执行时间必须考虑内存读写时间。
7. 答案中所有的数字均为非负整数，同时不超过 $10^{12}$。

任务 2 的评分规则

$$Score_{\mathrm{PA}}=\frac{1000\times\mathrm{Score}_{\mathrm{Perf}}}{\mathrm{Area}}$$

其中 $Score_{\mathrm{Perf}}$ 为任务 1 中的性能评价公式，值越高表明性能越好；Area 则是存储资源的面积，值越低越好。

每个测试点的分数

对于任务一的测试点，得分为：

$$Score=\mathrm{BaseScore}+S_{\log}(Score_{\mathrm{Perf}})$$

对于任务二的测试点，得分为：

$$Score=\mathrm{BaseScore}+S_{\log}(Score_{\mathrm{PA}})$$

其中 BaseScore 为通过正确性校验后的基础得分，每个测试点 5 分。其中 $S_{\log}$ 为标准排名得分函数，定义如下：

$$S_{\log}=\mathrm{BaseRankScore}\times\frac{\log(N+1)-\log(R)}{\log(N+1)}$$

其中 BaseRankScore 为通过排名部分总分，每个测试点 5 分，$N$ 为在该测试点通过正确性校验的参赛选手总人数，$R$ 为该测试点中你的排名（1 表示最好）。

题目总分数

本题目以 最后一次 提交的程序分数为准，总分数为所有测试点得分之和。

在本系统上的评分系统有一些差异，当所有测试点均通过正确性校验时即视为通过本题，显示的总得分为实际得分的 2 倍。

为了方便大家进行调试，我们提供了所有测试点的输入文件，同时提供了一个验证程序用于检查输出文件的正确性。验证程序接收两个参数，分别为输入文件的路径和答案文件的路径，使用方法如下：

./verifier <input_file> <output_file>

验证通过会打印 Verification passed! 和一些统计信息。

Verification passed!
Total execution time: 1076543 ns
Queue A execution time: 31048 ns
Queue B execution time: 1054324 ns
Area: 21.9 mm^2
Score_Perf: 0.275952

本题的 10 组输入以及 verifier 可执行文件见本题附件区的 down.zip。提供的 verifier 仅适用于 x86-64 Linux 环境。Windows 用户可通过 WSL 或虚拟机使用。首次运行前，请执行 chmod +x verifier 赋予执行权限，然后使用上述命令校验方案并计算性能指标。