Fuzz testing is a widely used technique for software vulnerability detection, but it is still limited in finding bugs nested in the deep program states. Parallel testing is an augmented method aiming to make the best of the computing resource to expose more deep program bugs. However, current parallel testing methods cannot deal well with task slicing so that the parallel nodes show serious duplication with each other, thus decreasing the efficiency in total. For instance, the original parallel mode of the well-known fuzzer American fuzzy lop (AFL) does not split the task and just synchronizes the interesting seeds without any internal execution information. In this paper, we put forward a novel program state sensitive parallel testing method, which: 1) splits the task into low correlated subtasks according to the program states and 2) adjusts the mutation engine to confine one instance's testing among its subtask-related code region as more as possible. Our method is an objective to reduce the testing collision between parallel instances and therefore improve the performance. We developed a new fuzzer called PAFL and implemented some experiments to investigate that if our parallel testing framework is positive when deploying multiple instances and if it shows a better path discovery compared with two state-of-the-art fuzzers, AFL and AFLFast. In the experiments, we employed PAFL with 1/2/4/8/16 to observe their path discovery and conclude that our new parallel framework is positive when using more multiple instances. We also compared PAFL with AFL and AFLFast by employing eight parallel instances for each fuzzer, and the results prove that our tool has the best path discovery among the three fuzzers. Compared with the original parallel AFL, PAFL can achieve averaged performance gains of 3.98, 3.04, 4.18, and 1.45 on the c++filt, objdump, readelf, and tcpdump, respectively. Besides, we took PAFL on binutils and libtiff, and finally, we found ten new bugs.