XPS: EXPL: FP: Collaborative Research: SPANDAN: Scalable Parallel Algorithms for Network Dynamics Analysis

University Of Nebraska At Omaha, Omaha NE

Investigators

Abstract

The goal of SPANDAN project is to create a novel architecture-independent framework for designing efficient, portable and scalable parallel algorithms for analyzing large-scale dynamic networks. SPANDAN will not only provide an intuitive methodology for efficiently translating sequential algorithms into scalable parallel algorithms for dynamic networks, but also provide mechanisms for their analytical evaluation and serve as a mediatory layer between applications and system level tuning. To evaluate the effectiveness of SPANDAN framework in real-world applications, the PIs will collaborate with social scientists and biologists. They will also integrate research findings into various courses such as network analysis, parallel algorithms, and bioinformatics. They will further collaborate with high schools to develop summer courses with the goal of encouraging women and minority students to pursue IT-related careers. As the underlying methodology, the SPANDAN framework will exploit graph sparsification techniques to divide the network into sparse subgraphs (certificates) that form the leaves of a sparsification tree. This innovative approach will lead to the design and analysis of efficient parallel algorithms for updating dynamic networks, and reduction of memory latency associated with parallelizing unstructured data. Specifically parallel algorithms will be designed for maintaining network topological characteristics, and updating influential vertices and communities. To demonstrate portability and performance, the developed algorithms will be implemented on the distributed memory clusters, shared memory multicores, and massively multithreaded CRAY-XMT. For further information see the project web site at: http://cs.mst.edu/labs/crewman/projects/SPANDAN/