非对称容差关系粗糙近似集的GPU加速方法

doi:10.19678/j.issn.1000-3428.0070473

摘要/Abstract

摘要：

大数据时代信息来源纷繁复杂, 收集数据形成的信息系统很难保证其完整性。在越来越大的不完备信息系统(IIS)中, 使用基于非对称容差关系的粗糙集理论进行知识蒸馏, 提升近似集的计算速度成为其应用之前必须要解决的问题。针对非对称容差关系的冗余容差类问题, 提出非对称容差关系的改进方案, 设计不完备信息系统中上、下近似集的布尔矩阵表示方法, 计算非对称容差关系的粗糙近似集的矩阵分块算法, 并在图像处理单元(GPU)上实现近似集计算过程的加速, 提高近似集的计算效率。另外, 针对GPU存储空间有限的现状, 构建不完备信息系统中对象之间的层次结构及其算法, 将全局关系矩阵转换成多个局部关系矩阵, 缓解计算最近容差类过程中GPU存储压力。在UCI数据集和生成数据集上的实验结果表明, 基于最近容差关系的容差类数量相较于基准情况明显减少, 同时, 矩阵分块算法在GPU上实现了对近似集计算过程的有效加速, 相比CPU串行计算和分布式并行计算, GPU分块算法执行速度平均提高了16.69倍和3.89倍。

关键词: 图像处理单元, 近似集, 最近容差关系, 矩阵分块, 不完备信息系统

Abstract:

In the era of big data, information sources are diverse and complex, making it difficult to ensure the integrity of the information systems formed from the collected data. In increasingly Incomplete Information Systems (IIS), using rough set theory based on asymmetric tolerance relations for knowledge distillation and improving the calculation speed of approximation sets are critical issues that must be addressed before their application. An improved scheme is proposed for the redundant tolerance class problem of asymmetric tolerance relations. A Boolean matrix representation method for the upper and lower approximation sets in incomplete information systems is designed, and a matrix-partitioning algorithm for calculating rough approximation sets of asymmetric tolerance relations is proposed. Furthermore, the acceleration of the approximation set calculation process is implemented on a Graphics Processing Unit (GPU) to improve the calculation efficiency of the approximation sets. Furthermore, given the limited storage space of GPUs, a hierarchical structure and its algorithm for objects in incomplete information systems are constructed, converting the global relationship matrix into multiple local relationship matrices to alleviate the storage pressure on GPUs during the calculation of the nearest tolerance classes. Experimental results on the UCI and generated datasets show that the number of tolerance classes based on the nearest tolerance relations is significantly reduced compared to the baseline case. Additionally, the matrix-partitioning algorithm effectively accelerates the approximate set calculation process for GPUs. Compared with CPU serial computation and distributed parallel computation, the GPU partitioning algorithm executes at an average speed of 16.69 times and 3.89 times faster.

Key words: Graphic Processing Unit (GPU), approximation sets, nearest tolerance relation, block-matrix, Incomplete Information System (IIS)

吴正江, 王梦松, 武星晨. 非对称容差关系粗糙近似集的GPU加速方法[J]. 计算机工程, 2026, 52(8): 247-259.

WU Zhengjiang, WANG Mengsong, WU Xingchen. GPU Acceleration Method for Rough Approximation Sets of Asymmetric Tolerance Relation[J]. Computer Engineering, 2026, 52(8): 247-259.

https://www.ecice06.com/CN/Y2026/V52/I8/247

图/表 12

图1 非对称容差关系到最近容差关系的转换

Fig.1 Conversion of the asymmetric tolerance relation to the nearest tolerance relation

图2 矩阵分块算法示意图

Fig.2 Schematic diagram of the matrix-block algorithm

图3 计算时间百分比

Fig.3 The percentage of computing time

图4 3种算法关系图

Fig.4 Relationship diagram of three algorithms

图5 分块大小与处理时间和内存的关系

Fig.5 The relationship between block size, processing time and memory

图6 分块大小与处理时间和显存的关系

Fig.6 The relationship between block size, processing time and video memory

图7 矩阵分块算法在CPU和GPU上的计算时间

Fig.7 Computation time of matrix block algorithm on CPU and GPU

参考文献 29

1	PAWLAK Z . Rough sets. International Journal of Computer[WT《Times New Roman》] & Information Sciences, 1982, 11 (5): 341- 356.
2	WANG G Q , LI T R , ZHANG P F , et al. Double-local rough sets for efficient data mining. Information Sciences, 2021, 571, 475- 498. doi: 10.1016/j.ins.2021.05.007
3	赵洁, 叶文浩, 梁周扬, 等. 基于不一致近邻的模糊粗糙集特征选择. 计算机工程, 2024, 50 (1): 110- 119. doi: 10.19678/j.issn.1000-3428.0066458
	ZHAO J , YE W H , LIANG Z Y , et al. Fuzzy rough set feature selection based on inconsistent nearest neighbors. Computer Engineering, 2024, 50 (1): 110- 119. doi: 10.19678/j.issn.1000-3428.0066458
