Stunkel, Craig B. | Search NASA

NASA NTRS1992

Address tracing of parallel systems via TRAPEDS

Trace-driven simulation is an important aid in performance analysis of computer systems. Capturing address traces to use in these simulations, however, is a difficult problem for parallel processor architectures. A technique termed TRAPEDS modifies executable code (at the assembly language level) to dynamically collect the address trace from executing code. TRAPEDS has recently been implemented on both a hypercube multicomputer and a shared-memory multiprocessor. Particular attention is focused on strategies for efficiently and accurately collecting traces from both classes of parallel machines. The iPSC/2 hypercube multicomputer implementation traces both user and system code, and performs simulation on-the-fly to avoid large storage costs. Strategies are detailed for mitigating address trace distortion when collecting operating system traces. The Encore Multimax multiprocessor implementation uses a timer-based approach to reflect the interleaving of the processor traces and stores the traces to disc. Time and space overhead results are presented for both TRAPEDS implementations. Experimental cache simulation results derived from iPSC/2 address traces are presented to illustrate the importance of tracing operating system references.

Stunkel, Craig B.↗

NASA NTRS1991

Address tracing for parallel machines

Recently implemented parallel system address-tracing methods based on several metrics are surveyed. The issues specific to collection of traces for both shared and distributed memory parallel computers are highlighted. Five general categories of address-trace collection methods are examined: hardware-captured, interrupt-based, simulation-based, altered microcode-based, and instrumented program-based traces. The problems unique to shared memory and distributed memory multiprocessors are examined separately.

Stunkel, Craig B.↗

NASA NTRS1991

Collecting address traces from parallel computers

Trace driven simulation is a well-established method of performance analysis for single processor computer systems. However, efficient and accurate memory address tracing for parallel computer systems is not well understood. In this paper we present a critical survey of recently implemented approaches to address tracing and highlight the issues specific to collection of traces for both shared and distributed memory parallel computers. These issues include potential distortion of the relative ordering of events by the address tracing activity, realistic interleaving of addresses generated by multiple processors, and I/O and storage problems associated with collecting traces for large parallel systems. The strengths and weaknesses of the parallel tracing approaches are described.

Stunkel, Craig B.↗

NASA NTRS1989

TRAPEDS - Producing traces for multicomputers via execution driven simulation

Trace-driven simulation is an important aid in performance analysis of computer systems. Capturing address traces for these simulations is a difficult problem for single processors and particularly for multicomputers. Even when existing trace methods can be used on multicomputers, the amount of collected data typically grows with the number of processors, so I/O and trace storage costs increase. A new technique is presented which modifies the executable code to dynamically collect the address trace from the user code and analyzes this trace during the execution of the program. This method helps resolve the I/O and storage problems and facilitates parallel analysis of the address trace. If a trace stored on disk is desired, the generated trace information can also be written to files during execution, with a resultant drop in program execution speed. An initial implementation on the Intel iPSC/2 hypercube multicomputer is detailed, and sample simulation results are presented. The effect of this trace collection method on execution time is illustrated.

Stunkel, Craig B.↗

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

Analysis of hypercube cache performance using address traces generated by TRAPEDS

The authors utilize a recently developed software method of capturing and analyzing address traces, known as TRAPEDS (TRAce Producing Execution Driven Simulation), to provide address traces for cache performance evaluation on a hypercube multicomputer. Utilizing TRAPEDS user code traces obtained from the implementations of several parallel algorithms on the Intel iPSC/2 hypercube, the authors simulate the cache performance effects of changing cache size, line size, and set associativity. Particular attention is devoted to the effect on cache performance of changing the dimension of the hypercube for a particular program and to the variation in cache statistics among the nodes of the hypercube.

Stunkel, Craig B.↗

NASA NTRS1988

TRAPEDS: Producing traces for multicomputers via execution-driven simulation

Trace-driven simulation is an important aid in performance analysis of computer systems. Capturing address traces for these simulations is a difficult problem for single processors and particularly for multicomputers. Even when existing trace methods can be used on multicomputers, the amount of collected data typically grows with the number of processors, so I/O and trace storage costs increase. A new technique is presented which modifies the executable code to dynamically collect the address trace from the user code and analyzes this trace during the execution of the program. This method helps resolve the I/O and storage problems and facilitates parallel analysis of the address trace. If a trace stored on disk is desired, the generated trace information can also be written to files during execution, with a resultant drop in program execution speed. An initial implementation on the Intel iPSC/2 hypercube multicomputer is detailed, and sample simulation results are presented. The effect of this trace collection method on execution time is illustrated.

Stunkel, Craig B.↗