Sign in to follow this  
Drigovas

Serialize or retain parallelism

Recommended Posts

Drigovas    509
This is just a question of preference more so than a technical how-to question, but it popped up in a conversation I was having with somebody earlier today and it seems to be a sort of thing that would be relevant to networking. When you're dealing with multiple connections that are handled in multiple threads, do you serialize the network packets into a single message pump, or do you perform logic associated with these packets in parallel. Either way requires synchronization of a structure. To serialize the messages would require locks on the structure [likely a queue] that acts as the single in/out for the game logic, and to operate in parallel would require locks within the game logic. What are your preferences, and what makes you choose one strategy over another? Personally, for small projects with small user counts, I prefer to serialize all the incoming packets into a single source and deal with them in the order that they appear in that pipe. I've had difficulty implementing such an approach effectively in large projects, so usually I opt to keep the parallelism all the way through the game logic in these cases [the single source becomes a bigger pain as a bottle neck than the parallelized game logic becomes a pain in the butt to implement]. Generally the experimental user count that I've found is pretty much 16 players and fewer -> serialization, 64+ players -> parallelization, with a gray area in between.

Share this post


Link to post
Share on other sites
Antheus    2409
Look into reactor/proactor dispatching mechanism. (here, for example, don't have link to original article right now).

Turns out it's the best compromise between both. It's inherently single-threaded, but allows transparent scalability to more threads.

[Edited by - Antheus on October 10, 2007 7:12:44 PM]

Share this post


Link to post
Share on other sites
hplus0603    11347
Why do you need threading at all, at the networking layer? If you use UDP, there is a single socket, which you'll be reading from in a single thread. How you then structure your world update and interest management may vary, but whether you thread there or not is not dependent on the networking.

Maybe I'm missing something from the question? Are you using TCP? On Windows?

Share this post


Link to post
Share on other sites
Drigovas    509
Well, the question was directly related to the use of TCP, and the use of more than a single thread for handling these connections, but it really doesn't totally have to be. Perhaps I'll ask it a bit more explicitly.

IFF you find yourself in a situation where you are receiving input of similar purpose on two or more threads [say, two threads in which you are attending to a separate set of sockets in each of these threads for similar purpose], [choice A] do you attempt to handle the data of these two threads in parallel, maintaining the parallelism throughout [perhaps within the threads themselves, perhaps not], or [choice B] do you attempt to collate this input into a single source, and handle it sequentially. Under what conditions do you choose one option over the other, and why?

Doesn't just have to do with networking, but figured this would be the field that it would most likely be encountered. [thus here would be where I could most likely encounter people who have developed a preference]

The reactor pattern [I believe this is the article you were referring to] would sort of be an example of choice B... The "Synchronous Event Demultiplexer" of the reactor pattern would be the gate that channels what could otherwise be a parallel process into a sequential one [actually, from my understanding, the goal of removing the complications associated with parallelism is the very purpose of the reactor pattern]. A similar philosophy can be taken with regard to squeezing commands from several threads into a single thread.

Still through, it is a matter of preference. [Personally, I like breaking my network code up into threads, but apparently I'm rather strange in that way, or at least thats what I'm gathering from this conversation so far. Of course if you single-thread everything, then this isn't a question that even applies to you.]

Share this post


Link to post
Share on other sites
hplus0603    11347
OK, so with TCP, on Windows, you'll end up with multiple threads, because that's what IOCP wants.

If the locking overhead of updating your world state is higher than the gain in parallelizing, then you should serialize to a single world update thread. If your world update is truly parallelizable, then keeping the updates on different threads is the best solution.

The main problem is that most simulation world update algorithms don't really lend themselves well to parallelization, both because of possible race conditions, and because of the algorithms involved (say, broad-phase collision detection).

Btw: solving that problem, and getting very high parallelism in simulation, is going to be a necessary challenge for the next few years. Sun is already shipping 64-core CPUs, and Intel can't be too far behind.

Share this post


Link to post
Share on other sites
drakostar    224
Regardless of your specific implementation and circumstances, this is almost certainly true: input is taken from the network and applied to the game model. Clearly you can't have more than one writer simultaneously changing the game data, so this is an inherently serial process. You might be able to parallelize input interpretation, but I doubt it would be particularly worthwhile.

A single thread handling network I/O via select or callbacks should be sufficient for most circumstances. Get input, interpret it, push it over to the game model thread's input queue for processing, and repeat. Sure, some packets may be purely read-only queries, but they're the exception in a multiplayer game.

You seem to get this, so I'm not sure what you think the advantage of more threads would be. Consider: what tasks are you parallelizing? Do they take significant CPU time (advantage: multi-processor systems) or require you to wait on something like file I/O (advantage: everyone)?

Share this post


Link to post
Share on other sites
Antheus    2409
Quote:
from my understanding, the goal of removing the complications associated with parallelism is the very purpose of the reactor pattern]. A similar philosophy can be taken with regard to squeezing commands from several threads into a single thread.


It's about removing context switch overhead, while retaining high granularity and low latency.

In theory, n threads would run in parallel. On a 64-core machine, 64 threads even might.

But as soon as you end up with hundreds of threads per core, you run into a wall. While having 500 clients served each by a thread on a 64 core machine might work well, you never solved the original problem - how to minimize overhead associated with threads.

This is where those designs come into play. Rather that waste time switching contexts or waiting for some other resources to become available, such design allows CPU to do something useful 100% of the time.

I like Boost::ASIO since it provides complete abstraction of all these concepts, and can be even used to implement other completely asynchronous structures (Active Objects, for example).

But neither of these can solve the problem of contention. At some point, you will run into synchronization issues. But this isn't the problem of either networking or libraries or OS or even hardware. The real challenge becomes partitioning the logic in such a way that you minimize the number of possible congestions in the first place.

Share this post


Link to post
Share on other sites
hplus0603    11347
Quote:
Clearly you can't have more than one writer simultaneously changing the game data, so this is an inherently serial process.


That's the question. Can you structure your game world state such that you can allow parallel updates? The Sun Game Server (project Darkstar) attempted this in one way, but ran into performance problems (can't do real-time updates to all objects in the world), and also structure problems (everything's a serialized object, so it's hard to for example run reports on the database).

There may be another world state organization that allows you to parallelize updates. After all, in the real world, my actions are independent of your actions, except when we're really close to each other. And, even so, I typically have some reaction time to your actions (unless physics is involved, i e direct contact).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this