Grand challenge problems See [WiAl 99]

A grand challenge problem is one that cannot be solved in a reasonable amount of time with today's computers.

These fundamental problems generate increasingly complex data, require realistic simulations of the processes under study, and demand intricate visualizations of the results See [Gran 99a]. These problems often require numerous large-scale calculations and have significant elements of multi-discipline and multi-geographic collaborations See [Gran 98]. Their solutions will have a broad economic and scientific impact, not only on the computing industry but probably on the human life in general See [Gran 99b]. The following list contains an overview of some problems in the Grand Challenges category as summarized in See [Gran 96], which can only give an impression of today's situation, since yet unrecognized application might emerge soon, for example from the expanding multimedia field See [Hoss 99].

Applied Fluid Dynamics

• Meso- to Macro-Scale Environmental Modeling
• Ecosystem Simulations
• Biomedical Imaging and Biomechanics
• Molecular Biology
• Molecular Design and Process Optimization
• Cognition
• Fundamental Computational Sciences
• Grand-Challenge-Scale Applications

Another idea would be to identify the equations, that have to be solved in order to get results for the Grand Challenge problems. These so-called Grand Challenge equations have been collected by See [Gran 99a]:

Newton's Equations

• Schrödinger Equation (time dependent)
• Navier-Stokes Equation
• Poisson Equation
• Heat Equation
• Helmholtz Equation
• Discrete Fourier Transform
• Maxwell's Equations
• Partition Function
• Population Dynamics
• Combined 1st and 2nd Laws of Thermodynamics
• Radiosity
• Rational B-Spline

To be more concrete, we will now give two representative examples of Grand Challenge problems in more detail:

Computational speed

• Amount of memory
• Accuracy of results

Clearly, computational speed is the most obvious characteristic required from a parallel computing system. Often, computations must be completed within a "reasonable" time period or have a specific deadline for the computations See [WiAl 99]. For example, the predictions of a weather forecasting program that requires two days to compute next days weather is certainly useless.

A second requirement is the amount of memory consumed by this large and complex problems, which can easily exhaust conventional computing systems. However, by coupling large numbers of processors which have access to their local memory, the total amount of memory can be scaled up. Please note, that the amount of memory also affects the computational speed, because obviously the data to be processed has to be transported from memory to CPU and return. This defines the need for a sufficient degree of interconnection bandwidth.

The last requirement is the accuracy of the results, that have to be computed. Yet, this is strongly connected to the other requirements, simply because the higher the computational speed and the amount of memory available, the higher the degree of accuracy that can be achieved. On contrary, restrictions in the available computing power and/or the available memory certainly reduce the obtainable accuracy, and many actual problems cannot be solved with sufficient degree of accuracy by today computers.

Multiple high-performance commodity priced compute nodes from regular commercial product lines (not special-purpose designs)

• Hierarchical memory systems (e.g. cache-only memory architectures and distributed shared memory systems with low-latency memory access)
• Very high performance storage and parallel I/O systems
• Scalable programming environments and operating systems
• A universal programming paradigm

Today, four years later than expected, the 1995 goal in execution rate was achieved, which can be attributed to the Accelerated Strategic Computing Initiative (ASCI) project See [ASCI 99]. This $1-billion program launched in 1994 by the US Department of Energy (DOE) seeks to build Tflop/s computer systems within 10 years See [Craw 96]. The participating government laboratories - Sandia National Laboratories, Lawrence Livermore National Laboratory, Los Alamos National Laboratory - collaborate in creating the leading-edge computations modeling and simulation capabilities required for maintaining safety, reliability, and performance of US nuclear stockpile and reducing the nuclear danger See [Gust 98]. Besides nuclear weapons research, simulation of other areas like biotechnology, medical and pharmaceutical research, weather prediction, aircraft and automobile design, industrial process improvement, environment projection, etc. are targeted See [HwXu 98]

The strategies adopted by the ASCI program have two notable features: accelerated development and balanced scalable design. Thus, ASCI aims not just at the peak speed of a particular computer system, but at a total system solution that can deliver sustained application performance at five orders of magnitude better than that in 1994. The scalable design approach defines the following steps See [HwXu 98]:

Focus on high-end platforms for scientific computing

• Use of commodity off-the-shelf (COTS) hardware and software components
• Use of massively parallel architectures

A step further than the ASCI program is targeted by the PetaFlops project See [NASA 97]. This project aims at the long term goal to achieve a supercomputing speed of 1 Pflop/s (10 5 flop/s). Recent studies suggest, that such a system could eventually be built in 2007 with exotic technologies and unknown costs. However, the more realistic idea is to build a massively parallel processor with conventional technology and COTS components by year 2015 at a cost of US$ 1 billion See [HwXu 98]. Such a system must effectively exploit massive parallelism in the range of thousands of processors to over a million of threads concurrently. In the following section, we will briefly summarize the historical steps that led to the current situation and have been performed to achieve these goals, before presenting an overview of the current state of supercomputer developments.

Supercomputer See [Morr 92]

Computer Technology: 1. Any of a category of extremely powerful, large-capacity mainframe computers that are capable of manipulating massive amounts of data in an extremely short time. 2. Any computer that is one of the largest, fastest, and most powerful available at a given time.

More characteristics are added by See [HwXu 98], who place supercomputers at the top of the pyramid of computer classes, because their sales volume is very low due to their high price. In addition, a supercomputer integrates many resources into a single system, employs cutting-edge technology, and has the highest performance.

Therefore, we can identify the following characteristics for a supercomputer at any given period of time:

Fastest available processing speed

• Largest possible memory size
• Biggest physical dimensions
• Greatest monetary cost

Please note, that these characteristics may be appropriate in most cases, but are also too vague to be exact. Thus, we need some kind of metric to establish a list of supercomputers, that must be based on one of the characteristics mentioned above. Since processing speed is obviously the most important identifier in many cases, we will now describe one approach to rank existing supercomputer architectures.

One Intel: ASCI Red

• One Hitachi: SR8000
• One IBM: SP Silver
• One SGI: ASCI Blue Mountain
• One SGI: Origin 2000/250
• Five SGI: T3E 900/1200

Please note, that the SGI ASCI Blue Mountain machine is actually composed of 48 Origin 2000 machines with 128 nodes each. Thus, it would be possible to identify this machine as a superscale SGI Origin 2000. As can be seen, SGI (Silicon Graphics) is currently the company with the most supercomputer architectures, which can be attributed to the acquisition of Cray Research, one of the traditional supercomputer manufacturers.

Another interesting fact, that is only indirectly given is the achieved level of peak performance, which is 67% for the Intel ASCI Red machine, but only 52% for the SGI ASCI Blue Mountain. The best result compared to the peak performance is reached by the Hitachi SR8000/128 (N=4), which achieves 85% although it consists of the smallest number of processors (128). The worst level of utilization for the Linpack benchmark is obtained with the IBM SP Silver (N=8), that achieves only 42% of its possible peak performance with a very high number of processors (1952).

the double number of transistors on a microchip for the same price of the chip.

• the double speed of the microprocessor for the same price of the chip.

while at the same time

the price of the microchip drops about 48% assuming the same processor speed and on-chip memory capacity.

One of the consequences of Moore's law is, that predictions about "the future supercomputer" are difficult, because technology changes constantly and will be completely different within a few years See [Simo 99]. Considering the performance of the Top 500 list, Moore's law would have expected an increase in performance of about 8 to 16 for the 6 years between June 1993 and June 1999. This has clearly been outdone by reality, with a speedup factor of 36 for that period. For the future, the ASCI program expects to extend from 1 Gflop/s in 1994 to 100 Tflop/s in 2004, which calls for a performance increase of 10 5 within this 10 years See [HwXu 98]. Yet, according to Moore's law, such a 10 5 -fold performance increase with constant hardware costs would require 26 to 32 years, which implies that 100 Tflop/s could not be achieved until year 2025.

Please note, that benchmarking is only one popular method to characterize the performance of applications and systems. Other performance metrics may be more appropriate for other areas of computing. Some well-known benchmarks are SPEC, NAS, STAP, LMBENCH, STREAM, PARKBENCH, Splash, TPC (Transaction Processing Performance Council) See [HwXu 98], and SKaMPI See [Reus 98].

SISD: Single Instruction stream, Single Data stream

• SIMD: Single Instruction stream, Multiple Data streams
• MISD: Multiple Instruction streams, Single Data stream
• MIMD: Multiple Instruction streams, Multiple Data streams

Another approach is the Erlanger Classification Scheme (ECS) developed by Händler See [BoHä 83]. It describes parallel computer architectures based on the number of control and processing elements that are available for problem solving. The notation divides the architectures into pipelining and concurrency principles, as well as mixtures between these two categories See [Quin 87].

These first two approaches to classify parallel systems are still widely used. Yet, today another way of distinguishing supercomputers seems to be equally appropriate. Kai Hwang and Zhiwai Xu identify five different classes of parallel architectures See [HwXu 98]4:

PVP - Parallel Vector Processors

• SMP - Symmetric Multiprocessors
• MPP - Massively Parallel Processors
• DSM - Distributed Shared-Memory Machines
• COW - Clusters of Workstations

Most of today's parallel machines are built with commercially available, off-the-shelf commodity hardware and software components. The only exception are PVP machines, where many building blocks are custom-made. Such systems contain a small number of powerful custom-designed vector processors, each capable of at least 1 Gflop/s performance. Examples for PVPs are the Cray C-90, the Cray T-90, and the NEC SX-4.

In contrast to the PVPs, SMPs apply commodity microprocessors with on-chip and off-chip caches, and access a shared memory through a high-speed bus architecture. These systems are symmetric, because every processor has equal access to the shared memory, the I/O devices, and the operating system services. A problem of SMP architectures is scalability, which is limited mainly due to the use of a centralized shared memory and a bus or crossbar system interconnect, which are both difficult to scale once built. Examples for SMPs are the IBM R50, the SGI Power Challenge, and the DEC Alpha server 8400.

The last three groups of parallel architectures, MPPs, DSMs, and COWs, are distributed memory machines, which allow to overcome the limitations of scalability and to take advantage of higher parallelism available in some applications of scientific computing, engineering simulation, signal processing, and data warehousing.

The group of MPPs generally refers to very large-scale computer systems. They apply commodity microprocessors with distributed memory as processing nodes, which are interconnected with a high communication bandwidth and low latency network, that can be scaled up to hundreds or even thousands of processors. Programs on these machines consist of multiple processes, each with its private address space, that communicate via message-passing routines. Synchronization takes place through blocking message-passing operations instead of shared-variable synchronization operations.

The DSM machines provide special hardware and/or software extensions, that provide the application user with a single address space although the memory is physically distributed among different nodes. Examples for DSM machines are the Stanford DASH architecture and the Cray T3D.

The last group of distributed memory machines is based on the cluster concept as implemented in Digital's TruCluster, IBM's SP2, and the Berkeley NOW. In a certain sense, Clusters are the low-cost variation of MPPs, which makes them an interesting choice for many research institutions (See [Buyy 99a] and See [Buyy 99b]). One important characteristic of COWs is that each node is a complete workstation (probably minus peripherals like monitor, keyboard, etc.) which is connected to the other nodes through a low-cost commodity network (e.g. Ethernet, FDDI, ATM, or Myrinet See [Pryl 99]). In contrast to MPPs, the network interface is only loosely coupled to the I/O bus of a node, and each node in a COW usually contains a local disk as well as a complete operating system, while MPPs may not provide a local disk at each node and only a microkernel.

However, it has to be noted, that the boundaries between these classes of supercomputer architectures are fuzzy, since it is often difficult to assign a selected hardware architecture to only one group. For example, the node of a COW may be an SMP itself, while DSM machines can also be implemented with software techniques on networks of workstations. Other examples are highly scalable clusters, which are often considered MPPs. Therefore, SMPs, MPPs, DSMs, and COWs are four overlapped architectural concepts as shown in Figure See Overlapped design space of clusters, MPPs, SMPs, and distributed computer systems [HwXu 98] See [HwXu 98]. For a more detailed discussion about the differences and similarities between these architectures, please take a look at See [HwXu 98] pages 31 to 36.

Another remark concerns the possibility extend the clustering idea into large-scale systems by connecting distributed supercomputer systems into so-called "Metacomputers" See [Brun 99], "Metasystems" See [Grim 98], "Computational Grids" See [FoKe 99], or the "Information Power Grid" See [LeKu 99]. A well-known example is the multi-institutional Globus project See [FoKe 98], which tries to enable computational grids that provide pervasive, dependable, and consistent access to high-performance computational resources for distributed users and resources. Such systems are composed from loosely coupled hardware architectures in order to perform computation on one particular problem See [FoKe 99]. Therefore, they are often addressed as the most-powerful computing platforms around.

Detect and exploit any inherent parallelism in an existing sequential algorithm

• Invent a new parallel algorithm
• Adapt another parallel algorithm that solves a similar problem

While sequential programming is already widely accepted and many people have been practicing it for a long time, parallelism is sometimes viewed as a rare and exotic subarea of computing, interesting and intellectually challenging but of little relevance to the average programmer See [Fost 94]. Furthermore, it is generally agreeable that parallel programming is in a sorry state, and we can identify the following reasons for its inferiority See [HwXu 98]:

