Parallel Processing Letters

Great advances in high-performance computing have given rise to scientific applications that place large demands on software and hardware infrastructures for both computational and data services. With these trends the necessity has emerged for distributed systems developers that once distinguished between these elements to acknowledge that indeed computational and data services are tightly coupled and need to be addressed simultaneously. In this article, we compile and discuss several strategies and techniques, like co-scheduling and co-allocation of computational and data services, dynamic storage capabilities, and quality-of-service, that can be used to help resolve some of the aforementioned issues. We present our interactions with a distributed computing system, NetSolve, and a Distributed Storage Infrastructure, IBP, as a case study of how some of these techniques can be effectively deployed and offer experimental evidence from early prototypes that validate our motivation and direction.

Java is becoming an increasingly popular language for developing distributed and parallel scientific and engineering applications. Jini is a Java-based infrastructure developed by Sun that can allegedly provide all the services necessary to support distributed applications. It is the aim of this paper to explore and investigate the services and properties that Jini actually provides and match these against the needs of high performance distributed and parallel applications written in Java. The motivation for this work is the need to develop a distributed infrastructure to support an MPI-like interface to Java known as MPJ.

In the first part of the paper we discuss the needs of MPJ, the parallel environment that we wish to support. In particular we look at aspects such as reliability and ease of use. We then move on to sketch out the Jini architecture and review the components and services that Jini provides. In the third part of the paper we critically explore a Jini infrastructure that could be used to support MPJ. Here we are particularly concerned with Jini's ability to support reliably a cocoon of MPJ processes executing in a heterogeneous envirnoment. In the final part of the paper we summarise our findings and report on future work being undertaken on Jini and MPJ.

Coscheduling of communication and computation is considered one of the crucial points to obtain good performance out of fast communication systems. Various techniques have been examined in literature ranging from strict "gang scheduling" of all processes possibly involved in message exchange to "implicit coscheduling" in which the communication support system may act on the scheduling of sending and receiving processes trying to improve performance without explicit coordination by special purpose message exchanges. Based on the experience in implementing the GAMMA communication system, we are convinced that some form of coscheduling is needed in order to obtain best performance in communication. However we believe that most of the approaches described in literature so far are too simplistic to be really effective. In this paper we point out and classify some of the major problems a system that attempts to coschedule communication and computation should address. We hope to clarify the goals of a coscheduler by taking some of the crucial characteristics of the communication into account. We also hope to be able to devise some more integrated and coherent strategies of coordination between process scheduling and choice of communication modes.

As processors become more powerful and clusters larger, users will exploit this increased power to progressively run larger and larger problems. Today's datasets in biology, physics or multimedia applications are huge and require high performance storage sub-systems. As a result, the hot spot of cluster computing is gradually moving from high performance computing to high performance IO. The solutions proposed by the parallel file-system community try to improve performance by working at the kernel level to enhance the regular IO design or by using a dedicated Storage Area Network like Fiber Channel.

We propose a new design to merge the communication network and the storage network at the best price. We have implemented it in OPIOM with the Myrinet interconnect: OPIOM moves data asynchronously from SCSI disks to the embedded memory of a Myrinet interface in order to send it to a remote node. This design presents attractive features: high performance and extremely low host overhead.

Interconnecting computers into clusters or computational grids promises many benefits for users of computational science and engineering, especially in terms of performance and costs. This situation is additionally supported by programming libraries like MPI and PVM, which are portable across different platforms and allow to exploit the available computing power. Consequently, the number of applications utilizing these computing structures is steadily increasing. Yet, there are also some pitfalls with possibly serious consequences, that must not be ignored by software developers. This paper describes some critical issues related to nondeterministic program behavior. With such kinds of programs different program executions are observed although the same input data are provided, leading to the irreproducibility effect, the completeness problem, and the probe effect. The impact of these effects, their weight for software developers, and how they are affected on supercomputer architectures and cluster environments are discussed. These critical issues need to be pointed out to users in order to raise their understanding and awareness of the problems. While the irreproducibility effect is believed to be sufficiently solved by record&replay mechanisms, existing solutions for the probe effect are only partially successful, and only very few approaches address the completeness problem. A simple solution for the latter is offered by automatic event manipulation and artificial replay, which is however restricted by time and memory constraints. In addition, this solution to the completeness problem also solves the probe effect in nondeterministic parallel programs.

