Reactive Systems and Microservices: Michael Mahoney

Reactive Systems and Microservices: Michael Mahoney

Recording: Reactive Systems and Microservices: Michael Mahoney

. So as I said, I'll tell you about some recent work we've been doing on doing certain types of matrix algorithms at large scale. And by large scale, I mean terabyte size and up. And so I think there's a couple ways you can think about this. One is you like to do stuff in Hadoop or Spark or whatever, and you do the usual things, which are not sophisticated matrix computations, quark matrix computations, meaning you might do a few iterations of a power method. But in terms of the actual computations, that's not so different than counts or joins or something. And so if you know QR decompositions, think QR decompositions are much more sort of complicated computations. And so we'll get to that

So you do those sorts of computations and you want to do more complicated stuff. And so when you do more complicated stuff, things get worse and start to break. And so we figured out where things broke and then how to fix it and have a good sense of the trade-off space there. A different way you might be thinking about this, which is probably less for the people in this room, but a lot of the people I talk to, they do sort of machine learning. And a lot of machine learning is sort of small scale machine learning. Meaning you have something and you have a new method and you find some data set and show that it works. And the data set's not too large, certainly not at this scale. And likely it wouldn't scale up to this scale

And so the question is, what fraction of these sort of machine learning algorithms that get published at machine learning venues, NIPs or ICML or whatever, would scale up the terabyte scale? And so that's a fair question. And so one of the sort of elephants in the room is going to be that what sort of level of rigor do you want on the computations? Sometimes you need an answer that is just sort of vaguely right. A few steps of an iteration sort of gets you moving in roughly the right direction. And that's good enough. And there's a lot of applications where that's good enough. And think of internet or social media. You want a ranking function. You want to get the top few things

And if you get a few other bad things and you miss a few things, it's not the end of the world. There's other computations where you want to be sort of quote exactly right, machine precision, a much higher quality algorithm. And for those, the trade-off space is very different. So a lot of machine learning now is something called stochastic gradient descent, which gives you sort of low quality approximations. And sometimes, ironically, the fact that it's low quality is actually a good thing, because the objective that you're fitting to is something you pulled out of there anyway. It's not perfectly correlated with what you want. So all these are themes that are going to be going on in the back end of what we'll talk about. And the question we want to ask is, can you take certain just very basic types of matrix algorithms, low rank approximations, if you know what those are, and do them at terabyte scale? And one of the criteria is we want to solve someone's problem

Meaning if doing this isn't going to solve a problem for social media and internet advertising, we don't want to do it. So find someone who has a problem. And so we have examples of that. And so I'll describe that. What I wanted to do is start out with some general thoughts. And the general thoughts will have to do with that. What are the types of computations you might want to run? That might seem sort of a little high level. But I think I wanted to set the stage a little bit because depending on your background, certain things are just very obvious

And if you had a different background, they would be completely non-obvious. And if you're a machine learner, a statistician, a computer scientist, and I say you want to have an algorithm that's good in some sense, you're going to think good means very different things. And if you're in certain applications, it means very different things. So I want to start off with some general thoughts. And that's going to get right to the heart of what we're talking about because the types of matrix computations we'll be talking about have been used in certain areas. They have a lot to add to what's going on in large scale machine learning, but you need to ask slightly different questions. And so then I'll talk about linear algebra and spark. For a certain class of problems, and we'll be talking about scientific problems

Cx and Cur, PCA and SVD are certain low rank matrix approximations. So get them working at terabytes scale and up. Talk about some applications to a number of different science problems, mass spec imaging and some stuff. And I'll say why these sorts of things are of interest. And one is a sort of scientific question. I'm not going to spend as much time on that. One is given that this is a problem that these people want to solve, what are the trade-offs in doing the linear algebra at scale? And the answer is depending on the types of computations you want to run, you lose between 2 and 10 and 5 and 50 or whatever. So it's something which is from acceptable to probably not acceptable

And so if you're at this end of it, and this is at a given scale, we actually anti-scale. If you're at that end of it, what can you do? And so you have something called Alchemist, which is basically going to solve that in a certain way. And I'll talk about that. I probably won't have time to talk about the communication avoiding stuff at the end, but I'll just mention it. And it fits within this. And this is actually going to be something that we use in Alchemist in the next couple months. We have the communication avoiding stuff, but not the Alchemist piece of it. OK, so the elephant in the room is if you ask someone about big data is the phrase today, and they give you an answer, the answer probably reveals more about them and their background and how they happen to be trained than it does about the data

Right? And so you might say you'd be a computer scientist, and you just say, just I need fast algorithms. You might be a scientific computing or a high performance computing person. And you just say, geez, I need a bigger machine. If you're a statistician, you just say, geez, I need to posit a model. A machine learner might just say, just choose some regularization function and smooth it out. Data scientists might just say, geez, it's a mess. Clean it all up. And so can we get one step beyond this? Maybe to be blind, two blind men, rather than just one blind man groping at the elephant to understand what's going on

So there's a lot of perspectives you can adopt. And I think relevant in general, but relevant to what we'll be talking about, sort of the lead axis of variance, the 10,000 foot views the following. So this is a little less true now than it was 10 years ago, precisely because the forcing function of large scale data and fields are moving to try and couple computation with sort of principled statistical issues. The lead axis of variance is the following. And it's particular element because computer scientists build big stuff. And they think about the world one way, and everyone else thinks about the world in a different way. So computer scientists think of the data as a record of everything that happened. The data in front of you is sort of all there is, in the sense that the way problems are parameterized and goodness statements are made, thinks that there's no tomorrow

It's just the data in front of you. It's clicks in a click log. It's comments in a box. It's the purchases at a store. And the goal is to find patterns in the data, whatever that means. And you do that by running some computation. And computations of interest are typically intractable, in some sense of the word, in whatever model of data access you have. And so you get approximation algorithms

And status, everyone else, but it's sort of formalized in statistics, but everyone else thinks about the data not interesting in and of itself, but sort of as a snapshot of the world. As the data are so valuable because there are noisy snapshots into what's going on in the world. And so the goal is not to make claims about the data. It's to make claims about the world. And you look at the data to do that. And so basically, you want to extract information about the world, and you do that by positing some model. And you might write down some Bayesian model, whatever. Or you might just say, I know that the physical model behaves this way

And so you cook that implicitly into the computations you run. So this is a big difference. They're not necessarily inconsistent, but it's a big difference. I mean, if you're computing some things that are obviously useless, that's not so good. But typically, you compute something that's not so obviously useless. If you're running a computation that is going to take the age of the universe, what are you going to do? You just run it for an hour and stop. In which case, who knows what you computed. And so you really start from one perspective or the other and come at it

So I think you're seeing a convergence now relative to 10 or 15 years ago. But you still see a lot of remnants of this. And it's going to be important for various technical as well as cultural reasons we'll be talking about. So they're very different paradigms. And in particular, in statistics and natural sciences, in scientific computing. And I mentioned scientific computing because a lot of linear algebra historically, it's used now in machine learning, but it's been developed in very, very mature ways in scientific computing. So scientific computing, the study of computation per se is secondary. You use computation, but it's secondary

And so in particular, it's sort of an axiom that it only makes sense to study algorithms for well-posed problems. So a well-posed problem is one whose solution exists and is unique and is robust to model parameters. So think. Do you want to be computing on problems that the solution doesn't exist or isn't unique or isn't robust? So computer scientists, it's easier to study computation per se in discrete settings. So complexity theory in algorithms is formulated that way, which means if you have a model that has vectors that are in a Euclidean space, so machine learners do, there's a bit of a disconnect. The theory of algorithms really divorces computation from the data. You make statements about algorithms, and there's no statement about the data. It's really very much secondary

So you run a fast algorithm and sort of later ask what it means. So what's an example of a ill-posed problem that a computer scientist might want to solve or that you might want to solve? A problem that's not robust is a minor tweak. What's the least significant digit of your bank account? Hopefully you have, whatever, $110,812.06. And if I write you a check for $100, what do you want to have happen when you deposit that check? You want to go and have the bank increment your total in your bank account by eight digits and get them all right. You're not going to be happy if the bank says, well, it's a noisy world, and round it down to $100,000. I mean, you laugh. But databases and infrastructures that computer scientists develop think about the world very discreetly in certain things. And machine learners and statisticians and everyone else that wants to do inference wants to be robust to those sorts of things

