Performance modeling and mapping of sparse computations

In the past, knowledge processing (anomaly detection, target identification, social network analysis) of sensor data did not require real-time processing speeds. However, the rapid growth in the size of the data and the shortening time scale of the required data analysis are driving the need for applications that provide real-time signal and knowledge processing at the sensor front end. Many knowledge processing techniques, such as Bayesian networks, social networks, and neural networks, have a graph abstraction. Graph algorithms are difficult to parallelize and thus cannot take advantage of multi-core architectures. Many graph operations can be cast as sparse linear algebra operations. While this increases the ease of programming, parallel sparse algorithms are still inefficient. This paper presents a search-based mapping and routing approach for sparse operations. Since finding well-performing maps and routes for sparse operations is a computationally intensive task, the mapping and routing algorithms have been parallelized to take advantage of the Lincoln Laboratory cluster computing capability, LLGrid. Our parallelization of the approach yielded near linear speed up and the mapping and routing results demonstrate over an order of magnitude performance improvement over traditional mapping techniques.