Ускорение вычислений по блочным алгоритмам разностного решения уравнения теплопроводности

Abstract

Учет особенностей архитектуры конкретной вычислительной системы при разработке нового алгоритма известного численного метода давно считается необходимым при синтезе параллельных и векторных алгоритмов. В настоящей работе предлагается принимать во внимание архитектурные особенности процессора еще на этапе конструирования самого численного метода, как это когда-то предлагалось академиком Гурием Ивановичем Марчуком, однако так и не закрепилось в широкой вычислительной практике. Данная идея иллюстрируется на примере синтеза новой разностной схемы для уравнения теплопроводности, традиционно являющимся объектом для испытания новшеств в теории разностных схем. В качестве упомянутой архитектурной особенности выбрана иерархическая структура памяти ЭВМ, обуславливающая появление коммуникационных издержек даже при использовании одного аппаратного вычислительного потока для организации расчетов. Учет данной особенности в вычислительной линейной алгебре связывают с блочными алгоритмами, в теории разностных схем – с приемом программирования «tiling». Однако для двухслойных разностных схем блочных алгоритмов решения сеточных уравнений до предлагаемой работы известно не было в силу невозможности организации блочных вычислений по существующим схемам. Для восполнения этого пробела авторы предлагают новый прием конструирования двухслойных разностных схем и смешанную схему со сдвигом как пример применения этого приема. В ходе экспериментов демонстрируется пятикратное ускорение расчетов по такой схеме относительно традиционной явной при той же вычислительной сложности. In this paper, proposing to take into account the architectural features of the processor at the stage of constructing the numerical method itself. This idea is illustrating by the example of the synthesis of a new difference scheme for the heat conduction equation, which has traditionally been the object of testing innovations in the theory of difference schemes. Architectural feature hierarchical structure of computer memory chosen causes the appearance of communication costs even when using a single hardware computational flow for organizing calculations. Accounting for this feature in computational linear algebra is associated with block algorithms. Accounting for this feature in the theory of difference schemes is associated with the technique of programming "tiling". However, for two-layer difference schemes of block algorithms for solving grid equations, prior to the proposed work, it was not known due to the impossibility of organizing block calculations using existing schemes. The authors propose a new method of constructing two-layer difference schemes and a mixed scheme with a shift as an example of the application of this method. In the course of the experiments, a fivefold acceleration of calculations according to this scheme is demonstrated relative to the traditional explicit, with the same computational complexity.