Analysis of Explicit vs. Implicit Tasking in OpenMP using Kripke
November 12, 2018
Dynamic task-based parallelism has become a widely-accepted paradigm in the quest for exascale computing. In this work, we deliver a non-trivial demonstration of the advantages of explicit over implicit tasking in OpenMP 4.5 in terms of both expressiveness and performance. We target the Kripke benchmark, a mini-application used to test the performance of discrete particle codes, and find that the dependence structure of the core “sweep” kernel is well-suited for dynamic task-based
systems. Our results show that explicit tasking delivers a 31.7% and 8.1% speedup over a pure implicit implementation for a small and large problem, respectively, while a hybrid variant also underperforms the explicit variant by 13.1% and 5.8%, respectively.
Google Scholar • Article
Fast Detection of Elephant Flows with Dirichlet-Categorical Inference
November 11, 2018
The problem of elephant flow detection is a longstanding research area with the goal of quickly identifying flows in a network that are large enough to affect the quality of service of smaller flows. Past work in this field has largely been either domain-specific, based on thresholds for a specific flow size metric, or required several hyperparameters, reducing their ease of adaptation to the great variety of traffic distributions present in real-world networks. In this paper, we present an approach to elephant flow detection that avoids these limitations, utilizing the rigorous framework of Bayesian inference. By observing packets sampled from the network, we use Dirichlet-Categorical inference to calculate a posterior distribution that explicitly captures our uncertainty about the sizes of each flow. We then use this posterior distribution to find the most likely subset of elephant flows under this probabilistic model. Our algorithm rapidly converges to the optimal sampling rate at a speed O(1/n), where n is the number of packet samples received, and the only hyperparameter required is the targeted detection likelihood, defined as the probability of correctly inferring all the elephant flows. Compared to the state-of-the-art based on static sampling rate, we show a reduction in error rate by a factor of 20 times. The proposed method of Dirichlet-Categorical inference provides a novel, powerful framework to elephant flow detection that is both highly accurate and probabilistically meaningful.
View the related slides presented at INDIS 2018.
Article
Systems and Methods for Footprint Based Scheduling
October 9, 2018
A system can generate and impose constraints on a compiler/scheduler so as to specifically minimize the footprints of one or more program variables. The constraints can be based on scopes of the variables and/or on dependence distances between statements specifying operations that use the one or more program variables.
Google Scholar • Article
Systems and Methods for Efficient Determination of Task Dependences After Loop Tiling
October 9, 2018
A compilation system can compile a program to be executed using an event driven tasks (EDT) system that requires knowledge of dependencies between program statement instances, and generate the required dependencies efficiently when a tiling transformation is applied. To this end, the system may use pre-tiling dependencies and can derive post-tiling dependencies via an analysis of the tiling to be applied.
Google Scholar • Article
Systems and Methods for Communication Using Sparsity Based Pre-Compensation
October 9, 2018
A signal pre-compensation system analyzes one or more properties of a communication medium and, taking advantage of the locality of propagation, generates using sparse fast Fourier transform (sFFT) a sparse kernel based on the medium properties. The system models propagation of data signals through the medium as a fixed-point iteration based on the sparse kernel, and determines initial amplitudes for the data symbol(s) to be transmitted using different communication medium modes. Fixed-point iterations are performed using the sparse kernel to iteratively update the initial amplitudes. If the iterations converge, a subset of the finally updated amplitudes is used as launch amplitudes for the data symbol(s). The data symbol(s) can be modulated using these launch amplitudes such that upon propagation of the pre-compensated data symbol(s) through the communication medium, they would resemble the original data symbols at a receiver, despite any distortion and/or cross-mode interference in the communication medium.
Google Scholar • Article
