登录 [F2] | 注册 | 找回密码 | 软件下载 | 更新历史 | 关于本站 | 管理团队
首页 排行榜 录像 雷界 论坛 教程 雷神殿 我的地盘 新手上路
[技术]【实验】如何用显卡计算高级局面的3BV.精 (7/443)
 [雷神] 王嘉宁 发表于 2022年9月23日
计算3BV的问题,本质上是个连通域标记问题(Connected-Component-Labelling),相关算法可分为串行和并行两种。其中,并行算法具有一定的学术研究价值,在2012-2015年之间甚至曾经成为硕士研究课题。

幸好,一个朴素的算法不难想到,所以本人将其实现并首先贴出。

本人实现了两个版本:
第一个:https://pastebin.com/mEhc2GtZ

第二个(貌似有些问题):https://pastebin.com/3RXZ9esW

其中,第一个版本暂时没有发现问题;第二个版本貌似有些问题,但已经接近正确。

在一块笔记本电脑上的型号为1050ti的显卡上,第一个版本的计算速度约为1200000局/秒;而作为对比,同样价格的CPU的计算速度约为300000局/秒(用ms_toollib来测算)。

第一个版本打包后的exe文件如下(为了看见打印的结果,请在命令行执行):
链接:https://pan.baidu.com/s/1c21IwUDb3tXVpEGANzruOg
提取码:bbbv

为了运行这个exe文件,你需要:
(1)拥有一块英伟达的显卡;
(2)如果运行不成功,安装一下cuda11:https://developer.nvidia.com/cuda-11.0-download-archive(大约2.7G);
(3)进一步,如果你想从源文件亲自编译得到exe,还需要安装Visual Studio。

其实无论对于何种局面,相比扫的速度,计算3BV总是快得多。用显卡计算3BV主要目的是对aradesh在国际网上发帖的回应https://minesweepergame.com/forum/viewtopic.php?f=15&t=1225&sid=989390beb51c47c43dd4116317952cbb,在这个贴子中,他说下次有人算这个东西要算一千万亿局的,非常嚣张
最近一次修改:2022-9-23 22:38:48
回复此主题
第 1 楼
 [雷圣] 濮天羿 回复于 2022年9月23日
有无可执行文件?
第 2 楼
 [雷圣] 濮天羿 回复于 2022年9月23日
看到了算数字这一步。算数字有三种方法:
1. 遇到雷则在周围+1
2. 遇到数字则数雷
3. 整个局面(数组形式,雷1,非雷0)与特定矩阵相乘,结果直接就是包含所有数字的局面。

在cpu上执行的时候,1最快。显卡上也许应该考虑3?(不懂显卡指令集
第 3 楼
 [雷神] 王嘉宁 回复于 2022年9月23日
如果目的单纯是算3BV,那么甚至都不用算数字,是数字一律填成1就好,不影响结果。
第 4 楼
 [雷圣] 濮天羿 回复于 2022年9月24日
GTX 1660 Ti

一共: 6553600
耗时:1.824000
速度:3592982.500000
第 5 楼
 [雷神] 毛涤尘 回复于 2022年9月24日
1660ti=1050ti*3
第 6 楼
 [雷圣] 郭锦洋 回复于 2022年9月26日
那么1000000000000/1200000/3600=231.481481h就能达到阿拉代谢的量
第 7 楼
 [雷圣] 郭锦洋 回复于 2022年9月26日
可以先来个10亿验证一下算法
  共 7 篇回复  首页 | 上一页 | 下一页 | 末页  现在是第 1/1 页
楼主信息
Copyright @ 2008 扫雷网 Saolei.wang 版权所有 陕ICP备19026089号-1