A Simple Methodology for Computing Families of Algorithms

2018/08/20 by Parikh, Devangi N., Myers, Margaret E., Vuduc, Richard +1
#FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Mathematical Software (cs.MS) #Programming Languages (cs.PL)

paper · doi:10.48550/arxiv.1808.07832

Abstract

Discovering "good" algorithms for an operation is often considered an art best left to experts. What if there is a simple methodology, an algorithm, for systematically deriving a family of algorithms as well as their cost analyses, so that the best algorithm can be chosen? We discuss such an approach for deriving loop-based algorithms. The example used to illustrate this methodology, evaluation of a polynomial, is itself simple yet the best algorithm that results is surprising to a non-expert: Horner's rule. We finish by discussing recent advances that make this approach highly practical for the domain of high-performance linear algebra software libraries.

Related

• Automatic Generation of Loop-Invariants for Matrix Operations
• Application-tailored Linear Algebra Algorithms: A search-based Approach
• Deriving Correct High-Performance Algorithms
• A Domain-Specific Compiler for Linear Algebra Operations
• Hierarchical Performance Modeling for Ranking Dense Linear Algebra Algorithms