Programs running on insecure or malicious hosts have often been cited as ripe targets for security attacks. The enabling technology for these attacks is the ability to easily analyze and control the running program. Dynamic instrumentation provides the necessary technology for this analysis and control. As embodied in the DynInst API library, dynamic instrumentation allows easy construction of tools that can: (1) inspect a running process, obtaining structural information about the program; (2) control the execution of the program, (3) cause new libraries to be dynamically loaded into the process' address space; (4) splice new code sequences into the running program and remove them; and (5) replace individual call instructions or entire functions.

With this technology, we have provided two demonstrations of its use: exposing vulnerabilities in a distributed scheduling system (Condor), and bypassing access to a license server by a word processor (Framemaker). The first demonstration shows the danger of remote execution of a job on a system of unknown pedigree, and the second demonstration shows the vulnerabilities of software license protection schemes. While these types of vulnerabilities have long been speculated, we show how, with the right tool (the DynInst API), they can be easily accomplished. Along with this discussion of vulnerabilities, we also discuss strategies for compensating for them.

Harness is an experimental metacomputing framework based on dynamic reconfigurability and extensible distributed virtual machines. The Harness system seeks to achieve two important goals. First, by enabling reconfiguration of the facilities provided by the virtual machine, Harness is able to provide specialized services appropriate to the platform and adapt to new technological developments. Second, Harness is able to adapt to application needs by configuring the required support services and programming environments on demand. In this paper, we describe the architecture and key features of Harness, and discuss the emulation of two distinct programming environments, namely Javaspaces and PVM, within the Harness environment.

The Basic Interface for Parallelism (BIP) [1] is a low-level communication system for Myrinet programmable network interface cards (NIC). On one hand BIP has proven that a very small latency and a very large throughput can be delivered. On another hand hardware implementations, like Giganet or NICs that implement the Scalable Coherent Interface (SCI), demonstrate very good performance for medium-sized messages. Our aim in this paper is to study how the programmable NICs can compare with the hardware solutions for medium-sized messages. We built a very precise model of the pipeline behavior driven by the NIC program in order to identify the bottlenecks. The results show that the pipeline quality is critical. We have developed an adaptive strategy as in [2] and then introduced it in BIP. Experiments show up to a two-fold gain over the previous BIP results and reach performances above the hardware solutions.

An efficient dynamic storage allocator is important for time-critical parallel programs. In this paper, we present a fast and simple parallel allocator for fixed size blocks on shared-memory multiprocessors. We show both theoretically and empirically that the allocator incurs very low lock contention. The allocator is tested with parallel simulation applications with frequent allocation and release requests. The results confirm that our allocator is indeed very efficient.

In this note we describe deterministic parallel algorithms for planar point location and for building the Voronoï Diagram of n co-planar points. These algorithms are designed for BSP/CGM-like models of computation, where p processors, with local memory each, communicate through some arbitrary interconnection network. They are communication-efficient since they require, respectively, O(1) and O(log p) communication steps and local computation per step. Both algorithms require local memory.

Delaunay triangulation has been much used in such applications as volume rendering, shape representation, terrain modeling and so on. The main disadvantage of Delaunay triangulation is large computation time required to obtain the triangulation on an input points sets. This time can be reduced by using more than one processor, and several parallel algorithms for Delaunay triangulation have been proposed. In this paper, we propose an improved parallel algorithm for Delaunay triangulation, which partitions the bounding convex region of the input points set into a number of regions by using Delaunay edges and generates Delaunay triangles in each region by applying an incremental construction approach. Partitioning by Delaunay edges makes it possible to eliminate merging step required for integrating subresults. It is shown from the experiments that the proposed algorithm has good load balance and is more efficient than Cignoni et al.'s algorithm and our previous algorithm.

We assume the multitape real-time Turing machine as a formal model for parallel real-time computation. Then, we show that, for any positive integer k, there is at least one language L_k which is accepted by a k-tape real-Turing machine, but cannot be accepted by a (k - 1)-tape real-time Turing machine. It follows therefore that the languages accepted by real-time Turing machines form an infinite hierarchy with respect to the number of tapes used. Although this result was previously obtained elsewhere, our proof is considerably shorter, and explicitly builds the languages L_k. The ability of the real-time Turing machine to model practical real-time and/or parallel computations is open to debate. Nevertheless, our result shows how a complexity theory based on a formal model can draw interesting results that are of more general nature than those derived from examples. Thus, we hope to offer a motivation for looking into realistic parallel real-time models of computation.

It is important for programmers to understand the semantics of a programming language. However, little work has been done about the semantic descriptions of HPF-like data-parallel languages. In this paper, we first define a simple language , which includes the principal facilities of a data-parallel language such as HPF. Then we present a denotational semantic model of . It is useful for understanding the components of an HPF-like language, such as data alignment and distribution directives, forall data-parallel statements.