8 ms·

Interesting discussion there too. With modern computers I wonder if explicit parallelism is more fundamental to what our computer science will be than is in vo

• Gh0stRAT 3y ago
  Humans are bad at reasoning about multiple threads simultaneously, so I suspect the more practical shift is the trend we've already been seeing toward more declarative syntax. eg `for` loops are being replaced by `foreach` loops,`map` and `filter` operations, etc. These tell the compiler/interpreter that you want to do some operation to all the items in your datastructure, leaving it up to the compiler/runtime whether and how to parallelize the work for you.
  • MR4D 3y ago
    I would upvote this 100 times if I could. I've thought this way ever since MacOS added the Grand Central Dispatch [1]. Of course, I thought industry would follow quickly and that tooling would coalesce around this concept pretty quickly. Seems the industry wants to take its sweet time. [1] - https://en.wikipedia.org/wiki/Grand_Central_Dispatch https://en.wikipedia.org/wiki/Grand_Central_Dispatch
    • cpgxiii 3y ago
      I mean, OpenMP dates back to 1997 (1998 for C and C++). Apple, however, has never supported it for what can only be selfish reasons (particularly since Clang has a quite good implementation provided by Intel, which can easily be installed on a Mac if you want). GCD came a decade later. For basic parallelism, nothing beats OpenMP for ease of adapting existing code (often a single "#pragma omp parallel for" directive is enough). Even for more complex parallelism, particularly where per-thread resources need to be managed, OpenMP still provides a much simpler programming model than the alternatives.
      • Jtsummers 3y ago
        OpenMP and GCD solve different problems. You'd not want to use GCD to parallelize the same tasks you're parallelizing with OpenMP in most cases. GCD is more suited for the one-off cases (toss this task into the queue, toss that task into the queue; or "as we get new items from the user toss the processing into the queue" but we don't know the rate of new items coming in so batching doesn't make as much sense), vice OpenMP which is targeting things like scientific computing/simulations where you know you have a million objects you want to perform a computation on. The GCD version of the same would be slower by a large measure if you spawned a task per work item or you'd recreate parts of OpenMP to divide the work across a smaller number of tasks. And you wouldn't want to use OpenMP for parallelizing the kind of things you toss into a work queue model like GCD offers.
        • cpgxiii 3y ago
          Sure, OpenMP and GCD provide different interfaces around the same concept of a managed threadpool. Given both, one would use them for different tasks (in the same way one actually uses OpenMP and std::async for complementary purposes). But in the context of GP's basic parallelelized for/map/reduce operations, either can be used fine (although OpenMP would probably be more pleasant to write).
          • osigurdson 3y ago
            I'm not familiar with GCD but after reading the wiki page, I'd say most languages have something like that: a queue that you can add things to, items can then be processed by multiple threads of execution. I'd also say that most languages have something similar to OpenMP, parallel for loops, etc. Great if you have some read only data in arrays and wish to process it. However, in my opinion, it doesn't really matter how convenient a parallel / async programming model is to use as the real work is ensuring that there isn't any shared mutable state being updated in parallel. The other issue is, once you have formulated / re-formulated a particular problem to this model, ensuring that it remains this way is pretty challenging on larger teams. Someone can easily unknowingly commit something that breaks such assumptions.
    • dogleash 3y ago
      > Seems the industry wants to take its sweet time. We're inching towards an in vogue way to do what erlang had figured out in the 80's. We'll pick up the pace any day now. Surely.
    • o11c 3y ago
      Grand Central Dispatch is famous for breaking tons of old programs for the grave sin of trying to `fork` a child process.
  • Affric 3y ago
    I agree to a large extent but I am referring more to our teaching of Computer Science. For our teaching of Software Engineering I think you're largely correct. > Humans are bad at reasoning about multiple threads simultaneously I am not so sure this is true, I do believe that people are poorly practiced. My experiences have led me to believe Universities silo explicit parallel programming too much. It's generally it's own non-compulsory subject in a Comp-Sci major.
  • johnloeber 3y ago
    Yep! The only thing that remains is to focus on that code being properly functional; i.e. avoiding side-effects. Side-effects and parallelism don't mix well. Wonder if this will give rise to more functional languages.
  • FpUser 3y ago
    >"Humans are bad at reasoning about multiple threads simultaneously" Humans are bad at reasoning about way too many things. I think mostly because many are lazy and do not want to learn. The ones who do have little problems. I do not find thread management particularly hard for the most parts (there are some exceptions but those are very uncommon).
    • mrkeen 3y ago
      Fine then. Your compiler is bad at reasoning about multiple threads simultaneously.
      • FpUser 3y ago
        So how my compiler reasons about multiple threads?
        • deleted 3y ago
          [deleted]
        • mrkeen 3y ago
          > Reads and writes do not always happen in the order that you have written them in your code, and this can lead to very confusing problems. In many multi-threaded algorithms, a thread writes some data and then writes to a flag that tells other threads that the data is ready. This is known as a write-release. If the writes are reordered, other threads may see that the flag is set before they can see the written data. > Reordering of reads and writes can be done both by the compiler and by the processor. Compilers and processors have done this reordering for years, but on single-processor machines it was less of an issue. https://learn.microsoft.com/en-us/windows/win32/dxtecharts/lockless-programming https://learn.microsoft.com/en-us/windows/win32/dxtecharts/l...
          • FpUser 3y ago
            >"In many multi-threaded algorithms, a thread writes some data and then writes to a flag that tells other threads that the data is ready. This is known as a write-release. If the writes are reordered, other threads may see that the flag is set before they can see the written data." This is why we have things like WaitForSingleObject and many other that deal properly with the chance of reordering and other concurrency related issues. All is fine with the reasoning on CPU, OS, Compiler and my own level. One just have to understand what is going on and know the tools. Those who are setting boolean flag to indicate the data is ready should not be programming for modern CPU's and have a basic knowledge first.
  • psalminen 3y ago
    I like the way you word this. Similar to the product I make, I describe my mind as an asynchronous queue. I can only reason about one thing at a time, but when I do that is fairly random. How this has played out in my life gives me caution about making this standard in computing.
  • lionkor 3y ago
    C++ has had std::execution_policy for a long time now - you pass that with an algorithm like sort, for_each, etc. and it will choose a way to parallelize that for you.
  • minikomi 3y ago
    Shades of clojure's transducers
  • tester756 3y ago
    >eg `for` loops are being replaced by `foreach` loops,`map` and `filter` operations, etc. These tell the compiler/interpreter that you want to do some operation to all the items in your datastructure, leaving it up to the compiler/runtime whether and how to parallelize the work for you. There's difference between doing it in order 1, 2, 3 and 3, 1, 2. foreach will not be replaced behind the scenes into multithreaded version since it changes behaviour. for is replaced with foreach because usually you dont need index and foreach is just handier and safer, that's it. .NET's std lib has Parallel.ForEach for such a thing. We really don't need magic to write multithreaded code. All we need is just really, really well designed APIs and primitives.
    • Gh0stRAT 3y ago
      >foreach will not be replaced behind the scenes into multithreaded version since it changes behaviour. It only (meaningfully) changes behavior if you're both iterating over an odered datastructure and the body of your loop has direct or indirect side-effects. (like printing, writing to a file, making network requests, etc)
      • dragonwriter 3y ago
        > It only (meaningfully) changes behavior if you're both iterating over an odered datastructure and the body of your loop has direct or indirect side-effects. Right, and not always even then, because that depends on what the consumer is concerned with as well. But the fact that it can means it's not a safe automatic substitution.
      • tester756 3y ago
        >nd the body of your loop has direct or indirect side-effects So like... huge % of the real world code bases
        • Gh0stRAT 3y ago
          Unfortunately yes. That being said, the hottest loops that would benefit the most from added parallelism tend to have fewer side effects already in my experience so things aren't quite so bleak.
  • imtringued 3y ago
    How about some HDL semantics with implicit pipelining... Every statement in a HDL language runs in parallel but you can still write implicitly sequential code in VHDL processes.
  • Tarq0n 3y ago
    Considering the developments in data engineering land I wonder if we'll be describing our operations as a DAG rather than maps and folds specifically.
  • graemep 3y ago
    Is the difficulty reasoning about threads a bit more specific than that? I think it is reasoning about threads with shared mutable state.
  • likeabbas 3y ago
    There will still be cases where more fine tuned control is warranted. Rust has done this very intelligently by moving data race controls to the compiler level.
  • pjmlp 3y ago
    It is more like the mainstream world is finally catching up with the world promised by functional programming since Lisp and parallel computing exists. Only now I can enjoy in modern hardware what I had to imagine when reading papers about Star Lisp and the Connection Machine, alongside other similar approaches.