So there's a big sort of mismatch there. And that's going to manifest itself in a lot of ways that we're going to be talking about. So when we want to do matrix computations at scale, what do we compare ourselves to? And do we compare ourselves to scientific computers who have one metric of goodness or statisticians or computer scientists? So this is sort of going to be underneath the hood. So I want to spend a couple of slides talking about a slightly more mature example of a scientific application. So this is not stuff we did at terabyte scale. This is still the sort of background. This is stuff from about eight or 10 years ago. But the problems we'll be asking now are at larger scale, but it's of a similar flavor

And think this is not suggesting friends on Facebook. And this is, so the details of the problems we'll be talking about at terabyte scale are different. But this is a much more mature area. So this will give you an example of the types of questions we'll be asking now in the future. OK, so as opposed to just making a prediction and being roughly right, a different type of application where you see large scale data is the following. So in genetics. So genetics, everyone, if you're a human, has the human genome. It's six billion base pairs

It's different than a sea urchin. In fact, there's no the human genome. You know, everyone has a slightly different genome. And there's lots of ways you can be different. If you're a geneticist, you know there's transpositions and translocations and insertions and deletions and lots of different things. Relevant for large scale data, the most common way people can be different is something called a single nucleotide polymorphism, so a SNP. is a single location in the DNA where some non-negligible fraction of people have one nucleotide or a different nucleotide. So in most cases, everyone has an A at this spot

But you know, some spots, some 12% and 88%, depending on the population you look at, has an A or a G. And so these are single nucleotide polymorphisms. And you can imagine this is of interest for a range of reasons. You want to understand population demographics and history and so on is one reason. Personalized medicine is a different reason. So there's a range of reasons why you might want this. And so to oversimplify a rather involved story, you can imagine constructing a term document matrix from this, right? Where the documents are people and the SNPs are terms. And so you encode this information in some way

So the density properties and things are different. But you know, it's things and features describing those things. So this is just to show you that someone went out and generated the data. Someone had to go to Siberia and get a blood sample in order to type those SNPs. And someone else had to go to the South Pacific. And so these are what graduate students spend their time doing. And so the particular data set. So HapMap, if you're familiar with that, is roughly 400 people by order million SNPs

So I said there's six billion base pairs. Ballpark, one in 1,000 base pairs are SNPs. So you're talking order million. The data we're going to be looking at it later on the bottom right is 2,000 people by 400,000 SNPs. So a slightly different data set. That's actually large scale data. So it's not large scale in the sense of terabytes. And so if you just say big is big

But this is fairly large. At the time, this was sort of state of the art. And so it's large by a genetic standard. But it's also large in the sense that computations start to become non-trivial. You can't just call with one line some QR code or some SVD code at that size. Maybe now on this machine you can, but eight years ago you couldn't. And so it's not huge or big like the elephant. But it's at least large by very reasonable standards

All right. So I have this matrix of data. And what are you going to do with it? So a common thing is to do something like the following. And a huge fraction of machine learning boils down to some variant of this. And this is a low rank approximation. I look at the 2,000 people. I look at the 400,000 SNPs. And I say give me the top two eigenvectors

And so after you do a whole lot of preprocessing, you get a picture that looks like this. So you see Africa, Middle East, Europe. And then on the bottom right, America means Native American Indians, and East Asia. So you sort of see Eurasia, but then you get some funny stuff like Mexicans in there and so on. So what's going on with this? And I say what's going on with this because what the geneticist wants to do is poke around with the data and understand what's going on in the data. And they're using a tool, in this case, something called principal components analysis that computes these eigenvectors. And they are trying to understand what's going on in the data and use these sort of algorithms as experimental probes to poke the data. So what's going on with the Mexicans? So they seem sort of out of place, right there in the middle of the Americas

And the answer is that visualizing data is good, but it comes with artifacts. And one artifact is that this is a two-dimensional surface, not a three-dimensional surface. If instead of plotting the top two eigenvectors, you plot the top three, you get this. So you see Africa, Middle East, Eurasia, East Asia, Oceania, Native American Indians down at the bottom. And if you know about human history, and if you don't, it's very believable that Mexicans are some sort of a mixing between Native American Indians and Europeans. And so what you see is out popping along the third dimension. So this is visual support for the so-called out-of-Africa hypothesis. This is something that 10 years ago, if you put in a computer science venue and said, see, my method found this, that computer science would love it because it'd say, see, it worked

No geneticist would say, yeah, we know that. What else can you do for me? So this is visual support for the out-of-Africa hypothesis. This is good as a sanity check. The geneticist wants to probe a little bit more interactively. So it's very different than the type of analytics you'd do in certain settings. This is good. It's not altogether satisfactory, though. And there's two reasons

This is going to get to the heart of what we're going to talk about. One is that we computed the top three eigenvectors of principal components in PCA. What are these principal components? are linear combinations of 2,000 people or linear combinations of 400,000 SNPs. They're a well-defined mathematical thing, but they don't mean anything in terms of the genetics. You can't go assay a type, a linear combination of 400,000 SNPs. When you go to the doctor, you're not interested in what a linear combination of 2,000 people do. You're interested in one particular person. So one issue is that this is reification

You don't want to just do prediction, push an ad on people or predict a movie. I want to understand something about the data in terms of the processes generating the data. And in areas where you know a lot more about the processes generating the data, and as a proxy for that thinks these sort of scientific applications, but in other areas. And as you get more sophisticated user modeling and internet and social media applications, you're actually starting to see some things like this. You want to understand and try and interpret the data and interpret the output of algorithms. The second is a running time issue. So let me go into a little bit more detail. So the second bullet on the bottom, selecting columns

So the PCA gives you optimal linear combinations of columns in a certain sense. And this is something that's totally textbook. But you could ask, say, I want to get the best k columns, the best three columns. And best is intractable by any notion of best, any interesting notion of best. So theorem, you can get an approximation algorithm. You can relax best. You can ask for an epsilon approximation. You know, all these are the usual trade offs that you do in computer science

And you can get approximations to the best. And they take a certain length of time. We'll get to that. The other is running time. Computing these SVDs. So we're talking large SVD and PCA, think of as the same. So computing large SVD or print PCAs. So these numbers are a little stale

But in commodity hardware, using the version of MATLAB, it took 2,000 by 400,000. It took 20 minutes. So you can go out for coffee and come back, right? But you don't want to run it once. You want to run 1,000 times because you're doing a cross-validation experiment. Then you cross-validate, and you see that there's a slight difference between something, but you realize you forgot to normalize something properly, so you've got to do it again tomorrow. So you iterate that process. So it's expensive in a very reasonable sense of the word. It's not a one-liner

If you want easy development, you can't just say, call PCA at that scale. And so you've got to start to think about, do you multiply this matrix before that one, or vice versa. So we're not even terabyte scaling. You're starting to worry about these sorts of issues in terms of user-friendliness. As a technical point, you're going to actually compute the SVD of AA transpose. Historically, numerical analysts and people in scientific computing would freak if you tried to do that, because it would blow up a condition number. But if you want two, or 10, or 100 eigenvectors, you wash out the bottom part of the spectrum. That may be perfectly acceptable

So that's actually what's done here. All right? So running time and sort of understanding the data is what we're going to do. So we ran these computations. We want to get larger. And a question that we're going to have to deal with is where are we going to run these computations? So there's the 99% and the 1%. And let's split the 1% into two half percents. So the 99% is going to run it here. If you go out and buy something yesterday and get a lot of memory, this thing has a terabyte of data

So this actually, you can get pretty large. It's actually hard to find a problem out there that solves someone's problem if you want to run PCA on 10x this, on 10 terabytes of data. We've done it. But it takes a bit of effort. If you want to run the computation, you can. But if you want to run the computation and solve someone's problem, it takes a bit of effort. So I mean, the 99%, you can get pretty large. So if you're going to get larger, there's sort of two camps

