Parallelization Of MSP Problem

NP Problem is a classical kind of computer science,All NP problems can be resolved to NP-Complete problem,the NPC problem is of considerable complexity.To find an polynomial time solution for NPC problem is becoming a pursuit of lots of scientist.Recently,a new NPC problem,MSP problem,was put forward,and a polynomial algorithm for solving MSP problem named after ZH algorithm was found,however,the algorithm is so complex that it runs slowly.In this paper,we use the parallel programming technique to accelerate ZH algorithm.In this paper,we came up a general way of paralleling polynomial time algorithm,firstly,we must confirm the code to paralleling,secondly,to inspect the algorithm to make sure the r/w conflicts are well coped with,finally,we should do some setting and optimizing work.In this way,we designed the parallel scheme for ZH algorithm,and transplant it to both PC platform and YH supercomputer.In further work,we optimized the paralleled ZH algorithm from several angle,such as workload balancing and message passing.Considering the hardware structure,we adopted a special parallel structure which do paralleling through multi-thread inside nodes,while message passing between nodes.We did the experiments and theory proof to confirm the correctness of our work,also,the experiments shows that our paralleling on ZH algorithm is efficient.