4	YAO W , ZHANG G , ZHOU C J . Real-valued hemimetric-based fuzzy rough sets and an application to contour extraction of digital surfaces. Fuzzy Sets and Systems, 2023, 459, 201- 219. doi: 10.1016/j.fss.2022.07.010
5	HU Q H , YU D R , LIU J F , et al. Neighborhood rough set based heterogeneous feature subset selection. Information Sciences: An International Journal, 2008, 178 (18): 3577- 3594. doi: 10.1016/j.ins.2008.05.024
6	ZHANG J B , LI T R , CHEN H M . Composite rough sets for dynamic data mining. Information Sciences, 2014, 257, 81- 100. doi: 10.1016/j.ins.2013.08.016
7	GUAN Y Y , WANG H K . Set-valued information systems. Information Sciences, 2006, 176 (17): 2507- 2525. doi: 10.1016/j.ins.2005.12.007
8	KRYSZKIEWICZM M . Rough set approach to incomplete information systems. Information Sciences, 1998, 112 (1-4): 39- 49. doi: 10.1016/S0020-0255(98)10019-1
9	STEFANOWSKI J, TSOUKIAS A, On the extension of rough sets under incomplete information[C]//Proceedings of International Workshop on Rough Sets, Fuzzy Sets, Data Mining, and Granular-Soft Computing. Berlin, Germany: Springer, 1999: 73-81.
10	袁静珍, 田祥宏, 马晓. 基于多粒度决策粗糙集的云计算产品分类方法. 控制工程, 2021, 28 (1): 55- 61.
	YUAN J Z , TIAN X H , MA X . Cloud computing product classification method based on multi-granularity decision rough set. Control Engineering of China, 2021, 28 (1): 55- 61.
11	WU Z J , WANG H , CHEN N , et al. Semi-monolayer covering rough set on set-valued information systems and its efficient computation. Information Journal of Approximate Reasoning, 2021, 130, 83- 106. doi: 10.1016/j.ijar.2020.12.011
12	孙妍, 米据生, 冯涛, 等. 变精度极大相容块粗糙集模型及其属性约简. 计算机科学与探索, 2020, 14 (5): 892- 900.
	SUN Y , MI J S , FENG T , et al. Maximum consistent block based variable precision rough set model and attribute reduction. Journal of Frontiers of Computer Science and Technology, 2020, 14 (5): 892- 900.
13	HAMED A , SOBHY A , NASSAR H . Distributed approach for computing rough set approximations of big incomplete information systems. Information Sciences, 2021, 547, 427- 449. doi: 10.1016/j.ins.2020.08.049
14	ROHMAT S R, HAIRULNIZAM M, SHAHREEN K, et al. A relative tolerance relation of rough set for incomplete information system[C]//Proceedings of the 3rd International Conference on Soft Computing and Data Mining. Berlin, Germany: Springer, 2018: 72-81.
15	DERIS M M, HAMID M A, NORAINI I, et al. Data reduction using similarity class and enhanced tolerance relation for complete and incomplete information systems[C]//Proceedings of the 10th International Conference on Information and Communication Systems. Washington D.C., USA: IEEE Press, 2019: 134-139.
16	吴正江, 吕成功, 王梦松. 融合GPU的拟单层覆盖近似集计算方法. 计算机工程, 2024, 50 (5): 71- 82. doi: 10.19678/j.issn.1000-3428.0067603
	WU Z J , LV C G , WANG M S . Calculation method for semi-monolayer covering approximation sets fushing GPU. Computer Engineering, 2024, 50 (5): 71- 82. doi: 10.19678/j.issn.1000-3428.0067603
17	XIA H, CHEN Z Z, WU Y M, et al. Attribute reduction method based on improved granular ball neighborhood rough set[C]//Proceedings of the 7th International Conference on Cloud Computing and Big Data Analytics. Washington D.C., USA: IEEE Press, 2022: 13-16.
18	危前进, 魏继鹏, 古天龙, 等. 粗糙集多目标并行属性约简算法. 软件学报, 2022, 33 (7): 2599- 2617.
	WEI Q J , WEI J P , GU T L , et al. Multi-objective parallel attribute reduction algorithm in rough set. Journal of Software, 2022, 33 (7): 2599- 2617.