And one camp says I'm computer scientist. I do distributed data centers. And another camp is scientific computing. And I want to have a supercomputer, roughly. So supercomputers are very high end, computer intensive, think numerical simulations. Big emphasis on HPC, high performance computing. And you do stuff in C and MPI and very sort of low level there. Distributed data centers, you want to have a model, an abstraction, and you're going to pay a price for an abstraction, but an abstraction

Typically data intensive. If you do three steps of a power method, if you do a select, if you do a join, if you do these sort of database operations, they're not put, I mean, a join. You go in and you join two things. You count. So these are not computationally sophisticated things. They might be non-trivial to do at scale. They might be non-trivial to pace together, but they're not in terms of communication. But they're not computationally

So data intensive. Big emphasis on, let's say, HPC, where you want high productivity computing. You're willing to sacrifice performance for productivity. And so this is the land of databases and MapReduce and Spark and so on. And so we want to do linear algebra at scale because of do machine learning and data analysis problems. As a use case, we're going to do something like genetics and scientific applications. And the question is, how do we judge ourselves? Do you judge yourself by some algorithm thing that computer scientists think about where they're talking about the data today? Do I want to parameterize problems where it's good for tomorrow? If I lose a factor of 1,000 in an abstraction of databases, that might be too much. But I can get that down to a factor of two

That's maybe not so bad. So this is what we're going to want to address. So Spark's architecture. So how many people know about Spark or Hadoop or something? How many people know about Spark? All right. So how many people know about MapReduce and Hadoop and something? OK. So MapReduce was something that solved the problem Google had in 2002 or so. And in 2005, some number of years later, they released it. And it's one of these things that was controversial

Some people loved it and some people hated it. And it was sort of a complicated landscape. I was watching that because we were doing sort of mathy stuff, some theory of algorithms and statistical theory, machine learning. And it's one of these things you just think, what are you talking about? People are arguing past each other. And so I wasn't directly involved, but watched it. And MapReduce has a relatively simple computational model. If you ask, where does MapReduce not perform well? The answer is going to be on iterative algorithms. And it's because you do a Map and a Reduce and you don't know where stuff's stored, so you're constantly writing stuff

Why do iterative algorithms matter here? So if you're doing linear algebra, you're either dense, in which case it's matrix vector multiplies in one form or another, or you're sparse. And if you're sparse, you don't densify. You do sparse stuff. And the canonical example of sparse things is iterative algorithms. So conjugate gradient and these sorts of things, although you could do that in a dense case too. So roughly, Spark is MapReduce++ in such a way that you keep states so you do iterative algorithms better. So question, does that mean we can do linear algebra? And so I came onto the scene several years ago, and we were talking about this. And we had these matrix algorithms

We're trying to scale them up in scientific applications. And the question is where? And you talk to people on one side of the fence, they say do it on our supercomputer, because those guys are terrible, and then you'll get great performance here. You talk to people on the other side of the fence, you'll say do it here. You can get great performance. How can things not go wrong? It's a distributed data system. Don't talk to them. It's too complicated. And so this is a progress report to say we finally feel like we get a pretty good sense of the landscape, and it's a little bit more textured than that

So Spark is a data parallel programming model. The RDD, the resilient distributed data set, is sort of the basic thing. Think of a distributed array type. RDDs can be cached in memory between iterations. So this is the state that Spark keeps that allows you to do iterative albums better. You can write an RDD down, you can keep it in memory, and go from one iteration to the next, and keep the data at the same spot. So you have a driver. The driver forms a DAG, the directly acyclic graph that governs the computation

And it schedules tasks on executors, and the executors do stuff. So there's a communication and there's a computation. And the communication is going to be the issue. I think computation is going to be relatively inexpensive. So communication is the issue. The computation is going to operate on one RDD to perform another. So think of it as a sort of functional thing. You have a thing, there's a step, you get another thing

So no inference there. It's just input, output, and there's some sort of functional relationship. The computation will take one RDD and produce another RDD. The overall job is broken into stages. And each stage is broken into a bunch of parallel independent tasks. So a bunch of stages, each stage is parallel tasks. Where does the communication happen? The communication happens between stages. So you have a bunch of stuff happening at this stage, but they don't talk

You have communication between the stages. So you can imagine that if your computation is relatively straightforward in terms of dependencies, that may be fine. You do a bunch of independent things at each stage, resync, iterate that process. You can imagine that if you have a sort of a complicated dependency structure in terms of communication, that might not be so good. So if you're familiar with QR, which is sort of a standard algorithm that results in linear algebra, QR gives you some triangular structure. And so the R has one non-zero in one column, and two on the next, and three on the next, and four on the next. And so you get a much more complicated communication pattern to compute that. And that's going to be expensive

So when I say we're going to do sort of non-trivial linear algebra at scale, what we want to do in the problems we're choosing is choose algorithms that sort of are good and bad with respect to particular methods. Some of the algorithms are going to have very straightforward communication patterns. And you would hope, and it's going to turn out to be the case, that you lose very little by doing this stuff in Spark. Stuff that has more non-trivial communication patterns, you might expect. And it'll turn out to be the case that we're going to lose a lot more. All right. So given all this, why do this in Spark? Why do any algorithm in Spark? is Hadoop++, and Hadoop is MapReduce, and that was designed to solve something. And I've already told you you can get in Google way back when, I've already told you you can get a lot of data on one machine

So why do it? So pros. So it's widely used. There is a, what do you call it, an ecosystem effect here. It's relatively easy to use for non-experts. I say that because I wouldn't say it's easy at this point, but it's compared to MPI or compared to assembly code. It's easy. There's a big ecosystem that you can use before and after. So the pain point for a lot of applications is not the particular linear algebra computation, or even the particular machine learning computation

But there's a whole, you know, you parse, and you do this, and you do that. There's a whole pipeline here. Spark can take advantage of single machine linear algebra codes. So you're going to have your data stored. However, if you're on a given machine, you can put low quality linear algebra codes in that machine, and you can put high quality linear algebra codes in that machine. There's a communication between machines, but when you're on one machine, you can take advantage of existing single machine codes. So think the LAPAC or Elemental or something like this. You have fault tolerance and a range of other things

So there's a bunch of pros. Cons. So classical MPI based linear algebra routines are just faster and more efficient. So if a factor of two matters, you shouldn't be doing this. And there are scientific computing applications, where a factor of two is the difference between a year and two years. And so if you do that, you go with MPI. I think it's easy to say we're just going to, I mean, I think one of the biification points here is that if you, on one side of the fence, you say this stuff sort of, I want performance and convenience. And by the way, I don't understand all that stuff, so I'm not going to do it

On the other side of the fence, you say, geez, it's convenient to say I really want to squeeze that last little factor of 1.1 out of my computation, even if I have to spend months doing it. And it's a convenient metric to fall back on. And so we're looking at something in between these two. But if you're just into performance, there's a layer here where we're going to have a spark. And you shouldn't have that if you're interested in that. There's no way currently to leverage legacy parallel linear algebra codes. There's been a lot of work done over the years on parallel linear algebra. Not a way currently

That's not to say in a couple of years it won't be, just not currently. There's a bunch of little gotchas like JBM size restrictions that are good to know about that I'm not going to go into much detail about. And so that may be solved, but there's a bunch of these sort of gotchas. All right. So what do we want to do here? I'll give you sort of a report card. And here's sort of what we're trying to do. So we want to get implementations of low rank factorization. So there's going to be PCA, which is just vanilla principal components analysis

NMF, which is a certain type of non-negative factorization. And randomized CX or CUR, which is basically the way to choose these good columns. So PCA is a well-defined thing. You have a matrix, there is a PCA. NMF is not a well-defined thing. NMF refers to one of 50 different algorithms, all of which computes something non-negative. So if I say NMF, you should raise your hand and say, what version of NMF are you computing? We're actually going to work with a relatively simple version of NMF. Other versions of NMF will have more complicated communication patterns that will look more like the PCA

