2009 · 184 citations · 20 references
ComputingComputer ScienceData MiningMachine LearningParallel ComputingData LocalityData ParallelismMatrix ComputationParallel ComputationParallel Performance AnalysisDense Matrix AlgorithmsMulti-core ComputingParallel ClusteringParallel Data MiningParallel ProgrammingParallel Sparse Linear AlgebraSparse Matrix AlgorithmsSparse Matrix Computation
Until recently, parallel programming has largely focused on the exploitation of data-parallelism in dense matrix programs. However, many important application domains, including meshing, clustering, simulation, and machine learning, have very different algorithmic foundations: they require building, computing with, and modifying large sparse graphs. In the parallel programming literature, these types of applications are usually classified as irregular applications, and relatively little attention has been paid to them. To study and understand the patterns of parallelism and locality in sparse graph computations better, we are in the process of building the Lonestar benchmark suite. In this paper, we characterize the first five programs from this suite, which target domains like data mining, survey propagation, and design automation. We show that even such irregular applications often expose large amounts of parallelism in the form of amorphous data-parallelism. Our speedup numbers demonstrate that this new type of parallelism can successfully be exploited on modern multi-core machines.
20
Adhi Harmoko S, M.Komp, Joseph Marie Jacquard et al. · 2005 · 18.4K citations
A hierarchical O(N log N) force-calculation algorithm
Josh Barnes, Piet Hut · Nature · 1986 · 3.7K citations
Steven Cameron Woo, Moriyoshi Ohara, Evan Torrie et al. · 1995 · 3.6K citations · Full text
Christian Bienia, Sanjeev Kumar, Jaswinder Pal Singh et al. · 2008 · 3.4K citations
Chi-Keung Luk, Robert Cohn, Robert Muth et al. · ACM SIGPLAN Notices · 2005 · 3.2K citations