8

Following along with the principle of not optimizing too early, I'm wondering at what point in the design / development of a piece of software do you start thinking about the concurrency opportunities?

I can well imagine that one strategy would be to write a single threaded application, and through profiling identify sections that are candidates to run in parallel. Another strategy I've seen a little of is to consider the software by groups of tasks and to make the independent tasks parallel.

Part of the reason for asking is that of course, if you wait until the end and only refactor the software to operate concurrently, you may structure things in the worst possible way and have a major task on your hand.

What experiences have helped to determine when you consider parallelization in your design?

7

The thing about thread tasks is you want high cohesion, low coupling, and good encapsulation. Interestingly enough, those happen to be worthy design goals for single-threaded applications as well. I had a task today that I didn't originally plan on parallelizing, but when I did, it involved little more than renaming a function to run() and changing how it was called.

Not optimizing too soon means don't put everything in a thread "just in case," but neither should you paint yourself into an architectural corner so it will be too difficult to optimize should the need arise.

1
  • Yes, re-entrant functions, work queues and that like can help in single threaded as well as in multithreaded applications, but they also allow for good extensibility toward parallel processing later. Which saves a lot of headache with synchronization problems later.
    – Coder
    Aug 25 '11 at 23:41
2

Java programmers should embrace the Callable interface for work units. If your whole application consists of a loop of creating Callables, shipping all the units of to an Executor, handle any post generation tasks, you have something that can be very easily be shaped into serial processing, "three work queues" and "do all at once" simply by picking the right executor.

We are slowly adapting this pattern as it is very common that the serial approach gets too slow at one point and then we need to do it anyway.

1

It varies with the project. Sometimes it's very easy to see what can be made parallel: perhaps your program processes batches of files. Suppose that the processing of each file is completely independent of all the other files so it might be quite obvious that you could process 1 file at a time, or 10, or 100, and none of these jobs will impact the other.

It gets a little more complicated when the potential parallel jobs aren't the same. Processing an image file, you could have one job that creates a histogram, another that produces a thumbnail, and maybe another that extracts EXIF metadata and then a final job that takes the output of all of these jobs and stores them in a database. In this example, it's maybe not clear if these should be run in parallel, or if they should (the last job will have to wait for the prior jobs to all complete successfully).

In my experiences, the easiest way to parallelize something is to look for processes that could be run as independently as possible (like in the first example) and start with those. I'd only try to make the second example run in parallel if I thought I'd make a significant gain in performance with it.

1

You must design concurrency into your application from the beginning. Normally as an optimization I would agree that it should be left until later if not inherently obvious. The problem is that concurrency may well require re-architecting your application from scratch in the worst case- some systems are virtually impossible to have concurrency tacked-on. An easy example of this is systems which share data- for example, the simulation and rendering aspects of a game.

0

I would say that threading is a part of the architecture of the application. So it is one of the first things I need to think of.

E.g. when I do a GUI application, the GUI code is single threaded so long running tasks (e.g. XML processing) would block the GUI, and should be run in a background thread instead.

E.g. a server would either be thread-based, where each request is handled by a new thread, or the server could be event-driven and use only one thread per cpu-core, but then again, long running tasks should be run in a background thread or be divided into smaller tasks.

0

With the way I approach things, multithreading kind of comes free of charge and relatively straightforward to apply in hindsight. But I'm thinking about data first. I don't know if this works for all domains but I'll try to cover how I go about it.

So first it's all about the coarsest kind of data required for the software that will be processed frequently. If it's a game that might be things like meshes, sounds, motion, particle emitters, lights, textures, things of this sort. And of course there's a lot to think about if you drill down to just meshes and think about how they should be represented, but we'll skip that for now. Right now we're thinking at the broadest architectural level.

And my first thought is, "How do we unify the representation of all of these things so that we can achieve a relatively uniform access pattern for all of these types of things?" And my first thought might be to store every single type of thing in its own contiguous array with a free list-type way to reclaim vacant spaces. And that tends to unify the API so that we can more easily, say, use the same kind of code to serialize meshes as we do lights and textures, at least as far as where and how these components are accessed. The more we can kind of unify how everything is represented, the more the code accessing those things tends to take on a uniform shape.

That's cool. Now we can also point to these things with 32-bit indices and only take half the memory of a 64-bit pointer. And hey, we can do set intersections in linear time now if we can associate a parallel bitset, e.g. We can also associate data to any one of these things very cheaply in parallel since we're indexing everything. Oh and that bitset can give us back a set of sorted indices to traverse in sequential order for improved memory access patterns, not having to reload the same cache line multiple times in a single loop. We can test 64-bits at a time. If all 64-bits are not set, we can skip over 64 elements at once. If all of them are set, we can process them all at once. If some are set but not all, we can use FFS instructions to quickly determine which bits are set.

But oh wait, that's kind of expensive if we only wanted to associate data to a few hundred things out of tens of thousands of things. So let's use a sparse array instead, like so:

enter image description here

And hey, now that we got everything stored in sparse arrays and indexing them, it'd be pretty easy to make this a persistent data structure.

enter image description here

Now we can write more cheap functions free of side effects since they don't need to deep copy what hasn't changed.

And here I've already been given a cheat sheet after learning about ECS engines, but now let's think about what type of broad functions should be operating on each type of component. We can call these "systems". The "SoundSystem" can process "Sound" components. Each system is a broad function that operates on one or more types of data.

enter image description here

That leaves us with many cases where, for any given component type, only one or two systems will generally access them. Hmm, that sure seems like it would help with thread safety and absolutely bring thread contention to a minimum.

Furthermore I try to think about how to do homogeneous passes over data. Instead of like:

for each thing:
    play with it
    cuddle it
    kill it

I seek to split it up into multiple, simpler passes:

for each thing:
    play with it
for each thing:
    cuddle it
for each thing:
    kill it

That sometimes requires storing some intermediate state for the next homogeneous deferred pass to process but I found that really helps me to maintain and reason about the code, knowing that each loop has simpler, more uniform logic. And hey, that seems like it would simplify thread safety and reduce thread contention.

And you just kind of keep going like this until you find that you have an architecture that's really easy to parallelize with confidence about its thread safety and correctness, but all initially with the focus of unifying data representations, having more predictable memory access patterns, reducing memory usage, simplifying control flows to more homogeneous passes, reducing the number of functions in your system that cause side effects without incurring very expensive deep copying costs, unifying your API, etc.

When you combine all of these things, you tend to end up with a system that minimizes the amount of shared state where you kinda stumbled upon a design that's really friendly for concurrency. And if any state needs to be shared, you often find it doesn't have much contention where it's cheap to use some synchronization without causing a thread traffic jam, and furthermore that it can often be handled by your central data structure which unifies the representation of all things in the system so that you don't have to apply thread syncs to a hundred different places, only a handful.

Now when we drill down to one of the more complex components like meshes, we repeat the same process of designing it, starting with thinking about the data first. And if we do that right, we might even be able to easily parallelize the processing of a single mesh, but the broader architectural design we established already lets us parallelize processing of multiple meshes.

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .