Engineering topics

Reed, Daniel A.

Publications and source records attributed to Reed, Daniel A..

18 records

NASA NTRS1996

Optimizing Input/Output Using Adaptive File System Policies

Parallel input/output characterization studies and experiments with flexible resource management algorithms indicate that adaptivity is crucial to file system performance. In this paper we propose an automatic technique for selecting and refining file system policies based on application access patterns and execution environment. An automatic classification framework allows the file system to select appropriate caching and pre-fetching policies, while performance sensors provide feedback used to tune policy parameters for specific system environments. To illustrate the potential performance improvements possible using adaptive file system policies, we present results from experiments involving classification-based and performance-based steering.

Madhyastha, Tara M.↗

NASA NTRS1992

Dynamic object management for distributed data structures

In distributed-memory multiprocessors, remote memory accesses incur larger delays than local accesses. Hence, insightful allocation and access of distributed data can yield substantial performance gains. The authors argue for the use of dynamic data management policies encapsulated within individual distributed data structures. Distributed data structures offer performance, flexibility, abstraction, and system independence. This approach is supported by data from a trace-driven simulation study of parallel scientific benchmarks. Experimental data on memory locality, message count, message volume, and communication delay suggest that data-structure-specific data management is superior to a single, system-imposed policy.

Totty, Brian K.↗

NASA NTRS1991

Scalable Performance Environments for Parallel Systems

As parallel systems expand in size and complexity, the absence of performance tools for these parallel systems exacerbates the already difficult problems of application program and system software performance tuning. Moreover, given the pace of technological change, we can no longer afford to develop ad hoc, one-of-a-kind performance instrumentation software; we need scalable, portable performance analysis tools. We describe an environment prototype based on the lessons learned from two previous generations of performance data analysis software. Our environment prototype contains a set of performance data transformation modules that can be interconnected in user-specified ways. It is the responsibility of the environment infrastructure to hide details of module interconnection and data sharing. The environment is written in C++ with the graphical displays based on X windows and the Motif toolkit. It allows users to interconnect and configure modules graphically to form an acyclic, directed data analysis graph. Performance trace data are represented in a self-documenting stream format that includes internal definitions of data types, sizes, and names. The environment prototype supports the use of head-mounted displays and sonic data presentation in addition to the traditional use of visual techniques.

Reed, Daniel A.↗

NASA NTRS1990

Ray tracing on distributed memory parallel systems

Among the many techniques in computer graphics, ray tracing is prized because it can render realistic images, albeit at great computational expense. In this note, the performance of several approaches to ray tracing on a distributed memory parallel system is evaluated. A set of performance instrumentation tools and their associated visualization software are used to identify the underlying causes of performance differences.

Jensen, David W.↗

NASA NTRS1990

Empirical comparison of heuristic load distribution in point-to-point multicomputer networks

The study compared several load placement algorithms using instrumented programs and synthetic program models. Salient characteristics of these program traces (total computation time, total number of messages sent, and average message time) span two orders of magnitude. Load distribution algorithms determine the initial placement for processes, a precursor to the more general problem of load redistribution. It is found that desirable workload distribution strategies will place new processes globally, rather than locally, to spread processes rapidly, but that local information should be used to refine global placement.

Grunwald, Dirk C.↗

NASA NTRS1990

Integrating performance data collection, analysis, and visualization

An integrated data collection, analysis, and data visualization environment is described for a specific parallel system - the Intel iPSC/2 hypercube. The data collection components of the environment encompass software event tracing at the operating system with a program level and a hardware-based performance monitoring system used to capture software events. A visualization system based on the X-window environment permits dynamic display and reduction of performance data. A performance data collection, analysis, and visualization environment makes it possible to access the effects of architectural and system software variations.

Malony, Allen D.↗

NASA NTRS1989

Linear optimization - A case study in performance analysis

