# Presentation: 763044

## Kriging residuals to account for spatially correlated errors

**Tot. Plants = b0 + b1 * ETM1 + b2 * ELEV + ... + Kriged Residuals**

**Tot. Plants = b0 + b1 * ETM1 + b2 * ELEV + ...**

**Kriged residuals**

**Kriging residuals to account for spatially correlated errors**

## What is Kriging?

- 2-Dimensional Spatial interpolator
- A weighted* *linear combination of point samples that exploits structure of spatial auto-correlation present in the data
- Spatial structure is determined by modeling the empirical variogram 	(autocorrelation as a function of separation distance).
- Using KB2D from Geostatistical Software Library (GSLIB)
-   	Widely used and open source.
- _	__Geostatistical Software Library and User’s Guide_,		Deutsch & Journel, 1998.

## Kriging Algorithm

- Begin with N samples of R  (e.g. residuals, **R****sampled**)
- For each pixel in the output image
- Calculate distance from pixel to each sample data point  (N x 1)
- Sort vector to find the NN nearest neighbor samples (NN x 1)
- Calculate covariance vector **D****j** for nearest neighbors (NN x 1)
- Calculate covariance matrix **C****ij** for nearest neighbors (NN x NN)
- Invert covariance matrix **C****ij**
- Multiply by covariance vector to create weight vector (NN x 1)
**	****	****	****W = C****-1**** ********D**
- Calculate dot product of data samples with weights to estimate R
**	****	****	****	****R****kriged**** = W ******** R****sampled**

## CGFS Test Case(790 points)

- 21.5 km

- 19.4 km

**Synthetic Dataset**
*Within the CGFS area* ...
- Began with original 79 samples
-    and
- added 711 randomly spaced points

## Elegantly Parallel Algorithm

- Parallelize using Domain Decomposition
- Each processor gets a subset of rows to estimate, but 	all of the residuals at the sample points.

## Previous MPI Implementation

- Fixed number of samples used in kriging each pixel.
- Constant processing time per row  Load balance.
- MPICH implementation on Linux Beowulf cluster.
- Nearly linear scaling with number of processors.
- Scaling efficiencies ~92% - 99%.
- Physically unrealistic: number of samples used should adapt to local sample density   Load imbalance.
- Submitted to CT project to satisfy Milestone F

## Xgrid(Distributed Computing for the Rest of Us?)

- Apple released in Jan 2004 and updated in March (Engr. Preview)
- Controller distributes jobs to agent processors (data & code)
- Controller sends more jobs to agents as they free or join grid
- Client collects results when agents finish

- Xgrid **client**

- Xgrid **controller**

- RAID**storage**

- jobs

- results

## Purchased Apple Xserve G5 in July
Server node + 10 compute nodes for GSFC
Dual G5 processors (2 GHz, 2 GB memory)
Gigabit Ethernet connectivity
3 TB Xserve RAID array + 2nd 4.8 TB array
Server + 5 nodes for USGS NIISS
OS 10.3 Server with GUI     management suite
Xgrid for “pool of
   processors”
   computing model
MPI also available for     legacy Beowulf codes

- Server node + 10 compute nodes for GSFC
- Dual G5 processors (2 GHz, 2 GB memory)
- Gigabit Ethernet connectivity
- 3 TB Xserve RAID array + 2nd 4.8 TB array
- Server + 5 nodes for USGS NIISS
- OS 10.3 Server with GUI     management suite
- Xgrid for “pool of
-    processors”
-    computing model
- MPI also available for     legacy Beowulf codes

**New Computing Environment**

## Cluster Status Displays

## Cluster Status Displays(continued)

**Tachometer illustrates**
**total processing power**
**available to cluster at**
**any time.**
**Changes rapidly as jobs**
**begin and end.**

## Kriging with Xgrid

- “Pool of Processors” Model
- Divide region to be kriged into  20 sets of rows.
- Compute each set of rows in a separate job.
- First 20 jobs are assigned one per agent by controller.
- Processors are given more rows as they finish jobs.
- Client assembles output image when all jobs are done (using simple concatenation).

## Tell KB2D to process a subset of rows:
     prompt%   kb2d   parameter_file  1   40
     prompt%   kb2d   parameter_file  2   40
     prompt%   kb2d   parameter_file  3   40

     prompt%   kb2d   parameter_file  40   40

-      prompt%   kb2d   parameter_file  1   40
-      prompt%   kb2d   parameter_file  2   40
-      prompt%   kb2d   parameter_file  3   40
-      prompt%   kb2d   parameter_file  40   40

**KB2D Modifications**

## Xgrid Custom Plugin for KB2D Kriging

## “Scaling Curve” forFixed Kriging

**“****Scaling Curve” for****Fixed Kriging**

**Number of Jobs**

**Speedup**

**20 agents****~ 3000 points****~ 15K x 20K**

## “Scaling Curve” forAdaptive Kriging

**“****Scaling Curve” for****Adaptive Kriging**

**Number of Jobs**

**Speedup**

**20 agents****~ 3000 points****~ 15K x 20K**

## Xgrid Evaluation

- Prototype implementation of GSLIB’s KB2D Kriging
- Implemented with custom plug-in, not on command line.
- Modest performance penalty for load-balanced parallel application.
- High utility and ease-of-use for load-imbalanced runs.
- Tuning needed to determine optimal job size.
- 240 job limit might prevent peak performance for adaptive kriging.
- Compute agents can enter and leave cluster dynamically.
- Controller crashes do occur, requiring resubmission.
- Results are not transferred to client until all jobs done.

## Status

- Xgrid kriging approved for “Milestone G” payment
- •   This code delivery successfully concluded   				Computational Technologies project.
- Xgrid looks promising for other statistical/geospatial tasks
-    E.g. exhaustive regression or variogram map generation
-    Any task done by row, as long as all data fit in agent
-    Independent simulations, e.g. parameter studies
-    MPI expertise is not required
- Improved Xgrid promised for Tiger release (OS 10.4)
-    Tiger released end of April
-    Includes programming interface (API)