I was looking at this today & yesterday. Boding well, these results look right for GPUs because they're in parity w/ Duane Merril's GPU BFS work.
Less clear is whether MapGraph beats existing single node HPC systems. In particular, instead of comparing to GraphLab, I'd love to see comparisons to GraphChi or TurboGraph!
The importance here is that huge graphs are now possible on single-node, and once these techniques get combined into distributed ones, most real-world graphs can be solved in real-time!
(If you like building this kind of bleeding edge stuff in performance, ML, and/or infoviz, we're hiring at graphistry.com :)
I've glanced over your paper just quickly, so I'm not sure whether I missed something: Did you analyze why your 24 threaded CPU version did so much worse in a few cases than the single threaded version? Did you use OpenMP without a defined thread affinity on a multi socket system?
We are big fans of GraphLab. We used the version that was available when we collected the performance data on GraphLab - last summer. The asynchronous engine was seg-faulting which is why we used the synchronous engine. Lots of details about this in the SIGMOD paper:
One current gold-rush topic is ASIC-resistant bitcoin mining.
Bitcoin works by generating a particular type of SHA256 hash -- you take some fixed inputs (transactions), a random input you can change (a nonce), and together they need to SHA256-hash into a special hash, eg one with 5 leading zero's.
This is known as a "proof of work" system -- it has the interesting property that it is quick to verify but difficult to produce (you can't predict a SHA256 hash). Mining bitcoin is basically brute-forcing tons of random inputs until you find an input that produces a special SHA256 hash, which you then advertise to the network and the network rewards you with libertarian disney dollars.
Now, you can make a custom chip (ASIC) that is optimized to churn out as many SHA256 hashes as possible -- far more and far faster than a CPU can. In fact, ASIC mining is the only cost-effective way to mine bitcoin these days. Thus, bitcoin mining is quickly becoming about who can buy the most chips and power them with the cheapest electricity, encouraging massive centralized data farms -- a Bad Thing if you believe in the Decentralize All The Things! promise of bitcoin.
A better proof-of-work system is one that shares the quick-to-verify-difficult-to-solve property of specially-formed SHA256 hashes, but one that can't be specialized for with an ASIC. Then more people could participate on commodity hardware and you would (theoretically) have less centralization (or at least encourage better commodity hardware instead of better specialized SHA256 chips).
Anyways, back to graph processing... one class of problem that is difficult to create specialized ASICs for yet is still 'quick-to-verify-but-difficult-to-solve' is finding cycles of a specific length (say 42) in a large graph. Basically solving such a problem is memory-hard, so an ASIC can only get you so far (although people have proposed ASIC farm architectures that try, eg with shared central memory accessed by many ASIC cores, which is starting to sound a bit like a GPU...)
We're interested in day-to-day business needs. Databases and compute engines here handle real-time transaction processing or data analysis for graph data. E.g., logistics, recommendation systems, social graphs (users, employees, companies), payments (fraud or segmentation), IT systems/traffic (performance & security), knowledge management (manufacturing, legal), etc.
For OLAP style processing there are also many uses. The most common is to look for clusters in large and complex sets of highly related data. (People, for example.) Cluster identification can be used in examining crime networks, disease propogation, finding likely "influencers" for marketing and political purposes, finding many-dimensional patterns of things people tend to buy, and so on. Apache Spark/GraphX is one such tool set.
Twitter uses offline graph processing to suggest who you should follow. Many companies use it (real time or offline) to suggest other items you might want to buy.
The really cool use case in my mind is combining OLTP+OLAP in real time. Hence the interest in GPU acceleration. We have an OLTP platform that integrates a CPU version of the GAS engine used in MapGraph:
Chiming in here. This is Bryan Thompson, the PI for the MapGraph project. We have new results for multiple GPUs with up to 29 billion traversed edges per second on 64 K20 GPUs and 4.3 billion directed edges. The multi-GPU code base is not yet the full MapGraph / GAS API, but we will be fixing that soon. We will be extending the capabilities of the platform in a number of directions, including allowing multiple partitions per GPU so you can operate on graphs larger than the GPU RAM without having to scale-out, and so you can operate on huge graphs on GPU clusters.
GraphLab (a purely memory based system) is much faster than GraphChi (a disk-based system using the parallel sliding window algorithm). Both GraphLab and GraphChi use "vertex cuts" which amount to 2D partitioning, which is what we use in the multi-GPU version MapGraph. This is also what is used by the world record holder for BFS traversal, which is the Blue Gene/Q.
We used the synchronous engine for GraphLab and the specified version of graphlab because that is what existed and worked (without segfaults) when we collected the data for the SIGMOD paper in the summer of 2013. We did cross-check the performance of GraphLab with the GraphLab developers.
One of the main reasons that CPU parallel graph algorithms slow down is because they hit the memory bandwidth of the bus. GPUs have 10x or more memory bandwidth. The K20 has 204 GB/s. The K40 has 288 GB/s. The Pascal GPU (2016) will have over 1 TB/s of memory bandwidth and 24 GB of RAM.
I've listed the MapGraph Publications below. See http://mapgraph.io for more details.
- MapGraph: A High Level API for Fast Development of High Performance Graph Analytics on GPUs - Zhisong Fu, Bryan Thompson, Michael Personick (SYSTAP, LLC). GRADES 2014, June 22, 2014, Snowbird, Utah, USA. Copyright 2014 ACM 978-1-4503-2982-8. DOI:http://dx.doi.org/10.1145/2621934.2621936
"MapGraph is up to two orders of magnitude faster than parallel CPU implementations on up 24 CPU cores and has performance comparable to a state-of-the-art manually optimized GPU implementation."
That doesn't bode well for my $1000 GPU Speed Parity Bounty
at
https://github.com/tromp/cuckoo
based on my belief that the Cuckoo Cycle graph-theoretic proof-of-work algorithm is more suited to CPUs.
I don't know. This is admittedly not something I know much about, but from poking around a bit, it looks like the Gather-Apply-Scatter model - or any other vertex-centric model - is not well suited to finding cycles of specific length. Compare eg GraphChi's triangle-counting code [1], which specifically notes the difficulties arising from having to maintain and work with large adjacency lists. I don't see a way around that for vertex-centric models.
That said, I haven't actually read your miner, so I don't know what it's doing or if something similar can be done for GAS-based frameworks. If someone who knows more wants to chime in, I'd be delighted to read more about this.
Most time in the miner is spent identifying which edges have an endpoint of degree 1, and thus cannot be part of any cycle. This degree counting sounds like it should be right up the Gather-Apply-Scatter alley...
Less clear is whether MapGraph beats existing single node HPC systems. In particular, instead of comparing to GraphLab, I'd love to see comparisons to GraphChi or TurboGraph!
The importance here is that huge graphs are now possible on single-node, and once these techniques get combined into distributed ones, most real-world graphs can be solved in real-time!
(If you like building this kind of bleeding edge stuff in performance, ML, and/or infoviz, we're hiring at graphistry.com :)