The Parallel Optimization And Implementation Of FFT Algorithm And The Heap Sort Algorithm Based On Multi-core Multi-threaded

The traditional serial algorithms cannot take full advantage of multiple processors; the development of multi-core processor technology provides a real important platform for parallel computing. Fast Fourier Transform (FFT) and Heap Sort algorithm FFT algorithm are very common, they are widely applied in signal transmission range and scientific calculation. The combination of Multi-core multi-threading technology and FFT algorithm is a hot spot for the application of FFT algorithm.Based on the multi-threaded technology in the multi-core platform, this paper, we make two parallel processing ways for FFT algorithm. Firstly, according to the characteristics of FFT algorithm, parity of the data set is divided into two parts. Create threads for each section and do run in parallel. Experiments show that when the data reaches 4,194,304,39% efficiency can be improved, and with the increase in the amount of data, efficiency close to nearly 40% and leveled. Secondly, for fully illustrating the problems that need attention in optimization project, this paper divided the butterfly transformation its internal cycle into two parts, each part creates a thread and run in parallel way. Experiments show that this method is not feasible with the data set increasing. So we need avoided create threads inside the loop.This paper implements the heap sort and merge sort parallel optimization algorithm, and make an analysis and research for single-threaded (serial), two threads, four threads running result in parallel sorting algorithm on the dual-core, triple-core processor platform. The results show that in the heap sorting algorithm, parallel way comparing with the serial heap can improve the efficiency of 42% when the amount of data is to 25 million, and with the increase in the amount of data, efficiency close to nearly 50% and leveled; In the merge sort algorithm, the threads need to create temporary stack inside, which makes the operating efficiency reduction after parallel sorting. This illustrates that optimization program in parallel way should be avoided in the interim to create multiple threads within the stack.