9 ms·
Pessimism about parallelism
- glenrivard 8y agoOne things that is not talked about a lot is parallelism in terms of kernel and I/O. There is the aspects of an application but what about system code? If read the FlexSC paper and using multiple cores you can see some pretty incredible improvements are possible. https://www.usenix.org/legacy/event/osdi10/tech/full_papers/Soares.pdf https://www.usenix.org/legacy/event/osdi10/tech/full_papers/... We should also see some of this with Zircon as it gets further along and looks to leverage cores in a type of pipelining.
- riskable 8y agoSeems like the solution is "the Unix way": Use a lot of little, single-purpose applications for competing larger tasks. That way you can let the OS worry about the parallelization. Even if you're making a large, multi-purpose app like, say, a spreadsheet you could still subdivide zillions of little tasks into their own applications. On an OS this makes little sense because of the overhead associated with spawning new processes but on Linux it'd be great.
- zozbot123 8y ago> you could still subdivide zillions of little tasks into their own applications. This is the approach Rust+Rayon are taking. Rust is in a good position to enable this because of language-level guarantees. Using "a lot of little, single-purpose" tasks means that each task has to own its memory; Unix of course enforces this separation, but this comes with some overhead. Language-level discipline can achieve much the same thing, more efficiently.
- phkahler 8y ago>>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. That's only true at the very high end, where you have so much data that it's not all physically close and transport time is relevant. With the reality of stalled clock speeds and multi-core systems, people are finding the parallelism in many applications. Scaling really appears to be coming to an end - if not at 7nm then at 5 (or what they'll call 5). I don't think we're going to meaningfully exhaust our ability to exploit parallelism before then. They're not used in every application but they are used by enough things that we should have them.
- anujsharmax 8y ago> 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. The cores are not being wasted because we don't know how to parallelize computations - as evident by the scientific software run for high performance computing applications, which scales upto million cores. Business decisions are responsible for these wastages. For example, many engineering software are licensed per core - so if you are using it on 16 cores, it costs A LOT more than using it on 4 cores. In some cases the licensing costs of the engineering software are higher than the cost of the hardware. So no one cares if few cores are wasted.
- rossdavidh 8y agoThis would make it a much better idea to run on a machine with only the cores you are using, though, yes?
- marcosdumay 8y agoAt some point you want those 16 cores so MS Word will have an acceptable performance, even if your auto-routing electrical CAD uses just 1 of them to solve its own NP-hard problem.
- waynecochran 8y agoDepth First Search is not parallelizable at all? Provably so? Just divvy up subtrees.
- nothrabannosir 8y agoI'm assuming they mean actually Depth First, where splitting up a tree and traversing branches in parallel violates the "First" part. It's a bit contrived, because obviously the name implies that it's sequential. But yeah, sometimes that's precisely what you need.
- waynecochran 8y agoYes. I guess the divvying up is more like breadth first. Most cases where I would use DFS this would work.
- wtracy 8y agoNothing that processes nodes in parallel can guarantee either correct depth first or breadth first ordering. That said, it's easy enough to get effectively correct ordering by reassembling the results in the correct order as the workers finish.
- rbehrends 8y agoWhat he is presumably talking about here is lexicographic DFS (as opposed to an unordered DFS), i.e. a DFS where the traversal order matters. To be precise: given a rooted digraph G with a set of vertices, an ordered adjacency list for each vertex, and two vertices a and b in G, does a DFS traversal of the graph that follows each adjacency list in order, visit a before b or b before a? In practice, what we are interested in in particular is both a reproducible preorder and postorder ordering based on the DFS traversal, which is of use in other algorithms (such as Tarjan's algorithm for strongly connected components [1]). This problem is P-complete and under the assumption that P != NC and under the parallelization assumptions underlying NC [3], is difficult to parallelize. So far, this is not very controversial, but in practice, NC does not properly reflect what we think of as "inherently sequential"; especially the assumption of a polynomial number of processors is a bit odd when you're not dealing with hardware circuits. On top of that, we often aren't interested in all possible graphs, but only specific types of graphs. As a consequence, yes, lexicographic DFS can be parallelized for many use cases or in a fashion that we care about. As a simple example, lexicographic DFS for trees can be parallelized efficiently. More generally, lexicographic DFS is already extremely fast if we have an existing in-memory representation of the graph (linear in the size of the representation with a small constant factor). It may take longer to construct the graph than to calculate a depth-first ordering of the vertices. In this case, we may not want to parallelize the DFS algorithm as such, but organize the construction of the graph so that we can run DFS in parallel with the construction. This is of particular interest if we can't fit the graph in memory or if computing the edges of the graph is expensive. For example, we may not be able to parallelize the search as such, but we can instead parallelize the neighbor expansion. The biggest issue here is that lexicographic DFS is a rather specialized problem in the family of graph search problems and many, many interesting types of graph searches can be parallelized just fine. For example, we can easily construct a parallel version of the A* algorithm; it will not explore the graph in the precisely same order, but as we are dealing with an algorithm guided by a heuristic, this is rarely a problem in practice. [1] Though we have, contra ESR, parallel algorithms for strongly connected components in directed graphs that do not require a DFS ordering for the entire graph [2]. [2] See the previous work section of this thesis, for example: https://www.cs.vu.nl/~wanf/theses/matei.pdf https://www.cs.vu.nl/~wanf/theses/matei.pdf [3] https://en.wikipedia.org/wiki/NC_(complexity)#The_NC_hierarchy https://en.wikipedia.org/wiki/NC_(complexity)#The_NC_hierarc...
- pcwalton 8y agoThis pessimism about whether software can effectively use CPU cores beyond two is easily refuted with a simple observation: High-end games are now running pretty close to 100% CPU utilization on octa-core console hardware. Parallelizing our software is mostly a question of investment at this point. In my experience, there isn't a lot of software that wouldn't benefit from CPU parallelism in some way or another. The bigger issues are (a) that a lot of software simply doesn't prioritize performance, for both good and bad reasons, and (b) that a lot of foundational software has been in maintenance mode for years and there isn't enough interest or funding to improve it.
- zozbot123 8y ago100% CPU on an octacore? See, ESR was right, it's bottlenecked by serial performance. Now 800% CPU utilization would be impressive!
- smolder 8y agoA multicore CPU is comprised of several cores. I don't think fully utilizing all cores means "800% CPU utilization"
- bitwize 8y agoOddly enough the load average, as reported by uptime and xload, uses just this metric: a machine with one CPU pegged has a load of 1.0. A fully utilized octa-core machine has a load of 8.0.
- kace91 8y agoWhat kind of foundational software are you referring to? Honest question.
- pcwalton 8y agolibpng, to name one example off the top of my head. It doesn't even have support for SIMD on x86 yet, in 2018.
- david-gpu 8y ago> 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. That's not right. GPUs do pretty well at tasks that have poor locality compared to CPUs, as long as there's a lot of parallelism to be exploited -- see for example ray tracing. The reason for this is that CPUs depend on their large caches, which are useless when there is little locality, while GPUs simply switch to another warp while data is being loaded from memory, and they have much higher memory bandwidth anyway. Also, GPUs are distinctively not systolic arrays. Hennesy's "Computer Architecture: a quantitative approach" has a good primer on Single instruction Multiple Threads (SIMT) architectures typically seen in GPUs.
- michelpp 8y ago> Also, GPUs are distinctively not systolic arrays. Hennesy's "Computer Architecture: a quantitative approach" has a good primer on Single instruction Multiple Threads (SIMT) architectures typically seen in GPUs. Good catch, as pointed out by wikipedia: "They are sometimes classified as multiple-instruction single-data (MISD) architectures under Flynn's taxonomy, but this classification is questionable because a strong argument can be made to distinguish systolic arrays from any of Flynn's four categories: SISD, SIMD, MISD, MIMD" https://en.wikipedia.org/wiki/Systolic_array https://en.wikipedia.org/wiki/Systolic_array
- wtracy 8y agoSIMT architecture is why GPUs are actually not that great for ray tracing. In a nontrivial scene, some rays will bounce more times than others, and that means that the whole parallel execution unit is tied up until every single ray terminates. (The other "threads" essentially execute NOP instructions in the meantime.) Despite what Nvidia would have you believe, a lot of VFX rendering is done on CPUs, not GPUs, and this is one of the reasons why. (For example, last I heard, Pixar does all their render work on Intel Xeons.)
- zzzcpan 8y ago> 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. None of these problems have anything to do with parallelism. But everything with "shared memory multithreading". There are plenty of sane concurrency models implementations out there. Which brings me to this part: > But the truth is, we don’t really know what the “right” language primitives are for parallelism on von-Neuman-architecture computers. We do know what the right language primitives are. Well, at least if you follow concurrency and distributed systems, where it's not even an important question anymore, you just stick to actor model as a default choice and stop caring about these things.
- gpderetta 8y ago>Race conditions, deadlocks, livelocks These have nothing to do with shared memory multithreading. You can easily have all of these with shared nothing distributed systems. >and insidious data corruption due to subtly unsafe orders of operation I'll give you this though.
- zzzcpan 8y agoThat's stretching it quite a bit. You can implement shared memory multithreading on top of actor model and have all of the same issues. If you don't do that though, you won't have those issues. Same way that you can implement memory unsafe primitives on top of memory safe ones.
- marcosdumay 8y agoMost desktop software does not use more than 1 core because most desktop software does not need anything near 1 full core. How much processing can it take to show you a button? That does not change the fact that some software does need more, and people are wise to dimension their computers taking the largest usual load into account, not the average one. That said, the point about memory locality is good. It is just not as important as the author makes - data tends to have locality, even physics pushes it there. But the point about non-parallelizable algorithms isn't good; who cares about the property of your algorithm? If the problems allow for parallelism (with local data), dump the algorithm and get one that scales. Also interestingly, the authors does bother to link the limits to the von Neumann architecture, but didn't think about using the extra cores to JIT-compile the binaries into some other architecture...
- mattnewport 8y ago> Most desktop software does not use more than 1 core because most desktop software does not need anything near 1 full core. How much processing can it take to show you a button? It seems like this ought to be true but in practice it's not, though the problem appears to be more due to developers not paying enough attention to performance than to fundamental limitations of the hardware. I can think of very few applications that I use on a day to day basis that do not have multiple areas where I wish they performed better.
- pornel 8y agoI've become parallelism optimist thanks to Rust. The borrow checker basically doesn't even have a concept of a single-threaded program. Everything you write in Rust is required to be thread-safe. This makes Rust appear more difficult, but it's just front-loading the effort required to make the whole program thread-safe (which to me felt nearly impossible for non-trivial C programs). From there you can sprinkle Rayon all over the place, send async work over channels, etc. The piece I'm missing is "Amdahl's-law-aware" profiler that would show not just where any code spends time, but only where the unparallelized bottlenecks spend time.
- twotwotwo 8y agoRe: showing bottlenecks, the Go latency tracer may be a neat reference point; it doesn't find serial parts automatically, but it shows the execution timeline so that you can see them. Besides serial bottlenecks, it can be useful for seeing where you blocked waiting on I/O and so on: https://blog.gopheracademy.com/advent-2017/go-execution-tracer/ https://blog.gopheracademy.com/advent-2017/go-execution-trac... There might already be similar tools for Rust; I know less about what's available there. (Go folks also added some tools for tracing across RPCs, which is less relevant to what you said but just kinda independently neat: https://medium.com/observability/debugging-latency-in-go-1-11-9f97a7910d68 https://medium.com/observability/debugging-latency-in-go-1-1...)
- steveklabnik 8y agoSome of this functionality just doesn’t exist (no way to track gc when you have no gc), some of it uses C/C++ tooling (syscalls can be straced), some of it is just different (suspend points aren’t implicit), and some of it is on the way (tokio-trace is basically the real equivalent here but either doesn’t quite exist yet or is very new, I forget which to be honest).
- fooker 8y ago> Everything you write in Rust is required to be thread-safe Either you have a poor understanding of thread safety or Rust has solved the halting problem.
- rossdavidh 8y agoAll interesting, but if we're talking about typical laptop/desktop users, beside the point, I think. The reality is that the entire computer's performance is not the bottleneck, for most of what a typical user is doing, most of the time. The limitation on performance is either: 1) in the user's head (e.g. a word processor and an author) 2) in the network the computer is attached to (much of what is done on the web) Getting faster/better performance out of your laptop/desktop won't help any, for the reason that your computer's performance is already not the limiting factor, for most of what a typical user is doing. Although, this does reinforce the point that adding even more cores to a typical user's laptop/desktop, isn't really accomplishing much, but for much simpler reasons than the issues discussed in the article.
- pjc50 8y ago3) in the storage 4) in the antivirus insisting on chewing each piece of IO very slowly in case it might have a virus
- mattnewport 8y agoThis is not the case in practice for most of what I'm doing, most of the time. I'm more of a power use than a typical user perhaps but I also have much higher end hardware than a typical user and I'm continually frustrated by performance issues that are primarily CPU, GPU or local storage related, although the network being a limiting factor is also common.
- sevensor 8y agoI've used satisfiability solvers, but I don't know enough about their internals to evaluate ESR's claim that satisfiability is intrinsically serial. ESR's argument seems to hinge on this idea, that regardless of how well you handle parallelism, it's not going to help with certain tasks.
- alan-crowe 8y agoIf I had to write a SAT solver to use lots of cores on an arbitrary boolean formula, I would farm out the work like this: This walk the tree to find the variable, X, that occurs most often. There is a weighting issue. Occurrences higher up the tree count more. Then I would create two expressions by substituting X = true and X = false. Now two cores can race to see which can find a satisfying assignment first. Clearly this division can be applied recursively until all the cores are busy.
- sevensor 8y agoThis is appealing, but I think you're only going to have full utilization for a short time? Many of your partitions of the problem are going to come back unsatisfiable, and then those cores go idle.
- Const-me 8y agoI have recently parallelized 3D flood fill algorithm, it’s essentially a graph search on a 3D grid of nodes. More precisely, the problem is known as connected-component labeling: https://en.wikipedia.org/wiki/Connected-component_labeling https://en.wikipedia.org/wiki/Connected-component_labeling The solution is to keep partitioning until you saturate all cores. As soon as all saturated, stop partitioning and compute. As soon as any task finished, resume partitioning. On the lower level, I used a thread pool. BTW, the infrastructure for that is built-in in Windows, see SubmitThreadpoolWork API: https://docs.microsoft.com/en-us/windows/desktop/api/threadpoolapiset/nf-threadpoolapiset-submitthreadpoolwork https://docs.microsoft.com/en-us/windows/desktop/api/threadp...
- petermcneeley 8y agoThe problem is the inverse. The problem is that there is not enough parallelism in hardware. Single digit core counts really are not that significantly parallel especially when there is a shared main memory bandwidth. An AVX2 code transform will give you more performance than a 8 core hyperthreaded code transform, without all the latency and coordination.
- misnome 8y agoOn the other hand, Intel tried lots of (slightly slower) cores with the Phi series - And part of the reason for dropping/sidelining was that although they are an interesting platform for experiments, nobody could work out how to effectively use that many parallel cores with all of the other constraints, like memory bandwidth.
- petermcneeley 8y agoI highly doubt that the scientific community "could not work out how to effectively use that many parallel core" given that the gaming community effectively used the SPE cores of the PS3. These cores are considerably more difficult to use as they only have small local memory and have strong alignment constraints. If the phi does not have enough bandwidth to service the cores that would simply mean it is not a parallel architecture.
- devxpy 8y agoWell maybe not in desktops, but don't you think that mobile devices (even micro controllers, like ESP8266) have a lot to benefit from multi-core, even for just regular apps that have nothing to do with number crunching/gaming etc.?
- foldr 8y agoThere's probably still plenty of scope for increasing single-core performance on devices like that.
- devxpy 8y agoWell here’s the thing though, I don’t feel like parallelism is just about speed. I for one like the idea of being able doing 10 things at once, and all tasks running at the same speed. It’s hard to do with current software, yes. But there a lot of room for improvement, no?
- foldr 8y agoIf you make the processor 10x faster, then you can effectively do 10 things at once without having multiple cores.
- ben-schaaf 8y agoThis isn't quite true. There's a lot more to CPU performance than how fast it can process instructions. Someone configured Intel's 9900k at 500mhz 8 cores and compared it to 4Ghz 1 core. The actual performance characteristics are vastly different. If I had to choose between 10x more cores or 10x faster cores, I'd choose more cores.
- wtracy 8y agoI'm having trouble imagining a performance benefit to two (otherwise identical) 1ghz cores over one 2ghz core, unless: 1. The two processes cause frequent evictions of the CPU cache in some way that two cores can mitigate by having separate caches. 2. You are able to pin a process to a CPU core, and eliminate all the overhead of running the process scheduler. I would be curious to see the benchmark you're referring to. My gut tells me that the performance differences come from comparing different processor families.
- vmarsy 8y agoI'm more optimistic about parallelism, and multi cores in general. Multi cores could have other advantages than parallelism. On mobile, if there's 8 cores, and if the device/os is able to figure out the current load, and based on that turn off up to 7 of those 8 cores, the energy savings could be significant on the CPU side. (Depending on how much energy CPU uses compared to the radio or screen on a smartphone) Another obvious advantage as pointed as the end of the article is individual processes running independent work next to each other. Such embarrassingly parallel work can keep all the CPU busy pretty well.
- twtw 8y agoI'm not sure what the takeaway here is. If desktop users don't need (or can't use) more cores, then don't get them - and call an end to the periodic performance improvements, because CPUs won't get faster without more cores. Maybe that's fine. On the other side, high performance computing demands more computational power, and the only promising path forward (at this time) is parallelism. I'm not motivated by optimism, but by pragmatism. As a sidenote, I don't understand this section: > 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! The same hardware is used for all of these things, and it was only (arguably) designed specifically for graphics (and even there "specific" is not certain).
- nickpsecurity 8y ago"and the only promising path forward (at this time) is parallelism." Don't forget the FPGA's, esp if bundled with CPU. They still partly work by parallelism but I think reconfigurable hardware deserves its own mention.
- jandrewrogers 8y agoAssertions about the difficulty of implementing effective parallelism reflects assumptions about software architecture that are common but not universal. The tools most people reach for tend to be either multithreaded locking of some type or functional "everything is immutable" style, neither of which scale well on real hardware. Complex applications that do use large numbers of cores efficiently use software architecture originally developed on supercomputers but is equally suited to ordinary machines with many cores: fine-grained latency hiding. In practice, this means extremely cheap logical concurrency, like proper coroutines, combined with a latency-aware scheduler (the harder part). This may not be "parallelism" in some strict sense but it has the same effect in terms of utilization and is sometimes used on supercomputers to maximize throughput. Programming languages often have some level of support for necessary primitives, such as goroutines, but then hide them behind an unsuitable scheduler. On the machines where latency-hiding was originally developed as an architecture (notably Tera's MTA), optimal scheduling was done by the hardware itself which had perfect visibility into relative latency with no overhead. Things are not that simple on x86/ARM. If you want to implement effective latency-hiding, you'll be implementing an equivalent scheduler in software, and often by inference because sometimes the only way to know the true latency of something is by doing it. I don't think it is that difficult but schedule design is not something most programmers know how to do well -- it is magic buried in operating systems and libraries. Nonetheless, you see more examples of this kind of software design for performance reasons. There are very few real-world applications that are so serial that latency-hiding is not effective at using all available cores, particularly in the server realm where the workload is inherently concurrent. The original target application for latency-hiding architectures was scaling graph analytics, which are often not amenable to more classical embarrassing parallelism.
- jungler 8y agoMy understanding of AAA game engine coding concurs with this analysis. It's become increasingly common to get more frames of graphics rendered in the same time span by kicking off the next frame before the first has finished, which can be extrapolated to a preconfigured buffer of many frames latency, similar to what is seen today with digital audio. Since game programmers already have to breathe concurrency problems just to achieve real-time stateful systems, and even more so to give an online multiplayer experience, this isn't a huge leap: many issues of this type have been resolved from the beginning with a double buffer or an intentional frame of latency. That said, the benefits of scaling up runtime game performance are diminishing as asset costs increasingly dominate the discussion: the extra scene detail comes with a price to the production cycle, and that may be what breaks the games-graphics-tech alliance before any fundamental limits to the technology are reached.
- mcguire 8y ago"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."
- avmich 8y agoWhat does he mean by "bad locality"? Why depth-first search can't be parallelized?
- lambda 8y ago> 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. While it's true that most of the time a 4-core or more machine has idle cores, I'm not convinced this is a problem. Yes, most of the time spent on a modern computer consists of doing things that aren't particularly computationally expensive. But our perception of the speed of a personal computer isn't based on some kind of steady state performance on batch jobs, I think that worst-case latency is a lot closer to how we perceive the speed of a computer. Of course, in specialized domains like HPC the steady state performance on batch jobs is important, but this article seems to be discussing personal computers. Even if they come up rarely, you still hit computational bottlenecks at times when latency is important. Whether it's some bloated web page, some big Excel computation, a compilation for us programmers, or the like, there are plenty of times where you hit some kind of bottleneck in which you can make effective use of all of your cores, so even if 99% of the time you have idle cores, that 1% of the time can shape your perception of how fast your computer is. And the fact that most of your CPUs are idle most of the time doesn't mean you are wasting power. Modern CPU cores conserve power when idle, via P-States (frequency scaling) and C-States (turning off idle cores). It is probably true that there is a lot of software out there which could take better advantage of parallelism but doesn't, in some cases due to performance not being prioritized, in some cases due to some essential complexity of parallelizing the code, but also in many cases due to accidental complexity of parallelizing code due to unsafe languages like C and C++ that can make it quite difficult to refactor serial code into parallel without worrying about introducing significant bugs.
- smallstepforman 8y agoESR doesn’t know of the Actor programming model. Intersting. In all honesty, neither did I until 16 months ago. Now I’m transitioning our parallel code to an Actor model.
- gpderetta 8y agoNo silver bullets.
- nickpsecurity 8y agoCheck out Pony language. It's like Rust for Actor-based programming. Wallaroo uses it in their production database. So, it's probably decent quality for a new language. https://www.ponylang.io/discover/#what-is-pony https://www.ponylang.io/discover/#what-is-pony
- jillesvangurp 8y agoI'm less pessimistic. IMHO an increasingly big factor is the amount of single core hardware out there that people have tended to optimize for at the cost of not properly utilizing multi core machines for the past decade or so. As quad core CPUs are becoming more or less standard, this is changing already. With 16-32 core CPUs becoming more commom, the pressure is on to utilize those as well. The use cases are much broader than gaming. I'd argue any kind of creative work involving graphics, audio, video, already utilizes any amount of CPU you can throw at it. Also, software like Firefox is leveraging multiple cores with their ongoing Rust rewrite of Firefox. I tend to use multiple CPUs when running software builds. There is a lot UI code that these days is written asynchronously from the ground up; meaning utilizing multiple CPUs is less of a big deal than it used to be. But yes, you need langauges, frameworks, drivers, operating systems, etc. that can facilitate this. I'd say there is quite bit of room for improvement here still.
- crimsonalucard 8y agoDfs is not parallel? Why not fork at every recursive call?
- IshKebab 8y ago> I coined the term “SICK algorithm”, with the SICK expanded to “Serial, Intrinscally – Cope, Kiddo!” Not only is that awful, but something is only "coined" if other people actually use it. You can just say "I will coin this!".