Parallel Programming

This is a thread to discuss various systems for writing parallel programs, at any level of abstraction, from the bare machine to a high-level language. It seems reasonable to say that it's easiest for most of us to think sequentially, when programming. It's somewhat difficult to consider machines in which every instruction operates ``at once'', at least for complex tasks. Even cells have some manner of sequential behavior. It's certainly easiest for me to consider parallel operation as sequences of sequential instructions happening in not necessarily meaningful orders; how do you consider parallel operation most easily? Which method(s) do you prefer to write a parallel program? Do you prefer dataflow, where you build pipelines of sorts? Is it instead the event-driven method, in which one provides an interface and actions and largely leave it at that? Is simple multi-threading, needing no introduction, your favorite? Do you prefer to ignore these details and let the system parallelize your programs for you? Do you prefer a system or method I've not mentioned; if so, do explain it. An example I like of a program in which every instruction executes ``at once'' is a program that calculates an approximation of a sum by each instruction calculating each individual value and adding them to the same location. This ignores populating memory with these instructions.

I am a fan of simple multithreading, but with green threads (like Haskell's threads, Erlang's processes, or Go's goroutines). There are two types of threads a program may use: operating system threads, managed by the kernel; and green threads, managed by some userland library. - Context-switching between OS threads is quite expensive, which is why the conventional wisdom is to do things like have one thread per core and distribute work between them, or have some other form of small thread pool. After a point, the more OS threads you have, the worse your program performs: it's spending so much time context-switching that it's getting nothing done! - On the other hand, context switching between green threads can be incredibly cheap. This is because your program doesn't need to go all the way to the kernel and its scheduler. It's even possible to do more intelligent scheduling, based on knowledge of the program semantics which the OS scheduler doesn't necessarily have. Green thread implementations will generally use one OS thread per core, and multiplex the green threads onto them. But because it is totally transparent to the programmer, you can create thousands (or millions!) of green threads on the same machine, with good performance. Multithreading when you don't need to keep track of how many threads you have, which cores they are running on, and what work they are doing, is much simpler. For example, in any sort of server program, you can just fork a new thread per request. This is the simple and obvious behaviour which people start out with, but switch away from due to the pitfalls of OS threads.

>>692 >There are two types of threads a program may use: operating system threads, managed by the kernel; and green threads, managed by some userland library. You dont know what youre talking about, the two kinds of threading models are thread locking where only one thread can run at a time while the other threads have to wait. All operating systems use this concurrency model, it obviously doesnt scale to multiple servers. And then there is message passing where many threads can run at the same time and this can scale across many server nodes. There are Big Data systems like Hadoop which takes message passing to huge levels. They break up search tasks on redundant data and perform them across multiple servers.

>>698 What are you talking about? >locking If one thread is running, another cannot run on the same core. This is obvious. I didn't contradict that. >multiple servers When did I say anything about multiple servers? >message passing Message passing is a way that threads may communicate, it has nothing to do with how the threads are actually scheduled.

>>700 >Message passing is a way that threads may communicate, it has nothing to do with how the threads are actually scheduled. that true, but the point I am making is that thread locking is always dependent on a scheduler on one computer and message passing is not

>>702 That's because communication is at a higher level of abstraction than how threads execute.

I've had some experience with writing parallel programs as part of my degree. I've used OpenMP, MPI, OpenCL and CUDA (and also had a brief look at pthreads and C++11 threads). I find MPI hard to deal with, but the benefits are huge in terms of performance if you can use multiple CPUs. OpenMP is usually the easiest to use but it is interesting to note that I have been able to get better performance out of OpenCL (on the same CPU), providing the problem size is large enough to outweigh the higher overhead. Obviously the problem with CUDA is that it's proprietary and the problem with OpenCL is that most implementations are proprietary (I've never got Beignet to work). Honestly now that I'm used to the OpenCL API I'd much rather use it than anything else, especially for one device. I guess for multiple CPUs MPI is king.

