Search

As we continue to evolve into large-scale parallel systems, many of them employing hundreds of computing engines to take on mission-critical roles, it is crucial to design those systems anticipating and accommodating the occurrence of failures. Failures become a commonplace feature of such large-scale systems, and one cannot continue to treat them as an exception. Despite the current and increasing importance of failures in these systems, our understanding of the performance impact of these critical issues on parallel computing environments is extremely limited. In this paper we develop a general failure modeling framework based on recent results from large-scale clusters and then we exploit this framework to conduct a detailed performance analysis of the impact of failures on system performance for a wide range of scheduling policies. Our results demonstrate that such failures can have a significant impact on the mean job response time and mean job slowdown under existing scheduling policies that ignore failures. We therefore investigate different scheduling mechanisms and policies to address these performance issues. Our results show that periodic checkpointing of jobs seems to do little to ease this problem. On the other hand, we demonstrate that information about the spatial and temporal correlation of failure occurrences can be very useful in designing a scheduling (job allocation) strategy to enhance system performance, with the former providing the greatest benefits. [ABSTRACT FROM AUTHOR]

Scientific applications are becoming more complex and more I/O demanding than ever. For such applications, the system with dedicated I/O nodes does not provide enough scalability. Rather, a serverless approach is a viable alternative. However, with the serverless approach, a job's execution time is decided by whether it is co-located with the file blocks it needs. Gang scheduling (GS), which is widely used in supercomputing centers to schedule parallel jobs, is completely not aware of the application's spatial preferences. In this paper, we show that gang scheduling does not do a good job scheduling I/O intensive applications. We extend gang scheduling by adding different levels of I/O awareness, and propose three schemes. We show that all these three new schemes are better than gang scheduling for I/O intensive jobs. One of them, with the help of migration, outperforms the others significantly for all the workloads we look at. [ABSTRACT FROM AUTHOR]

With the rise of fast interconnection technologies and new concepts to utilize them without operating system interaction (like VIA [4]), compute clusters are becoming increasingly commonplace. Most of the interconnection networks focus only on message passing as their prime programming model neglecting the large code basis for shared memory. However, by utilizing the Scalable Coherent Interface (SCI) [19] with its ability to transparently perform remote memory operations, it is possible to support both efficient message passing and transparent shared memory on one single platform. This introduces a previously unknown flexibility into the cluster architecture. [ABSTRACT FROM AUTHOR]

In this paper we present an efficient design for message passing over a reflective memory network. First, we consider the attributes of reflective memory communication networks and the requirements to efficiently build message-passing functionality on these networks. We then introduce the Bill-Board Protocol, a lock-free protocol which provides low-latency send, receive, and multicast functionality to higher-level applications over reflective memory networks. The communication protocol and an implementation on SCRAMNet is described in detail. Lastly, the performance of this protocol is demonstrated. [ABSTRACT FROM AUTHOR]

Streamlining communication is key to achieving good performance in shared-memory parallel programs. While full hardware support for cache coherence generally offers the best performance, not all parallel machines provide it. Instead, software layers using Shared Virtual Memory (SVM) can be built to enforce coherence at a higher level. In prior work, researchers have studied application-specific cache coherence protocols implemented either in SVM systems or as handlers run by programmable protocol processors. Since the protocols are specialized to the needs of a single application, they can be particularly helpful in reducing the long latencies and processing overhead that sometimes degrade performance in SVM systems. This paper studies implementing application-specific protocols in hardware, but not via an instruction-based protocol processor as is typical. Instead, we consider configurable implementations based on Field-Programmable Gate Arrays (FPGAs). This approach can be faster than software-based techniques and less expensive than some hardware-based techniques. We study one application, appbt, in detail, including a VHDL-level design of the configurable protocol design. We sketch out approaches for other applications as well. Implementing protocol operations in configurable hardware improves communication performance by roughly 11X for a 32-node system. While overall speedups are a more modest 12% our method is promising because of its flexibility and because it offers a new way of harnessing configurable hardware at the network interface, where it already exists or could be easily added to current systems. [ABSTRACT FROM AUTHOR]

High-speed local area networks (LANs) support many distributed applications. These applications require some system availability guarantees. However, LANs may change their topology due to switches and hosts being turned on/off, link remapping, and component failures. In these cases, a distributed reconfiguration algorithm is executed. This algorithm analyzes the topology, computes the new routing tables, and downloads them to the corresponding switches. Unfortunately, in most cases user traffic is stopped during the reconfiguration process to avoid deadlock. Although network reconfigurations are not frequent, they may take hundreds of milliseconds to execute, thus degrading system availability significantly. In this paper, we propose a new deadlock-free distributed reconfiguration algorithm that is able to asynchronously update the routing tables without stopping user traffic. This dynamic reconfiguration algorithm is valid for any topology, including regular as well as irregular topologies. [ABSTRACT FROM AUTHOR]

