Hacker News Reader

One interesting thing going forward (over the next decade) regarding deep learning and high-performance computing will be if we can circumvent the big serial bottleneck - that is, depth. The best benchmarks have generally all been set by networks with significantly increased levels of depth compared to the previous records. Gradient descent, however, requires propagating residuals back through every layer of the network (to tune the lowest layers, at any rate). This is inherently a serial task. Recurrent networks can be considered to be infinitely deep - in practice they're truncated to some finite level during training.

There are a couple of solutions to these problems that are being worked on - including various "learning-to-learn" approaches. One approach (DeepMind published, I believe) is to locally train an auxiliary network to predict the back-propagated residuals coming down from the top. It will be interesting to see if these approaches pan out, or if eventually we start to run into real serial bottlenecks again as we build ever-deeper networks.

Just want to clarify the Cell[1] CPU was used in the PS3, not the PS2. The PS2 used the Emotion Engine CPU made my Sony and Toshiba [2].

[1]: https://en.wikipedia.org/wiki/Cell_(microprocessor)?wprov=sf...

[2]: https://en.wikipedia.org/wiki/Emotion_Engine?wprov=sfsi1

Everything at web scale is embarrassingly parallel, at least on some fronts. There's still often the bottleneck of maintaining state (in a database, probably), but a heavily loaded server will have hundreds or thousands of processes or threads or some kind of async (probably epoll or something reasonably efficient on modern systems) to serve many clients. Which is why Erlang (and Elixir) has some very enthusiastic proponents.

Serving the web is, I think, a very big part of the "general computing" space, today.

Serving the web seems to split between a) IO-bound problems and b) databases. It is certainly not embarassingly parallel in the "would benefit from GPUs" sense.

Those thousands of threads just sit there waiting for the database to respond a lot of the time. The database is busy trying to keep things synchronized across nodes. It is just that the hard stuff is pushed down to the database layer.

