cuFFT并非不可战胜！

背景介绍¶

密度泛函理论（Density Functional Theory，简称DFT）在材料计算，医药和分子化学等领域扮演着重要的角色，是微观世界建模的重要工具。在高性能计算技术与机器学习方法飞速发展的今天，理论计算有望更快速地突破科学边界，解决更多的实际问题。密度泛函理论兼具效率与精度，正在释放出巨大的潜力。

ABACUS作为积淀深厚的国产开源密度泛函计算软件，致力于结合高性能计算和机器学习方法，推动电子结构新算法的发展和普及，为更多科研人员、老师和学生们提供更方便易用的免费开源软件，为更多开发者提供一个框架清晰、方便上手的开发平台，努力将第一性原理方法打造成面向实际应用场景的解决方案。

在ABACUS等DFT软件计算中有一个很重要的倒易空间到实空间的转换，涉及到快速傅里叶算法也就是FFT。不过这个转化和通常的FFT不同，它带有一定的稀疏性。我们可以将在倒易空间需要变换的数据视为是一个球体，这个球体位于一个三维的正立方体中，球体直径小于等于立方体边长的一半，立方体其他部分置零，然后将整个立方体输入到FFT中进行变换得到实空间数据。但受限于接口问题目前只能应用cuFFT或者FFTW等成熟的库，没法有效利用数据的稀疏性。在实际计算中，FFT的计算占比达30%以上，是一个相当大的计算瓶颈。我们以ABACUS为基础，将相关问题抽象出来，提供了一个物理意义无关的优化问题模型。

赛题描述¶

考虑立方体$D$，定义其边长为$c$，球$R$为$D$中的一个球体，球的半径为$r$，$r≤c/4$。

为简化起见，考虑$D$和$R$的中心重合位于原点处。注意：这里边长都是整数，格点位于每个整点处，若长度为$m$，则格点数为$m+1$。若边长为奇数，则原点分布于正中间，若边长为偶数，则自动扩充边长为变长$+1$。

FFT输入数据示意图，仅有彩色球体为有效数据，其余部分置为零。

输入¶

• 立方体边长$c$
• 球体半径$r$
• 三维复数数据$A$，$A$的大小为$c$的3次方，以一维数组形式连续存储。$A$的初始化说明如下：
  • 遍历$A$中的数据元素P(x,y,z);
  • 如果$P$到球心距离小于半径$r$，则P=random_complex;
  • 否则$P$置零。

输出¶

• $A$经过逆傅里叶变化后的输出数组$B$。

其中，A是频域空间，B是时域空间。

评测说明¶

• 初始代码中提供了一份使用cuFFT作为实现的代码，以下简称为Baseline版本。要求选手实现的版本以下简称为Acclerate版本。
• Baseline提供了编译说明，可以在Github下载，Baseline相关问题可直接在仓库提交ISSUE讨论。
• Acclerate的输出应该和Baseline一致（允许误差：$1*10^{-5}$）。

你可以在/data/software/tools/cufft找到评测用的输入数据

评分标准¶

• 将在规定的硬件平台上运行选手的程序，分别对于如下大小的c和r进行10次运行，取平均耗时为最终耗时结果：

• 一个complex为16 byte，最大的输入数据集512^3次方为2GB数据大小。
• 每个样例分别取Accelerate和Baseline的耗时之比，计算所有样例比值的加权平均为最终评分标准。
• IO时间不算在你的评分时间中
• 注：本题采用并行评测的方式，评测过程中返回已完成的点数可能并非按照顺序，请知悉。

handout使用方式¶

• compile.sh：编译你的程序
• run.sh c r num：在c, r的条件下，用你的程序中处理data中的num个数据。

提交方式¶

提交你的answer.cpp，我们会编译并运行。

参考文档¶

• ABACUS Documentation ‒ ABACUS documentation
• https://docs.nvidia.com/cuda/pdf/CUFFT_Library.pdf
• FFT and sparse FFT techniques and applications

附件¶

初始工作区

下载cufft_handout_update.zip