This article describes the design and development of a smart-and-connected low-cost Iowan-designed canopy (I-Canopy) sensor system that is enabled by the Internet of Things (IoT) devices capabilities, empowered by solar-based rechargeable batteries, and developed for community science applications. The I-Canopy sensor, is designed for real-time monitoring of near-surface air properties (temperature, relative humidity, pressure) and soil properties (temperature and moisture) for a wide range of weather and canopy conditions. The sensor is well suited for rural areas where the real-time data of air and soil is lacking in part due to the lack of broadband internet connection, and in part due to the limited (if any) ground-based weather stations in the current federal and state observation network. The canopy sensor has been tested in rural communities in western Nebraska to provide information for farmer's decision-making of irrigation and agricultural water use in the crop growing season. The sensor is capable to transmit data through both WiFi and LoRaWAN in real-time to a cloud data server and the local data server. Presented here are the first results of the sensor design and sensor data evaluation in various out-door environments, which illustrates the high-level readiness of the sensor for large-scale deployment for either routine or scientific applications for rural areas.

Summary form only given. In science and engineering, a tsunami of new experimental and computational data and a suite of increasingly ubiquitous sensors pose vexing problems in data analysis, transport, visualization and collaboration. Cloud computing and "big data," together with our experiences with clusters and grids, are extending our notions of computational science and engineering, bringing technical, political and economic challenges. What are the software structures and capabilities that best exploit these capabilities and economics while providing application compatibility and community continuity? What are the appropriate roles of public clouds relative to local computing systems, private clouds and grids? How can we best exploit elasticity for peak demand? How do we optimize performance and reliability? How do we provide privacy and security? How do we balance traditional HPC investments against distributed systems and big data opportunities and avoid past research infrastructure pitfalls? How do we integrate the emerging Internet of Things and ubiquitous sensors for multidisciplinary fusion, while also managing security and privacy?

Existing supercomputers have hundreds of thousands of processor cores, and future systems may have hundreds of millions. Developers need detailed performance measurements to tune their applications and to exploit these systems fully. However, extreme scales pose unique challenges for performance-tuning tools, which can generate significant volumes of I/O. Compute-to-I/O ratios have increased drastically as systems have grown, and the I/O systems of large machines can handle the peak load from only a small fraction of cores. Tool developers need efficient techniques to analyze and to reduce performance data from large numbers of cores.

Abstract Achieving high performance for distributed I/O on a wide‐area network continues to be an elusive holy grail. Despite enhancements in network hardware as well as software stacks, achieving high‐performance remains a challenge. In this paper, our worldwide team took a completely new and non‐traditional approach to distributed I/O, calledParaMEDIC: Parallel Metadata Environment for Distributed I/O and Computing, by utilizing application‐specifictransformationof data to orders of magnitude smaller metadata before performing the actual I/O. Specifically, this paper details our experiences in deploying a large‐scale system to facilitate the discovery of missing genes and constructing a genome similarity tree by encapsulating the mpiBLAST sequence‐search algorithm into ParaMEDIC. The overall project involved nine computational sites spread across the U.S. and generated more than a petabyte of data that was ‘teleported’ to a large‐scale facility in Tokyo for storage. Copyright © 2010 John Wiley & Sons, Ltd.

In this paper, we describe the design and implementation of two mechanisms for fault-tolerance and recovery for complex scientific workflows on computational grids. We present our algorithms for over-provisioning and migration, which are our primary strategies for fault-tolerance. We consider application performance models, resource reliability models, network latency and bandwidth and queue wait times for batch-queues on compute resources for determining the correct fault-tolerance strategy. Our goal is to balance reliability and performance in the presence of soft real-time constraints like deadlines and expected success probabilities, and to do it in a way that is transparent to scientists. We have evaluated our strategies by developing a Fault-Tolerance and Recovery (FTR) service and deploying it as a part of the Linked Environments for Atmospheric Discovery (LEAD) production infrastructure. Results from real usage scenarios in LEAD show that the failure rate of individual steps in workflows decreases from about 30% to 5% by using our fault-tolerance strategies.