The paper deals with the performance of two parallel variants of the simplex algorithm on a message-passing system. First, the simplex algorithm is reviewed, two possible parallelizations of the algorithm are discussed, and results of benchmark speedups of the alternatives are presented. Between column and row partitionings, the row partitioning method is found to be generally superior, while the column partitioning method is more efficient when the number of rows is small, and the number of columns is much greater that the number of rows. Various performance analysis tools are then applied to examine the reasons for relative performance differences, and communication idle time due to global minimization and load imbalances is noted as the main factor in execution slowdown.

Stunkel, Craig B.↗

NASA NTRS1989

Experiences with hypercube operating system instrumentation

The difficulties in conceptualizing the interactions among a large number of processors make it difficult both to identify the sources of inefficiencies and to determine how a parallel program could be made more efficient. This paper describes an instrumentation system that can trace the execution of distributed memory parallel programs by recording the occurrence of parallel program events. The resulting event traces can be used to compile summary statistics that provide a global view of program performance. In addition, visualization tools permit the graphic display of event traces. Visual presentation of performance data is particularly useful, indeed, necessary for large-scale parallel computers; the enormous volume of performance data mandates visual display.

Reed, Daniel A.↗

NASA NTRS1988

Visualizing Parallel Computer System Performance

Parallel computer systems are among the most complex of man's creations, making satisfactory performance characterization difficult. Despite this complexity, there are strong, indeed, almost irresistible, incentives to quantify parallel system performance using a single metric. The fallacy lies in succumbing to such temptations. A complete performance characterization requires not only an analysis of the system's constituent levels, it also requires both static and dynamic characterizations. Static or average behavior analysis may mask transients that dramatically alter system performance. Although the human visual system is remarkedly adept at interpreting and identifying anomalies in false color data, the importance of dynamic, visual scientific data presentation has only recently been recognized Large, complex parallel system pose equally vexing performance interpretation problems. Data from hardware and software performance monitors must be presented in ways that emphasize important events while eluding irrelevant details. Design approaches and tools for performance visualization are the subject of this paper.

Malony, Allen D.↗

NASA NTRS1988

Parallel discrete event simulation using shared memory

With traditional event-list techniques, evaluating a detailed discrete-event simulation-model can often require hours or even days of computation time. By eliminating the event list and maintaining only sufficient synchronization to ensure causality, parallel simulation can potentially provide speedups that are linear in the numbers of processors. A set of shared-memory experiments, using the Chandy-Misra distributed-simulation algorithm, to simulate networks of queues is presented. Parameters of the study include queueing network topology and routing probabilities, number of processors, and assignment of network nodes to processors. These experiments show that Chandy-Misra distributed simulation is a questionable alternative to sequential-simulation of most queueing network models.

Reed, Daniel A.↗

NASA NTRS1987

Context Switching with Multiple Register Windows: A RISC Performance Study

Although previous studies have shown that a large file of overlapping register windows can greatly reduce procedure call/return overhead, the effects of register windows in a multiprogramming environment are poorly understood. This paper investigates the performance of multiprogrammed, reduced instruction set computers (RISCs) as a function of window management strategy. Using an analytic model that reflects context switch and procedure call overheads, we analyze the performance of simple, linearly self-recursive programs. For more complex programs, we present the results of a simulation study. These studies show that a simple strategy that saves all windows prior to a context switch, but restores only a single window following a context switch, performs near optimally.

Konsek, Marion B.↗

NASA NTRS1987

Stencils and problem partitionings - Their influence on the performance of multiple processor systems

Given a discretization stencil, partitioning the problem domain is an important first step for the efficient solution of partial differential equations on multiple processor systems. Partitions are derived that minimize interprocessor communication when the number of processors is known a priori and each domain partition is assigned to a different processor. This partitioning technique uses the stencil structure to select appropriate partition shapes. For square problem domains, it is shown that non-standard partitions (e.g., hexagons) are frequently preferable to the standard square partitions for a variety of commonly used stencils. This investigation is concluded with a formalization of the relationship between partition shape, stencil structure, and architecture, allowing selection of optimal partitions for a variety of parallel systems.

