Abstract multiple specialization and its application to program parallelization.

Program specialization optimizes programs for known valúes of the input. It is often the case that the set of possible input valúes is unknown, or this set is infinite. However, a form of specialization can still be performed in such cases by means of abstract interpretation, specialization then being with respect to abstract valúes (substitutions), rather than concrete ones. We study the múltiple specialization of logic programs based on abstract interpretation. This involves in principie, and based on information from global analysis, generating several versions of a program predicate for different uses of such predicate, optimizing these versions, and, finally, producing a new, "multiply specialized" program. While múltiple specialization has received theoretical attention, little previous evidence exists on its practicality. In this paper we report on the incorporation of múltiple specialization in a parallelizing compiler and quantify its effects. A novel approach to the design and implementation of the specialization system is proposed. The resulting implementation techniques result in identical specializations to those of the best previously proposed techniques but require little or no modification of some existing abstract interpreters. Our results show that, using the proposed techniques, the resulting "abstract múltiple specialization" is indeed a relevant technique in practice. In particular, in the parallelizing compiler application, a good number of run-time tests are eliminated and invariants extracted automatically from loops, resulting generally in lower overheads and in several cases in increased speedups.

Compile-time derivation of variable dependency using abstract interpretation

Traditional schemes for abstract interpretation-based global analysis of logic programs generally focus on obtaining procedure argument mode and type information. Variable sharing information is often given only the attention needed to preserve the correctness of the analysis. However, such sharing information can be very useful. In particular, it can be used for predicting runtime goal independence, which can eliminate costly run-time checks in and-parallel execution. In this paper, a new algorithm for doing abstract interpretation in logic programs is described which concentrates on inferring the dependencies of the terms bound to program variables with increased precisión and at all points in the execution of the program, rather than just at a procedure level. Algorithms are presented for computing abstract entry and success substitutions which extensively keep track of variable aliasing and term dependence information. In addition, a new, abstract domain independent ñxpoint algorithm is presented and described in detail. The algorithms are illustrated with examples. Finally, results from an implementation of the abstract interpreter are presented.

Efficient top-down set-sharing analysis using cliques

Abstract. We study the problem of efficient, scalable set-sharing analysis of logic programs. We use the idea of representing sharing information as a pair of abstract substitutions, one of which is a worst-case sharing representation called a clique set, which was previously proposed for the case of inferring pair-sharing. We use the clique-set representation for (1) inferring actual set-sharing information, and (2) analysis within a top-down framework. In particular, we define the new abstract functions required by standard top-down analyses, both for sharing alone and also for the case of including freeness in addition to sharing. We use cliques both as an alternative representation and as widening, defining several widening operators. Our experimental evaluation supports the conclusión that, for inferring set-sharing, as it was the case for inferring pair-sharing, precisión losses are limited, while useful efficieney gains are obtained. We also derive useful conclusions regarding the interactions between thresholds, precisión, efficieney and cost of widening. At the limit, the clique-set representation allowed analyzing some programs that exceeded memory capacity using classical sharing representations.

Abstract specialization and its application to program parallelization

Program specialization optimizes programs for known valúes of the input. It is often the case that the set of possible input valúes is unknown, or this set is infinite. However, a form of specialization can still be performed in such cases by means of abstract interpretation, specialization then being with respect to abstract valúes (substitutions), rather than concrete ones. This paper reports on the application of abstract múltiple specialization to automatic program parallelization in the &-Prolog compiler. Abstract executability, the main concept underlying abstract specialization, is formalized, the design of the specialization system presented, and a non-trivial example of specialization in automatic parallelization is given.

Independence in constraint logic programs

Studying independence of literals, variables, and substitutions has proven very useful in the context of logic programming (LP). Here we study independence in the broader context of constraint logic programming (CLP). We show that a naive extrapolation of the LP definitions of independence to CLP is unsatisfactory (in fact, wrong) for two reasons. First, because interaction between variables through constraints is more complex than in the case of logic programming. Second, in order to ensure the efUciency of several optimizations not only must independence of the search space be considered, but also an orthogonal issue - "independence of constraint solving." We clarify these issues by proposing various types of search independence and constraint solver independence, and show how they can be combined to allow different independence-related optimizations, from parallelism to intelligent backtracking. Sufficient conditions for independence which can be evaluated "a-priori" at run-time are also proposed. Our results suggest that independence, provided a suitable definition is chosen, is even more useful in CLP than in LP.

