More Like this

1. Distributed numerical and machine learning computations via two-phase execution of aggregated join trees

   https://doi.org/10.14778/3450980.3450991  

   Jankov, Dimitrije; Yuan, Binhang; Luo, Shangyu; Jermaine, Chris (March 2021, Proceedings of the VLDB Endowment)

   null (Ed.)

   When numerical and machine learning (ML) computations are expressed relationally, classical query execution strategies (hash-based joins and aggregations) can do a poor job distributing the computation. In this paper, we propose a two-phase execution strategy for numerical computations that are expressed relationally, as aggregated join trees (that is, expressed as a series of relational joins followed by an aggregation). In a pilot run, lineage information is collected; this lineage is used to optimally plan the computation at the level of individual records. Then, the computation is actually executed. We show experimentally that a relational system making use of this two-phase strategy can be an excellent platform for distributed ML computations. 

   more » « less
2. Higher-order probabilistic adversarial computations: categorical semantics and program logics

   https://doi.org/10.1145/3473598  

   Aguirre, Alejandro; Barthe, Gilles; Gaboardi, Marco; Garg, Deepak; Katsumata, Shin-ya; Sato, Tetsuya (August 2021, Proceedings of the ACM on Programming Languages)

   Adversarial computations are a widely studied class of computations where resource-bounded probabilistic adversaries have access to oracles, i.e., probabilistic procedures with private state. These computations arise routinely in several domains, including security, privacy and machine learning. In this paper, we develop program logics for reasoning about adversarial computations in a higher-order setting. Our logics are built on top of a simply typed λ-calculus extended with a graded monad for probabilities and state. The grading is used to model and restrict the memory footprint and the cost (in terms of oracle calls) of computations. Under this view, an adversary is a higher-order expression that expects as arguments the code of its oracles. We develop unary program logics for reasoning about error probabilities and expected values, and a relational logic for reasoning about coupling-based properties. All logics feature rules for adversarial computations, and yield guarantees that are valid for all adversaries that satisfy a fixed resource policy. We prove the soundness of the logics in the category of quasi-Borel spaces, using a general notion of graded predicate liftings, and we use logical relations over graded predicate liftings to establish the soundness of proof rules for adversaries. We illustrate the working of our logics with simple but illustrative examples. 

   more » « less
3. Perceptual-Centric Image Super-Resolution using Heterogeneous Processors on Mobile Devices

   https://doi.org/10.1145/3636534.3690698  

   Huang, Kai; Yin, Xiangyu; Gu, Tao; Gao, Wei (December 2024, in Proceedings of the 30th ACM International Conference on Mobile Computing and Networking (MobiCom), 2024.)

   Image super-resolution (SR) is widely used on mobile devices to enhance user experience. However, neural networks used for SR are computationally expensive, posing challenges for mobile devices with limited computing power. A viable solution is to use heterogeneous processors on mobile devices, especially the specialized hardware AI accelerators, for SR computations, but the reduced arithmetic precision on AI accelerators can lead to degraded perceptual quality in upscaled images. To address this limitation, in this paper we present SR For Your Eyes (FYE-SR), a novel image SR technique that enhances the perceptual quality of upscaled images when using heterogeneous processors for SR computations. FYESR strategically splits the SR model and dispatches different layers to heterogeneous processors, to meet the time constraint of SR computations while minimizing the impact of AI accelerators on image quality. Experiment results show that FYE-SR outperforms the best baselines, improving perceptual image quality by up to 2x, or reducing SR computing latency by up to 5.6x with on-par image quality. 

   more » « less
4. Rateless Codes for Distributed Non-linear Computations

   https://doi.org/10.1109/ISTC49272.2021.9594268  

   Mallick, Ankur; Smith, Sophie; Joshi, Gauri (October 2021, 11th International Symposium on Topics in Coding)

   Machine learning today involves massive distributed computations running on cloud servers, which are highly susceptible to slowdown or straggling. Recent work has demonstrated the effectiveness of erasure codes in mitigating such slowdown for linear computations, by adding redundant computations such that the entire computation can be recovered as long as a subset of nodes finish their assigned tasks. However, most machine learning algorithms typically involve non-linear computations that cannot be directly handled by these coded computing approaches. In this work, we propose a coded computing strategy for mitigating the effect of stragglers on non-linear distributed computations. Our strategy relies on the observation that many expensive non-linear functions can be decomposed into sums of cheap non-linear functions. We show that erasure codes, specifically rateless codes can be used to generate and compute random linear combinations of these functions at the nodes such that the original function can be computed as long as a subset of nodes return their computations. Simulations and experiments on AWS Lambda demonstrate the superiority of our approach over various uncoded baselines. 

   more » « less
5. Abstractions for specifying sparse matrix data transformations

   Nandy, Payal; Hall, M; Davis, E; Olschanowsky, C; Mohammadi, M; He, W; Strout, M (January 2018, Proceedings of the Eighth International Workshop on Polyhedral Compilation Techniques)

   The inspector/executor paradigm permits using runtime information in concert with compiler optimization. An inspector collects information that is only available at runtime; this information is used by an optimized executor that was created at compile time. Inspectors are widely used in optimizing irregular computations, where information about data dependences, loop bounds, data structures, and memory access pa erns are collected at runtime and used to guide code transformation, parallelization, and data layout. Most research that uses inspectors relies on instantiating inspector templates, invoking inspector library code, or manually writing inspectors. is paper describes abstractions for generating inspectors for loop and data transformations for sparse matrix computations using the Sparse Polyhedral Framework (SPF). SPF is an extension of the polyhedral framework for transformation and code generation. SPF extends the polyhedral framework to represent runtime information with uninterpreted functions and inspector computations that explicitly realize such functions at runtime. It has previously been used to derive inspectors for data and iteration space reordering. is paper introduces data transformations into SPF, such as conversions between sparse matrix formats, and show how prior work can be supported by SPF. We also discuss possible extensions to support inspector composition and incorporate other optimizations. is work represents a step towards creating composable inspectors in keeping with the composability of a ne transformations on the executors. 

   more » « less