So we're going to work with a relatively simple one for that reason. Not that it's good for other reasons, but it'll stress test the linear algebra in the right ways. If we worked with a more complicated version of NMF, we would have communication that looked like PCA. So the bottleneck is PCA is going to have the more complicated communication patterns. The version of NMF we're going to work with is going to be a tall, and I'm not asking anything that should be very simple in terms of communication. Randomize CX and CY are sort of in between the two. The bottlenecks of matrix vector multiply, but it's a matrix vector multiply with a particularly nice vector. This is one of these randomized linear algebra algorithms

And so it's a multiply with a random matrix. And so that's what it has is relatively nice. We want to apply these to these low rank factorizations on terabyte size data. Scientific data, we want to do it in Spark. We want to understand Spark performance in a couple ways. One is going to be commodity clusters versus HPC platforms. Figure out these two sides of the fence, talk past each other, what's actually going on. So we want to get a comparison there

We want to quantify the scalability gaps between C and MPI and well-tuned Spark-based implementations. And we're going to want to provide a general purpose interface between Spark and traditional MPI codes, basically, to do numerically intensive sort of machine learning at scale. So a lot of this work is with a bunch of people. A postdoc of mine, Alex Skittins, did the lion's share of the work and sort of led the charge. But this is a collaboration with a couple of people. So I'm at Berkeley. I'm in the AMP lab, among other places, at Berkeley. So AMP lab develops Spark and a bunch of other things

And so how do these machine learning algorithms and the matrix algorithms perform there? Lawrence Berkeley Lab is up the hill. They have lots of different types of scientific data, and also scientific computing expertise. And they wanted to know how does Spark work for data center workflows that arise in science. And so think the genetics example. The products we have with MLS are much more mature than that. But think the genetics example. Those are the questions we're asking. And then Cray

is Cray, supercomputer Cray. How do they fit in the mix? So they're actually providing the machines for LBL. is nurse. is a subset of LBL. They're actually providing the machines for LBL. And they're getting customer demand. You say, why would Cray's customers be demanding Spark for their machines? And the answer is not everyone in the world wants to squeeze out that last little bit of performance. You might be in an environment where it just turns out to be easier to work with the existing supercomputers

But you want to take advantage of this broader ecosystem. And so you want to put Spark. So they're actually getting customer demand. And so they want to understand these trade-offs. All right. In terms of the applications, there was a couple of things you're interested in. One was climate science. And I'll describe in a little bit more detail what that is

But basically, that is simulated data. So on the HPC machine, you run a big, long computation. You generate gobs of data. And then you analyze it. And you tweak the conditions on the Earth. And you have a few more forest fires. You dump a bit more carbon dioxide in. And then how does this change? And so you run lots of these computations

And you get error bar estimates for various things. So that's simulated data. And so that's going to be very different than the other types of data. And for that, there's PCA, the low rank approximation. Nuclear physics, we wanted to look for a certain type of subatomic particles. There we were using NMF. PCA actually solved this problem. We were looking at NMF

It turns out that's not going to solve the particular problem they have. So think of this as we're interested in the scaling issues. But that's not going to solve the science problem. And mass spec, we have some published results at smaller scale and may scale it up. But there you're looking at the location of chemically important ions. So think I have a sample. I cut the sample up and send it through the machine. And certain hydrocarbons have slightly higher charge to mass ratio, whatever

And what does that suggest? And so if a cell is dividing and the time scale for the cell to divide is a bit longer, a bit shorter, you can imagine the hydrocarbons in the cell wall have a chance to work out kinks. And so what could rapidly dividing cells, namely hydrocarbons that haven't worked out the kinks, what could rapidly dividing cells be suggestive of? So you can imagine you go into the doctor's office, they take a biopsy, and they want to determine if you have cancer. All right. So this is sort of an example. You know, I want to get some sense of whether you have a disease. And so do very fine scale measurements of patients. So mass spec, you want to find that. All right

So the data sets, the resolutions isn't too good here. But the first one is the mass spec. That's going to be a terabyte. The size of that is 8 million by 100,000. Diabase in nuclear physics, it's a billion by 200. And then we're going to have two climate data sets that are a little bit different. One is 6 million by 50,000, that's two terabytes. And one is 20 or 30 million by 80,000

And that's going to be 16 terabytes. So that's the largest I'll be talking about today. We're looking at some other things that are a bit larger. That's the largest I'll be talking about today. So size scale, 1 to 16 terabytes. A couple different types of low rank computations. So the first thing to note is that all of these are very rectangular, actually. That plays well to the existing way Sparx implemented

If you want to get the lower dimensions a bit larger, and not be extremely sparse in terms of a matrix completion in terms of a recommendation system. If you wanted to get the smaller dimension large, then you'd have to do more complicated computations involving multiple machines on smaller size samples. And that's a whole other can of worms. So we're rectangular enough that we're not doing that here. OK. So we're going to want to compare EC2 with two HPC platforms. And then we're going to want a better understanding of Spark versus CNMPI scaling for PCA and NMF on the two HPC platforms. So we're going to take Spark, put it on EC2, put it on one supergaming, put it on another

How's it going to perform? It's out of the box. Where's it going to be faster? I'm running PCA. Give me 100 eigenvectors of this thing. So which of these environments is going to be faster, do you think? EC2 or your supercomputer? EC2. Why? OK. This is great. We have a disagreement. So the thing you've got to be careful of, it's not clear what a supercomputer is

Every supercomputer is designed and very tailored. And so just because you have something working here doesn't mean it works on the next one. That's a gotcha. OK. Let's say . So I have no idea how it performed there. And I actually have no idea because it's actually hard to know if you, we looked at two ones here. And it's hard to know how, I mean, if I knew all the specs, I could probably say something

But it's not immediately obvious how it ports because they're not commoditized. I mean, everyone's a little bit special. OK. So and we use H5 Spark to read dense matrices, so we're doing from the same data. We tried to, there's a few gotchas. This is a statement about the world, right? We had to go down. We took down the machine at LBL for a day last March. We ran this

You do your best job to take measurements in this and that. And you realize you didn't do something quite right. So there's a few gotchas. But so I think this is the fairest sort of state of the art evaluation of this. And so there's all these things that we tried to be as fair as possible in terms of MPI and Spark reading from the same source. OK. So platform comparisons. So out of the box, the first supercomputer we applied, it was a factor of 1,000 or something terrible

And I'll get to why. So a trivial reason, but it's not out of the box. OK. So randomized CXCUR. So bioimaging. So if you know what principal comments are, they give you a bunch of vectors. And those are vectors that are good for the column space that describe the data. Other vectors that are good for the column space are the actual columns of the matrix

And so I could pull out a slide deck from this machine and talk for three hours on the theory underlying this sort of stuff. So this is sort of a very principled way to get good columns. And to get these good columns, you need to compute certain things called leverage scores. And the bottleneck to computing those leverage scores is a random projection. And you can use that random projection for a low rank approximation or this thing. And so that's the bottleneck for both of these computations. And so just keep them in the back of your mind. I mention that because if you do random projections on one machine, you need to use one type of random projection because you're interested in flops

In both the distributed and the HPC environments, you had to spark other types of random projections are better because communication is the pain point. And so the theory would hold them both cases. But when you actually implement it, the computation versus communication trade-off, you get very different results. So we want to get a low rank approximation. There's the result. The bottleneck to this random projection is I want to do essentially a matrix analog of a power method, a few iterations of this. So this is something if you just take a textbook, you have a bunch of letters there. That's standard linear algebra if you're familiar with that

And there's sort of a right way and a wrong way to multiply. And we did it sort of the right way. And that's how it works on one machine. People that design linear algebra code design it so you don't have to think about it. There's a lot under the hood in terms of getting these things to work properly. One of the things is under the hood in a distributed data system, not a single machine, is there's a right way. But then you need to map it to actually computing the power iterations in Spark. We had to do it with a tree aggregate operation over an RDD

So there's a link for these slides are up on our web page also. So there's a link for some of the details. So we had to do a tree aggregate operation to get that done properly. So runtimes. So the first line is EC2. The second line is the first Cray, the XC40 that LBL is running, and the next one is an experimental Cray cluster. Out of the box, let me see what the no, do I have the DRAM, the, which one is this? The SD. So we're doing 70 iterations