Parallel programming involves all issues of sequential programming plus many more issues for managing the parallel complexity.

• Sequential programmers rely only on the von Neumann model, where a processor executes one sequence of instructions, while there exist many different parallel programming models See [Fost 94].
• Software environments (compilers, debuggers, profilers) are much more advanced for sequential program development.
• Sequential programming is more mature, with a huge base of accumulated knowledge, including mistakes discovered and lessons learned in the past.

Foster reports about studies of trends in applications, computer architecture, and networking which indicate that this view is changing. He believes that "parallelism is becoming ubiquitous, and parallel programming is becoming central to the programming enterprise" See [Fost 94]. This view is supported by Hwang and Xu, who describe recent advances in this area See [HwXu 98]:

Many parallel algorithms have already been developed or are currently being investigated.

• A small set of simple parallel algorithmic paradigms has emerged and is becoming accepted (e.g. phase parallelism, divide and conquer, pipelining, etc.).
• Native models are converging either towards the single-address space, shared-variable model for PVPs, SMPs, and DSMs, or towards the multiple-address space, message-passing model for MPPs and COWs.
• High-level models are converging toward three standard models, data parallel, message-passing, and shared-variable.

Before discussing these models, we will briefly identify the fundamental requirements for parallel software. Regardless of the architecture of the target parallel computer the challenge of parallel programming is to harmoniously coordinate several program segments while assuring correctness as well as high performance See [Lewi 93]. Due to the fact that good performance can only be achieved if an algorithm fits the architecture See [Quin 87], extensive interaction between algorithm designers and computer system architects is required See [Sieg 92]. Thus, it is necessary to investigate parallel programming paradigms in connection with the intended hardware architectures.

Programming model

• Data-parallel programming
• Task-parallel programming
• Parallelization approach
• Implicit parallelism
• Explicit parallelism

The parallel programming model identifies, how a program synchronizes its parallel parts. In the data-parallel or Single-Program-Multiple-Data (SPMD) model, the execution of the code is driven by the program's data, which means that the same code is executed on different data domains See [Hwan 93]. Therefore, the application's data are partitioned into separate sets, and identical operations are performed on all sets at the same time whenever possible. Obviously, the data-parallel approach is only meaningful, if large arrays of data are processed, e.g. with vectors and matrices See [Lewi 93]. This limitation does not exist in the task-parallel (also called control-parallel) or Multiple-Program-Multiple-Data (MPMD) model, which supports more than one thread of control. A single program can perform different operations in the same time interval, and different programs may operate on different data within one application. Additionally, the order in which concurrent parts are executed is governed by program control rather than by the availability of data.

Both types of programs, SPMD and MPMD, can be executed on MIMD architectures See [Flyn 72], because different instructions can be executed by different processes at the same time. However, SPMD programs may also be more restrictive, if they permit not only multiple processes executing the same code, but also require them to execute the same instruction at the same time. Therefore, such restrictive SPMD programs may also be executed on SIMD architectures See [HwXu 98].

In addition to the parallelism model, the parallelization approach describes different methods to develop corresponding programs for parallel machines. We distinguish two different ways of expressing the programs parallelism in the source code, implicit and explicit parallelism See [Bemm 92]. Implicit parallelism means that the program's parallelism is hidden from the programmer, who applies accustomed abstractions as available in sequential programming languages. The explicit parallelization approach is characterized by the active role of the programmer in exploiting the parallelism; the applied programming models offer explicit constructs for describing the concurrent execution as well as communication and synchronization between the processes.

Please note, that it is often difficult to draw a clear line between the implicit and the explicit parallelization approach. In fact, for some people implicit parallelism would mean to write purely sequential code and leave all the parallelization work to the compiler and the optimizer (see See [Bode 95]). For them, even adding declarative statements to the code would mean to introduce some explicit means of parallelization. This is for example the case in HPF-dialects (see below), which offer declarations to improve the compiler's results during data partitioning. Yet, these declarations are added in comments, so that every HPF program is still applicable to sequential machines. For that reason, the usual interpretation of explicit parallelism is, when the control flow of the program is actually determined by dedicated statements (e.g. for sending and receiving messages).

Another more practically oriented approach to characterize parallel programming is provided by Foster See [Fost 94] as well as by Hwang and Xu See [HwXu 98]. While Foster concentrates on the explicit parallelization approaches, Hwang and Xu also include the implicit approach. In concrete, they identify the following four models that are used on todays existing parallel computers:

Implicit

• Data-parallel
• Message-passing
• Shared variable

Although this list is somehow contrary to the classification described above and mixes some areas, it is well-established in the parallel computing community due to its relevance in practice. We will also stick to these items and describe them in more detail below.

Bernstein's theorem See [Bern 66]

In the general case it is undecidable whether two arbitrary operations in an imperative sequential program can be executed in parallel.

This theorem implies, that there is no automatic technique, neither compile time nor run time, that can fully exploit all potential parallelism in a sequential program. As a consequence to overcome this theoretical limitations, two solutions are suggested: Either apply explicit parallelism as discussed below or use a programming language which makes parallelism recognition easier and abolish the imperative style altogether. The latter is an important research issue, which includes besides others the following computational styles See [HwXu 98]:

Functional programming

• Logic programming
• Computing-by-learning
• Object-oriented programming

There are some advantages of these approaches, for example a purely functional program is coherent, meaning it is guaranteed to be determinate, deadlock-free, and compositional, and it is abstract, meaning there is no need to explicitly specify parallelism, communication, synchronization, scheduling, etc.

However, there are also advantages in the imperative style. Firstly, it is mature, time-proven and familiar to most programmers. Secondly, it is derived from the von Neumann model with commodity hardware and can therefore be implemented efficiently. Thirdly, the imperative style dominates programming of today's sequential and parallel computers. As a consequence, we will now focus on the explicit parallel programming models with imperative computational style.

HPF-like: Fortran 9x, HPF, CM C*

• Message-passing: PVM, MPI, SP2 MPL, nCUBE 2
• Shared-variable: X3H5, OpenMP, Cray Craft, SGI Power C

The HPF-like group (often called the data-parallel languages) assumes a single address space, removing the need for data allocation. However, many of these languages allow to apply data allocation with explicit directives to improve the memory accesses. In addition, HPF-like programs are single-threaded, which ensures that they are determinate and deadlock-free, and loosely synchronous, because there is no need for explicit synchronization.

For the HPF-like group, there are two influential standard languages: Fortran 9x and High-Performance Fortran (HPF). Programs written in these languages are portable on a wide range of machines (MPPs, DSMs, SMPs, COWs, and PVPs). Furthermore, there exist machine-specific languages, such as C* for the CM-5 (Thinking Machines Connection Machine), which are not standardized and thus not portable.

In message-passing programs, users must explicitly allocate data and workload to processes. Such programs are multithreading because multiple threads of control exist that may possibly execute different code. Therefore, both control parallelism (MPMD) and data parallelism (SPMD) are supported. In order to reduce designing and coding complexity, many parallel message-passing programs are implemented as SPMD programs, where only a single code is executed on all processes. (Consider an MPP with over 1000 processes, where each of them would execute a different program!) Furthermore, every MPMD program can be formulated as an SPMD program.

These programs execute asynchronously, which requires special operations to synchronize processes for correct execution order (e.g. barrier, blocking communication). Due to separate address spaces of the processes, the data variables in one process are not visible to other processes. Explicit interaction operations, including data mapping, communication, synchronization, and aggregation must be resolved by the user. This introduces the "owner-compute" rule See [HwXu 98], where the process that owns a piece of data performs the computations associated with it.

An advantage of the message-passing over the HPF-like languages is its flexibility. Yet, it still lacks support to manage a global data structure efficiently. In addition, message-passing programs usually exploit large-grain parallelism, which can be attributed to high communication latencies occurring during message transfer. For programming, there exist two widely used libraries, PVM and MPI, which will be discussed in more detail in Section See Message-Passing Programs. Both of them are implemented in virtually all types of parallel computers, thus ensuring a high level of portability for message-passing programs.

The last of the three explicit parallel models is the shared-variable model, often called shared-memory model. It is comparable to the HPF-like approach because it offers a single address space with global naming where all shared data reside. Consequently, there is no need for data allocation. Furthermore, it is similar to the message-passing model due to its multi-threading and asynchronous behavior, which again requires explicit synchronization methods for maintaining correct execution order. Yet, communication can take place implicitly through variable writes and reads in the shared memory.

A widespread misconception is that the shared-variable model is generally and in any case better suited for fine-grain parallelism than the message passing model See [HwXu 98]. This is not true because as a model it can be implemented on any parallel architecture, be it PVP, SMP, DSM, MPP, or COW. On contrary the only requirement for fine-grain parallelism is the existence of efficient communication and synchronization methods on the underlying platform. This includes, that a shared-variable program may incur higher interaction overhead and run more slowly than a message-passing program on a COW, an MPP, or even on an SMP.

The advantage of the shared-memory model is that it is assumed to be easier to program than message-passing programs See [Karp 87]. Some people consider message-passing as the low-level approach to parallel programming, while shared-memory is on a higher-level. While this popular statement is not wrong, it is also not an established fact backed by scientific research. Fact is that there are many more existing applications for SMPs and PVPs, than there are for MPPs and COWs See [HwXu 98]. Developing an efficient parallel program which is loosely synchronous and operates in a regular communication pattern does not necessarily favor the shared-variable approach, but may also be implemented with message-passing. The shared-variable model has an edge for irregular parallel applications, and wherever global pointer operations are required. Shared-variable programs do not require explicit partitioning and data allocation, although their absence may affect performance badly.

One big disadvantage of shared-memory programs is, that subtle synchronization mistakes may probably occur easily and more frequently than in message-passing programs (see Section See Errors from Process Communication and Synchronization) See [Karp 87]. In addition, there is no widely accepted standard yet, that allows to port programs easily between architectures See [HwXu 98]. Several solutions to this problem are in the line, most notable the three shared-memory programming standards ANSI X3H5, OpenMP, and POSIX Threads.

The ANSI X3H5 standard has not gained wide acceptance, but has substantially influenced the design of several commercial shared-memory languages. In fact, no commercial shared-memory systems adhere to X3H5 completely, although some parts are supported See [HwXu 98]. The X3H5 definition consists of a conceptual standard programming model and bindings for C, Fortran 77, and Fortran 90. Its main ideas are parallelism constructs, parallel blocks, parallel loops, implicit barriers, thread interaction, and synchronization.

Furthermore, it was the basis for the OpenMP standard See [Thro 99], which is now being supported by a group of hardware and software vendors, such as DEC, Intel, IBM, Kuck&Associates, SGI, Portland Group, Numerical Algorithms Group, US DOE ASCI program, etc. See [HwXu 98]. It is a set compiler directives, library routines, and environment variables that collectively provide a shared-memory API (Application Programming Interface) for different platforms and operating systems. The key features of OpenMP are compiler directives, called orphan directives, to enable parallel execution of major portions of the code with small code modifications. Besides that, OpenMP provides a set of run-time library routines with associated environment variables, which are used to control and query the parallel execution environment, to provide general-purpose lock functions, set execution mode, etc.

The POSIX Threads, also known as Pthreads, stands for the official IEEE POSIX 1003.1c-1995 thread standard, which was established by the IEEE standards committee. It offers function for thread management (create, exit, join,...), thread synchronization (lock, unlock, wait, post,...), and others. It is widely available as an influential standard for multithreading at the Unix operating system layer. An example are Solaris Threads, which offer many common features of Pthreads and are a mature commercial product.

Good Enough testing See [Bach 98]

Good Enough testing is the process of developing a sufficient assessment of quality, at a reasonable cost, to enable wise and timely decisions to be made concerning the product.

This definition identifies several characteristics of the professional software engineering task related to the quality of a product and its evaluation. The following questions are of major importance:

How accurate and complete is the product's quality assessment?

• What level of testing is possible within the project costs constraints?
• How well does the assessment serve the project and the business in terms of potential product risks?
• How to time all these activities?
• When has enough testing been performed?

Similarly, Dubois argues that the verification of a program is often based on a series of problems with known results See [Dubo 99]. Since it must be prepared to solve a general problem, its results can only be taken as an approximate answer and it requires good judgement to decide about the program's correctness and reliability. These differences between the actual and the desired answers arise from numerical noise, chosen approximations, inaccurate models of physical properties, or actual coding errors See [Dubo 99]. Therefore, it is often difficult to judge whether an answer is a bug or a modeling problem. Many bugs are indistinguishable from errors in modeling or deficiencies in the applied numerical techniques. At worst, a bug may cause a model's revision or a complete rejection of an approach. At best, a bug can only be detected through considerably high efforts of testing5.

Obtaining a formal specification of an informally described problem.

• Based on this formal specification, selection of a mathematical verification method to prove the software's correctness with effective, affordable methods

The quality of software is defined by its characteristics and features offered during application and development to achieve the demanded requirements See [FlZü 97]. Most frequently, these quality criteria are correctness, reliability and portability See [Enge 88]. The correctness of a program can be defined as follows:

Without stated requirements, no testing is possible.

