``High Throughput Computing on Distributively Owned Grids''
Prof. Miron Livny
University of Wisconsin
Madison, WI 53706
E-mail: miron@cs.wisc.edu
URL: http://www.cs.wisc.edu/~miron/

Introduction

As more scientists, engineers, and decision makers use computers to generate behavioral data on complex phenomena, it is not uncommon to find customers of computing facilities who ask the question: How much behavioral data can I generate by the time my report is due? This question represents a paradigm shift. In contrast to other users, these throughput oriented users measure the power of the system by the amount of work it can perform in a fixed amount of time. The fixed time period is measured in the relatively coarse units of days or weeks, whereas the amount of work is seemingly unbounded --- one can never have too much data when studying a biological system, testing the design of a new hardware component, or evaluating the risk of an investment.

Given their unbounded need for computing resources, the throughput oriented community is closely watching activity in the computational grids area, and anxiously awaiting the formation of productive High Throughput Computing (HTC) grids. To meet the seemingly infinite appetite for computing power of this community, a HTC grid has to be continuously on the lookout for additional resources and therefore must have the mentality of a scavenger. The services of a provider of computing power are always accepted regardless of the resource's characteristics, degree of availability, or duration of service. As a result, the pools of resources HTC grids draw upon to serve their customers are large, dynamic and heterogeneous collections of hardware, middleware, and software.

As a result of the recent decrease in the cost/performance ratio of commodity hardware and the proliferation of software vendors, resources that meet the needs of HTC applications are plentiful and have different characteristics, configurations and flavors. A large majority of these resources reside today on desk-tops, owned by interactive users, and are frequently upgraded, replaced or relocated. The decrease in the cost/performance ratio of hardware also rendered the concept of multi-user time-sharing obsolete. In most organizations, each machine is usually allocated to one individual in the organization to support his/her daily duties. A small fraction of these machines will be grouped into farms and allocated to groups who are considered to be heavy users of computing by management. As a result of this trend, while the absolute computing power of organizations has improved dramatically, only a small fraction of this computing power is accessible to HTC users due to the ever increasing fragmentation of computing resources. In order for a HTC grid to productively scavenge these distributively owned resources, the boundaries marked by owners around their computing resources must be crossed.

However, crossing ownership boundaries for HTC requires that the rights and needs of individual resource owners be honored. The restrictions placed by owners on resource usage for HTC can be complex and dynamic. The constraints attached by owners to their resources prevent the HTC grid from planning future allocations. All the resource manager of the grid knows is the current state of the resources. It therefore has to treat them as sources of computing power that should be exploited opportunistically. Available resources can be reclaimed at any time and resources occupied by their owners can become available without any advance notice. The resource pool is also continuously evolving as the mean time between hardware and software upgrades of desk-top machines is steadily decreasing.

In addition to ownership boundaries, HTC grids must cross administrative domains as well. The main obstacle to inter-domain execution is access to the grid from which the application was submitted, such as input and output files. The HTC grid has to provide means by which an application executing in a foreign domain can access its input and output files that are stored at its home domain. The ability to cross administrative domains not only contributes to the processing capabilities of the grid, but also broadens the ``customer circle'' of the grid. It makes it very easy to connect the computer of a potential customer to the grid. In a way, the HTC grid appears to the user as a huge increase in the processing power of her personal computer since almost everything looks the same except for the throughput.

HTC applications usually follow the master-worker paradigm, where a list of tasks is executed by a group of workers under the supervision of a master. The realization of the master and the workers and their interaction may take different forms. The workers may be independent jobs submitted by a shell script that acts as the master and may collect their outputs and summarize them, or they can be implemented as a collection of processes which receive their work orders in the form of messages from a master process that expects to receive the results back in messages. Regardless of the granularity of the work-units and the extent to which the master regulates the workers, the overall picture is the same --- a heap of work is handed over to a master who is responsible for distributing its elements among a group of workers.

Making high throughput computing grids a reality will require intensive and innovative research in a wide range of areas. We list here some of challenges we face on the way to the deployment of large scale productive HTC computational grids.

1. Understanding the sociology of a very large and diverse community of providers and consumers of computing resources. In a HTC grid, every consumer can also be a provider and every provider can also be a consumer of services. We need to understand the needs of these communities and develop tools that will enable them to interact with the grid, monitor its behavior and express their policies.
2. Throughput oriented parallel applications. The effectiveness of a HTC grid depends on the ability of the applications to adapt to changes in the availability of processors and memory. Applications that require a fixed number of processors and memory are unlikely to benefit from the services of a HTC grid.
3. Understanding the economics (relationship between supply and demand) of a HTC grid. While basic priority schemes for guaranteeing fairness in the allocation of resources are well understood, mechanisms and policies for equitable dispersion of services across large computational grids are not. A major aspect in the development of such policies involves understanding supply and demand for services in the grid.
4. Data staging --- moving data to and from the computation site. When the problem of providing vast amounts of CPU power to applications becomes better understood, the next hurdle that must be crossed will be that of providing sufficiently sophisticated Resource Management services to individual throughput oriented applications. A major aspect of this problem is that of integrated staging, transport and storage media management mechanisms and policies for high throughput.
5. Tools to develop and maintain robust and portable resource management mechanisms for large, dynamic and distributed environments. Current approaches to developing such complex resource management frameworks usually involve a new implementation of large fractions of the framework for each instance of a marginally different Resource Management System. We also lack tools to monitor the behavior of large distributed environment and keep track of large collections of jobs submitted to such environments. Given the rapid changes in hardware and operating systems, the biggest potential source of throughput inefficiency is exclusion of resources due to the inability of the mechanisms of a HTC grid to operate on new computers. There is nothing more frustrating for a HTC customer than new resources that are likely to be the biggest and fastest being excluded from the HTC grid due to porting difficulties.