Both can be true. Database development, both the way they're built and the way people use them, has been focused on scaling across machines and storage for most of the history of the web; it's possible it'll never quite catch up with CPU, but it will continue to move that way. I don't know what the next evolution of databases looks like (I'm definitely not a database expert), but if Google and facebook and Amazon and Microsoft and many others need it to scale beyond what is currently possible to keep up with CPU parallelization, they'll figure out how to make it scale.

aren't databases in turn being held back by the hardware limitations like IO bandwidth?

Yeah, the Erlang ecosystem is so much better (for web) than everything else available today, it's not even funny.

Though it seems like there is some very major obstacle in people understanding it. It's so frustrating, I've already stopped advocating for Erlang/Elixir. Currently I'm concentrating in just reaping the benefits and doing my stuff.

Yep, I've built two very nice servers in erlang, but main problem - only I can extend and modify them in my company, my coworkers can't learn this. One made some inroads into this, but there's just too many cheap .net and java developers around for erlang to be successfull.

Upside for me - I'm irreplaceable. Downside - there's no one to help when something is wrong and company progress is throttled by my performance.

Elixir is partly fixing this problem. Though it's still not enough because the hard part is not the syntax (as most newcomers tend to blame their failure on), but the things you write with the language, which are the same for Elixir and Erlang.

If you are using immutable data structures/pure fp, then you can get a lot parallelism without the need for shared memory because the state is on the stack. As the article posits, you can just pass messages to the functions/objects and receive results back. Again, as the article suggests, the major problem is memory bandwidth. The trick is building a bus (busses?) that allows you to aggregate partial solutions.

This is why I'm very bullish on languages like Haskell in the future (say 10-15 years from now). It's interesting that the article suggest OO because I think the key to allowing massive parallelisation is immutability. Immutable OO and pure FP is essentially equivalent AFAICT, but the latter currently has nicer language support.

Having spent quite a bit of time designing massively parallel algorithms (concurrency starting at several thousand cores on up), computer scientists are often baffled when I tell them that FP and immutability don't help. In practice, it solves the wrong problem and creates a new one because massively parallel systems are almost always bandwidth bound (either memory or network) and making copies of everything just aggravates that. You can't build hardware busses to compensate or companies like Cray would have long ago.

If you look at effective highly scalable parallel codes of this nature, you see two big themes: pervasive latency hiding and designing the topology of the software to match the topology of the hardware. The requisite code to implement this is boring single-threaded C/C++ which is completely mutable but no one cares because "single-threaded". Immutability burns much needed bandwidth for no benefit. This among other reasons is why C and C++ are ubiquitous in HPC.

The challenge is that CS programs don't teach pervasive software latency hiding nor is much ink spilled on how you design algorithms to match the topology of the hardware, both of which are fairly deep and obscure theory.

We don't need new languages, we need more software engineers who understand the nature of massive parallelism on real hardware, which up until now is largely tribal knowledge among specialists that design such codes. (One of the single most important experiences I had as a software engineer was working on several different supercomputing architectures with a different cast of characters; there are important ideas in that guild about scaling code that are completely missing from mainstream computer science.)

Very well put, I just have one addendum: Add Fortran to the list. If you program multidimensional array like data structures as flat arrays in C or C++, use Fortran for the kernels and Python for the glue instead. It's just as performant, has much more batteries included and is much more comfortable to achieve a high performance.

I'm not about to join the FP circle jerk, but well-executed immutability can reduce memory bandwidth requirements rather than increasing them. This is because often in large C (and Java) codebases, the uninitiated will copy large structures and buffers when they don't need to, because they don't trust the other code[rs]. If you have a tree-like datastructure such as a nested map, immutability lets you copy the structure by reference even when modifying the contents.

That said, the added complexity in memory management means that if you can afford good programmers, it's better that they just try to avoid this practice in the first place. So HPC folks take the mutable approach.

I guess it's hard to say if an average, middle-of-the-road programmer will ever be able to productively work on parallel systems.

Having spent a good bit of time in HPC from a practical and academic perspective, I'll second that claim.

One example I like to bring up is the textbook hotplate, where the temperature for a single cell is equal to the average of its temperature and the temperatures around it. Each iteration is embarrassingly parallel, but the result of the iteration is necessary to proceed. Instead of synchronizing the entire cluster between iterations, each node computes the results for an extra N cells in each direction, allowing N iterations to occur before synchronization is necessary (after the first iteration, the outermost cells are inaccurate, after the 2nd iteration, the outer two layers are inaccurate, etc. Eventually, you want to sync before the cells we care about are affected). This leads to massively diminished returns as you break the problem into smaller chunks. But even for smaller chunks, doubling or tripling the work per node is still faster than synchronizing.

Heh, yes, very much that.

My sole contribution to HPC was inventing a graph algorithm (circa 2009) for breadth-first search that didn't require the usual iterated barrier synchronization super-step you have with BSP algorithms. Instead, every node would run free with almost no synchronization but a clever error correction mechanism backed out all the incorrect traversals for a completely negligible cost (both space and time) relative to the ability to let the computation run as though it was embarrassingly parallel. It basically allowed every node to always be doing (mostly) constructive work without waiting on another node.

But yeah, burning a bit of CPU to eliminate synchronization is frequently a huge win. This is where knowing how much compute you can do within a given latency window is helpful.

Do you have a citation for that?

>> If you look at effective highly scalable parallel codes of this nature, you see two big themes: pervasive latency hiding and designing the topology of the software to match the topology of the hardware

Do you have any good reference to learn general HPC and those topics? Best I could find when I searched last time was Udacity's High Performance Computing mooc and its reference book "Introduction to Parallel Computing".

Computer Architecture and Parallel Processing Paperback – International Edition, January 1, 1986

by Kai Hwang (Author)

https://www.amazon.com/Computer-Architecture-Parallel-Proces...

In certain circumstances, new languages can help software engineers to get high performance. For example, the lift project at the university of Edinburgh. It's a skeletal (think functional, but on the immutability/higher order functions rather than category theory) domain specific language for writing GPU kernels in. The team there have managed to use it to implement matrix-multiplication kernels that beat everything apart from NVIDIA's own assembly language implementations, just by using the safety and separation of concerns that a functional approach brings.

If you have high bandwidth, you can do many of the same things as with shared memory. HPC users have historically used message passing on moderately communication heavy codes.

True, it has not been used for "general purpouse computing" but historically shared memory multiprocessors hadn't been either. We are just now starting to see things like parallelism in web browsers, 10-20 years after shared memory MP became common on desktop. Software is just slow to change.

HPC is usually a balancing act between the performance you gain by adding another node and the time you lose passing messages around. You can't just keep adding nodes without introducing some form of shared memory because you will very quickly become limited by your bandwidth.

What is shared memory, if not message passing (with some particular semantics) implemented at the hardware level? I.e. messages == cache lines, semantics == cache coherency protocol. Particularly so when you go to (nowadays) multi-socket systems, where everything is NUMA.

There is a smallish sub-segment of the HPC market where customers really want large CC-NUMA systems, AFAIK SGI (whoever owns them these days, HPE?) is more or less the only supplier. But the vast majority of HPC is clusters using message passing.

If I were to choose some awfully general statement about HPC, rather than yours I'd choose "supercomputers are not tools for solving small problems faster, but rather tools that make solving larger problems possible". I.e. the entire weak vs. strong scaling thing etc.

To be honest, yours is probably the far better statement.

This question, what to do with a 'shared nothing' machine, is the real heart of the question.

The original article talked about putting ARM-9 cores on a chip which is also overkill, your typical object neither cares nor needs any of the complex memory architecture an ARM-9, had they chosen a Cortex-M they could have put twice the number of cores on their chip with no loss of computability.

But as John points out, the challenge is how you actually program these things. One interesting proposal I heard was to compile code with every loop unrolled and every branch hard coded either one way or the other. So for every "branch" in a piece of code you would generate two binaries, one where it was taken and one where it wasn't. That means four if statements, 16 different binaries. (pruned for cases that couldn't happen though). And then you ran your input on every copy of the program simultaneously. [1] The issue though, and it became crystal clear to me as I was working my way through how Google processed logs and log data, was that feeding the output of one computation into the input of another became the limiter and the interconnect of the fabric was the real bottleneck. That analysis got a tremendous validation when the underlying network upgrades started getting processed. It made it possible to run the same sort of test on a group of machines connected in the 'old' way, and the same machines connected in the 'new' way. That demonstrated just how important inter-machine communication could be in making them productive.