• A software product must satisfy its stated requirements.
• All test cases should be traceable to one or more stated requirements and vice versa.
• Requirements must be stated in testable terms.

Static code analysis

• Test case preparation
• Test monitoring and output checking
• Fault isolation, debugging
• Retesting (once a presumed fix has been made)
• Integration of routines into (larger) systems
• Stopping

Static code analysis starts with the usual compiler diagnostics and detailed data-type checking. In addition control flow and reachability analysis are applied with structural analysis programs and others. As an extension to structural analysis tools, test cases preparation aids assist the engineers in choosing (input) data values to make the program execute along a desired path. Yet, these tools are only sufficient to generate a limited amount of inputs, for which the outputs must still be calculated manually or with other means of computer-support.

For this work, the more important parts are test monitoring and output checking, as well as fault isolation and debugging. In order to perform a maximum of testing automatically, techniques have been developed for various kinds of dynamic data-type checking and assertion checking, and for timing and performance analysis. In addition, test post-processing tools aid the users with output comparators and exception report capabilities, as well as test-oriented data reduction and report generation packages. For the area of fault isolation and debugging, we may distinguish well-established methods like core dumps, traces, snapshots, and breakpointing, from highly interactive capabilities like replay or backtracking.

After fixing the code, retesting is used to compare previous test cycles with the results of the corrected code. Again comparators to check the differences in the code, inputs, and outputs between the original and the modified program are applied. These test management tools are further extended for integrating the routines into bigger systems, where additional activities like interface consistency checking have to be performed. Finally, the halting problem of testing as defined above with Good Enough testing may also be supported by tools, which means that tools offer a means of quantifying the amount of testing that has been performed.

Debugging See [McHe 89]

Debugging is the process of locating, analyzing, and correcting suspected errors.

Today, a lot of a programmer's development time is spent on debugging See [Agra 91]. Therefore, it is often ranked as one of the most significant bottlenecks while at the same time the weakest link in the software life-cycle See [Stit 92]. The debugging phase is applied after runtime failures or incorrect results have been observed during testing. In that case, the errors and their origin must be detected and corrected See [Enge 88]. Whenever bugs arise, programmers should be able to locate and correct them with a minimum amount of effort, leaving more time and energy available for progressive work See [Stit 92].

While the importance of testing and debugging is highly accepted in the software engineering domain, there is still a surprising lack of books that thoroughly discuss software debugging at a practical level See [Stit 92]. Of course, there are books describing the features of one or more debugging tools from a user's view, but these do not provide a general look onto the problem of solving program bugs. From the scientific point of view, debugging is still studied very little, compared, for example, to compilers See [Rose 96]. In addition, debugging is still absent from current-day computer science curriculums, which leaves students and programmers without much guidance.

In See [Lieb 97], Lieberman defines debugging as "... the dirty little secret of computer science". He argues that the computer science community as a whole has largely ignored the debugging problem. Today's commercial programming environments provide debugging tools that are little better than the tools that came with programming environments 30 years ago. The most difficult problem is to figure out exactly what went wrong. This results from the fact, that programs are complex artifacts, and consequently, debugging often struggles against this complexity See [Lieb 97]. As a consequence, debugging is still a matter of trial and error.

Bug-hunting is often described as detective work. Stitt defines the phases of the debugging process to be arranged around the "research, gain knowledge and deduce phase". Furthermore, he identifies five major tactics of debugging, which may be used individually or in combination with othersSee [Stit 92]:

Preliminary investigations: is it really a bug?

• Static debugging: verification of requirements and design as well as source code analysis
• Run-time observation: testing, experimenting and analysis of program results
• Source code manipulation: instrumentation and partial execution
• Dynamic debugging: breakpointing, single-stepping, monitoring and testing

A tool that supports the user during this process is called a debugger. Two possible definitions are given below:

to follow the executable program step by step (tracing)

• to stop and continue the programs execution at breakpoints (breakpointing)
• to display and manipulate the contents of variables, registers, and memory locations (inspection)

In addition to these basic features, debuggers may also include support for more advanced or specialized activities. An example advanced technique often anticipated by users is program slicing, a technique which extracts only those lines of code that are related to the current track of investigations (see See [Weis 82] and See [Weis 84]). Other examples are debugging capabilities tailored to one particular set of errors, like memory leaks or incorrect pointer references.

Probably the most important activity of debugging is breakpointing. It is based on breakpoints, which can be defined as follows:

Error

• Failure
• Fault
• Bug

We will provide corresponding definitions in the following paragraphs, which have been derived from existing literature, in this case especially the opinions given in See [Brit 98], See [Choi 91], See [Enge 88], See [KrWi 98], See [McHe 89]. Probably the most precisely and formally defined approach is offered by Grabner's view of errors and associated program states See [Grab 99], which is also included in this section.

Error (informal definition) See [Enge 88]

An error is defined as the computation (calculation and outputting) of one or more incorrect results by a computer.

This definition of an error is the most commonly used, and the term "error" has also been used in Definition See Debugging [McHe 89] for debugging. The noted lack of precision is established by two issues: On the one hand, there needs to be a distinction between the observed erroneous behavior and the original error itself. On the other hand, the term "results" identifies not only the output of a program, but also incorrect states during execution.

Grabner discusses these problems in more detail by focusing on the states of application programs, which consist of simple and compounded instructions See [Grab 99]. For each of these instructions there is a well-defined initial state - before the instruction is executed - and a terminal state - after the instruction has been executed. A compounded instruction may consist of several intermediate states. During debugging, the user can investigate these states and apply corresponding activities. Grabner defines the state of a program during execution as follows:

State of program during execution See [Grab 99]

For a given view onto a program, let t represent the instant of time at the terminal state of instruction a t , and let s t ( v ) be the value of variable at time t .

Then, the state s t of the program at time t is the set of the values of its variables s t ( v ), so that: .

In this definition, a t is an instruction, whose operation assigns a new value to variable . Although the set V contains all the variables of a program, the user's main interests are those variables, that are modified by instruction a t See [Grab 99]. Figure See State of a program at a given instruction describes the relation between the instruction and its variables in a small diagram. In See [Pine 99], the author introduces another distinction by classifying those variables as "noncurrent", whose actual values as computed by instruction a t differ from the values expected by the user.

An important issue of Definition See State of program during execution [Grab 99] is the view onto the program. This view is usually defined by the user by selecting a corresponding granularity for the analysis activities. The most coarse granularity is certainly the program itself. In this case, the initial state is defined by the initial state of the variables, while the final state represents the results of the program. In most cases, the user selects a finer level of granularity. Typical examples for debugging are the instructions of the program in its high-level programming language or in assembler language See [Grab 99]. In Section See Program State Changes, we will review and adapt this definition of a program's state for our event graph.

Based on the definition of a program state, an error can formally be defined as follows:

Error See [Grab 99]

An error in a program is observed through an incorrect program state s t , which means that one or more variables contain a wrong value at time t .

In terms of errors, two kinds can generally be distinguished: hardware errors and software errors. The former result from erroneous functions of electronic elements, which have been initiated e.g. by dust, heat, variations in electrical currents, and others, or have been introduced through corrupted connections and cables or by other faulty components. The appearance of hardware errors leads to interruptions of service, which often result in complete breakdowns or system shutdowns. An improvement to this situation is offered by fault-tolerant systems, which increase the systems hardware reliability by incorporating replicated and redundant system components. In the scope of this work, we will not consider hardware errors any further, but instead concentrate on the second kind of errors, that manifest themselves in software.

Software errors (often called logical errors) are based on an incorrect sequence of statements, which can further be attributed to errors in the implementation or in the basic algorithm. These kinds of errors are related to program behavior, that is unexpected, unintended, or otherwise wrong due to some incorrect activity of a human or the environment See [KrWi 98].

Additionally, Britcher believes, that a fault is rarely the work of a single operation. More often than not is it a logical sequence that runs to dozens of lines of code and crosses modules See [Brit 98]. In this context, Grabner distinguishes between the following kinds of errors See [Grab 99]:

Errors of origin

• Subsequent errors

An error of origin is one, that is observed at the program state where it occurs initially. Therefore, such an error manifests the first occurrence of an incorrect operation. This is also the place, where the correction should be applied. However, since errors are seldom detected immediately, users are usually confronted with subsequent errors first. Such subsequent errors exist always only as a consequence of an error of origin. They reveal an incorrect program state, that results from both, their operation and incorrect input variables. This relation between several states of a program is also expressed in the term fault, which can be defined as follows:

Bug See [KrWi 98]

A bug is the commonly used term for an error with originally unknown location and reason. A bug can also be attributed to a poorly prepared and executed test, as well as a bad program description that may lead users to mistake correct behavior for bugs.

The notions and terms described above can also be described with a conceptual overview as presented in Figure See Conceptual overview of notions and terms. A special group are the false errors, which occur at state changes, that are incorrectly assumed to be wrong.

During debugging, we want to pinpoint the very origin of an error, i.e. the first incorrect operation, which is often a difficult task. For that reason, we may identify several more characteristics of bugs.

In principal, if the software's design is logically and mathematically correct, it should be so into infinity (with exception of certain types of calendar calculations - see Section See The Millennium Bug, "See The Millennium Bug"). Consequently, if a software error arises it may only originate from the following set of possibilities See [Stit 92]:

Included in the original design or coding.

• Introduced through program modification.
• Introduced as a side effect of another bug fix.

Additionally, there are those errors related to failures of the hardware on which the program is executed, and to the corruption of the media on which the program is stored. Software components differ fundamentally from hardware components, because they don't suffer from aging or transient failures. Instead, when software components fail, the reasons are See [Boyl 99]:

Inaccuracies of the problem specification, which results in programs that behave differently than intended by the specifier.

• Errors introduced during software development, which results in programs that behave differently than intended by the programmer.
• Errors introduced during compilation, which results in programs that behave differently than intended by the compiler.

The so-called group of "occasional errors" may reside undetected in a program for very long time, even several years. They manifest themselves sporadically only on certain rare combinations of input and system state See [BlWa 96]. These malicious errors may only surface, when other factors of the system environment change (e.g. marginal stack allocation, conflicting use of resources between system components, timing failures, and other results from heavy system load) See [Stit 92].

Stitt offers some more characteristics to establish a classification of errors with the following three classes See [Stit 92]:

Consistency: errors may occur either with consistency or with a frustrating lack of consistency

• Intermittence: both, consistent and variable type of failures may be intermittent
• Fuzzy cases: is the problem really a result of a errors?

These different characteristic are very useful during debugging. Only if users are aware about all the different possibilities, they are able to react to incorrect program behavior and perform corresponding error detection activities. To underline the importance of these tasks, the following section describes actual cases of erroneous behavior observed in computer systems.

Lethal errors

• Airplane crashes
• Governmental and commercial mishaps
• Internet worm/hackers
• Millennium bug

The radiation controllers in two Japanese nuclear power-plants failed to operate correctly, requiring to manually input the correct data.

• Seven US nuclear power-plants reported minor problems, although none of them affected safety systems.
• A US spy satellite and a French military satellite encountered minor glitches, but were reportedly never out of control.
• The atomic weapon laboratory in Oak Ridge, Tennessee, which is also the biggest US uranium depot, faced allegedly harmless date problems
• Egypt's national news wire service briefly stopped filing.
• In three Swedish hospitals cardiac control systems shut down operation.
• A Stockholm bank refused electronic access to customer's accounts.
• A bank in Cologne incorrectly transferred several millions to some customers.
• Several hundred slot machines at the Delaware horse track shut down operation.
• A CyberCash credit-card verification caused duplicate transactions.
• Some jail sentences in Italy were increased by a century due to Y2k-bugs.
• The South-Korean Millennium Baby was registered with an age of 100 years.

