Recent work have used both failure logs and resource use data separately (and together) to detect system failure-inducing errors and to diagnose system failures. System failure occurs as a result of error propagation and the (unsuccessful) execution of error recovery mechanisms. Knowledge of error propagation patterns and unsuccessful error recovery is important for more accurate and detailed failure diagnosis, and knowledge of recovery protocols deployment is important for improving system reliability. This paper presents the CORRMEXT framework which carries failure diagnosis another significant step forward by analyzing and reporting error propagation patterns and degrees of success and failure of error recovery protocols. CORRMEXT uses both error messages and resource use data in its analyses. Application of CORRMEXT to data from the Ranger supercomputer have produced new insights. CORRMEXT has: (i) identified correlations between resource use counters that capture recovery attempts after an error, (ii) identified correlations between error events to capture error propagation patterns within the system, (iii) identified error propagation and recovery paths during system execution to explain system behaviour, (iv) showed that the earliest times of change in system behaviour can only be identified by analyzing both the correlated resource use counters and correlated errors. CORRMEXT will be installed on the HPC clusters at the Texas Advanced Computing Center in Autumn 2017.

Failure diagnosis for large compute clusters using only message logs is known to be incomplete. Recent availability of resource use data provides another potentially useful source of data for failure detection and diagnosis. Early work combining message logs and resource use data for failure diagnosis has shown promising results. This paper describes the CRUMEL framework which implements a new approach to combining rationalized message logs and resource use data for failure diagnosis. CRUMEL identifies patterns of errors and resource use and correlates these patterns by time with system failures. Application of CRUMEL to data from the Ranger supercomputer has yielded improved diagnoses over previous research. CRUMEL has: (i) showed that more events correlated with system failures can only be identified by applying different correlation algorithms, (ii) confirmed six groups of errors, (iii) identified Lustre I/O resource use counters which are correlated with occurrence of Lustre faults which are potential flags for online detection of failures, (iv) matched the dates of correlated error events and correlated resource use with the dates of compute node hang-ups and (v) identified two more error groups associated with compute node hang-ups. The pre-processed data will be put on the public domain in September, 2016.

The use of console logs for error detection in large scale distributed systems has proven to be useful to system administrators. However, such logs are typically redundant and incomplete, making accurate detection very difficult. In an attempt to increase this accuracy, we complement these incomplete console logs with resource usage data, which captures the resource utilisation of every job in the system. We then develop a novel error detection methodology, the CRUDE approach, that makes use of both the resource usage data and console logs. We thus make the following specific technical contributions: we develop (i) a clustering algorithm to group nodes with similar behaviour, (ii) an anomaly detection algorithm to identify jobs with anomalous resource usage, (iii) an algorithm that links jobs with anomalous resource usage with erroneous nodes. We then evaluate our approach using console logs and resource usage data from the Ranger Supercomputer. Our results are positive: (i) our approach detects errors with a true positive rate of about 80%, and (ii) when compared with the well-known Nodeinfo error detection algorithm, our algorithm provides an average improvement of around 85% over Nodeinfo, with a best-case improvement of 250%.

A majority of parallel applications executed on HPC clusters use MPI for communication between processes. Most users treat MPI as a black box, executing their programs using the cluster's default settings. While the default settings perform adequately for many cases, it is well known that optimizing the MPI environment can significantly improve application performance. Although the existing optimization tools are effective when used by performance experts, they require deep knowledge of MPI library behavior and the underlying hardware architecture in which the application will be executed. Therefore, an easy-to-use tool that provides recommendations for configuring the MPI environment to optimize application performance is highly desirable. This paper addresses this need by presenting an easy-to-use methodology and tool, named MPI Advisor, that requires just a single execution of the input application to characterize its predominant communication behavior and determine the MPI configuration that may enhance its performance on the target combination of MPI library and hardware architecture. Currently, MPI Advisor provides recommendations that address the four most commonly occurring MPI-related performance bottlenecks, which are related to the choice of: 1) point-to-point protocol (eager vs. rendezvous), 2) collective communication algorithm, 3) MPI tasks-to-cores mapping, and 4) Infiniband transport protocol. The performance gains obtained by implementing the recommended optimizations in the case studies presented in this paper range from a few percent to more than 40%. Specifically, using this tool, we were able to improve the performance of HPCG with MVAPICH2 on four nodes of the Stampede cluster from 6.9 GFLOP/s to 10.1 GFLOP/s. Since the tool provides application-specific recommendations, it also informs the user about correct usage of MPI.

