Skip to main content
gamedev.net
🔒 Locked

Double-buffered simulation == GPU capable?

Started by Hodgman 6 replies 1.4k views
Original Post
Hodgman
Hodgman
I recently came across this SIGGRAPH presentation from ID Software, via the ATOM game's blog. I've been writing an engine based on double-buffered game-states for 6 months or so in my spare time and I'd be interested in hearing if anyone else here is looking into this technique too. My engine hasn't reached the point yet where I'm able to do any meaningful tests to see whether this system is really worthwhile, and so far I've had this lingering thought that I might be wasting my time on this system. After reading ID's talk though, I'm feeling reassured. Despite having implemented a system similar to what ID are describing in this presentation, the implications of such a system never occurred to me until I read this:
Quote:
Timothy Farrar's Blog: Note Jon's game parallelization for game entities description exactly parallels current GPU function. Majority of code only gathers data from previous frame (texture fetch of results from previous frame), and writes to self (writing to multiple render targets). One sync point, massive easy parallelism.
Has anyone else thought about this? I mean, being able to run all of our game logic on the GPU has got to be a good thing™, doesn't it? [Edited by - Hodgman on August 31, 2008 10:45:20 PM]
Kylotan
Kylotan
I think you and I have touched on this subject before. I've been given the impression that quite a few people use the double-buffered game state concept, and that it's perfectly workable. However, I also think you have to build it into the system right from the start, which is less trivial than sometimes stated.

And, I think that a lot of this talk about it being amazing for parallelism is overstated and not necessarily entirely relevant. All the talk here is of graphics and geometry - if that's all you have your CPU working on during a game, then I personally think you have a crap game. ;) Sure, there's vague talk of running game entity code on the GPU... IF you can write it in such a way that you can gather all the data you will possibly need for AI behaviour in the previous frame... IF you have enough graphics memory left for your actor logic after your artists have filled it up with the 16384x16384 textures they want to use... IF you can even express your actor logic in a way that is conducive to being compiled to shader code or whatever... too many ifs for my liking.
Hodgman
Hodgman
Quote:
Original post by Kylotan
I think you and I have touched on this subject before. I've been given the impression that quite a few people use the double-buffered game state concept, and that it's perfectly workable.
Yeah there was a rather long multi-threading thread a while back :)
Do you know if there are many (any?) publications on this topic, relating to games specifically? I've heard a MS guy say he hacked it into some games so they could run better on the 360, but he was very sparse on the details.

Quote:
Original post by Kylotan
All the talk here is of graphics and geometry - if that's all you have your CPU working on during a game, then I personally think you have a crap game. ;)
Aren't all of ID's games just graphics tech demos? ;)

Quote:
And, I think that a lot of this talk about it being amazing for parallelism is overstated and not necessarily entirely relevant.
Well it depends on how many actors you have in your world. Even if each only does a small amount of work, enabling parallel processing of them lets you scale from 1-core @ 1000 actors to 100 cores @ 100,000 actors... (assuming linear scaling!)

Quote:
Sure, there's vague talk of running game entity code on the GPU... IF you can write it in such a way that you can gather all the data you will possibly need for AI behaviour in the previous frame... IF you can even express your actor logic in a way that is conducive to being compiled to shader code or whatever... too many ifs for my liking.
I don't think the frame-delayed gather is really a problem - you can run multiple 'update frames' per 'time-step' if you need to.
To allow the game logic to either run on the CPU or on the GPU as shaders, you could develop a higher level language, which implements a programming model aimed at double-buffered sims -- kinda like EPIC did with UnrealScript (which implemented game features like network replication, etc as native language features).

Quote:
IF you have enough graphics memory left for your actor logic after your artists have filled it up with the 16384x16384 textures they want to use...
ID's using sparse virtual textures so texture memory management isn't a problem for them.
Kylotan
Kylotan
Quote:
Original post by Hodgman
Do you know if there are many (any?) publications on this topic, relating to games specifically? I've heard a MS guy say he hacked it into some games so they could run better on the 360, but he was very sparse on the details.

Sadly I'm ignorant on this topic, apart from what I've read here and in various forums.

Quote:
Even if each only does a small amount of work, enabling parallel processing of them lets you scale from 1-core @ 1000 actors to 100 cores @ 100,000 actors... (assuming linear scaling!)