Without doubt, scientific discovery, business practice and social interactions are moving rapidly from a world of homogeneous and local systems to a world of distributed software, virtual organizations and cloud computing infrastructure, all powered by multicore processors and large-scale infrastructure. In science, a tsunami of new experimental and computational data and a suite of increasingly ubiquitous sensors pose vexing problems in data analysis, transport, visualization and collaboration. In society and business, software as a service and cloud computing are empowering distributed groups. Letpsilas step back and think about the longer term future. Where is the technology going and what are the implications? What architectures are appropriate? How to we manage power and scale? What are the right size building blocks? How do we come to grips with the fact that our clusters and data centers are now bigger than the Internet was just a few years ago? How do we develop and support malleable software? What is the ecosystem of components in which distributed, data rich applications will operate? How do we optimize performance and reliability? How do we program these systems?

Scientific applications have diverse characteristics and resource requirements. When combined with the complexity of underlying distributed resources on which they execute (e.g. Grid, cloud computing), these applications can experience significant performance fluctuations as machine reliability varies. Although the performance and reliability of cluster and Grid systems have been studied separately, there has been little analysis of the lost Quality of Service (QoS) experienced with varying availability levels. To enable a dynamic environment that can account for such changes while providing required QoS, next generation tools will need extensible application interfaces that allow users to qualitatively express performance and reliability requirements for the underlying systems. In this paper, we use the concept of performability to capture the degraded performance that might result from varying resource availability. We apply the resulting model to workflow planning and fault tolerance strategies. We present experimental data to validate our model and use simulation results driven by failure data from real HPC systems to demonstrate how the proposed scheme better accounts for resource availability.

Emerging petascale systems will have many hundreds of thousands of processors, but traditional task-level tracing tools already fail to scale to much smaller systems because the I/O backbones of these systems cannot handle the peak load offered by their cores. Complete event traces of all processes are thus infeasible. To retain the benefits of detailed performance measurement while reducing volume of collected data, we developed AMPL, a general-purpose toolkit that reduces data volume using stratified sampling. We adopt a scalable sampling strategy, since the sample size required to measure a system varies sub-linearly with process count. By grouping, or stratifying, processes that behave similarly, we can further reduce data overhead while also providing insight into an application's behavior. In this paper, we describe the AMPL toolkit and we report our experiences using it on large-scale scientific applications. We show that AMPL can successfully reduce the overhead of tracing scientific applications by an order of magnitude or more, and we show that our tool scales sub-linearly, so the improvement will be more dramatic on petascale machines. Finally, we illustrate the use of AMPL to monitor applications by performance-equivalent strata, and we show that this technique can allow for further reductions in trace data volume and traced execution time.

Grids promote new modes of scientific collaboration and discovery by connecting distributed instruments, data and computing facilities. Because many resources are shared, application performance can vary widely and unexpectedly. We describe a novel performance analysis framework that reasons temporally and qualitatively about performance data from multiple monitoring levels and sources. The framework periodically analyzes application performance states by generating and interpreting signatures containing structural and temporal features from time-series data. Signatures are compared to expected behaviors and in case of mismatches, the framework hints at causes of degraded performance, based on unexpected behavior characteristics previously learned by application exposure to known performance stress factors. Experiments with two scientific applications reveal signatures that have distinct characteristics during well-performing versus poor-performing executions. The ability to automatically and compactly generate signatures capturing fundamental differences between good and poor application performance states is essential to improving the quality of service for Grid applications.

Good load balance is crucial on very large parallel systems, but the most sophisticated algorithms introduce dynamic imbalances through adaptation in domain decomposition or use of adaptive solvers. To observe and diagnose imbalance, developers need system-wide, temporally-ordered measurements from full-scale runs. This potentially requires data collection from multiple code regions on all processors over the entire execution. Doing this instrumentation naively can, in combination with the application itself, exceed available I/O bandwidth and storage capacity, and can induce severe behavioral perturbations. We present and evaluate a novel technique for scalable, low-error load balance measurement. This uses a parallel wavelet transform and other parallel encoding methods. We show that our technique collects and reconstructs system-wide measurements with low error. Compression time scales sublinearly with system size and data volume is several orders of magnitude smaller than the raw data. The overhead is low enough for online use in a production environment.

This study examined the interplay among processor speed, cluster interconnect and file I/O, using parallel applications to quantify interactions. We focused on a common case where multiple compute nodes communicate with a single master node for file accesses. We constructed a predictive model that used time characteristics critical for application performance to estimate the number of nodes beyond which further performance improvement became unattainable. Predictions were experimentally validated with NAMD, a representative parallel application designed for molecular dynamics simulation. Such predictions can help guide decision making to improve machine allocations for parallel codes in large clusters.

