Designing,Analysis And Implementation Of Distributed Parallel Algorithms

It is well known that the contradiction between the finiteness of single computer's technology development and the infiniteness of requirement for science computing determines that multi-computers' parallel will be the development of computer. This also leads to that parallel computing will be the main computing method in the future, and the development of parallel processing technology will be the main power to impel the constructing of national defense and the development of national science and technology. Accordingly, the increasingly demanding for science computing is also the main power to impel the flourish development of parallel processing technology in those twenty years. Though the parallel processing technology got abundant development in those years, but there are also some unsolved problems. All of those lead to the foundation of the ninth five years?project-barallel algorithm and its application in electronic systems, which deeply researched involved parallel algorithms based on distributed systems, such as mesh-connected multi-processors, hypercube-eonnected multi-processQrs, cluster and so on. This paper takes some important items-wavelet transform and QR orthonormal transform from this project as its main research object, at the sanie time, other associating algorithms of distributed systems are also be discussed and several valuable results are obtained. Wavelet transform has important applications in some fields, such as geological exploring, data compressing, edge detecting. Since the huge data iii need to be processed in those fields mostly, it is necessary to research the parallel realizing of wavelet transform. During the researching process, some other problems which are associated with wavelet application are also been researched, such as all-to-all personalized exchange, processor scheduling, parallel algorithm of LBG and so on. The detailed contents are described as follows. After analyzing the mathematical model of 2D WT, this paper proposes a parallel algorithm of it by equally blocking based on mesh-connected multi-processors, and its communication cost is also been reduced effectively by translating the filter. The algorithm has the characteristic of little communication and load balancing. It also fits to realize multi-level wavelet transform, according with the demanding for multiresolution in actual application. Another realizing method for 2D WT is transposing parallel. One main problem of it is the all-to-all personalized exchange, that is all the processors in system will transfer different message which is equal in length to all other processors in the same system. Its performance will badly affect parallel systems?efficiency, and may bring the systems? communication bottleneck. For all-to-all personalized exchange of short messages on mesh, this paper proposes a new best algorithm, which is better than the proposed algorithms to solve the above communicatjon bottleneck. Due to mesh's easy scalabiity, it becomes the popular architecture for modem parallel machine. So this paper also discusses mesh architecture iv during the process of researching the parallel algorithm on mesh. Based on its user sharing, This paper proposes a n...