Co-Exploration of NLA Kernels and Specification of Compute Elements in Distributed Memory CGRAs

Coarse Grained Reconfigurable Architectures (CGRA) are emerging as embedded application processing units in computing platforms for Exascale computing. Such CGRAs are distributed memory multi- core compute elements on a chip that communicate over a Network-on-chip (NoC). Numerical Linear Algebra (NLA) kernels are key to several high performance computing applications. In this paper we propose a systematic methodology to obtain the specification of Compute Elements (CE) for such CGRAs. We analyze block Matrix Multiplication and block LU Decomposition algorithms in the context of a CGRA, and obtain theoretical bounds on communication requirements, and memory sizes for a CE. Support for high performance custom computations common to NLA kernels are met through custom function units (CFUs) in the CEs. We present results to justify the merits of such CFUs.

PLUTO plus : Near-Complete Modeling of Affine Transformations for Parallelism and Locality

Affine transformations have proven to be very powerful for loop restructuring due to their ability to model a very wide range of transformations. A single multi-dimensional affine function can represent a long and complex sequence of simpler transformations. Existing affine transformation frameworks like the Pluto algorithm, that include a cost function for modern multicore architectures where coarse-grained parallelism and locality are crucial, consider only a sub-space of transformations to avoid a combinatorial explosion in finding the transformations. The ensuing practical tradeoffs lead to the exclusion of certain useful transformations, in particular, transformation compositions involving loop reversals and loop skewing by negative factors. In this paper, we propose an approach to address this limitation by modeling a much larger space of affine transformations in conjunction with the Pluto algorithm's cost function. We perform an experimental evaluation of both, the effect on compilation time, and performance of generated codes. The evaluation shows that our new framework, Pluto+, provides no degradation in performance in any of the Polybench benchmarks. For Lattice Boltzmann Method (LBM) codes with periodic boundary conditions, it provides a mean speedup of 1.33x over Pluto. We also show that Pluto+ does not increase compile times significantly. Experimental results on Polybench show that Pluto+ increases overall polyhedral source-to-source optimization time only by 15%. In cases where it improves execution time significantly, it increased polyhedral optimization time only by 2.04x.

Folding of Protein L with Implications for Collapse in the Denatured State Ensemble

A fundamental question in protein folding is whether the coil to globule collapse transition occurs during the initial stages of folding (burst phase) or simultaneously with the protein folding transition. Single molecule fluorescence resonance energy transfer (FRET) and small-angle X-ray scattering (SAXS) experiments disagree on whether Protein L collapse transition occurs during the burst phase of folding. We study Protein L folding using a coarse-grained model and molecular dynamics simulations. The collapse transition in Protein L is found to be concomitant with the folding transition. In the burst phase of folding, we find that FRET experiments overestimate radius of gyration, R-g, of the protein due to the application of Gaussian polymer chain end-to-end distribution to extract R-g from the FRET efficiency. FRET experiments estimate approximate to 6 angstrom decrease in R-g when the actual decrease is approximate to 3 angstrom on guanidinium chloride denaturant dilution from 7.5 to 1 M, thereby suggesting pronounced compaction in the protein dimensions in the burst phase. The approximate to 3 angstrom decrease is close to the statistical uncertainties of the R-g data measured from SAXS experiments, which suggest no compaction, leading to a disagreement with the FRET experiments. The transition-state ensemble (TSE) structures in Protein L folding are globular and extensive in agreement with the Psi-analysis experiments. The results support the hypothesis that the TSE of single domain proteins depends on protein topology and is not stabilized by local interactions alone.

An extension of the Quasicontinuum Treatment of Multiscale Solid Systems to Nonzero Temperature

Covering the solid lattice with a finite-element mesh produces a coarse-grained system of mesh nodes as pseudoatoms interacting through an effective potential energy that depends implicitly on the thermodynamic state. Use of the pseudoatomic Hamiltonian in a Monte Carlo simulation of the two-dimensional Lennard-Jones crystal yields equilibrium thermomechanical properties (e.g., isotropic stress) in excellent agreement with ``exact'' fully atomistic results.