Yeah, I just think that in many cases it's an invalid statement because actors don't process in isolation unless either their individual simulation is rather trivial, or you have a good system for communicating asynchronous messages. My guess is that the graphics-obsessed guys have entity AI that falls broadly into the first category, and the rest of us lack the languages and the tools to work with the second category. Give us a version of Erlang that compiles to shader code, and then we can talk...!

Quote:
I don't think the frame-delayed gather is really a problem - you can run multiple 'update frames' per 'time-step' if you need to.
To allow the game logic to either run on the CPU or on the GPU as shaders, you could develop a higher level language, which implements a programming model aimed at double-buffered sims -- kinda like EPIC did with UnrealScript (which implemented game features like network replication, etc as native language features).

Well, yeah, this is exactly the problem. Nobody in their right mind would say this approach is useless - after all, if there are logic gates available, then if we can use them, we benefit. But it's the cost of doing that which matters. The frame-delayed gather is an issue because it completely changes the way you need to write your algorithms. You need to turn logic upside down - no longer can you query something for a value you want, but you must have the system inject that value into the function in case you need it. Aggregate queries are tough - how do you find the nearest opponent, or count the number of threats within range?

Sure, it's not impossible, and it's nothing a new language couldn't achieve. But it's not going to look like C++ or Java in the way that UnrealScript did. I'll mention Erlang as an example of what I'd expect: something inherently concurrent, designed to accept messages (which can be asynchronous), and which holds no local state. It'll work perfectly, if anybody can get their head around it.

Quote:
Quote:
IF you have enough graphics memory left for your actor logic after your artists have filled it up with the 16384x16384 textures they want to use...
ID's using sparse virtual textures so texture memory management isn't a problem for them.

The question is, will this be a problem for everybody else? Or this is only a system that is practical for graphics gurus? Apart from my concern that the programming paradigm for AI would need to change significantly, the other concern is that enthusiasm for this area of development comes almost exclusively from graphics people who are excited about graphics hardware. Do they appreciate the needs of other types of developers? Sometimes I worry that graphics people dismiss the rest of the game as being little more than physics, for example. Perhaps I am doing them a disservice.
Drigovas
Drigovas
There are two questions that need to be asked with this sort of processing: 1) Can these tasks be run independently and thus in parallel at all, and 2) if they can, then can the data be marshaled cheaply. A yes to 1) means that you can run it in parallel, a yes to 2) means it is a candidate to be pushed into the GPU.

In the world of graphics, both of these questions are obvious yes's, which is why we have GPU hardware in the first place. The articles cited largely focused around this as was pointed out by Kylotan. Game physics is another thing that can typically be easily bent to function in this way. Game logic, on the other hand, presents some problems. The problem is one of communication, and specifically the establishment of race conditions if you have two entities performing actions that would render the opposite entities action an illegal move. Things like physics resolve this by allowing for inaccuracies in the simulation [two things CAN be in one place at one time, but are that way for such a short period as to be largely irrelevant]. Tolerating these inaccuracies are not always possible within the logic of a game. The alternative is to have hand-shake sequences that span a number of frames to allow for entities to arbitrate disputes, which isn't always simple. There is also then the question about what is done in the mean time, as these multiple phase interactions are being handled, and additional state is potentially changing.

There is also, as has been pointed out, the fact that very frequently in games we see chains of entities that are tightly coupled with respect to game logic, that could introduce issues with the propagation of messages along the chain of entities as these messages make a single 'hop' per iteration [then of course comes the question about whether or not your chain can be broken, which means you'll have to borrow some of the knowledge from the networking community and design these strange graphs to assert that sent messages don't just die half-way to their destination... yuck + latency].

At the very least you'll need a very clever dispute arbitration mechanism, even if you just decide that between entity N and M, N is always right if they disagree...
Antheus
Antheus
Quote:
I don't think the frame-delayed gather is really a problem - you can run multiple 'update frames' per 'time-step' if you need to.


While that's true, it does cause an inconvenience.

Consider a logic circuit simulator. 
(+) -->[NOT]-->|OR|-->[NOT]--> (LED)    ---------->|  |


On each tick, you process each entity:
void OR::process() { new.output = old.input1 || old.input2;}
This works.

But the moment you model JK or RS cell, it will show some unexpected flicker, or won't work at all. The reason is obvious from schematic - different pathways need different number of updates to propagate the changes.

While simple answer is to add some meta information to know when an operation is "complete", this becomes far from trivial when dealing with realistic scenario, where "complete" will mean "done with transaction from logic perspective", not individual parts of transaction.

