2016/03/08 by Varun Nagpal, Nagpal, Varun
Computer Science · #C.1.2 #C.1.3 #C.1.4 #C.4 #D.1.3 #Distributed #E.1 #F.2.2 #FOS: Computer and information sciences #G.1.0 #G.2.2 #Graph Theory and Algorithms #H.3.4 #I.3.1 #Interconnection Networks and Systems #Network Packet Processing and Optimization #Parallel #Parallel Computing and Optimization Techniques #Performance (cs.PF) #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1603.02655
openalex publication_date 2016/03/08 · openalex created_date 2022/09/30 · openalex updated_date 2026/07/28
One area of Computing applications which poses significant challenge of\nperformance scalability on Chip Multiprocessors(CMP's) are Irregular\napplications. Such applications have very little computation and unpredictable\nmemory access patterns making them memory-bound in contrast to compute-bound\napplications. Since the gap between processor and memory performance continues\nto exist, difficulty to hide and decrease this gap is one of the important\nfactors which results in poor performance of these applications on CMP's.\n The goal of this thesis is to overcome many such challenges posed during\nperformance acceleration of an irregular graph algorithm called Triad Census.\nWe accelerated the Triad Census algorithm on two significantly different Chip\nMultiprocessors: Dual-socket Intel Xeon Multicore (8 hardware threads per\nsocket) and 240-processor core NVIDIA Tesla C1060 GPGPU(128 hardware threads\nper core).\n The experimental results obtained on Intel Multicore Xeon system shows\nperformance speedups (w.r.t baseline sequential) of maximum 56x , average 33x\nand minimum 8.3x for real world graph data sets. On NVIDIA Tesla C1060 GPGPU,\nwe were able to match almost equally the Multicore results - 58.4x maximum,\n32.8x average and 4.2x minimum speedups w.r.t baseline sequential. In terms of\nraw performance, for the graph data set called Patents network, our results on\nIntel Xeon Multicore(16 hw threads) were 1.27x times faster than previous\nresults on Cray XMT(16 hw threads) while results achieved on GPGPU were\ncomparatively slower(0.72x). To the best of our knowledge, this algorithm has\nonly been accelerated on supercomputer class computer named Cray XMT and no\nwork exists that demonstrates performance evaluation and comparison of this\nalgorithm on relatively lower-cost Multicore and GPGPU based platforms.\n