Accelerated Parallel Generation of Binomial Coefficients using GPU
Mohsin AltafWani, S. M. K. Quadri · International Journal of Computer Applications · 2013
GPUs (Graphics processing units) can be used for general purpose parallel computation.Developers can develop parallel programs running on GPUs using different computing architectures like CUDA or OpenCL.The Binomial Coefficient Generation is used to generate a table of binomial coefficients each entry in row n and column k of this table contains number of combinations of n objects taken k at a time.It is known that this problem can be solved by dynamic programming technique using O(nk)-time complexity algorithm where the table to be generated has n rows and k columns.The main contribution of this paper is to present a parallel implementation of this O(nk)-time algorithm on a GPU and to analyze the speed up possible when compared to a CPU based implementation.