Youssef Elmougy | Publications

2024

On the Cloud We Can’t Wait: Asynchronous Actors Perform Even Better on the Cloud

Aniruddha Mysore, Youssef Elmougy, Akihiro Hayashi

VIVEKFEST Symposium at SPLASH, 2024

Abstract PDF (to appear) Slides (to appear)

This study investigates the performance of asynchronous actor programming and synchronous Partitioned Global Address Space (PGAS) versions of graph kernels on a Cloud platform and a High-Performance Computing (HPC) platform. Using the Bale suite of graph microkernels, we compare the execution times of kernels implemented with OpenSHMEM (synchronous PGAS) and HClib-actor (asynchronous) on both Azure Cloud with Ethernet and an HPC cluster with InfiniBand. Our results reveal significant performance differences between these platforms. While the asynchronous version outperforms the synchronous version in both settings, the performance gap is dramatically wider on the Cloud platform, with the asynchronous version showing up to 1,000x improvement over the synchronous version in some cases. Moreover, we observe highly variable execution times in the Cloud, likely due to shared resource interference and unpredictable data center traffic. These findings highlight the importance of choosing appropriate programming models for different computational platforms, especially as Cloud platforms are becoming more affordable and easier to access compared to traditional HPC clusters. Our work provides valuable insights for both researchers and practitioners in optimizing parallel programming strategies across diverse computational settings.
Enabling User-level Asynchronous Tasking in the FA-BSP Model - Case Study: Distributed Triangle Counting

Akihiro Hayashi, Shubhendra Singhal, Youssef Elmougy, Jiawei Yang

VIVEKFEST Symposium at SPLASH, 2024

Abstract PDF (to appear) Slides (to appear)

While the FA-BSP model provides significant performance improvements in large-scale graph applications, its single-threaded execution model may limit the performance of certain graph applications. This paper explores the potential benefits of enabling user-level asynchronous tasking with async and finish in FA-BSP programs using distributed triangle counting. The initial results from a generic HPC cluster show that a version using asynchronous tasking leads to a performance increase of 3% to 32%.
Asynchronous Distributed Actor-based Approach to Jaccard Similarity for Genome Comparisons

Youssef Elmougy, Akihiro Hayashi, Vivek Sarkar

ISC High Performance, 2024

Abstract PDF Slides GitHub Repo

The computation of genome similarity is important in computational biology applications, and is assessed by calculating the Jaccard similarity of DNA sequencing sets. However, it's challenging to find solutions that can compute Jaccard similarity with the efficiency and scalability needed to fully utilize capabilities of modern HPC hardware. We introduce a novel approach for computing Jaccard similarity for genome comparisons, founded on an actor-based programming model. Our algorithm takes advantage of fine-grained asynchronous computations, distributed/shared memory, and the Fine-grained Asynchronous Bulk-Synchronous Parallelism execution model. Our performance results on the NERSC Perlmutter supercomputer demonstrate that this approach scales to 16,384 cores, showing an average of 4.94x and 5.5x improvement in execution time at the largest scale and relevant hardware performance monitors at medium scale compared to a state-of-the-art baseline. Our approach is also able to process much larger scale genomic datasets than this baseline. We make our source code publicly available at https://github.com/youssefelmougy/jaccard-selector/.
A Distributed, Asynchronous Algorithm for Large-Scale Internet Network Topology Analysis

Youssef Elmougy, Akihiro Hayashi, Vivek Sarkar

IEEE/ACM International Symposium on Cluster Computing and the Grid (CCGRID), 2024. 🏅Won the IEEE TCSC SCALE 2024 Award

Abstract PDF SCALE 2024 Award Slides Demo Video

With the growing complexity of modern internet networks, we introduce a distributed, asynchronous, and scalable algorithm tailored for determining the centrality and importance of various levels of the global internet network topology at a massive scale. By utilizing triangle formations and neighborhood densities in these complex networks, our algorithm provides valuable insights into the structural importance of individual nodes and the intricate relationships among interconnected entities. Focusing on the global internet's prime components — routers, IP addresses, and Autonomous Systems — the algorithm provides a scalable solution extending to the global internet infrastructure, datacenters, cloud networks, and private networks. By taking advantage of the parallelism, distributed processing, efficient communication, and fine-grained asynchronous execution through an Actor-based programming system, our algorithm is capable of efficiently processing and performing rapid computations on large-scale internet networks. We perform scalability studies on the NERSC Perlmutter supercomputer and the Georgia Tech HPC PACE cluster using three large-scale real-world network datasets and one large-scale synthetic network dataset, achieving up to 91.7% parallel efficiency scaling out to 2K cores and reducing execution time from 5.7 hours to 18.3 seconds, while performing 105.4x better on average compared to related approaches. Our research contributes significantly to facilitating enhanced network management, fault tolerance and resilience, and security, but as well to improving overall network stability, reducing latency, and optimizing energy consumption across the vast internet network devices environment.

