Write a Blog >>
PPoPP 2021
Sat 27 February - Wed 3 March 2021
Tue 2 Mar 2021 13:54 - 14:00 - Session 7. Posters 2 Chair(s): Todd Mytkowicz

Uncertain (or Probabilistic) graphs have been ubiquitously used to represent noisy, incomplete, and inaccurate linked data in many emerging applications. Existing solutions are heavily time-consumed on even a simple node-to-node reliability query over uncertain graphs, which is a #P-hard problem, as they need to evaluate an exponential number of certain instances (``possible worlds") generated from the uncertain graph. Modern GPUs provide the massive amount of parallelism to efficiently process large-scale certain graph computation, but the challenges still exist due to their lack of the support for complex probabilistic nature of uncertain graphs. Specifically, the storage representation of an uncertain graph would be exponential on samples for reasonable accuracy. Traditional processing methods by storing each instance and then running certain graph analytic are deemed undesirable on GPU. Meanwhile, compared to conventional certain graph analytics, the probabilistic processing along each node-to-node path over an uncertain graph is much more computation-insensitive than memory-insensitive traversal.

To address these challenges, we adopt a unified indexing bit-aware path structure (BitPath) by pre-sampling ``possible world", which largely reduces the redundant irregular traversing and computation overhead, and propose to share and prune these pre-indexed BitPaths on parallel configurations. By taking advantage of GPUs, We present BPGraph, an efficient and scalable GPU-accelerated analytic framework that processes uncertain graphs using optimized fine-grained hybrid execution and GPU-friendly data formation after decomposing graph into more regular linked pieces. BPGraph proposes constructs for the uncertain graph applications on multi-accelerator programming. Meanwhile, several modern GPU-based features are exploited to accelerate the parallel execution, including cooperative groups and a finer-grained intra-GPU synchronization between parallel threads. Extensive experimental evaluations on widely real-world graphs and algorithms demonstrate that BPGraph significantly achieves significant speedup compared to CPU-based approaches.

Conference Day
Tue 2 Mar

Displayed time zone: Eastern Time (US & Canada) change

13:30 - 14:30
Session 7. Posters 2Main Conference
Chair(s): Todd MytkowiczMicrosoft Research
13:30
6m
Talk
POSTER: In-situ Workflow Auto-tuning through Combining Component Models
Main Conference
Tong ShuSouthern Illinois University Carbondale, Yanfei GuoArgonne National Laboratory, Justin WozniakArgonne National Laboratory, Xiaoning DingNew Jersey Institute of Technology, Ian FosterArgonne Nat Lab and U.Chicago, Tahsin KurcStony Brook University
Link to publication
13:36
6m
Talk
POSTER: Simplifying Low-Level GPU Programming with GAS
Main Conference
Da YanHong Kong University of Science and Technology, Wei WangHong Kong University of Science and Technology, Xiaowen ChuHong Kong Baptist University
Link to publication
13:42
6m
Talk
POSTER: Corder: Cache-Aware Reordering for Optimizing Graph Analytics
Main Conference
YuAng ChenThe Chinese University of Hong Kong, Shenzhen, Yeh-Ching ChungThe Chinese University of Hong Kong, Shenzhen
Link to publication
13:48
6m
Talk
POSTER: DFOGraph: An I/O- and Communication-Efficient System for Distributed Fully-out-of-Core Graph Processing
Main Conference
Jiping YuTsinghua University, Wei QinTsinghua University, Xiaowei ZhuTsinghua University, Zhenbo SunTsinghua University, Jianqiang HuangTsinghua University, Xiaohan LiTsinghua University, Wenguang ChenTsinghua University
Link to publication
13:54
6m
Talk
POSTER: An Efficient Uncertain Graph Processing Framework for Heterogeneous Architectures
Main Conference
Heng ZhangInstitute of Software, Chinese Academy of Sciences; University of Sydney, Lingda LiBrookhaven National Laboratory, Donglin ZhuangUniversity of Sydney, Rui LiuUniversity of Chicago, Shuang SongFacebook Inc., Dingwen TaoWashington State University, Yanjun WuInstitute of Software, Chinese Academy of Sciences, Shuaiwen Leon SongUniversity of Sydney
Link to publication
14:00
6m
Talk
POSTER: Dynamic Scaling for Low-Precision Learning
Main Conference
Ruobing HanPeking University, Min SiArgonne National Laboratory, James W. DemmelUC Berkeley, Yang YouUC Berkeley
Link to publication
14:06
6m
Talk
POSTER: Exploring Deep Reuse in Winograd CNN Inference
Main Conference
Ruofan WuRenmin University of China, Feng ZhangRenmin University of China, Zhen ZhengAlibaba Group, Xiaoyong DuRenmin University of China, Xipeng ShenNorth Carolina State University
Link to publication
14:12
6m
Talk
POSTER: A Novel Memory-Efficient Deep Learning Training Framework via Error-Bounded Lossy Compression
Main Conference
Sian JinWashington State University, Guanpeng LiUniversity of Iowa, Shuaiwen Leon SongUniversity of Sydney, Dingwen TaoWashington State University
Link to publication
14:18
6m
Talk
POSTER: FFT Blitz: The Tensor Cores Strike Back
Main Conference
Sultan DurraniUniversity of Illinois at Urbana-Champaign, Muhammad Saad ChughtaiGeorgia Institute of Technology, Abdul DakkakUniversity of Illinois at Urbana-Champaign, Wen-mei HwuUniversity of Illinois at Urbana-Champaign, Lawrence RauchwergerUIUC
Link to publication
14:24
6m
Break
Break
Main Conference