| 1 |
Parallel Rendering on the ICSD SPARC-10's
|
| 2 |
|
| 3 |
Greg Ward
|
| 4 |
Energy and Environment Division
|
| 5 |
|
| 6 |
|
| 7 |
The Information and Computing Services Division was kind
|
| 8 |
enough to make 10 Sun SPARC-10's available on the network
|
| 9 |
for enterprising individuals who wished to perform experi-
|
| 10 |
ments in distributed parallel processing. This article
|
| 11 |
describes the method we developed to efficiently run an
|
| 12 |
incompletely parallelizable rendering program in a distri-
|
| 13 |
buted processing environment.
|
| 14 |
|
| 15 |
The lighting simulation and rendering software we have
|
| 16 |
developed over the past 8 years, Radiance, has only recently
|
| 17 |
been made to work in parallel environments. Although paral-
|
| 18 |
lel ray tracing programs have been kicking around the graph-
|
| 19 |
ics community for several years, Radiance uses a modified
|
| 20 |
ray tracing algorithm that does not adapt as readily to a
|
| 21 |
parallel implementation. The main difference is that Radi-
|
| 22 |
ance produces illumination information that is globally
|
| 23 |
reused during the rendering of an image. Thus, spawning
|
| 24 |
disjoint processes to work on disjoint parts of an image
|
| 25 |
will not result in the linear speedup desired. Each
|
| 26 |
independent process would create its own set of "indirect
|
| 27 |
irradiance" values for its section of the image, and many of
|
| 28 |
these values would be redundant and would represent wasted
|
| 29 |
CPU time. It is therefore essential that this information
|
| 30 |
be shared among different processes working on the same
|
| 31 |
scene. The question is, how to do it?
|
| 32 |
|
| 33 |
To minimize incompatibilities with different UNIX implemen-
|
| 34 |
tations, we decided early on in our parallel rendering work
|
| 35 |
to rely on the Network File System (NFS) only, imperfect as
|
| 36 |
it is. The chief feature that enables us to do parallel
|
| 37 |
rendering is NFS file locking, which is supported by most
|
| 38 |
current UNIX implementations. File locking allows a process
|
| 39 |
on the same machine or a different machine to restrict
|
| 40 |
access on any section of an open file that resides either
|
| 41 |
locally or on an NFS-mounted filesystem. Thus, data-sharing
|
| 42 |
is handled through the contents of an ordinary file and
|
| 43 |
coordinated by the network lock manager. This method can be
|
| 44 |
slow in states of high contention, therefore access fre-
|
| 45 |
quency must be kept low.
|
| 46 |
|
| 47 |
In this article, we will refer to processes rather than
|
| 48 |
machines because the methods presented work both in cases of
|
| 49 |
multiple processors on a single machine and multiple
|
| 50 |
machines distributed over a network.
|
| 51 |
|
| 52 |
The method we adopted for sharing our indirect irradiance
|
| 53 |
values is simple. Each process caches together a small
|
| 54 |
number of values (on the order of 16 -- enough to fill a
|
| 55 |
standard UNIX buffer) before appending these to a file. In
|
| 56 |
preparation for writing out its buffer, the process places
|
| 57 |
an exclusive lock on the file, then checks to see if it has
|
| 58 |
grown since the last time. If it has, the process reads in
|
| 59 |
the new information, assuming it has come from another pro-
|
| 60 |
cess that is legitimately working on this file. Finally,
|
| 61 |
the process flushes its buffer and releases the lock on the
|
| 62 |
file. The file thus contains the cumulative indirect irra-
|
| 63 |
diance calculations of all the processes, and every process
|
| 64 |
has this information stored also in memory (up until the
|
| 65 |
last time it flushed its buffer). Saving the information to
|
| 66 |
a file has the further advantage of providing a convenient
|
| 67 |
way to reuse the data for later renderings.
|
| 68 |
|
| 69 |
The image to be rendered is divided into many small pieces,
|
| 70 |
more pieces than there are processors. This way, if one
|
| 71 |
piece takes longer than the others, the processors that had
|
| 72 |
easy pieces are not all waiting for the processor with the
|
| 73 |
difficult piece to finish. Coordination between processes
|
| 74 |
is again handled by the network lock manager. A file con-
|
| 75 |
tains the position of the last piece being worked on, and as
|
| 76 |
soon as a processor finishes its piece, it locks the file,
|
| 77 |
finds out what to work on next, increments the position and
|
| 78 |
unlocks the file again. Thus, there is no need for a single
|
| 79 |
controlling process, and rendering processes may be ini-
|
| 80 |
tiated and terminated at will.
|
| 81 |
|
| 82 |
ICSD's offer to use their farm of SPARC-10's was an ideal
|
| 83 |
opportunity to test our programs under real conditions. The
|
| 84 |
problem at hand was producing numerically accurate, high-
|
| 85 |
resolution renderings of the lower deck of a ship under dif-
|
| 86 |
ferent lighting conditions. Three images were rendered one
|
| 87 |
at a time, with all 10 SPARC-10 machines working on each
|
| 88 |
image simultaneously. The wall time required to render one
|
| 89 |
image was about 4.3 hours. The first machine finished with
|
| 90 |
all it could do shortly after the last image piece was
|
| 91 |
assigned at 2.8 hours. Thus, many of the processors in our
|
| 92 |
test run were done before the entire image was complete.
|
| 93 |
This is a problem of not breaking the image into small
|
| 94 |
enough pieces for efficient processor allocation.
|
| 95 |
|
| 96 |
For the time that the processors were running, all but one
|
| 97 |
had 98% or 99% CPU utilization. The one exception was the
|
| 98 |
file server, which had 94% CPU utilization. This means that
|
| 99 |
the processors were well saturated while working on our job,
|
| 100 |
not waiting for image piece assignments, disk access, etc.
|
| 101 |
|
| 102 |
If we include the time at the end when some processors had
|
| 103 |
finished while others were still going, the effective CPU
|
| 104 |
utilization averaged 84%, with the lowest at 75%. Again,
|
| 105 |
this low figure was due to the fact that the picture should
|
| 106 |
have been divided into more than the 49 pieces we specified.
|
| 107 |
(The overall utilization was really better than this, since
|
| 108 |
we set the jobs up to run one after the other and once a
|
| 109 |
processor finished its part on one image it went on to work
|
| 110 |
on the next image.)
|
| 111 |
|
| 112 |
The real proof of a parallel implementation is not CPU util-
|
| 113 |
ization, however, it is the speedup factor. To examine
|
| 114 |
this, it was necessary to start the job over, running on a
|
| 115 |
single processor. Running alone, one SPARC-10 took about 35
|
| 116 |
hours to finish an image, with 99% CPU utilization. That is
|
| 117 |
about 8.2 times as long as the total time required by 10
|
| 118 |
processors to finish the image (due mostly to idle proces-
|
| 119 |
sors at the end). This ratio, 8.2/10, is very close to the
|
| 120 |
average effective CPU utilization value of 84%, indicating
|
| 121 |
that parallel processing does not result in a lot of redun-
|
| 122 |
dant calculation.
|
| 123 |
|
| 124 |
Our experience showed that an incompletely parallelizable
|
| 125 |
problem could be solved efficiently on distributed proces-
|
| 126 |
sors using NFS as a data sharing mechanism. The principle
|
| 127 |
lesson we learned from this exercise is that good utiliza-
|
| 128 |
tion of multiple processors requires that the job be broken
|
| 129 |
into small enough chunks. It is perhaps significant that
|
| 130 |
the time spent idle, 16%, corresponds roughly to the percen-
|
| 131 |
tage of the total time required by a processor to finish one
|
| 132 |
piece (since there were about 5 chunks for each processor).
|
| 133 |
If we were to decrease the size of the pieces so that each
|
| 134 |
processor got 20 pieces on average, we should expect the
|
| 135 |
idle time to go down to around 5%.
|