• jeremycarter 3y ago
  I think this is why I'm a huge advocate of the Actor Model.
  • jacquesm 3y ago
    Likewise, it is one of the best solutions to this problem. And it also nicely maps onto language constructs, much nicer than the other options that I've worked with.
    • jeremycarter 3y ago
      Perhaps it can be Actors turn to have some hype this decade?
• samsquire 3y ago
  LMAX Disruptor has on their wiki that average latency to send a message from one thread to another at 53 nanoseconds. For comparison a mutex is like 25 nanoseconds and more if Contended but a mutex is point to point synchronization. The great thing about the disruptor it is that multiple threads can receive the same message without much more effort. https://github.com/LMAX-Exchange/disruptor/wiki/Performance-Results https://github.com/LMAX-Exchange/disruptor/wiki/Performance-... https://gist.github.com/rmacy/2879257 https://gist.github.com/rmacy/2879257 I am dreaming of language that is similar to Smalltalk that stays single threaded until it makes sense to parallise. I am looking for problems for parallelism that are not big data. Parallelism is like adding more cars to the road rather than increasing the speed of the car. But what does a desktop or mobile user need to do locally that could take advantage of the mathematical power of a computer? I'm still searching. I am thoughtful of the Itanium and VLIW architecture for parallelism ideas.
  • Affric 3y ago
    > I am looking for problems for parallelism that are not big data. Parallelism is like adding more cars to the road rather than increasing the speed of the car. But what does a desktop or mobile user need to do locally that could take advantage of the mathematical power of a computer? I'm still searching. The things we currently let servers do but it would mean we can keep user data local and not hand it over to service providers. I believe that is a worthy end goal.
  • tmountain 3y ago
    It sounds like you are thinking about concurrency more than parallelism. The answer to your question is very general at a high level. Any task that can be broken up into chunks benefits. In the simplest terms, tasks that can be computed in buckets with a final result computed from those buckets will benefit from concurrency. Think of a video game as a good example. Environment calculations are happening in the background while the main game loop is processing. There are almost infinite use cases and examples, so I won’t try to enumerate them all.
  • sitkack 3y ago
    Pervasive parallelism could make massive efficiency gains in computation possible. If we could move many work loads to hundreds or thousands of threads we could run it much lower clock frequencies and thus lower power. It could also enable the use of cheap, small in order cores, further boosting core counts. Multithreading doesn’t always have to be around increasing speed, it can also reduce power