2023

Accelerating Actor-based Distributed Triangle Counting (poster)

Aniruddha Mysore, Kaushik Ravichandran, Youssef Elmougy, Akihiro Hayashi, Vivek Sarkar

International Conference on Supercomputing (SC), 2023

Abstract Extended Abstract Poster

Triangle counting is a cornerstone operation in large graph analytics. It has been a challenging problem historically, owing to the irregular and dynamic nature of the algorithm. This inhibits compile-time optimizations and also requires runtime optimizations such as message aggregation and load-imbalance mitigation. Popular triangle counting algorithms are either inherently slow, fail to take advantage of advanced hardware in modern processors, or involve sparse matrix operations. With its support for fine-grained asynchronous messages, the Partitioned Global Address Space (PGAS) with the Actor model has been identified to be efficient for irregular applications [3, 11, 12]. However, few triangle counting implementations have been optimally implemented on top of PGAS Actor runtimes. To address the above-mentioned challenges, we propose a setintersection-based implementation of a distributed triangle counting algorithm atop the PGAS actor runtime. Evaluation of our approach on the PACE Phoenix cluster and the Perlmutter supercomputer showed encouraging results.
Demystifying Fraudulent Transactions and Illicit Nodes in the Bitcoin Network for Financial Forensics

Youssef Elmougy, Ling Liu

ACM KDD Conference on Knowledge Discovery and Data Mining (KDD), 2023

Abstract PDF ArXiv PDF Slides GitHub Repo

Blockchain provides the unique and accountable channel for financial forensics by mining its open and immutable transaction data. A recent surge has been witnessed by training machine learning models with cryptocurrency transaction data for anomaly detection, such as money laundering and other fraudulent activities. This paper presents a holistic applied data science approach to fraud detection in the Bitcoin network with two original contributions.

First, we contribute the Elliptic++ dataset, which extends the Elliptic transaction dataset to include over 822k Bitcoin wallet addresses (nodes), each with 56 features, and 1.27M temporal interactions. This enables both the detection of fraudulent transactions and the detection of illicit addresses (actors) in the Bitcoin network by leveraging four types of graph data: (i) the transaction-to-transaction graph, representing the money flow in the Bitcoin network, (ii) the address-to-address interaction graph, capturing the types of transaction flows between Bitcoin addresses, (iii) the address-transaction graph, representing the bi-directional money flow between addresses and transactions (BTC flow from input address to one or more transactions and BTC flow from a transaction to one or more output addresses), and (iv) the user entity graph, capturing clusters of Bitcoin addresses representing unique Bitcoin users. Second, we perform fraud detection tasks on all four graphs by using diverse machine learning algorithms. We show that adding enhanced features from the address-to-address and the address-transaction graphs not only assists in effectively detecting both illicit transactions and illicit addresses, but also assists in gaining in-depth understanding of the root cause of money laundering vulnerabilities in cryptocurrency transactions and the strategies for fraud detection and prevention. The Elliptic++ dataset is released at https://www.github.com/git-disl/EllipticPlusPlus.
Highly Scalable Large-Scale Asynchronous Graph Processing using Actors

Youssef Elmougy, Akihiro Hayashi, Vivek Sarkar

IEEE/ACM International Symposium on Cluster Computing and the Grid (CCGRID), 2023. 🏅Won the IEEE TCSC SCALE 2023 Award

Abstract PDF SCALE 2023 Award Slides Demo Video

With the accelerating growth of Big Data, real-world graph processing applications now need to tackle graphs with billions of vertices and trillions of edges, thereby increasing the demand for effective solutions to application scalability. Unfortunately, current approaches to implementing these applications on modern HPC systems exhibit poor scale-out performance with increasing numbers of nodes. The scalability challenges for these applications are driven by large data sizes, synchronization overheads, and fine-grained communications with irregular data accesses and poor locality. This paper presents the scalability of a novel Actor-based programming system, which provides a lightweight runtime that supports fine-grained asynchronous execution and automatic message aggregation atop a Partitioned Global Address Space (PGAS) communication layer. Evaluations of the Jaccard Index and PageRank applications on the NERSC Perlmutter system demonstrate nearly perfect scaling up to 1,000 nodes and $64$K cores (one-third of the targeted 3000-nodes for Perlmutter). In addition, our Actor-based implementations of Jaccard Index and PageRank executed with parallel efficiencies of 85.7% and 63.4% for the largest run of 64K cores. This performance represents a 29.6x speedup relative to UPC and OpenSHMEM versions of PageRank.
A Fine-grained Asynchronous Bulk Synchronous parallelism model for PGAS applications

