Search for: All records

Fixed-point iteration over parallel relational algebra (RA) operators underpins a broad class of symbolic AI and recursive analytic workloads, including graph reachability, points-to analysis, and rule-based inference. At scale, each iteration materializes substantial intermediate and output relations across distributed memory, causing persistence I/O to become a dominant contributor to end-to-end cost. This I/O is inherently write-dominated: every iteration emits a delta of newly derived tuples, while the runtime must periodically checkpoint accumulated relation state to stable storage for fault tolerance and out-of-core execution. This paper presents a case study in optimizing checkpoints for parallel iterated relational algebra, comparing an existing relation-dumping pipeline against a structured, performance-tuned alternative. The baseline stores relations as opaque binary dumps via POSIX positioned writes or collective MPIIO with minimal file-system hinting.We extend this pipeline with a parallel HDF5 backend that stores relations as schema-aware datasets and writes rank partitions using HDF5 hyperslabs with collective transfers. To avoid the performance cliffs associated with default parallel HDF5 settings, we apply a systematic size-aware tuning policy that configures both HDF5 property lists and MPI-IO hints. The optimized pathway uses a two-phase workflow that creates the file and dataset first and then performs the parallel write. It also applies output-regime-dependent alignment and buffering, configures metadata caching and sieve buffering, selects an appropriate dataset layout, and enforces collective dataset transfers. Across final write sizes from 15 GB to 30 GB, the tuned HDF5 path consistently outperforms the MPI-IO baselines. At higher MPI process counts, it is often 35%-58% faster while producing self-describing outputs. 

Modern Datalog engines (e.g., LogicBlox, Soufflé, ddlog) enable their users to write declarative queries which com- pute recursive deductions over extensional facts, leaving high-performance operationalization (query planning, semi- naïve evaluation, and parallelization) to the engine. Such engines form the backbone of modern high-throughput ap- plications in static analysis, network monitoring, and social- media mining. In this paper, we present a methodology for implementing a modern in-memory Datalog engine on data center GPUs, allowing us to achieve significant (up to 45×) gains compared to Soufflé (a modern CPU-based en- gine) on context-sensitive points-to analysis of PostgreSQL. We present GPUlog, a Datalog engine backend that imple- ments iterated relational algebra kernels over a novel range- indexed data structure we call the hash-indexed sorted ar- ray (HISA). HISA combines the algorithmic benefits of in- cremental range-indexed relations with the raw computa- tion throughput of operations over dense data structures. Our experiments show that GPUlog is significantly faster than CPU-based Datalog engines while achieving a favorable memory footprint compared to contemporary GPU-based joins. 

Faceted execution is a linguistic paradigm for dynamic information-flow control with the distinguishing feature that program values may be faceted. Such values represent multiple versions or facets at once, for different security labels. This enables policy-agnostic programming: a paradigm permitting expressive privacy policies to be declared, independent of program logic. Although faceted execution prevents information leakage at runtime, it does not guarantee the absence of failure due to policy violations. By contrast with static mechanisms (such as security type systems), dynamic information-flow control permits arbitrarily expressive and dynamic privacy policies but imposes significant runtime overhead and delays discovery of any possible violations. In this paper, we present the two different abstract interpretations for faceted execution in the presence of first-class policies. We first present an abstraction which allows one to reason statically about the shape of facets at each program point. This abstraction is useful for statically proving the absence of runtime errors and eliminating runtime checks related to facets. Reasoning statically about the contents of faceted values, however, is complicated by the presence of first-class security labels, especially because abstract labels may conflate more than one runtime label. To address these issues, we also develop a more precise abstraction that relies on an analysis tracking singleton heap abstractions. We present an implementation of our coarse abstraction in Racket and demonstrate its performance on several sample programs. We conclude by showing how our precise domain can be used to verify information-flow properties.