Dec 24

Pessimism about parallelism

Massive concurrency and hardware parallelism are sexy topics in the 21st century. There are a couple of good reasons for this and one rather unfortunate one.

Two good reasons are the combination of eye-catching uses of Graphics Processing Units (GPUs) in games and their unexpected secondary uses in deep-learning AI – these exploit massive hardware parallelism internally. The unfortunate reason is that single-processor execution speeds hit a physics wall in about 2006. Current leakage and thermal runaway issues now sharply limit increases in clock frequency, and the classic way out of that bind – lowering voltage – is now bumping up against serious quantum-noise issues.

Hardware manufacturers competing for attention have elected to do it by putting ever more processing cores in each chip they ship and touting the theoretical total throughput of the device. But there have also been rapidly increasing amounts of effort put into pipelining and speculative execution techniques that use concurrency under the hood in attempts to make the serial single processors that programmers can see crank instructions more rapidly.

The awkward truth is that many of our less glamorous computing job loads just can’t use visible concurrency very well. There are different reasons for this that have differing consequences for the working programmer, and a lot of confusion abroad among those reasons. In this episode I’m going to draw some distinctions that I hope will help all of us think more clearly.

First, we need to be clear about where harnessing hardware parallelism is easy and why that seems to be the case. We look at computing for graphics, neural nets, signal processing, and Bitcoin mining, and we see a pattern: parallelizing algorithms work best on hardware that is (a) specifically designed to execute them, and (b) can’t do anything else!

We also see that the inputs to the most successful parallel algorithms (sorting, string matching, fast-Fourier transform, matrix operations, image reverse quantization, and the like) all look rather alike. They tend to have a metric structure and an implied distinction between “near” and “far” in the data that allows it to be carved into patches such that coupling between elements far from each other is negligible.

In the terms of an earlier post on semantic locality, parallel methods seem to be applicable mainly when the data has good locality. And they run best on hardware which – like like the systolic-array processors at the heart of GPUs – is designed to support only “near” communication, between close-by elements.

By contrast, writing software that does effective divide-and-conquer for input with bad locality on a collection of general-purpose (Von Neumann architecture) computers is notoriously difficult.

We can sum this up with a heuristic: Your odds of being able to apply parallel-computing techniques to a problem are inversely proportional to the degree of irreducible semantic nonlocality in your input data.

Another limit on parallel computing is that some important algorithms can’t be parallelized at all – provably so. In the blog post where I first explored this territory I coined the term “SICK algorithm”, with the SICK expanded to “Serial, Intrinscally – Cope, Kiddo!” Important examples include but are not limited to:¬†Dijkstra’s n-least-paths algorithm; cycle detection in directed graphs (with implications for 3-SAT solvers); depth first search; computing the nth term in a cryptographic hash chain; network-flow optimization.

Bad locality in the input data is implicated here, too, especially in graph- and tree-structure contexts. Cryptographic hash chains can’t be parallelized because their entries have to be computed in strict time order – a strictness which is actually important for validating the chain against tampering.

There’s a blocking rule here: You can’t parallelize if a SICK algorithm is in the way.

We’re not done. There are at least two other classes of blocker that you will frequently hit.

One is not having the right tools. Most languages don’t support anything but mutex-and-mailbox, which has the advantage that the primitives are easy to implement but the disadvantage that it induces horrible complexity explosions and is nigh-impossible to model accurately in your head at scales over about four interacting locks.

If you are lucky you may get some use out of a more tractable primitive set like Go channels (aka Communicating Sequential Processes) or the ownership/send/sync system in Rust. But the truth is, we don’t really know what the “right” language primitives are for parallelism on von-Neuman-architecture computers. And there may not even be one right set of primitives; there might be two, three, or more different sets of primitive appropriate for different problem domains but as incommensurable as one and the square root of two. At the present state of the art in 2018 nobody actually knows.

Last but not least, the limitations of human wetware. Even given a tractable algorithm, a data representation with good locality, and sharp tools, parallel programming seems to be just plain difficult for human beings even when algorithm being applied is quite simple. Our brains are not all that good at modelling the simpler state spaces of purely serial programs, and much less so at parallel ones.

