Solomonik’s Communication Cost Research Earns Early Career Prize From SIAM Supercomputing Group

12/2/2019 David Mercer, Illinois Computer Science

Prof. Edgar Solomonik was recognized for work that addresses a key challenge in parallel algorithms.

Written by David Mercer, Illinois Computer Science

The Society for Industrial and Applied Mathematics (SIAM) has awarded Illinois CS Assistant Professor Edgar Solomonik its SIAG/SC Early Career Prize for work that produced an algorithm that reduces the communication cost involved in parallel computing.

Edgar Solomonik
Edgar Solomonik
SIAG/SC is SIAM’s supercomputing group, and the prize is recognition of truly influential work done by a young researcher.

The prize is awarded every two years to an individual in their early career for outstanding research contributions in algorithms research and development for parallel scientific and engineering computing. The work, according to SIAM, “must contain significant research contributions to algorithms for parallel computing in science and engineering.”

“I’m very excited to receive the award,” Solomonik said, noting that he knows every member of the small group of previous winners. “I’m grateful to be part of such a list of researchers.”

Those prior winners include former Illinois CS Adjunct Professor Torsten Hoefler, who won in 2012 and is now a professor at ETH Zurich and director of its Scalable Parallel Computing Laboratory. Hoefler was also Solomonik’s post-doctoral advisor, and a co-author of the paper for which Solomonik was recognized with the Early Career prize. Wake Forest University Assistant Professor Grey Ballard also was a co-author.

The paper is “A Communication-Avoiding Parallel Algorithm for the Symmetric Eigenvalue Problem.” It was published in the proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures in 2017.

Professor James W. Demmel, who was Solomonik’s PhD advisor at the University of California, Berkeley and another co-author, nominated him for the prize.

Demmel’s nomination letter outlines how fundamental the problem Solomonik’s work attempts to address is to computing.

“A major motivation for Edgar's, and much of our group's and now others' work, is that arithmetic is no longer the dominant cost in executing many algorithms, instead the main cost is communication, i.e. moving data, either between levels of a memory hierarchy or between processors over a network,” Demmel wrote.

“So to continue to scale algorithms to run efficiently on more processors or new memory hierarchies, it is important to design algorithms that communicate as little as possible, hitting lower bounds if possible.”

Solomonik, as Demmel noted in his letter, is widely known for his work on parallel algorithms with reduced or even optimal communication requirements for a number of computational tasks.

In this case, Solomnik said, the paper introduced an algorithm that computes eigenvalues – numbers that characterize a matrix – and does so with reduced movement of data.

“Such algorithms have been known going back to the ‘80s,” he said. “We have extended those to a number of new problems and shown that they can be practical in new implementations.

“A communication cost, both in terms of the amount of data moved as well as in the number of times different processes have to communicate, poses the main problem in parallel algorithms,” Solomonik said.

Research presented in the paper then goes a step further, using two new parallel algorithms that achieve lower communication costs for the full-to-band and band-to-band reductions. Both of these algorithms leverage a novel QR factorization algorithm for rectangular matrices.

In addition to the prize, Solomonik says he’s particularly excited about the opportunities for him and for his research group at the upcoming SIAM Conference on Parallel Processing for Scientific Computing, where he’ll receive the prize.

Solomonik will have the chance to deliver a talk, and several of his students will have the chance to present their research, too. 

Poster presentations are planned by PhD students Linjian Ma and Yuchen Pang, and by MS student Navjot Singh. Talks will be given by PhD students Samah Karim and Edward Hutter, both part of a 12-speaker mini-symposium organized by Solomonik.

He sees the conference as a great opportunity for his entire group.

“Currently we are doing research in a few different areas, largely tied in by the general direction of more efficient algorithms for tensor computations,” Solomonik said. “When used in algebraic expressions, tensors kind of open up a whole new body of questions in numerical algorithms.”


Share this story

This story was published December 2, 2019.