And so the green is the computation. The red that you can see on some is loading metadata. The yellow is loading data. And then there's a bit of blue stuff that's post processing. So the 70 iterations, if we were doing 30 iterations, that green would be cut in half. Why 70 versus 30? No reason to think you should think that one's better than the other. But if you're designing the algorithm, that's something to keep in mind. The relevant piece here is that if you're doing one or two, meaning a very low precision sort of iterative algorithm, other stuff may dominate

But if you're doing a larger number that's common in applications, you want a finer approximation of the low rank space or whatever, you're going to need 10, 20, 70, 100. And there, to first order, these are all the same. Right? So the y-axis is time. It's not log scale or something. So maybe they're a factor of two different. But the first order, they're pretty similar, actually. We ran, do I have this here or not? There's a breakdown if you want the details. So the experimental outperformed EC2 and XC40

Why? So XC40, the supercomputer they had, out of the box performed much worse. And why is it? Because if you're going to run on a supercomputer, why do you need local memory? Right? You load stuff in and you just crunch numbers. And so Spark assumes there's local memory, because if you're on EC2, why wouldn't you have local memory? So there's a gotcha. So out of the box. And so this is the sort of thing that wasn't hard to fix. And by wasn't hard to fix, I mean after a few months you're trying to figure it out, it's soft. So once you take care of that, so we could mimic that with luster. There's some things like that we could do

So the numbers I showed you that said they're all about the same, we mimic that by writing to luster. So an HPC, if you're interested in that, meaning if you want to, still an open question of why you'd want to, we'll get to what you gain or lose by doing this in HPC on the next set of evaluations. But it turns out in some cases you'll want to. On HPC, you can do a few things to modify sort of out of the box Spark if you want to get better sort of numerically intensive stuff. One is say clean Scratch space more often. That's not something that Spark boys much about. To help fit Scratch entirely in RAM, say, no need to spill the luster. Maybe allow the user to specify the order to fill Scratch directories

Do RAM then luster. Exploit the fact that Scratch on a shared file system is global to avoid wasted communication. So these are sort of lessons learned. One of the sort of things that in retrospect, you know, I talked to some people, they said, oh yeah, you should obviously do that. But it took us a year to figure out. When I asked them a year ago, they didn't tell us this. So this is one of these things that probably a good thing for the engineers at Databricks and wherever they know. And other people want to develop Spark

And if you're trying to get something to work out of the box, these are going to be the sort of gotchas that you're going to face. All right. So Spark versus MPI. So we're going to do Spark, which comes out of distributed data. You could put Spark on this thing, right? You don't have to put it on an EC2. And so we put it on this, not this thing, but single machines. But we're going to evaluate it on EC2 and NERSC, which is the LBL machine, not the experiment with Cray one. So here's the climate problem

We want a low rank approximation. So the data they're going to work with is simulated data, as I said. If you know anything about scientific computing, it's that sort of stuff, right? You have a system. You evaluate the PDE of boundary conditions. I mean, whether it's protein folding or climate. You compute these sort of things. It's a common MO in a range of scientific applications. And so here they want to evaluate the, essentially, treatments if you put stuff in the atmosphere or whatever

So you run this for on the order of 30 years. The increment is six hours, ballpark. And what's the length scale of the simulation, right? They don't simulate this room versus the next room over. The stuff that people had used before had a length scale of roughly 100 kilometers on a side in the whole Earth. 100 kilometers on a side. When you're 100 kilometers on a side, you can get certain course properties. And you get up to, I don't remember the number, a tenth of a terabyte or some moderately large size. But you miss certain things

So you miss the San Francisco Bay, for example. It just doesn't exist. You don't see mountains, right? If you're 100 kilometers on a side, the height of a mountain is 10,000 feet, 20,000 feet. You just don't resolve that. If you go down to 25 kilometers on a side, you can pick these things up. You can pick up the bay. You can pick up mountain ranges. You can pick up things like this

So you actually get a much finer evaluation of what's going on. But it's a lot more expensive. It's 4x more expensive and maybe slightly longer because of other reasons. In addition, we're going to look at atmosphere and separately ocean. Those are the two data sets we looked at. You want to look at altitude. So in the atmosphere, you want to look up in altitude. And in the oceans, you want to look down in the altitude

And the reason is there may be interesting currents or something going on with this z dependence, the altitude dependence. And if you do that, you're going from essentially a 2D system at some level of granularity to a 3D system. And you can imagine that blows things up. So the 16 terabyte got very large for that reason. So this is just a picture to say, see, we computed. So this, I could have computed something on a hundredth the size and you would have gotten the same picture. You wouldn't have been able to tell the difference. So this is actually the first principal component of the temperature field, 180 degree latitude on the 16 terabyte data set

So you show this to a climate scientist, you'd say, yeah, I know that that exists. But we're validating what they know and then going from there. But this is computation on the first principal component of the 16 terabyte data set. So in particular, there's a lot of vertical variation, right? There's stuff going on here that as a function of the altitude varies that you don't see with traditional surface analysis. So that's what they're interested in. OK, so we're running on Cori, their machine. And we're running NMF versus PCA. And why don't I, I guess I'll show you the numbers and explain why the numbers

Although I've hinted sort of why we're going to see the numbers. So Cori, we have 1600 compute nodes. There's the specs on the cores per node and the size per node. NMF, so I said the version of NMF we're running as a relatively simple version of NMF. And I'll show you what that is. But basically, it boils down to a QR. And we can do a tall, skinny QR. So you can do in one pass over the data

So you go from 50 to 100 to 300 cores with NMF, the nodes with NMF. MPI, fairly low level, how does it perform? You go from a minute to 45 seconds to 30 seconds. So is that good or not? So I don't know. Ask an HPC person or ask. You're going down. Maybe you should go down more. Maybe you shouldn't. I don't know

But you're going down. You're going in the right direction. Spark time. So spark's going from four minutes to three and a half minutes to 70 seconds. So again, maybe it should be slightly more or less. But you're going in the right direction. Ballpark, it looks reasonable. And the gap is decreasing slightly

4.2, 4.6. That could be a fluctuation effect. I don't know. We don't have a good estimate on the variability of the numbers because you had to bring the machine down and run this one. But that may very well be a fluctuation effect because you're taking the ratio of two numbers. And one went down to 45. So it stayed slightly lower than the 327. So that could be a fluctuation

But you're going down to 2.3. And that we think is a real effect. So you're going in the right direction. So PCA. has this more nontrivial communication pattern, meaning it's not one pass QR. It's not straightforward matrix vector multiply. It's more nontrivial type of communication pattern. And we're on the two terabyte data set

And we're looking at 100 nodes, 300 nodes, and 500 nodes. MPI is a minute and a half, a minute and 56 seconds. So again, not a big change. You might want more. You might not. You can talk about the details. But you're going in the right direction. You're decreasing

Spark time is going from 15 to 13. That may again be a fluctuation effect up to 19. So you're actually going in the wrong direction. The gap's increasing. It increases from 10 to 20. Is that real or not? Go to 16 terabytes. Compare MPI and Spark. There's a few little gotchas

We couldn't get Spark working with all 1,600 nodes. You can only get 1,522. A few other things like that. MPI is two minutes. Spark is 70 minutes. So you're losing 26x. More than 20, more than 13, more than 9. So what you're seeing here on the straightforward linear algebra, you're seeing what you'd expect

And what distributed data systems people expect when they do two steps of an iteration or do they do joins and counts. They're seeing its scale, which is what they'd expect. What you're seeing when you're running nontrivial linear algebra, meaning stuff that isn't just a few steps of iteration but involves more nontrivial communication patterns, you're seeing antiscaling. And it worsens with concurrency and data size. So we wanted originally, and we're still hoping to run PCA on 100 terabytes. So we're not going to take exactly what we have here. We're going back and I'll tell you we're doing it before we get to that. So why is this working? So say we're computing the truncated PCA

