Code tiling for improving the cache performance of PDE solvers

• For SOR-like PDE solvers, loop tiling either helps little in improving data locality or hurts their performance. We present a novel compiler technique called code tiling for generating fast tiled codes for these solvers on uniprocessors with a memory hierarchy. Code tiling combines loop tiling with a new array layout transformation called data tiling in such a way that a significant amount of cache misses that would otherwise be present in tiled codes are eliminated. Compared to nine existing loop tiling algorithms, our technique delivers impressive performance speedups (faster by factors of 1.55-2.62) and smooth performance curves across a range of problem sizes on representative machine architectures. The synergy of loop tiling and data tiling allows us to find a problem-size-independent tile size that minimises a cache miss objective function independently of the problem size parameters. This "one-size-fits-all" scheme makes our approach attractive for designing fast SOR solvers without having to generate a multitude of versions specialised for different problem sizes.

Subject headings

TEKNIK OCH TEKNOLOGIER  -- Elektroteknik och elektronik (hsv//swe)

ENGINEERING AND TECHNOLOGY  -- Electrical Engineering, Electronic Engineering, Information Engineering (hsv//eng)

Keyword

Australia

Computer science

Data engineering

Jacobian matrices

Multidimensional systems

Partial differential equations

Processor scheduling

Tiles

Buffer storage

Cache memory

Memory architecture

Metadata

Tile

Compiler techniques

Machine architectures

Objective functions

Performance curve

Codes (symbols)

Publication and Content Type

ref (subject category)

kon (subject category)