An approach is defined that describes a method of iterating over massively large arrays containing sparse data using an approach that is implementation independent of how the contents of the sparse arrays are laid out in memory. What is unique and important here is the decoupling of the iteration over the sparse set of array elements from how they are internally represented in memory. This enables this approach to be backward compatible with existing schemes for representing sparse arrays as well as new approaches. What is novel here is a new approach for efficiently iterating over sparse arrays that is independent of the underlying memory layout representation of the array. A functional interface is defined for implementing sparse arrays in any modern programming language with a particular focus for the Chapel programming language. Examples are provided that show the translation of a loop that computes a matrix vector product into this representation for both the distributed and not-distributed cases. This work is directly applicable to NASA and its High Productivity Computing Systems (HPCS) program that JPL and our current program are engaged in. The goal of this program is to create powerful, scalable, and economically viable high-powered computer systems suitable for use in national security and industry by 2010. This is important to NASA for its computationally intensive requirements for analyzing and understanding the volumes of science data from our returned missions.
This work was done by Mark James of Caltech for NASA's Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free online at www.techbriefs.com/tsp under the Information Sciences category.
The software used in this innovation is available for commercial licensing. Please contact Karina Edmonds of the California Institute of Technology at (626) 395-2322. Refer to NPO-42502.
This Brief includes a Technical Support Package (TSP).
Representation-Independent Iteration of Sparse
(reference NPO-42502) is currently available for download from the TSP library.
Don't have an account?
Overview
The document titled "A Representation Independent Approach for Efficiently Iterating Over Sparse Arrays" (NPO-42502) presents a novel method for iterating over large arrays that contain sparse data, focusing on an implementation-independent approach. This technique decouples the iteration process from the internal memory representation of the sparse arrays, allowing for greater flexibility and compatibility with both existing and future sparse array representations.
The primary innovation lies in the development of a functional interface that can be utilized in modern programming languages, with a particular emphasis on the Chapel programming language. Chapel is being developed under the DARPA High Productivity Computing Systems (HPCS) program, which aims to create powerful, scalable, and economically viable high-performance computing systems suitable for national security and industrial applications. This is particularly relevant for NASA, which requires efficient computational methods to analyze vast amounts of scientific data from its missions.
The document provides examples demonstrating how to translate traditional loop constructs, such as those used in matrix-vector products, into this new representation. This is applicable in both distributed and non-distributed computing environments, showcasing the versatility of the approach.
The significance of this work extends beyond theoretical implications; it directly addresses the computational challenges faced by NASA and its Jet Propulsion Laboratory (JPL). By enabling efficient access to sparse data through a set of iteration operators, the proposed method enhances the performance of high-performance computing systems, which are critical for processing and understanding complex scientific datasets.
In summary, the document outlines a significant advancement in the field of sparse data processing, emphasizing a representation-independent approach that is compatible with various programming paradigms. This innovation not only supports NASA's computational needs but also contributes to the broader landscape of high-performance computing, making it a valuable resource for researchers and developers in the field. The work is positioned to facilitate more efficient data handling and processing, ultimately aiding in the analysis of scientific data and enhancing the capabilities of future computing systems.
