7 ms·

Forget about complex shared-memory or message passing architectures: that stuff doesn't scale, and is so incredibly brittle anyway (think about what happens to

Forget about complex shared-memory or message passing architectures: that stuff doesn't scale, and is so incredibly brittle anyway (think about what happens to an MPI program if one core goes offline). MPI is not good at fault tolerance, though MPI-3 will help some. MapReduce and Sawzall are well-suited to the problems they were made for: largely independent operations on very large data sets with occasional reductions and weak synchronization. Usually disk is a significant factor and strong scalability is not especially important. But they really can't compete with MPI for other problem domains. Claiming that MPI doesn't scale is demonstrably false, as evidenced by PDE solvers running on 200k - 300k cores (Jaguar, Jugene, etc). This is a comfortable order of magnitude larger than Google is running, and the communication requirements of those algorithms are far more demanding, with essential all-to-all communication as well as low-latency global reductions (for which Blue Gene has dedicated hardware). The need for these low-latency all-to-all operations is actually very fundamental (formally proven). The algorithms also tend to have much stricter synchronization requirements, for example, nothing can be done until everyone gets the result of a dot product, because the next operation needs to happen in a consistent subspace (though MPI has fine asynchronous support). There has been plenty of work trying to make algorithms less synchronous, but weakly synchronous algorithms almost uniformly have worse algorithmic scalability (number of iterations to solution increases by more than a constant factor). And since problem sizes are usually chosen to fit in memory, the network doesn't get a free pass due to the disk being slow. If you care about strong scalability, MapReduce and Sawzall are probably not good choices. Similarly, if your problem domain requires low-latency all-to-all, reductions, or "ghost exchange".

Retric 16y ago
200k - 300k cores... a comfortable order of magnitude larger I would assume Google has well over over 20,000 cores. Or did you mean something else?
- jedbrown 16y ago
  From talking with someone at Google Zurich who is involved in page-rank computations, those jobs run on ~10k to 20k cores. Of course Google has many more distributed around the world, but unless something has changed in the last few months, they are not running single jobs on more than about 20k cores.
  - Retric 16y ago
    In many ways pagerank is a special case where you need a lot of resources for a short period of time. In such cases you could use PMI but that's not the hard part of scaling for Google. From what I have read, Google treats its global compute infrastructure in a reasonably abstract fashion. To the point where their production systems share resources across datacenters so that losing a datacenter has minimal impact. Thus, when Google people talk about "scale" they often mean getting it to work for long periods of time, efficiently, on flaky hardware, spread across the world, which PMI does not do.
    - jedbrown 16y ago
      You use "PMI" consistently, but I assume you mean "MPI". MPI is not a silver bullet, and if your problem can be reasonably solved with nearly asynchronous algorithms such that fault tolerance is a bigger problem than network performance, then MPI is probably not a good choice. But this is a rather narrow definition of "scale" (and much different from the standard definition over the last several decades of scientific computing), and for more tightly coupled problems, MPI can beat these alternative paradigms by huge margins.
      - Retric 16y ago
        The more cores you have the more important dealing with failure becomes. Multi CPU super computers have been dealing with these issues for a while. 2-3 CPU failures per day is fairly common and losing a rack in the middle of a job is way too common.
        jedbrown 16y ago
        Yes, however the algorithms are such that failure cannot be made strictly local. For example, when solving a stiff PDE, there is unavoidable and quite complex global communication at every time step (indeed, within the nonlinear solves required in each time step). There is no hope of "continuous local checkpointing" or the like because the program state is changing to the tune of gigabytes per second per node. The most common response is to perform global checkpoints often enough that hardware failure is not too expensive, but infrequently enough that your program performance doesn't suffer too much. Bear in mind that our jobs are not normally hitting disk heavily, so frequent checkpointing could easily cost an order of magnitude. When hardware failure occurs, the entire global job is killed and it is restarted from the last checkpoint. There are libraries (e.g. BLCR) that integrate with MPI implementations and resource managers for checkpoint, restart, and migration. Note that it is not possible to locally reconstruct the state of the process that failed because there just isn't enough information unless you store all incoming messages, which can easily be a continuous gigabyte per second per node. Even if you had a fantastic storage system that gave you ring storage with bandwidth similar to the network, local reconstruction wouldn't do much good because the rest of the simulation could not continue until the replacement node had caught up, so the whole machine would be idle until during this time. If you have another job waiting to run, you could at least get something done, but the resource management implications of such a strategy are not a clear win. So if hardware failure becomes so frequent that global checkpointing is too costly, the only practical recourse is to compute everything redundantly. Nobody in scientific computing is willing to pay double to avoid occasionally having to restart from the last checkpoint, so this strategy has not taken off (though there are prototype implementations).
