High Performance Low Rank Schur Complement for the Helmholtz Equation
A bit of a disclaimer here, I don't have really too much of a background in seismic.
In fact, my background is mostly in HPC and linear algebra. So if you have any question on seismic, I mean, I'm sure there will be
other people who could help you in this room.
So I'll be talking about high-performance low-rank Schur complement for the Helmholtz equation. Here's my outline for this afternoon.
I'll start with some motivation and then I have one slide for the seismic imaging application.
I'll talk about one-sided matrix factorization, which is the core kernel to
solve this application.
Another way of solving it is also to make an approximation, try to approximate
those Schur complement, and I'll be introducing here or
discussing, describing some of the latest work we've done in this K-blast
library at KAUST and basically what's next. So without further delay,
so we, you know, as I said, we have lots of experience in and expertise in dense linear algebra and we apply those low-rank approximation
in those problem coming from covariance matrix problem.
So those are problem where they basically generate a matrix, a covariance matrix, which
explain the different interaction between, you know, particle, for instance, and the matrix is dense, right?
Initially the matrix is dense, but it has some low-rank structure that you would like to exploit.
So we've been pretty successful here in doing this in the context of climate and weather
application and we'd like to take those, you know, those idea and those
implementation that we made for such problem and try to extend it for seismic. And seismic, so we know more in dense linear algebra
per se, so we're talking about, you know, sparse linear algebra here. So either direct or
iterative solvers in the case, you know, if you want to do preconditioning.
So if you want to do, if your matrix is symmetric or non-symmetric, you will use those factorization here.
In both cases, you have to do some nested dissection,
where you basically try to separate the different, you know, contributions.
And you do some ordering internally to expose the low-rankness of your matrix.
And so in the case, if you want to exploit the spatial geometry,
you will do some Morton ordering. And if you want to do a purely algebraic solver,
you will use some graph partitioning tool. So the state-of-the-art when it comes to sparse solvers,
you know, there are mostly two families there, multifrontal and supernodal methods.
Mostly MEMS and sweet-sparse for multifrontal. And for supernodal, you have super-LU and past-X.
So they all have a tree structure. Okay, they all have a tree structure in trying to solve,
you know, this problem. And depending on how they traverse that tree,
whether it's left or right looking,
you basically falling into multifrontal or supernodal method.
So for multifrontal, you have some fronts to assemble until you reach your, you know, first separator.
Or you have nodes for, you know, for supernodal methods.
So you have two levels of parallelism for those two different categories.
Subtrees, thanks to your nested dissection.
So you have trees, subtrees, which are independent, which can be processed concurrently.
And you have also parallelism happening within a front, within one node, the single node.
And depending if you are doing direct or iterative method,
so if you're doing direct method, for instance,
you will set an accuracy. Your problem requires such accuracy.
And then you will solve all the way with that accuracy in mind,
making sure you maintain that accuracy throughout your computation.
If you are in the mode of preconditioning, right,
so there you will do some truncation. You will have fixed ranks.
Okay, so you will fix some ranks.
And you will have, you know, you basically have your blocks truncated up to that rank that you are looking for.
And of course, then at the end, when you reach, you know, at each level, in fact, of your tree,
and in particular, when you reach your first node,
you have to solve those dense Schur complements.
Okay, at each level of your tree, and in particular, at your last level.
And this is where we really focus.
So this is where we try to accelerate as much as we can that operation here,
so that we can, you know, come into the picture of those sparse linear algebra libraries.
So this is the application.
So seismic imaging, the idea is to come up with an X-ray of the subsurface
by solving this Helmholtz equation that is, I guess, familiar to most of you here.
So I won't spend too much time, but, you know, we try to basically solve it
in the case of sparse direct solvers.
So the way we want to do this, you know, you usually factorize your matrix.
Okay, so you have assembled your different, you know, fronts,
and once you reach, you know, the root node of your factorization,
you basically need to factorize that matrix and provide a full factorization.
So if the matrix is symmetric, you would use this LDLT factorization.
If the matrix is non-symmetric, you will use this LU factorization.
So they are the same in the sense that today, those sparse linear algebra, you know, libraries,
you know, they will use what we call block algorithm.
Like, you know, this is the, what in LAPAC, this is the legacy, basically,
a paradigm within LAPAC.
And of course, if they do it in distributed memory, they will use ScalaPAC here.
But essentially, you know, you have those final and update sequence,
and those sequence are done successively, okay,
and, you know, what happens is you don't have too much parallelism within the panel, okay.
Most of the parallelism occur within this update, you know, phase of the matrix,
and basically, you know, most of the threads are utilizing that phase here.
So what happens is you have this fork-and-join model, okay.
So, you know, this is something that does not scale for, you know, moving,
looking at, you know, large systems with a huge number of resources.
This fork-and-join model has, you know, inherently this bulk synchronous programming model,
and, you know, that is a problem with this.
So, with this block algorithm.
Of course, we looked at this plasma, you know, library, like, almost a decade ago,
trying to further expose much more parallelism during that factorization,
but what we call a tile algorithm, redesigning those block algorithms
instead into, you know, a tile algorithm, so processing the matrix into tiles,
and, you know, having this fine-grained computation allows you to expose much more parallelism, all right.
So that's the state of the art when it comes to doing, you know, dense linear algebra
within, you know, the sparse linear algebra family.
All right, so this is if you were to not consider any special structure on your matrix, okay.
So you only assume your matrix is dense, fully dense, and you sort of do brute force.
You factorize your matrix as is.
What happens, it turns out that some of those matrices, in particular for seismic imaging,
in those short complement calculations, those matrices can be, you know, can be approximated.
Some of the off-diagonal blocks, you know, have some low-rank properties.
So what essentially I'm trying to tell you here is those dense tiles initially can be approximated
by an outer product of two tall and skinny matrices, okay.
And this is an accuracy that you would, you know, set up from the application point of view,
or, you know, here on the left side, in fact, I'm showing two modes of operation.
On the left side, this is where you are in the preconditioning mode,
where you will use fixed rank across, you know, across all your blocks,
so that you can go as fast as possible.
And as a preconditioner, that's what you are really looking at, okay.
And on the right side, this is where you do direct solve,
and this is where you use fixed accuracy, and this is dependent on the application.
All right, so the question is how you approximate this small off-diagonal dense tiles, right.
They have some low-rank property, but how do you approximate them?
So the way we approximate them, we use this in-house library called stars-h.
And the idea behind this library is to try to approximate those dense blocks as fast as possible.
And we use for this three different kernels.
We experiment, or we assess the performance of three different methods to approximate those blocks.
You know, this divide-and-conquer SVD, rank-revealing QR,
and this randomized SVD from Gunnar Martinsson methodology.
And if we do that, we look at performance on approximating each of those off-diagonal blocks.
So we have matrix sizes here, and we have time in seconds.
The first one that I'm looking at is this SVD divide-and-conquer.
And what happens is, you know, it's pretty slow, it's very slow to compress,
and not only that, it does not scale, okay.
It does not scale across those 28 cores of Broadwell system.
If I look at, you know, this rank-revealing QR, I get much faster, you know, in terms of time, you know, to compress.
However, I still have the same problem.
I'm not scaling across all cores.
This is mostly because, you know, I'm saturating the bandwidth,
and basically I'm not able to, you know, outperform, you know, getting linear speed up here.
If I look at this third randomized SVD methodology to approximate the matrix, you know, it does scale pretty well.
And in terms of performance, compared to the other, you know, other methodology,
in fact, I'm getting a factor of 2, at least, for the matrix size that I'm looking at here.
So I do have scalability, I'm much faster than the other two methods,
so this is, you know, sort of a way to go to compress those blocks.
The problem is, time-to-solution is great, right?
But at the end of the day, you really want to check how much of the hardware you are utilizing.
So what we do here, we plot, you know, the theoretical peak performance of the system,
depending whether I'm using, you know, 7-core, 14-core, meaning one socket,
or 28-core, the overall system, I'm using two sockets.
What happened here is I'm really running extremely low, okay?
I'm running extremely low, I'm not able to extract performance out of that chip, okay?
And that's a problem, and that's a problem,
and I'll be discussing why here, in my next slides.
So I'm looking here at the heat maps, okay?
I'm looking at the heat maps.
So this is basically, you know, size of the blocks, alright?
And this is accuracy.
How much accuracy I want to have in those off-diagonal blocks, okay?
So, and this is basically doing it on this 3D helmet, with n equals 32,
and I have 10 grid points per wavelength on this unit cube domain.
So what is happening here, this frequency depends on the number of mesh points, okay,
that I have in each direction.
So what happened here is, so the, you know, for 512, for instance,
you know, for a block size of 512, and an approximation or an accuracy of 10 to the power of minus 14,
my rank is 200, okay?
So it's a good saving compared to initial, you know, dense blocks, okay?
So I'll be able to only calculate or operate on ranks, which is 200,
so that is a huge saving in terms of memory and in terms of complexity as well.
But, you know, it gets even more, you know, nicer when I move to single precision accuracy,
which is really the case for those seismic imaging.
You know, I'm able to go up to, you know, 100 in terms of rank size.
So this is great, okay?
And if I increase now my number of mesh points, 64, I do have the same behavior.
So the matrix, the short complement is larger, is bigger or larger to solve,
and, you know, at the level of matrix single precision, you know,
I'm getting one-fourth of the total tile in terms of ranks.
So this is good, and this is even better if I increase further my number of mesh points,
I'm getting around, you know, 400 or so for the ranks.
So the main problem when it comes to performance, you know,
if you recall the bad performance that I was getting is, you know, I'm dealing with small ranks, okay?
So here, even though I was mentioning single precision,
but as soon as you try to get even lower, you know, lower precision,
you can go, you know, very small in terms of ranks, okay?
And the problem is that today, if you want to do blast operation,
if you recall the talk this afternoon, the machine learning talk, right,
where he had issues getting performance because he was operating on small blocks.
He was doing those gems on small blocks,
and it turns out that the software ecosystem when it comes to blast,
from each vendor, they don't support, you know, such small rank sizes.
They're not able, basically, to give you good performance, you know,
if you were to run small blast operation on their hardware, okay?
So there is this effort, like, almost a year now, being led by Jack Dongara from UTK,
in basically renovating or revisiting the legacy blast,
so that they can perform, you know, give you much better performance on those small granularity.
And this is called the batch blast effort.
So at KAUST, we have this K-blast library, which tries to handle, you know, those cases, extreme cases,
and this is how, you know, we are able to get, you know, good performance.
So if I took into, you know, a little bit about K-blast, you know, this is very disruptive, okay?
This is very disruptive because, again, we don't have support from vendors.
You're by yourself.
So you get to come up with a good way of doing it, and, you know,
very disruptive because we're dealing with very small sizes.
So we need to basically able to concurrently or simultaneously run a huge batch of, you know,
a blast operation simultaneously, so that we increase our occupancy,
whether we're running on the GPU.
And, in fact, not only that, we try to get performance out of the GPU or the, you know, the Intel K&L
by removing all those overhead due to the API call, okay?
We don't get performance today, for instance, on MKL, DGEM, if you were to run 32x32,
mostly because MKL, under the hood, check for many parameters, okay?
Check for, you know, if your metrics are correct, if it has to initialize, you know, some memory buffer internally.
So there are many overheads which do not forgive you at this small scale, okay?
So those batch blasts basically remove all this out of the picture
and try to, you know, schedule a lightweight version of those small kernels
and many of them all together, so that you have high occupancy on your hardware that you target.
On top of this, in kblast, we use recursive formulation.
It's not enough to run 32x32, okay?
You really try to redesign your algorithm so that you occupy your, you know,
highest level in your, you know, memory subsystem.
Basically, you try to run at the register level.
So you have to do, you know, micro-blocking, if you will,
so that you stay as much as possible at the level of the registers.
And, you know, for that, we need to minimize data transfer, enhance locality,
and, of course, increase arithmetic intensity, even though the block is very small.
And as I said, again, you know, the start-of-the-earth implementation,
they're not well optimized for the scope, for the small size, or they're not supported at all.
I'm getting there.
So those are the batch blasts, you know, that we currently support within kblast.
And kblast is open source.
It's fully available for download on GitHub.
And what we have to do here, we have to implement what we call those batch blasts, okay?
And those batch blasts, you know, for instance, here doing this Cholesky factorization,
they have two levels of batch, you know, or nested parallelism happening.
You schedule many of those Cholesky factorization, you know, at the same time.
And internally, within each Cholesky factorization, you also have some batch, you know, scheduling happening.
And this is represented by this dimension here, okay?
And, of course, by having this recursive formulation, you're basically, you know, running many, many matrix multiplication.
Some performance here on single GPU and multiple GPU for those, you know, critical kernel used for the short complement.
And we compare against, you know, the available implementation from, you know, kblast or MKL or Magma.
And for the small scope, you know, for the scope of the small sizes that we're talking about,
we do have higher performance thanks to this recursive implementation and, you know,
trying to block and leave at the level of the registers.
And performance linearly scale as you increase, you know, the number of GPU here.
If you plug in those TRSM and TRMM in the higher level, you know, linear algebra like Cholesky or the solve of the Cholesky,
you do get even much more benefit compared to other implementation.
And here is, you know, the first sort of, you know, short complement in a batch mode, okay?
So it's the first time we, there is no such operation existing out there.
So we implemented this batch of complement so that we can operate at each level of the tree traversal that we are having when doing those multi-frontal or supermodal libraries.
And as you increase basically the width of your panel, you get much, much higher performance on this Pascal GPUs up to 1 teraflop here for 128.
All right, so what's next?
So this is, you know, if you put all together the story that I mentioned, okay?
So HECMA, this is the library or the flagship, you know, project that we have at KAUST, at the Extreme Computing Research Center.
So this is the library.
This library require this H-core.
This is essentially where you would call those batch, you know, blast operation.
Internally, it depends on the star's H.
This is the library which, in fact, approximate the matrix.
So the matrix is approximated and then you operate on it.
And to do that, you rely on this K-blast library which is able to provide high-performance numerical kernels.
And basically, that's more or less it.
So the gray part are the part that we don't cover and we basically rely on the system to have them already installed.
Some future work.
There are a lot to do here.
It's very disruptive because we don't have yet support from the vendors.
Because, you know, from a runtime perspective, right now, scheduling those small tasks, right,
which are extremely low arithmetic intensity, it's extremely challenging.
Simply because, you know, runtimes have their own overhead and, you know, by scheduling basically low arithmetic intensity kernel,
they are not able to remove that overhead for the scheduling.
So there are lots of research to be conducted there.
Of course, there are many people looking into it and this is great.
So we'll be able to compare against them.
And, you know, I'll finish with this slide.
So I would like to thank the collaborators, students, and vendors.
And that's it.
Thank you very much, Hathem.
We have time for one or two questions.
No questions?
So I have one.
Today, your implementation is running on CPU and GPU, both systems?
Correct.
And did you test that on the overall Helmholtz wave equation because what you have shown is small test case?
That's right.
What are the limits today of the implementation?
So, I mean, yes, that's right.
We have not run on much larger mesh sizes.
I think the main problem would be from a runtime perspective.
So I think we have the core kernels to being able to run those small, you know, simultaneous blast operations on small data.
However, we don't have a runtime support.
So the runtime to schedule those different tasks are not yet being exposed to such low arithmetic intensity kernels.
And they have a hard time to cope with that.
And the Helmholtz equation you've shown here is a finite difference implementation?
Yes.
Second order in space?
So it's second order in space.
Yeah, it's standard finite difference.
How is it sensitive to higher order finite difference?
We have not yet looked at it.
Any more questions?
Thank you very much.
Thank you.