These news items are also confirmed by official authorities. The US government (President Clinton's Y2k-representative John Koskinen) announced, that only minor incidents have been observed, which have been solved immediately. A similar statement was issued by Bruce McConnel, the Year 2000 representative of the United Nations, who stated, that globally no major disturbances have been perceived. Yet, the French magazine "01-Informatique" reported, that more than 15 percent of the French industry observed glitches due to the Y2k-bug, especially in the areas accounting and finance, but also in personnel, payment, and production.

However, all in all it seems, that the preparations for the Y2k-bug have paid off. Considering the amount of money, this was not a cheap effort. For example, the US government estimates, that governments and companies worldwide spent US$200 billion to prevent a Year 2000 catastrophe. These numbers are even exceeded by the International Data Corporation (IDC), who reckoned up to US$280 billion, while the Gartner Group evaluated even US$300 to US$600 billion in expenses. Of course, these amounts and the actually observed effects of the Y2k bug lead to some critical voices concerning waste of money. There are some critical issues, that have to be mentioned in this context. Firstly, it remains to be seen if the upcoming months still do not reveal any major Y2k failures. Secondly, it will forever be unknown, what would have happened if these investments in the information technology sector would not have been placed in advance. Thirdly, there is always the problem of concealment, and some (probably critical) Y2k-issues will never be revealed in public.

Related to the Y2k bug there are other notorious dates, like February 29th, 2000, which is an intercalary day that may be missed by some systems. Another previous example is the "Nines Problem", which was predicted for September 9th, 1999. Concerns over this date arose from a programming convention that used four nines in a row - 9999 - to tell computers to stop processing data or to prepare for maintenance. Some thought, that the 9/9/99 would be a precursor to the millennium bug, although the latter is expected to be much more critical. Yet, September 9th, 1999 has passed without any major incidents or disruption of computer systems in Asia, Europe, and the US. Some reasons for this unexpected non-appearance are, that the date would have to be stored in BCD or ASCII-format and would equal "090999" or "990909" as usual.

Simple checking See [BlWa 96]

Let f be an arbitrary mathematical function. Then consider the following task: given an input x and an output y , determine whether or not y = f(x) ; that is, determine whether or not the input/output pair represents a correct computation of f . This task is called simple checking .

In this case, the function f ( x ) describes the behavior of some program P ( x ) as intended by the user. Therefore it serves as a specification of intended program behavior, which is required for evaluating the correctness of the program as defined in Section See Software Quality. To recapitulate, a program is always correct relative to its specification. This correctness is verified during testing cycles, which apply simple checking iteratively for a set of inputs .

Setting a breakpoint7

• Executing the program until the breakpoint
• Analyzing the process state at the breakpoint

The connections between these three activities are described with Figure See Iterations of the debugging cycle. The first time-line shows one iteration of the testing cycle from Figure See Traditional testing and debugging cycle. Given some arbitrary input, the program is executed until it arrives at an observation point. At this point, an error is observed, which means that either a program failure occurs or incorrect results are detected. Obviously, the reason for this incorrect behavior must be placed at the observation point or somewhere before the observation point. Thus, the problem of the debugger is to deduce the conditions under which the program produced the incorrect output See [Agra 91]. This characterizes debugging as a "backward" process. In practice, this activity is called "flowback" analysis See [Balz 69] and there are basically two solutions to this problem:

Reverse execution

• Backtracking with re-execution

The best solution would be to execute the program backwards one step at a time, starting at the observation point up to the point of the bug's origin See [Choi 91]. By comparing the states of the program at each of these steps, the error would be localized between the point where the state of the program was what was expected and the first point where the state was not what was expected See [Paul 99]. However, while this optimal solution could certainly improve the situation of many debugging users, it is not feasible in reality. The reason is that it is practically difficult and most times impossible to execute a program reverse in time, because many statements in a program and therefore the computing processes are irreversible8. One obvious example is the manipulation of file pointers and I/O descriptors See [Feld 88].

As a consequence, debugging is always based on backtracking by re-execution, where the program's statements are executed using their original order. The goal is the same as for reverse execution, to track the processes' history backwards in time from the manifestation of the error (the observation point) to the point at which the bug initially caused the erroneous behavior See [Choi 91].

In order to investigate the history of the process, the user is provided with the illusion of reverse execution See [PaLi 88]. To achieve this, a breakpoint is positioned somewhere in the code before the observation point as visualized with the second time-line diagram of Figure See Iterations of the debugging cycle. Since it is a priori unknown, if the breakpoint is really adequate, it can only be positioned at a suspected error location. Afterwards the program is executed until this breakpoint is reached. At this suspected error location the process state can be analyzed and information about the program's behavior can be gained. If this information is sufficient, and the bug has been detected, the debugging cycle is stopped and the faulty lines of code can be corrected. Otherwise, the error may either be located before or after the selected breakpoint location, which defines the new suspected error location. If the current breakpoint is placed after the new suspected error location, the program has to be restarted and executed again up to the new breakpoint. On contrary, if the current breakpoint is before the new suspected error location, it is usually easy to continue execution from the current position.

Some related work in this context are the prototype implementations of IGOR See [Feld 88], Spyder See [Agra 91], and PPD See [Choi 91]. IGOR is a tool that supports reversible execution with a mechanism available on arbitrary virtual memory systems See [Feld 88]. The basic idea is to peek at the virtual memory page tables and trace the reasons why these pages have been dirtied since the last checkpoint. A different approach is taken by Spyder, a debugging tool for monoprocessor C-programs which offers dynamic program slicing See [Weis 84] for execution-backtracking See [Agra 91]. Initially, an arbitrary variable and a corresponding program location is selected, for which Spyder automatically determines the statements that affect its value up to that position in the program. After executing the program with different test cases, Spyder helps to decide which statements in this dynamic slice to examine first. And finally, it allows to restore the program state at any location by backtracking the program execution to that location, without requiring to re-execute the program from the beginning.

A prototype debugging system dedicated to parallel programs of the Sequent Symmetry shared-memory multiprocessor is the Parallel Program Debugger PPD See [Choi 91]. It provides information on the data and control flow of a program's execution, while trying to keep both execution-time and debug-time overhead low. This is achieved by combining incremental tracing and program re-execution. With incremental tracing, the amount of tracing is selected according to the needs of the debugging user. Initially, only a small amount of trace data is generated during program execution. Afterwards, this initial data is supplemented during follow-up debugging cycles by detailed information, which is generated by tracing only selected parts of the program that are re-executed on demand.

The biggest problems of these approaches are the costs associated with restarting the program's execution, which is especially unacceptable for larger programs See [PaLi 88]. As a consequence, a variety of solutions is proposed to restart the program from intermediate code positions. In 1969, Balzer introduced the "history tape" within the EXtendable Debugging and Monitoring System See [Balz 69]. This is a observation capability that collects and stores all the data about a program's execution in order to format and present it to the user during debugging. Based on these data, flowback analysis can be performed by constructing an inverted tree, that describes how information flowed through the program to produce the value at the bottom node of the tree. In addition, a function for debug-time history-playback allows to retrieve information from the history tape, at any time of the program's execution.

The problem of the history tape is, that it requires enormous amounts of memory and is practically useless for present-day applications. In order to decrease these memory requirements while at the same time omitting the need to restart the program's execution at the beginning is to store required execution data periodically during the program's execution See [PaLi 88]. This is called "checkpointing" and provides the possibility to restart the program at all the places, where a snapshot of the program has been saved See [Feld 88]. While this approach is especially useful for debugging, it has also been used simply to ensure efficient usage of expensive computing environment, whenever long-lasting programs are executed and require a certain degree of fault-tolerance. In contrast to pure debugging, the main goal of checkpointing is to resume the execution, whenever a program's execution fails due to the loss of some external service See [Plan 95].

The traditional approach to testing and debugging as described above provides a brief overview of these activities and how they are usually carried out for sequential programs. Several testing and debugging tools have been developed that support users in that area. In addition, programmers tried to apply the same kind of techniques to parallel programs, and expected similar results. Yet, there are some fundamental difficulties that have to be solved for parallel program debugging, which cannot be mastered with this traditional debugging cycle. These problems will be discussed in the next section, before proposing a revised debugging approach that is also sufficient for testing and debugging of parallel programs.

The Heisenberg Principle: a debugger should intrude the debuggee only in a minimal way.

• Truthful debugging: at all costs, the debugger must be truthful so that the programmer may always trust it.
• Program context information: the most important issue is the presentation of content information, to know where one is.
• Debugging trails system development: any debugger that may be applied is almost always behind the technology one is using.

The Heisenberg (Uncertainty) Principle describes the intrusiveness of the probes inserted into any system being measured or tested See [LePa 85]. Originating from quantum mechanics, it states that one can never know everything about a quantum state See [Feyn 96]. Applied to software, another name for this behavior is the "Probe Effect" See [Gait 86], while errors established by these effect are often called "Heisenbugs" See [LePa 85]See [Rons 00]. Obviously, the intrusion should be kept a minimum in order to guarantee analysis data as correct as possible. In particular, the act of debugging an application should not change the behavior of the application. Otherwise, the usefulness of the debugger falls into question See [Rose 96].

In software debugging, a debugger violates the pure Heisenberg Principle in many ways, simply because it is in memory and controlled by the same operating system as the application being observed. This can affect the application in many ways, especially if the program is parallel and nondeterministic. For that reason, we will describe the Probe Effect in more detail in Section See The Probe Effect.

Bugs that are affected by this sort of thing are rare but extremely challenging and time-consuming because they are now so elusive. For sequential programs, bugs of this sort may also disappear when print statements are added to the source code of the debugged application, because the addition of the print statement may shift objects around in memory just enough to move the elusive bug somewhere else or even masks its existence. Another example is the disappearance of bugs when run under the auspices of a debugger, which leaves developers with no effective way to proceed See [Rose 96].

The most simplest solution for the Probe Effect would be to constantly perform program observation. In this case, the observation data describes the program's behavior accurately, but can be thrown away if not needed. This approach has been proposed many times, but isn't relevant in practice. Its main disadvantage is that observation activities need to be pinpointed well in advance, which makes this solution to rigid for practical usage. In addition, it requires some mechanism for managing observation data, which would be especially crucial on multitasking, multiuser systems.

Another critical issue of debugging is to always provide truthful information during debugging, which means, that the debugger must never mislead the user because the user is frequently testing out theories of how the observed failure may be cause See [Rose 96]. Obviously, any misinformation will direct the user in a potentially wrong direction, may cause a general lack of trust into the debugging tool and will dramatically hamper effective progress simply by devastating the user. Some big problems of debuggers are observed with optimized code, simply because the optimizing compiler changes the code radically and may prevent accurate information about how the optimized code maps back to the original source code. Another problem is observed, when variables are inspected which are currently being transferred between their actual memory location and the processors registers. Furthermore, compilers may eliminate unused variables from the code, which may be difficult to be recognized by the debugger See [Rose 96].

The most important issue for the debugging user is program context information, which may include several different types of information about source code, stack back-trace, variable values, thread information, and others. Therefore, a debugging tool must always relate the manifestation of the bug with the original lines of source code See [Rose 96]. In principle, programs can only be debugged, if the connection between their behavior and the original source code can be established See [Baec 97]. Yet, these lines may not contain the actual cause of the bug, because many bugs occur in a place much earlier to the manifested effects. Thus, the next important issue is to backtrack the code to the original place of the bug, the root-cause.

And finally, one of the biggest problems of debuggers is, that system developments occur long before any corresponding strong debugging support for the new systems developments is available. System vendors react to the mass market, which in turn requires certain technologies. Of course, debugging is only one of these technologies, but only with sufficient support for debugging, reliable systems may be developed. Therefore, Rosenberg suggests, that debugger developers need to push the systems vendors to provide the necessary infrastructure in order to enable support of the latest debugging technologies, while at the same time application developers need to push for debuggers in order to debug their complicated applications on the new architectures with its next great features See [Rose 96].

Increased complexity

• Amount of debugging data
• Additional anomalous effects

One reason is the increased complexity of parallel programs compared to their sequential counterparts. While most sequential debuggers perform symbolic debugging9 on source code level, this may be hard in the parallel case.

For example, consider opening a source code window for each participating process, and perform debugging a program with more than a handful of processes. It has been noted before that text is inappropriate in many cases to display and manage the inherent complexity of parallel programs See [Panc 96a]. Therefore, some means of abstraction seems useful to establish a layer above the source code level. However, it has also been noted above, that some connection to the original lines of code is required in order to detect the corresponding location of faulty statements.

Another reason is the possible huge amount of storage required for debugging data, that has to be provided and analyzed. Since debugging is based on the program's results and the states of the processes during execution, analyzing these data from massively parallel programs may impose a heavy burden onto developers. Often immense and uncontrollable amounts of data are obtained See [Ober 98], and users are often overwhelmed with potentially irrelevant data See [Reed 97]. The result is the so-called "maze-effect" See [Damo 94], which means that observers are completely lost. Although this is also possible in the sequential case, it is much more likely in parallel machines, simply because of the increased amount of debugging data. Therefore, a debugging tool must allow to concentrate on the essential details, instead of flooding the user with all the possible data See [Netz 96].

In addition there are other problems which exist on smaller program scales, too. An example is the set of errors in parallel programs, which consists of multiple sequential bugs and errors established by synchronization and communication of concurrently executing tasks. While the multiplication of sequential bugs may already represent a big obstacle, the existence of anomalous effects due to concurrency makes parallel debugging even worse. The reason for these effects in parallel programs stems from the increased influence of the underlying parallel hardware system. Consider the debugging cycle for a simple program, consisting of the subfunctions f0, f1,... fn as sketched in the left diagram of Figure See Comparison of sequential and parallel program influences [KrVo 98]. Applying the simple checking method, we would use repeated executions in order to determine the correct intermediate states between these subfunctions. If the sequence of subfunctions f0, f1, and f2 describes the desired computation, the resulting output y is determined by the provided input x and the interaction with the system environment. If the input is the same and system-interactions can be reproduced, each iteration of the debugging cycle would yield the same output, and intermediate results can be analyzed with breakpoints and single-stepping during iterative re-executions.

In parallel programs the situation is more difficult, because the subfunctions are executed on concurrent processes and all process-interactions are influenced by the computer system. Consider the parallel program of Figure See Comparison of sequential and parallel program influences [KrVo 98], consisting of subfunctions f0, f1, and f2 on process 0, as well as g0, g1, and g2 on process 1. Again the output is determined by the computation of these subfunctions, the input x, and all system interactions. Since communication and synchronization are carried out by the system, even small changes in the system state may trigger different behavior See [Netz 96]. Some of these system characteristics are (compare with See [McHe 89] and See [Kran 97a]):

Processor speed and load imbalance

• Scheduling decisions of the processor and the operating system
• Cache contents, cache conflicts, and memory access patterns
• Network throughput and network conflicts (latencies, contention)
• Nondeterminism on the interconnection network

Unfortunately several of these environmental parameters cannot be controlled by the user, neither during subsequent executions of the program in the testing cycle, nor during the debugging cycle with the debugging tool. Therefore, these small variations in the system environment may vigorously influence the execution path of a program and introduce lots of difficulties for program testers and debuggers.

Deadlocks and livelocks

• Stampede and bystander effects
• Irreproducibility effects
• Completeness problems
• Probe effects

Deadlocks and livelocks are well-known effects arising from concurrently executing and communicating or synchronizing processes (e.g. See [GlSh 80], and See [Nata 86]). The former describes the situation, where each of the participating processes is mutually waiting or blocked until one of the others does something See [MaJa 97]. The latter characterizes a group of processes that is continuously changing their state in response to changes of other processes without doing any useful work See [Buth 99]. In both cases, the program's progress is suspended until something resolves the conflict. As a side effect, the state where each of the processes persists, is usually a good starting point for debugging, and errors of this type can usually be corrected easily See [SnHo 88]. Several tool exists for deadlock and livelock analysis. A recent example is the Deadlock Checker See [MaJa 97], which uses various innovative techniques to prove deadlock and livelock-freedom for communicating sequential processes. Other solutions are described in See [Chan 83], See [Germ 84], and See [Sing 89].

In contrast, stampede and bystander effects are much more difficult to debug. The stampede effect See [SnHo 88] may emerge after an error has already been encountered on one process. However, since it is rarely possible to stop all the other processes immediately, they may continue to execute and stampede over the evidence of this original error. As a consequence, only limited useful information is left for the subsequent debugging process. In case of the bystander effect See [SnHo 88], the data space of one process is corrupted by another one. Obviously, the corrupted process is the first candidate for debugging, when in fact a different process originally caused the damage.

The effects described so far exist in any system composed from concurrently executing processes. In contrast, the irreproducibility effect and the completeness problem may only emerge in nondeterministic parallel programs, while the consequences of the probe effect are much more critical in this type of programs. Due to this fact, understanding, writing, and debugging nondeterministic programs is accepted to be one of the most difficult activities in parallel software development See [McHe 89]. Consequently, a debugging tool should be able to cope with this group of effects, if it is intended to provide sufficient support during program analysis and error detection.

Determinism See [Enge 88]

A program executed by a machine is called deterministic, if there exists exactly and only one follow-up state after each programming statement. This means, that the follow-up statement of any statement is always uniquely defined. In addition, every deterministic program must terminate10.

Obviously, a program with deterministic behavior offers some desirable qualities, and developers believe, that consistent and reliable software products must be deterministic See [Stei 98]. Yet, it also restricts the programmer's and their code too much for many applications. This is also expressed in some research papers, which believe that the importance of nondeterminism is steadily increasing, especially in the domain of parallel and distributed programming. An important goal is to obtain a better level of performance. If the usage of nondeterministic communications is increased, the degree of parallelism can be raised. As a consequence, potential parallelism in parallel or distributed computing systems is better utilized than in deterministic programs.

A simple case is a FIFO queue (First In - First Out), where data is processed based on their order of arrival See [NeMi 92b]. An actual example is offered by parallel ray tracing algorithms (e.g. See [CaSc 89], and See [JeRe 92]), which compute the final results by dividing the scene onto concurrent processes. The load is distributed between the processes by a master-worker scheme, that handles requests on a first come first served basis. Due to the nature of these algorithms even the same scene may be computed by different processes with a different order of the traced rays.

Although this is obviously the most important reason for using nondeterministic communication features, there are other substantial reasons, for instance when modelling reality. If the computing system simulates a natural phenomenon with nondeterministic characteristics, the simulation program must reproduce the same behavior. Please note, that this is usually implemented with random number generators, but it is also possible to achieve similar results with nondeterministic communication statements. Typical applications in this domain are chaotic, physical computations, which may be inherent nondeterministic. Examples are crashtest simulations for car manufacturers (e.g. PAM-CRASH See [Lons 94] and See [Lons 95]), where different results may be observed although the same kind of impact is used as an input. This represents reality, because the deformation of objects is determined by the applied forces and variations in the environment that are to inconceivable to be modelled. Thus, there is a certain degree of chance involved.

Another reason for using nondeterminism, which is probably more error-prone than the reasons described above, is "programmer's laziness". Often, determining the correct order of nondeterministic events is much more difficult than choosing one of the possible events. Thus, the program is implemented to react to the most likely program states in a way that is assumed to be correct. Yet, this method contains a major pitfall, because introducing nondeterminism often introduces unexpected behavior under certain conditions, which results in hazardous, occasional bugs (see See Definition and Classification of Errors). Therefore, this kind of using nondeterminism should clearly be avoided as much as possible.

Connected to programmer's laziness is our last example of nondeterminism in software, which may be labeled "accidental nondeterminism" or unintended nondeterminism (see See [DaFr 94], See [Kran 96d], and See [KrWi 98]). While all the reasons above apply nondeterminism intentionally, some programs contain nondeterminism without the user's knowledge. In this case, unintentional nondeterminism is creeping into the code due to misplaced or misused synchronization or communication functions. This is very dangerous, because users are unaware about the potential havoc and may therefore miss to check for this possibility.

As a next step, we will now define nondeterminism based on the definition of determinism above, because obviously any program that is not deterministic is nondeterministic. At this point, we should remark that nondeterminism is sometimes called nondeterminacy (e.g. See [EmPa 88], See [Emra 92], and See [DaFr 93]) or even indeterminacy (e.g. See [LeMe 87]), but all these terms describe the same characteristics. We will stick to nondeterminism, since it is the most widely used of all these alternatives.

Nondeterminism

A program is nondeterministic, if - for a given input - there may be situations where an arbitrary programming statement is succeeded by one of two or more follow-up states. This freedom of choice may be determined by pure chance or unawareness of the complete state of the execution environment.

This definition shows that the key problem of nondeterminism is the absence of sufficient knowledge about the actual, complete state and its follow-up states in the computing environment. This leads us back to Figure See Comparison of sequential and parallel program influences [KrVo 98], which described the differences between sequential and parallel programs, and the influence of the computing system, respectively. As mentioned before, it is difficult if not impossible to describe the complete state of a parallel computing system at any time during a program's execution.

Based on Definition See Nondeterminism, we will now try to characterize a nondeterministic program with the following definition:

Nondeterministic programs

Nondeterministic programs do not fully specify all possible execution sequences, but allow a degree of freedom in selecting subsequent program states. Consequently, a program is nondeterministic, if successive executions of the same program may yield different results although the same input is provided See [NeMi 92b].

There are two remarks to this view about nondeterministic programs. Firstly, the input must be valid according to the program's specifications. This means, that only input data that may actually be processed by the application may be considered. The reason is, that illegal input may affect the program's execution in an undefined, unexpected way and may thus also be responsible for different results during successive program executions.

Secondly, the appearance and composition of the program's results have to be discussed in more detail. The question is, what are the actual results of a nondeterministic program? Of course, most important are the final results of the computation, which (hopefully) represent the purpose of the application and intent to provide a solution for the user's primary goal. Yet, in the sense of testing and tuning, it may also be interesting to determine those factors besides the input, that influenced the results of the program. Therefore we include the following items in the term "results" of Definition See Nondeterministic programs:

Final results

• Intermediate results
• Interaction patterns between concurrent processes

All these items are influenced by the nondeterminism of the program and may thus vary in subsequent executions although the same valid input is provided. This distinction is necessary if the correctness of the program is investigated. The reason is, that it may be possible to obtain correct final results with different intermediate results for any nondeterministic program. In addition, we may observe the same final results from a parallel program, whose execution varies in the interaction pattern of its processes. As a consequence, the possible nondeterministic behavior of the program is often concealed for the user, which means a high potential for malicious occasional errors. Such programs may even operate correctly for long periods of time, until suddenly incorrect results are revealed.

Please note, that most research papers in this domain (e.g. See [SnHo 88], See [McHe 89], See [NeMi 92b]) consider only the results of the program as being important. Only recently, Ronsse et al distinguish between external nondeterminism and internal nondeterminism See [Rons 00]. External nondeterminism means that an application returns different results for repeated executions with the same input data, while internal nondeterminism means that repeated executions with the same input yield the same results, but the internal execution path is different.

In addition, See [DaFr 94] distinguish intended and unintended nondeterminism, and propose to leave intended nondeterminism without investigation. Unfortunately, this leaves the problem, that even intended nondeterminism may reveal program errors. Similar ideas are described in See [NeDa 94] and See [Netz 96], who characterize feasible nondeterministic events as well as artifacts occurring due to nondeterminism, and propose to detect the set of artifacts and simply ignore them. Although these viewpoints may contain a critical pitfall as described above, we found only Oberhuber See [Ober 98] to cover variations in the communication/synchronization pattern of concurrently executing processes.

External sources:

• Interrupt service routines for handling requests from I/O peripherals
• Internal sources (defined by the program itself):
• Return values from system calls like random number generators See [NeMi 92b]
• (Internal) communication or synchronization functions

The main distinction between external sources and internal sources identifies those items that can be controlled by the program and those that are completely independent from the user's code. In principle, external sources should be handled completely by the operating system, and should not interfere with the program in any case. Although these reasons may introduce very problematic situations, we may assume that their exceptions are covered by the operating system. Thus, we will not discuss them in more detail. (Please remember, that operating systems are also software and many critical errors are included in them, too - see Section See An Example of Bug Potential)

In addition, external sources like interrupt service routines and return values from the random number generator, do exist in sequential as well as in parallel programs. Thus, a parallel debugger must handle each of these cases, but there are solutions for covering internal sources in sequential tools. (In Section See Random Number Generation we will briefly discuss the integration of functionality for random number generators in our approach).

The remaining item - (internal) communication and synchronization functions - only exists in parallel programs, which contain concurrently executing and interacting processes. The question is, whether or not some kind of ordering is enforced onto the process communication and synchronization. If the interaction between the processes of one program is strictly ordered for all possible inputs, the interaction pattern will be the same for each execution. In that case, communication and synchronization does not introduce nondeterminism in the program's behavior. On contrary, if the parallel environment permits different orders of process interaction, the results of the program may possibly be influenced by the order that occurs during program execution. Such a place in the code, that allows different orders during program execution, is called a "race condition". A possible formal definition to race conditions is offered by Helmbold and McDowell:

Equivalent execution See [Leu 90]

Two executions of a process p are considered to be equivalent, if the process p receives the same information from the other processes at the same instants. The instant of an arbitrary event is defined by the interval in which only this event takes place. This means that two executions of a parallel program will be considered to be equivalent if the execution of each of its processes is equivalent

In order to achieve such an equivalent execution, all the elements that influence a process have to be determined. These are the input data provided by the user and the items identified as reasons for race conditions in Section See Race Conditions. Since equivalent input is a basic requirement for the debugging cycle, any method offering equivalent execution must only reproduce the return values from system calls and equivalent communication and synchronization functions.

The solution of record&replay methods is based on a two-step approach. During an initial record phase, the order of critical elements is stored in tracefiles, so that the tracefiles contain sufficient data to describe all the choices taken at nondeterministic events in the code. Afterwards, if the program has to be re-executed and an execution equivalent to the initial record phase is needed, these tracedata are used as a constraint for the program. This is performed by the replay tool, that forces the target program to take the same choice at any nondeterministic point as has been taken during the record phase. If the order of all elements is the same for every program run, their behavior is equivalent and the same errors and results are observed. Thus, record&replay methods allow nondeterministic programs to be tested and optionally re-executed according to the users needs.

The history of record&replay techniques - sometimes called deterministic execution See [CaTa 91], trace-driven simulation See [Fren 95], or instant replay See [LeMe 87] - dates back to an approach by Curtis and Wittie See [CuWi 82], who proposed a technique to record the contents of each message as it is received by the corresponding process. Similar approaches are described in See [Smit 84] and See [LeRo 85] with the advantage that selected processes could be replayed in isolation. Yet, the biggest drawback of these approaches was the requirement of significant monitor and storage overhead. Thus, this data-driven approach to record&replay techniques was dropped for control-driven approaches. The latter only preserve the order of occurring operations, and generate the transferred data again during each replay execution.

Probably the first control-driven approach of record&replay was Instant Replay by LeBlanc and Mellor-Crummey See [LeMe 87]. Their idea was to trace the relative order of significant events (usually communication events occurring at send and receive function calls) instead of the data associated with these events. Since the contents of all process interactions do not need to be stored, this approach requires less time and space to save the information needed for replay. In addition, Instant Replay does not depend on a particular form of interprocess communication. Indeed it was originally intended to be applied for debugging parallel programs on tightly coupled multiprocessers, where processes communicate via shared variables and more frequently than in message-passing systems See [LeMe 87].

Several other record&replay methods have been implemented as an extension of Instant Replay. In fact, most existing prototype tools that allow analysis of nondeterministic parallel programs are based on this approach. Some example implementations of record&replay tools are IVD See [Mack 93], Panorama See [MaBe 93], PDT See [Clem 95b], Buster See [Xion 96], and DDB See [SiRa 97].

In See [Mack 93], a program replay mechanism for the message passing library PVM is described, that has been developed and integrated in the Interactive Visualization Debugger IVD See [Hao 93]. Another integrated parallel debugger for PVM programs that includes record&replay capabilities is Buster, which is described in See [Xion 96]. On contrary, the Panorama debugger has been implemented for the Intel iPSC/860 and the nCUBE architectures See [MaBe 93], and supports both on-line and post-mortem debugging. In this case, on-line means that the debugger is running without any constraints, while during post-mortem re-execution the program's behavior is controlled by a simple record&replay facility.

The Parallel Debugging Tool PDT is announced as an interactive, source-level debugger for distributed-memory parallel programs within the Annai programming environment See [Clem 95a]. It offers debugging support for high-level data-parallel programs based on High Performance Fortran (HPF) as well as message-passing programs based on the MPI standard See [Clem 95b]. For MPI programs, PDT also includes a record&replay mechanism, which represents an implementation of the approach described in See [NeMi 92b] (see below) with an extension for asynchronous probe primitives. The main problem of this approach is its high amount of monitor overhead, which is generated by maintaining extensive timing information during the record phase.

Another implementation of Instant Replay is included in the Distributed DeBugger DDB See [SiRa 97], which targets at the multihreaded Mach distributed operating system developed at Carnegie Mellon University. One of the key goals of Mach is to support a distributed system on top of heterogeneous hardware platforms. This is only one of the characteristics addressed by DDB, which supports the minimal requirements for debugging distributed programs as identified by its authors. In their paper See [SiRa 97], they authors also cover 29 other distributed debuggers and classifies them according to the following criteria: What kind of replay is provided? What types of breakpoints are supported? What effects can be controlled with breakpoints? Which event types are observed by the system?

Of special interest is the proposal of Netzer and Miller, who developed an optimal tracing technique which tries to minimize the amount of necessary trace data, both for message passing systems See [NeMi 92b] and shared variable programs See [Netz 93]. Their idea is based on the fact, that only those events affecting the race conditions do have to be traced. By making such run-time decisions, only a fraction of the total number of events (as required with Instant Replay) have to be stored in the tracefiles.

Although this on-the-fly trace reduction approach of Netzer and Miller is optimal in the common case and offers a good performance in the worst case, it could be further improved for space and time efficiency using certain characteristics of the underlying system. Such improvements for time efficiency have been described in See [FaCh 95] and See [FaCh 96], while improvements for space efficiency can be found in See [LeSc 92] and See [LeSc 93]. Several combined efforts for shared variable programs have been proposed by Audenaert, Levrouw, and Ronsse in See [AuLe 95], See [Levr 94], See [RoLe 95], and See [RoLe 96]. Additionally, they show how to apply very simple compression algorithms to traces in order to further minimize tracefile size See [Rons 95]. In cooperation with Ronsse we developed a technique for message-passing parallel programs that produces even smaller traces and is less intrusive than the others described above (for details, please refer to See [RoKr 98]). In Section See Possible Optimizations, we will show that this approach can be further improved by exploiting certain characteristics of most existing message passing libraries. An approach that has been influenced by this work and is therefore comparable to ours is MPL*, which described by Chassin et al in See [Chas 99].

From the approaches that are not based on Instant Replay, some worth-mentioning are Deterministic Execution See [TaCa 91], Demand-Driven Replay See [MiTa 95] and On-the-Fly Replay See [Gers 94]. In Deterministic Execution, a sequence of synchronization constructs is generated based on an initial execution of the program. By inserting these synchronization constructs into the replayed execution, the irreproducibility effect can be eliminated See [CaTa 91]. The trace of the initial execution is also required for Demand-Driven Replay, which replays a program between breakpoints by allowing only those interprocess activities, that are needed to reach the next breakpoint See [MiTa 95]. The only technique that does not require a dedicated record phase is On-the-Fly Replay, because record and replay phase are executed simultaneously. The replay phase is steered by the record phase by exchanging ordering information between both executions See [Gers 94].

Several valid results may exist for one set of inputs.

• Critical errors may occur only sporadically.

These problems may occur in nondeterministic programs, because different results may be computed for one set of inputs. Furthermore, different execution paths of the program may still compute the same results. Thus, the observed results may not necessarily represent the only valid executions of the program See [DaFr 94]. For example, in programs modeling nondeterministic scenarios from reality, several valid executions may exist and may be of interest to the user. In addition, some errors may be hidden in executions that may seldom or never occur during testing. Yet, since environmental parameters may affect the program unpredictably, every possible execution of a program must theoretically be considered during testing.

Formally, this means that the testing approach of Section See The Testing Cycle has to be extended for nondeterministic parallel programs. Again, we apply the simple checking approach of Blum and Wasserman See [BlWa 96] (see Definition See Simple checking [BlWa 96]). After choosing an arbitrary mathematical function f ( x ) that describes the behavior of some program P ( x ), and a valid input x , we have to determine whether or not y = f ( x ) in order to confirm if the input/output pair represents a correct computation of f . The problem is, that there may be more than one correct output y for each set of inputs . Thus, for satisfying the test completion criterion with nondeterministic programs it is necessary to compute each output y from a set of possible outputs for each input of the set of valid inputs in X . As a consequence, some means of steering the choices at nondeterministic events have to be provided. The goal is to obtain alternate versions of particular test cases during replay, based on some previously recorded program execution.

Although this problem is well-known in the parallel debugging community, there are only few solutions that address this completeness problem. In fact, most of these solutions try to overcome this problem by eliminating or controlling the nondeterminism occurring due to communicating processes. A simple approach would be serialization of the code, which means that no process is allowed to proceed concurrently to any other existing process. If the processes are executed in a pre-defined sequential order, race conditions simply cannot occur.

One example of this approach is "controlled execution" See [TaCa 96], which also offers a method to perform automatic testing. Based on a technique for describing the desired communication behavior, the replay tool forces the program to execute the communication as specified. Therefore, the order of all communication events is predefined and races are not permitted. In addition, selected events of the communication description can be varied, allowing to perform restricted permutation testing. An extended approach to this technique is offered by Oberhuber See [Ober 98], who proposes to specify not only input data for testing, but also the sequences of interprocess communication See [Ober 95]. In this approach control patterns are applied for establishing the order between the communication events. Such control patterns are dynamic rules to define the order of process interaction. They can be grouped hierarchically to express more and more complex patterns, which should then sufficiently describe the expected communication structure of a parallel program. This eliminates nondeterminism and guarantees reproducibility, if the predefined behavior is enforced by the debugging tool during execution and re-execution See [Ober 95].

There are several problems to all these proposals. Firstly, the user is confronted with an additional means of specifying the program's communication behavior. It may be difficult to demand this from the average user, who already described the program's behavior by specifying the communication statements in the original source code. Not only does it require to learn a new description language, but also a correct relation between the program code and the communication specification. Secondly, the correctness and completeness of the communication specification must be guaranteed in order to mask all possible executions for all possible inputs. This may be possible in some cases, but is certainly limited in case of highly complex and large programs, which may exhibit totally unexpected behavior. Thirdly, these solutions do not exhaustively test the program's execution, but instead pretend to test the most feasible cases. Therefore, the user may be mislead and trust in a program, that is actually not completely tested and may exhibit incorrect behavior whenever executed without this controlling mechanisms.

In contrast to the solutions described so far, our proposal addresses the completeness problem more directly. The first description of our idea is presented by Grabner and Volkert in See [GrVo 93], who nicknamed this approach "event manipulation". An improved version of their basic idea together with a corresponding replay mechanism can be found in See [Kran 95a] and See [GrVo 96]. Our basic idea was also extended in See [Kran 97b], where we show that a combination of race condition detection with control and data flow analysis can provide vital information for selecting appropriate race condition candidates. Recently, the original manual approach has been automated as described in See [KrVo 98]. This latest instance of automatic event manipulation will be described in more detailed in Chapter See Automatization of Nondeterminism Analysis. Therefore, the following paragraph gives only a brief summary of our proposed approach.

The main idea of our approach can be formulated as follows: Firstly, an initial execution of the target program is observed during a record phase. The observed data is analyzed and encountered race conditions are identified. Based on these race conditions, the following question is explored: What would have happened, if the order of the communication events at some arbitrary race condition would be different from the observed order? The answer to this question for any selected race condition in the observed execution is derived with two steps:

Event manipulation

• Artificial replay

Event manipulation means, that the observed order of communication events is changed. In the original approach, this change is applied graphically in a display that represents the program's communication behavior. After the exchange has been performed, a replay of the program is initiated, that enforces the artificially generated new behavior. This re-execution has to perform two distinct tasks to solve the question stated above: Up to the point of the event manipulation, the program is replayed exactly as observed during the record phase. After the event manipulation has been performed, the program is executed without any constraints. This is necessary, because the future of the program after this exchange is unknown due to the nondeterminism and cannot be derived from the behavior stored during the record phase.

With this event manipulation and replay approach, we can easily investigate different program executions for one particular set of inputs. Furthermore, all possible permutations of the observed program execution can be derived, if all combinations of event orders at each of the racing receives are tested. For the original approach described in See [GrVo 93] and See [GrVo 96], this would mean that each possible event order has to be generated manually by the user. Since this could represent a major drawback for many parallel programs, we revised this manual approach to perform the event manipulation and artificial replay automatically See [KrVo 98]. In this case, an initial execution is analyzed by a testing tool, that identifies all the race conditions in the program and generates the complete set of follow-up executions automatically without user interaction. Then, the resulting executions and their corresponding outputs represent all possible executions of the target program for the selected input.

The few comparable approaches for solving the completeness problem are described with the Hindsight prototype debugger in See [Spie 93], with the Time Controlled Environment TCE in See [Kraw 00], and with the macrostep approach in See [Kacs 98]. Hindsight targets ordering errors occurring due to missing synchronization operations by exchanging the order in which synchronization operations are carried out See [Spie 93]. The TCE (together with the Race Detection Testing Strategies RDS) tries to modify a program run during subsequent execution by introducing artificial delays or changes to the process allocation scheme See [Kraw 00].

In contrast to these approaches, macrostep debugging as proposed by Kacsuk in See [Kacs 98] can be used to perform complete testing. The main idea is, that the user describes the minimal relevant test sequence for a given problem, and the tool automatically derives each possible execution for this test sequence. This is achieved by exhaustively traversing the execution tree of a program, where the debugger takes a different choice at each race condition during subsequent re-executions of the program See [Kacs 99]. The only limitation of macrostep debugging is, that it is based on the GRAPNEL visual programming language See [Kacs 97]. Although this language uses PVM for low-level communication routines, the visual objects applied in GRAPNEL are much more restrictive than what would be possible with the underlying message passing library. While this is certainly an advantage for the inexperienced user, it also reduces the number of possibilities at race conditions vigorously.

In practice, the number of possible combinations would probably prohibit exhaustive testing See [DaFr 94]. One important reason is, that these possible combinations and the corresponding replay phases may deliver some totally new executions with potentially new race conditions, which of course have to be treated by the testing program in the same way as the original execution. In certain cases it may even be imaginable, that the program delivers new executions endlessly, which prohibits to perform the complete tests of the program. An example is a program with a loop, that requires a specific ordering of events for loop termination.

Therefore, the debugging tool has to provide certain precautions in order to limit the testing cycle to the most probable executions (compare with Definition See Good Enough testing [Bach 98]: See Good Enough testing [Bach 98]). Some of our solutions to this problem are described in detail in Section See Ideas for Test Reduction. Another solution based on our basic event manipulation approach can be found in See [KiCh 97], which is intended to detect occasional bugs (see Section See Definition and Classification of Errors) that occur only sporadically due to racing messages. Their idea is to re-execute the program while imposing a strictly different message ordering than observed. By maximizing the number of reordered pairs of message deliveries, errors that would otherwise occur only sporadically should materialize.

Probe effect See [Gait 86]

The probe effect is an alteration in the frequency of run-time computational errors observed when delays are introduced into concurrent programs.

This means that the behavior of a program is influenced when something slows down the execution of one or more processes. Obviously, adding a debugging tool represents a certain amount of delay, and that delay may vigorously affect the debuggee's execution. The critical issue is the size of the observation functions which are added to the code during the instrumentation phase. This size determines the monitor overhead, which is on the one hand the time spent in the instrumented code, and on the other hand the amount of memory needed by the observation functions.

Therefore, a primary goal of any debugging tool must be to generate very little overhead. Yet, even the smallest overhead consumes some amount of memory and there will always be an execution delay of the target program, which modifies the time of occurrence of events. Thus, the data that is generated by the observer describes events that occurred later in time, compared to an execution where debugging is turned off. An additional problem to the displacement of observed events is introduced, if the target program reveals nondeterministic behavior. In that case, the order of events at race conditions may be affected, leading to a completely different execution that would have been observed without the debugging tool. In fact, any attempt to debug a program may change that behavior so much, that the collected data will not be adequate See [KrWi 98]. Furthermore, new errors may occur while others may be hidden in program branches not taken during the observed execution, which would otherwise have occurred if the program had been executed without the debugger. In more pathological cases the observed application may be prevented from exhibiting any sensible behavior at all.

These problems have been extensively addressed by Malony, Reed, and Wijshoff in See [Malo 91a], See [MaRe 91], and See [Malo 92]. They distinguish between direct intrusion and indirect intrusion, the latter being very difficult to estimate and correct. In their model, direct intrusion is corrected post-mortem by estimating the amount of tracing and subtracting this overhead from the measured event data. This approach works well for programming models with deterministic communication (e.g. fork-join in See [MaRe 91], and rendezvous in See [Mail 95]). However, it is insufficient for nondeterministic behavior of asynchronous communication as offered by the standard message passing interface MPI, because the latter would require post-mortem changes in the order of traced events. As a consequence, Maillet introduces conservative approximation as described in See [Mail 95], which applies only corrections that do not interfere with the traced event order. Another idea for nondeterministic programs was described by Leu and Schiper See [LeSc 92], and later by Teodorescu and Chassin de Kergommeaux See [TeCh 97]. Both ideas focus on tracing only the minimum amount of information required to allow re-execution of programs. Thus, this initial execution is assumed to be only slightly perturbed and is therefore considered as an approximation of a unperturbed execution See [FaCh 96]. Afterwards the replayed executions are used to apply performance tracing and generate additional timing information.

Other contributions in this domain have been described in See [Will 92], See [SaMa 93], See [Gann 94a], See [Gann 94b] and See [Jaki 95]. In contrast to all these correction algorithms, there also exists a group of monitor overhead prevention algorithms. One example is the "logical clock approach" of Cai and Turner, which uses a virtual time to reflect the real time execution of each process when running without monitoring See [CaTu 94]. During execution, the interprocess communication is controlled by this virtual time rather than the real time in order to avoid the probe effect See [TuCa 93]. A similar approach is described by Zhang et al (see See [LiZh 95] and See [Zhan 98]), who correct the monitor intrusion with artificial delays, so that the relative speed of all the processes remains the same. Similar ideas are proposed in See [Wu 96] and See [Wu 98], where different communication protocols are used to distinguish the monitoring activities from other computational tasks in order to allow automatic removal of monitor intrusion. In See [HoMi 96], Hollingsworth an Miller describe a data collection cost system, that provides users with feedback about the impact of the data collection on the running program. In addition, their system allows to define the level of perturbation that affects the program's execution, which is then controlled by the monitor.

The problems of all these previous approaches to correct the probe effect are, that either they do not treat the possibility of actual changes in event order, or they pretend that changes in event order did not occur in the first place. Yet, even the smallest overhead may lead to such program perturbations and different program behavior. Thus, a complete overhead removal strategy must deal with both types of program perturbation, changes in event timing and event ordering. In See [Kran 99b] and See [Scha 99], we describe a possible solution to this problem that includes necessary clock synchronization algorithms, calculation of corrected event occurrence timings, and automatic event manipulation and replay at places where changes in event ordering are detected.

One of the problems of our approach is the accuracy of the correction algorithms, which prohibits to identify the one and only execution that would occur without the debugging tool attached to the code. This problems may be attributed partially to the achievable accuracy of clock synchronization algorithms, partially to the measurements of communication and overhead. In our case, we implemented a simple solutions based on Lamport's condition that sends must happen before receives, as well as the more sophisticated synchronization method proposed by Maillet et al in See [MaTr 95] and See [Mail 96]. For the overhead measurements, we applied the SKaMPI benchmark developed by Reussner et al See [Reus 98], which provided detailed timings for the complete MPI standard functionality See [Kran 99c].

Another problem is that in many cases there exists not only one possible execution due to the nondeterminism, but several executions with almost equal probability. In the worst case, every possible execution path may occur in reality, which connects the probe effect to the irreproducibility problem and the difficulties of exhaustive testing described above. As a consequence, our correction algorithm derives the set of possible executions with the highest probability, where each of them may most likely occur if debugging is turned off. This issue will be discussed in combination with automatic nondeterminism analysis in Section See Ideas for Test Reduction.

A (graphical) user interface with features for

• Displaying source code
• Inspecting (and manipulating) the processes stack, the hardware registers, and the applications variables.
• Handling breakpoints
• Controlling the execution of the target program
• A debugging kernel with functionality for
• Managing the program's symbol table
• Evaluating expressions
• Controlling and executing processes
• An operating system for accessing
• Operating system functions
• The debuggee

A similar architecture is proposed by Bemmerl, who formally defines the key features of an arbitrary debugging tool as follows:

PD = arbitrary connections of control flow-data flow, and concurrency events with operators AND, OR, and a suitable ordering relation, as well as

• DO = breakpoints
trace state-inspection state-manipulation

Heterogeneity and portability: supporting different programming models and hardware architectures (possibly in the same environment)

• Usability: handling the characteristics of parallel programs like
• Increased complexity
• Amount of debugging data
• Additional anomalous effects

One of the most important criteria for any tool developer is a definition of target systems, which in our case are high performance supercomputers. Since there exist different architectures and possibilities of programming them (as described in Section See Supercomputing and Section See Parallel Programming), a wide variety of strategies and tools with different functionality have already been proposed, leading to some nice tool prototypes or even commercial products. Furthermore, every hardware vendor provides its own native support for debugging on their respective architectures, like for example nCUBE with the ndb Debugger, CONVEX with its CXdb, or Intel with the Paragon Debugger ipd on its iPSC/860 architectures.

This diversity is an issue of some on-going projects in this domain, which address the problems of portability and heterogeneity in parallel debuggers and performance analysis tools See [Panc 95]. Corresponding solutions are usually based on the fact, that all vendor-specific tools provide similar functionality under a different user interface. Consequently, it seems useful to develop portable debuggers which could be used on different hardware platforms, thus dismissing the need to learn several debugging tools when switching between different platforms.

Some examples in this context are P2D2 See [Hood 96], Panorama See [MaBe 93], PDBG See [Cunh 98b], PDT See [Clem 95b], and DCBD See [Wang 99], as well as the best-known commercial debugging tool Totalview See [Dolp 98]. These tools offer debugging support on several multiprocessor architectures and networks of workstations. An important characteristic of almost all these systems is, that every approach applies several instances of an existing sequential debugger in order to perform the debugging task on the participating processes. Thus, their idea is to offer a graphical interface for managing the features of these "base debuggers" See [MaBe 93], which are in most cases variants of the GNU debugger gdb See [Stal 93]. In these cases, the parallel debuggers adopt a client-server architecture to provide a uniform interface for different platforms, communication libraries and programming models See [ChHo 94].

Although this portability may be useful in many cases, it introduces some obstacles especially on large scale computing systems like massively parallel machines or heterogeneous clusters of supercomputers, the so-called metacomputers. In fact, one of the biggest problems experienced during debugging of supercomputer applications is connected to the amount of data that has to be analyzed See [Frum 98]. Firstly, these programs tend to be long-lasting, from some hours to several days or even more. As a consequence, many state changes occur that have to be observed, transferred, stored, and processed by the debugging tool. In the worst case, debugging a supercomputer may require another supercomputer to perform the analysis task. Secondly, the execution time and the large number of participating processes leads to enormous interprocess relations, which cannot be comprehended by the user. Thirdly, a great amount of debugging activities have to be performed equally for different processes and repeated iterations of the target application.

Thus, the basic requirements heterogeneity and usability have to be supported by methods for managing parallel programs in order to increase the lucidity and applicability. For that reason, we identified the following optional features:

Abstraction

• Automatization

Abstraction means, that the amount of debugging data presented to the user is reduced to a suitable minimum. Besides the regular meaning of forming some kind of mental generalization, this also includes related techniques like transformation, reduction, extraction, isolation, and filtering. Error detection can only be applied successfully, if the user can comprehend the observed activities See [Kime 95]. This means, that a debugging tool should offer capabilities allowing the programmer to focus the scope of attention to limited regions within the program See [BeSt 94]. Furthermore, it may be equally important to permit different levels of abstraction in order to select the most appropriate level for the conducted debugging operations, so that only the data relevant to the user is presented See [From 95c]. Sometimes it may be useful to see the execution of the program in a coarse graphical overview, while at other times it may be beneficial to display the program on the level of machine instructions. Thus, a most important feature is to provide connections for dynamically switching between different levels of abstraction. It's the nature of debugging, that one doesn't know just what to look for in advance, so it is certainly important to provide access to the vast amount of debugging data while at the same time offering functionality for managing these data.

Besides abstraction, a lot of debugging efforts can be supported by automatization if repeated debugging activities are performed without user interaction. Some examples are the automatic detection of program failures, abstraction of detectable, for the user probably invisible properties, and iterative testing for the completeness problem. For example, after reading the core file, users can be directed to the place in the code where the program exited. Or, race conditions and corresponding memory access patterns or racing messages can be evaluated automatically. Some sophisticated methods consider statistical testing See [Walt 95] and automatic checking of dynamic properties using regular grammars or finite automata See [Baba 95].

Of course, due to the nature of debugging and its strong relation to the user's knowledge, a complete automatization of the debugging process is certainly impossible. For instance, the correction of a detected anomaly must always be carried out by the user. Therefore, the goal of powerful debugging tools must be to perform as many debugging activities automatically or semiautomatically with the main directions given by the user.

Based on these requirements, we may now try to classify existing work and identify the drawbacks of previous approaches. Only a strategy or tool supporting these characteristics may then be applicable to full-scale applications, and may allow to perform debugging activities impossible with existing solutions. In addition, it may also improve the error detection task on smaller-scale application sizes, especially if it can be combined with other tools in this area.

the OMIS project,

• the Ptools consortium,
• and the HPD forum.

The first attempt, which will also be mentioned in Section See Monitoring Tools, is the Online Monitoring Interface Specification OMIS12 See [LuWi 97]. This effort was initiated in 1996 by Ludwig and Wismüller at the LRR (Lehrstuhl für Rechnertechnik und Rechnerorganisaton) of the Technical University Munich together with Sunderam from Emory University, Atlanta, one of the creators of the Parallel Virtual Machine PVM. Since then, the authors of OMIS were able to dissipate it to a broad community, and several compliant tools have already matured at various research institutions around the world. Proposals for extensions to the standard, are coordinated by the OMIS group, while software products being developed in the framework of this project will be released under the GNU public license conditions to deliver a maximum profit for the user community.

In contrast to the OMIS standard, the Parallel Tools Consortium Ptools13, established in 1993, seeks to increase the cooperation between representatives from federal, industrial, and academic sectors in order to address the factors that inhibit tool usage and tool usability on parallel computers See [Panc 96b]. Their self-imposed mission is to take a leadership role in defining, developing, and promoting parallel tools that meet the specific requirements of users who develop scalable applications on a variety of platforms. This is attempted with two activities: On the one hand, Ptools organizes meetings for members of the above mentioned organizations in order to provide a forum, where tool developers interact directly with potential users in order to help formalizing and prioritizing user requirements for tool support. On the other hand, Ptools promotes tool portability and consistency by sponsoring projects to develop general tools that can execute reliably across a broad range of parallel and clustered computing systems. This is supported by the Ptools infrastructure, that includes channels for acquiring input from the high-performance computing community, working groups involving tool users, researchers and developers, and mechanisms for formalizing and distributing tool components for adoption by the industry. Although Ptools is operated from the United States, its membership is open to all organizations and persons interested in parallel tools without any membership fees.

One of the activities sponsored by the Ptools consortium is the High Performance Debugging Forum HPDF14, which was officially established in 1997. Its goal is the definition of a useful and appropriate set of standards relevant to debugging tools for high-performance computing See [Brow 97]. This base level standard has to meet the sometimes conflicting constraints of being useful to users, realistically implementable by developers, and architecturally independent across multiple platforms. In order to meet the criterion for timeliness, the HPD forum restricted itself to two years, where the first year should be used to develop a standard that could then be implemented during the second year. And in fact, Version 1 of the HPD standard was released in 1998. However, while the standard was developing fast and is in some parts still being discussed, actual implementations of its functionality are still not available by now. However, there are notably some organizations working on it, and it will be interesting to see, whether their efforts can lead to substantial benefits for the group of debugging users.

Another interesting approach with some nice potential, although actually not termed as a standard, is collaborative debugging See [DoMu 97]. Its idea is to create distributed debugging communities around the globe based on the World Wide Web technology. These groups of programmers will then describe and fix bugs in collaboration, with probably high potential benefits for the quality of the resulting software. A first solution is the Internet Software Visualization Laboratory (ISVL), which uses a client/server architecture to deliver visualizations of program behavior on any Java-enable Web browser See [DoMu 97]. Another approach is offered by Kansas, a multiuser virtual world, which allows people to experiment with building programs and collaboratively hunting bugs See [Smit 97].

Monitor oriented layer: the monitor

• Analysis oriented layers:
• Data access layer
• Selection layer
• Tool support layer
• Tool layer
• Application oriented layers: application support

The bottom layer of this model represents the connection between the analysis tools and the target system. It denotes the observation component in See [Hond 95], and is responsible for the data collection. Its main tasks are to record the dynamic course of state-changes that constitute the execution of the actually observed program. Obviously, there is a strong connection between the observer and the observed program, as well as the underlying system.

The next four layers above the monitor oriented layer are called the analysis oriented layers. The data access layer provides access functionality for obtaining the observation data from the monitor layer. In order to reduce this exhaustive data and relate it to corresponding analysis tools, the selection layer provides functionality for filtering and compounding the data. In the tool support layer, this data can be accessed by generic functions without any semantics and utility functions like statistics or other operations. The actual semantic oriented analysis tasks are provided by the tool layer, which offers a wide variety of activities: trace validation, statistical evaluation, visualization of execution behavior, animation, as well as processing the data for other tools on the next layer, like modelling tools, debugging and performance analysis tools, and tools for load balancing. This top-most layer of the hierarchy, the application oriented layer, constitutes the interface to the user, and is therefore the connecting link between the analysis tool and its client.

In See [Hond 95], the four analysis oriented layers and the application oriented layers are combined in the analysis or visualization component. Its most important property is the way of displaying the program to the user. In general, we may distinguish textual representation (e.g. source code) or graphical representation (with many different ways to visualize the monitored data). As mentioned before, the advantages of the latter can only be acquired if a combination of both approaches is included through some kind of source code reference.

Tools can also be divided by whether analysis and visualization takes place simultaneously with the program execution or after it, which establishes the following two groups:

On-line analysis tools

• Post-mortem analysis tools

In the on-line case, the data of the monitor is transported to the analysis component, while the target program is still executing. In the post-mortem case, the program is executed and analysis data is stored in tracefiles, which are investigated only after the program's execution terminated. Please note, while post-mortem allows to remove the analysis components (the five upper layers in Mohr's approach See [Mohr 92]) from the executing program, it still requires to include at least the monitoring component, because this component can only retrieve state information when the program is actually running.

