Publications

Systems and Methods for Footprint Based Scheduling

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

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

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

Computationally Efficient CP Tensor Decomposition Update Framework for Emerging Component Discovery in Streaming Data

We present streaming CP update, an algorithmic framework for updating CP tensor decompositions that possesses the capability of identifying emerging components and can produce decompositions of large, sparse tensors streaming along multiple modes at a low computational cost. We discuss a large-scale implementation of the proposed scheme integrated within the ENSIGN tensor analysis package, and we evaluate and demonstrate the performance of the framework, in terms of computational efficiency and capability to discover emerging components, on a real cyber dataset.

Accelerating Dijkstra's Algorithm Using Multiresolution Priority Queues

Multiresolution priority queues are data structures recently discovered by Reservoir Labs that reduce the entropy of some critical graph algorithms—such as Dijkstra’s or Prim’s algorithms—and deliver new lower computational complexity bounds. These new data structures are capable of exploiting the multiresolution properties of discrete algorithms, a characteristic that has been otherwise overlooked in the field of graph algorithms. Similar to the concept of resolution found in signal processing—by which a signal can be undersampled while information loss is zero or very small—graphs’ entropy tends to be concentrated in regions that can be efficiently exploited by multiresolution data structures. In this approach, a small controllable bounded discrete error is introduced in a way that entropy is substantially reduced, resulting in new lower computational complexity algorithms.

While the fastest currently known graph algorithms provide exact solutions at the expense of incurring high computational costs, a multiresolution graph algorithm is capable of softening graph problems and breaking their current information theoretic barriers, introducing a small amount of controlled error in a way that the problem’s entropy is reduced. As a result, a new class of higher performance graph algorithms is enabled, enabling the solution of previously deemed intractable problems by identifying solutions that are close to optimal and within a known bounded error.