>>692 seconding. Green threading + functional programming = the most sane way to do concurrency

>>591 loss

>>742 lmao

So, I've written a program that performs a repetitive and simple task that can be split very finely into as many parallel units as I care to use. I currently use less than ten, as it's more than sufficient for my purposes. It also doesn't matter if these processes fall wildly out of sync, as there's no need to sync in the first place and they randomize behavior anyways. I've a lock I use in only one place at the beginning of an action and during error handling; the lock is obtained, a quick action is performed, and the lock is released; I'm going to need locking behavior in a more frequent part of the program now, as well, for a shared resource, which will also be accessed and released quickly. I see no strong reason to not simply reuse the same lock, as it's already named as a lock and adding another lock would only increase the size of the program and add another lock in memory. What do you think of this approach? I don't see any harm in it.

This was the first book about programming I ever downloaded. "I'm going to learn programming in a couple of months, this sure looks helpful"

I wrote a priority queue to benefit from parallelism. I was using OpenMP and my problem was that I needed as way to shift an array in parallel so I made the array twice as long and gave every element a read safe location. Either at the end or beginning of a PQueue sift/insert however you implement it, you update the read safe slots with the primary slots. That made shifting very easily, but multiple shifts require the read safe slots be updated. You can shift by 2, but not by 1 then 1 without resetting. OpenMP is annoying though since it's only good for certain tasks.

>>1992 Using two separate locks will improve performance as the two unrelated critical sections won't block the other. Unless you are already running out of resources (are you on some embedded device?), I doubt that a single additional lock will significantly bloat your program. But if you really care about it you could just measure the difference.

>>698 This is not correct

I found these videos by a guy I'm subscribed to on youtube to be a smooth yet pragmatic intro to parallelism specifically in the domain of C/++: https://www.youtube.com/watch?v=Pc8DfEyAxzg https://www.youtube.com/watch?v=MfEkOcMILDo https://www.youtube.com/watch?v=kIA_UtdVabQ https://www.youtube.com/watch?v=_z-RS0rXg9s