Sri Raj Paul, Akihiro Hayashi, Kun Chen, Youssef Elmougy, Vivek Sarkar

Journal of Computational Science, 2023

Abstract PDF GitHub Repo

The Partitioned Global Address Space (PGAS) model is well suited for executing irregular applications on cluster-based systems, due to its efficient support for short, one-sided messages. Separately, the actor model has been gaining popularity as a productive asynchronous message-passing approach for distributed objects in enterprise and cloud computing platforms, typically implemented in languages such as Erlang, Scala or Rust. To the best of our knowledge, there has been no past work on using the actor model to deliver both productivity and scalability to irregular PGAS applications with large number of small messages.

In this paper, we introduce a new programming system for PGAS applications, in which point-to-point remote operations can be expressed as fine-grained asynchronous actor messages. In our approach, the programmer does not need to worry about programming complexities related to message aggregation and termination detection. Our approach can be viewed as extending the classical Bulk Synchronous Parallelism model with fine-grained asynchronous communications within a phase or superstep. We believe that our approach offers a desirable point in the productivity-performance space for PGAS applications, with more scalable performance and higher productivity relative to past approaches. Specifically, for seven irregular mini-applications from the Bale Kernels and three graph kernels executed using 2048 cores in the NERSC Cori system, our approach shows geometric mean performance improvements of >= 20x relative to standard PGAS versions (UPC and OpenSHMEM) while maintaining comparable productivity to those versions.

This is an extended version of the conference paper “A Productive and Scalable Actor-Based Programming System for PGAS Applications” (Paul et al., 2022)[1] from ICCS 2022.

2021

Diagnosing the interference on CPU-GPU Synchronization Caused by CPU Sharing in Multi-Tenant GPU Clouds

Youssef Elmougy, Weiwei Jia, Xiaoning Ding, Jianchen Shan

IEEE International Performance, Computing, and Communications Conference (IPCCC), 2021

Abstract PDF Slides

The GPU-accelerated cloud, enabled by maturing GPU virtualization techniques, has become the most attractive platform for high-performance computing and machine learning workloads. However, it is notoriously challenging to build the multi-tenant GPU cloud where resources, like CPUs and GPUs, can be shared. One well-known and heavily studied reason is that workloads suffer from poor performance isolation and low GPU utilization when GPUs are shared. But little attention has been paid to another fundamental yet under studied problem: how sharing CPUs among GPU instances could affect the workload performance?

Targeting this problem, the paper conducts experiments to measure the performance slowdown and vGPU utilization decrease under interference from CPU sharing. The results show that GPU workloads suffer from poor and unpredictable performance and heavy vGPU under-utilization because of CPU sharing. We find that such interference is the result of the complex interplay between the characteristics of CPU-GPU interactions and the special behavior of shared vCPUs: vCPU discontinuity. To diagnose how vCPU discontinuity causes the interference, the paper leverages NVIDIA Nsight Systems for fine-grained profiling and has the following findings: 1) vCPU discontinuity causes inefficient CPU-GPU synchronizations; 2) vCPU discontinuity delays task offloading to the vGPU; 3) Polling-based CPU-GPU synchronization suffers from interference more than blocking-based CPU-GPU synchronization; 4) GPU workloads with frequent task offloads and synchronizations are more vulnerable. Based on the findings, the paper proposes a novel polling-then-blocking CPU-GPU synchronization primitive. Evaluation shows that it can improve the performance by 4.2x.
Anomaly Detection on Bitcoin, Ethereum Networks Using GPU-accelerated Machine Learning Methods

Youssef Elmougy, Oliver Manzi

IEEE International Conference on Computer Theory and Applications (ICCTA), 2021

Abstract PDF Slides

Blockchain technology is continually gaining momentum, with applications expanding in sectors beyond digital assets and financial services. With the existence of a public distributed ledger, the validity of transactions and accounts on the blockchain can be easily reviewed. Nevertheless, there are malicious persons that attempt to fraud cryptocurrency holders, undermining the reliability of the blockchain. This study focuses on identifying fraudulent transactions and accounts by detecting anomalies in the Bitcoin and the Ethereum transaction networks, the two largest cryptocurrencies. By leveraging GPU-accelerated machine learning models, including Support Vector Machines, Random Forest, and Logistic Regression, we draw the metadata of over 30 million transactions on the Bitcoin network and confirmed transactions from over 500 thousand accounts on the Ethereum network. We offer insight into feature importance through sensitivity analysis, as well as train accurate models that allow for method adoption in automated fraud detection systems. The trained models achieve an accuracy and recall of 96.9% and 0.987 on the Bitcoin dataset, and 80.2% and 0.835 on the Ethereum dataset. The study of anomaly detection in the cryptocurrency blockchain done in this paper can be generalized to other blockchain networks, including health service blockchains, public sector blockchains, and financial intelligence blockchains.