This is used for dimensionality reduction, as I said, in a range of other things. It's defined in this way. So the two steps of computing it are the following. So we need to compute the truncated eigenvalue decomposition of A transpose A. That's not the way, as I said, a numerical analyst would do it. But we wanted to get just the top part of the spectrum. I think we're computing, I think it was 20 eigenvectors or something. Not all, however many

So not all 50,000 or whatever the number was. So very low rank approximation. And then we'll wash the bottom part out. So that blowing up of the condition number doesn't hurt us here. But it could if we wanted to get farther down in the spectrum. And that gives us v. is the right singular vectors. This is part of the PCA

And then we compute the SVD of A times v. And then that gives us the rest of it. So if you're familiar with PCA, you know what the sigmas and v's mean. And if not, we do two steps. The truncated eigenvalue decomposition of A transpose A, and then the SVD of A times vk. We're going to use long source method. That's going to require only matrix vector multiplies in the first step. And then we assume that the second step is small enough that the SVD can be constructed locally

So this is one of these other interesting trade offs. What if that's false? And we could just make it true, right? Just don't compute more. And you can think of this as a model selection. If the rank parameter is a model selection parameter, maybe the right rank is 57. But I can only compute 50 locally. So I have a slightly misspecified model. But go from there. And that sort of trade offs common

So we're assuming that we're small enough that we can do it locally here. Computing the long source iterations in Spark. MLlib, Linalge eigenvalue decomposition interface to RPAC. So this requires matrix vector products against A transpose. So what we're going to see is that we lost a factor of 2 to 26 in the 1 to 16 terabyte size scale. That'll get worse if we get larger. Where are we losing stuff? So here's the overhead from the perspective of a task. So you have a task

Remember I told you RDD and you split it up. Tasks. Here's the view of one task. There's going to be potentially a task start delay, scheduler delay, part one, task overheads. Then you run the computation. Then you do other stuff. There's more overheads. There's more scheduling delay

There's time waiting. There's a straggler. There's time waiting till end. So we're going to split this up into a couple different things. So we're on the 2.2 data set. So the small climate data set. And what you see is on PCA. I think I have an MF on the next one

Maybe I don't. So there's orange and sort of, I guess, purple are certain waiting times. And then there's basically the light blue and the dark blue are computations. So you're doing a gram matrix vector product, and I guess the light green, sorry, and the dark green are other computations. So the blue is the gram matrix vector product. And then the two greens are the other local computations distributed A times V and the local SVD on AV. So the green's small. The blue, it's decreasing

So MPI 100, 300, 500 nodes, it's decreasing. And SPARK 100, 300, 500, decreasing. You look at the overheads, which is the purple and the orange, increasing. You go from 1 to 3 to 500. So this is what you see. It's a linear scale on the y-axis. So you're losing a lot. But maybe it doesn't kill you

That's why you saw the factor of whatever the numbers were for the two terabytes. I think it was order 10. Order 16. On the 16 terabytes, we lost a factor of 25 or 28, whatever it was. And so this is the reason why. So now we're on the log scale. The y-axis is a log scale. So the blues and the greens is SPARK and MPI

And what you see is that SPARK's in general worse by some factor. In some cases, it's a little bit better. There's a range of trade-offs here. We understand some of these. We understand we don't understand others. The point is that you have overheads, and the overheads are an order of magnitude larger. So this is a log scale. So on the right, it being a little bit higher is much, much higher

So on the 16 terabyte, the climate computation using 48,000 cores, the overheads are an order of magnitude higher. We have a breakdown in terms of a range of other things like this. The NMF is, as I said, is a particularly nice form of NMF. It boils down to QR decomposition. It assumes it's some separability thing. So it boils down to a QR decomposition. There's a bunch of types of QR decomposition. We can run a tall, skinny QR, which you can do in one pass if the rows are ordered in the usual way

And so we're going to do tall, skinny QR. This will require tree reduce in one pass over the data. How does this perform? So MPI, 50, 100, 300, everything going down. SPARK, 50, 100, 300. There's a hiccup there, but it's going down. And overheads, the purple and the orange, going down. So scaling the right way, scaling it the way you'd expect. And that's because you paid the factor of 2 to 8 or whatever it was with the NMF

The single digits, not the 26. And it's because the NMF has a straightforward communication pattern. So what are lessons learned? With favorable data, tall and skinny. Remember, if you get fatter, you're going to have to deal with something on the small problems with multiple machines. And that's another can of worms. And well-adapted algorithms. This wasn't out of the box. We had to do tree reduces the right way

So this is not out of the box. But can you do numerically intensive machine learning at scale? If you do that and you try and do it in SPARK, it's 4 to 26 times slower than MPI. So should we include I.O. in that number or not? I would say yes because HBCs are spreading to computers. On time, their I.O. are spread to purpose I.O. Some of them are doing high bandwidth memory or only for us because we do the system. That's a much higher I.O

buffer. So that's also when they verify it in the ring architecture. You are also attached to her. So these are actually the factor that you lay or you have to find a little . Good. Fair point. Does anyone want to take the counterpoint? Come on. Anyone? So the answer is it depends on who you ask

Some people would say obviously yes. Some people would say obviously no. So HPC people would give one answer. And database people and EC2 people would give another answer. This is if it's included. If you don't include it, those numbers are 5 to 40. So they change a little bit, but not to change the leading order a bit of what we're saying. But they do change a little bit depending on whether or not you include I.O

And whether you should include I.O. or not depends on the area you come from. Precisely for these reasons is one example. Spark overheads are ordered a magnitude higher than the computations in PCA. The overheads are moderate if you're working with fairly straightforward computations. And something like page rank is a straightforward computation. Some people say this is the biggest, important, most hard problem linear algebra, it's just straightforward. It's a matrix vector multiply and fits very well with the database accounting paradigm

But if you're going to have more non-trivial linear algebra, you're going to have Hilbert spaces, vector spaces, are much more structured than flat tables. And so you're going to have much higher overheads if you do that. H5 spark performance is inconsistent. That needs some more work. And large gaps means it's worthwhile investigating efficiently interfacing MPI codes with sparks. So one answer to this is don't do it. All right, I'm doing internet, social media something. I just need to get an answer that's roughly right

Better than going to all this effort is to get 100 models that are all of which roughly right and put them together with an ensemble method. All right, that's a common thing that people do in machine learning. And that's perfectly legitimate if you want to optimize prediction accuracy. There's a trade-off between that and understanding, which is what certain other people want, the scientists want. And so there are people who are going to want this. And at this scale, if you say I'm only going to ever work with 16 terabyte data sets, you say fine, eat that factor of 26. And you'll be fine. And that may be what they're willing to live with

Now I want to do it on 100 terabyte data set. I want to do it on something larger. And that factor of 26, I don't know what it'll become. hundreds or something. And now that starts to become prohibitive. So can we investigate efficiently interfacing MPI codes in Spark? If you're going to do these computations in this environment, and at least currently doing these sorts of computations at that scale, you've got to be in this environment. You essentially can't do this in EC2. So why can't you do these PCA on 100 terabytes of data on EC2? And it's nothing technical about anything I've been talking about in overheads or why

The answer is I can't get the data there. Just moving the data costs an obscene amount. Now if you have a cluster in-house, and you're generating data, and it's actually there, that may not be the case. But essentially you can't do this at EC2 now because it's moving the data to be too expensive. And so the point of comparison here that we're comparing to is if you wanted to do it at that scale. Maybe in a few years this will be different. But at least currently that's the case. So we're calling this Alchemist

We were sitting around one day and describing what to do. There's LA pack. There's Elemental, which is a set of linear algebra codes. And just linear algebra wasn't performing all we needed to make some sort of conversion to fix stuff. And we thought, you know what, Alchemist. And we were on the fence. We'd write this up, make this a paper, just put this in the code or something. And once you have a good name, you have to run with it

So we came up with Alchemist. So if you remember nothing else from the talk, remember Alchemist is going to turn your bad metal nuggets into gold or something. And so this will solve your problems. So remember Alchemist if you remember nothing else. So Spark is 4x plus slower than MPI. Remember the structure of a Spark. You could just use Spark as a scheduler and eat that factor of 4, right? We're running into the problem here because we're doing the linear algebra inside Spark. And each task has this, you need to do stuff

