Study On CUDA—based Parallel Algorithm For Constructing Concept Lattices

Formal concept analysis is an effective tool used in knowledge representation andknowledge discovery, has been widely used in many field, such as data mining,machine learning, information retrieval and so on. In the application of FCA, conceptlattice must be build firstly, therefore, the efficiency of the algorithm to build conceptlattice is very important. By use of GPU CUDA parallel computing architecture cangreatly improve performance, it has been increasingly used in general-purpose parallelcomputing. it offers a new thinking to solve construction problem.In this paper, the hardware architecture and software system of CUDA are deeplyanalyzed, optimization strategy of CUDA program are also described. FCBOalgorithm’s data structures and logical structure are analyzed, it was modified so that itcan run on the CUDA platform. Finally the transformed algorithm was ported toCUDA platform, experiment results show that the transformed algorithm is reliable andfeasible..The main contribution and innovation of this paper are as follows:1. Lattice construction algorithm optimization strategy is proposed by analyzingthe CUDA multi-threaded programming model combined with data structures andalgorithms characterized of Lattice construction algorithm. Analysis the characteristicsof FCBO, and transform it into an algorithm which can running in CUDA platformbased on optimization strategy;2. The transformed algorithm is implemented on CUDA platform and comparedwith the original algorithm.