The DiamondCandy algorithm for maximum performance vectorized cross-stencil computation

На основе поиска оптимальной пространственно-временной декомпозиции 3D1T пространства операций построен новый алгоритм DiamondCandyV для эффективной реализации конечно-разностных вычислений с использованием аппаратной векторизации. Базовый элемент разбиения пространства операций DiamondCandy получен пересечением областей зависимостей и влияния (конусоидов) для схем с шаблоном типа крест. Благодаря этому алгоритм характеризуется высокой вычислительной интенсивностью и локализует обрабатываемые данные на верхних уровнях иерархии памяти современных компьютеров. Ключевой особенностью алгоритма является легко реализуется в программном коде поддержка двух основных средств повышения производительности современных процессоров, а именно аппаратной векторизации (с использованием SIMD расширения AVX) и вычислительных потоков с общей памятью (many-core CPU). Обсуждаются детали программной реализации поддержки параллельности различных уровней на примере численного решения волнового уравнения. Результаты тестирования реализации алгоритма показывают повышение производительности на порядок по сравнению с традиционными алгоритмами с пошаговой синхронизацией. Также, в отличие от традиционного подхода, с увеличением размера обрабатываемых данных производительность не деградирует.