检索结果-内蒙古大学图书馆

A Data-Centric Software-Hardware Co-Designed Architecture for large-scale graph processing

IEEE TRANSACTIONS ON COMPUTERS 2025年第4期74卷 1109-1122页

作者： Li, Zerun Chen, Xiaoming Yang, Yuxin Min, Feng Zhang, Xiaoyu Han, Yinhe Chinese Acad Sci Inst Comp Technol Beijing 100190 Peoples R China Univ Chinese Acad Sci Beijing 100190 Peoples R China

graph processing plays an important role in many practical applications. However, the inherent characteristics of graph processing, including random memory access and the low computation-to-communication ratio, make it difficult to efficiently execute on traditional computing architectures, such as CPUs and GPUs. Near-memory computing has the characteristics of low latency and high bandwidth. It is widely regarded as a promising direction for designing graph processing accelerators. However, the storage space of a single device cannot meet the demand of large-scale graph processing. Using multiple devices will bring lots of inter-device data transmission, which may counteract the benefits of near-memory computing. To fundamentally reduce the data transmission overhead, we propose a data-centric graph processing framework for systems with multiple near-memory computing devices. The framework uses a data-centric programming model as the software hardware interface. For software, we propose an optimized data flow and a heuristic multi-step weighted maximum matching algorithm to achieve efficient inter-device communication and ensure load balancing. For hardware, we design a data reuse driven task controller and a data type-aware on-chip memory, which can effectively improve the utilization of the on-chip memory. Compared with the two most recent near-memory graph accelerators, our framework significantly reduces energy consumption and inter-device communication.

关键词： Bandwidth Memory management Computational modeling System-on-chip Software Hardware Computer architecture Three-dimensional displays Performance evaluation Data communication large-scale graph processing near memory computing memory system accelerator

来源：评论

学校读者我要写书评

暂无评论

graphH: A processing-in-Memory Architecture for large-scale graph processing

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2019年第4期38卷 640-653页

作者： Dai, Guohao Huang, Tianhao Chi, Yuze Zhao, Jishen Sun, Guangyu Liu, Yongpan Wang, Yu Xie, Yuan Yang, Huazhong Tsinghua Univ Dept Elect Engn Beijing 100084 Peoples R China Tsinghua Univ Beijing Natl Res Ctr Informat Sci & Technol Beijing 100084 Peoples R China Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90095 USA Univ Calif San Diego Jacobs Sch Engn Comp Sci & Engn Dept La Jolla CA 92093 USA Peking Univ Sch EECS Ctr Energy Efficient Comp & Applicat Beijing 100871 Peoples R China Univ Calif Santa Barbara Dept Elect & Comp Engn Santa Barbara CA 93106 USA

large-scale graph processing requires the high bandwidth of data access. However, as graph computing continues to scale, it becomes increasingly challenging to achieve a high bandwidth on generic computing architectures. The primary reasons include: the random access pattern causing local bandwidth degradation, the poor locality leading to unpredictable global data access, heavy conflicts on updating the same vertex, and unbalanced workloads across processing units. processing-in-memory (PIM) has been explored as a promising solution to providing high bandwidth, yet open questions of graph processing on PIM devices remain in: 1) how to design hardware specializations and the interconnection scheme to fully utilize bandwidth of PIM devices and ensure locality and 2) how to allocate data and schedule processing flow to avoid conflicts and balance workloads. In this paper, we propose graphH, a PIM architecture for graph processing on the hybrid memory cube array, to tackle all four problems mentioned above. From the architecture perspective, we integrate SRAM-based on-chip vertex buffers to eliminate local bandwidth degradation. We also introduce reconfigurable double-mesh connection to provide high global bandwidth. From the algorithm perspective, partitioning and scheduling methods like index mapping interval-block and round interval pair are introduced to graphH, thus workloads are balanced and conflicts arc avoided. Two optimization methods are further introduced to reduce synchronization overhead and reuse on-chip data. The experimental results on graphs with billions of edges demonstrate that graphH outperforms DDR-based graph processing systems by up to two orders of magnitude and 5.12x speedup against the previous PIM design.

关键词： Hybrid memory cube (HMC) large-scale graph processing memory hierarchy on-chip networks

来源：评论

学校读者我要写书评

暂无评论

A Cost-Efficient Auto-Scaling Algorithm for large-scale graph processing in Cloud Environments with Heterogeneous Resources