This BOF is a venue for presentations and discussions of progress in the dual problems of evaluating the performance (including reliability) of petascale computing systems and of developing application codes that scale to run effectively on such systems. We therefore invite participation by representatives of large-system vendors, funding agencies, infrastructure operators, appplication-development groups, and others that have a stake in design, operation, and successful use of these systems.Technical topics to be addressed include: scaling properties of benchmark suites; scalable machine models; application modeling to predict scaling for future machines; the problem of preparing applications for petascale environments; and the role of all of these topics in petascale acquisitions.At this session we will start planning for a series of workshops on the subject.

In this session the awards for: Best Paper, Best Student Paper, Best Poster, ACM Student Research Competition, Analytics Challenge, Bandwidth Challenge, and Storage Challenge will be presented.

Summary form only given. Systems built from commodity processors dominate high-performance computing, with systems containing thousands of processors now being deployed. As node counts for multi-teraflop systems grow to tens of thousands, with proposed petaflop system likely to contain hundreds of thousands of nodes, and with a tsunami of new experimental and computational. The mean time before failure (MTBF) for the individual components (i.e., processors, disks, memories, power supplies, fans and networks) is high. In contrast to parallel systems, distributed software for networks, whether transport protocols or Web/Grid services, are designed to be resilient to component failures. Our thesis is that these "two worlds" of software-distributed systems and parallel systems. In this paper, we describe possible approaches for the design and effective use of large-scale systems. The approaches range from intelligent hardware monitoring and adaptation, through low-overhead recovery schemes, statistical sampling and differential scheduling and to alternative models of system software, including evolutionary adaptation.

Grid applications access distributed, and often shared, resources. One consequence of this resource sharing is that measured application performance can vary widely and in unexpected ways. Determining the causes of poor performance, due to either anomalous application behavior or contention for shared resource use, and adapting to changing circumstances are critical to creation of robust Grid applications. Performance contracts and real-time adaptive control are two mechanisms to realize soft performance guarantees in Grid environments. Performance contracts formalize the relationship between application performance needs and resource capabilities. During execution, contract monitors use performance data to verify that expectations are met. When the contracted specifications are not satisfied, the system can choose to either adapt the application to available resources or reschedule the application on a new set of resources that can satisfy the original contract specifications. We describe an infrastructure for Grid application contract development and monitoring. This infrastructure, based on the Autopilot toolkit, provides flexible and scalable tools to assess both application and system behavior.

Today, clusters built from commodity PCs dominate high-performance computing, with systems containing thousands of processors now being deployed. As node counts for multi-teraflop systems grow to thousands and with proposed petaflop system likely to contain tens of thousands of nodes, the standard assumption that system hardware and software are fully reliable becomes much less credible. Concomitantly, understanding application sensitivity to system failures is critical to establishing confidence in the outputs of large-scale applications. Using software fault injection, we simulated single bit memory errors, register file upsets and MPI message payload corruption and measured the behavioral responses for a suite of MPI applications. These experiments showed that most applications are very sensitive to even single errors. Perhaps most worrisome, the errors were often undetected, yielding erroneous output with no user indicators. Encouragingly, even minimal internal application error checking and program assertions can detect some of the faults we injected.

Inadequate I/O performance remains a major challenge in using high-end computing systems effectively. To address this problem, we present TsModeler, an automatic time series modeling and prediction framework for adaptive I/O prefetching that uses ARIMA time series models to predict the temporal patterns of I/O requests. These online pattern analysis techniques and cutoff indicators for autocorrelation patterns enable multistep online predictions suitable for multiblock prefetching. This work also combines time series predictions with spatial Markov model predictions to determine when, what, and how many blocks to prefetch. Experimental results show reductions in execution time compared to the standard Linux file system across various hardware configurations.

Given the increasing performance disparity between processors and storage devices, exploiting knowledge of spatial and temporal I/O requests is critical to achieving high performance, particularly on parallel systems. Although perfect foreknowledge of I/O requests is rarely possible, even estimates of request patterns can potentially yield large performance gains. This paper evaluates Markov models to represent the spatial patterns of I/O requests in scientific codes. The paper also proposes three algorithms for I/O prefetching. Evaluation using I/O traces from scientific codes shows that highly accurate prediction of spatial access patterns, resulting in reduced execution times, is possible.

