Non-Recursive Beam Search on GPU for Formal Concept Analysis
William B. Langdon, Shin Yoo, Mark Harman · 2011
We document a parallel non-recursive beam search GPGPU FCA algorithm written in nVidia CUDA C. We run it on benchmarks and to analyse software module dependency. Despite kernel_sort removing repeated calculations, 32 bit packing and optimising GPU data structures and kernels, we do not yet see major speed ups. Instead GeForce 295 GTX and Tesla C2050 report 141072 concepts (maximal rectangles, clusters) in about one second. Future improvements in graphics hardware may make GPU implementations of Galois lattices competitive.