To figure out how many threads we need, and what each will be doing, we need to break the game into its various disciplines:

Now, let's look at the timing requirements and CPU intensity of these tasks:

(A), (B), and (C) are very closely linked (logically) and use considerably less CPU than (D), so it's reasonable to keep these three tasks in the same thread.

(D) is extremely CPU intensive—it can be interesting to try to break it into many pieces.

(E) *must* stay in real time—sound must never stand still. Therefore, it should get its own thread.

Using the Innerstrike game as an example, we can distribute these tasks across four threads (plus one):

• The "game controller" thread covers tasks (A), (B), and (C): It gets input from the user and does all the 3D geometry (but not the rendering). This thread takes 30% to 50% of one of the CPUs.

• The music and sound mixer thread (E) plays four tracks of music and mixes in individual sound effects. It takes a small chunk of one CPU.

• Two "graphic server" threads (D) do the rendering. They operate from a list of "rendering orders" as they draw to and from the frame buffer (or off-screen window). The first server is responsible for drawing the "common" interface and everything generated by player one; the second thread is responsible for player two. These threads pretty much eat up whatever cycles are left (on both CPUs).

(The "plus one" thread mentioned above is the default BWindowScreen window thread, which provides the interface to the App Server; this thread takes almost no CPU time and isn't really part of the architecture of the game.)

Note that if the game is being played in single-player mode, only one server thread is used. Thus, in this mode, a dual- CPU machine isn't used to its full potential. But I decided that for Innerstrike, splitting the rendering of a single view into two threads (to take advantage of both CPUs, regardless of the number of players) was too much trouble, and may have produced unreliable results.

If we look at the most important parts of Innerstrike, we see that the game controller thread (the "master") controls the two graphic server threads (the "slaves"). The master communicates with its slaves through two multibuffer channels. Each channel is protected by two semaphores:

• BUFFER_EMPTY indicates how many buffers are ready to be filled (by the master) with rendering orders.

• BUFFER_WAITING indicates how many buffers are waiting to be rendered by the slaves.

The buffers are always used in the same order, so we don't need an explicit list of empty (or waiting) buffers—we just need to know which one is the next. So each channel also has two indices, CURRENT_EMPTY_BUFFER and CURRENT_WAITING_BUFFER.

Each time the master wants to send rendering orders to a slave, it asks the specific channel for a new empty buffer by acquiring the BUFFER_EMPTY semaphore. When a buffer becomes available, the master fills it and releases the BUFFER_WAITING semaphore, and then increments (modulo the number of buffers in the channel) the CURRENT_EMPTY_BUFFER index.

The slave side is even simpler. A slave tries to get new rendering orders by acquiring the BUFFER_WAITING semaphore. When the buffer becomes available, the slave executes the orders in the buffer and then releases the BUFFER_EMPTY semaphore and increments the CURRENT_WAITING_BUFFER index. Then it starts all over again.

Here's a generic implementation (potentially not bug free!):

void master() {
  ...
  for  (i=0;i<2;i++)  {
    BUFFER_EMPTY[i]  =  create_sem(0,  "Ready  to  go");
    BUFFER_WAITING[i]  =  create_sem(0,  "Don't  disturb");
    CURRENT_EMPTY_BUFFER[i]  =  0;
    CURRENT_WAITING_BUFFER[i]  =  0;
  }
  ...
  while  (game_running)  {
    switch  (what_happening)  {
    ...
    case  DRAW_WITH_ONE_SLAVE  :
      acquire_sem(BUFFER_EMPTY[0]);

      {  /*  get  the  buffer  indexed  */  }
      {  /*  by  CURRENT_EMPTY_BUFFER[0]  */  }
      {  /*  fill  the  buffer  with  rendering  orders  */}

      release_sem(BUFFER_WAITING[0]);
      CURRENT_EMPTY_BUFFER[0]  =
        (CURRENT_EMPTY_BUFFER[0]+1)  %  BUFFER_COUNT;
      break;

    case  DRAW_WITH_TWO_SLAVES  :
      acquire_sem(BUFFER_EMPTY[0]);

      {  /*  get  the  buffer  indexed  */  }
      {  /*  by  CURRENT_EMPTY_BUFFER[0]  */  }
      {  /*  fill  the  buffer  with  rendering  orders  */}

      release_sem(BUFFER_WAITING[0]);
      CURRENT_EMPTY_BUFFER[0]  =
        (CURRENT_EMPTY_BUFFER[0]+1)  %  BUFFER_COUNT;

      acquire_sem(BUFFER_EMPTY[1]);

      {  /*  get  the  buffer  indexed  */  }
      {  /*  by  CURRENT_EMPTY_BUFFER[0]  */  }
      {  /*  fill  the  buffer  with  rendering  orders  */}

      release_sem(BUFFER_WAITING[1]);
      CURRENT_EMPTY_BUFFER[1]  =
        (CURRENT_EMPTY_BUFFER[1]+1) % BUFFER_COUNT;
      break;
    ...
    }
  }
}

void  slave(int  index)  {
  ...
  while  (TRUE)  {
    acquire_sem(BUFFER_WAITING[index]);

    {  /*  get the buffer indexed  */  }
    {  /*  by CURRENT_WAITING_BUFFER[index]  */  }
    {  /*  execute the rendering orders in the buffer  */  }

    release_sem(BUFFER_EMPTY[index]);
      CURRENT_WAITING_BUFFER[index]  =
    (CURRENT_WAITING_BUFFER[index]+1)  %  BUFFER_COUNT;
  }
}

Since semaphores, context switching, and memory allocation aren't free, I recommend that you use a small number of big buffers. In Innerstrike I use a BUFFER_COUNT of 2, enough to have the master working on the next frame as the slaves are drawing the previous one. Using more than two buffers increases the game's latency (the delay between the user's action and the reaction on-screen) without any real speed improvement.

With regard to the size of the buffers, I allocate enough memory (per buffer) to store the full description of a single frame. However, you don't have to be so precise. You can allocate significantly larger buffers without worrying about the entire buffer being swapped into physical memory: Individual pages are loaded into RAM *only* as they are touched.

To avoid paging as the game starts running, you should walk through your buffers (as your application is launching) and touch the first few pages that you know you will be using. Here, again, you don't have to be terribly precise—if your game eats up more pages as it's running, keep in mind that the master will touch these pages before the slaves get to them, so the delay incurred by swapping the pages in will be partly absorbed by the latency of the game (since the master is running at least one frame ahead of the slaves).

Plugging all of this into BWindowScreen's ScreenConnected() function (which toggles the game's access to the screen) is trivial. Just make sure that...

...nobody accesses the frame buffer before a ScreenConnected(TRUE) or after a ScreenConnected(FALSE).

...the game does nothing while the screen is disconnected.

...you update the frame buffer description each time ScreenConnected(TRUE) is called, and make sure nobody uses a value that's not up to date.

Following these rules shouldn't present any problems. We just need to get control of all the buffers in both channels to be sure that...

...the slaves aren't operating on the buffers and there aren't any old buffers left.

...the master isn't using the current value of the frame_buffer description, since it doesn't own any buffers (the master is supposed to use the frame_buffer description only to describe rendering orders in a buffer).

So here's a generic implementation of ScreenConnected():

void BWindowScreen::ScreenConnected(bool active)
{
  int   i;

  if (!active) {
    for (i=0;i<BUFFER_COUNT;i++) {
      acquire_sem(BUFFER_EMPTY[0]);
      acquire_sem(BUFFER_EMPTY[1]);
    }

    { /* optional: save the frame_buffer */ }
  }
  else {
    { /* optional: restore the frame_buffer */ }

    { /* Get a new description of the frame_buffer /* };
    for (i=0;i<BUFFER_COUNT;i++) {
      release_sem(BUFFER_EMPTY[0]);
      release_sem(BUFFER_EMPTY[1]);
    }
  }
}

Now you should understand why we initialized the semaphores to 0—the first ScreenConnected(TRUE) will release all the buffers and start the game running. Just be careful to create all the semaphores before the BWindowScreen, as there's currently a race condition bug in the Game Kit between the completion of the BWindowScreen constructor and the first call to ScreenConnected(TRUE). (This bug should be fixed in DR9).

• Using a double buffer between the master and the slaves (between the controller and the renderer) *does* increase the game's latency. You might assume that the game will, therefore, feel slow and unresponsive. But this isn't really the case. The delay between the user's decision to act, and the delivery of the event to the computer is *already* significant: All the way from the brain's decision, through the nerves, then the activation of the muscle, and the move itself (let's say with a joystick). This is a long time from the computer's point of view -- usually more than one second. Adding a twentieth of a second (the typical cost of the double buffer) isn't all that significant—the user will never feel it.

  If a user feels that a game is sluggish, it's probably because the game isn't generating enough frames per second—the brain is extremely sensitive to this rate—or because the input device/driver is slow or insensitive.

• Each time you give up control of the screen (through ScreenConnected(FALSE)), the frame buffer will be reset and reconfigured for another application (or the application server). When you get control back, you may need to restore your previous frame buffer content (everything else is managed by the Game Kit).

  In the above sample, I suggest a very simple solution: Explicitly save and restore the frame buffer. In most cases, you can redraw the full screen just by calling a "refresh_screen" function, which you can implement to redraw everything from scratch (this is what I do in the Dominos sample application).

• The speed of the communication between the master and its slaves depends on the amount of data you're sending: To make this as fast as possible, you should try to pass as little data as possible. For example, the Innerstrike game stores all the texture maps in a shared area, so only a pointer to them needs to be passed.

  Also, Innerstrike allows many faces to share the same texture map descriptor. So you can say "I want to map my texture onto *this* projection...," and then say "...and apply it to all *these* faces."

  You might also try reducing the number of vertices by using big faces (I use up to 6 points in Innerstrike), or by using triangle- and quadrangle-faced strips.

• It's usually easier to debug your program if you can put it in "single thread" mode. If you look at the previous sample, you'll see I always write only in one buffer of any channel at a time. Thus I can store the currently used buffer descriptor in a global variable, and so easily switch between direct calls and the buffered multithreaded architecture. To do this, you just need a few C-macros (or inline C++ functions):

  -> OpenChannel(channel_index); -> CloseChannel(channel_index); -> RenderingOrder(my_parameters); // one macro for each distinct rendering order

  In "direct" mode, you just map OpenChannel() and CloseChannel() to nothing ( {;} for example) and call the RenderingOrder() functions directly.

  In buffered mode, you map OpenChannel() and CloseChannel() to...

  void OpenChannel(int index)
  {
    acquire_sem(BUFFER_EMPTY[index]);
  
    { /* set the global buffer to the buffer indexed by
      * CURRENT_EMPTY_BUFFER[index]
      */
    }
  }
  
  void CloseChannel(int index)
  {
    release_sem(BUFFER_WAITING[index]);
    CURRENT_EMPTY_BUFFER[index] =
      (CURRENT_EMPTY_BUFFER[index]+1) % BUFFER_COUNT;
  }
  

  ...and then map all your RenderingOrder() macros to a function that simply pushes the ID of the desired rendering order (and its parameters) into the current global buffer. When the slave receives the buffer, it gets the rendering order ID and reads the parameters. This leaves the problem of actually invoking the rendering order: A simple method is to use a switch() based on the order ID. If you're really clever, you can pretend the buffer is a stack, push a function pointer and parameters onto this pseudo-stack, and then "execute" it. Fast -- but not terribly portable. By enabling or disabling your function mappings, you can switch between a straightforward single-threaded implementation (the code generated in that case will not include anything useless) and your multithreaded one. This is definitely useful for debugging and testing.

Heard in the halls:

"Could you take over Pulse and make it a little better"
"Sure, here it is... Oh you meant for DR9?"

So, this week's source is a modified version of the Pulse application. It's a little cleaned up and will work with one or two processors in the machine (don't click that button). With the exception of one UI flaw, it's visually the same as what comes with the machine.

I'll warn you now that there are a couple of low-level system calls in there that aren't documented and probably never will be, but here's the code for your perusal.

ftp://ftp.be.com/pub/Samples/pulse.tgz

Titles: BeZap
Location: ftp://ftp.be.com/pub/contrib/util/bezap.install
Author: blue dot software <bluedot@68k.org>

Speaking of resource viewers such as Pulse, BeZap does an excellent job of not just showing system resources, but acting as a thread/team manager as well. It looks like wherever the BeOS has left a hole, developers have rushed in with very good alternatives. I really like this tool. It makes killing off those errant processes that much easier. Make sure you look at the about box animation as well.

Macworld is rapidly approaching. So it's time for me to start acting like a cheerleader. There are no logistics to make available yet, but I want to start pounding the drum early to get developers to think of what they'll want to show at Macworld. We would prefer our booth to be filled with applications written by our developers, not by us. So start thinking about polishing that killer app by Macworld time. If you're ready to go, then we'll be ready to show! Over the next few weeks I'll pound the drum louder and louder until it's so deafening you can do nothing but complete those apps and help us show off your wares.