Understanding the dynamic behavior of parallel programs is key to developing efficient system software and runtime environments; this is even more true on emerging computational Grids where resource availability and performance can change in unpredictable ways. Event tracing provides details on behavioral dynamics, albeit often at great cost. We describe an intermediate approach, based on curve fitting, that retains many of the advantages of event tracing but with lower overhead. These compact "application signatures" summarize the time-varying resource needs of scientific codes from historical trace data. We also developed a comparison scheme that measures similarity between two signatures, both across executions and across execution environments.

Input/output performance on current parallel file systems is sensitive to a good match of application access patterns to file system capabilities. Automatic input/output access pattern classification can determine application access patterns at execution time, guiding adaptive file system policies. In this paper, we examine and compare two novel input/output access pattern classification methods based on learning algorithms. The first approach uses a feedforward neural network previously trained on access pattern benchmarks to generate qualitative classifications. The second approach uses hidden Markov models trained on access patterns from previous executions to create a probabilistic model of input/output accesses. In a parallel application, access patterns can be recognized at the level of each local thread or as the global interleaving of all application threads. Classification of patterns at both levels is important for parallel file system performance; we propose a method for forming global classifications from local classifications. We present results from parallel and sequential benchmarks and applications that demonstrate the viability of this approach.

Summary form only given, as follows. The complete presentation was not made available for publication as part of the conference proceedings. Commodity processors and storage (embodied in clusters), very high-performance WAN and LAN interconnects, Linux and open source HPC and Grid software are transforming the way we develop and deploy high-performance computing resources. Concurrently, a new model of nationally integrated, tightly coupled scientific data archives and instruments is emerging. This talk outlines a new worldview of distributed data, computing, and network resources for 21st century science and engineering. It concludes with a look at the future of cluster computing and some thoughts on the five and ten year futures.

Bursty application I/O patterns, together with transfer limited storage devices, combine to create a major I/O bottleneck on parallel systems. This paper explores the use of time series models to forecast application I/O request times, then prefetching I/O requests during computation intervals to hide I/O latency. Experimental results with I/O intensive scientific codes show performance improvements compared to standard UNIX prefetching strategies.

Complex, distributed applications pose new challenges for performance analysis and optimization. This paper outlines an online approach to performance analysis where developers are active participants, using integrated measurement and immersive performance visualization to tune parallel and distributed applications.

In this paper we present the design of SvPablo, a language independent performance analysis and visualization system that can be easily extended to new contexts with minimal changes to the software infrastructure. At present, SvPablo supports analysis of applications written in C, Fortran 77, Fortran 90, and HPF on a variety of sequential and parallel systems. In addition to capturing application data via software instrumentation, SvPablo also exploits hardware performance counters to capture the interaction of software and hardware. Both hardware and software performance data are summarized during program execution, enabling measurement of programs that execute for hours or days on hundreds of processors. This performance data is stored in a format designed to be language transparent and portable. We demonstrate the usefulness of SvPablo for tuning application programs with a case study running on an SGI Origin 2000.

Computer systems and applications are growing more complex. Consequently, performance analysis has become more difficult due to the complex, transient interrelationships among runtime components. To diagnose these types of performance issues, developers must use detailed instrumentation to capture a large number of performance metrics. Unfortunately, this instrumentation may actually influence the performance analysis, leading the developer to an ambiguous conclusion. In this paper, we introduce a technique for focusing a performance analysis on interesting performance metrics. This technique, called dynamic statistical projection pursuit, identifies interesting performance metrics that the monitoring system should capture across some number of processors. By reducing the number of performance metrics, projection pursuit can limit the impact of instrumentation on the performance of the target system and can reduce the volume of performance data.

With increasing development of applications for heterogeneous, distributed computing grids, the focus of performance analysis has shifted from a posteriori optimization on homogeneous parallel systems to application tuning for heterogeneous resources with time varying availability. This shift has profound implications for performance instrumentation and analysis techniques. Autopilot is a new infrastructure for dynamic performance tuning of heterogeneous computational grids based on closed loop control. The paper describes the Autopilot model of distributed sensors, actuators, and decision procedures, reports preliminary performance benchmarks, and presents a case study in which the Autopilot library is utilized in the development of an adaptive parallel input/output system.

