I perform research in the area of high-performance distributed systems. Combining separate resources into a single tool gives computational scientists, medical doctors, experimental scientists, stock analysts, production and distribution managers, and many other people the power to accomplish tasks that were previously impossible. Unfortunately, the power obtained by combining resources comes at a high cost; the complexity of distributed, heterogeneous, multi-user environments limits the development and use of these applications to a small number of experts. The goal of my research is to make the power of distributed systems available to anyone who can benefit from them.
Distributed systems are more than the mere combination of several big computers into one huge computer. Many problems are naturally distributed and thus impossible to solve until effective solutions to the problems of distributed systems are found. Enormous data sets cannot be moved, but interactive means of analysis and visualization are crucial to understanding the information in the data. Scientific instruments that manipulate samples and medical instruments that examine patients may not be in or near the scientist's or doctor's office, but the monitoring and control of the instruments must be available in their offices to perform effective analysis. Combining information from separate databases to make a single pricing and distribution analysis for a company requires the interaction of several systems. Several people collaborating on the same project may need to interact with the same data simultaneously so that each of them can contribute to the analysis. Without effective solutions to distributed computing challenges, these problems cannot be solved.
Despite years of progress, utilizing distributed systems is still extremely difficult. Selecting the appropriate resources and conveying the application's requirements to the appropriate system administrators are challenging problems that most users are unable to handle. Coordinating resources at multiple locations, while either ensuring that they can exchange data at a rate sufficient for the application or reprocessing the data to reduce the amount exchanged, requires advanced knowledge of the systems involved. Ideally, the user should be able to design the application, submit it to the system, and have the most appropriate resources automatically selected and used.
My research focuses on solutions needed to overcome the complexities of distributed systems and make their power available for anyone who needs them. I look for solutions that consider detailed system- and network-level information when managing the application but do not require the application designer or user to understand that information personally. My experience has shown that the best research is motivated by existing problems--in either real-world applications or middleware. It is only through experience with concrete examples of high-level applications that the requirements for low-level systems become clear.
My first experience with making the power of distributed systems available in a high-level application framework was with Dome, a distributed object system designed to provide applications with advanced parallel features transparently. Performance analysis of Dome revealed that the applications spent much of their time waiting for communication to complete. While the transparency made it easier to write parallel code, it also resulted in extremely poor data placement.
I developed a system to optimize the performance of Dome's collective communication operations, which were primarily responsible for the bottlenecks. This package, named ECO, improved the efficiency of Dome applications by measuring the communication delays between machines and then optimizing the data placement and message patterns used for the collective operations needed by the application.
Although successful, developing ECO made it clear to me that a better solution was needed. The measurements used to optimize the communication structure were imprecise, expensive, and ineffective on newer networks.
Most of my thesis work has been conducted under the Remulac project at CMU. The major product of Remulac is Remos, which provides information for resource-aware applications. Although Remos provides information about both computing and networking resources, I will focus on the networking components of the project that are part of my research. My experience with the inadequacies of existing network information tools provided a motivation for designing the features of Remos. In the design process, we considered our previous experiences with tools, the requirements of a variety of distributed applications, the resource information available through various measurement techniques, and the steps required to convert resource data into predictions useful to the application.
To meet the needs of all applications, two separate query-based interfaces were provided. For applications having many ways to adapt to or select resources, a topology interface was designed to provide the maximum amount of detail of the network's structure, within the constraint of using a standardized representation. The detail provides the information needed to make complex decisions, such as processor selection, although inaccuracies may be introduced in the effort to represent all networks with the same format.
For applications having simpler information requirements, an interface was designed that accepts a combination of end-to-end data connections and reports the bandwidth available for each. Although different options are available for how these connections are combined, inaccuracies may be introduced for some applications whose connections are not fully representable with this interface. On the other hand, it allows the Remos implementation to respond to the query using whatever information is appropriate for the particular type of network, without the standardization process required for the topology interface.
Fulfilling the requirements of this API requires detailed network information. Most previous network performance measurement systems have been based on benchmarking, which requires sending data over the network to determine its current performance level. This technique is invasive, does not scale well, and is incapable of providing the topology information needed for our API.
To avoid these problems, Remos was designed from the outset to take advantage of information obtained directly from the network. Fortunately, the Simple Network Management Protocol (SNMP) is implemented in almost all networking components available today and provides the information needed for utilization measurement and topology discovery. Although utilization counters are available through SNMP, no work had previously been done to determine whether useful performance predictions could be made using those counters. I have compared the accuracy of SNMP-based predictions with benchmark-based predictions in real network, controlled testbed, and simulated network experiments. The results of these experiments indicate that the accuracy of SNMP-based predictions is equal to that of benchmark-based predictions. In addition, the SNMP technique generates little additional traffic across the network, scales well with the number of components in the network, and provides topology and hop-by-hop information about the utilization of the network.
Remos is only useful to the extent that it supports interesting applications. ECO is a good example of middleware that can use Remos. In addition, I will discuss an application that uses Remos, as well as an extension to the LogP parallel computation model that uses the information provided by Remos to apply the LogP model to distributed systems.
Applications involving retrieving, processing, and viewing massive amounts of data require distributed processing. The Quake project at CMU is an excellent example of this class of applications. The price of success at building the world's largest earthquake simulations is having to analyze the data. To this point, the earthquake researchers involved have been unable to visualize their data except through tedious remote processing done by staff at the Pittsburgh Supercomputing Center.
Bringing interactive visualization to these researchers' desktops will revolutionize their work. Visualizing large datasets involves the coordination of computing and networking resources. The Distributed visualization (Dv) project at CMU is solving this problem in a resource-limited environment. Because of the real-time nature of visualization, the success of Dv applications requires accurate predictions of both CPU and network availability. The topology obtained through Remos is used to select the best locations for processing the data, and the bandwidths between those locations and the desktop are used to optimize the final frame rate and image quality for optimum interactive response.
Network information is also useful in more abstract computational models. The LogP and related models are useful for predicting the performance of many algorithms on MPP's. Distributed systems tend to have low bisection bandwidth that is correctly reflected in the gap parameter of the LogP model. However, their high endpoint bandwidths can still be taken advantage of by algorithms using primarily neighborhood communication. I have expanded the gap parameter of LogP to reflect this behavior and refer to this parameter as the "local gap." This heuristic has proven accurate in predicting the performance of neighborhood-based communication patterns across a range of networks. Although part of a high-level model, calculating the local gap requires detailed knowledge of the network's topology, which is not available without a system such as Remos.
Distributed computing continues to offer exciting challenges and great promise. The infrastructure to support interesting, efficient, and easy-to-use systems is still in its infancy. The development of Remos and similar or related tools, such as NWS and Globus, is beginning to provide the support needed for adaptive, complex, and user-friendly applications. The challenge is now expanding on this basis by developing tools that bring the power available in distributed environments to people who previously could not manage such applications.
A specific area of interest to me is developing application models that are useful for adaptive applications. Remos provides the information needed by applications to adapt their behavior to available resources. However, the dynamic run-time behavior exhibited by these applications makes managing them very difficult. Reliable resource utilization and predictable completion time enhance the usefulness of adaptivity from both system management and end-user perspectives.
This predictability is absolutely critical to the widespread use of distributed systems. The emergence of distributed systems as significant computing facilities depends on two factors: people must want to develop and use distributed applications, and resources must be allocated for use by these applications. Without the ability to use application models to predict the run-time behavior of adaptive applications, these two requirements will not be met. System managers will be unwilling to dedicate resources to chaotic, unpredictable applications that alternately underutilize and then overload their facilities. Likewise, users will be frustrated by unpredictable completion time or highly variable interactive behavior, looking elsewhere for more reliable techniques.