We know this because there is plenty of real-world evidence that debugging implementations of parallelizing code is worse than merely _difficult_ for humans. Race conditions, deadlocks, livelocks, and insidious data corruption due to subtly unsafe orders of operation plague all such attempts.

Having a grasp on these limits has, I think, has been growing steadily more important since the collapse of Dennard scaling. Due to all of these bottlenecks in the supply of code that can use multiple cores effectively, some percentage of the multicore hardware out there must be running software that will never saturate its cores; or, to look at it from the other end, the hardware is overbuilt for its job load. How much money and effort are we wasting this way?

Processor vendors would love you to overestimate the functional gain from snazzy new silicon with ever larger multi-core counts; however else will they extract enough of your money to cover the eye-watering cost of their chip fabs and still make a profit? So there’s a lot of marketing push out there that aims to distract capacity planners from ever wondering when those gains are real.

And, to be fair, some places they are. The kind of servers that live in rack mounts and handle hundreds of thousands of concurrent transactions per second probably have their core count matched to their job load fairly well. Smartphones or embedded systems, too – in both these extreme cases a lot of effort goes into minimizing build costs and power budgets, and that’s going to exert selective pressure against overprovisioning.

But for typical desktop and laptop users? I have dark suspicions. It’s hard to know, because we’ve been collecting real performance gains due to other technology changes like the shift from spinning-rust to solid-state mass storage. Gains like that are easy to mistake for an effect of more CPU throughput unless you’re profiling carefully.

But here’s the shape of my suspicion:

1. For most desktop/laptop users the only seriously parallel computing that ever takes place on their computers is in their graphics chips.

2. More than two processor cores is usually just wasteful hotrodding. Operating systems may be able to parcel out applications between them, but the general run of application software is unable to exploit parallelism and it is rare for most users to run enough different processor-hungry applications simultaneously to saturate their hardware that way.

3. Consequently, most of the processing units now deployed in 4-core-and-up machines are doing nothing most of the time but generating waste heat.

My regulars include a lot of people who are likely to be able to comment intelligently on this suspicion. It will be interesting to see what they have to say.

UPDATE: A commenter on G+ points out that one interesting use case for multicores is compiling code really quickly. Source for a language like C has good locality – it can be compiled in well-separated units (source files) into object files that are later joined by a linker.

Dec 16

The blues about the blues

Some kinds of music travel well – they propagate out of their native cultures very readily. American rock music and European classical music are obvious examples; they have huge followings and expert practitioners pretty much everywhere on earth that’s in contact with civilization.

Some…don’t travel well at all. Attempts to imitate them by people who aren’t native to their home culture seldom succeed – they fall afoul of subtleties that a home-country connoisseur can hear but not explain well, or at all. The attempts may be earnestly polished and well meant, but in some ineffable way they lack soul. American blues music and to a lesser but significant extent jazz are like this, which is all the more interesting because they’re close historical and genetic kin to rock.

Why am I thinking about this? Because one of the things that YouTube’s recommender algorithms make easy (and almost inevitable) is listening to strings of musical pieces that fit within what the algorithms recognize as a genre. I’ve noticed that the places where its genre recognition is most likely to break down are correlated with whether the genre travels well. So whatever I’m noticing about that distinction is not just difficult for humans but for machine learning as well, at least at current state of the art.

Most attempts at blues by non-Americans are laughable – unintentional parodies by people trying for the real thing. Not all; there was an older generation of British and Irish musicians who immersed in the form in the early Sixties and grokked it well enough to bring it back to the U.S., completely transforming American rock in the process. There are, for some reason, a small handful of decent blues players in Holland. But elsewhere, generative understanding of the heart of the blues is so rare that I was utterly gobsmacked when I found it in Greece.

I don’t know for sure, not being a home-country connoisseur, but I strongly suspect that Portuguese fado is like this. I have a pretty good ear and readily synchronize myself to different musical styles; I can even handle exotica like Indian microtones decently. But I wouldn’t go near fado, I sense a grave risk that if I tried any actual Portuguese fado fan would be politely suppressing a head-shaking he-really-don’t-get-it reaction the same way I usually have to when I listen to Eurojazz.