引用

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 2021年第8期47卷 1729-1741页

作者： Heidari, Safiollah Buyya, Rajkumar Univ Melbourne Sch Comp & Informat Syst Cloud Comp & Distributed Syst CLOUDS Lab Parkville Vic 3010 Australia

graph processing model is being adopted extensively in various domains such as online gaming, social media, scientific computing and Internet of Things (IoT). Since general purpose data processing tools such as MapReduce are shown to be inefficient for iterative graph processing, many frameworks have been developed in recent years to facilitate analytics and computing of large-scale graphs. However, regardless of distributed or single machine based architecture of such frameworks, dynamic scalability is always a major concern. It becomes even more important when there is a correlation between scalability and monetary cost - similar to what public clouds provide. The pay-as-you-go model that is used by public cloud providers enables users to pay only for the number of resources they utilize. Nevertheless, processing large-scale graphs in such environments has been less studied and most frameworks are implemented for commodity clusters where they will not be charged for the resources that they consume. In this paper, we have developed algorithms to take advantage of resource heterogeneity in cloud environments. Using these algorithms, the system can automatically adjust the number and types of virtual machines according to the computation requirements for convergent graph applications to improve the performance and reduce the monetary cost of the entire operation. Also, a smart profiling mechanism along with a novel dynamic repartitioning approach helps to distribute graph partitions expeditiously. It is shown that this method outperforms popular frameworks such as Giraph and decreases more than 50 percent of the dollar cost compared to Giraph.

关键词： Cloud computing Scalability Computational modeling Internet of Things Heuristic algorithms Software algorithms Clustering algorithms Cloud computing large-scale graph processing auto-scaling cost saving heterogeneous resources

来源：评论

学校读者我要写书评

暂无评论

BC-BSP: A BSP-Based System with Disk Cache for large-scale graph processing

BC-BSP: A BSP-Based System with Disk Cache for Large-Scale G...

引用

7th Open Cirrus Summit (OCS)

作者： Bao, Yubin Wang, Zhigang Bai, Qiushi Gu, Yu Yu, Ge Zhang, Hongxu Deng, Chao Guo, Leitao Northeastern Univ Sch Info Sci & Eng Shenyang Peoples R China

ISBN: (纸本)9780769549088

Many applications in real life can be modeled by graph, and the data scale is very large in many fields. People have paid more attention to large-scale graph processing. A BSP-based system with disk cache for large-scale graph processing is proposed in this paper. The system has the ability to expand the functions and strategies (such as adjusting the parameters according to the volume of data and supporting multiple aggregation functions at the same time), to process large-scale data, to balance load, and to run clustering or classification algorithms on metric datasets. Some experiments are done to evaluate the scalability of the system implemented in the paper, and the comparison between BC-BSP-based applications and MapReduce-based ones are made. The experimental results show that BSP-based applications have higher efficiency than the MapReduce-based applications when the volume of data can be put in the memory during the course of processing;on the contrary the latter is better than the former.

关键词： BSP MapReduce large-scale graph processing Disk Cache Big data

来源：评论

学校读者我要写书评

暂无评论

Towards GPU-Accelerated large-scale graph processing in the Cloud

Towards GPU-Accelerated Large-Scale Graph Processing in the ...

引用

5th IEEE International Conference on Cloud Computing Technology and Science (IEEE CloudCom)

作者： Zhong, Jianlong He, Bingsheng Nanyang Technol Univ Singapore 639798 Singapore

ISBN: (纸本)9781479915484

Recently, we have witnessed that cloud providers start to offer heterogeneous computing environments. There have been wide interests in both clusters and cloud of adopting graphics processors (GPUs) as accelerators for various applications. On the other hand, large-scale graph processing is important for many data-intensive applications in the cloud. In this paper, we propose to leverage GPUs to accelerate large-scale graph processing in the cloud. Specifically, we develop an in-memory graph processing engine G2 with three non-trivial GPU-specific optimizations. Firstly, we adopt fine-grained APIs to take advantage of the massive thread parallelism of the GPU. Secondly, G2 embraces a graph partition based approach for load balancing on heterogeneous CPU/GPU architectures. Thirdly, a runtime system is developed to perform transparent memory management on the GPU, and to perform scheduling for an improved throughput of concurrent kernel executions from graph tasks. We have conducted experiments on an Amazon EC2 virtual cluster of eight nodes. Our preliminary results demonstrate that 1) GPU is a viable accelerator for cloud-based graph processing, and 2) the proposed optimizations improve the performance of GPU-based graph processing engine. We further present the lessons learnt and open problems towards large-scale graph processing with GPU accelerations.