Both approaches have different advantages, with on-line being the primary choice for standard error detection tools. The reason is, that on-line analysis tools allow a much more flexible approach to program state inspection than post-mortem, because the user can determine what to inspect at each point during the execution. On the other hand, the post-mortem approach allows some analysis techniques, that can not be performed with on-line tools, primarily because on-line tools can only rely on the past and present of a program's execution, while post-mortem approach may analyze the program from its beginning to its termination. An example, where post-mortem approaches are superior to on-line approaches is race condition detection, because on-line methods may not be able to identify the complete set of race conditions at any point during the execution.

Hardware monitoring

• Hybrid monitoring
• Software monitoring

Hardware monitors represent an extension of the target system on the hardware architecture level. Thus, their usage is generally restricted to vendors or hardware experts, and requires a lot of expertise and knowledge during installation and operation. The biggest problem of these monitors is, that even the most advanced tools are restricted to a few observation points and provide only low-level data as well as a low-level interface. In addition, such monitors offer little portability because they address only one particular hardware architecture. Yet, their advantage is the very little overhead that is produced during program observations, which denotes a lot of benefits in terms of the probe effect.

One of the few widely-known hardware monitors is ZM4 (german: "Zählmonitor 4") See [Hofm 87], the fourth generation of hardware monitors developed at the University Erlangen-Nürnberg See [Klar 95]. ZM4 tries to overcome the portability problem by offering a variety of interfaces for several target systems, from Transputers via the networks of personal computers to the MEMSY system (Modular Expandable Multiprocessor System), which is characterized by its extensive support for measurements See [Hofm 93]. Additionally, the interpretation of ZM4's results is supported by the post-mortem software environment SIMPLE (Source related Integrated Multiprocessor and -computer Performance evaluation, visualization and modeLing Environment) See [Daup 92], which tries to relate the observed data with the original source code in order to compensate for the low-level data obtained by the monitor.

