Invited Talk 1

Maintaining Connected Components for Unending Graph Streams

Cynthia Phillips
(Sandia National Laboratories)

Motivated by the properties of (unending) real-world cybersecurity streams, we summarize/sketch an algorithm to maintain a streaming graph and its connected components at single-edge granularity: every edge insertion could be followed by a query related to connectivity. To the best of our knowledge, this is the first streaming graph system to update at that granularity. In cybersecurity graph applications, the input stream typically consists of edge insertions; individual deletions are not explicit. Analysts will maintain as much history as possible and will trigger bulk deletions when necessary. During a bulk deletion (called "aging"), and the associated data-structure repairs, queries are disabled, but the system properly ingests any new edges that arrive.
 
We briefly describe the (distributed parallel) algorithms. We present a (proved) relationship among four quantities for indefinite operation: the proportion of query downtime allowed, the proportion of edges that survive an aging event, the proportion of duplicated edges, and the bandwidth expansion factor. The latter is how much faster processors must communicate with each other than the stream arrival rate. We will also present some experimental results on Intel Sky Lake processors. This algorithm might be of increased interest now with the arrival of systems like Cerebras with extremely fast on-wafer networking.

Mobirise

Cindy Phillips historically worked in combinatorial optimization, algorithm design and analysis, and parallel computation with elements of operations research. Her work has spanned theory, general solver development, and applications. She still works in combinatorial optimization. More recently, she has worked in “big data” areas, including streaming, complex (social) network analysis, and trajectory analysis and she has worked in co-design of algorithms and architectures for extreme-scale future machines. She also has worked in/done work in: scheduling, network and infrastructure surety, integer programming, graph algorithms, and cybersecurity.

Invited Talk 2

Communicating More—synchronously—saves Time

Richard Vuduc
(Georgia Institute of Technology)

The mantra of parallel algorithms is "minimize communication." We counter this view by showing instances where communicating more, not less, saves time. While these examples come primarily from applications in graph analytics with fine-grained communication and irregular parallelism, there are also instances in dense matrix computation where a similar conclusion may hold, at least in theory. The key technique is asynchronous, aggressively overlapped communication. A question I will pose is whether overlapping is merely a performance engineering concern, or whether there is anything algorithmically deeper about it “under the hood.”
Mobirise

Rich Vuduc is a professor at the Georgia Institute of Technology (“Georgia Tech”), in the School of Computational Science and Engineering, a department devoted to the study of computer-based modeling and simulation of natural and engineered systems. His research lab, The HPC Garage (@hpcgarage), is interested in high-performance computing, with an emphasis on algorithms, performance analysis, and performance engineering. He is a recipient of a DARPA Computer Science Study Groupgrant; an NSF CAREER award; a collaborative Gordon Bell Prize in 2010; Lockheed-Martin Aeronautics Company Dean’s Award for Teaching Excellence (2013); and Best Paper Awards at the SIAM Conference on Data Mining (SDM, 2012) and the IEEE Parallel and Distributed Processing Symposium (IPDPS, 2015), among others. He has also served as his department’s Associate Chair and Director of its graduate programs. External to Georgia Tech, he currently serves as Chair of the SIAM Activity Group on Supercomputing (2018-2020); co-chaired the Technical Papers Program of the “Supercomputing” (SC) Conference in 2016; and serves as an associate editor of both the International Journal of High-Performance Computing Applications and IEEE Transactions on Parallel and Distributed Systems. He received his Ph.D. in Computer Science from the University of California, Berkeley, and was a postdoctoral scholar in the Center for Advanced Scientific Computing the Lawrence Livermore National Laboratory.

‌

AI Website Generator