Analysis And Implementation Of Fast Parallel Algorithms For Discrete Gabor Transform And Expansion

Gabor expansion and transform are commonly used tools in signal processing. However, their computational efficiency problems need to be study and solved. The computational efficiency of past researches on fast algorithm are limited to their serial structure. In addition, the parallel algorithms for computing the Gabor expansion and signal reconstruction proposed are limited in theory, have not analyzed and implemented in the parallel environment. Thus, problems appeared in implementation require to be tackled. In this dissertation, the two of fast parallel algorithms for Gabor transform and inverse are analyzed and implemented. The optimized issues are presented here to improve their implementation efficiency.The existing fast parallel algorithms are block time recursive algorithm based on parallel lattice structure and multirate filtering based fast parallel algorithm. The former algorithm will generate a lot of communication and synchronization overhead in implementation due to its recursive structure and inter-process communication. This has a great influence on the implementation efficiency. The improved implementation method is presented through expanding the recursive parts to iterative form. This operation makes the inter-process communication and synchronization become serial calculation inner process. The expanding make the formula used for Gabor transform or its inverse completely independent each other. Thus, the efficiency will greatly improved without communication and synchronization.Multirate filtering based fast parallel algorithm has more parallelism and lower computation complexity compared to the algorithm former. But there still has some overhead time spend in communication operation when implemented in cluster environment. In this study, the implementation method is optimized. In the implementation of pure MPI model, the method of dividing the communication into sub-communication group is presented. This makes the global MPI gathering communication become smaller locally communication process. The implementation reduce the gathering communication time overhead. The size of sub-communication group is selected based on the test result on particular computer hardware. In implementation on multicore cluster architecture, the MPI+OpenMP model is used to implement the algorithm to optimize the communication. The communication is divided into two levels of heterogeneous structure. In the first level, using the shared memory employed OpenMP model to communication inter-node. In the second level, using the MPI model to deal with intra-node communication. This improved the communication efficiency, and more generally to the popularization and application of performance of different hardware architecture.The implementation methods proposed here can be generalized to real valued discrete Gabor transform which can be DCT-kernel, DST-kernel and DHT-kernel. These could also be generalized to multi-window Gabor transform and their inverse due to the theoretical properties.These methods presented here are implemented and analyzed on a cluster computer with hybrid architecture. The research results illustrate that the efficiency of these algorithm are improved in implementation.