Ensuring high reliability of large-scale clusters is becoming more critical as the size of these machines continues to grow, since this increases the complexity and amount of interactions between different nodes and thus results in a high failure frequency. For this reason, predicting node failures in order to prevent errors from happening in the first place has become extremely valuable. A common approach for failure prediction is to analyze traces of system events to find correlations between event types or anomalous event patterns and node failures, and to use the types or patterns identified as failure predictors at run-time. However, typical centralized solutions for failure prediction in this manner suffer from high transmission and processing overheads at very large scales. We present a solution to the problem of predicting compute node soft-lockups in large scale clusters by using a decentralized online clustering algorithm (DOC) to detect anomalies in resource usage logs, which have been shown to correlate to particular types of node failures in supercomputer clusters. We demonstrate the effectiveness of this system by using the monitoring logs from the Ranger supercomputer at Texas Advanced Computing Center. Experiments shows that this approach can achieve similar accuracy as other related approaches, while maintaining low RAM and bandwidth usage, with a runtime impact to current running applications of less than 2%.

SUMMARY The important role high‐performance computing (HPC) resources play in science and engineering research, coupled with its high cost (capital, power and manpower), short life and oversubscription, requires us to optimize its usage – an outcome that is only possible if adequate analytical data are collected and used to drive systems management at different granularities – job, application, user and system. This paper presents a method for comprehensive job, application and system‐level resource use measurement, and analysis and its implementation. The steps in the method are system‐wide collection of comprehensive resource use and performance statistics at the job and node levels in a uniform format across all resources, mapping and storage of the resultant job‐wise data to a relational database, which enables further implementation and transformation of the data to the formats required by specific statistical and analytical algorithms. Analyses can be carried out at different levels of granularity: job, user, application or system‐wide. Measurements are based on a new lightweight job‐centric measurement tool ‘TACC_Stats’, which gathers a comprehensive set of resource use metrics on all compute nodes and data logged by the system scheduler. The data mapping and analysis tools are an extension of the XDMoD project. The method is illustrated with analyses of resource use for the Texas Advanced Computing Center's Lonestar4, Ranger and Stampede supercomputers and the HPC cluster at the Center for Computational Research. The illustrations are focused on resource use at the system, job and application levels and reveal many interesting insights into system usage patterns and also anomalous behavior due to failure/misuse. The method can be applied to any system that runs the TACC_Stats measurement tool and a tool to extract job execution environment data from the system scheduler. Copyright © 2014 John Wiley & Sons, Ltd.

This paper presents a tool chain, based on the open source tool TACC_Stats, for systematic and comprehensive job level resource use measurement for large cluster computers, and its incorporation into XDMoD, a reporting and analytics framework for resource management that targets meeting the information needs of users, application developers, systems administrators, systems management and funding managers. Accounting, scheduler and event logs are integrated with system performance data from TACC_Stats. TACC_Stats periodically records resource use including many hardware counters for each job running on each node. Furthermore, system level metrics are obtained through aggregation of the node (job) level data. Analysis of this data generates many types of standard and custom reports and even a limited predictive capability that has not previously been available for open-source, Linux-based software systems. This paper presents case studies of information that can be applied for effective resource management. We believe this system to be the first fully comprehensive system for supporting the information needs of all stakeholders in open-source software based HPC systems.

Bursts of abnormally high use of resources are thought to be an indirect cause of failures in large cluster systems, but little work has systematically investigated the role of high resource usage on system failures, largely due to the lack of a comprehensive resource monitoring tool which resolves resource use by job and node. The recently developed TACC_Stats resource use monitor provides the required resource use data. This paper presents the ANCOR diagnostics system that applies TACC_Stats data to identify resource use anomalies and applies log analysis to link resource use anomalies with system failures. Application of ANCOR to first identify multiple sources of resource anomalies on the Ranger supercomputer, then correlate them with failures recorded in the message logs and diagnosing the cause of the failures, has identified four new causes of compute node soft lockups. ANCOR can be adapted to any system that uses a resource use monitor which resolves resource use by job.

Program performance optimization is usually based solely on measurements of execution behavior of code segments using hardware performance counters. However, memory access patterns are critical performance limiting factors for today's multicore chips where performance is highly memory bound. Therefore diagnoses and selection of optimizations based only on measurements of the execution behavior of code segments are incomplete because they do not incorporate knowledge of memory access patterns and behaviors. This paper presents a low-overhead tool (MACPO) that captures memory traces and computes metrics for the memory access behavior of source-level (C, C++, Fortran) data structures. It also presents a complete process for integrating code segment-based and memory access pattern measurements and analyses for performance optimization specifically targeting multicore chips and multichip nodes of clusters. MACPO explicitly targets the measurement and metrics important to performance optimization for multicore chips. MACPO uses more realistic cache models for computation of latency metrics than those used by previous tools. Evaluation of the effectiveness of adding memory access behavior characteristics of data structures to performance optimization was done on subsets of the ASCI, NAS and Rodina parallel benchmarks and one application program from a domain not represented in these benchmarks. Adding memory behavior characteristics enabled easier diagnoses of bottlenecks and more accurate selection of appropriate optimizations than with only code centric behavior measurements. The performance gains ranged from a few percent to 38 percent.