A novel routing scheme is proposed for virtual cut-through switching that attempts to combine the low routing delay of deterministic routing with the flexibility and low queuing delays of adaptive routing on k-ary n-cube networks. In this hybrid routing scheme a message is routed as soon as possible along a minimal path to its destination even though the routing choice may not be optimal. Results show that the disadvantages of making a non-optimal routing decision are offset by its speed. Two pipelined implementations of this hybrid routing mechanism are evaluated and compared to traditional deterministic and adaptive implementations. The experimental evaluations show that both hybrid implementations do indeed achieve their objectives under various types of traffic patterns. [ABSTRACT FROM AUTHOR]

The shared object model is an appealing programming abstraction for distributed computing. By hiding the details of the network and data distribution, it allows the programmer to focus on higher-level concerns, and makes the program structure robust in the presence of changes in distribution patterns or environment. Nevertheless, it is not at all clear that the distributed shared object model can be adapted to the needs of modern large-scale distributed applications. The Aleph Toolkit is a collection of Java packages intended to support the construction of distributed shared objects in a way that addresses networking-related performance issues. This paper describes the design and rationale for the Aleph API, as well as our preliminary experience implementing a distributed shared object system in Java. [ABSTRACT FROM AUTHOR]

Implicitly parallel programming languages place the burden of exploiting and managing parallelism upon the compiler and runtime system, rather than on the programmer. This paper describes the design of NIP, a runtime system for supporting implicit parallelism in languages which combine both functional and object-oriented programming. NIP is designed for scaleable distributed memory systems including networks of workstations and custom parallel machines. The key components of NIP are: a parallel task execution unit which includes an efficient method for lazily creating parallel tasks from loop iterations; a distributed shared memory system optimised for parallel object-oriented programs; and a load balancing system for distributing work over the nodes of the parallel system. The paper describes the requirements placed on the runtime system by an implicitly parallel language and then details the design of the components that comprise NIP, showing how the components meet these requirements. Performance results for NIP running programs on a network of workstations are presented and analysed. [ABSTRACT FROM AUTHOR]

This paper describes the Scheduled Transfer (ST) protocol that can be used by applications to bypass the operating system (OS) for network communications. The design of ST has been influenced by two overriding goals. First, we want ST to be used to move data between multiple vendors' machines and over different media; therefore, we have proposed ST as an ANSI standard and defined a network protocol that is independent of the underlying physical layer. Second, ST has been designed to operate in a large, heavily-loaded scientific computing environment, and this goal is manifested in several ways. ST has been designed to minimize receive processing, relieving network congestion that could occur if the receiver exerts backpressure into the network. ST provides a mechanism by which upper layer protocol (ULP) headers can be separated from application data, a capability that is generally necessary to avoid a subsequent memory-to-memory copy in the host. ST includes support for reassembly of application messages that are striped across multiple physical interfaces. ST also includes a flow control mechanism that relieves the ULP from this responsibility and provides the opportunity for the implementor to offload this function to the network interface (NI). [ABSTRACT FROM AUTHOR]

Standard user-level networking architecture such as Virtual Interface (VI) Architecture enables distributed applications to perform low overhead communication over System Area Networks (SANs). This paper describes how high-level communication paradigms like stream sockets and remote procedure call (RPC) can be efficiently built over user-level networking architectures. To evaluate performance benefits for standard client-server and multi-threaded environments, our focus is on off-the-shelf sockets and RPC interfaces and commercially available VI Architecture based SANs. The key design techniques developed in this research include credit-based flow control, decentralized user-level protocol processing, caching of pinned communication buffers, and deferred processing of completed send operations. The one-way bandwidth achieved by stream sockets over VI Architecture was 3 to 4 times better than the same achieved by running legacy protocols over the same interconnect. On the same SAN, high-performance stream sockets and RPC over VI Architecture achieve significantly better (between 2-3x) latency than conventional stream sockets and RPC over standard network protocols in Windows NTTM 4.0 environment. Furthermore, our high-performance RPC transparently improved the network performance of Distributed Component Object Model (DCOM) by a factor of 2 to 3. [ABSTRACT FROM AUTHOR]

The evolution of the Fast Messages (FM) communication library has shown the importance of flow control to deliver the raw hardware performance of currently available interconnection networks to the applications. However, the credit-based solution used in FM to provide flow control, though simple and efficient for systems of limited dimension, does not scale well when the dimension of the parallel system increases. In this paper, we propose an extension to the FM flow control algorithm where credits can be assigned on-demand to communicating nodes. The experimental results reported in the paper demonstrate that the performance of this new scheme is virtually insensitive to system dimension providing that messages are long enough and there are not communication hot spots in the system. In presence of more general communication patterns, the proposed dynamic credit assignment mechanism can be used to implement adaptive credit allocation policies. [ABSTRACT FROM AUTHOR]

The Multimedia Router (MMR) architecture is aimed at providing QoS to multimedia traffic in a local area environment, while retaining a compact and simple design. In this paper, we show some preliminary performance evaluation results. The workload was composed of a mix of synthetic CBR traffic and semi-synthetic VBR traffic. The latter was obtained from real MPEG-2 video sequences. We show that, with a simple scheduling algorithm, amenable for single-chip implementation, the link bandwidth utilization is quite satisfactory, while still providing acceptable delays to both CBR and VBR traffic. [ABSTRACT FROM AUTHOR]

