Exploiting community structure for floating-point precision tuning
Exploiting community structure for floating-point precision tuning
复制标题
DOI：
10.1145/3213846.3213862
复制
发表时间：
2018-07
期刊：
影响因子：
--
通讯作者：
Hui Guo;Cindy Rubio-González
中科院分区：
文献类型：
--
作者：
Hui Guo;Cindy Rubio-González
浮点类型因其复杂的表示而臭名昭著。混合精度的有效使用，即在不同的计算中使用不同的精度，对于实现精度和性能之间的良好平衡至关重要。不幸的是，即使对于数值专家来说，推理混合精度也很困难。已经提出了系统地搜索浮点变量和/或程序指令以找到给定程序的更快、混合精度版本的技术。然而，这些技术的特点是其黑盒性质，并且由于搜索空间大而面临可扩展性限制。在本文中，我们利用浮点变量的社区结构来设计用于精度调整的可扩展分层搜索。具体来说，我们执行依赖性分析和边缘分析来创建呈现浮点变量网络的加权依赖性图。然后，我们将网络上的层次结构构建为社区检测问题，并提出一种迭代降低社区精度的层次搜索算法。我们在 HiFPTuner 工具中实现了我们的算法，并表明它在 75.9% 的实验中表现出比现有技术更高的搜索效率，平均搜索时间减少了 59.6%。此外，HiFPTuner 在 51.7% 的实验中找到了更有利可图的配置，其中一种已知与通过详尽搜索找到的全局最优配置一样好。
Floating-point types are notorious for their intricate representation. The effective use of mixed precision, i.e., using various precisions in different computations, is critical to achieve a good balance between accuracy and performance. Unfortunately, reasoning about mixed precision is difficult even for numerical experts. Techniques have been proposed to systematically search over floating-point variables and/or program instructions to find a faster, mixed-precision version of a given program. These techniques, however, are characterized by their black box nature, and face scalability limitations due to the large search space. In this paper, we exploit the community structure of floating-point variables to devise a scalable hierarchical search for precision tuning. Specifically, we perform dependence analysis and edge profiling to create a weighted dependence graph that presents a network of floating-point variables. We then formulate hierarchy construction on the network as a community detection problem, and present a hierarchical search algorithm that iteratively lowers precision with regard to communities. We implement our algorithm in the tool HiFPTuner, and show that it exhibits higher search efficiency over the state of the art for 75.9% of the experiments taking 59.6% less search time on average. Moreover, HiFPTuner finds more profitable configurations for 51.7% of the experiments, with one known to be as good as the global optimum found through exhaustive search.