Parallel input/output systems attempt to alleviate the performance bottleneck that affects many input/output intensive applications. In such systems, an understanding of the application access pattern, especially how requests from multiple processors for different file regions are logically related, is important for optimizing file system performance. We propose a method for automatically classifying these global access patterns and using these global classifications to select and tune file system policies to improve input/output performance. We demonstrate this approach on benchmarks and scientific applications using global classification to automatically select appropriate underlying Intel PFS input/output modes and server buffering strategies.

The modest I/O configurations and file system limitations of many current high-performance systems preclude solution of problems with large I/O needs. I/O hardware and file system parallelism is the key to achieving high performance. We analyze the I/O behavior of several versions of two scientific applications on the Intel Paragon XP/S. The versions involve incremental application code enhancements across multiple releases of the operating system. Studying the evolution of I/O access patterns underscores the interplay between application access patterns and file system features. Our results show that both small and large request sizes are common, that at present, application developers must manually aggregate small requests to obtain high disk transfer rates, that concurrent file accesses are frequent, and that appropriate matching of the application access pattern and the file system access mode can significantly increase application I/O performance. Based on these results, we describe a set of file system design principles.

Article Free Access Share on PPFS: a high performance portable parallel file system Authors: James V. Huber Department of Computer Science, University of Illinois, Urbana, Illinois Department of Computer Science, University of Illinois, Urbana, IllinoisView Profile , Andrew A. Chien Department of Computer Science, University of Illinois, Urbana, Illinois Department of Computer Science, University of Illinois, Urbana, IllinoisView Profile , Christopher L. Elford Department of Computer Science, University of Illinois, Urbana, Illinois Department of Computer Science, University of Illinois, Urbana, IllinoisView Profile , David S. Blumenthal Department of Computer Science, University of Illinois, Urbana, Illinois Department of Computer Science, University of Illinois, Urbana, IllinoisView Profile , Daniel A. Reed Department of Computer Science, University of Illinois, Urbana, Illinois Department of Computer Science, University of Illinois, Urbana, IllinoisView Profile Authors Info & Claims ICS '95: Proceedings of the 9th international conference on SupercomputingJuly 1995 Pages 385–394https://doi.org/10.1145/224538.224638Online:03 July 1995Publication History 127citation614DownloadsMetricsTotal Citations127Total Downloads614Last 12 Months18Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Supporting source-level performance analysis of programs written in data-parallel languages requires a unique degree of integration between compilers and performance analysis tools. Compilers for languages such as High Performance Fortran infer parallelism and communication from data distribution directives, thus, performance tools cannot meaningfully relate measurements about these key aspects of execution performance to source-level constructs without substantial compiler support. This paper describes an integrated system for performance analysis of data-parallel programs based on the Rice Fortran 77D compiler and the Illinois Pablo performance analysis toolkit. During code generation, the Fortran D compiler records mapping information and semantic analysis results describing the relationship between performance instrumentation and the original source program. An integrated performance analysis system based on the Pablo toolkit uses this information to correlate the program's dynamic behavior with the data parallel source code. The integrated system provides detailed source-level performance feedback to programmers via a pair of graphical interfaces. Our strategy serves as a model for integration of data-parallel compilers and performance tools.

