In the classic high-performance computing domain (HPC), the vast majority of computations are conducted in double-precision 64-bit floating-point numbers (fp64, double-precision, IEEE-754 binary64). The rise of Deep Neural Networks (DNNs) resulted in hardware (HW) capable of processing 16-bit floating point numbers (fp16, half precision, IEEE-754 binary16) up to 16 times faster in terms of floating-point operations per second (flops) and up to 4 times faster in terms of memory bandwidth (BW). At the same time, the short mantissa and exponent for fp16 numbers lead to a very fast loss of precision of computations, producing wrong computational results without any option to recover them in reduction operations of size greater than approximately $$$2000$$$. As the typical problem size in HPC is much larger than $$$2000$$$, this makes fp16 computations almost useless. To surmount this major roadblock, smarter algorithms for reduction operations are needed.

Description. There is a sequence of floating-point numbers stored in IEEE-754 binary64 (double precision, fp64) format $$$x_i$$$ of length $$$N$$$. The sequence needs to be summed up to $$$S = x_1 + x_2 + \ldots + x_N$$$. As professional computer equipment with native support for fp16 is usually unavailable to the general audience, we propose to do operations in a simplified simulated environment, that is, we do computations in fp64 format with mantissa and exponent cut to the range admissible in fp16. In particular, small values that do not fit fp16 admissible range turn into zeros, while excessively large values turn into infinities.

Objective. Your objective is to sum up as many sequences as possible as fast as possible and as accurately as possible. Please note that you may do summation in fp64 format, but the summation process would be slow though accurate. If you do plain summation in fp16 format, it can be fast, but inaccurate, especially for larger sequences.

In this problem, there are 2 example tests and 76 main tests. Each main test is scored as follows.

The first part of scoring is related to accuracy. We denote the sum calculated by the solution as $$$S_c$$$. Next, we calculate the expected sum $$$S_e$$$ as precisely as we can, and store it in binary64 format. Then the accuracy score is calculated as: $$$$$$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{.}$$$$$$

For example, if the calculated sum is $$$99.0$$$ and the expected sum is $$$100.0$$$, the accuracy score is $$$A = \left(\frac{\left|99 - 100\right|}{\left|100\right|}\right)^{0.05} = \left(\frac{1}{100}\right)^{0.05} = 0.794328...$$$. If the relative error is $$$\frac{1}{1000}$$$, the accuracy score is $$$A = \left(\frac{1}{1000}\right)^{0.05} = 0.707945...$$$. If the solution is exact, we get $$$A = \left(10^{-20}\right)^{0.05} = 0.1$$$.

The second part of scoring is related to the types used for summation. We define the weight $$$W$$$ of the algorithm as follows. If the algorithm performs $$$k$$$ additions (adding up $$$k + 1$$$ values), its weight is:

• $$$1 \cdot k$$$ for half precision,
• $$$2 \cdot k$$$ for single precision,
• $$$4 \cdot k$$$ for double precision.

The third part of scoring is related to a penalty for memory reads. We list the $$$N$$$ numbers appearing in the algorithm from left to right, omitting all curly brackets. We divide the numbers into consecutive blocks of 16 elements; the last block may contain less than 16 elements. In each block, its first element $$$i$$$ initiates a memory read. For every other element $$$j$$$ of the block, if $$$\left|j - i\right| > 15$$$, it is too far from the memory which was read for this block, and you get a penalty. The penalties increase gradually: the $$$x$$$-th penalty you get will be $$$x / 20\,000$$$. The penalty counter $$$x$$$ is global, it persists across different blocks. All the penalties add up to the total penalty $$$P$$$.

For example, consider the following algorithm: {s:1,2,3,4,5,6,7,8,9,10,{d:20,19,18,17,16},11,12,13,14,15}. It performs $$$15$$$ additions in single precision, and one of its elements is also an algorithm which performs $$$4$$$ additions in double precision. Thus its weight is $$$W = 15 \cdot 2 + 4 \cdot 4 = 46$$$. The first memory read block is 1,2,3,4,5,6,7,8,9,10,20,19,18,17,16,11, the initial read is at position $$$1$$$, and the positions in the block that are more than $$$15$$$ units away are $$$20$$$, $$$19$$$, $$$18$$$, and $$$17$$$, so we get $$$4$$$ penalties. The second memory read block is 12,13,14,15, the initial read is at position $$$12$$$, and there are no penalties. The total penalty is $$$P = (1 + 2 + 3 + 4) / 20\,000 = 0.0005$$$.

Putting the second and third part together, we calculate the average cost for a single operation as: $$$$$$C = \frac{W + P}{N-1}\text{.}$$$$$$ Then the data score is calculated as: $$$$$$D = \frac{10.0}{\sqrt{C + 0.5}}\text{.}$$$$$$ Lastly, taking the accuracy score into account, the score for the test is: $$$$$$\mathit{Score} = \frac{D}{A}\text{.}$$$$$$ All individual test scores for main tests sum up together to produce the final score. Examples are checked, but do not contribute to the score.