Another kind of hardware monitors are so-called hardware counters, which are directly included in the microprocessor's hardware. These counters can be incremented whenever predefined events occur, and thus may be used to obtain heuristics about process activities. At present, there are two efforts worth mentioning in this domain. One is PCL (Performance Counter Library) See [BeZi 98] developed at the Research Center Jülich, the other is PerfAPI or PAPI (Performance Application Programming Interface) See [Mucc 99] developed in the frame of the Parallel Tools Consortium (see Section See Collaborative and Standardization Efforts to Debugging). An example of using these hardware performance counters is described in See [Rabe 99], where the PCL library was integrated on the SGI Cray T3E architecture to observe the frequency of calls to routines of the standard Message Passing Interface library.

The second monitoring technique, hybrid monitoring, is a mixture between software monitoring and hardware monitoring. Mohr characterized hybrid monitoring as follows See [Mohr 93]: the recognition of events is done in software, but the recording and time stamping is done in hardware. It is still rather low-level in order to generate as little overhead as possible, while at the same time supports software probes and other functional characteristics from software monitors. Its main advantages compared to pure hardware monitors are, that it is much more flexible and portable, while at the same time providing an improved interface to the user.

An example hybrid monitor has been developed by Malony and Reed for the iPSC/2-Hypercube system See [MaRe 90]. Their tool operates on a 5-bit parallel interface of the hardware architecture, which connects each of the processors to one common connector. With this approach, the 32 nodes hypercube is divided into two 16 nodes hypercubes, where one of them performs the computational task, while the other performs the observation See [Klar 95].

