摘要： 拟单层覆盖粗糙集是一种匹配集值信息系统且有高质量和高效率的粗糙集模型。拟单层覆盖近似集的计算过程中存在大量计算密集且逻辑简单的运算,为此,提出拟单层覆盖近似集的矩阵化表示方法,以利用图形处理器(GPU)强大的计算性能加速计算过程。为了实现这一目标,使用布尔矩阵表示拟单层覆盖近似空间中的元素,引入与集合运算对应的布尔矩阵算子,提出拟单层覆盖粗糙近似集(DE、DA、DE0与DA0)的矩阵表示,并设计矩阵化拟单层覆盖近似集算法(M_SMC)。同时,相应的定理证明了拟单层覆盖近似集的矩阵表示形式与原始定义的等价性。然而,M_SMC运行过程中出现了矩阵存储和计算步骤的内存消耗过多问题。为了将算法部署到显存有限的GPU上,优化矩阵存储和计算步骤,提出分批处理的矩阵化拟单层覆盖近似集算法(BM_SMC)。在10个数据集上的实验结果表明,融合GPU的BM_SMC算法与单纯使用中央处理器(CPU)的BM_SMC算法相比计算效率提高2.16~11.3倍,BM_SMC算法可以在有限的存储空间条件下充分利用GPU,能够有效地提高拟单层覆盖近似集的计算效率。

关键词: 拟单层覆盖近似集, 集值信息系统, 矩阵化, GPU加速, 分批处理

Abstract: A semi-monolayer covering rough set is a high-quality and efficient rough-set model for matching set-valued information systems. There are a large number of computationally intensive and simple logical operations in the calculation process of a semi-monolayer covering approximation set. Therefore, this study proposes a matrix-based algorithm for semi-monolayer covering approximation sets to utilize the powerful computing performance of Graphics Processing Unit(GPU) to accelerate the calculation process. In order to achieve this goal, Boolean matrices are used to represent the elements in the semi-monolayer covering approximate sets. Boolean matrix operators corresponding to set operations are introduced, and a matrix representation of the semi-monolayer covering rough approximation set (DE, DA, DE0, and DA0) is proposed. A matrix based semi-monolayer covering approximation set algorithm (M_SMC) is designed. The corresponding theorems prove the equivalence between the matrix representation and the set representation of a semi-monolayer covering approximate sets. However, there is an issue with excessive memory consumption in the matrix storage and calculation steps during the operation of M_SMC. To deploy the algorithm on GPU with limited graphics memory and to optimize the matrix storage and calculation steps, a batch processing matrixed semi-monolayer covering approximation set algorithm (BM_SMC) is proposed. The experimental results on 10 datasets show that the BM_SMC algorithm fused with the GPU improves the computational efficiency by 2.16-11.3 times compared with the BM_SMC algorithm using only the CPU. The BM_SMC algorithm can fully utilize the GPU under limited storage-space conditions and effectively improve the computational efficiency of semi-monolayer coverage approximation sets.

Key words: semi-monolayer covering approximation sets, Set-Valued Information Systems(SVIS), matrization, Graphics Processing Unit(GPU) acceleration, batch processing

中图分类号: 

• TP391