into the final output. Due to the intrinsic diversity of processing 
  
  
  
  
  
  
  
  
  
  
  
  
the local area network. The open source TORQUE project 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
The 
algorithms, merge procedures vary. For some algorithms, ^ (Staples, 2006) was customized to provide a basis for our con 
additional edge operations must be carried out before the merge parallel framework. con 
between two adjacent results; while for other ones, all the | suc 
intermediate results can be merged in a batch mode without any — Fig. 6 illustrates the structure of our parallel framework.The | dis 
additional edge operations. system consists of four components: pbs server, pbs sched, | exti 
database, and pbs mom. These four components collaborate | imp 
Therefore, the complete execution graph can be divided into two — closely to perform LiDAR point cloud processing. 
categories according to the decomposition and merge paradigms: The 
two-level n-ary tree, and n-level binary tree patterns, illustrated (obser) ce, exe 
by Fig.4. In the first type, all the intermediate results are merged poe EET orte EEE cac 
in a whole; in the second type two adjacent intermediate results | i froi 
are merged hierarchically. | | PBS Server PBS Sched MySQL | exe 
i we i | stat 
! NN / 
Server Le SE Sa edi 8 it t 
(p ® RNC d exe 
Nes GES a Nd nou goo oo hg 
| PBS MOM pen PBS MOM E PBS MOM | | The 
| Jost Speed 4 | fat 
RE | whi 
VASE i em Lo cud pbs 
and 
Figure 6. The TORQUE-based parallel framework witl 
dec 
The database is the newly designed module for TORQUE. It 
stores current information for later scheduling, e.g. the 
distribution of decomposed blocks, the status of job execution, 
and the state of I/O between nodes. The database is hosted in a 
MySQL instance. The detailed information about these tables is 5.1 
Figure 4. Two types of Split-and-Merge paradigms listed in Table 2, 3 and 4. 
(left: two-level n-ary tree; right: n-level binary tree) The 
run 
; : ; ; : Field Name Type Length C | 
For a specific LiDAR algorithm, the execution pattern is defined Di 
by its internal procedure. Users/programmers only focus on the block name vchar 40 ITI 
actual implementation of two tasks: Split (program S) and nod 
Merge (program M). After the implementation of these two node_name vehar 40 the 
programs, the framework will automatically generate a node type integer Th 
collection of scripts to encapsulate these individual split and t 
merge tasks. Illustrated by interpolating four point blocks into a cho 
DEM, the generated task scripts are listed in Fig.5 and Table 1. Table 2. The structure of tbl block distribution 1 
e 
Field Name Type Length 
task id vchar 40 
4 6 node name vchar 40 
start time datetime 
5 T completion time datetime 
; : 3 Table 3. The structure of tbl task execution 
Figure 5. Four point blocks for interpolation Cui T 
: : 7 Fi 
idw_interpolate -i abc_0_0.las -o abc_04.dem ieidiNume Type Leng 
idw interpolate -i abc_1_0.las -o abc_05.dem block name vchar 40 
idw interpolate -iabc 0 l.las -o abc 06.dem 
idw interpolate -i abc 0 2.las -o abc. 07.dem node source vchar 40 
dem merge -i abc 04.dem/ abc 05. dem / abc 06. dem / > 
abc 07. dem -o0 abc 0l.dem node_dest yehar 40 
start time datetime 
Tablel. A list of automatically generated task scripts 5.2 
completion time datetime 
4. THE PARALLEL FRAMEWORK One 
Lan | triai 
Our universal parallel framework is built on a standard SMP Table 4. The structure of tbl_io_information Spli 
(Symmetric Multiprocessor) cluster. Each node is connected by 
204