In this paper we describe a new parallel program package for phylogenetic analysis of DNA sequences. This program is based on a more advanced algorithm, named Advanced Stepwise Addition (ASA), for phylogenetic analysis using maximum likelihood approaches. There are two main advantages of our parallel program package over many existing ones using the simple master/workers technique. Firstly the size of the tree search space can be freely chosen and so we are able to fill up a large-scale supercomputer (as long as it is computationally feasible) to alleviate the problems of thoroughness and phylogenetic uncertainty. Secondly we adopt SPMD programming technique in our implementation. Our approach can effectively reduce the overall communication costs and alleviate the problem of communication bottleneck caused by using the simple master/workers technique. Therefore, it is more suitable for execution on large-scale high-performance parallel computers.