Program performance optimization is generally based on measurements of execution behavior of code segments. However, an equally important task for performance optimizations is understanding memory access behaviors and thus, data structure access patterns and properties. Because memory-related problems in multi-core applications can have a significant impact on overall performance, optimizations in data access patterns will likely give a big boost to application performance. But effective diagnosis of performance bottlenecks requires that the memory measurements be related to high-level data structures (C, C++ arrays, structures, etc.). In this work, we present a low-overhead tool that captures memory traces and computes several metrics for performance characteristics of source-level data structures. Explicit consideration is given to measurement and diagnosis for multicore chips. Case studies which include (manual) use of the data structure memory access metrics to select and implement optimizations are given.

A goal for the analysis of supercomputer logs is to establish causal relationships among events which reflect significant state changes in the system. Establishing these relationships is at the heart of failure diagnosis. In principle, a log analysis tool could automate many of the manual steps systems administrators must currently use to diagnose system failures. However, supercomputer logs are unstructured, incomplete and contain considerable ambiguity so that direct discovery of causal relationships is difficult. This paper describes the second generation FDiag log-based failure diagnostics framework that provides automation of the manual failure diagnosis process and determines with high confidence, the likely cause of the failure, the components involved and the event sequences which contain the times of the causal and terminal events. FDiag extracts relevant events from the system logs, performs correlation analysis on these events and from these correlations determines the components involved and the event sequences. The diagnostics capabilities of FDiag are validated by comparing its assessments on known instances of recurrent failures on the Ranger supercomputer at the University of Texas at Austin. We believe FDiag is the first log analyzer to demonstrate this level of diagnostics capability from the system logs of an open source software stack incorporating Linux and the Lustre file system. FDiag will be put into production use for support of failure diagnosis on Ranger in September, 2011.

The computation nodes of modern supercomputers commonly consist of multiple multicore processors. To maximize the performance of such systems requires measurement, analysis, and optimization techniques that specifically target multicore environments. This paper first examines traditional unicore metrics and demonstrates how they can be misleading in a multicore system. Second, it examines and characterizes performance bottlenecks specific to multicore-based systems. Third, it describes performance measurement challenges that arise in multicore systems and outlines methods for extracting sound measurements that lead to performance optimization opportunities. The measurement and analysis process is based on a case study of the HOMME atmospheric modeling benchmark code from NCAR running on supercomputers built upon AMD Barcelona and Intel Nehalem quad-core processors. Applying the multicore bottleneck analysis to HOMME led to multicore aware source-code optimizations that increased performance by up to 35%. While the case studies were carried out on multichip nodes of supercomputers using an HPC application as the target for optimization, the pitfalls identified and the insights obtained should apply to any system that is composed of multicore processors.

System event logs are often the primary source of information for diagnosing (and predicting) the causes of failures for cluster systems. Due to interactions among the system hardware and software components, the system event logs for large cluster systems are comprised of streams of interleaved events, and only a small fraction of the events over a small time span are relevant to the diagnosis of a given failure. Furthermore, the process of troubleshooting the causes of failures is largely manual and ad-hoc. In this paper, we present a systematic methodology for reconstructing event order and establishing correlations among events which indicate the root-causes of a given failure from very large syslogs. We developed a diagnostics tool, FDiag, to extract the log entries as structured message templates and uses statistical correlation analysis to establish probable cause and effect relationships for the fault being analyzed. We applied FDiag to analyze failures due to breakdowns in interactions between the Lustre file system and its clients on the Ranger supercomputer at the Texas Advanced Computing Center (TACC). The results are positive. FDiag is able to identify the dates and the time periods that contain the significant events which eventually led to the occurrence of compute node soft lockups.

HPC systems are notorious for operating at a small fraction of their peak performance, and the ongoing migration to multi-core and multi-socket compute nodes further complicates performance optimization. The readily available performance evaluation tools require considerable effort to learn and utilize. Hence, most HPC application writers do not use them. As remedy, we have developed PerfExpert, a tool that combines a simple user interface with a sophisticated analysis engine to detect probable core, socket, and node-level performance bottlenecks in each important procedure and loop of an application. For each bottle-neck, PerfExpert provides a concise performance assessment and suggests steps that can be taken by the programmer to improve performance. These steps include compiler switches and optimization strategies with code examples. We have applied PerfExpert to several HPC production codes on the Ranger supercomputer. In all cases, it correctly identified the critical code sections and provided accurate assessments of their performance.

This paper formulates and illustrates the integration of resource safety verification into a design methodology for development of verified and robust real-time embedded systems. Resource-related concerns are not closely linked with current xUML model-based software development although they are critical for embedded systems. We describe how to integrate resource analysis techniques into the early phase of an xUML-based development cycle. Our hybrid framework for resource safety verification combines static resource analysis and runtime monitoring. A case study based on an embedded controller for satellite simulation, TableSat, illustrates the benefits obtained by incorporating resource verification into design and combining static analysis and runtime monitoring.

