Alexander OKHOTIN
U Turku

Implementing Boolean matrix multiplication on a GPU

General-purpose computation on Graphics Processing Units (GPU) is now
becoming a popular topic. A GPU is a mass-produced supercomputer at a
price of a consumer toy (which is, after all, its primary purpose),
and its raw computational power is currently at least 10-20 times
greater than that of a CPU. However, successfully utilizing this power
requires specialized programming techniques. This talk is a report on
the author's recent experience of implementing Boolean matrix
multiplication on a GPU, and on the challenges encountered while
optimizing a simple algorithm for this hardware. Boolean matrix
multiplication often occurs in theoretical computer science as a
subproblem of various algorithms, and its efficient implementation will
help accelerating those algorithms. Furthermore, the general experience
of implementing it on GPU should equally apply to different kinds of
scientific computations. The talk will include a general introduction
to GPU programming.

This is a joint work with Christian Reitwiessner from University of
Wuerzburg, Germany.