Recent advances in computer architecture significantly enhance the computational capacity of multicore systems. It allows large-scale graphs to be processed inside a single machine. Nevertheless, the irregular processing pattern of graph-structured data constrains the hardware resources from being productively utilized. In this paper, we investigate the constraints in two aspects: workload imbalance and parallel inefficiency. When a graph analytics algorithm is multithreaded, the thread time is highly diversified, indicating an uneven work distribution. Also, the intensive thread contention lowers the computing capacity of CPU cores, thereby hindering the effective utilization of CPU resources. To address these challenges, we present a proactive graph caching strategy that unequally segments graph components into cache-able subsets of varying sizes, namely Syze. First, the computational loads of cache-sized subgraphs are estimated. Then, the demanding subgraphs are further subdivided until certain threshold is met. Moreover, during the propagation of updates, a fraction of vertex ID (i.e., several bits) are encoded to facilitate the communication between subgraphs. As a result, Syze is able to balance the workloads amongst the logical cores by shortening the longest thread execution time. Meanwhile, it alleviates thread contention and thus elevates the parallel efficiency of multicores. Compared with well-optimized Ligra, Gemini and GPOP, Syze achieves accelerations by up to <inline-formula><tex-math notation="LaTeX">$17.76\times$</tex-math></inline-formula> , <inline-formula><tex-math notation="LaTeX">$11.67\times$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$2.81\times$</tex-math></inline-formula> respectively. Additionally, the side effects of Syze are evaluated, including raised cache misses and memory accesses. They play a trivial role in deciding the overall performance, as their costs are far outweighed by the gains from the even distribution of workloads and the improved utilization of multicores.  Author: Please confirm or add details for any funding or financial support for the research of this article. ?>

YuAng Chen

Yeh-Ching Chung

IEEE Transactions on Parallel and Distributed Systems

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS (TPDS) 每月出版一次。它发表了一系列论文、对以前发表的论文的评论以及涉及当前对我们的读者很重要的并行和分布式系统研究领域的调查文章。感兴趣的特定领域包括但不限于：A) 并行和分布式算法，重点关注以下主题：计算模型；数值、组合和数据密集型并行算法、并行和分布式系统的算法和数据结构的可扩展性、通信和同步协议、网络算法、调度和负载平衡。B) 并行和分布式计算的应用，包括计算和数据-支持科学与工程、大数据应用、并行众包、大规模社交网络分析、大数据管理、云和网格计算、科学和生物医学应用、移动计算和网络物理系统。C) 并行和分布式架构，包括指令级和线程级并行架构；多处理器系统的设计、分析、实施、故障恢复和性能测量；多核处理器，异构多核系统； PETASCALE 和 EXASCALE 系统设计；新颖的大数据架构；专用架构，包括图形处理器、信号处理器、网络处理器、媒体加速器和其他专用处理器和加速器；技术对建筑的影响；网络和互连架构；并行 I/O 和存储系统；内存层次结构；节能和绿色计算架构；可靠的架构；以及性能建模和评估。D) 并行和分布式软件，包括并行和多核编程语言和编译器、运行时系统、操作系统、互联网计算和 WEB 服务、资源管理（包括绿色计算）、用于网格、云和数据中心的中间件，库、性能建模和评估、并行编程范例以及编程环境和工具。

The IEEE Transactions on Parallel and Distributed Systems (TPDS) is a monthly journal that publishes significant papers, reviews, and survey articles in the field of parallel and distributed systems research. The journal focuses on specific areas including: A) Parallel and distributed algorithms, emphasizing computational models, numerical, combinatorial, and data-intensive parallel algorithms, scalability of algorithms and data structures, communication and synchronization protocols, network algorithms, scheduling, and load balancing; B) Applications of parallel and distributed computing, including computational and data-supported science and engineering, big data applications, parallel crowdsourcing, large-scale social network analysis, big data management, cloud and grid computing, scientific and biomedical applications, mobile computing, and cyber-physical systems; C) Parallel and distributed architectures, covering instruction-level and thread-level parallel architectures, design and analysis of multiprocessor systems, fault tolerance and performance measurement, multicore processors, heterogeneous multicore systems, PETASCALE and EXASCALE system design, novel big data architectures, specialized architectures (including graphics processors, signal processors, network processors, media accelerators, etc.), network and interconnection architectures, parallel I/O and storage systems, memory hierarchies, energy-efficient and green computing architectures, reliable architectures, and performance modeling and evaluation; D) Parallel and distributed software, including parallel and multicore programming languages and compilers, runtime systems, operating systems, internet computing and web services, resource management (including green computing), middleware for grids, clouds, and data centers, libraries, performance modeling and evaluation, parallel programming paradigms, and programming environments and tools.

《IEEE Transactions on Parallel and Distributed Systems (TPDS)》是一本每月出版的期刊，致力于发表并行和分布式系统研究领域的重要论文、评论以及调查文章。期刊关注的特定领域包括：A) 并行和分布式算法，重点研究计算模型、数值、组合和数据密集型并行算法、算法和数据结构的可扩展性、通信和同步协议、网络算法、调度和负载平衡等；B) 并行和分布式计算的应用，包括计算和数据支持的科学与工程、大数据应用、并行众包、大规模社交网络分析、大数据管理、云计算和网格计算、科学与生物医学应用、移动计算和网络物理系统；C) 并行和分布式架构，涵盖指令级和线程级并行架构、多处理器系统的设计与分析、故障恢复与性能测量、多核处理器和异构多核系统、PETASCALE和EXASCALE系统设计、新颖的大数据架构、专用架构（如图形处理器、信号处理器、网络处理器、媒体加速器等）、网络和互连架构、并行I/O和存储系统、内存层次结构、节能和绿色计算架构、可靠性架构以及性能建模与评估；D) 并行和分布式软件，包括并行和多核编程语言与编译器、运行时系统、操作系统、互联网计算与WEB服务、资源管理（包括绿色计算）、用于网格、云和数据中心的中间件、库、性能建模与评估、并行编程范例以及编程环境和工具。

IEEE Trans. Parallel Distrib. Syst.

An Unequal Caching Strategy for Shared-Memory Graph Analytics

This paper presents a proactive graph caching strategy that unequally segments graph components into cache-able subsets of varying sizes, namely Syze, which alleviates thread contention and thus elevates the parallel efficiency of multicores.

Category	Quartile
计算机科学	2
计算机科学, 计算机理论方法	1
计算机科学, 工程电子与电气	2

An Unequal Caching Strategy for Shared-Memory Graph Analytics

ivySCI AI Smartly Parses PDF, Answers Researchers' Questions, and Helps You Understand Papers in Seconds

Journal Info

Category	Quartile
ENGINEERING, ELECTRICAL & ELECTRONIC	1