Box set subtraction is widely used in SAMR to compute data dependency and nested restriction. Traditional box set subtraction algorithms suffer from high time complexity, which often dominates execution time for large scale SAMR simulations. In this paper, a divide and conquer box set subtraction algorithm with linear time complexity was proposed, and enhanced by domain decomposition parallelization. Experiment results on regular box set and irregular box set of SAMR application verify linear time complexity property. And for large scale problems, our algorithm shows great improvement on computing time.

Communication algorithms need to exchange data between adjacent subdomains. The detection of adjacent subdomains is an import task for communication algorithms, which can be done by solving an intersection problem of boxes. An interval tree algorithm is proposed for intersection problems. Taking advantage of structured mesh applications, it is able to maintain 0 (Nlog N) time complexity. Numerical experiments show that the algorithm is able to achieve high computational efficiency and good scalability. It supports parallel computing of miUion-box scale.

In order to realize the parallelization of LARED-R-1,a serial code for numerical simulation of two-dimensional radiation transport,a directed graph is used to accurately describe the data dependencies.A parallel pipeline flux sweeping algorithm is applied to parallelize the code efficiently.Moreover,a special technique of buffering short messages for less communications is presented to improve the parallel performance.For a typical model discretized by 3 800 cells,100 energy groups and 40 directions,tests on a parallel machine show that the parallel LARED-R-1 achieves parallel efficiency by 80% with 64 processors and by 53% with 128 processors,respectively.