Combining Tensor Decompositions and Graph Analytics to Provide Cyber Situational Awareness at HPC Scale
September 24, 2019
This paper describes MADHAT (Multidimensional Anomaly Detection fusing HPC, Analytics, and Tensors), an integrated workflow that demonstrates the applicability of HPC resources to the problem of maintaining cyber situational awareness. MADHAT combines two high-performance packages: ENSIGN for large-scale sparse tensor decompositions and HAGGLE for graph analytics. Tensor decompositions isolate coherent patterns of network behavior in ways that common clustering methods based on distance metrics cannot. Parallelized graph analysis then uses directed queries on a representation that combines the elements of identified patterns with other available information (such as additional log fields, domain knowledge, network topology, whitelists and blacklists, prior feedback, and published alerts) to confirm or reject a threat hypothesis, collect context, and raise alerts. MADHAT was developed using the collaborative HPC Architecture for Cyber Situational Awareness (HACSAW) research environment and evaluated on structured network sensor logs collected from Defense Research and Engineering Network (DREN) sites using HPC resources at the U.S. Army Engineer Research and Development Center DoD Supercomputing Resource Center (ERDC DSRC). To date, MADHAT has analyzed logs with over 650 million entries.
Article
Automatic Parallelization to Asynchronous Task- Based Runtimes Through a Generic Runtime Layer
September 24, 2019
With the end of Moore’s law, asynchronous taskbased parallelism has seen growing support as a parallel programming paradigm, with the runtime system offering such advantages as dynamic load balancing, locality, and scalability. However, there has been a proliferation of such programming systems in recent years, each of which presents different performance tradeoffs and runtime semantics. Developing applications on top of these systems thus requires not only application expertise but also deep familiarity with the runtime, exacerbating the perennial problems of programmability and portability. This work makes three main contributions to this growing landscape. First, we extend a polyhedral optimizing compiler with techniques to extract task-based parallelism and data management for a broad class of asynchronous task-based runtimes. Second, we introduce a generic runtime layer for asynchronous task-based systems with representations of data and tasks that are sparse and tiled by default, which serves as an abstract target for the compiler backend. Finally, we implement this generic layer using OpenMP and Legion, demonstrating the flexibility and viability of the generic layer and delivering an end-to-end path for automatic parallelization to asynchronous task-based runtimes. Using a wide range of applications from deep learning to scientific kernels, we obtain geometric mean speedups of 23.0 (OpenMP) and 9.5 (Legion) using 64 threads.
Article
Fast and Scalable Distributed Tensor Decompositions
September 24, 2019
Tensor decomposition is a prominent technique
for analyzing multi-attribute data and is being increasingly
used for data analysis in different application areas. Tensor
decomposition methods are computationally intense and often
involve irregular memory accesses over large-scale sparse data.
Hence it becomes critical to optimize the execution of such data
intensive computations and associated data movement to reduce
the eventual time-to-solution in data analysis applications. With
the prevalence of using advanced high-performance computing
(HPC) systems for data analysis applications, it is becoming
increasingly important to provide fast and scalable implementation
of tensor decompositions and execute them efficiently on
modern and advanced HPC systems. In this paper, we present
distributed tensor decomposition methods that achieve faster,
memory-efficient, and communication-reduced execution on HPC
systems. We demonstrate that our techniques reduce the overall
communication and execution time of tensor decomposition
methods when they are used for analyzing datasets of varied
size from real application. We illustrate our results on HPE
Superdome Flex server, a high-end modular system offering
large-scale in-memory computing, and on a distributed cluster
of Intel Xeon multi-core nodes.
Article
Fast Large-Scale Algorithm for Electromagnetic Wave Propagation in 3D Media
September 24, 2019
We present a fast, large-scale algorithm for the
simulation of electromagnetic waves (Maxwell’s equations) in
three-dimensional inhomogeneous media. The algorithm has a
complexity of O(N log(N)) and runs in parallel. Numerical
simulations show the rapid treatment of problems with tens of
millions of unknowns on a small shared-memory cluster ( 16
cores).
Article
Combinatorial Multigrid: Advanced Preconditioners For Ill-Conditioned Linear Systems
September 24, 2019
The Combinatorial Multigrid (CMG) technique is a
practical and adaptable solver and combinatorial preconditioner
for solving certain classes of large, sparse systems of linear equations.
CMG is similar to Algebraic Multigrid (AMG) but replaces
large groupings of fine-level variables with a single coarse-level
one, resulting in simple and fast interpolation schemes. These
schemes further provide control over the refinement strategies at
different levels of the solver hierarchy depending on the condition
number of the system being solved [1]. While many pre-existing
solvers may be able to solve large, sparse systems with relatively
low complexity, inversion may require O(n2) space; whereas, if
we know that a linear operator has ~n = O(n) nonzero elements,
we desire to use O(n) space in order to reduce communication
as much as possible.
Being able to invert sparse linear systems of equations, asymptotically
as fast as the values can be read from memory, has been
identified by the Defense Advanced Research Projects Agency
(DARPA) and the Department of Energy (DOE) as increasingly
necessary for scalable solvers and energy-efficient algorithms [2],
[3] in scientific computing. Further, as industry and government
agencies move towards exascale, fast solvers and communicationavoidance
will be more necessary [4], [5]. In this paper, we present
an optimized implementation of the Combinatorial Multigrid in
C using Petsc and analyze the solution of various systems using
the CMG approach as a preconditioner on much larger problems
than have been presented thus far. We compare the number of
iterations, setup times and solution times against other popular
preconditioners for such systems, including Incomplete Cholesky
and a Multigrid approach in Petsc against common problems,
further exhibiting superior performance by the CMG. 1 2
Index Terms—combinatorial algorithms, spectral support
solver, linear systems, fast solvers, preconditioners, multigrid,
graph laplacian, benchmarking, iterative solvers
Article
