【实验】如何用显卡计算高级局面的3BV

首页

排行榜

录像

雷界

论坛

教程

雷神殿

我的地盘

新手上路

[技术]【实验】如何用显卡计算高级局面的3BV.精 (7/672)

　[雷神] 王嘉宁发表于 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 页

楼主信息

赞助广告

近期不再显示