PC clusters as a platform for image processing: promises and pitfalls

Printer Friendly Format

Page 3 of 3
| Previous |

PC clusters as a platform for image processing: promises and pitfalls

Partitioning a single process for parallel execution
Process-level parallelism cannot be applied to all types of tasks you might want to distribute across a cluster. One important category, illustrated by the second example above, involves a task where external constraints require that a single instance of a single process execute faster than it can on a single computer.

At this point we can no longer ignore the question of what the process does and how it does it. In fact, we need to have the source code, and to be prepared to rewrite some of it. In essence, it is necessary to restructure the process so that it becomes several pieces which can be run on separate computers. It may well be that these parts will need to communicate among themselves while executing, so a cross-machine interprocess communication mechanism is also needed.

Figure 2: Partitioning an image processing task across nodes
(You may want to restructure the software yourself, or to buy revised software from someone who has already gone through the process, or to contract someone to do the rewrite for you. Obviously, licensing considerations are important.)

We will not try to explain the restructuring process in detail here. If the software you want to partition was created at your lab, partitioning may be easy. Otherwise it may be difficult or even (if you don't have the source code) impossible. However, the second example, illustrated in Figure 2, shows well why we contend that cluster processing is very appropriate to remote sensing.

The objective is to do some sort of time-consuming computations, which we have not specified, to a remote sensing image. From a computational perspective, any remote -sensing image is the image of a.fragment of the landscape (or skyscape, seascape, etc.) with arbitrary boundaries. Usually, though not always, the computational properties are unchanged if we work separately with fragments of that fragment, and then recombine the partial results.

The illustration depicts subdividing the image into six regions, each to be processed on one node of a six-node cluster. There is nothing magical about either the number or the shape of regions, or the number of cluster nodes. An important question, however, is the detailed mathematical properties of the computational algorithm. If each pixel is computed independently of the values of adjacent pixels, then each region can be processed separately and there may be no need to revise the core program at all. (You just need to subdivide and then reassemble the image.) However, if computations for one region must consider information about other regions, then mechanisms must be available for communicating that information in a timely and efficient manner between cluster nodes. A commonly used facility for this is the Message Passing Interface (MPI) (Snir et al., 1999).

Moving form the Lab to the real world: Designs for dragon/IPS
Traditionally, PC clusters have been to a large extent laboratory animals. They have been created one at a time, frequently by the same group which will ultimately be using them. Thus, their users tend to be familiar with their innards and able to adapt to changing configuration and support software. As the economic and performance benefits of the Beowulf architecture become better known, there is a growing demand to move clusters from an experimental into a production status. The PC-based computer nodes themselves are familiar and widely available, as are (to a somewhat lesser extent) the network and operating system components. However, specialized clustering software, at a level appropriate to the intended user community, also needs to be available.

Goldin-Rudahl Systems, Inc. has been making and selling the Dragon/ips þ remote-sensing package for many years, as well as providing software consulting services. As of the current release of Dragon, we have no need for cluster computing. Dragon is quite fast enough on a single computer, in part because we do not currently support any particularly time-consuming image processing algorithms.

As we look to a future of very large images, hyperspectral images, real-time processing, and algorithms such as neural network and genetic processing, we can see our needs outstripping single-machine capabilities. PC clusters appear to be an inevitable answer to this need. However, we have to recognize that our customers are not computer science research labs; they are remote sensing and GIS labs. We anticipate that we will need to provide, one way or another, solutions for the following cluster-specific software requirements:

Application software. Dragon is already running on Linux at the process level. New image processing and GIS algorithms, as they are developed, will be designed for parallel execution. We will also create, on special order, custom image processing or GIS modules. For the lab which is already running a Beowulf, this will be sufficient. However, we feel that we also need to adapt to the needs of a "novice" lab. Therefore, we are developing:

Task management software. The concept of a cluster is defeated if the user needs to specify in detail what gets executed where and when. On the other hand, you are wasting your money if tasks are not allocated efficiently to available computing resources.

The approach taken by most of the popular task management systems, such as PVM (Geist et al., 1997), is essentially top-down, with an executive that distributes processes to nodes based on.various policies or heuristics. At Goldin-Rudahl Systems we are using a different approach based on the language Linda (Carriero & Gelertner, 1989), in which the allocation of work is self-organizing and involves all nodes.
Status monitoring software. It can be surprisingly difficult to notice, in a cluster, that one of your computers has stopped working altogether, especially if you never really intended to give up on remote sensing research to devote yourself full-time to system administration. We are working on simple and intuitive tools for monitoring cluster status.

Conclusions
The configuration discussed here is commonly referred to as a Beowulf cluster or desktop supercomputer or pile-of-PC's. Active research in architecture and tools is ongoing in numerous locations around the world. Here in Asia, for example, Dr. Putchong Uthayopas (Uthayopas, 2001) at Kasetsart University in Bangkok has done extensive work on the administrative and status monitoring aspects of cluster execution.

Because of the nature of remote sensing and GIS algorithms, which can often be decomposed spatially or along other dimensions, these processes are excellent candidates for execution in a cluster environment. The amount of geospatial data being gathered is growing at an extreme, indeed almost frightening, rate. Beowulf clusters provide one potential solution for extracting vital information from these masses of data in a timely and cost-effective way.

Problems remain, however. Setting up a cluster computer may not be a trivial effort. As a commercial vendor of remote sensing solutions, our company is interested in resolving these problems so that specialis ts in fields quite outside of computer science, who do not wish to trouble themselves with becoming Unix gurus, can gain the benefit of using this technology.

References

Carriero, N. & Gelertner, D., 1989. Linda in Context. Communications of the ACM, April 1989, Vol.32, No.4, pp 444-458.
Geist, A.., Beguelin, A.., Dongarra, J., Jiang, W., Manchek, R., & Sunderam, V., 1997. PVM Parallel Virtual Machine: A Users’ Guide for Networked Parallel Computing. MIT Press, Cambridge, Massachusetts.
Snir, M., Otto, S., Huss-Lederman, S., Walker, D. & Dongarra, J., 1999. MPI – The Complete Reference. MIT Press, Cambridge, Massachusetts. Sterling, T., Salmon, J., Becker, D. & Savarese, D., 1999. How to Build a Beowulf. MIT Press, Cambridge, Massachusetts.
Uthayopas, P., 2001. Building a Resources Monitoring System for SMILE Beowulf Cluster. Kasetsart University, Bangkok, Thailand. http://prg.cpe.ku.ac.th/publications/hpcasia.pdf

Page 3 of 3
| Previous |