Networks of workstations (NOWs) are becoming a cost-effective alternative for small-scale parallel computing. Usually, NOWs present an irregular topology as a consequence of the needs in a local area network. Routing algorithms used in NOWs are inherently different from those used in regular networks, mainly due to the irregular connections between switches. In these algorithms, routing is considerably restricted in order to avoid deadlocks. Recently, a general methodology for the design of adaptive routing algorithms for irregular networks has been proposed by the authors. The resulting algorithms increase the maximum achievable throughput while reducing message latency. In this paper, we study how much network performance we are losing due to the irregular topology of NOWs. We analyze the performance of the up*/down* routing algorithm in a 2D mesh topology and compare it with the performance achieved by the XY routing scheme in the same network, in order to answer the following two questions: 1) in a 2D mesh, which of the two routing algorithms achieves better performance?, and 2) where does the up*/down* routing algorithm work better, in a 2D mesh or in an irregular network?. Simulation results show that the up*/down* routing strategy performs better in a regular network than in an irregular one. On the other hand, the XY routing algorithm considerably outperforms the up*/down* scheme. However, when the adaptive routing algorithm proposed by the authors is used, differences in performance are much smaller. Thus, the higher performance of a regular topology could not compensate for the loss in wiring flexibility with respect to irregular networks, or their capability of adding a single switch at any moment. [ABSTRACT FROM AUTHOR]

The Hybrid Technology MultiThreaded (HTMT) project is an attempt to design a machine with radically new hardware technologies that will scale to a petaflop by the 2004 time frame. These technologies range from multi-hundred GHz CPUs built from superconductive RSFQ devices through active optical networks and 3D holographic memories to Processing-In-Memory (PIM) for active memories. The resulting architecture resembles a three level hierarchy of "networks of processing nodes" of different technologies and functionality. All this new technology, however, has a huge and unknown effect on software execution models for applications. This paper discusses several potential HTMT models and how they can be prototyped and demonstrated using a combination of multithreaded Java and LAN-connected workstations. [ABSTRACT FROM AUTHOR]

Network-aware applications actively adapt to the level of service they receive from the network. This allows the application to execute well over a diverse set of networks and under a wide range of network conditions. However, network diversity and dynamic network conditions make the development of network-aware applications a difficult task, since the developer has to be an expert in both the application domain and networking. In this paper we look at a number of network-aware applications and identify three adaptation strategies that have proven to be effective. These strategies can be viewed as adapation models that capture the essential structure of the adaptation process. Similar to the use of programming models in parallel and distributed computing, adaptation models can be used to guide the development of other network-aware applications and they can also form the basis for programming support, e.g. middleware, that supports the development of network-aware applications. In this paper we describe the three adaptation models, compare their features and applicability, and briefly discuss how these models impact the design of middleware that supports network-aware applications. [ABSTRACT FROM AUTHOR]

This paper presents a low-communication overhead and high-performance data parallelism implementation of the Everglades Landscape Fire Model (ELFM) in a network of workstations (NOWs). Checkpointing and rollback techniques were used to handle the spread of fire which is a dynamic and irregular component of the model. A synchronous checkpointing mechanism was used in the parallel ELFM code using Message Passing Interface (MPI). The speedup and performance of the parallel program were also studied. Results show that the performance of ELFM using MPI is significantly enhanced by using the checkpointing and rollback mechanisms. [ABSTRACT FROM AUTHOR]

While improvements in semiconductor technology have made it possible to accommodate a large physical memory in today's machines, the need for supporting an even larger virtual address space continues unabated. Improvements in disk access times have however lagged improvements in both processor and memory speeds. Recent advances in networking technology has made it possible to go out on the network and access the physical memory on other machines at a cost lower than accessing the local disk. This paper describes a system implemented for such a remote paging environment. This system allows us to use a fine grain (a subpage) data transfer unit for remote memory paging and to employ different algorithms for determining when and how to transfer these units. The novelty of our implementation is that all the policy decisions about the subpage size and the subpaging algorithm are made at the user level, thus letting applications choose their own set of parameters. Performance results indicate that applications can benefit significantly from this flexibility. [ABSTRACT FROM AUTHOR]

A Network of Workstations (NOW) is emerging as a cost-effective solution to high performance computing. However, we need to lower the cost of communicating between the workstations to make this platform viable. With the advent of high-performance networks such as ATM and Myrinet, the physical network is no longer the communication bottleneck. Rather, the major overhead can now be attributed to software. This overhead is a direct result of the cost that a message incurs as it travels through different protection domains. We can alleviate this problem by allowing protected user-level access directly to the network, thereby eliminating the kernel from the critical path. This paper presents a description of the design, implementation and performance of a protected user-level messaging system over Myrinet, called MU-Net, that can handle multiple application processes concurrently. MU-Net has been implemented on the SUN Solaris 2.5 operating system. [ABSTRACT FROM AUTHOR]