Research On The Scalable Parallel Computing And Its Application

Since 1990, to catch up with the requirement of solving large scale problems and complex systems in the scientific researches and practical applications, parallel computing with high performance has developed greatly. However, with the scale expansion of the supercomputer, the scalability research on the parallel algorithms has been paid more and more attention. For such kind of application requirement, in this paper, we do research on the subject of scalable parallel computing existed in the field of traditional parallel computing on planar Delaunay Triangulation, and untraditional parallel computing on two classic NP-Complete problems of exact cover and SAT.For the problem of Delaunay Triangulation, there have been a lot of mature algorithms having different advantages and disadvantages. In our paper, by combine the incremental construction and divide & conquer, and adopting the technique of projection and convex hull, we present two parallel algorithms for DT. Based on PRAM-EREW model, without increasing the work complexity, the first algorithm can decrease to O(n). However, this new algorithm doesnot have scalability. Thus, based on PRAM-CREW model, we also propose another parallel DT algorithm having good scalability. Keeping O(nlogn) work complexity unchanged, the time performance can be enhanced with the increaing number of processors.For NP-Complete problems, traditional parallel computing has no ability to solve the problem of exponential time or processors. As DNA computing affords a number of useful properties such as massive parallelism and a huge memory capacity, thus it is believed to be a potential solution to NP-Complete and other difficult mathematical problems. However, similar to the traditional computers, the problem of "exponential explosion" also exists in DNA computers. Therefore, in our paper, we propose a new DNA computation model with high scalability, and design new algorithms for exact cover problem. The new algorithms can decrease the DNA strands from O(2ⁿ) to O(2^n/2), without increasing the originally polynomial time. In addtion, based on Chang model, we also propose another new DNA algorithm for solving SAT problem. This new algorithm needs no initial solution space, therefore, within polynomial time, it can greatly decrease the needed number and length of DNA strands.