The kNN algorithm is a classical algorithm often used in machine learning and data mining programs. With the increasing amount of data, the execution time of the kNN algorithm increases sharply. In order to effectively utilize GPU and other computing units of modern computers to reduce the computation time of the kNN algorithm, we present a parallel kNN algorithm based on OpenCL, which parallelizes the two segments of bottleneck code: distance calculation and sorting. The algorithm adopts the fine-grained parallelization strategy and the optimized memory model in the phase of distance calculation and uses bitonic sort that can optimize memory model in the phase of sorting. We use Letter, one of UCI datasets, as the test set and E8400 AND GTS450 to run the kNN algorithm for testing. The computing speed of the parallel kNN algorithm accelerated by GPU is 40.79 times faster than that of its CPU version.