Using LAPACK Can Improve Efficiency of Embedded Software

Do terms like eigenvector, eigenvalue, matrix multiplication, and simultaneous linear equations make your hands sweat, your heart race, and spark a sudden wish for a little Valium®? Or do they make your eyes gleam with anticipation as you ponder the endless possibilities of matrix factorization, condition numbers, and determinants and permanents? Either way, if you are developing embedded software solutions for advanced driver assistance systems (ADAS) you are likely to need the Linear Algebra Package (LAPACK) as you deal with the data structures (matrices and vectors) needed for sensor fusion, object detection, and object tracking – common, but computationally complex tasks in ADAS applications.

LAPACK provides routines for solving systems of simultaneous linear equations, least-squares solutions of linear systems of equations, eigenvalue problems, and singular value problems. LAPACK also provides associated matrix factorizations (also called decompositions), including LU, Cholesky, QR, SVD (singular value decomposition), Schur, and generalized Schur, as well as relevant computations such as reordering of the Schur factorizations and estimating condition numbers. LAPACK can handle both dense and banded matrices, either real or complex, in both single- and double-precision. However, LAPACK is not meant to be used with general sparse matrices.

A Step Back in Time

If you’ve been endowed with the “gift of years” (that is, you’re older than dirt and your embedded software development career dates back to the Cray® supercomputer and slide rules), you can probably skip this section. But for you younger developers, a foray down memory lane may be interesting.

Once upon a time… there was a computer language known as FORTRAN 77. And there were some heavy-hitter mathematicians/computer programmers, such as Cleve Moler (the founder of MATLAB) and Jack Dongarra (the founder of the Innovative Computing Laboratory). They got together with some colleagues in the 1970s and created a software library for solving numerical linear algebra problems, called LINPACK, and a software library for numerical computation of eigenvalues and eigenvectors of matrices, called EISPACK.

Fast forward to the 1990s, when Dongarra collaborated with several others to create the first LAPACK library, essentially a re-do of LINPACK and EISPACK, designed to run more efficiently on modern cache-based architectures. In 2000, MATLAB (which started its life in the late 1970s as an interactive calculator built on top of LINPACK and EISPACK) incorporated LAPACK. In 2008, LAPACK was rewritten in FORTRAN 90. Officially, LAPACK is a software package provided by Univ. of Tennessee; Univ. of California, Berkeley; Univ. of Colorado Denver; and NAG Ltd. Since 2010, work on LAPACK has been supported by the National Science Foundation.

The most recent LAPACK version is 3.7.0, updated December 24, 2016 (apparently as a Christmas present to LAPACK users). LAPACK has also been extended to run on distributed-memory systems in later packages such as ScaLAPACK (Scalable LAPACK) and PLAPACK (Parallel Linear Algebra Package). Related projects include CLAPACK (LAPACK converted into the C programming language), PLASMA (Parallel Linear Algebra for Scalable Multi-core Architectures), and MAGMA (Matrix Algebra on GPU and Multicore Architectures).

What’s So Special about LAPACK?

ADAS applications are often time-sensitive; that is, they can afford very little latency. Use of an optimized LAPACK library can speed execution by much as 10X faster than open-source offerings or in-house implementations.

According to the netlib.org website, LAPACK uses block matrix operations, such as matrix multiplication, that can be optimized for each architecture to account for the memory hierarchy, and so provide a relatively portable way to achieve high efficiency on a wide variety of architectures.

LAPACK performs most computations by calling various Basic Linear Algebra Subprograms (BLAS). LAPACK is specifically designed to exploit the Level 3 BLAS -- a set of specifications for FORTRAN subprograms that perform matrix-matrix operations. Again, quoting netlib.org, because of the coarse granularity of the Level 3 BLAS operations, their use promotes high efficiency on many high-performance computers, particularly if specially coded implementations are provided by the manufacturer (such as that provided by TASKING® for embedded solutions).

Aside from computation speed, porting ADAS applications from one architecture to another can be simplified dramatically you use a standard interface for common linear algebra operations. Consequently, a standard interface-based application can immediately achieve excellent efficiency even on new target platforms without the need for designers to optimize and test the underlying, performance-critical computations in the target-specific library. It is important to note that, in the context of ADAS, that not all libraries are adequately certified for safety-critical applications or suitable for embedded systems.

How to Get LAPACK

LAPACK is a freely-available software package, available from netlib.org via anonymous FTP. You can use it in commercial software packages as long as proper credit is given to the LAPACK authors. If you make modifications to the LAPACK routines, netlib.org asks that you change the name of the routine and comment the changes made to the original.

Are You Developing ADAS Applications for AURIX?

TASKING provides an implementation of the LAPACK interface (including BLAS) as a library for AURIX™ and AURIX 2nd Generation architectures in the form of a highly optimized, highly tested binary library for usage with the TASKING TriCore™ Compiler (included in the TASKING VX-Toolset for TriCore) and other architectures.

If you develop and maintain portable, yet high-performance applications for AURIX architectures and compiled with a TASKING TriCore compiler, you should take a closer look.