A case study in mechanically deriving dense linear algebra code. (November 2013)

• Record Type: Journal Article
• Authors: Marker, Bryan; Batory, Don; van de Geijn, Robert
• Is Part Of: International journal of high performance computing applications. Volume 27:Number 4(2013)
• Page Start: 440
• Page End: 453
• Publication Date: 2013-11
• Subjects: program generation -- distributed memory computing -- high-performance numerical algorithms -- dense linear algebra -- autotuning; High performance computing -- Periodicals; Supercomputers -- Periodicals; 004.1105
• DOI: 10.1177/1094342013492178
• Languages: English
• ISSNs: 1094-3420

Abstract

Design by Transformation (DxT) is a top-down approach to mechanically derive high-performance algorithms for dense linear algebra. We use DxT to derive the implementation of a representative matrix operation, two- sided Trmm. We start with a knowledge base of transformations that were encoded for a simpler set of operations, the level-3 BLAS, and add only a few transformations to accommodate the more complex two- sided Trmm. These additions explode the search space of our prototype system, DxTer, requiring the novel techniques defined in this paper to eliminate large segments of the search space that contain suboptimal algorithms. Performance results for the mechanically optimized implementations on 8192 cores of a BlueGene/P architecture are given.