I have to develop a C++ parallel programming project for college. The task is arbitrary. The reference framework we're encouraged to use is FastFlow ( http://calvados.di.unipi.it/ ), as it's developed by researchers from our university, among others. FF is pretty fine; it works well and is very high level, but it's also ugly as sin and suffers from the many eccentricities of C++ template programming. Do you lains have any framework you would like to suggest? Maybe something innovative that could pique both mine and my prof's interest? The target architecture is a manycore CPU (we'll do the benchmarks on a Xeon Phi), so no FPGA or GPU or such.

>>3295 Boost is pretty good and used everywhere. It also has parralell programming support

How do people usually do parallelization when they want minimal overhead? I'm working on some tools (in c) to do simple image processing (filtering, layer merge, etc) and I don't want to have to spawn pthreads or an opencl context or whatever because the program basically just pulls in an image file, does a matrix operation, and dumps the result. I've looked into compiler/automatic parallelization, but I don't really know where to start. Is that the best way to go about it? I know I should probably just use a functional language, but this problem comes up often enough in the types of c programs I write that I'd like to find a solution.

>>3299 >I don't want to have to spawn pthreads or an opencl context or whatever Threads and processes are the only parallelization primitives your Operating System has. Pick one. >How do people usually do parallelization when they want minimal overhead? What do you mean by "overhead". These "functional languages" you allude to are not magic. Just because you type less code doesn't mean it's faster or that fewer things are going on in the background. If you want pretty abstractions to hide the complicated reality from you then C is the wrong language.

>>3299 Pthreads are actually fairly lightweight since they're very low level, don't be be afraid to use them. If anything, they're too basic. If they really are too much for your domain, however, you can take a look at the manual page for clone , which is the system call used in Linux to spawn threads. It basically lets a process spawn a new process within the same memory space. As a remark, though, when we talk parallelization overhead in a shared memory architecture we generally refer to the managing costs necessitated by the pattern you're applying: event loop, pipeline, farm or whatever. The cost of spawning threads per se is usually vastly inferior to the cost of coordinating them. Also, if all you're doing is algebra consider a framework that can offload to the GPU.

>>3295 C++ is... not good for this. Honestly, I've had the best luck just writing a simple thread pool with C++11 threads and divying up your tasks in an intelligent fashion. If you're working on large datasets it becomes a lot easier since you can make your tasks bigger. The highest core count I've ever worked with is 64 though so ymmv.

>>3299 If you're willing to switch to C++, Intel has a not-so-well-known library called Threading Building Blocks. It's been my go-to when it comes to parallel programming ever since I heard of it for the first time. It allows for efficient mapping of tasks to threads much like Go's goroutines. It's also got many advanced features, like data structures that are designed specifically for concurrent use with minimal locking (with interfaces compatible with their std:: equivalents so it's easy to switch), but simple stuff like parallel for loops is also really easy to do. If you want to stick to C, I think that OpenMP is your best bet when it comes to efficiency (it's less efficient than TBB on my computer though), it has far less features, but a plus is that all of the parallelism is done through #pragma s, which means that a program can be compiled (albeit without parallelism) even by a compiler that doesn't support it.

hell is a: SEMAPHORE

>>692 >>740 Green threads are nothing but koolaid. Every major language that uses them lived on to deeply regret it. You call these things threads yet only one of them will ever execute at a time. I don't care how many operating system threads your language's implementation maps them to, it's guaranteed to have a global lock that prevents more than one "thread" from executing at any given time. They're coroutines with a scheduler. They cannot take advantage of multiprocessor hardware. You have concurrency but you do not have parallelism. The only real use case they support is yielding the processor when the code makes system calls. The implementation knows to release the lock in these cases; it's the only situation where you have actual parallelism... Even though one of the "threads" isn't actually executing much, it's just waiting for the system call to return. People like to call these things "lightweight", as if they somehow used less resources than whatever your operating system provides. Wake up. Your "threads" have stacks too. This simple fact will put a hard limit on how many you can have in memory. pthread on Linux allows you to set a minimum stack size of 16 KB. Go uses something like 8 KB per goroutine; possibly more in newer versions. If you have 4 GB of free memory, you can maintain 250 000 pthread s and double that amount of goroutines. Not such a big difference, especially considering the default Linux stack size is 8 MB and that pthread gives you actual parallelism. If you're actually running at this scale, chances are you are writing a web server; asynchronous programming with event loops is vastly superior to threads with respect to network socket I/O and uses a lot less memory. Goroutines are meant to support language-level concurrency; this does NOT imply parallelism. The thread is about parallel programming, not concurrent programming. This kindergarten where "threads" are easy and there's no locking only exists because it's not actually parallel. >For example, in any sort of server program, you can just fork a new thread per request. This is the simple and obvious behaviour which people start out with, but switch away from due to the pitfalls of OS threads. They will just as easily switch away from silly "green thread" implementations. They have exactly the same pitfalls of operating system threads. Just because you allocated a little less memory for a stack doesn't mean your soykaf is scalable. Overhead of one execution stack per accepted connection is quite simply stupid and "green threading" libraries do exactly nothing to change that fact. All they do is recreate an operating system function in user space and lie to people by promising "speed increases" of undefined nature. It's the kind of brain damage you find in CS research papers, like fuarrrking microkernels.

>>692 >It's even possible to do more intelligent scheduling, based on knowledge of the program semantics which the OS scheduler doesn't necessarily have. Yet another lie. Just because the kernel doesn't know or care about what your code is doing doesn't mean you have to go out and implement a god damn scheduler in user space. That is quite simply stupid. What you do is inform the kernel so that it can properly manage your soykaf. Some Google person experimented with this. They introduced new SwitchTo system calls to Linux that let them inform the kernel that some thread is not going to execute anymore. So the Linux scheduler gives two threads some quantum of time and one thread is still waiting on some system call. What the language implementation does is tell the kernel that the blocked thread is done for now and that it can schedule the second thread. The kernel does just that, allowing the second thread to use the remaining quantum of time without having to incur scheduling overhead again. This is simpler and better than some brain-damaged "green threading" implementation. I'm not sure if these improvements made it into upstream but Google is probably using these patches themselves. This is how you do things. You play nice with the kernel. What you don't do is build soykafty abstractions on top of it because you think it's too hard to understand or program with. What you most definitely don't do is reimplement features the kernel is already excellent at as monstrous user space libraries.

>>4185 >>4186 two issues: for distributed systems, you don't have a single kernel to manage your tasks for you. You *need* an abstraction layer, there's no way around it. Also, except for very small fast microkernels(L4 comes to mind), context switches are expensive.

>>4194 >distributed systems >abstraction It all depends on what you want. Erlang engineers decided copying around data all over the place was cost-effective considering the intended use of their language, so the language has no shared memory. If you want distributed computing, obviously you're going to need to incur the cost of copying data around, due to the simple fact they haven't invented networked RAM yet and even if they had it would have been slow compared to motherboard north bridge. Doesn't mean every single parallel programming system needs to be like that. >context switches are expensive Some tens of nanoseconds. Please. >only microkernels are fast The system calls are fast but then you realize you have to copy data all over the place through your silly kernel message passing mechanism, and then it's not just your language that's slow as soykaf, it's your entire operating system and every single program running on it.

>>4199 >Some tens of nanoseconds. Please. suppose you have 10 thousand threads. It adds up fast. >then you realize you have to copy data all over the place through your silly kernel message passing mechanism I referenced L4 specifically for a reason.

>>4199 >Some tens of nanoseconds. Please. I mean, even in normal programming situations I'd avoid context switches. However, it really depends how you schedule things. If you are smart, you can limit the number of context switches and limit the bottleneck. > it's your entire operating system and every single program running on it. To be fair Microkernals are usually used for integrity, not performance. You could follow that logic backwards and say that by reversing the trend and putting more tasks in the Kernel - at the cost of safety and ease of use - you could increase performance where needed. >You *need* an abstraction layer, there's no way around it. Yeah but that doesn't mean that the abstraction layer closest to the metal can't interact with low level parallelism primitives. Obviously for something like a massive distributed system I wouldn't count on something like green threads to divvy up the work. >I referenced L4 specifically for a reason. I mean, that's a totally theoretical argument. Is there anybody doing any kind of significant parallel computing on something like L4? To my knowledge Microkernels are mostly used in embedded systems and high reliability systems. Nearly ever massive data crunching operation I've seen has been on some kind of Linux, and I really can't imagine there existing a Microkernel that would be appropriate for the job. And I suppose if you really needed that sort of operation to go down on a small embedded system, the way to go would be to make an FPGA or something that rigs up the parallelism in hardware. Talking out of my ass on that one, but that's how I'd go about it if I needed some serious number crunching on a tiny computer. Your home router likely agrees with me.

>>4206 >I really can't imagine there existing a Microkernel that would be appropriate for the job. you're not wrong, but I was referencing how in every system except for very fast microkernels context switching and IPC can be very expensive, not how they are particularly suited for parallel computing.

>>4210 Yeah and my point is that it's not worth considering fast context switching since it's not a practical option. I agree with you.

Whenever I consider this topic, it feels like general parallel operations are still largely sequential and massively parallel operations are largely trivial. So, it feels strange to make a difference between parallel and sequential program in the way this is often done, because you can have purely sequential and a combination, but purely parallel seems only capable of trivial things, in comparison, but this could simply be my lack of familiarity or a vague notion of what being purely parallel is. What do you think?

>>4210 >except for very fast microkernels context switching and IPC can be very expensive Context switching is expensive no matter the OS (it's usually the single biggest slowdown with a normal workload) and it's not something you can measure as "10s of nanoseconds per thread" either. The slowdown comes not from the length of the operation itself but from the cache flushes it entails. Microkernels usually spend a lot more time context switching btw just because they do it more. Exokernels are a better example of an OS that does it less. The switch itself will be roughly the same no matter your kernel architecture. "Green" threads (I've never actually heard that term, userspace threads seems better but whatever), have the upside that they don't context switch and the downside that they don't context switch. I could easily write an OS (temple OS does this) that never flushes caches on context switch by using a single system wide address space and it's when we look at this that we see the big problem. You're sacrificing security for efficiency, which is fine in some contexts but not universally. Let's take the web server example and imagine it has a nasty buffer overrun that let's someone execute whatever code they want. With userspace threading our attacker can read everything about the other requests being handled. With OS threading they cannot, the memory just isn't mapped into the address space they've taken control of.

>>3295 OpenMP is pretty much the standard.

>>8153 Of course. Microkernels are supposed to be a reliability improvement, not a performance one. I do wonder if you could have your cake and eat it too. I agree that flushing the cache is necessary on real systems, but I wonder if the security of cached data could be made the responsibility of the CPU. Imagine this: The CPU's cache has two bit memory. Every cell of cache memory has two bits, one to two the intended data, and a second to mark the data as kernel or user data. Of course, as it stands today this would represent a massive hit to cache sizes and performance. However, I predict that as more logic as added to CPU's, this might become a doable configuration. Another architecture I thought of exploring is a duel cache system. This isn't unprecedented, Harvard architectures often have separate caches for data and instructions. In my spin on the system, I would have a physically separate cache for Kernel and user data. I imagine there are performance and architecture reasons why this would be a bad idea, but I believe that the architecture designs of the future will explore more complex set ups like the ones I described. We will eventually have so many gates that designers wont have a problem dedicating many of them to "smarter" components. Reconfigurable components may also allow once unthinkable designs to become viable.

I see a great deal of flack concerning OO online. Firstly, I refer to real OO in this post. I don't see the difference between OO and so-called microservices. This seems to me to simply be a realization of OO. I believe Alan Kay has said the Internet is a good example of OO or some of the principles of it. I find OO to perhaps be the most natural parallel programming paradigm, but I don't have a great deal of exposure to others. Do you agree or is there a different paradigm you find most natural? I can agree that automatic parallelization is the most desirable, but that does relegate parallel execution as an optimization and nothing more. That may be the correct way to look at it, though.

>>11156 Data-oriented design http://www.dataorienteddesign.com/dodbook/

>>11156 pure functional programming. no shared mutable state to worry about. and data oriented design. limited hidden state makes it easier to safely parallelize operations.

I've been learning Ada these past few months and it's informed my ideas of how some languages should handle parallel programming. Ada has tasks and protected objects, each can be one-off or reusable types; tasks have entries you can invoke, only any one at a time, and these are called rendezvous; protected objects are basically thread-safe data so you don't need to manually manage locks. If you pay attention, the system is carefully designed so that memory allocation for queuing isn't necessary, as everything can preallocate a constant amount. In brief, I don't really think I should ever play with locks manually again. No, that should be done for me.

>>8153 >>8385 https://blog.darknedgy.net/technology/2016/01/01/0/ tl;dr look at QNX and L4 before saying that microkernels are slow.

I recently read this paper on the Reduceron, a machine specialized for Haskell. It's fascinating, because it takes advantage of some of the parallel possibility of the Haskell programs it executes, by virtue of parallel memory access. It also has other neat qualities, such as hardware laziness and replacing applications in memory with the result to avoid needless recomputing, but I'm concerned with the parallelism here. I'm led to believe implicit parallelism like this is still perhaps the best option. It allows the programmer to specify the correct ordering for those components which need it, and then merely avoid specifying the other ordering, to get parallel execution without effort, given an appropriate language and environment. The more literal control the programmer avoids, the more the program can be made parallel by the machine.

What are the nicest experiences you've had with multithreading? >Actor model >CSP >Borrow checking >Auto iterator parallelization >DIY I recently used Rust's Rayon library for some simple multithreading and it was really nice.