• ketralnis 3y ago
  Can you talk about the difference between what you're calling explicit parallelism and said textbooks?
• xboxnolifes 3y ago
  As I see it, parallelism is in the same vein as memory management. Most of what we program can, and should, use some form of automatic management, and manual management is reserved for the areas where it is needed for performance. It's an implementation detail, and if we can abstract it away to make it easier to utilize, we should.
• dmead 3y ago
  Aren't we already?
• Jtsummers 3y ago
  Do you mean implicit parallelism? Because what we have now is typically explicit paralellism. Creating a thread or forking a subprocess is explicit parallelism, the programmer chooses that option. A function like `map` that can utilize a parallel or sequential implementation depending on circumstances the runtime or compiler are aware of without direct input from the programmer would be implicit parallelism. If the `map` function takes an execution context that signifies parallel or sequential execution then we're back to explicit.
• eslaught 3y ago
  Parallelism in CS is a bit like security in CS. People know it matters in the abstract senses but you really only get into it if you look for the training specifically. We're getting better at both over time: just as more languages/libraries/etc. are secure by default, more now are parallel by default. There's a ways to go, but I'm glad we didn't do this prematurely, because the technology has improved a lot in the last decade. Look for example at what we can do (safely!) with Rayon in Rust vs (unsafely!) with OpenMP in C++. And there are things even further afield like what I work on [1][2][3]. [1]: https://legion.stanford.edu/ https://legion.stanford.edu/ [2]: https://regent-lang.org/ https://regent-lang.org/ [3]: https://github.com/nv-legate/cunumeric https://github.com/nv-legate/cunumeric
  • eyegor 3y ago
    See also https://github.com/cupy/cupy https://github.com/cupy/cupy https://github.com/inducer/pyopencl https://github.com/inducer/pyopencl
  • winter_blue 3y ago
    What's the difference between Legion and Regent, by the way? I noticed the Regent code is inside the Legion repo. Is Legion the system, and Regent the language? Can Legion be used without Regent, or vice versa?
    • eslaught 3y ago
      Legion is a C++ runtime system. It exposes APIs in C++ and C. You can write code directly to it with C++ (and CUDA/HIP/SyCL if you want to use GPUs). But the only requirement is a C++ compiler and standard build system (Make/CMake). Regent is a programming language. The compiler for Regent generates Legion code. Semantically, Regent is mostly a simplification of Legion. There are fewer moving pieces, so fewer things you need to worry about. Many of the "gotchas" that exist in Legion are taken care of by the language/compiler so idiomatic code usually "just works". It also does GPU code generation for you so you don't need to hand-write CUDA/HIP/etc. The tradeoff is that you're using a new programming language, so you have to be willing to take that risk.
  • 3y ago
