Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Finite difference stencil parallelizing method based on iteration space sticks

A block and iterative technology, applied in the field of parallel finite difference templates, can solve problems such as hindering the parallelization of loops, and achieve the effect of improving data locality, reducing cache miss rate, and improving data locality

Inactive Publication Date: 2011-09-28
HANGZHOU DIANZI UNIV
View PDF0 Cites 5 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

Parallelization of loops is severely hindered by the block dependencies introduced by iteration space partitioning

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Finite difference stencil parallelizing method based on iteration space sticks
  • Finite difference stencil parallelizing method based on iteration space sticks
  • Finite difference stencil parallelizing method based on iteration space sticks

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0033] Below in conjunction with accompanying drawing and embodiment, specific embodiment of the present invention is described in further detail:

[0034] The traditional iterative method executes the sequence process as follows:

[0035] In one iteration, according to the order of the grid points, iteratively update all the grid points in turn:

[0036] for ( t=1; t<=T; t++ )

[0037] for ( i=1; i

[0038] for ( j=1; j

[0039] A[t+1][i][j]=(A[t+1][i-1][j]+A[t][i+1][j]+A[t][i][ j] + A[t+1][i][j-1] + A[t][i][j+1]) / 5

[0040] where T represents the number of iterations and N×N represents the size of the matrix.

[0041] In the above method, there are four ways of data reuse:

[0042] In the row-first storage format, A[i][j], A[i][j+1]...

[0043] In the j cycle, A[i][j] is reused in the process of updating A[i][j-1], A[i][j] and A[i][j+1].

[0044] In the i cycle, A[i][j] is reused in the process of updating A[i-1][j], A[i][j] and A[i+1][j].

[0...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention relates to a finite difference stencil parallelizing method based on iteration space sticks. In the traditional parallel iterative method, synchronous operation for maintaining the data dependence relation is needed both in iteration and among the iterations. The method provided by the invention comprises the following steps of: dividing an iteration space into grid sticks in a time-axis direction to realize multiple recursion-type iteration-step updates on the same grid block, thereby improving the data locality in the sticks at the same time of not changing the property of a serial stencil iterative method; and then reordering the grid sticks to realize the parallelization of staggered sticks in the finite difference stencil method. Compared with the traditional domain decomposition method and a red-black ordering parallel method, the method provided by the invention has better data locality, parallelization efficiency and extensibility.

Description

technical field [0001] The invention belongs to the field of engineering calculation and relates to a parallel finite difference template method based on iterative space strips. Background technique [0002] With the increasingly complex problems to be solved in scientific computing and the rapid development of parallel computers, parallel computing has become an indispensable means to solve large-scale parallel scientific computing problems. In the fields of scientific and engineering computing such as computational mathematics and computational physics, many problems ultimately boil down to solving sparse linear algebraic equations. Therefore, efficiently solving large-scale sparse linear algebraic equations on parallel computers has become an important task in the field of scientific computing. [0003] Due to the limitations of rounding errors, computer memory and computational complexity, it is almost impossible to directly solve this type of equation system for large-...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
IPC IPC(8): G06F17/00
Inventor 张纪林徐向华万健蒋从锋张伟任永坚
Owner HANGZHOU DIANZI UNIV
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com