Multiscale Treatment of Thin-Film Lubrication

A multiscale technique that combines an atomistic description of the interfacial (near) region with a coarse-grained (continuum) description of the far regions of the solid substrates is proposed. The new hybrid technique, which represents an advance over a previously proposed dynamically-constrained hybrid atomistic-coarse-grained treatment (Wu et al.J. Chem. Phys., 120, 6744, 2004), is applied to a two-dimensional model tribological system comprising planar substrates sandwiching a monolayer film. Shear–stress profiles (shear stress versus strain) computed by the new hybrid technique are in excellent agreement with “exact” profiles (i.e. those computed treating the whole system at the atomic scale).

Deformation Twinning In Bulk Nanocrystalline Metals: Experimental Observations

Deformation twins have been observed in nanocrystalline (nc) fcc metals with medium-to-high stacking fault energies such as aluminum, copper, and nickel. These metals in their coarse-grained states rarely deform by twining at room temperature and low strain rates. Several twinning mechanisms have been reported that are unique to nc metals. This paper reviews experimental evidences on deformation twinning and partial dislocation. emissions from grain boundaries, twinning mechanisms, and twins with zero-macro-strain. Factors that affect the twinning propensity and recent analytical models on the critical grain sizes for twinning are also discussed. The current issues on deformation twinning in nanocrystalline metals are listed.

New Deformation Twinning Mechanism Generates Zero Macroscopic Strain In Nanocrystalline Metals

Macroscopic strain was hitherto considered a necessary corollary of deformation twinning in coarse-grained metals. Recently, twinning has been found to be a preeminent deformation mechanism in nanocrystalline face-centered-cubic (fcc) metals with medium-to-high stacking fault energies. Here we report a surprising discovery that the vast majority of deformation twins in nanocrystalline Al, Ni, and Cu, contrary to popular belief, yield zero net macroscopic strain. We propose a new twinning mechanism, random activation of partials, to explain this unusual phenomenon. The random activation of partials mechanism appears to be the most plausible mechanism and may be unique to nanocrystalline fcc metals with implications for their deformation behavior and mechanical properties.

Curie Transition Of Nc Nickel By Mechanical Spectroscopy And Magnetization Study

Mechanical spectroscopy measurement is performed to study the internal friction of nanocrystalline ( NC) nickel with an average grain size of 23 nm from room temperature to 610 K. An internal friction peak is observed at about 550 K, which corresponds to the Curie transition process of the NC nickel according to the result of magnetization test. Moreover, the fact that the Curie temperature of NC nickel is lower than that of coarse-grained nickel is explained by an analytical model based on the weakening of cohesive energy.

Formation of Single and Multiple Deformation Twins in Nanocrystalline fcc Metals

Deformation twins are often observed to meet each other to form multi-fold twins in nanostructured face-centered cubic (fcc) metals.Here we propose two types of mechanism for the nucleation and growth of four different single and multiple twins. These mechanisms provide continuous generation of twinning partials for the growth of the twins after ucleation. A relatively high stress or high strain rate is needed to activate these mechanisms, making them more prevalent in nanocrystalline materials than in their coarse-grained counterparts.Experimental observations that support the proposed mechanisms are presented.

A scheme for multiple sequences alignment optimization-an improvement based on family representative mechanics features

As a basic tool of modern biology, sequence alignment can provide us useful information in fold, function, and active site of protein. For many cases, the increased quality of sequence alignment means a better performance. The motivation of present work is to increase ability of the existing scoring scheme/algorithm by considering residue–residue correlations better. Based on a coarse-grained approach, the hydrophobic force between each pair of residues is written out from protein sequence. It results in the construction of an intramolecular hydrophobic force network that describes the whole residue–residue interactions of each protein molecule, and characterizes protein's biological properties in the hydrophobic aspect. A former work has suggested that such network can characterize the top weighted feature regarding hydrophobicity. Moreover, for each homologous protein of a family, the corresponding network shares some common and representative family characters that eventually govern the conservation of biological properties during protein evolution. In present work, we score such family representative characters of a protein by the deviation of its intramolecular hydrophobic force network from that of background. Such score can assist the existing scoring schemes/algorithms, and boost up the ability of multiple sequences alignment, e.g. achieving a prominent increase (50%) in searching the structurally alike residue segments at a low identity level. As the theoretical basis is different, the present scheme can assist most existing algorithms, and improve their efficiency remarkably.