19	ZHANG J B , WONG J S , PAN Y , et al. A parallel matrix-based method for computing approximations in incomplete information systems. IEEE Transactions on Knowledge and Data Engineering, 2015, 27 (2): 326- 339. doi: 10.1109/TKDE.2014.2330821
20	FARYAL N , USMAN Q , MUHAMMAD S R . A parallel rule-based approach to compute rough approximations of dominance based rough set theory. Engineering Applications of Artificial Intelligence, 2022, 115, 105285. doi: 10.1016/j.engappai.2022.105285
21	RAZA M S , QAMAR U . A parallel approach to calculate lower and upper approximations in dominance based rough set theory. Applied Soft Computing Journal, 2019, 84, 105699. doi: 10.1016/j.asoc.2019.105699
22	倪鹏, 刘阳明, 赵素云, 等. 动态模糊粗糙特征选取算法. 计算机科学与探索, 2020, 14 (2): 236- 243.
	NI P , LIU Y M , ZHAO S Y , et al. Dynamic fuzzy rough feature selection algorithm. Journal of Frontiers of Computer Science and Technology, 2020, 14 (2): 236- 243.
23	ZHANG J B , ZHU Y , PAN Y , et al. Efficient parallel Boolean matrix based algorithms for computing composite rough set approximations. Information Sciences, 2016, 329, 287- 302. doi: 10.1016/j.ins.2015.09.022
24	WU Z J , CHEN N , GAO Y . Semi-monolayer cover rough set: concept, property and granular algorithm. Information Sciences, 2018, 456, 97- 112. doi: 10.1016/j.ins.2018.04.066
25	JING S Y , LI G L , ZENG K , et al. Efficient parallel algorithm for computing rough set approximation on GPU. Soft Computing, 2018, 22 (22): 7553- 7569. doi: 10.1007/s00500-018-3050-z
26	GAO Y , LV C W , WU Z J . Attribute reduction of boolean matrix in neighborhood rough set model. International Journal of Computational Intelligence Systems, 2020, 13 (1): 1473- 1482. doi: 10.2991/ijcis.d.200915.004
27	HU Y M, LI T R, HU J, et al. Parallel attribute reduction algorithms based on CUDA[C]//Proceedings of International FLINS Conference. Singapore: [s. n], 2018: 1-10.
28	NVIDIA. CUDA toolkit documentation V11.1.0[EB/OL]. [2024-09-05]. https://docs.nvidia.com/cuda/archive/11.1.0/.
29	CuPy. CuPy API reference[EB/OL]. [2024-09-05]. https://pypi.org/project/cupy-cuda111/10.3.1.

[1]	吴正江, 武星晨, 连涛, 王梦松. 基于图优化的容差关系粗糙集分布式算法[J]. 计算机工程, 2026, 52(3): 346-354.
[2]	高昂, 王银山, 燕雯, 宋昌成, 王龙, 姚二林. 面向鲲鹏处理器的HPL-MxP多重lookahead优化[J]. 计算机工程, 2025, 51(8): 354-363.
[3]	吴正江, 吕成功, 王梦松. 融合GPU的拟单层覆盖近似集计算方法[J]. 计算机工程, 2024, 50(5): 71-82.
[4]	徐怡, 侯迪. 基于矩阵的粗糙集近似集快速计算算法[J]. 计算机工程, 2023, 49(5): 22-28.
[5]	吴正江, 张亚宁, 张真, 梅秋雨, 杨天. 拟单层覆盖粗糙集中近似集的增量更新算法[J]. 计算机工程, 2022, 48(6): 200-206,212.
[6]	方玉玲, 陈庆奎. 基于矩阵转换的卷积计算优化方法[J]. 计算机工程, 2019, 45(7): 217-221,228.
[7]	程凯,田瑾,马瑞琳. 基于GPU的高效稀疏矩阵存储格式研究[J]. 计算机工程, 2018, 44(8): 54-60.
[8]	曹炳汝,刘勇. 基于集对势优势关系的变精度粗糙集模型[J]. 计算机工程, 2015, 41(11): 35-40.
[9]	刘永文, 李天瑞, 陈红梅, 高子喆, 谷小广. 覆盖广义粗糙集中近似集增量更新方法研究[J]. 计算机工程, 2012, 38(2): 156-158.
[10]	陈庆奎, 曹欢欢, 庄松林. 一种GPU集群的动态任务映射策略[J]. 计算机工程, 2012, 38(17): 268-271.
[11]	汪琼枝, 吴涛, 毛军军, 张培根. 基于近似度的不完备信息系统属性约简[J]. 计算机工程, 2011, 37(3): 47-48.
[12]	王炜, 徐章艳, 王帅, 杨炳儒. 不完备信息系统属性约简的矩阵算法[J]. 计算机工程, 2011, 37(14): 36-38.
[13]	朱文强, 伏玉琛. 一种基于粗糙集的社区结构发现算法[J]. 计算机工程, 2011, 37(14): 41-43.
[14]	李晓瑜, 徐章艳, 王炜, 杨炳儒. 不完备信息系统中一种新的求核算法[J]. 计算机工程, 2011, 37(11): 56-58.
[15]	田　文;徐　帆;王宏远;周　波. 基于CUDA的尺度不变特征变换快速算法[J]. 计算机工程, 2010, 36(8): 219-221.

选择文件类型/文献管理软件名称

选择包含的内容