You can't have this complicated communication pattern. So why don't we have a task and sort of just write down to MPI and do stuff? You're going to pay a fixed overhead in terms of what you write. That's going to be a factor of whatever. And then you do MPI. You take advantage of highly optimized code. So that's roughly the idea. So for efficiency, we're going to want as little overhead as possible in terms of file I.O. and RAM and network usage and all these things

So there's a couple possibilities. So HDFS. Red is bad and green is good. So there's 2x RAM. That's good. It writes to disk. It's efficient, but it has to do some network shuffling. Pass the Ignite

2x to 3x, how many copies do you need to keep? And 3 is more than 2. So that's not so good. The file I.O. doesn't do, uses networks well, has restrictions on partitioning. You know, Alexio, similar. And so we want Alchemist that's green across the board, which means it's going to be good across the board. We have a prototype working. There's a certain, it's not sort of single digits

It's whatever it is. It's better than the 26. And the reasons for that slowdown are orthogonal to anything we've been talking about. It's just sort of rewriting something. And so we're taking care of that now. So let's say that's solved. But it's not. But it's nothing related to what we're talking about here

So the Alchemist architecture is going to be, we're going to have a gateway Spark. It'll call MPI. Well, this is going to be within a single Spark job, right? So we're in a single, so Spark doesn't know the difference. It's just doing something. It writes down. It does stuff in MPI and sends it back. Send the metadata for I.O. to this gateway

Send the matrix to the gateway. It's that conversion that we're doing suboptimally in a certain way. And so Alchemist will do the repartitioning of the matrix. It'll execute MPI code and repartition back. And so it's this repartitioning step that you can imagine if there's better and worse ways to do it. And if there's a couple of intermediate layers, the first thing we tried didn't work. So we're doing that sort of by hand now. Each call to Alchemist is going to be a single stage within the Spark process

So Alchemist will enable, we want it to enable it to sort of a lightweight wrapper around APIs for existing MPI codes. So we're going to get the convenience of Spark and the ecosystem. If you want that last factor of two, don't do this. But if you're going to live with a factor of four, whatever, we're hoping for low single digits, do this. And you'll scale just fine because you pay that factor of four and whatever it's going to be, and that's it. So a bunch of technical reports. These slides are up, et cetera, et cetera, if you want more details. So sophisticated data analogists, and I don't want to use that term pejorative deletement

Other things aren't because they're sophisticated in different ways. But at least in terms of stress testing linear algebra, doing the sort of thing biostatisticians do, doing the sort of thing, as small scale machine data scientists do, where you sort of look at things interactively and you want to get control over your estimates that's finer than a few steps of the power method, is going to require stronger control over the linear algebra. Just because you can predict something well doesn't mean you got the linear algebra right. There's this notion of weak learners and small learners. And what it means is that you've got the linear algebra not completely wrong. You're a little bit in the right direction, but it doesn't mean you got the linear algebra in terms of dotting the i's and crossing the t's. But if you want to do more fine scale statistical data analysis, you need that. At small scale, that's a solved problem

You call LAPAC, some numerical analyst solved it for you. can ignore it. That's the usual sort of agreement with linear algebra code, whether it's in Python or MATLAB or R or whatever. At large scale, that's just false. And so in that sense, it's the Wild West. And what you can lean on is just much weaker in terms of its infrastructure on the linear algebra side. Most workflows and applications don't demand much of the linear algebra. If you talk to most scientists, and we're pushing the edge here, if you talk to most scientists, they'd say, I want to solve a climate problem

I'm just going to cut the data down in a factor of 10 and try and solve my problem. Why do I go to all this rigamarole? And you talk to the mass spec people, they'll say the same thing. And you talk to machine learners who are doing movie predictions, they'll say the same thing. Why am I doing this just paste together some more models and get some data? So most applications actually don't stress linear algebra much. But meaning now you don't have this infrastructure stuff to rely on. Low rank algorithms for interpretable scientific data analytics on tens of terabytes of data. Complex data workflows will involve linear algebra one step. And the communication optimization is a range of trade offs here that are going to be interesting

I think there's a more general question about what's the right way to do these sorts of computations. Linear algebra is one of these things that impedance matches a lot of theory, mathematical and algorithmic and statistical, to the nuts and bolts of getting stuff to run here. And there's a bifurcation point in the history of computer science and numerical analysis sort of banished and database people and discrete theory of computation took over. And now things are evolving and this stuff's coming back precisely because you want to do the inferential step. And what's the right way to do that at scale? Some of these issues will matter. Some won't. We blow up the condition number. They're not going to be happy about that

But we do that for very good statistical reasons in this case. So what's the right way to do these sorts of computations at scale? So with that, let me wrap up. I'll say that I'm going to skip a bunch of slides here on communication. And the leading order bit from those slides is that I was talking about QR, whether it's on one machine or many machines. And there is some algorithm. Call it algorithm A. And one thing you can do is to say, I want to optimize flops. I want to optimize computation

And that's a legitimate metric. And it's the right one if computation is the expensive thing. If computation is relatively cheap and communication is the expensive thing, that may not be the right thing. And that's true both on one machine in terms of memory hierarchies, but also in distributed data systems. Right? Because you could have distributed data systems. We have strong links between the different machines. And that's starting to look a little bit like a supercomputer. That supercomputer is without local memory

And what does that look like? So there's a whole trade-off space in terms of latency and bandwidth parameters. And so we're looking at a bunch of stuff in communication avoiding linear algebra for data analysis and machine learning. So this is something that people have looked at in scientific computing for single machines, for memory hierarchies. One, the questions you'd ask in data analysis. But two, the types of trade-offs in terms of latency and bandwidth and these sorts of parameters is very different for terabyte scale machine learning. So I talked about just vanilla, straightforward, low rank. We have results on ridge regression, lasso, and a range of other sort of things that are fundamentally linear algebraic, but stress test the machine learning and doing numerically intensive computation at scale in different ways. So I'll skip over that

But if anyone's interested, we have results along those lines, too. And with that, let me wrap up. So a quick question. You have the Alchemist model, and it is communicating with the open MPI layer for this hardware level, C level optimization, optimization. My other question is, how do you persist cache, which is actually the most important benefit of direct open MPI management? You may say, OK, previous time in the period, it's doing a well to layer cache, and it's actually faster than reading from anywhere on memory. If your Spark is sticking out. You're talking about persist across Spark? When we call MPI, MPI takes care of it. I mean, it's the last view

However, your next job may utilize all that. Yeah. However, how do you transfer the stages of cache already there? Or persist across maybe another node, saying, should we local allocated task another node? Or on this node, how does this optimization happen? Yeah, I mean, I think that's two steps ahead. Oh, sorry. The question was about cache and persisting this between different steps in Spark, so that MPI can take advantage of it. Sorry. So that's two steps ahead. Right now, we're treating the Spark job, call MPI, do something that's going to be numerically intensive

That would probably be within that factor of four. We might, you know, so you can imagine a bunch of engineering effort, we get this right, and then that question arises. But that's, I think, still two steps ahead. OK. For what I've been, a lot of nowadays, HBC from my experience, we are actually not using CPU level . They are using these offload cards, such as or GPU or whatever, using standards that are OpenCC, OpenCR, which is more to the other protocol now. Is there any plan to rather just go OpenCR than? Yeah. That's probably three steps ahead

OK. You know, I think, yeah, we're trying to take the easy thing first, which is just get the stuff working together. So the question was, well, I mean, the question was just a finer scale trade off with a range of these things in terms of going beyond CPU computations to a range of things. Right now, essentially, what we're saying is within Spark, within a given RDD, call an MPI computation and do something. I don't care what it is, it's whatever MPI will do. You know, not worrying about, you know, cross iterations and if MPI wants to do something here because someone developed something, that's fine. But we're not managing that in that sense. I mean, more political question, not a technical one

