| Abstract: | The study of sparse grids has been done in a lot of works, but none of them pay special attention on the concept of “layer”, not to mention the further research on this new concept. This work presents the layer concept at first, and then based on it a new parallel sparse grid construction algorithm is proposed, which fills the niche that few works design such kind of algorithm on shared memory architecture. With the superiorities of the layer concept, the sparse grids can be constructed in a “layer by layer” manner on a much easier structure which is the simplified tree. Different from the classical tree structures used in the former sparse grid construction algorithm, the simplified tree reduces the number of sparse grid points further and at the same time avoids many unnecessary usages of pointers. Moreover, the correctness of the algorithm is guaranteed by the two correctness criterions, and its main advantages include that it can achieve load balance among the threads easily and that it can be applied in the function domains of any kinds of configurations, which is demonstrated by theory. After that, the algorithm is tested on flash calculations which are an important application from reservoir simulations. According to the characteristics of the issue, a modified version of the algorithm is given. By comparing the tested results with those of the former algorithm, it is found that a great quantity of construction time is saved by this algorithm. |
