Putting Queens in Carry Chains, No̱27
Putting Queens in Carry Chains, No̱27
复制标题
将皇后放入运载链中，No̱27
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Matthias R. Engelhardt
中科院分区：
文献类型：
--
作者：
Thomas B. Preußer;Matthias R. Engelhardt
N-Queens Puzzle是一个有趣的组合问题。到目前为止，还不能用公式计算出广义N × N棋盘上N个非攻击皇后的不同有效放置数。相反，这些数字的计算是基于穷举搜索，其复杂性随着问题大小N而急剧增加。目前已知所有N到26的解数。并行搜索解决方案非常简单。它是通过预先将皇后放置在某个棋盘区域内来实现的。这些预放置划分了搜索空间。预放置的所选范围允许大范围的分区粒度。这种易于划分的特性使得N-Queens Puzzle成为极大并行计算方法的一个很好的展示案例，也是并行计算资源的一个灵活基准。本文介绍了Q27项目，这是一个开源项目，旨在计算27-Queens Puzzle的解决方案计数。这是第一个推动N-Queens Puzzle前沿的项目，它利用了正方形的完整对称群D4。与整个搜索空间的简单探索相比，这将整体计算复杂度降低到八分之一。本文详细介绍了冠状预放置，使分区的整体搜索在这种方法下。相对于计算的物理实现，它描述了硬件结构，有效地探索所产生的子问题，通过利用位级操作和它们的映射到FPGA设备，以及在分布式计算中组织贡献设备的基础设施。几个FPGA平台的性能进行了评估，使用Q27计算作为基准，并提出了一些有趣的意见，从现有的部分解决方案。最后，对剩余运行时间和最终结果的预期大小进行了估计。
The N-Queens Puzzle is a fascinating combinatorial problem. Up to now, the number of distinct valid placements of N non-attacking queens on a generalized N × N chessboard cannot be computed by a formula. The computation of these numbers is instead based on an exhaustive search whose complexity grows dramatically with the problem size N. Solutions counts are currently known for all N up to 26. The parallelization of the search for solutions is embarrassingly simple. It is achieved by pre-placing the queens within a certain board region. These pre-placements partition the search space. The chosen extent of the pre-placement allows for a wide range of the partitioning granularity. This ease of partitioning makes the N-Queens Puzzle a great show-off case for tremendously parallel computation approaches and a flexible benchmark for parallel compute resources. This article presents the Q27 Project, an open-source effort targeting the computation of the solution count of the 27-Queens Puzzle. It is the first undertaking pushing the frontier of the N-Queens Puzzle that exploits the complete symmetry group D4 of the square. This reduces the overall computational complexity already to an eighth in comparison to a naive exploration of the whole search space. This article details the coronal pre-placement that enables the partitioning of the overall search under this approach. With respect to the physical implementation of the computation, it describes the hardware structure that explores the resulting subproblems efficiently by exploiting bit-level operations and their mapping to FPGA devices as well as the infrastructure that organizes the contributing devices in a distributed computation. The performance of several FPGA platforms is evaluated using the Q27 computation as a benchmark, and some intriguing observations obtained from the available partial solutions are presented. Finally, an estimate on the remaining run time and on the expected magnitude of the final result is dared.