A slightly more contrived example of bomb update logic:
- If I am in DISARMED state, notify everyone in range I will explode, go into PRIMED state
- If I receive a STOP command, I will go into DISARMED mode
- If I am in PRIMED state, explode

When objects in range receive notification about bomb going into PRIMED state, they immediately issue STOP command, and nothing happens.

But what if these objects can't decide for themselves, and need to ask someone else? And that someone may need to look at weather, check the oil and tire pressure (all through 1 frame delay), taking 20 updates to issue STOP command? If that is known, how many frames do we wait? What if that someone needs to read something from file, taking 270ms, where logic update takes 15ms per frame. Would having bomb wait 1000ms before exploding really solve anything?

And what happens, if two entities Ping Pong each other, resulting in non-overflowing infinite loop? When do you interrupt them?

I don't know of a solution for generic case.
Hodgman
Hodgman
Quote:
Consider a logic circuit simulator.
I'll try an answer this in another post, because it's a long answer ;)

Quote:
But what if these objects can't decide for themselves, and need to ask someone else? And that someone may need to look at weather, check the oil and tire pressure (all through 1 frame delay), taking 20 updates to issue STOP command? If that is known, how many frames do we wait? What if that someone needs to read something from file, taking 270ms, where logic update takes 15ms per frame. Would having bomb wait 1000ms before exploding really solve anything?
What if we get rid of the ubiquitous "Update" or "Tick" function - get rid of the update method of "for each entity call Update"?

Instead only update entities that need to be updated - this way there is no fixed overhead to performing a "frame", only the amount of work that needs to be done in a frame is done, and no more.
I believe we can do this through deferred function calls (messages). When an entity wants to affect another entity, it can pass a message to it which will be executed next frame. Instead of looping through all entities each frame, we just loop through all messages. No messages, no work.

So if we then disconnect 'frames' from 'time steps', we can then do all 20 hypothetical updates in a single 15ms time-step.


I think that now I'm making changes that don't agree with GPU architecture any more though. I guess I'm back in multi-core CPU land now.

Quote:
And what happens, if two entities Ping Pong each other, resulting in non-overflowing infinite loop? When do you interrupt them?
Well, in single-threaded code you get an infinite loop, so I think it's fair for the multi-threaded version to get stuck in an infinite loop as well.
Hodgman
Hodgman
Quote:
Consider a logic circuit simulator. 
(+) -->[NOT]-->|OR|-->[NOT]--> (LED)    ---------->|  |


On each tick, you process each entity:
void OR::process() { new.output = old.input1 || old.input2;}
This works.

But the moment you model JK or RS cell, it will show some unexpected flicker, or won't work at all. The reason is obvious from schematic - different pathways need different number of updates to propagate the changes.


I'm not quite sure if this will work, I've just scratched it out quickly.

It seems we need some kind of two-phase update, where all new inputs are collected first, and then new outputs are calculated in a second pass?

What if upon receiving an input, the logic entity signals that it requires a second frame (not a second time-step). In this second frame (after all input function calls have been made across the system), it calculates the new output values and sends out new input messages that are to be executed in the next time step (not next frame).

In pseudo C++, first the message processor: (N.B. this is single-threaded to make it simpler)
class TimeStepper{public:	void DeferredFunction( double atTime, FunctionObject )	void DoTimeStep()	{		currentTime += timeStepSize;		do//a frame		{			DeferredFunctionList callThisFrame;			move any deferred calls with atTime <= currentTime into callThisFrame;			for itFn as each callThisFrame			  itFn->Call();		}while( !callThisFrame.empty() );	}	double CurrentTime() const;	double NextTime() const;}

Now the logic entity:
class Component{public:	void SetInput( double atTimeStep, int id, bool value )	{		m_TimeStepper.DeferredFunction( atTimeStep, SetInput_(id, value) );	}private:	void SetInput_( int id, bool value )	{		if( inputs[id] != value )		{			inputs[id] = value;			if( !dirtyInput )			{				dirtyInput = true;				m_TimeStepper.DeferredFunction( m_TimeStepper.CurrentTime(), UpdateLogic_() );			}		}	}	virtual void UpdateLogic_()	{		check inputs, calculate outValues;		for itOut as each outputs, itVal as each outValues		  itOut->first->SetInput( m_TimeStepper.NextTime(), itOut->second, *itVal );	}	typedef std::pair<Component*,int> SocketId;	std::vector<bool>     inputs;	std::vector<SocketId> outputs;}

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.