Research On Scheduling Method For Parallel Computing Scan

Deterministic particle transport problems can be converted to complex integraldifferential equations which contains mass physical parameters. This kind of equationscan be solved by digital imitation methods, but the huge calculation is one of the biggestproblems which are avoidless, so the scalable parallel algorithm for solving transportequations is desirable. Paralllel computing scan method is used to solve the particletransport equations on parallel computers by the discrete ordinate (Sn) method on theunstructured grids. Parallel computing scan problem belongs to the precedenceconstrained scheduling problem which is NP-complete, and it is a hard work in the fieldof parallel computing.First, Based on the grid decomposing across processors, a new Sn parallelalgorithm for particle transport on the unstructured grids is presented. The algorithmimplements parallel computation for different angle directions and energy groups,according to the orders of the computing queue. During the parallel computation, it is noneed to compute the priorities and arrange the priority queues.Then，synthesizing the data dependence of all directions and all grids, basing onB-LEVEL priority, a priority ordering algorithm is designed. In order to overlap thecomputation and communication, the algorithm gives priority to computing the gridswhich needn’t receive the upstream grids’ messages.Local methods have been designed by modifying and localizing the B-LEVEL、BFDS、DFDS and DFHDS sheduling methods. Based on the task priority ordering, alocal scheduling method is designed, which using the dependent informantion of tasksamong the neighboring processors. The local scheduling method uses the improvedlocal B-LEVEL method. The priority of each task is updated by the task is upstream ordownstream. So the local sheduling method has more parallel performace with bettorcomputing sequence.Using Sn parallel algorithm and priority ordering algorithm, a two dimensiontransport equation was solved on large parallel computer system, results show thatalgorithms in this paper have well scalability. Relative to64processors, parallelefficiency is67%on1024processors.In a word, the local sheduling method in this paper can be used to solve the largescale problem. Combining with the Sn parallel algorithm, the real problem of parallelcomputing scan can be solved fastly in the effective way.