What do the Spark folks think of this? Are they going to adopt the core of the MPI interface? So, I mean, I'm at least one of the Spark folks. So I have an office in Amplab. And yeah, I mean, I think, so Amplab is, so Berkeley has a good model whereby, you know, you have these labs that live for five years and then they die. And dying is a good thing because you can move on. And so I think when we first had these results a few years ago, it was a little more sensitive because there's a lot of papers that says Spark does wonderful on such and such because I found one data set and did an easy use case. So Spark does terribly on such and such because I evaluated it in a way that wasn't fair to it. So, I mean, this, I think, you know, there's a few pimples here and I tried to point out, you know, we brought the machine down for one day and there's a few things we don't know. But I think this is the sort of most thorough and sort of fair comparison

When it was first out, people were asking us, well, did you do this or that or that, but I think it was clear, I mean, one, we were in-house, we were them. And so we ran up by them to make sure we didn't do anything. We weren't missing obvious things. And I think the take home for this is, there's a couple ways to use this. I mean, one is because of this, the problem's well characterized. We, you know, we, in the sense that, you know, we have a good sense of where it performs well and poorly and it's not surprising. Of course, you didn't tell me this a year ago when I was asking you this, but, you know, it's not, it makes sense. And in a sense, it's good that we give this to not the Amplab people, but Spark, Apache Spark or Databricks or something to say, you know, don't just believe what everyone's telling you about how wonderful it is

You know, here's points where there's a problem and if nothing else, it's good to say, you know, here's failure modes because you can drill down on that. So in that sense, that, in that sense, I think that's very good. And when people saw that we did a thorough and fair job and we understood what we were doing, that was good. And I think now, you know, this is, it's a less of a research thing. And so now that Amplab's wound down and RISE is starting, good, it's out, you know, move on. And, but, you know, this is an important evaluation for, you know, engineers that want to, I think there's a couple ways to take this, right? I mean, if you're an MPI person, you're going to say, yeah, you lose a factor 26, that's still terrible, I'm going to still do my own MPI. And, and that's exactly, you know, the wrong thing to do. How many years has, has MPI been around and people have been optimizing this to death and Spark's been around for five years or whatever, right? And so there's a lot of points here where if you put in a massive amount of engineering effort, you can close those gaps

And so I think that's the value in this. I mean, I think more on the other side, going back to the MPI people, if you really need that last little bit, you know, just study MPI, go down to, you know, go down to source code. I mean, do whatever. But say that you don't care about Spark and data and machine learning, you know, you just want to do your scientific computing. I mean, is sort of MPI the right level of granularity to be thinking about these computations? And speaking, and this is to answer the political aspect of your question, right? And some people say, yeah, what else would you do? But it's not clear that's the right level of granularity. I mean, there's certain things that aren't handled well, like fault tolerance, that Spark and these distributed systems are basically designed to do. Now, if you're paying a factor of 20 or 40, you can fail 19 or, you know, 39 times and still be better than that. But if you start to whittle that down to a factor of four, then that's not so clear

And then there's just the programming model question. What's the right level of granularity to be doing numerically intensive computing? I mean, is the overhead to learn MPI? I mean, you're never going to beat assembly code. So why are you comparing to assembly code? I mean, MPI is a little bit higher, but it's still, it's fairly low level. And, you know, I didn't go into the details of the randomized matrix algorithms, but, you know, there's a theory that says, you know, theorem such and such, it's good in this way. We implemented it in RAM. We implemented the distributed data system. You can imagine folding fault tolerance into the algorithm. So there's an oversampling factor that I didn't describe as, I want to get k eigenvectors

It's intractable to get the best k columns, but if I allow myself to choose k plus p, you know, a few extra, then it works out. So why don't you allow me to choose, you parametrize the problem. Are you a computer scientist or a machine? How do you parametrize problems? Parametrize the problem to ask for k plus 2p, and then stop whenever the first k plus p come. If the failure modes in the system are orthogonal to the way you light a data or whatever, you get a random sample of k plus p when that happens. So you've folded the fault tolerance into the algorithm. And so it's not, and so I think there's some lessons, even with the particular implementation that Spark has, in terms of the way Spark's thinking about fault tolerance and other types of things that are of value for MPI, even if you're just interested in this and don't care about that. Whether or not that takes off is a longer political conversation than that answer. But I think that's sort of roughly the situation

So I have a question. So you probably got free time on the NERSC as well as from EC2. But you can estimate how much it would cost to buy the time. And so how much would it cost in terms of dollars instead of time? Is it a... Yeah, I should know the answer to that, because I was in the audience once and Alex Gittens, the guy who did the lion's share work, was asked that question. And his answer was basically, I don't know if someone else paid the bills. I don't know offhand. I mean, I paid some, I didn't pay other

So I think it would depend on how you allocated the spending, because EC2 costs something. It's just whatever it is. We could optimize that if you wanted to go to a machine with higher and lower priority. The way NERSC works is they have a queue and range of things. When we brought it down for a day, that's not something that there's a price for. We knew the people, they wanted to evaluate the system, you bring it down. They have sort of an internal, you know, dollar, I mean, it's not a dollars, but some internal budget mechanism. So I don't know how to convert that to dollars and cents

That would be a fair comparison to EC2. So I think that's, there's no easy answer to that. But I suspect that it will be a much better comparison, because EC2 is so cheap and having a dedicated supercomputer is expensive. Yeah, so this is one of these things, should you count I.O. or not? You know, is EC2 cheap or not? You know, I don't know if it's cheap. I mean, I was paying some of the bill, you know, it's not so cheap. It was more expensive for me, but that's because I didn't pay these dollars, these, you know, credits on NERSC. But it's not so cheap

And certainly it's cheaper than a multibillion dollar supercomputer. But, you know, that's like, that's not, the relevant comparison for most people. I mean, you can imagine, I work at LBL. The U.S. government, for geopolitical reasons, has decided to invest in distributed data systems explicitly or implicitly because of tax breaks. Or it's decided to invest in supercomputers. And this is just a fixed cost, right? So I don't pay that. And LBL may, you know, and I'm using LBL as a proxy, not them in particular

But, you know, they may want to give away hours, or, you know, to get people on their system. So the mass spec thing we're talking about, it didn't happen there, but we were talking about it there. And it happens in other places where you generate data. And this is sort of the place where, in that area, data is stored. And you're a scientist at some place. And you come here, you generate data, you leave it here, and you can analyze it. In which case, the cost structure is very different. So it's one of these things, it took us a couple years to figure out these numbers

And I still feel like I don't know the answer to the question you're asking. Because it really depends, you know, do you count the fixed cost or not? Do you count the fact that, so I think that's, both sides say that they're cheaper. And I don't know the best way to have a fair answer to that, I guess. And one more question. So the audience for Alchemist, I guess, uses supercomputers. Because even if you exploit MPI, you don't have a . It doesn't know. Yeah, I mean, I think the immediate thing is that

The, more generally, the question is, say you want to do PCA on 100 terabytes. I can imagine there's people out there that don't have, I know there, you know, that don't have access to a supercomputer, that want to do it in some distributed data center. And maybe they want, you know, there may be some phenomenon out there that didn't exist 10 years ago that's computationally intensive in machine learning and it's all the rage and allows you to do a very good job predicting, you know, cats and stuff, right? And so 10 years ago that didn't exist. Now deep learning sort of is there. And that's a relatively computationally intensive aspect of machine learning. Now they do SGD and a range of other trade-offs, but I can imagine that that highlights the importance of sort of numerically intensive and computationally intensive machine learning type algorithms more generally. And someone might say, geez, I want to run PCA on 100 terabytes. And so I want to build an in, and 100 terabytes isn't so, so large

It's 100 of those. And so maybe it's a couple hundred or whatever depending on the size of your machine. And so I build something in-house and I cook in fast interconnects and I sort of mimic something. And so the quantitative numbers I put up are different because the interconnects are a little bit worse. But, you know, if you did that, you could use Alchemist and you'd pay a factor of instead of four or whatever the number we're going to get, it's a factor of eight. So I think the general question is, how do you want to do computationally intensive machine learning at the scale of 10 hundred more terabytes? And so that's sort of the target audience. So the first to mark, you know, the foot in the door would be the scientists who are doing that and have a supercomputer because that's the easiest foot in the door. But the question I think is more general

Thank you.