Determination of variable dependence information through abstract interpretation

Traditional schemes for abstract interpretation-based global analysis of logic programs generally focus on obtaining procedure argument mode and type information. Variable sharing information is often given only the attention needed to preserve the correctness of the analysis. However, such sharing information can be very useful. In particular, it can be used for predicting run-time goal independence, which can eliminate costly run-time checks in and-parallel execution. In this paper, a new algorithm for doing abstract interpretation in logic programs is described which infers the dependencies of the terms bound to program variables with increased precisión and at all points in the execution of the program, rather than just at a procedure level. Algorithms are presented for computing abstract entry and success substitutions which extensively keep track of variable aliasing and term dependence information. The algorithms are illustrated with examples.

A study of set-sharing analysis via cliques

We study the problem of efñcient, scalable set-sharing analysis of logic programs. We use the idea of representing sharing information as a pair of abstract substitutions, one of which is a worst-case sharing representation called a clique set, which was previously proposed for the case of inferring pair-sharing. We use the clique-set representation for (1) inferring actual set-sharing information, and (2) analysis within a topdown framework. In particular, we define the abstract functions required by standard top-down analyses, both for sharing alone and also for the case of including freeness in addition to sharing. Our experimental evaluation supports the conclusión that, for inferring set-sharing, as it was the case for inferring pair-sharing, precisión losses are limited, while useful efñciency gains are obtained. At the limit, the clique-set representation allowed analyzing some programs that exceeded memory capacity using classical sharing representations.

HKT2;2/1, a K+-permeable transporter identified in a salt tolerant rice cultivar through surveys of natural genetic polymorphism

We have investigated OsHKT2;1 natural variation in a collection of 49 cultivars with different levels of salt tolerance and geographical origins. The effect of identified polymorphism on OsHKT2;1 activity was analysed through heterologous expression of variants in Xenopus oocytes. OsHKT2;1 appeared to be a highly conserved protein with only five possible amino acid substitutions that have no substantial effect on functional properties. Our study, however, also identified a new HKT isoform, No-OsHKT2;2/1 in Nona Bokra, a highly salt-tolerant cultivar. No-OsHKT2;2/1 probably originated from a deletion in chromosome 6, producing a chimeric gene. Its 5¢ region corresponds to that of OsHKT2;2, whose full-length sequence is not present in Nipponbare but has been identified in Pokkali, a salt-tolerant rice cultivar. Its 3¢ region corresponds to that of OsHKT2;1. No-OsHKT2;2/1 is essentially expressed in roots and displays a significant level of expression at high Na+ concentrations, in contrast to OsHKT2;1. Expressed in Xenopus oocytes or in Saccharomyces cerevisiae, No-OsHKT2;2/1 exhibited a strong permeability to Na+ and K+, even at high external Na+ concentrations, like OsHKT2;2, and in contrast to OsHKT2;1. Our results suggest that No-OsHKT2;2/1 can contribute to Nona Bokra salt tolerance by enabling root K+ uptake under saline conditions.

Ionization levels of doped copper indium sulfide chalcopyrites

The electronic structure of modified chalcopyrite CuInS2 has been analyzed from first principles within the density functional theory. The host chalcopyrite has been modified by introducing atomic impurities M at substitutional sites in the lattice host with M = C, Si, Ge, Sn, Ti, V, Cr, Fe, Co, Ni, Rh, and Ir. Both substitutions M for In and M for Cu have been analyzed. The gap and ionization energies are obtained as a function of the M-S displacements. It is interesting for both spintronic and optoelectronic applications because it can provide significant information with respect to the pressure effect and the nonradiative recombination.

Electronic and photon absorber properties of Cr-Doped Cu2ZnSnS4

The Cu2ZnSnS4 (CZTS) semiconductor is a potential photovoltaic material due to its optoelectronic properties. These optoelectronic properties can be potentially improved by the insertion of intermediate states into the energy bandgap. We explore this possibility using Cr as an impurity. We carried out first-principles calculations within the density functional theory analyzing three substitutions: Cu, Sn, or Zn by Cr. In all cases, the Cr introduces a deeper band into the host energy bandgap. Depending on the substitution, this band is full, empty, or partially full. The absorption coefficients in the independent-particle approximation have also been obtained. Comparison between the pure and doped host's absorption coefficients shows that this deeper band opens more photon absorption channels and could therefo:e increase the solar-light absorption with respect to the host.