This paper presents a new state space reduction technique that applies to model checking of software. The new technique, precision abstraction, borrows ideas from dataflow analysis to identify procedures that can be analyzed context-insensitively without affecting the accuracy of the verification of a given property. These context-insensitive procedures can then be represented with fewer states than would be needed context-sensitive analysis. Preliminary results indicate that the number of transitions in the analysis prescribed by our approach is at least 155 times fewer than the exhaustive analysis a model checker would otherwise perform.

Abstract This paper is a case study of the effectiveness of component‐oriented development for enhancing both productivity and performance for parallel programs. A process for converting monolithic applications into semantically composable components is described. The supporting software, the P‐COM2 compositional compiler, is briefly described. The componentized version of Sweep3D is described. Productivity is illustrated by composing different instances of the Sweep3D code through automated composition of components using P‐COM2. These instances, each of which targets improving performance for some execution environment or problem case, are examples of a family of instances which are composable from a modest set of components. It is found that customization of componentized codes by component‐level adaptation may yield substantial performance improvement for specific execution environments. We identify and explain some of the benefits of component‐oriented development for high‐performance parallel systems. Copyright © 2006 John Wiley & Sons, Ltd.

This paper presents initial research on unification of methods for verification and validation (V&V) of software systems. The synergism among methods for V&V are described. The requirements for a unification are defined. The initial steps of a case study of application of the unified approach to V&V is sketched including definition of the problem domain, the approach and some details of a property specification language. An undergraduate course introducing the unified approach to V&V is described. The relationship of this research to other efforts toward unification of V&V are discussed.

This paper presents a classification of implementations of access control systems based on a lattice taxonomy where the axes are properties of the implementation. The current taxonomy has six axes representing:partitioning of control over sharing of access control credentials, distribution of the state relevant to access control decisions,.delity of policy enforcement, the identity resolution mechanism, local versus centralized decisions,and static or adaptive trust management.Analysis of implemented systems in terms of these properties sheds insight on tradeo .s between performance, scalability and potential vulnerability to specified attacks. The taxonomy reveals that distributed systems for several points on the lattice with interesting access control characteristics have not yet been implemented. The relationship of this classification to conventional classifications by type (for instance,role-based access control or mandatory access control) and mechanism (for instance,access control list or capabilities)is briefly discussed. Several implementations of access control are classi .ed by their values for these properties.The roles of access control in formulation and operation of distributed systems are discussed.

The Grid is rapidly emerging as the dominant paradigm for wide area distributed application systems. As a result, there is a need for modeling and analyzing the characteristics and requirements of Grid systems and programming models. This work adopts the well-established body of models for distributed computing systems, which are based upon carefully stated assumptions or axioms, as a basis for defining and characterizing Grids and their programming models and systems. The requirements of programming Grid applications and the resulting requirements on the underlying virtual organizations and virtual machines are investigated. The assumptions underlying some of the programming models and systems currently used for Grid applications are identified and their validity in Grid environments is discussed. A more in-depth analysis of two programming systems, the Imperial College E-Science Networked Infrastructure (ICENI) and Accord, using the proposed definitions' structure is presented.

Internet and Grid-based systems, whether their purpose is computation, collaboration and information sharing, are all instances of systems based on application of fundamental principles of distributed computing. This paper reports on a graduate seminar on Internet and Grid computing which focuses on the fundamental principles and concepts of distributed computation which underlie Internet and Grid systems, both software and applications. The course takes a broad definition of Internet, and Grid computing, ranging across high performance computation to peer-to-peer file sharing systems. The focus is on identification and analysis of the concepts and principles underlying Grid computing and how they are realized and applied in systems ranging from Globus to Freenet with Web services in between. In summary, the course is a "what is it" rather than a "how to do it". Each participant does a project concerning an Internet or Grid computing subject and presents it to the class.

This paper defines and describes a fully distributed implementation of Google's highly effective pagerank algorithm, for "peer to peer" (P2P) systems. The implementation is based on chaotic (asynchronous) iterative solution of linear systems. The P2P implementation also enables incremental computation of pageranks as new documents are entered into or deleted from the network. Incremental update enables continuously accurate pageranks whereas the currently centralized web crawl and computation over Internet documents requires several days. This suggests possible applicability of the distributed algorithm to pagerank computations as a replacement for the centralized Web crawler based implementation for Internet documents. A complete solution of the distributed pagerank computation for an in-place network converges rapidly (1% accuracy in 10 iterations) for large systems although the time for iteration may be long. The incremental computation resulting from addition of a single document converges extremely rapidly, typically requiring update path lengths of fewer than 15 nodes even for large networks and very accurate solutions. This implementation of pagerank provides a uniform ranking scheme for documents in P2P systems, and its integration with P2P keyword search provides one solution to the network traffic problems engendered by return of document hits. In basic P2P keyword search, all the document hits must be returned to the querying node causing large network traffic. An incremental keyword search algorithm for P2P keyword search where document hits are sorted by pagerank, and incrementally returned to the querying node is proposed and evaluated. Integration of this algorithm into P2P keyword search can produce dramatic benefit both in terms of effectiveness for users and decrease in network traffic. The incremental search algorithm provided approximately a ten-fold reduction in network traffic for two-word and three-word querying.

