Ctrl-P to Print

Discovery and Exploitation of Structure in Algorithms (DESA)

Overview

The Discovery and Exploitation of Structure in Algorithms (DESA) program seeks a dramatic reduction of expert human programmer involvement in porting critical high-performance algorithmic capabilities into new and upgraded computing platforms and into new classes of processing hardware. Design tools are sought to enable programmers without platform-specific expert ise (e.g., application experts) to produce algorithm implementations that are optimized to a target platform. As new platforms emerge requiring substantially different algorithm implementations in order to make best use of their architectural characteristics, DESA tools will enable these implementations to be produced by application practitioners without investment in platform specific expertise—thereby enabling rapid and inexpensive porting of legacy software to new host machines. Similarly, DESA tools are sought to allow application practitioners to optimally partition hardware-firmware in algorithm implementations on new hybrid platforms and to produce application-specific integrated circuit (ASIC) designs exploiting new technological capabilities.

DESA is prototyping major advances in software engineering and processor (ASIC) design by demonstrating mechanisms for producing libraries of algorithmic primitives that are both optimized and portable. In the first phase of the program, researchers demonstrated a tool that enabled power efficient implementations of the Fast Fourier Transform that were more efficient then expert-developed implementations and required 1/80th the development time. Performers developed an architecture and implementations of the Fast Multipole Method, which outperformed previous Gordon Bell prize winning machines. In the program’s second phase, high-level algorithm specification tools will be produced to allow application domain experts (e.g., engineers in signal processing or fluid dynamics) to specify algorithmic library modules.

Successful realization of the DESA vision will lower DoD system costs and decrease design cycle time currently entailed by extensive hand-tuning of software module, firmware, and ASIC designs for the most computationally intensive mathematical operations in DoD systems. The primary areas of potential national security impact for the tools to be produced by this program are in digital signal processing applications (e.g., communication systems, radar, and other sensing systems) and computational physics (e.g., computational fluid dynamics for aerodynamics and combustion modeling, and computation electromagnetics for low-observable vehicle design).