Reed, Daniel A.↗

NASA NTRS1987

The impact of domain partitioning on the performance of a shared memory multiprocessor

The impact of the choice of domain partition/stencil pairs in solving elliptic partial differential equations on a multiprocessor system with both global shared memory and local memory is considered. A parallel execution time model is given for square and hexagonal partitions using both five-point and nine-point star discretizations. Results from the model for a particular multiprocessor system show that keeping copies of partition boundaries in local memory significantly improves performance.

Patrick, Merrell L.↗

NASA NTRS1987

The performance of multicomputer interconnection networks

The interdependency of nodes and multicomputer interconnection networks is examined using simple calculations based on the asymptotic properties of queueing networks. Methods are described for choosing interconnection networks that fit individual classes of applications. It is also shown how analytic models can be extended to benchmark existing interconnection networks.

Reed, Daniel A.↗

NASA NTRS1987

MPF: A portable message passing facility for shared memory multiprocessors

The design, implementation, and performance evaluation of a message passing facility (MPF) for shared memory multiprocessors are presented. The MPF is based on a message passing model conceptually similar to conversations. Participants (parallel processors) can enter or leave a conversation at any time. The message passing primitives for this model are implemented as a portable library of C function calls. The MPF is currently operational on a Sequent Balance 21000, and several parallel applications were developed and tested. Several simple benchmark programs are presented to establish interprocess communication performance for common patterns of interprocess communication. Finally, performance figures are presented for two parallel applications, linear systems solution, and iterative solution of partial differential equations.

Malony, Allen D.↗

NASA NTRS1987

Parallel discrete event simulation: A shared memory approach

With traditional event list techniques, evaluating a detailed discrete event simulation model can often require hours or even days of computation time. Parallel simulation mimics the interacting servers and queues of a real system by assigning each simulated entity to a processor. By eliminating the event list and maintaining only sufficient synchronization to insure causality, parallel simulation can potentially provide speedups that are linear in the number of processors. A set of shared memory experiments is presented using the Chandy-Misra distributed simulation algorithm to simulate networks of queues. Parameters include queueing network topology and routing probabilities, number of processors, and assignment of network nodes to processors. These experiments show that Chandy-Misra distributed simulation is a questionable alternative to sequential simulation of most queueing network models.

Reed, Daniel A.↗

NASA NTRS1986

Benchmarking hypercube hardware and software

It was long a truism in computer systems design that balanced systems achieve the best performance. Message passing parallel processors are no different. To quantify the balance of a hypercube design, an experimental methodology was developed and the associated suite of benchmarks was applied to several existing hypercubes. The benchmark suite includes tests of both processor speed in the absence of internode communication and message transmission speed as a function of communication patterns.

Grunwald, Dirk C.↗

NASA NTRS1985

Analysis of adaptive algorithms for an integrated communication network

Techniques were examined that trade communication bandwidth for decreased transmission delays. When the network is lightly used, these schemes attempt to use additional network resources to decrease communication delays. As the network utilization rises, the schemes degrade gracefully, still providing service but with minimal use of the network. Because the schemes use a combination of circuit and packet switching, they should respond to variations in the types and amounts of network traffic. Also, a combination of circuit and packet switching to support the widely varying traffic demands imposed on an integrated network was investigated. The packet switched component is best suited to bursty traffic where some delays in delivery are acceptable. The circuit switched component is reserved for traffic that must meet real time constraints. Selected packet routing algorithms that might be used in an integrated network were simulated. An integrated traffic places widely varying workload demands on a network. Adaptive algorithms were identified, ones that respond to both the transient and evolutionary changes that arise in integrated networks. A new algorithm was developed, hybrid weighted routing, that adapts to workload changes.

Reed, Daniel A.↗