Search

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]