And Eurojazz players have a better frequency of not ludicrously failing than Euro blues players! Why? I don’t know. I can only guess that the recognition features of “real” jazz are less subtle than for “real” blues, and imitators are thus less likely to slide into unintentional parody. But since I can’t enumerate those recognition features this remains a guess. I do know timing is part of it, and there are uses of silence that are important. Eurojazz tends to be too busy, too slick.

If it’s any consolation to my non-American readers, Americans don’t automatically get it either. My own beloved wife, despite being musically talented, doesn’t have the ear – blues doesn’t speak to her, and if she were unwise enough to try to imitate it she would doubtless fail badly.

One reason I’m posting this is that I hope my commenters might be able to identify other musical genres that travel very poorly – I want to look for patterns. Are there foreign genres that Americans try to imitate and don’t know they’re botching?

And now a different kind of blues about the blues…

There’s an unacknowledged and rather painful truth about the blues, which is that that the primitive Delta versions blues fans are expected to revere are in many ways not as interesting as what came later, out of Chicago in particular. Monotonous, repetitive lyrics, primitive arrangements…but there’s a taboo against noticing this so strong that it took me over forty years to even notice it was there, and I might still not have if I hadn’t spent two days immersed in the rootsiest examples I could find on YouTube.

I found that roots blues is surrounded by a haze of retrospective glorification that (to my own shock!) it too often fails to deserve. And of course the obvious question is “Why?”. I think I’ve figured it out, and the answer is deeply sad.

It’s because, if you notice that later, more evolved and syncretized versions of the blues tend to be more interesting, and you say so, you risk making comparisons that will be interpreted as “white people do it better than its black originators”. And nobody wants that risk.

This came to me as I was listening to a collection of blues solos by Gary Moore, a now-deceased Irishman who played blues with both real heart and a pyrotechnic brilliance you won’t find in Robert Johnson or (one of my own roots favorites) John Lee Hooker. And found myself flinching from the comparison; took me an act of will to name those names just now, even after I’d been steeling myself to it.

Of course this is not a white > black thing; it’s an early vs. late thing. Recent blues players (more likely to be white) have the history of the genre itself to draw on. They have better instruments – Gary Moore’s playing wouldn’t be possible without Gary Moore’s instrument, you can get more tone colors and dynamic range out of a modern electric guitar than you could out of a wooden flattop with no pickups. Gary Moore grew up listening to a range of musical styles not accessible to an illiterate black sharecropper in 1930 and that enriched his playing.

But white blues players may be at an unfair disadvantage in the reputational sweepstakes forever simply because nobody wants to takes the blues away from black people. That would be a particularly cruel and wrong thing to do given that the blues originated as a black response to poverty and oppression largely (though not entirely) perpetrated by white people.

Yes, the blues belongs to all of us now – it’s become not just black roots music but American roots music; I’ve jammed onstage with black bluesmen and nobody thought that was odd. Still, the shadow of race distorts our perceptions of it, and perhaps always will.

Dec 04

The curious case of the missing accents

I have long been a fan of Mark Twain. One of the characteristics of his writing is the use of “eye dialect” – spellings and punctuation intended to phoneticize the speech of his characters. Many years ago I noticed a curious thing about Twain’s eye dialect – that is, he rendered few or no speech differences between Northern and Southern characters. His Northerners all sounded a bit Southern by modern standards, and his Southerners didn’t sound very Southern.

The most obvious possible reason for this could have been that Twain, born and raised in Missouri before the Civil War, projected his own border-state dialect on all his characters. Against this theory I could set the observation that Twain was otherwise a meticulously careful writer with an excellent ear for language, making that an unlikely sort of mistake for him. My verdict was: insufficient data. And I didn’t think the question would ever be resolvable, Twain having died when sound recording was in its infancy.

Then I stumbled over some fascinating recordings of Civil War veterans on YouTube. There’s Confederate “General” Julius Howell Recalls the 1860s from 1947. And 1928-1934: Recollections of the US Civil War. And here’s what jumped out at me…

Continue reading