Braid is a very good game that overcomes some ham-fisted writing and overly ambitious themes. I won’t really dwell on talking about the game in this post other than to say that I recommend it, and that there are some mild spoilers in the remainder of this post.
I saw a post by the author commenting on the fact that getting the game to run on the PS3 would be a "gargantuan effort," and that got me thinking about the reasons why, along with how the game engine works to begin with.
First of all, the time-rewinding mechanism appears to be using input recording rather than state recording. That is, the state of the user’s controller is stored for each frame of the game, and is used to control the player’s character during time rewinds/fast forwards. I base this idea off of the fact that, in the world that uses your "time shadow," the shadow’s actions are based on the player’s controller input, and the replayed actions can be affected by the current state of the world.
Naturally, there is additional information stored to assist with the time mechanics of the game — input alone is not enough to reconstruct the state of the world. Jumping, for example, plays a significant role in the game, and being able to "rewind" a jump requires knowledge about when and where the jump started. (If it were possible to efficiently reconstruct the state of the game up to a certain time, you could avoid storing the "where" part, but I don’t think this is the case.) Additionally, the behavior of AI actors like the bunny and cannons would require some state to be saved in order to properly rewind or replay their actions.
The game runs at a steady 60 FPS. If we assume that replay data is stored at the same frequency, and we assume 128 bytes of replay data per frame (a number that I simply pulled out of a hat that said "reasonable assumptions"), then 15 minutes of gameplay results in about 7 MB of uncompressed replay data. This back-of-the-envelope calculation leads me to believe that the reason that Braid would be difficult to port to the PS3 is not related to utilizing more than 256 MB of RAM. (The Xbox 360’s 512 MB of RAM is unified, whereas the PS3 has a hard separation of 256 MB of main memory and 256 MB of GPU memory.) There should be plenty of memory for the replay data on both platforms, given the relative sparseness of the levels.
With that possibility ruled out, what does that leave? I think it’s related to the game engine (and replay system) architecture, not the amount of data being created. My guess is that the updates performed by the game engine are, by design, fully reversible, in order to minimize the amount of replay data that needs to be stored. Furthermore, in order to allow for really fast rewinding/replaying (up to 8x, while remaining at 60 FPS), the game update tasks are parallelized.
The game state that is touched by these parallel steps, however, is large enough such that it will not fit into the 256K memory on each SPE of the Cell processor. Furthermore, the game update phase is not organized in any way that would permit "windows" of the game data to be sent to (and modified on) the SPEs. This is pretty much the worst-case performance scenario for the PS3 and the Cell — the need to parallelize algorithms that touch a large data set in a random-access manner.
I don’t think this is an insoluble problem, but a solution that would work well on the Cell would likely look drastically different from what you would write if you only had to consider the PC and Xbox 360. And when you consider the size of the programming team that created Braid, it’s easy to make the choice between rearchitecting the code and moving on to the next game by scrapping the notion of a PS3 port.
Please note that all of the above is just speculation — I don’t have any idea if this is actually the case, but I like to speculate about game engine design and implementation, since I’ve had quite a bit of experience with it…