So a model for optimizing both in parallelization (interdependencies in state) and scheduling (interdependencies in time) it essential for making a shared nothing cluster perform better than a very large shared memory machine.

[1] Branch prediction is good enough these days to make this not much of a win.

Today, loop unrolling is usually a lose if it makes the loop much bigger. Branch prediction is better today, but cache misses are worse.

> Today, loop unrolling is usually a lose if it makes the loop much bigger.

Is this true?

For example, suppose I have a loop that does 1 million iterations and an increment of `i += 1`. If I unroll that to have an increment of `i += 10`, now I only have to do 100,000 iterations. That is 900,000 eliminated branches.

What am I missing?

The key thing missing is if it makes the loop much bigger. if

That example does not make the loop much bigger, since it's trivial to combine multiple of these additions to one bigger one (even assuming that extra checks for overflow behavior might be needed, depending on the data type). Many other operations do not compress like this, e.g. those that iterate over many elements in a large data structure, need temporary results, ... Then loop unrolling likely causes costly cache misses.

Modern superscalar CPUs are computing the branch at the same time they're doing the operation. They're also renaming registers, so that the reuse of the same register on the next iteration may actually use a different register internal to the CPU. It's entirely possible for five or so iterations of the loop to be running simultaneously.

Classic loop unrolling is more appropriate to machines with lots of registers, like a SPARC. There, you wrote load, load, load, load, operate, operate, operate, operate, store, store, store, store. All the loads, all the operates, and all the stores would overlap. AMD-64, unlike IA-32, has enough registers that you could do this. But it may not be a win on a deeply pipelined CPU.

> The real question is "what do we do with a lot of CPUs without shared memory?"

At the extreme we would go biological, that's what. But then we're talking 10^n in the billions ranges (say n = 15) and unlikely that we would directly "program" these tiny computing engines.

I think hierarchical models (in terms of system organization, with specialized sub-systems or 'organs' if you will) are inevitable unless these little machines have recourse to some sort of breakthrough in communication that would permit arbitrary [efficient and non-local] meshing.