Efficient parallel execution of the program requires
the load balancing of the work among component processes [1]. Because the
scene graph is an irregular and dynamic data structure, it cannot be partitioned
for parallel traversing by multiple processes. In parallel programming
paradigm, problems with irregular and dynamic data structure, such as the
scene graph of a synthetic environment, can be solved by the partition
of the program (also called partition in the control domain). The program
must be divided into a number of processes, and each process must perform
a sub-set of operations from the entire operations set of the program.
A balanced partitioning of the image generation program can be accomplished
by dividing the scene graph traversing operation into a sequence of traversing
operations, each of then executing a subset of the operation set needed
in each node of the graph. Every traversing operation is an execution stage
of the program and is implemented as a separate process. All processes
are connected in a simple directed graph, a linear array, which is known
as the task dependence graph of the program. The typical stages
in image generation are: update objects position in synthetic environment,
culling the objects towards the viewing frustum, draw the surfaces, etc
(Figure 3). The stages of the program are executed as corresponding processes
on available processors of the image generator, in a pipeline mode.
A constant frame rate is obtained if the image generation
processes are triggered with a given frequency which, usually is an integer
sub-multiplier of the display vertical synchronization rate, in order to
allow double frame-buffer swapping during vertical retrace time. The optimal
solution for program partition into stages, (each stage executed as a process),
and the assigning of processes to available processors in a multiprocessor
station depend on the number of processors and the relative amount of computational
time required for each stage [2], [3]. Figure 4 shows a partition of image
generation program into three stages, pipelined executed as three processes
on the same number of processors. Successive images (denoted frames) are
obtained after all stages are executed for each of them.
|
Each process is activated synchronously with the update
frame rate but the actual process execution time is not constant and depends
on the current frame. The condition for real-time execution is that the
maximum execution time (worst case execution time) of processes for frame
generation, to be less then the frame duration.
4.VIRTUAL MEMORY MANAGEMENT
With a limited size of physical memory, only a limited
number of virtual segments of a virtual scene can be present in memory
at any given instance. Let M be the set of physical memory addresses
allocated to store the input data of the program (scene graph), and V
the set of virtual segments of the scene. The physical memory is dynamically
allocated to different segments of the scene, depending on the relative
position of the segment towards the observer position. The virtual memory
management demands the implementation of the following mapping: ft:V®
MÈ{Æ
}
In other words, the mapping ft translates
a virtual segment into a memory address, if the segment is present in the
memory, and ft = Æ if
the segment is not present in memory. Dynamic mapping of virtual segments
to physical memory is partially similar with virtual memory mechanism included
in almost all operating systems, but there are some different requirements.
The first requirement is that in real-time image generation it is not acceptable
a memory miss, because the absence of an object needed for rendering would
produce an artifact in the generated image. Therefore, we cannot expect
a memory miss interrupt in order to swap virtual segments, and we must
prevent a memory miss situation by repeatedly execution of the following
mapping
function:
mapping_function () {
for (i = 0; i < p;
i++)
{
Compute the dist. D
of the segm. Vi
if (LSCB[i].status
> 0) {
if (D > switchOut) {
/* Segment detachment */
Disconnect segm. Vi from the scene
Delete the segment Vi
LSCB[i].status = 0;
}
}
else if (D <
switchIn)
{
/* Segment attachment */
Load
the segment Vi
Connect
segm. Vi in the scene
LSCB[i].status
= 1;
}
}
}
The program maintains a list of control blocks, for all virtual
segments of the scene (the list LSCB). Every segment control block stores
information needed for dynamic segment switch, which are:
-
The spatial dimension and the position in the scene of the
segment;
-
The backing store file name of the segment;
|