Rapid increases in computing and communication performance are exacerbating the long-standing problem of performance-limited input/output. Indeed, for many otherwise scalable parallel applications. input/output is emerging as a major performance bottleneck. The design of scalable input/output systems depends critically on the input/output requirements and access patterns for this emerging class of large-scale parallel applications. However, hard data on the behavior of such applications is only now becoming available. In this paper, we describe the input-output requirements of three scalable parallel applications (electron scattering, terrain rendering, and quantum chemistry, on the Intel Paragon XP/S. As part of an ongoing parallel input/output characterization effort, we used instrumented versions of the application codes to capture and analyze input/output volume, request size distributions, and temporal request structure. Because complete traces of individual application input/output requests were captured, in-depth, off-line analyses were possible. In addition, we conducted informal interviews of the application developers to understand the relation between the codes' current and desired input/output structure. The results of our studies show a wide variety of temporal and spatial access patterns, including highly read-intensive and write-intensive phases, extremely large and extremely small request sizes, and both sequential and highly irregular access patterns. We conclude with a discussion of the broad spectrum of access patterns and their profound implications for parallel file caching and prefetching schemes.

Assessing the performance and software interactions of emerging parallel input/output systems is a critical first step in input/output software tuning. Moreover, understanding the system response to well-understood, synthetic input/output patterns is itself a prelude to analysis of more complex application input/output patterns. We have conducted a series of experiments to measure the performance of the CM-5's new Scalable Disk Array (SDA) and Scalable Parallel File System (SFS) using the file system interfaces provided by the data parallel CM Fortran and message passing CMMD programming models. The results of these experiments suggest that the CM-5's parallel input/output systems is an improvement over its predecessor, the CM-2 Data Vault. However, network bandwidth can be a bottleneck for the data reordering phase of input/output operations.

The National Center for Supercomputing Applications (NCSA) at the University of Illinois typifies current, high-performance computing centers that support a diverse user base of both academic and industrial accounts. The data requirements of this user community, coupled with resource constraints, mandate the use of an archival file system. This paper analyzes the spatial and temporal patterns of file archive transactions on the NCSA file archive. Analysis of archive transaction traces shows that the access patterns differ from those observed during studies of secondary storage systems: the files are larger, there are large temporal and spatial variations in transaction patterns, and a small number of research groups can easily account for twenty percent of the total traffic.

The Thinking Machines CM-5 is one of the first of a new generation of massively parallel systems.To assess the scalability of the CM-5's computation and interprocessor communication rates, we used a sem"es of benchmarks to measure the performance of the CM-5 data and control networks, the node vector units, and the balance of computation and communication.At the application level, we found the achievable communication bandwidth and processing rates to be roughly fifiy percent and forty percent, respectively, of the corresponding theoretical peak rates.Our early assessment is that the CM-5 is scalable but that a better balance of communication and processing rates would increase its effectiveness. 1

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.>

Abstract Among the many techniques in computer graphics, ray tracing is prized because it can render realistic images, albeit at great computational expense. Ray tracing's large computation requirements, coupled with its inherently parallel nature, make ray tracing algorithms attractive candidates for parallel implementation. In this paper we illustrate the utility and the importance of a suite of performance analysis tools when exploring the performance of several approaches to ray tracing on a distributed memory parallel system. These ray tracing algorithm variations introduce parallelism based on both ray and object partitions. Traditional timing analysis can quantify the performance effects of different algorithm choices (i.e. when an algorithm is best matched to a given problem), but it cannot identify the causes of these performance differences. We argue, by example, that a performance instrumentation system is needed 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 stapistics 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 computations; assimilating the enormous volume of performance data mandates visual display.

The authors study the instrumentation perturbations of software event tracing on the Alliant FX/80 vector multiprocessor in sequential, vector, concurrent, and vector-concurrent modes. Based on experimental data, they derive a perturbation model that can approximate true performance from instrumented execution. They analyze the effects of instrumentation coverage, (i.e., the ratio of instrumented to executed statements), source level instrumentation, and hardware interactions. The results show that perturbations in execution times for complete trace instrumentations can exceed three orders of magnitude. With appropriate models of performance perturbation, these perturbations in execution time can be reduced to less than 20% while retaining the additional information from detailed traces. In general, it is concluded that it is possible to characterize perturbations through simple models. This permits more detailed, accurate instrumentation than traditionally believed possible.>

It is shown that new techniques are needed to analyze and present performance data from massively parallel systems. Although parallel programs contain many tasks, typically, there are only a few equivalence classes of task behavior. The author is planning to incorporate algorithms for performance data clustering and display (i.e. equivalence class identification) performance data presentation.>

This paper discusses the following: effective instrumentation as the key to effective monitoring; distributed monitoring systems as a basis for general purpose distributed multiprocessors; problems and prospects; performance monitoring, fact and fancy; and software aspects.>

The complexity of parallel computer systems makes a priori performance prediction difficult and experimental performance analysis crucial. A complete characterization of software and hardware dynamics, needed to understand the performance of high-performance parallel systems, requires execution time performance instrumentation. Although software recording of performance data suffices for low frequency events, capture of detailed, high-frequency performance data ultimately requires hardware support if the performance instrumentation is to remain efficient and unobtrusive.

A tracing library for the Cray X-MP and Cray 2 supercomputers has been developed that supports the low-overhead capture of execution events for sequential and multitasked programs. This library has been extended to use the automatic instrumentation facilities on these machines, allowing trace data from routine entry and exit, and other program segments to be captured. To assess the utility of the trace-based tools, three of the Perfect Benchmark codes have been tested in scalar and vector models with the tracing instrumentation. In addition to computing summary execution statistics from the traces, interesting execution dynamics appear when studying the trace histories. It is also possible to compare codes across the two architectures by correlating the event traces. It is concluded that adding tracing support in Cray supercomputers can have significant returns in improved performance characterization and evaluation.>

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 we explore the performance of several approaches to ray tracing on a distributed memory parallel system. A set of performance instrumentation tools and their associated visualization software are used to identify the underlying causes of performance differences.

A method is presented that realizes a kind of interconnection network, called a hyperswitch network, that is achieved using a mixture of static and dynamic topologies. Available of fault-free paths need not be specified by a source because the routing header can be modified in response to congestion or faults encountered as a path is established. This method can be accomplished in a static topology such as the hypercube network if the nodes have switching elements which are capable of dynamically performing the necessary routing header revisions. Detailed simulation results show that the hyperswitch network is consistently more efficient than fixed-path routing for large message traffic conditions. The simulation results also show that the hyperswitch network has equivalent latency overhead for messages with localized and antilocal destinations (i.e., less than a 25% difference between diameter 1 and 5).>

The authors discuss a scheduling system implemented on a network of 12 AT&T 3B2 microcomputers, running a transport distributed operating system, the Loadable Illinois Networked Kernal (LINK). It is noted that the design overhead for a scheduling system built as part of an existing distributing computer system is very small compared to the design of the operating system itself. Moreover, an implementation allows one to answer many questions concerning load balancing problems that cannot be answered (or cannot be answered precisely) by queuing network models or simulation. The hardware and software environments are described together with the scheduler. Several experiments were performed to test the job scheduling system and it was found that substantial performance increases are possible compared to systems without a job scheduling system.>

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 queuing network models.>

Repeated studies have shown that a single switching technique, either circuit or packet switching, cannot optimally support a heterogeneous traffic mix composed of voice, video and data. Integrated networks support such heterogeneous traffic by combining circuit and packet switching in a single network. To manage the statistical variations of network traffic, we introduce a new, adaptive routing algorithm called hybrid, weighted routing. Simulations show that hybrid, weighted routing is preferable to other adaptive routing techniques for both packet switched networks and integrated networks.

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.

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. We derive partitions that minimize interprocessor communication when the number of processors is known a priori and each domain partition is assigned to a different processor. Our partitioning technique uses the stencil structure to select appropriate partition shapes. For square problem domains, we show that nonstandard partitions (e.g., hexagons) are frequently preferable to the standard square partitions for a variety of commonly used stencils. We conclude with a formalization of the relationship between partition shape, stencil structure, and architecture, allowing selection of optimal partitions for a variety of parallel systems.

The applicability of static data flow architectures to the iterative solution of sparse linear systems of equations is investigated. An analytic performance model of a static data flow computation is developed. This model includes both spatial parallelism, concurrent execution in multiple PEs, and pipelining, the streaming of data from array memories through the PEs. The performance model is used to analyze a row-partitioned iterative algorithms for solving sparse linear systems of algebraic equations. On the basis of this analysis, design parameters for the static data flow architecture as a function of matrix sparsity and dimension are proposed.

Because a group of interconnected microcomputers may not share any globally addressable memory, it is crucial that a multimicrocomputer interconnection network capable of efficiently supporting message passing be found. Using task precedence graphs to represent the time varying behavior of parallel computations, both the behavior of interconnection networks under varying workloads and the feasibility of distributed scheduling are investigated.

Recent developments in very large scale integration have made it feasible to construct a highly parallel computer composed of large numbers of interconnected microcomputers. The modeling problems posed by this approach to parallel processing differ in several significant respects from those associated with traditional queueing network models of computer systems. Among them are the size of the models, the varied interconnection network topologies, and algorithm dependent internode communication patterns. We extend queueing theoretic models to include multimicrocomputer networks with primary emphasis on two areas: characterizing interconnection network workloads and finding efficient solution techniques for the resulting models.

Several interconnection structures for a distributed multimicrocomputer message-passing system are compared on the basis of cost and performance. Among the structures analyzed are buses, double rings, D-dimensional toroids, trees, cube-connected cycles, and chordal rings. Network cost is defined in terms of the number of network nodes and the unit cost of communication links and their associated connections. Simple asymptotic performance bounds are derived based on the bottleneck analysis of a queueing network. In contrast to the usual assumption of uniform message routing, the technique permits the introduction of a reference locality notion to the message routing behavior of network nodes. Finally, the cost, performance, and performance/cost functions are examined as the number of network nodes becomes very large.