An N-sequential execution method for parallel programs and its application to MGTP

An efficient parallel execution method is presented for parallel programs which create many tasks at runtime on parallel machines with N number of processing elements (PEs) available at any time. In this method, the number of tasks activated at the same time is limited to at most N, and the exceeding number of created tasks are suspended until they are allowed to be activated, thus being processed sequentially. A PE can request a task to another PE only when the set of executable tasks of the requesting PE is empty. A PE can transfer a task to another PE only when the latter requests it and the set of executable tasks of the requested PE is not empty. This effectively suppresses the communication overhead induced by the task transfers between PEs. Also, it allows tasks which should be better executed sequentially to stay on a single PE, while keeping the execution rate of tasks at every PE very high. We implemented the method for the parallel theorem proving system MGTP written in the concurrent programming language KL1 running on the parallel inference machine PIM/m (128PE) as well as the shared-memory parallel machine Cray SuperServer6400 (20PE). The results show remarkable reduction of communication overhead achieving significant speedup.