This paper presents an approach to integration of model checking into component-based development of software systems. This approach assists in development of highly reliable component-based software systems and reduces the complexity of verifying these systems by utilizing their compositional structures. Temporal properties of a software component are specified, verified, and packaged with the component. Selection of a component for reuse considers not only its functionality but also its temporal properties. When a component is composed from other components, a property of the component is verified on an abstraction of the component. The abstraction is constructed from environment assumptions of the component and verified properties of its sub-components. A general component model that enables component verification is defined. Component verification is discussed in the context of the instantiation of the general component model on an Asynchronous Interleaving Message-passing computation model. This approach has been applied to improve reliability of instances of TinyOS, a component-based run-time system for networked sensors. A case study on TinyOS is included, which illustrates the applicability of this approach, the detection of a bug, and the reduction in model checking complexity.

The paper presents an approach to model checking software system designs specified in xUML (http://www.kc.com/html/xuml.html), an executable subset of UML. This approach is enabled by the execution semantics of xUML and is based on automatic translation from xUML to S/R, the input language of the COSPAN model checker (R.H. Hardin et al., 1996). Model transformations are applied to reduce the state space of the resulting S/R model that is to be verified by COSPAN. An xUML level logic for specifying properties to be checked is defined. Automated support is provided for translating properties specified in the logic to S/R representations and mapping error traces generated by COSPAN to xUML representations.

The POEMS project is creating an environment for end-to-end performance modeling of complex parallel and distributed systems, spanning the domains of application software, runtime and operating system software, and hardware architecture. Toward this end, the POEMS framework supports composition of component models from these different domains into an end-to-end system model. This composition can be specified using a generalized graph model of a parallel system, together with interface specifications that carry information about component behaviors and evaluation methods. The POEMS Specification Language compiler will generate an end-to-end system model automatically from such a specification. The components of the target system may be modeled using different modeling paradigms and at various levels of detail. Therefore, evaluation of a POEMS end-to-end system model may require a variety of evaluation tools including specialized equation solvers, queuing network solvers, and discrete event simulators. A single application representation based on static and dynamic task graphs serves as a common workload representation for all these modeling approaches. Sophisticated parallelizing compiler techniques allow this representation to be generated automatically for a given parallel program. POEMS includes a library of predefined analytical and simulation component models of the different domains and a knowledge base that describes performance properties of widely used algorithms. The paper provides an overview of the POEMS methodology and illustrates several of its key components. The modeling capabilities are demonstrated by predicting the performance of alternative configurations of Sweep3D, a benchmark for evaluating wavefront application technologies and high-performance, parallel architectures.

This paper presents the design, development and application of a computational infrastructure to support the implementation of parallel adaptive algorithms for the solution of sets of partial differential equations. The infrastructure is separated into multiple layers of abstraction. This paper is primarily concerned with the two lowest layersof this infrastructure: a layer which defines and implements dynamic distributed arrays (DDA), and a layer in which several dynamic data and programming abstractions are implemented in terms of the DDAs. The currently implemented abstractions are those needed for formulation of hierarchical adaptive finite difference methods, hp-adaptive finite element methods, and fast multipole method for solution of linear systems. Implementation of sample applications based on each of these methods are described and implementation issues and performance measurements are presented.

The I/O bottleneck in parallel computer systems has recently begun receiving increasing interest. Most attention has focused on improving the performance of I/O devices using fairly low level parallelism in techniques such as disk striping and interleaving. Widely applicable solutions, however, will require an integrated approach which addresses the problem at multiple system levels, including applications, systems software, and architecture. We propose that within the context of such an integrated approach, scheduling parallel I/O operations will become increasingly attractive and can potentially provide substantial performance benefits. We describe a simple I/O scheduling problem and present approximate algorithms for its solution. The costs of using these algorithms in terms of execution time, and the benefits in terms of reduced time to complete a batch of I/O operations, are compared with the situations in which no scheduling is used, and in which an optimal scheduling algorithm is used. The comparison is performed both theoretically and experimentally. We have found that, in exchange for a small execution time overhead, the approximate scheduling algorithms can provide substantial improvements in I/O completion times.

This paper describes the first results from research on the compilation of constraint systems into task level parallel programs in a procedural language. This is the only research of which we are aware which attempts to generate efficient parallel programs for numerical computation from constraint systems. Computations are expressed as constraint systems. A dependence graph is derived from the constraint system and a set of input variables. The dependence graph, which exploits the parallelism in the constraints, is mapped to the language CODE, which represents parallel computation structures as generalized dependence graphs. Finally, parallel C programs are generated. To extract parallel programs of appropriate granularity, the following features are included. (i) modularity, (ii) operations over structured types as primitives, (iii) sequential C functions. A prototype of the compiler has been implemented. The domain of matrix computations is targeted for applications. Initial results are very encouraging.

Decomposition abstraction is the process of organizing and specifying decomposition strategies for the exploitation of parallelism available in an application. In this paper we develop and evaluate declarative primitives for rule-based programs that expand opportunities for parallel execution. These primitives make explicit, implicit relations among the data and similarly among the rules. The semantics of the primitives are presented in a general object-based framework such that they may be applied to most rule-based programming languages. We show how the additional information provided by the decomposition primitives can be incorporated into a semantic-based dependency analysis technique. The resulting analysis reveals parallelism at compile time that is very difficult, if not impossible, to discover by traditional syntactic analysis techniques. Simulation results demonstrate scalable and broadly available parallelism.

We propose a new approach for the parallel execution of production system programs. This approach embodies methods of decomposition abstraction using declarative mechanisms. Application semantics can then be exploited to achieve a much higher degree of concurrency. We present the underlying object-based framework of production systems and discuss the ensuing semantic-based dependency analysis technique. In particular, we define a new notion of functional dependency to characterize associative relationships among data objects, which can be used to determine concurrently executable rules.

We describe a purely declarative method for introducing modularity into forward-chaining, rule-based languages and its embodiment in the Venus rule language. The method is enforced by the syntax of the language and includes the ability to parameterize the rule groups. Drawing from two of three Venus applications developed to date, we illustrate how this form of modularity contributes directly to the resolution of certain software engineering problems associated with rule languages.>

Events are occurence instance of actions. The thesis of this paper is that the use of "actions", instead of events, greatly simplifies the problem of concurrent debugging.

No abstract available.

The problem of resource management for many processor architectures can be viewed as the problem of simultaneously updating data structures that hold system state. An approach in which the possibility of using structures with weakened specifications is examined, is presented. Specifically, data structures that weaken the specification of a priority queue, permitting it to be updated simultaneously by multiple processes are introduced. Two structures, the concurrent heap and the software banyan are proposed, along with their associated algorithms for update. The algorithms are shown to possess attractive properties of simultaneous update and throughput. The results of simulation and actual implementations show that such data structures can improve the execution times of parallel algorithms quite significantly. These structures are proposed as possible basic building blocks for implementation of resource allocation in operating systems.>

Rule-based expert systems are increasingly used to monitor and control the operations of complex real-time systems which require intensive knowledge-decision processing and human expertise. These embedded AI systems must respond to events in the rapidly changing external environment so that the results of the expert system's computation in each monitor-respond cycle are valid in safely operating the real-time system. Determining how fast an expert system can respond under all possible situations is a difficult problem. We have developed an efficient analysis methodology for a large class of rule-based EQL programs to determine whether a program in this class has bounded response time. In particular, we have identified several sets of primitive behavioral constraint assertions: an EQL program which satisfies all constraints in one of these sets of assertions is guaranteed to have bounded response time. Here, we enhance the applicability of our analysis technique by introducing a facility with which the rule-based programmer can specify application-specific knowledge that is too difficult to be mechanically detected in the new language Estella in order to determine the performance of an even wider range of programs. We also describe efficient algorithms for implementing the analysis tools.>

CODE 2.0 is a graphical parallel programming system that targets the three goals of ease of use, portability, and production of efficient parallel code. Ease of use is provided by an integrated graphical/textual interface, a powerful dynamic model of parallel computation, and an integrated concept of program component reuse. Portability is approached by the declarative expression of synchronization and communication operators at a high level of abstraction in a manner which cleanly separates overall computation structure from the primitive sequential computations that make up a program. Execution efficiency is approached through a systematic class hierarchy that supports hierarchical translation refinement including special case recognition. This paper reports results obtained through experimental use of a prototype implementation of the CODE 2.0 system.

A key point in rapid system prototyping is to be able to incorporate into the design and development process specification of hardware and software systems in a more-or-less uniform framework. This paper presents a representation basis for parallel computation structures which covers both hardware and software systems, which is declarative and in which specification of components and structures is well separated. The top level and most abstract specification of the representation basis is: (a) All parallel computation structures can be represented as an extended form of directed graphs called data/control flow graphs (DCGs) with appropriate semantics chosen for the nodes and the arcs. The nodes are transformational components and the arcs are communication components. (b) All executions of parallel computation structures can be described as traversals of these graphs by appropriately defined transactions. (c) There exist straightforward algorithms for translations between this and other representations of parallel computation systems such as equational or production rule programs or finite state machines.>

Reports on the initial experimental evaluation of ROPE (reusability-oriented parallel programming environment), a software component reuse system. ROPE helps the designer find and understand components by using a new classification method called structured relational classification. ROPE is part of a development environment for parallel programs which uses a declarative/hierarchical graphical programming interface. This interface allows use of components with different levels of abstraction, ranging from design units to actual code modules. ROPE supports reuse of all the component types defined in the development environment. Programs developed with the aid of ROPE were found to have error rates far less than those developed without ROPE.>

The goals for the Computation Oriented Display Environment (CODE) are to provide a representation power sufficient for facile expression of a wide class of parallel algorithms while at the same time permitting compilation to reasonably efficient programs on a wide spectrum of parallel execution environments and to provide a hierarchical approach to development of parallel programs. CODE is based on a formally specified model of parallel computation which covers most conventional MIMD models of parallel computation. The model is formulated at a higher level of abstraction than conventional MIMD shared-name-space and partitioned-name-space models of parallel computation. The conceptual foundation of CODE, in particular basing the language on an abstract model of parallel computation, has led to two significant capabilities which had not been anticipated: a calculus of composition which may be exploitable for automated or semiautomated program construction and a natural basis for highly effective component reuse.>

A vertically partitioned structure for the design and implementation of object-oriented systems is proposed, and their performance is demonstrated. It is shown that the application-independent portion of the execution overheads in object-oriented systems can be less than the application-independent overheads in conventionally organized systems built on layered structures. Vertical partitioning implements objects through extended type managers. Two key design concepts result in performance improvement: object semantics can be used in the state management functions of an object type and atomicity is maintained at the type manager boundaries providing efficient recovery points. The performance evaluation is based on a case study of a simple but nontrivial distributed real-time system application.>

The authors evaluate and compare the performance of two concurrency control protocols for distributed databases with multiversioned entities, assuming that each transaction incrementally declares its access set from the successive parts of the preordered entities. The first protocol is called protocol proposed (PP). The second is a variant of the protocol proposed by D.P. Reed (1978), here called RP1. Performance results for these protocols are collected using simulations. Key performance issues of PP are studied and relative performance of PP and RP1 is compared. Extra memory requirement is the most important cost for PP, while the cost associated with abortion of transactions are most important for RP1. For slow communication networks, at all workloads except some range of low workloads, PP performs better than RP1. For fast networks, between low to very high workloads RP1 performs better for a range of parameters. At extremely high workloads, both perform poorly, but the higher memory requirement of PP is more tolerable than the high abortion rate of RP1. A protocol similar to PP is proposed that permits universioned entities and so does not have extra memory cost and has the advantages of PP.>

This paper presents a protocol for improving concurrency and preserving consistency in databases with multi-versioned entities: the database could be either centralized or distributed and may or may not have data replication. In the proposed protocol entities are assigned an order and each transaction accesses entities in this order, with possibly skipping entities that need not be accessed: the out-of-order accesses are permitted at an additional costs. Also, each transaction carries with it, as it moves along the pre-ordered entities, the state information about all preceding transactions which must execute logically before this transaction at all succeeding entities to ensure serializability of transactions. At each entity, a transaction executes logically after all the transactions in the state carried to the entity by the transaction.

article Free Access Share on Dynamic, distributed resource configuration on SW-banyans Authors: John Feo Departments of Computer Sciences and Computer and Electrical Engineering, The University of Texas at Austin, Austin, Texas Departments of Computer Sciences and Computer and Electrical Engineering, The University of Texas at Austin, Austin, TexasView Profile , Roy Jenevein Departments of Computer Sciences and Computer and Electrical Engineering, The University of Texas at Austin, Austin, Texas Departments of Computer Sciences and Computer and Electrical Engineering, The University of Texas at Austin, Austin, TexasView Profile , J. C. Browne Departments of Computer Sciences and Computer and Electrical Engineering, The University of Texas at Austin, Austin, Texas Departments of Computer Sciences and Computer and Electrical Engineering, The University of Texas at Austin, Austin, TexasView Profile Authors Info & Claims ACM SIGARCH Computer Architecture NewsVolume 13Issue 3June 1985 pp 268–275https://doi.org/10.1145/327070.327233Published:01 June 1985Publication History 0citation156DownloadsMetricsTotal Citations0Total Downloads156Last 12 Months7Last 6 weeks4 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

This paper proposes a model or paradigm for the development of parallel algorithms, gives an example of the proposed paradigm, and displays algorithms developed by application of the technique. The algorithm for the merge of two ordered lists developed through application of this technique is thought to be original. The paradigm proposed is to create composite unit operations which combine data movement between data structures with a conventional operation such as compare or add. The composite operation constructed for this study is based upon partitioning the data elements into two linear lists. Exchange of data between adjacent elements in each list are then combined with compares and adds to complete the composite operations. This composite operation can be implemented on at least the following computational architectures.

The problems of resource allocation, configuration and reconfiguration and network control must be solved before reconfigurable array computers can be effectively utilized. The interconnection networks proposed for these systems vary so that there has been no common or optimal solution proposed to these problems. This paper defines and describes the objectives, design, implementation and use of a network controller for a reconfigurable array computer, the Texas Reconfigurable Array Computer (TRAC). The objectives for the network controller are defined by management of the system state, the requirements of the operating system for functionality and the interface the network presents to the operating system. These objectives may be expected to have at least some commonality across most reconfigurable network architectures. The structure of the network controller given herein may offer guidance for development of controllers for other reconfigurable network architectures.

This paper presents an algorithm for the formation of configurations connecting processors to memory and I/O devices on rectangular SW banyan networks with equivalent processor resources as the base nodes and equivalent memory and I/O resources as the apex nodes. Given a set of resource configuration requests, the algorithm always finds a partition of the network that meets the requests in space and time complexity linear with respect to the number of resources in the network.

Real-time systems and systems to interface human work environments will dominate the growth of computer applications over the next decade. These systems must execute their functions with the time-liness and responsiveness required in these environments. The design, development and testing of such systems must guarantee performance as well as functionality and reliability. There is not yet in place a technology to support this requirement for engineering of performance. The research and development community in performance has focused primarily on analysis and deduction rather than the performance arena. This talk will define and discuss the tasks of engineering performance into software systems and describe the recent progress towards this goal.

This paper proposes the use of virtual machine architectures as a means of modeling and analyzing networks and distributed computing systems. The requirements for such modeling and analysis are explored and defined along with an illustrative study of an X.25 link-level protocol performance under normal execution conditions. The virtualizable architecture used in this work is the Data General Nova 3/D.

We outline herein an approach to evolutionary database systems design and evolutionary database design which is intended to lower the total costs of maintaining, developing and executing application programs against a database. The premise is that it should be possible to have an evolutionary database system which executes efficiently while providing explicit support for changes in application usage. The key concepts are: hierarchical layering of a database specification, inclusion of static/dynamic characteristics in specification of the database, and a hybrid compile/interpret system for the execution phase of the data management system itself.

This paper defines and determines a graph model of a computer system in a form applicable to system performance analysis. The power of this modeling technique with respect to comprehensibility, accuracy of representation and ease of validation and modification is demonstrated by application to modeling of the UT-2 operating system for the CDC 6000 series computer system. This multiprocessor-multi-programmed operating system with its high degree of parallelism provides an excellent test for the utility and range of application of graph models in performance evaluation. A programmed representation of the kernel monitor is used. All other system processes are represented in graph form and are input data to the simulator. A generally applicable technique for extracting graph representations of processes are represented in graph form and are input data to the simulator. A generally applicable technique for extracting graph representations of processes from event trace data is described and applied to the event trace generated by the UT-2 operating system. The technique is both complete and general and may be profitably applied for either partial or complete models of any type of complex computer system process where data or techniques for automated graph construction are available or can he applied.

Data integrity control is a significant function in a large data base system. A rollback/restart/recovery (R/R/R) capability is one of the two principal components of a data integrity control system. R/R/R is the capability, on the detection of an invalid data state at time t, to rollback the data system to a valid state known to exist at time to and then restore it to a state of validity at time t via a recovery process. The design and application of R/R/R systems has received very little attention. Chandy [1] has recently reviewed previous work.

Rollback and recovery (RR) is a method of enchancing the reliability of file or data base systems. At certain points in time, called checkpoints, a copy of the data or files is made on tape (or other storage devices). A chronological record is kept of all transactions which modify the data stored by the system; this record is called the audit trail. When an error is detected, the copy of the files or data made at the most recent checkpoint is loaded, and all transactions on the audit trail since this check point are reprocessed in chronological sequence, thus recovering from the error. This paper presents models and techniques which aid in determining optimal times for checkpoints.

This paper presents model studies of some integrated feedback-driven scheduling systems for a multiprogrammed computer system.

This paper investigates some of the effects of varying the number of central processing units (CPU's) available to a multiprogramming system both when parallel processing of a single task (multitasking) is allowed and is not allowed. The variables investigated are those that would be expected to control the CPU queue length distribution and include the degree of multiprogramming, CPU service discipline, CPU service distribution, the degree of cooperation between processors engaged in multitasking, and the ratio of CPU to I/O service capacity. The computer systems are modeled by queueing networks. Analytic results are displayed in many cases with supplementation by numeric and simulation solutions when convenient or necessary. It is demonstrated that under properly defined conditions doubling the number of CPU's in a system can more than double throughput. The effectiveness of multitasking in improving throughput is found to be fairly small if the degree of multiprogramming ranges from modest to high.