Field G. Van Zee libflame: The Complete Reference www.lulu.com (Frequently updated here) 2009 Paperback: $11.58 or download for free

Robert A. van de Geijn and Enrique S. Quintana-Ortí. The Science of Programming Matrix Computations www.lulu.com 2008 Paperback: $14.21 or download for free

Science: Knowledge that has been reduced to a system.

Objective

The objective of the FLAME project is to transform the development of dense linear algebra libraries from an art reserved for experts to a science that can be understood by novice and expert alike. Rather than being only a library, the project encompasses a new notation for expressing algorithms, a methodology for systematic derivation of algorithms, Application Program Interfaces (APIs) for representing the algorithms in code, and tools for mechanical derivation, implementation and analysis of algorithms and implementations.

Online Presentations

A number of on-line presentations provide a more interactive overview of the FLAME project.

• Details

Notation

The key insight that enables the FLAME methodology is a new, more stylized notation for expressing loop-based linear algebra algorithms. This notation closely resembles how algorithms are naturally illustrated with pictures.

Figure 1: Blocked LU Factorization without pivoting (Variant 1).

Related publications

• Paolo Bientinesi, Enrique S. Quintana-Ortí, and Robert van de Geijn. "Representing Linear Algebra Algorithms in Code: The FLAME APIs," TOMS, 31(1):27-59, March 2005.
• Robert A. van de Geijn and Enrique S. Quintana-Ortí, The Science of Programming Matrix Computations.

Derivation

The FLAME project promotes the systematic derivation of loop-based algorithms hand-in-hand with the proof of their correctness. Key is the ability to identify the loop-invariant: the state to be maintained before and after each loop iteration, which then prescribes the loop-guard, the initialization before the loop, how to progress through the operand(s), and the updates. To derive the shown algorithm for LU factorization one fills in the below "worksheet". In the grey-shaded areas predicates appear that ensure the correctness of the algorithm.

Figure 2: Derivation of algorithm in Figure 1.

Related publications

• John A. Gunnels, Fred G. Gustavson, Greg M. Henry, and Robert A. van de Geijn, "FLAME: Formal Linear Algebra Methods Environment," TOMS, 27(4):422-455, December 2001.
• Paolo Bientinesi, John A. Gunnels, Margaret E. Myers, Enrique S. Quintana-Ortí, and Robert van de Geijn, "The Science of Deriving Dense Linear Algebra Algorithms," TOMS, 31(1):1-26, March 2005.
• Robert A. van de Geijn and Enrique S. Quintana-Ortí, The Science of Programming Matrix Computations.

APIs

A number of APIs have been defined fo representing the algorithms in different languages. These include

function [ A_out ] = LU_blk_var1( A, nb_alg )   [ ATL, ATR, ...     ABL, ABR ] = FLA_Part_2x2( A, ...                                0, 0, 'FLA_TL');   while ( size( ATL, 1 ) < size( A, 1 ) )     b = min( size( ABR, 1 ), nb_alg );     [ A00, A01, A02, ...       A10, A11, A12, ...       A20, A21, A22 ] = ...       FLA_Repart_2x2_to_3x3( ATL, ATR, ...                              ABL, ABR, b, b, 'FLA_BR');     %----------------------------------------------%     A01 = trilu( A00 ) \ A01;     A10 = A10 / triu( A00 );     A11 = A11 - A10 * A01;     A11 = LU_unb_var1( A11 );     %----------------------------------------------%     [ ATL, ATR, ...       ABL, ABR ] = ...       FLA_Cont_with_3x3_to_2x2( A00, A01, A02, ...                                 A10, A11, A12, ...                                 A20, A21, A22, ...                                 'FLA_TL');   end   A_out = [ ATL, ATR             ABL, ABR ];   return

Figure 3: FLAME@lab code for algorithm in Figure 1.

Related publications

• Paolo Bientinesi, Enrique S. Quintana-Ortí, and Robert van de Geijn. "Representing Linear Algebra Algorithms in Code: The FLAME APIs," TOMS, 31(1):27-59, March 2005.
• Tze Meng Low, Kent Milfeld, Robert van de Geijn, and Field Van Zee. "Parallelizing FLAME Code with OpenMP Task Queues," FLAME Working Note #15. The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-2004-50.
• John A. Gunnels, Daniel S. Katz, Enrique S. Quintana-Ortí, and Robert van de Geijn. "Fault-Tolerant High-Performance Matrix-Matrix Multiplication: Theory and Practice," The International Conference for Dependable Systems and Networks (DSN-2001), pp. 47-56, July 2-4, 2001.
• Robert A. van de Geijn and Enrique S. Quintana-Ortí, The Science of Programming Matrix Computations.

Tools

A number of tools have been created to help the development of FLAME algorithms.

Spark

Spark is a tool for mechanical creation of code skeletons. By filling out a menu, an outline for FLAME@lab code, FLAME/C code, FLaTeX algorithm, or FLaTeX worksheet are generated. This greatly simplifies the generation of the rigid format advocated by the FLAME methodology.

Try Spark

• Visit the Spark webpage.
• Take an online tutorial.

AutoFLAME

AutoFLAME represents a glimpse at the ultimate goal of the FLAME project: the mechanical (automatic) generation of linear algebra libraries. For now, given a mathematical description of the linear algebra operation, the system can derive correct algorithms and code, with moderate human intervention.

Related publications

• Paolo Bientinesi, Sergey Kolos, and Robert A. van de Geijn, "Automatic Derivation of Linear Algebra Algorithms with Application to Control Theory," PARA 2004, LNCS 3732, pp. 385--394, 2005.

Performance

• Performance comparison: libflame v. PLASMA

Team

The FLAME Team includes participants from UT-Austin' Department of Computer Sciences, UT-Austin's Center for Space Research, UT-Austin's Texas Advanced Computing Center, Universidad Jaume I (Spain), Aachen University (Germany), and industry (IBM, Intel, National Instruments, NEC Solutions (America), Inc.).

Active participants

• Details

Sponsors

The FLAME project is sponsored by the National Science Foundation, National Instruments, NEC Solutions (America), Inc., and Hewlett-Packard.

• Details

Publications

The FLAME project has generated a large number of journal and conference publications, in addition to a working note series.

• Details

LinearAlgebraWiki

The LinearAlgebraWiki on linear algebra theory, algorithms, and implementation is being maintained by the FLAME project.

Downloads

Libraries and materials can be downloaded for those interested in trying the approach and resulting libraries.

• libFLAME
• Other FLAME related tools and libraries

Reference Materials

We maintain a number of documents and web pages.

• Details

Information for Developers

The FLAME libraries are maintained in a repository managed with subversion.

• Details

Contact us

Please e-mail us at flame@cs.utexas.edu or rvdg@cs.utexas.edu.

Last Updated on 12 August 2008 by field.