Electronic, structural, and optical properties of the host and Cr-doped cadmium thioindate

The cadmium thioindate spinel CdIn2S4 semiconductor has potential applications for optoelectronic devices. We present a theoretical study of the structural and optoelectronic properties of the host and of the Cr-doped ternary spinel. For the host spinel, we analyze the direct or indirect character of the energy bandgap, the change of the energy bandgap with the anion displacement parameter and with the site cation distribution, and the optical properties. The main effect of the Cr doping is the creation of an intermediate band within the energy bandgap. The character and the occupation of this band are analyzed for two substitutions: Cr by In and Cr by Cd. This band permits more channels for the photon absorption. The optical properties are obtained and analyzed. The absorption coefficients are decomposed into contributions from the different absorption channels and from the inter-and intra-atomic components.

Electronic properties of doped magnesium thioindate ternary spinel in the normal and in the inverse structure

We present a theoretical study of the structural and electronic properties of the M-doped MgIn2S4 ternary spinel semiconductor with M = V, Cr, and Mn. All substitutions, in the normal and in the inverse structure, are analyzed. Some of these possible substitutions present intermediate-band states in the band gap with a different occupation for a spin component. It increases the possibilities of inter-band transitions and could be interesting for applications in optoelectronic devices. The contribution to, and the electronic configuration of, these intermediate bands for the octahedral and tetrahedral sites is analyzed and discussed. The study of the substitutional energies indicates that these substitutions are favorable. Comparison between the pure and doped hosts absorption coefficients shows that this deeper band opens up more photon absorption channels and could therefore increase the solar-light absorption with respect to the host.

Photovoltaic application of the V, Cr and Mn-doped cadmium thioindate

The CdIn2S4 spinel semiconductor is a potential photovoltaic material due to its energy band gap and absorption properties. These optoelectronic properties can be potentiality improved by the insertion of intermediate states into the energy bandgap. We explore this possibility using M = Cr, V and Mn as an impurity. We analyze with first-principles almost all substitutions of the host atoms by M at the octahedral and tetrahedral sites in the normal and inverse spinel structures. In almost all cases, the impurities introduce deeper bands into the host energy bandgap. Depending on the site substitution, these bands are full, empty or partially-full. It increases the number of possible inter-band transitions and the possible applications in optoelectronic devices. The contribution of the impurity states to these bands and the substitutional energies indicate that these impurities are energetically favorable for some sites in the host spinel. The absorption coefficients in the independent-particle approximation show that these deeper bands open additional photon absorption channels. It could therefore increase the solar-light absorption with respect to the host.

Ionization energies of amphoteric-doped Cu2ZnSnS4: Photovoltaic application

The substitution of Cu, Sn or Zn in the quaternary Cu2ZnSnS4 semiconductor by impurities that introduce intermediate states in the energy bandgap could have important implications either for photovoltaic or spintronic applications. This allows more generation–recombination channels than for the host semiconductor. We explore and discuss this possibility by obtaining the ionization energies from total energy first-principles calculations. The three substitutions of Cu, Sn and Zn by impurities are analyzed. From these results we have found that several impurities have an amphoteric behavior with the donor and acceptor energies in the energy bandgap. In order to analyze the role of the ionization energies in both the radiative and non-radiative processes, the host energy bandgap and the acceptor and the donor energies have been obtained as a function of the inward and outward impurity-S displacements. We carried out the analysis for both the natural and synthetic CZTS. The results show that the ionization energies are similar, whereas the energy band gaps are different.

Electronic and optical properties of substitutional V, Cr and Ir impurities in Cu2ZnSnS4

The substitution of cation atoms by V, Cr and It in the natural and synthetic quaternary Cu2ZnSnS4 semiconductor is analyzed using first-principles methods. In most of the substitutions, the electronic structure of these modified CZTS is characterized for intermediate bands with different occupation and position within of the energy band gap. A study of the symmetry and composition of these intermediate bands is carried out for all substitutions. These bands permit additional photon absorption and emission channels depending on their occupation. The optical properties are obtained and analyzed. The absorption coefficients are split into contributions from the different absorption channels and from the inter- and intra-atomic components. The sub bandgap transitions are significant in many cases because the anion states contribute to the valence, conduction and intermediates bands. These properties could therefore be used for novel optoelectronic devices.