关键词： large-scale graph processing GPGPU graph partitioning cloud computing GPU accelerations

来源：评论

学校读者我要写书评

暂无评论

graphIA: An In-situ Accelerator for large-scale graph processing 18

GraphIA: An In-situ Accelerator for Large-scale Graph Proces...

引用

International Symposium on Memory Systems (MEMSYS)

作者： Li, Gushu Dai, Guohao Li, Shuangchen Wang, Yu Xie, Yuan Univ Calif Santa Barbara Dept Elect & Comp Engn Santa Barbara CA 93106 USA Tsinghua Univ Dept Elect Engn BNRist Beijing 100084 Peoples R China

ISBN: (纸本)9781450364751

graph processing is widely used in various domains, while processing large-scale graphs has always been memory-bound. In-situ processing is a promising solution to overcome the "memory wall" challenges in such memory-intensive applications. Previous accelerator designs for graph processing only focused on integrating more computing units inside memories or using more memory layers, rather than exploiting the huge parallelism lying in memory banks. In this paper, we present graphIA, an In-situ Accelerator for large-scale graph processing based on DRAM technology. graphIA couples large-capacity memory and computing resource in DRAM by connecting multiple chips with computation circuits inside. graphIA chips are organized into a scaling ring interconnection, which is able to maximize the individual bandwidth with minimal connection overheads and scale to larger graphs by using more chips. Banks in DRAM are organized into heterogeneous edge and vertex banks, cooperating with customized peripheral circuits. Data duplication and scheduling schemes in heterogeneous banks are further introduced to overcome the performance loss caused by the irregular local and remote memory access in our multi-chip ring structure, achieving 1.63x and 1.16x speedup respectively. According to our extensive experiments, by adopting graphIA design, our in-situ accelerator achieves 217x speedup CPU-DRAM designs.

关键词： large-scale graph processing DRAM In-situ Accelerator

来源：评论

学校读者我要写书评

暂无评论

Out-of-core GPU Memory Management for MapReduce-based large-scale graph processing 16

Out-of-core GPU Memory Management for MapReduce-based Large-...

引用

16th IEEE International Conference on Cluster Computing (CLUSTER)

作者： Shirahata, Koichi Sato, Hitoshi Matsuoka, Satoshi Tokyo Inst Technol Tokyo Japan Japan Sci & Technol Agcy CREST Tokyo Japan

ISBN: (纸本)9781479955480

GPUs can accelerate edge scan performance of graph processing applications;however, the capacity of device memory on GPUs limits the size of graph to process, whereas efficient techniques to handle GPU memory overflows, including overflow detection and performance analysis in large-scale systems, are not well investigated. To address the problem, we propose a MapReduce-based out-of-core GPU memory management technique for processing large-scale graph applications on heterogeneous GPU-based supercomputers. Our proposed technique automatically handles memory overflows from GPUs by dynamically dividing graph data into multiple chunks and overlaps CPU-GPU data transfer and computation on GPUs as much as possible. Our experimental results on TSUBAME2.5 using 1024 nodes (12288 CPU cores, 3072 GPUs) exhibit that our GPU-based implementation performs 2.10x faster than running on CPU when graph data size does not fit on GPUs. We also study the performance characteristics of our proposed out-of-core GPU memory management technique, including application's performance and power efficiency of scale-up and scale-out approaches.

关键词： large-scale graph processing GPGPU MapReduce Out-of-core Algorithms Big Data Applications

来源：评论

学校读者我要写书评

暂无评论

Foregraph: Exploring large-scale graph processing on Multi-FPGA Architecture 17

ForeGraph: Exploring Large-scale Graph Processing on Multi-F...

引用

ACM/SIGDA International Symposium on Field-Programmable Gate Arrays

作者： Dai, Guohao Huang, Tianhao Chi, Yuze Xu, Ningyi Wang, Yu Yang, Huazhong Tsinghua Univ Dept Elect Engn TNLIST Beijing Peoples R China Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90024 USA Microsoft Res Asia Hardware Comp Grp Beijing Peoples R China

ISBN: (纸本)9781450343541