Dendrites Inhibition in Rechargeable Lithium Metal Batteries

The specific high energy and power capacities of rechargeable lithium metal (Li⁰) batteries are ideally suited to portable devices and are valuable as storage units for intermittent renewable energy sources. Lithium, the lightest and most electropositive metal, would be the optimal anode material for rechargeable batteries if it were not for the fact that such devices fail unexpectedly by short-circuiting via the dendrites that grow across electrodes upon recharging. This phenomenon poses a major safety issue because it triggers a series of adverse events that start with overheating, potentially followed by the thermal decomposition and ultimately the ignition of the organic solvents used in such devices.

In this thesis, we developed experimental platform for monitoring and quantifying the dendrite populations grown in a Li battery prototype upon charging under various conditions. We explored the effects of pulse charging in the kHz range and temperature on dendrite growth, and also on loss capacity into detached “dead” lithium particles.

Simultaneously, we developed a computational framework for understanding the dynamics of dendrite propagation. The coarse-grained Monte Carlo model assisted us in the interpretation of pulsing experiments, whereas MD calculations provided insights into the mechanism of dendrites thermal relaxation. We also developed a computational framework for measuring the dead lithium crystals from the experimental images.

Programming chemical kinetics: engineering dynamic reaction networks with DNA strand displacement

Over the last century, the silicon revolution has enabled us to build faster, smaller and more sophisticated computers. Today, these computers control phones, cars, satellites, assembly lines, and other electromechanical devices. Just as electrical wiring controls electromechanical devices, living organisms employ "chemical wiring" to make decisions about their environment and control physical processes. Currently, the big difference between these two substrates is that while we have the abstractions, design principles, verification and fabrication techniques in place for programming with silicon, we have no comparable understanding or expertise for programming chemistry.

In this thesis we take a small step towards the goal of learning how to systematically engineer prescribed non-equilibrium dynamical behaviors in chemical systems. We use the formalism of chemical reaction networks (CRNs), combined with mass-action kinetics, as our programming language for specifying dynamical behaviors. Leveraging the tools of nucleic acid nanotechnology (introduced in Chapter 1), we employ synthetic DNA molecules as our molecular architecture and toehold-mediated DNA strand displacement as our reaction primitive.

Abstraction, modular design and systematic fabrication can work only with well-understood and quantitatively characterized tools. Therefore, we embark on a detailed study of the "device physics" of DNA strand displacement (Chapter 2). We present a unified view of strand displacement biophysics and kinetics by studying the process at multiple levels of detail, using an intuitive model of a random walk on a 1-dimensional energy landscape, a secondary structure kinetics model with single base-pair steps, and a coarse-grained molecular model that incorporates three-dimensional geometric and steric effects. Further, we experimentally investigate the thermodynamics of three-way branch migration. Our findings are consistent with previously measured or inferred rates for hybridization, fraying, and branch migration, and provide a biophysical explanation of strand displacement kinetics. Our work paves the way for accurate modeling of strand displacement cascades, which would facilitate the simulation and construction of more complex molecular systems.

In Chapters 3 and 4, we identify and overcome the crucial experimental challenges involved in using our general DNA-based technology for engineering dynamical behaviors in the test tube. In this process, we identify important design rules that inform our choice of molecular motifs and our algorithms for designing and verifying DNA sequences for our molecular implementation. We also develop flexible molecular strategies for "tuning" our reaction rates and stoichiometries in order to compensate for unavoidable non-idealities in the molecular implementation, such as imperfectly synthesized molecules and spurious "leak" pathways that compete with desired pathways.

We successfully implement three distinct autocatalytic reactions, which we then combine into a de novo chemical oscillator. Unlike biological networks, which use sophisticated evolved molecules (like proteins) to realize such behavior, our test tube realization is the first to demonstrate that Watson-Crick base pairing interactions alone suffice for oscillatory dynamics. Since our design pipeline is general and applicable to any CRN, our experimental demonstration of a de novo chemical oscillator could enable the systematic construction of CRNs with other dynamic behaviors.

