赛灵思FPGA助力解决困扰7年的27皇后难题

作者:陆健锋

有一个古老而著名的N皇后问题,即放置n个皇后在n*n棋牌中,使两两间的皇后不会相互攻击(同一行、同一列、同一斜线上的皇后都会自动攻击),它是回溯算法的典型案例。其26皇后在2009年被解开,但Q(27)的深入拓展持续了六年。

现在,德累斯顿工业大学的托马斯B.普瑞瑟尔团队已经解开了Q(27)问题。可以参考文章“Solving the N-Queens Puzzle for 27 Queens using FPGAs”,在这里他们详述了为什么选择攻克27皇后问题,用了什么样的算法和设计,以及这个过程中的宝贵经验。在9月19日,他们再一次运用大量并行FPGA来获取到了答案:

Q(27) = 234,907,967,154,122,528

普瑞瑟尔团队完成这个挑战用的是Xilinx Vivado HL设计套件工具,他们通过该设计套件工具来合成那些问题解决方案,将问题解决方案放在Xilinx 7系列FPGA的两个套件中来实现,即 KC705 Kintex-7 FPGA Eval Kit 和 VC707 Virtex-7 FPGA Eval Kit。(如果你对27皇后问题的解决方法和经验感兴趣,可以在他们团队的Github page网页上查看到具体细节和代码。)

在一个偶然的参观拥有巨大计算能力的服务器中,发现所提供的参考设计使用了Vivado设计套件,所以普瑞瑟尔博士将其使用到了解决27皇后问题中。在测试中意外发现,和之前的综合结果相比,Vivado HL设计套件在KC705板子上能提升67%的综合能力和7%的速度,在VC707板子上能提升56%的综合能力和2%的速度。时钟频率从271MHz提高到290MHz。Vivado相比较于ISE流程变得明显出众很多,在紧凑性和速度上都得到很好的提升。综合后,他们仍然用了超过一年的时间来计算Q(27)的结果,这也显示了这个计算是多么复杂。

声明:本文为原创文章,转载需注明作者、出处及原文链接,否则,本网站将保留追究其法律责任的权利