Global transformations for legacy parallel applications via structural analysis and rewriting

Performance and scalability optimization of large HPC applications is currently a labor-intensive, manual process with very low productivity. Major difficulties come from the disaggregated environment for HPC application development: the compiler is only involved in local decisions (core or multithreaded domain), while a library-based, communication-oriented programming model realizes whole-machine parallelism. Realizing any major global change in such a disaggregated environment is very difficult and involves changing large portions of the source code. We present semi-automated techniques, based on structural analysis and rewriting, for performing global transformations on an HPC application source code. We present two case studies using the Self-Consistent Field (SCF) standalone benchmark as well as the Coupled Cluster (CCSD) module (2.9 million lines of Fortran code), a key module of the NWChem computational chemistry application. We demonstrate how structural rewriting techniques can be used to automate transformations that affect multiple sections of the application’s source code. We show that the transformations can be applied in a systematic fashion across the source code bases with minimal manual effort. These transformations improve the scalability of the SCF benchmark by more than two orders of magnitude and the performance of the full CCSD module by a factor of four.     

Syntactic compression codes at the zero entropy point

Syntactic compression codes compress the tree, which is the syntax of a binary source message. The ones considered here originate from image processing. The syntactic trees usedhave a constant valency and their binary labels distinguish whether the source substring derived from a node is completely zero or not. We compress them simply by deleting some redundant subtrees.

These codes fall into a theoretically new class of codes which is wider than the classical ones. They are here studied in the neighborhood of a zero of the binary entropy function. There, their behavior is close to that of an infinite run length encoding and the optimum valency is three. Finally, we open a problem, related with automata theory, which perhaps could provide a further link between Information Theory and Algorithmic Information Theory.     

Counterexamples in infinitary rewriting with non-fully-extended rules

We show counterexamples exist to confluence modulo hypercollapsing subterms, fair normalisation, and the normal form property in orthogonal infinitary higher-order rewriting with non-fully-extended rules. This sets these systems apart from both fully-extended and finite systems, where no such counterexamples are possible.     

Undecidable properties of flat term rewrite systems

Reachability, joinability and confluence properties are known to be undecidable for flat term rewrite systems (TRS). We give shorter and conceptually simpler proofs of these results. We also prove undecidability of weak normalization and unique normalization properties for flat TRS. The first author was supported by Spanish Ministry of Education and Science by the FORMALISM project (TIN2007-66523) and by the LOGICTOOLS-2 project (TIN2007-68093-C02-01). The second author was supported by Spanish Ministry of Education and Science by the FORMALISM project (TIN2007-66523).     

Practical ultra‐reliability for abstract data types

The Term Redundancy Method (TRM) is a novel approach for obtaining ultra‐reliable programs through specification‐based testing. Current specification‐based testing schemes need a prohibitively large number of test cases for estimating ultra‐reliability. They assume the availability of an accurate program‐usage distribution prior to testing, and they assume the availability of a test oracle. This paper shows how to obtain ultra‐reliable abstract data types specified with equational specifications, with a practical number of test cases, without an accurate usage distribution, and without the usual test oracle. The effectiveness of the TRM in failure detection and recovery is demonstrated on the aircraft collision avoidance system TCAS. Copyright © 2007 John Wiley & Sons, Ltd.     

Simulation of the oregonator model by using deterministic ARMS

We propose a deterministic method for simulating chemical reactions, deterministic abstract rewriting system on multisets (DARMS), which is based on the concept of mass action low. The feasibility and utility of DARMS are demonstrated by applying it to the oregonator, which is a well-known model of the Belousov-Zhabotinskii (BZ) reaction. This work was presented in part at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008     

Hard combinators

Hard Interaction systems can be presented as graph relabeling with a handshake mechanism that provide local synchronization. We present a particular one with only four symbols and seven rules that can be used to simulate all the other hard interaction systems.