The performance of large-scale graph processing suffers from challenges including poor locality, lack of scalability, random access pattern, and heavy data conflicts. Some characteristics of FPGA make it a promising solution to accelerate various applications. For example, on-chip block RAMs can provide high throughput for random data access. However, large-scale processing on a single FPGA chip is constrained by limited on-chip memory resources and off-chip bandwidth. Using a multi-FPGA architecture may alleviate these problems to some extent, while the data partitioning and communication schemes should be considered to ensure the locality and reduce data conflicts. In this paper, we propose Foregraph, a large-scale graph processing framework based on the multi-FPGA architecture. In Foregraph, each FPGA board only stores a partition of the entire graph in off-chip memory. Communication over partitions is reduced. Vertices and edges are sequentially loaded onto the FPGA chip and processed. Under our scheduling scheme, each FPGA chip performs graph processing in parallel without conflicts. We also analyze the impact of system parameters on the performance of Foregraph. Our experimental results on Xilinx Virtex Ultrascale XCVU190 chip show Foregraph outperforms state-of-the-art FPGA-based large-scale graph processing systems by 4.54x when executing PageRank on the Twitter graph (1.4 billion edges). The average throughput is over 900 MTEPS in our design and 2.03x larger than previous work.

关键词： large-scale graph processing multi-FPGA architecture

来源：评论

学校读者我要写书评

暂无评论

The Comparison of large-scale graph processing Algorithms Implementation Methods for Intel KNL and NVIDIA GPU 3rd

The Comparison of Large-Scale Graph Processing Algorithms Im...

引用

3rd Russian Supercomputing Days (RuSCDays)

作者： Afanasyev, Ilya Voevodin, Vladimir Lomonosov Moscow State Univ Moscow Russia

ISBN: (纸本)9783319712543;9783319712550

The paper describes implementation approaches to large-graph processing on two modern high-performance computational platforms: NVIDIA GPU and Intel KNL. The described approach is based on a deep a priori analysis of algorithm properties that helps to choose implementation method correctly. To demonstrate the proposed approach, shortest paths and strongly connected components computation problems have been solved for sparse graphs. The results include detailed description of the whole algorithm's development cycle: from algorithm information structure research and selection of efficient implementation methods, suitable for the particular platforms, to specific optimizations for each of the architectures. Based on the joint analysis of algorithm properties and architecture features, a performance tuning, including graph storage format optimizations, efficient usage of the memory hierarchy and vectorization is performed. The developed implementations demonstrate high performance and good scalability of the proposed solutions. In addition, a lot of attention was paid to profiling implemented algorithms with NVIDIA Visual Profiler and Intel (R) VTune (TM) Amplifier utilities. This allows current paper to present a fair comparison, demonstrating advantages and disadvantages of each platform for large-scale graph processing.

关键词： graph algorithms GPU KNL CUDA Vectorization SSSP SCC large-scale graph processing

来源：评论

学校读者我要写书评

暂无评论

PMS: an Effective Approximation Approach for Distributed large-scale graph Data processing and Mining 17

PMS: an Effective Approximation Approach for Distributed Lar...

引用

ACM Conference on Information and Knowledge Management (CIKM)

作者： Cao, Yingjie Zhang, Yangyang Li, Jianxin Beihang Univ SKLSDE Beijing Peoples R China Beihang Univ Sch Comp Sci & Engn Beijing Peoples R China

ISBN: (纸本)9781450349185

Recently, large-scale graph data processing and mining has drawn great attention, and many distributed graph processing systems [68, 10, 11, 13, 14, 17, 20] have been proposed. However, large-scale graph processing remains a challenging problem. Because the computation time in some cases is still unacceptable especially when the time is limited. As illustrated in Table 1, nearly three hours are needed when running Single-Source Shortest Path algorithm on the USA-road dataset 1 using performant open-source distributed graph processing systems. In this paper, we propose an effective priority-based message sampling (PMS) approach to further improve the performance of distributed graph processing at the cost of some accuracy loss. Noticing that the passing and processing of messages dominates the computation time, our approach works by eliminating those less useful messages directly without passing them which can effectively reduce the computation overhead. We implement our approach basing on Apache Giraph [6], a popular open-source implementation of Google's Pregel [14] and report the primary results of our prototype system. The experimental results show that our approach can achieve reasonable accuracy with much less computation time.

关键词： large-scale graph processing distributed system approximate computation

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：