A similar approach has been implemented in our EMU (Event Monitoring Utility) See [Kran 96a], which offers a monitoring cube strategy for hypercube multiprocessor architectures (such as the nCUBE 2 multiprocessor and the SGI Origin 2000). Again, the available hypercube is divided into two smaller hypercubes with equal dimension, where one performs the computation while it is being observed by the other cubes. In principle, the functionality of the monitor is divided into two parts, with a very small part for accessing the process state on the computational nodes and a remaining larger part with the functionality for processing and storing these data on the monitoring nodes. In See [Kran 96a] we describe the advantages of this hybrid monitoring approach compared to software monitoring approaches in terms of monitor overhead. Other hybrid monitoring approaches are described in See [Gorl 91], See [HaWy 90], See [Lump 90], See [Malo 89], and See [Mari 90].

The last group of monitoring tools is probably the most widely used, the software monitoring approaches. As a consequence, there exists a wide range of different techniques for different hardware architectures, e.g. See [Gris 91], See [Joyc 87], See [LeRo 85], See [LePa 85], See [Mail 95], See [Mill 86], and See [Snod 88]. Most of these tools are solely intended for one specific parallel system, prohibiting its usage on other operating systems and hardware architectures. Instead, it seems that every tool developer restarts with another implementation of a monitoring component, because each system has its own design goals and philosophy for solving one particular class of problems. Yet, this is a minor discrepancy which has been noted before, because the basic characteristics of all these approaches are comparable.