snissn 16y ago
http://en.wikipedia.org/wiki/National_Center_for_Computational_Sciences#Jaguar http://en.wikipedia.org/wiki/National_Center_for_Computation...

Retric 16y ago

200k - 300k cores... a comfortable order of magnitude larger I would assume Google has well over over 20,000 cores. Or did you mean something else?

jedbrown 16y ago
From talking with someone at Google Zurich who is involved in page-rank computations, those jobs run on ~10k to 20k cores. Of course Google has many more distributed around the world, but unless something has changed in the last few months, they are not running single jobs on more than about 20k cores.
- Retric 16y ago
  In many ways pagerank is a special case where you need a lot of resources for a short period of time. In such cases you could use PMI but that's not the hard part of scaling for Google. From what I have read, Google treats its global compute infrastructure in a reasonably abstract fashion. To the point where their production systems share resources across datacenters so that losing a datacenter has minimal impact. Thus, when Google people talk about "scale" they often mean getting it to work for long periods of time, efficiently, on flaky hardware, spread across the world, which PMI does not do.
  - jedbrown 16y ago
    You use "PMI" consistently, but I assume you mean "MPI". MPI is not a silver bullet, and if your problem can be reasonably solved with nearly asynchronous algorithms such that fault tolerance is a bigger problem than network performance, then MPI is probably not a good choice. But this is a rather narrow definition of "scale" (and much different from the standard definition over the last several decades of scientific computing), and for more tightly coupled problems, MPI can beat these alternative paradigms by huge margins.
    - Retric 16y ago
      The more cores you have the more important dealing with failure becomes. Multi CPU super computers have been dealing with these issues for a while. 2-3 CPU failures per day is fairly common and losing a rack in the middle of a job is way too common.
      - jedbrown 16y ago
        Yes, however the algorithms are such that failure cannot be made strictly local. For example, when solving a stiff PDE, there is unavoidable and quite complex global communication at every time step (indeed, within the nonlinear solves required in each time step). There is no hope of "continuous local checkpointing" or the like because the program state is changing to the tune of gigabytes per second per node. The most common response is to perform global checkpoints often enough that hardware failure is not too expensive, but infrequently enough that your program performance doesn't suffer too much. Bear in mind that our jobs are not normally hitting disk heavily, so frequent checkpointing could easily cost an order of magnitude. When hardware failure occurs, the entire global job is killed and it is restarted from the last checkpoint. There are libraries (e.g. BLCR) that integrate with MPI implementations and resource managers for checkpoint, restart, and migration. Note that it is not possible to locally reconstruct the state of the process that failed because there just isn't enough information unless you store all incoming messages, which can easily be a continuous gigabyte per second per node. Even if you had a fantastic storage system that gave you ring storage with bandwidth similar to the network, local reconstruction wouldn't do much good because the rest of the simulation could not continue until the replacement node had caught up, so the whole machine would be idle until during this time. If you have another job waiting to run, you could at least get something done, but the resource management implications of such a strategy are not a clear win. So if hardware failure becomes so frequent that global checkpointing is too costly, the only practical recourse is to compute everything redundantly. Nobody in scientific computing is willing to pay double to avoid occasionally having to restart from the last checkpoint, so this strategy has not taken off (though there are prototype implementations).

snissn 16y ago

http://en.wikipedia.org/wiki/National_Center_for_Computational_Sciences#Jaguar http://en.wikipedia.org/wiki/National_Center_for_Computation...