TechTalks from event: IEEE IPDPS 2011

Note 1: Only plenary sessions (keynotes, panels, and best papers) are accessible without requiring log-in. For other talks, you will need to log-in using the email you registered for IPDPS 2011. Note 2: Many of the talks (those without a thumbnail next to the their description below) are yet to be uploaded. Some of them were not recorded because of technical problems. We are working with the corresponding authors to upload the self-recorded versions here. We sincerely thank all authors for their efforts in making their videos available.

SESSION 14: Parallel Graph and Particle Algorithms

  • Computing Strongly Connected Components in Parallel on CUDA Authors: Jiri Barnat (Masaryk University, Czech Republic); Petr Bauch (Masaryk University, Czech Republic); Lubos Brim (Masaryk Universi
    The problem of decomposing a directed graph into its strongly connected components is a fundamental graph problem inherently present in many scienti?c and commercial applications. In this paper we show how some of the existing parallel algorithms can be reformulated in order to be accelerated by NVIDIA CUDA technology. In particular, we design a new CUDA-aware procedure for pivot selection and we adapt selected parallel algorithms for CUDA accelerated computation. We also experimentally demonstrate that with a single GTX 480 GPU card we can easily outperform the optimal serial CPU implementation by an order of magnitude in most cases, 40 times on some suf?ciently big instances. This is an interesting result as unlike the serial CPU case, the asymptotic complexity of the parallel algorithms is not optimal.
  • On optimal tree traversals for sparse matrix factorization Authors: Mathias Jacquelin (ENS Lyon, France); Loris Marchal (CNRS, France); Yves Robert (ENS Lyon, France); Bora Ucar (CNRS, France)
    We study the complexity of traversing tree-shaped work?ows whose tasks require large I/O ?les. Such work?ows typically arise in the multifrontal method of sparse matrix factorization. We target a classical two-level memory system, where the main memory is faster but smaller than the secondary memory. A task in the work?ow can be processed if all its predecessors have been processed, and if its input and output ?les ?t in the currently available main memory. The amount of available memory at a given time depends upon the ordering in which the tasks are executed. What is the minimum amount of main memory, over all postorder schemes, or over all possible traversals, that is needed for an in-core execution? We establish several complexity results that answer these questions. We propose a new, polynomial time, exact algorithm which runs faster than a reference algorithm. Next, we address the setting where the required memory renders a pure in-core solution unfeasible. In this setting, we ask the following question: what is the minimum amount of I/O that must be performed between the main memory and the secondary memory? We show that this latter problem is NP-hard, and propose ef?cient heuristics. All algorithms and heuristics are thoroughly evaluated on assembly trees arising in the context of sparse matrix factorizations.
  • Fast Community Detection Algorithm With GPUs and Multi-core Architectures Authors: Jyothish Soman (IIIT-Hyderabad, India); Ankur Narang (IBM India Research Labs, New Delhi, India)
    In this paper, we present the design of a novel scalable parallel algorithm for community detection optimized for multi-core and GPU architectures. Our algorithm is based on label propagation, which works solely on local information, thus giving it the scalability advantage over conventional approaches. We also show that weighted label propagation can overcome typical quality issues in communities detected with label propagation. Experimental results on well known massive scale graphs such as Wikipedia (100M edges) and also on RMAT graphs with 10M - 40M edges, demonstrate the superior performance and scalability of our algorithm compared to the well known approaches for community detection. On the hep-th graph (352K edges) and the wikipedia graph (100M edges), using Power 6 architecture with 32 cores, our algorithm achieves one to two orders of magnitude better performance compared to the best known prior results on parallel architectures with similar number of CPUs. Further, our GPGPU based algorithm achieves 8 improvement over the Power 6 performance on 40M edge R-MAT graph. Alongside, we achieve high quality (modularity) of communities detected, with experimental evidence from well-known graphs such as Zachary karate club, Dolphin network and Football club, where we achieve modularity that is close to the best known alternatives. To the best of our knowledge these are best known results for community detection on massive graphs (100M edges) in terms of performance and also quality vs. performance trade-off. This is also a unique work on community detection on GPGPUs with scalable performance.
  • A Study of Parallel Particle Tracing for Steady-State and Time-Varying Flow Fields Authors: Tom Peterka (Argonne National Laboratory, USA); Robert Ross (Argonne National Laboratory, USA); Boonthanome Nouanesengsey (The
    Particle tracing for streamline and pathline generation is a common method of visualizing vector ?elds in scienti?c data, but it is dif?cult to parallelize ef?ciently because of demanding and widely varying computational and communication loads. In this paper we scale parallel particle tracing for visualizing steady and unsteady ?ow ?elds well beyond previously published results. We con?gure the 4D domain decomposition into spatial and temporal blocks that combine in-core and out-of-core execution in a ?exible way that favors faster run time or smaller memory. We also compare static and dynamic partitioning approaches. Strong and weak scaling curves are presented for tests conducted on an IBM Blue Gene/P machine at up to 32 K processes using a parallel ?ow visualization library that we are developing. Datasets are derived from computational ?uid dynamics simulations of thermal hydraulics, liquid mixing, and combustion.