In See [Mohr 93] Mohr tries to emphasize this fact and describes a possible way for a target-independent way of monitoring and analyzing parallel systems. The latest results of these ideas have been implemented in EARL, the Event Analysis and Recognition Language, which allows to construct new trace analysis tools by writing scripts in the EARL language See [WoMo 98]. Similar goals are pursued by several standardization approaches for the monitoring layer of debugging and performance analysis tools. One of the earlier representatives in this category is PICL, the Portable Instrumented Communication Library developed at the Oak Ridge National Laboratory See [Geis 90]. One of the central ideas of PICL was to offer the user a communication library that is available on different parallel computer architectures and offers the same kind of communication operations. In addition, PICL allows to generate traces for post-mortem analysis, which report the calls to the PICL functions. Consequently, an analysis tool like Paragraph See [HeEt 91a] can be used to evaluate the contents of the PICL traces and derive valuable information about the program's execution.

A comparable solution was developed by Reed at al within the Pablo performance tuning environment See [Reed 93], which consists of several components for instrumenting, tracing, and analyzing parallel MPI programs. The trace file format of this toolset is the Pablo Self-Defining Data Format (SDDF) See [Aydt 92], which is a data description language for specifying both data record structures and data record instances. In a certain sense it is a data meta-format, because it can describe general data records as opposed to a predefined set of records. Originally developed to link the Pablo instrumentation software to the other analysis components of pablo, like Autopilot See [Ribl 98], Virtue See [Reed 95], and svPablo See [DeRo 98], it has proven to be even more general and extensible than first envisioned by its authors. By providing features like compactness, portability, generality, and extensibility, it is nowadays used by several other monitoring and analysis tools.

For the sake of completeness, we also require one remark concerning these three tracefile descriptions, EARL, PICL, and SDDF. Each of this formats is placed on ASCII representations, which offers a high degree of flexibility and readability. In fact, in most cases, users may even be able to understand the contents of the traces without any analysis tool. Yet, this feature includes also the drawback, that tracefile size may grow easily leading to enormous requirements of trace storage. For that reason, most comparable approaches try to establish binary representations, which allow to store a program's behavioral data more efficiently. In addition, there are approaches that try to apply compression mechanisms to traces as described in See [Rons 95]. In See [Frum 98] an interesting idea is described, which compresses the trace data based on information-theoretic techniques. Comparable statistical methods are followed in See [Reed 97] and See [Yan 98].

The problem of tracefile size is also less critical in relation to on-line monitoring tools, e.g. the Online Monitoring Interface Standard OMIS See [Ludw 96] by Ludwig et al, which has already been described in Section See Collaborative and Standardization Efforts to Debugging and is currently available as Version 2.0 See [LuWi 97]. With this interface description, various types of run-time tools for parallel and distributed systems and the systems themselves can be interconnected. By using a monitoring system with a standardized interface, arbitrary target systems could be supported with the same powerful set of tools. Furthermore, tool developers can easily attach new tools to already existing implementations of OMIS compliant monitoring (OCM) systems on different target architectures, which in term can concurrently serve several compliant tools, thus offering a means for tool interoperability See [Wism 98a].

Another interesting idea related to monitoring tools is the integration of record&replay mechanisms. Certainly, the record phase is performed by a monitoring system which retrieves all the necessary information to guarantee an equivalent execution during the follow-up replay phases. Of course, this monitor requires only the most basic features and needs not generate complete process state information for the analysis tasks. Instead, this process state information may be generated during the replay phases, when the amount of monitor overhead is harmless. Therefore, it seems useful to include the replay functionality directly in the monitoring code, so that for each record function a corresponding replay function is provided.

In order to evaluate the benefits of this approach, we have reworked our original approach to monitoring - EMU (Event Monitoring Utility) - and its corresponding replay tool PARASIT (PARAllel SImulation Tool) into the NOndeterministic Program Evaluator NOPE. The advantages of this approach are manifold: Firstly, it improves the usability, because only one interface is provided and both the record and the replay component are steered with similar commands. Secondly, the code is more compact and additional instrumentation functions can be added for the record and replay phases simultaneously. Thirdly, and probably most important, it is very easy to switch between the monitor function and the replay function, which is especially important when event manipulation has been carried out.

In addition, we have studied the documentation of OMIS, and we believe that a similar approach could be applied by simply using the intrinsic steering possibilities of such a monitoring tool. The resulting OMIS compliant record&replay tool could profit from all the advantages of every OMIS compliant tool, while at the same time provides the same features as our own record&replay tool NOPE.

Visual programming See [Pric 98]

Visual programming is the use of "visual" techniques to specify a program.

Software visualization See [Baec 97]

Software visualization is the systematic and imaginative use of the technology of interactive computer graphics and the disciplines of graphic design, typography, color, cinematography, animation, and sound design to enhance the comprehension of algorithms and computer programs.

The main difference between these two areas is their goal. While visual programming seeks to make program specification easier by using a graphical (or "visual") notation, software visualization seeks to improve the understanding of programs and algorithms using various techniques. Yet, there are also some similarities which arise from the visual techniques being applied. For example, many visual programming tools can be cited that include both, a mechanism for specifying the program and a mechanism for investigating the actual behavior of the program (e.g. HeNCE See [Begu 93b]). Often, different kinds of representations are used for these two tasks, but there exists some notable exceptions which offer the same visual representation during program construction as well as during error detection and tuning (e.g. Visper See [Stan 98]).

The similarity between both fields, software visualization and visual programming, is also recognizable from their main goal. In both cases visualization is used in the sense of forming a mental image of something that can be aided by graphical, auditory, and other sensory modalities. These means are utilized to aid the reasoning and understanding of programs and their executions, respectively See [Zhan 99]. This is underlined by Miller, who believes that visualization should guide, not rationalize See [Mill 93]. In this context, to guide means that the visualization supports the user in discovering things, that were unknown before. In contrast, to rationalize means that things are presented, that are already well-known.

Since we are mainly interested in software visualization, we will take a closer look at the classification of Price, Baecker, and Small See [Pric 98]. They distinguish the following different types of techniques, which are derived from the distinction between programs and algorithms, static and dynamic representation, and code and data values See [Pric 98]:

Program visualization

• Static code visualization
• Static data visualization
• Data animation
• Code animation
• Algorithm visualization
• Static algorithm visualization
• Algorithm animation

The main distinction is between programs and algorithms, where program visualization is used to display actual program code or data structures, while algorithm visualization operates on higher-level descriptions of software. Both kinds of visualization support either representations of code segments or data values, and are performed either statically, where the display contains a snapshot of the data, or dynamically, where the display is changed over a period of time and portrays data processing and the occurrence of state changes.