← 返回题目列表

Codeforces · 1953/A

A. 保精度求和算法

中文机器翻译题面 查看原题

在经典的高性能计算领域(HPC)中,绝大多数计算都是以双精度64位浮点数(fp64、双精度、IEEE-754 binary64)进行的。深度神经网络 (DNN) 的兴起使得硬件 (HW) 能够处理 16 位浮点数(fp16、半精度、IEEE-754 二进制 16),每秒浮点运算(触发器)速度提高了 16 倍,内存带宽 (BW) 提高了 4 倍。同时,fp16 数字的短尾数和指数会导致计算精度的快速损失,产生错误的计算结果,而没有任何选项可以在大小大于约 $$$2000$$$ 的归约运算中恢复它们。由于 HPC 中的典型问题规模远大于 $$$2000$$$,这使得 fp16 计算几乎毫无用处。为了克服这一主要障碍,需要更智能的归约运算算法。

描述。有一个以 IEEE-754 二进制 64(双精度,fp64)格式 $$$x_i$$$ 存储的浮点数序列,长度为 $$$N$$$。该序列需要求和为 $$$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 二进制 64 值。

请注意,实际的二进制 64 值并不总是完全等于给定的十进制值。相反,实际给定值是用二进制 64 表示的最接近的数字。当读取输入时,大多数编程语言都会自动为您进行转换。

保证序列中的每个数字要么是 $$$0$$$,要么绝对值在 $$$10^{-300}$$$ 和 $$$10^{300}$$$ 之间(含)。

输出

打印一行来描述求和过程。该行应包含求和的编码算法。我们使用此编码进行实际求和并报告结果,以避免需要寻找能够本地执行 fp16 运算的硬件。

编码算法由要使用的数据类型组成,后跟使用该数据类型求和的值列表。该算法的结果是给定值的总和,按照给定数据类型从左到右按给定顺序计算。它看起来如下:

{类型:值_1,值_2,...,值_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$$$。

每个输入值必须仅使用一次。

示例

输入 #1

2 -4.815473e+04 -1.862622e+04

输出 #1

{d:1,2}

输入 #2

3 -4.815473e+01 1.862622e+02 2.997603e+02

输出 #2

{d:1,2,3}

注意

评分:
在这个问题中,有 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}\text{.}$$$$$$

例如,如果计算总和为 $$$99.0$$$,预期总和为 $$$100.0$$$,则准确度得分为 $$$A = \left(\frac{\left|99 - 100\right|}{\left|100\right|}\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$$$,如果 $$$\left|j - i\right| > 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}\text{.}$$$$$$ 然后数据得分计算为: $$$$$$D = \frac{10.0}{\sqrt{C + 0.5}}\text{.}$$$$$$ 最后,将准确度得分代入帐户中,测试分数为: $$$$$$\mathit{Score} = \frac{D}{A}\text{.}$$$$$$ 主要测试的所有单独测试分数相加得出最终分数。检查示例,但不计入分数。

本题准备了两组测试:初步测试和最终测试。在比赛期间,每份提交的作品都会经过初步测试。比赛结束后,对于每位参赛者:

- 评审团采用初步测试非零分的最新提交材料。
- 此提交已在最后一组测试中进行了测试。
- 参赛者根据最终测试的表现进行排名。

两组测试的设计相似,但不相同。