CF1953A.Accuracy-Preserving Summation Algorithm

在经典的高性能计算（HPC）领域，绝大多数计算都是用双精度 64 位浮点数（fp64，双精度，IEEE-754 binary64）进行的。深度神经网络（DNN）的兴起带来了能够处理 16 位浮点数（fp16，半精度，IEEE-754 binary16）的硬件，这些硬件在每秒浮点运算次数（flops）上最高可比 fp64 快 16 倍，在内存带宽（BW）上最高可快 4 倍。然而，fp16 的尾数和指数都很短，导致计算精度损失极快，在规模大于约 $2000$ 的归约操作中会产生错误的计算结果且无法恢复。由于 HPC 中的典型问题规模远大于 $2000$，这使得 fp16 计算几乎毫无用处。为了解决这一重大障碍，需要更智能的归约操作算法。

描述：有一个长度为 $N$ 的浮点数序列 $x_i$，以 IEEE-754 binary64（双精度，fp64）格式存储。需要将该序列求和，得到 $S = x_1 + x_2 + \ldots + x_N$。由于一般用户通常无法获得原生支持 fp16 的专业计算设备，我们建议在一个简化的模拟环境中进行操作，即用 fp64 格式进行计算，但将尾数和指数截断到 fp16 可接受的范围。具体来说，过小的值超出 fp16 可接受范围会变为零，过大的值会变为无穷大。

目标：你的目标是尽可能快且尽可能准确地对尽可能多的序列进行求和。请注意，你可以用 fp64 格式进行求和，但这样虽然准确，速度会很慢。如果用 fp16 格式直接求和，速度会很快，但对于较大的序列则会非常不准确。

输入包含一行。首先是一个整数 $N$，表示序列的长度。接下来是 $N$ 个双精度浮点数，构成序列 $x_i$，其中 $i = 1, \ldots, N$。

变量约束：

• 序列长度：$2 \leq N \leq 1\,000\,000$。
• 序列中每个数的值：为合法的 IEEE-754 binary64 值，以十进制格式给出。

注意，实际的 binary64 值不一定与给定的十进制值完全相等。实际给定的值是 binary64 能表示的最接近的数。在读取输入时，大多数编程语言会自动完成这种转换。

保证序列中的每个数要么为 $0$，要么其绝对值在 $10^{-300}$ 到 $10^{300}$ 之间（含端点）。

输出一行，描述求和过程。该行应包含一个编码后的求和算法。我们用这种编码来实际进行求和并报告结果，以避免必须依赖原生支持 fp16 运算的硬件。

编码算法由所用数据类型和需要用该类型求和的值列表组成。算法的结果是用指定数据类型，从左到右、按给定顺序对这些值求和。格式如下：

{type:value_1,value_2,...,value_k}

如上所示，整个算法被大括号（“{”和“}”）包围。下一个字符表示三种可能的数据类型之一：

• “d” 表示 fp64 求和，
• “s” 表示 fp32 求和，
• “h” 表示 fp16 求和。

然后是一个冒号（“:”）。接下来是不为空的值列表，用逗号（“,”）分隔。注意中间没有空格。

每个值可以是以下之一：

• 一个从 $1$ 到 $N$ 的整数，表示输入序列中的位置：此时该值直接来自输入；
• 另一个算法：此时该值为该算法的结果。

一些例子：

• {d:1,2,3,4} 表示用双精度计算 $x_1 + x_2 + x_3 + x_4$；
• {h:4,3,2,1} 表示用半精度计算 $x_4 + x_3 + x_2 + x_1$；
• {d:{s:3,4},{h:2,1}} 表示用双精度计算 $y + z$，其中：
  • $y$ 用单精度计算 $x_3 + x_4$，
  • $z$ 用半精度计算 $x_2 + x_1$；
• {h:1,4,{d:3,2}} 表示用半精度计算 $x_1 + x_4 + y$，其中：
  • $y$ 用双精度计算 $x_3 + x_2$。

每个输入值必须且只能使用一次。

计分方式

本题有 2 个样例测试和 76 个主测试。每个主测试的得分如下。

第一部分得分与准确性相关。用你的算法计算的和记为 $S_c$。我们尽可能精确地计算期望和 $S_e$，并以 binary64 格式存储。然后准确性得分计算如下：

$$A = \left(\max\left(\frac{\left|S_c - S_e\right|}{\max\left(\left|S_e\right|, 10^{-200}\right)}, 10^{-20}\right)\right)^{0.05}$$

例如，若计算和为 $99.0$，期望和为 $100.0$，则准确性得分为 $A = \left(\frac{|99 - 100|}{|100|}\right)^{0.05} = \left(\frac{1}{100}\right)^{0.05} = 0.794328...$。若相对误差为 $\frac{1}{1000}$，则 $A = \left(\frac{1}{1000}\right)^{0.05} = 0.707945...$。若结果完全准确，则 $A = \left(10^{-20}\right)^{0.05} = 0.1$。

第二部分得分与所用求和类型相关。我们定义算法的权重 $W$。若算法执行了 $k$ 次加法（即加了 $k+1$ 个值），其权重为：

• 半精度：$1 \cdot k$
• 单精度：$2 \cdot k$
• 双精度：$4 \cdot k$
  此外，若算法包含其他算法，其权重递归计算并加到父算法权重上。

第三部分得分与内存读取惩罚相关。我们将算法中出现的 $N$ 个数字按从左到右顺序列出（忽略所有大括号）。将这些数字按每 16 个分为一组，最后一组可能不足 16 个。每组的第一个元素 $i$ 触发一次内存读取。对于该组的其他元素 $j$，若 $|j - i| > 15$，则超出了本组内存读取范围，你会受到惩罚。惩罚逐步增加：第 $x$ 次惩罚为 $x / 20\,000$。惩罚计数器 $x$ 是全局的，在不同分组间持续累加。所有惩罚之和为总惩罚 $P$。

例如，考虑如下算法：{s:1,2,3,4,5,6,7,8,9,10,{d:20,19,18,17,16},11,12,13,14,15}。它用单精度执行 15 次加法，其中有一个元素是用双精度执行 4 次加法的算法。因此其权重为 $W = 15 \cdot 2 + 4 \cdot 4 = 46$。第一个内存读取块为 1,2,3,4,5,6,7,8,9,10,20,19,18,17,16,11，初始读取在位置 1，块内距离超过 15 的位置有 20, 19, 18, 17，因此有 4 次惩罚。第二个块为 12,13,14,15，初始读取在 12，无惩罚。总惩罚为 $P = (1 + 2 + 3 + 4) / 20\,000 = 0.0005$。

将第二、三部分合并，单次操作的平均代价为：

$$C = \frac{W + P}{N-1}$$

然后数据得分为：

$$D = \frac{10.0}{\sqrt{C + 0.5}}$$

最后，综合准确性得分，单个测试的得分为：

$$\mathit{Score} = \frac{D}{A}$$

所有主测试的单项得分相加，得到最终得分。样例测试仅用于检查，不计入总分。

本题准备了两套测试数据：初步测试和最终测试。在比赛期间，每次提交会在初步测试集上评测。比赛结束后，对于每位选手：

• 评测组会选取该选手在初步测试中得分不为零的最后一次提交。
• 这次提交会在最终测试集上评测。
• 选手根据最终测试的表现进行排名。

两套测试数据设计相似，但不完全相同。

由 ChatGPT 4.1 翻译