More Like this

1. Dynamic Mesh Processing on the GPU

   https://doi.org/10.1145/3731162  

   Mahmoud, Ahmed H; Porumbescu, Serban D; Owens, John D (August 2025, ACM Transactions on Graphics)

   We present a system for dynamic triangle mesh processing entirely on the GPU. Our system features an efficient data structure that enables rapid updates to mesh connectivity and attributes. By partitioning the mesh into small patches, we process all dynamic updates for each patch within the GPU's fast shared memory. This approach leveragesspeculative processingfor conflict handling, minimizing rollback costs, maximizing parallelism, and reducing locking overhead. Additionally, we introduce a new programming model for dynamic mesh processing. This model provides concise semantics for dynamic updates, abstracting away concerns about conflicting updates during parallel execution. At the core of our model is thecavity operator, a general mesh update operator that facilitates any dynamic operation by removing a set of mesh elements and inserting new ones into the resulting void. We applied our system to various GPU applications, including isotropic remeshing, surface tracking, mesh decimation, and Delaunay edge flips. On large inputs, our system achieves an order-of-magnitude speedup compared to multi-threaded CPU solutions and is more than two orders of magnitude faster than state-of-the-art single-threaded CPU solutions. Furthermore, our data structure outperforms state-of-the-art GPUstaticdata structures in terms of both speed and memory efficiency. 

   more » « less
2. Thermal Simulation of a CPU Based on Model Order Reduction

   Ruttan K., Jiang L. (October 2020, IEEE MIT Undergraduate Research Technology Conference 2020)

   null (Ed.)

   A previously developed thermal simulation technique based on model order reduction is applied to the simulation of a CPU. The approach is derived from proper orthogonal decomposition (POD) that projects the physical domain onto the POD space. It has been demonstrated that the developed approach offers an accurate thermal simulation of the CPU with a reduction in numerical degrees of freedom by several orders of magnitude compared to the direct numerical simulation (DNS). In addition, the technique has the capability of providing spatial resolution as fine as the direct numerical simulation for the CPU. 

   more » « less
3. G-thinker: A Distributed Framework for Mining Subgraphs in a Big Graph

   Yan, Da; Guo, Guimu; Chowdhury, Md Mashiur; Özsu, Tamer; Ku, Wei-Shinn; Lui, John C.S. (January 2020, Proceedings of the 36th IEEE International Conference on Data Engineering (ICDE))

   Mining from a big graph those subgraphs that satisfy certain conditions is useful in many applications such as community detection and subgraph matching. These problems have a high time complexity, but existing systems to scale them are all IO-bound in execution. We propose the first truly CPU-bound distributed framework called G-thinker that adopts a user-friendly subgraph-centric vertex-pulling API for writing distributed subgraph mining algorithms. To utilize all CPU cores of a cluster, G-thinker features (1) a highly-concurrent vertex cache for parallel task access and (2) a lightweight task scheduling approach that ensures high task throughput. These designs well overlap communication with computation to minimize the CPU idle time. Extensive experiments demonstrate that G-thinker achieves orders of magnitude speedup compared even with the fastest existing subgraph-centric system, and it scales well to much larger and denser real network data. G-thinker is open-sourced at http://bit.ly/gthinker with detailed documentation. 

   more » « less
4. White-box testing of big data analytics with complex user-defined functions

   https://doi.org/10.1145/3338906.3338953  

   Gulzar, Muhammad Ali; Mardani, Shaghayegh; Musuvathi, Madanlal; Kim, Miryung (January 2019, ESEC/FSE 2019: Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering)

   Data-intensive scalable computing (DISC) systems such as Google’s MapReduce, Apache Hadoop, and Apache Spark are being leveraged to process massive quantities of data in the cloud. Modern DISC applications pose new challenges in exhaustive, automatic testing because they consist of dataflow operators, and complex user-defined functions (UDF) are prevalent unlike SQL queries. We design a new white-box testing approach, called BigTest to reason about the internal semantics of UDFs in tandem with the equivalence classes created by each dataflow and relational operator. Our evaluation shows that, despite ultra-large scale input data size, real world DISC applications are often significantly skewed and inadequate in terms of test coverage, leaving 34% of Joint Dataflow and UDF (JDU) paths untested. BigTest shows the potential to minimize data size for local testing by 10^5 to 10^8 orders of magnitude while revealing 2X more manually-injected faults than the previous approach. Our experiment shows that only few of the data records (order of tens) are actually required to achieve the same JDU coverage as the entire production data. The reduction in test data also provides CPU time saving of 194X on average, demonstrating that interactive and fast local testing is feasible for big data analytics, obviating the need to test applications on huge production data. 

   more » « less
5. G-thinker: a general distributed framework for finding qualified subgraphs in a big graph with load balancing

   https://doi.org/10.1007/s00778-021-00688-z  

   Yan, Da; Guo, Guimu; Khalil, Jalal; Özsu, M. Tamer; Ku, Wei-Shinn; Lui, John C. (January 2022, The VLDB journal)

   Finding from a big graph those subgraphs that satisfy certain conditions is useful in many applications such as community detection and subgraph matching. These problems have a high time complexity, but existing systems that attempt to scale them are all IO-bound in execution. We propose the first truly CPU-bound distributed framework called G-thinker for subgraph finding algorithms, which adopts a task-based computation model, and which also provides a user-friendly subgraph-centric vertex-pulling API for writing distributed subgraph finding algorithms that can be easily adapted from existing serial algorithms. To utilize all CPU cores of a cluster, G-thinker features (1) a highly concurrent vertex cache for parallel task access and (2) a lightweight task scheduling approach that ensures high task throughput. These designs well overlap communication with computation to minimize the idle time of CPU cores. To further improve load balancing on graphs where the workloads of individual tasks can be drastically different due to biased graph density distribution, we propose to prioritize the scheduling of those tasks that tend to be long running for processing and decomposition, plus a timeout mechanism for task decomposition to prevent long-running straggler tasks. The idea has been integrated into a novelty algorithm for maximum clique finding (MCF) that adopts a hybrid task decomposition strategy, which significantly improves the running time of MCF on dense and large graphs: The algorithm finds a maximum clique of size 1,109 on a large and dense WikiLinks graph dataset in 70 minutes. Extensive experiments demonstrate that G-thinker achieves orders of magnitude speedup compared even with the fastest existing subgraph-centric system, and it scales well to much larger and denser real network data. G-thinker is open-sourced at http://bit.ly/gthinker with detailed documentation. 

   more » « less