Automatic algorithm derivation and exploration in linear algebra for parallelism and locality

Parallelization is one of the major challenges for programmers. But parallelizing existing code is a hard task that can lead to less than optimal solutions since sequential programs can su er from impediments to parallelization resulting from the semantic of the languages or the data structures used rather than the nature of the problem being solved. To avoid such artifacts, programmers can analyze the algorithms to decide which dependencies are "real" and which can be ignored. But even then, conventional algorithms were developed with speci c objectives in mind, such as reducing the total number of operations, which while good to achieve sequential performance, may not be the primary objective when considering parallel machines. We propose to focus on a speci c domain and attack the parallelizing issue at the source, starting from a high level description of the equations without any knowledge of existing algorithms to solve the problem and automatically derive parallel solutions. Hydra accepts an equation written in terms of operations on matrices and automatically produces highly e cient code to solve these equations. Processing of the equation starts by tiling the matrices. This transforms the equation into either a single new equation containing terms involving tiles or into multiple equations some of which can be solved in parallel with each other. Hydra continues transforming the equations using tiling and seeking terms that Hydra knows how to compute or equations it knows how to solve. The end result is that by transforming the equations Hydra can produce multiple solvers with di erent locality behavior and/or di erent parallel execution pro les. Next, Hydra applies empirical search over this space of possible solvers to identify the most e cient version. In this way, Hydra enables the automatic production of e cient solvers requiring very little or no coding at all and delivering performance approximating that of the highly tuned library routines such as Intels MKL. With faster development time for modern architecture, the time available for hand-tuning of high performance libraries diminishes. Intel already started o ering auto-tuned library routines (From Spiral) in their IPP library, to broaden the scope of application of the collection, without having to increase the man hours required to hand-tune everything