A fully-nonlocal energy-based formulation and high-performance realization of the quasicontinuum method

The quasicontinuum (QC) method was introduced to coarse-grain crystalline atomic ensembles in order to bridge the scales from individual atoms to the micro- and mesoscales. Though many QC formulations have been proposed with varying characteristics and capabilities, a crucial cornerstone of all QC techniques is the concept of summation rules, which attempt to efficiently approximate the total Hamiltonian of a crystalline atomic ensemble by a weighted sum over a small subset of atoms. In this work we propose a novel, fully-nonlocal, energy-based formulation of the QC method with support for legacy and new summation rules through a general energy-sampling scheme. Our formulation does not conceptually differentiate between atomistic and coarse-grained regions and thus allows for seamless bridging without domain-coupling interfaces. Within this structure, we introduce a new class of summation rules which leverage the affine kinematics of this QC formulation to most accurately integrate thermodynamic quantities of interest. By comparing this new class of summation rules to commonly-employed rules through analysis of energy and spurious force errors, we find that the new rules produce no residual or spurious force artifacts in the large-element limit under arbitrary affine deformation, while allowing us to seamlessly bridge to full atomistics. We verify that the new summation rules exhibit significantly smaller force artifacts and energy approximation errors than all comparable previous summation rules through a comprehensive suite of examples with spatially non-uniform QC discretizations in two and three dimensions. Due to the unique structure of these summation rules, we also use the new formulation to study scenarios with large regions of free surface, a class of problems previously out of reach of the QC method. Lastly, we present the key components of a high-performance, distributed-memory realization of the new method, including a novel algorithm for supporting unparalleled levels of deformation. Overall, this new formulation and implementation allows us to efficiently perform simulations containing an unprecedented number of degrees of freedom with low approximation error.

Implementação de algoritmos genéticos paralelos em uma arquitetura MPSoC.

Essa dissertação apresenta a implementação de um algoritmo genético paralelo utilizando o modelo de granularidade grossa, também conhecido como modelo das ilhas, para sistemas embutidos multiprocessados. Os sistemas embutidos multiprocessados estão tornando-se cada vez mais complexos, pressionados pela demanda por maior poder computacional requerido pelas aplicações, principalmente de multimídia, Internet e comunicações sem fio, que são executadas nesses sistemas. Algumas das referidas aplicações estão começando a utilizar algoritmos genéticos, que podem ser beneficiados pelas vantagens proporcionadas pelo processamento paralelo disponível em sistemas embutidos multiprocessados. No algoritmo genético paralelo do modelo das ilhas, cada processador do sistema embutido é responsável pela evolução de uma população de forma independente dos demais. A fim de acelerar o processo evolutivo, o operador de migração é executado em intervalos definidos para realizar a migração dos melhores indivíduos entre as ilhas. Diferentes topologias lógicas, tais como anel, vizinhança e broadcast, são analisadas na fase de migração de indivíduos. Resultados experimentais são gerados para a otimização de três funções encontradas na literatura.

River Crake (at Bouthrey Bridge) freeze coring report

This is the River Crake (at Bouthrey Bridge) freeze coring report produced by Lancaster University in 1999. This study looks at fine materials in river Crake at Bouthrey Bridge that may have to be considered detrimental to successful salmonid spawning. Following an observed decline in quality of salmonid fisheries at the site an investigation was initiated to assess the extent of ingress of fine sediments into the spawning gravels. Fine sediments from one potential source, upstream riverbanks, are also compared to those isolated from the spawning gravels. The percentage by weight of fine sediments for the six freeze cores, was found to be lower than first expected, given the visual appearance of the reach. However the fines were found to be distributed evenly down the cores with a marked absence of an upper, coarse gravel armour layer. In addition the median grain size (D50) of the six samples was generally low, falling to 6mm for core 5. The low median grain size and the absence of coarse grained upper strata are considered detrimental to the success rate of salmonid spawning.