2017 · 29 citations · 40 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureParallel ComputingSchedulingConcurrency ControlHardware AccelerationParallel ArchitecturesParallel Computer ArchitectureShared-memory MultiprocessingShared-memory ParallelismBaseline ArchitectureConflict DetectionGraph Processing SystemsParallel SchedulingParallel Transaction ProcessingScheduler DesignSynchronization MechanismsTransactional Memory
Many applications that operate on large graphs can be intuitively parallelized by executing a large number of the graph operations concurrently and as transactions to deal with potential conflicts. However, large numbers of operations occurring concurrently might incur too many conflicts that would negate the potential benefits of the parallelization which has probably made highly multi-threaded transactional machines seem impractical. Given the large size and topology of many modern graphs, however, such machines can provide real performance, energy efficiency, and programability benefits. This paper describes an architecture that consists of many lightweight multi-threaded processing engines, a global transactional shared memory, and a work scheduler. We present challenges of realizing such an architecture, especially the requirement of scalable conflict detection, and propose solutions. We also argue that despite increased transaction conflicts due to the higher concurrency and single-thread latency, scalable speedup over serial execution can be achieved. We implement the proposed architecture as a synthesizable FPGA RTL design and demonstrate improved per-socket performance (2X) and energy efficiency (22X) by comparing to a baseline platform that contains two Intel Haswell processors, each with 12 cores.
40
Maurice Herlihy, J. Eliot B. Moss · 1993 · 2.2K citations
R-MAT: A Recursive Model for Graph Mining
Deepayan Chakrabarti, Yiping Zhan, Christos Faloutsos · 2004 · 1.3K citations · Full text
A scalable processing-in-memory accelerator for parallel graph processing
Junwhan Ahn, Sungpack Hong, Sungjoo Yoo et al. · 2015 · 761 citations
LogTM: Log-based Transactional Memory
K.E. Moore, Jayaram Bobba, Michelle J. Moravan et al. · 2006 · 685 citations
Robert Alverson, David Callahan, Daniel Cummings et al. · 2014 · 649 citations