We have proposed an automatic timing verification method based on the time sequential machines, which are extended to describe the times that each action takes. In this work, we discuss how to perform this verification method on a parallel machine efficiently. Since the original verification algorithm is based on the state space traversal, we consider the parallel method in which each successor state from one state is performed in a different processor. In the method, traversed states should be kept in processors for the equivalence check of states. It may affect the performance whether traversed states are kept locally or globally. We implement these two ways, and compare their performance on Fujitsu parallel computer AP1000.