• jacquesm 3y ago
  Reasoning about parallel execution is hard. You need high level language and library support for that unless you want to spend the rest of your life in tricky debugging territory.
• User23 3y ago
  The formalisms for nondeterminism are over half a century old now. This is fundamentally a solved problem, although the typical case analysis technique many programmers tend to prefer falls down hard. Incidentally that’s why unix signals suck.
• dehrmann 3y ago
  Parallelism ended up going off in a few different directions. For things like running a web service, requests are fast enough, and the real win from parallelism is in handling lots of requests side-by-side. This is where No-GIL comes in. Within handling a single request, if there are a lot of sub-requests, that's usually handled by async code, but not so much for the async performance win as much as spinning up threads is either expensive or thread pools are a hassle. Remember that async is better for throughput, but worse for latency, and if you're parallelizing a service request, you're probably more worried about latency. Async won mostly on ergonomics. The other place you see parallelism is large offline jobs. Things like Map-reduce and Presto. Those tend to look like divide-and-conquer problems. GPU model training looks something like this. What never happened is local, highly parallel algorithms. For a web service, data size is too small to see a latency win, they're complicated, and coordination between threads become costly. The small exceptions are vectorized algorithms, but these run one one core, so there isn't coordination overhead, and online inference, but again, this is heavily vectorized.
  • rsaxvc 3y ago
    > What never happened is local, highly parallel algorithms. GPUs maybe? Also, excellent answer.
• fulafel 3y ago
  It seems serious parallel programming has mostly gone with shader/ISPC style data-parallel computation with low-level languages and the old school threads & locks model has been relegated to a side support role lost except on the CPU side. There's interesting stuff going on in the VHLL world with languages like Futhark, Jax, Mojo, etc that would be a better peer group for Python and its high level of abstraction.
• imtringued 3y ago
  I am more of a fan of finding implicit parallelism. You could think of a given problem as a heap of spaghetti. If you can untangle the mess, then each noodle might still be sequential, but you can process them in parallel. If you can find enough independent sequential problems in your programs then you can easily fill up cores, mostly because we don't have that many. I only have eight. The problem is that this requires additional graph processing and there it makes your programs slower, which kind of defeats the point. The goal is to find the right tradeoff.
• spullara 3y ago
  As soon as computers had 4+ cores we should have been going hard on it.