PROOF -- The Parallel ROOT Facility

Building on the experience gained from the implementation and operation
of the PIAF [1] system we have developed the parallel ROOT facility,
PROOF. The main problems with PIAF were due to the fact that its proper
parallel operation depended on a cluster of homogeneous equally performant
and equally loaded machines. Due to PIAF's simplistic partitioning of a
job in N equal parts, where N is the number of processors, the overall
performance was governed by the slowest node. The running of a PIAF cluster
was an expensive operation since it required a cluster dedicated solely to
PIAF. The cluster could not be used for other types of jobs without
destroying the PIAF performance.

In the implementation of PROOF we made the slave servers the active
components that ask the master server for new work whenever they are
ready. In this scheme the parallel processing performance is 
a function of the duration of each small job, packet, and the networking
bandwidth and latency. Since the bandwidth and latency of a networked
cluster are fixed the main tunable parameter in this scheme is the
packet size. If the packet size is choosen too small the parallelism
will be destroyed by the communication overhead caused by the many
packets sent over the network between the master and the slave servers.
If the packet size is too large the effect of the difference in performance
or each node is not evened out sufficiently.

Another very important factor is the data locality. In most cases we
want to analyse a large number of data files which are distributed
over the different nodes of the cluster or over a geographically
distributed set of computing resources connected by WANs. To group
these files together we use a chain. A chain provides a single logical
view of the many physical files. To optimize performance by preventing
huge amounts of data being transfered when analysing a chain, each slave
server is assigned a packet which is local to the node. Only when a slave has 
processed all its local data will it get packets assigned that cause 
remote data access. A packet is a simple data structure of two numbers:
"begin event" and "number of events". The master server generates
a packet when asked by a slave server, taking into account the time it
took to process the previous packet and which files in the chain are
local to the slave server. The master keeps a list of all generated
packets per slave, so in case a slave dies during processing, all its
packets can be reprocessed by the remaining slaves.


[1] PIAF Users Guide, CERN Program Library