Dynamic term size computation in logic programs via program transformation

Knowing the size of the terms to which program variables are bound at run-time in logic programs is required in a class of applications related to program optimization such as, for example, recursion elimination and granularity analysis. Such size is difficult to even approximate at compile time and is thus generally computed at run-time by using (possibly predefined) predicates which traverse the terms involved. We propose a technique based on program transformation which has the potential of performing this computation much more efficiently. The technique is based on finding program procedures which are called before those in which knowledge regarding term sizes is needed and which traverse the terms whose size is to be determined, and transforming such procedures so that they compute term sizes "on the fly". We present a systematic way of determining whether a given program can be transformed in order to compute a given term size at a given program point without additional term traversal. Also, if several such transformations are possible our approach allows finding minimal transformations under certain criteria. We also discuss the advantages and present some applications of our technique.

Deriving a fixpoint computation algorithm for top-down abstract interpretation of logic programs

Bruynooghe described a framework for the top-down abstract interpretation of logic programs. In this framework, abstract interpretation is carried out by constructing an abstract and-or tree in a top-down fashion for a given query and program. Such an abstract interpreter requires fixpoint computation for programs which contain recursive predicates. This paper presents in detail a fixpoint algorithm that has been developed for this purpose and the motivation behind it. We start off by describing a simple-minded algorithm. After pointing out its shortcomings, we present a series of refinements to this algorithm, until we reach the final version. The aim is to give an intuitive grasp and provide justification for the relative complexity of the final algorithm. We also present an informal proof of correctness of the algorithm and some results obtained from an implementation.

Remarks on methods for the computation of boundary-element integrals by co-ordinate transformation

It is well known that the evaluation of the influence matrices in the boundary-element method requires the computation of singular integrals. Quadrature formulae exist which are especially tailored to the specific nature of the singularity, i.e. log(*- x0)9 Ijx- JC0), etc. Clearly the nodes and weights of these formulae vary with the location Xo of the singular point. A drawback of this approach is that a given problem usually includes different types of singularities, and therefore a general-purpose code would have to include many alternative formulae to cater for all possible cases. Recently, several authors1"3 have suggested a type independent alternative technique based on the combination of standard Gaussian rules with non-linear co-ordinate transformations. The transformation approach is particularly appealing in connection with the p.adaptive version, where the location of the collocation points varies at each step of the refinement process. The purpose of this paper is to analyse the technique in eference 3. We show that this technique is asymptotically correct as the number of Gauss points increases. However, the method possesses a 'hidden' source of error that is analysed and can easily be removed.

A review on probabilistic graphical models in evolutionary computation

Thanks to their inherent properties, probabilistic graphical models are one of the prime candidates for machine learning and decision making tasks especially in uncertain domains. Their capabilities, like representation, inference and learning, if used effectively, can greatly help to build intelligent systems that are able to act accordingly in different problem domains. Evolutionary algorithms is one such discipline that has employed probabilistic graphical models to improve the search for optimal solutions in complex problems. This paper shows how probabilistic graphical models have been used in evolutionary algorithms to improve their performance in solving complex problems. Specifically, we give a survey of probabilistic model building-based evolutionary algorithms, called estimation of distribution algorithms, and compare different methods for probabilistic modeling in these algorithms.

An efficient nonlinear transformation for the numerical computation of the singular integrals appearing in the 2-D Boundary Element Method

We discuss several methods, based on coordinate transformations, for the evaluation of singular and quasisingular integrals in the direct Boundary Element Method. An intrinsec error of some of these methods is detected. Two new transformations are suggested which improve on those currently available.

GreenDisc: a HW/SW energy optimization framework in globally distributed computation

In recent future, wireless sensor networks (WSNs) will experience a broad high-scale deployment (millions of nodes in the national area) with multiple information sources per node, and with very specific requirements for signal processing. In parallel, the broad range deployment of WSNs facilitates the definition and execution of ambitious studies, with a large input data set and high computational complexity. These computation resources, very often heterogeneous and driven on-demand, can only be satisfied by high-performance Data Centers (DCs). The high economical and environmental impact of the energy consumption in DCs requires aggressive energy optimization policies. These policies have been already detected but not successfully proposed. In this context, this paper shows the following on-going research lines and obtained results. In the field of WSNs: energy optimization in the processing nodes from different abstraction levels, including reconfigurable application specific architectures, efficient customization of the memory hierarchy, energy-aware management of the wireless interface, and design automation for signal processing applications. In the field of DCs: energy-optimal workload assignment policies in heterogeneous DCs, resource management policies with energy consciousness, and efficient cooling mechanisms that will cooperate in the minimization of the electricity bill of the DCs that process the data provided by the WSNs.

GreenDisc: a HW/SW energy optimization framework in globally distributed computation

In recent future, wireless sensor networks ({WSNs}) will experience a broad high-scale deployment (millions of nodes in the national area) with multiple information sources per node, and with very specific requirements for signal processing. In parallel, the broad range deployment of {WSNs} facilitates the definition and execution of ambitious studies, with a large input data set and high computational complexity. These computation resources, very often heterogeneous and driven on-demand, can only be satisfied by high-performance Data Centers ({DCs}). The high economical and environmental impact of the energy consumption in {DCs} requires aggressive energy optimization policies. These policies have been already detected but not successfully proposed. In this context, this paper shows the following on-going research lines and obtained results. In the field of {WSNs}: energy optimization in the processing nodes from different abstraction levels, including reconfigurable application specific architectures, efficient customization of the memory hierarchy, energy-aware management of the wireless interface, and design automation for signal processing applications. In the field of {DCs}: energy-optimal workload assignment policies in heterogeneous {DCs}, resource management policies with energy consciousness, and efficient cooling mechanisms that will cooperate in the minimization of the electricity bill of the DCs that process the data provided by the WSNs.

Computation of Independent Sensitivities Using Maggi’s Formulation

Computation of Independent Sensitivities Using Maggi’s Formulation

Photon Management Structures for Absorption Enhancement in Intermediate Band Solar Cells and Crystalline Silicon Solar Cells

El objetivo de la tesis es investigar los beneficios que el atrapamiento de la luz mediante fenómenos difractivos puede suponer para las células solares de silicio cristalino y las de banda intermedia. Ambos tipos de células adolecen de una insuficiente absorción de fotones en alguna región del espectro solar. Las células solares de banda intermedia son teóricamente capaces de alcanzar eficiencias mucho mayores que los dispositivos convencionales (con una sola banda energética prohibida), pero los prototipos actuales se resienten de una absorción muy débil de los fotones con energías menores que la banda prohibida. Del mismo modo, las células solares de silicio cristalino absorben débilmente en el infrarrojo cercano debido al carácter indirecto de su banda prohibida. Se ha prestado mucha atención a este problema durante las últimas décadas, de modo que todas las células solares de silicio cristalino comerciales incorporan alguna forma de atrapamiento de luz. Por razones de economía, en la industria se persigue el uso de obleas cada vez más delgadas, con lo que el atrapamiento de la luz adquiere más importancia. Por tanto aumenta el interés en las estructuras difractivas, ya que podrían suponer una mejora sobre el estado del arte. Se comienza desarrollando un método de cálculo con el que simular células solares equipadas con redes de difracción. En este método, la red de difracción se analiza en el ámbito de la óptica física, mediante análisis riguroso con ondas acopladas (rigorous coupled wave analysis), y el sustrato de la célula solar, ópticamente grueso, se analiza en los términos de la óptica geométrica. El método se ha implementado en ordenador y se ha visto que es eficiente y da resultados en buen acuerdo con métodos diferentes descritos por otros autores. Utilizando el formalismo matricial así derivado, se calcula el límite teórico superior para el aumento de la absorción en células solares mediante el uso de redes de difracción. Este límite se compara con el llamado límite lambertiano del atrapamiento de la luz y con el límite absoluto en sustratos gruesos. Se encuentra que las redes biperiódicas (con geometría hexagonal o rectangular) pueden producir un atrapamiento mucho mejor que las redes uniperiódicas. El límite superior depende mucho del periodo de la red. Para periodos grandes, las redes son en teoría capaces de alcanzar el máximo atrapamiento, pero sólo si las eficiencias de difracción tienen una forma peculiar que parece inalcanzable con las herramientas actuales de diseño. Para periodos similares a la longitud de onda de la luz incidente, las redes de difracción pueden proporcionar atrapamiento por debajo del máximo teórico pero por encima del límite Lambertiano, sin imponer requisitos irrealizables a la forma de las eficiencias de difracción y en un margen de longitudes de onda razonablemente amplio. El método de cálculo desarrollado se usa también para diseñar y optimizar redes de difracción para el atrapamiento de la luz en células solares. La red propuesta consiste en un red hexagonal de pozos cilíndricos excavados en la cara posterior del sustrato absorbente de la célula solar. La red se encapsula en una capa dieléctrica y se cubre con un espejo posterior. Se simula esta estructura para una célula solar de silicio y para una de banda intermedia y puntos cuánticos. Numéricamente, se determinan los valores óptimos del periodo de la red y de la profundidad y las dimensiones laterales de los pozos para ambos tipos de células. Los valores se explican utilizando conceptos físicos sencillos, lo que nos permite extraer conclusiones generales que se pueden aplicar a células de otras tecnologías. Las texturas con redes de difracción se fabrican en sustratos de silicio cristalino mediante litografía por nanoimpresión y ataque con iones reactivos. De los cálculos precedentes, se conoce el periodo óptimo de la red que se toma como una constante de diseño. Los sustratos se procesan para obtener estructuras precursoras de células solares sobre las que se realizan medidas ópticas. Las medidas de reflexión en función de la longitud de onda confirman que las redes cuadradas biperiódicas consiguen mejor atrapamiento que las uniperiódicas. Las estructuras fabricadas se simulan con la herramienta de cálculo descrita en los párrafos precedentes y se obtiene un buen acuerdo entre la medida y los resultados de la simulación. Ésta revela que una fracción significativa de los fotones incidentes son absorbidos en el reflector posterior de aluminio, y por tanto desaprovechados, y que este efecto empeora por la rugosidad del espejo. Se desarrolla un método alternativo para crear la capa dieléctrica que consigue que el reflector se deposite sobre una superficie plana, encontrándose que en las muestras preparadas de esta manera la absorción parásita en el espejo es menor. La siguiente tarea descrita en la tesis es el estudio de la absorción de fotones en puntos cuánticos semiconductores. Con la aproximación de masa efectiva, se calculan los niveles de energía de los estados confinados en puntos cuánticos de InAs/GaAs. Se emplea un método de una y de cuatro bandas para el cálculo de la función de onda de electrones y huecos, respectivamente; en el último caso se utiliza un hamiltoniano empírico. La regla de oro de Fermi permite obtener la intensidad de las transiciones ópticas entre los estados confinados. Se investiga el efecto de las dimensiones del punto cuántico en los niveles de energía y la intensidad de las transiciones y se obtiene que, al disminuir la anchura del punto cuántico respecto a su valor en los prototipos actuales, se puede conseguir una transición más intensa entre el nivel intermedio fundamental y la banda de conducción. Tomando como datos de partida los niveles de energía y las intensidades de las transiciones calculados como se ha explicado, se desarrolla un modelo de equilibrio o balance detallado realista para células solares de puntos cuánticos. Con el modelo se calculan las diferentes corrientes debidas a transiciones ópticas entre los numerosos niveles intermedios y las bandas de conducción y de valencia bajo ciertas condiciones. Se distingue de modelos de equilibrio detallado previos, usados para calcular límites de eficiencia, en que se adoptan suposiciones realistas sobre la absorción de fotones para cada transición. Con este modelo se reproducen datos publicados de eficiencias cuánticas experimentales a diferentes temperaturas con un acuerdo muy bueno. Se muestra que el conocido fenómeno del escape térmico de los puntos cuánticos es de naturaleza fotónica; se debe a los fotones térmicos, que inducen transiciones entre los estados excitados que se encuentran escalonados en energía entre el estado intermedio fundamental y la banda de conducción. En el capítulo final, este modelo realista de equilibrio detallado se combina con el método de simulación de redes de difracción para predecir el efecto que tendría incorporar una red de difracción en una célula solar de banda intermedia y puntos cuánticos. Se ha de optimizar cuidadosamente el periodo de la red para equilibrar el aumento de las diferentes transiciones intermedias, que tienen lugar en serie. Debido a que la absorción en los puntos cuánticos es extremadamente débil, se deduce que el atrapamiento de la luz, por sí solo, no es suficiente para conseguir corrientes apreciables a partir de fotones con energía menor que la banda prohibida en las células con puntos cuánticos. Se requiere una combinación del atrapamiento de la luz con un incremento de la densidad de puntos cuánticos. En el límite radiativo y sin atrapamiento de la luz, se necesitaría que el número de puntos cuánticos de una célula solar se multiplicara por 1000 para superar la eficiencia de una célula de referencia con una sola banda prohibida. En cambio, una célula con red de difracción precisaría un incremento del número de puntos en un factor 10 a 100, dependiendo del nivel de la absorción parásita en el reflector posterior. Abstract The purpose of this thesis is to investigate the benefits that diffractive light trapping can offer to quantum dot intermediate band solar cells and crystalline silicon solar cells. Both solar cell technologies suffer from incomplete photon absorption in some part of the solar spectrum. Quantum dot intermediate band solar cells are theoretically capable of achieving much higher efficiencies than conventional single-gap devices. Present prototypes suffer from extremely weak absorption of subbandgap photons in the quantum dots. This problem has received little attention so far, yet it is a serious barrier to the technology approaching its theoretical efficiency limit. Crystalline silicon solar cells absorb weakly in the near infrared due to their indirect bandgap. This problem has received much attention over recent decades, and all commercial crystalline silicon solar cells employ some form of light trapping. With the industry moving toward thinner and thinner wafers, light trapping is becoming of greater importance and diffractive structures may offer an improvement over the state-of-the-art. We begin by constructing a computational method with which to simulate solar cells equipped with diffraction grating textures. The method employs a wave-optical treatment of the diffraction grating, via rigorous coupled wave analysis, with a geometric-optical treatment of the thick solar cell bulk. These are combined using a steady-state matrix formalism. The method has been implemented computationally, and is found to be efficient and to give results in good agreement with alternative methods from other authors. The theoretical upper limit to absorption enhancement in solar cells using diffractions gratings is calculated using the matrix formalism derived in the previous task. This limit is compared to the so-called Lambertian limit for light trapping with isotropic scatterers, and to the absolute upper limit to light trapping in bulk absorbers. It is found that bi-periodic gratings (square or hexagonal geometry) are capable of offering much better light trapping than uni-periodic line gratings. The upper limit depends strongly on the grating period. For large periods, diffraction gratings are theoretically able to offer light trapping at the absolute upper limit, but only if the scattering efficiencies have a particular form, which is deemed to be beyond present design capabilities. For periods similar to the incident wavelength, diffraction gratings can offer light trapping below the absolute limit but above the Lambertian limit without placing unrealistic demands on the exact form of the scattering efficiencies. This is possible for a reasonably broad wavelength range. The computational method is used to design and optimise diffraction gratings for light trapping in solar cells. The proposed diffraction grating consists of a hexagonal lattice of cylindrical wells etched into the rear of the bulk solar cell absorber. This is encapsulated in a dielectric buffer layer, and capped with a rear reflector. Simulations are made of this grating profile applied to a crystalline silicon solar cell and to a quantum dot intermediate band solar cell. The grating period, well depth, and lateral well dimensions are optimised numerically for both solar cell types. This yields the optimum parameters to be used in fabrication of grating equipped solar cells. The optimum parameters are explained using simple physical concepts, allowing us to make more general statements that can be applied to other solar cell technologies. Diffraction grating textures are fabricated on crystalline silicon substrates using nano-imprint lithography and reactive ion etching. The optimum grating period from the previous task has been used as a design parameter. The substrates have been processed into solar cell precursors for optical measurements. Reflection spectroscopy measurements confirm that bi-periodic square gratings offer better absorption enhancement than uni-periodic line gratings. The fabricated structures have been simulated with the previously developed computation tool, with good agreement between measurement and simulation results. The simulations reveal that a significant amount of the incident photons are absorbed parasitically in the rear reflector, and that this is exacerbated by the non-planarity of the rear reflector. An alternative method of depositing the dielectric buffer layer was developed, which leaves a planar surface onto which the reflector is deposited. It was found that samples prepared in this way suffered less from parasitic reflector absorption. The next task described in the thesis is the study of photon absorption in semiconductor quantum dots. The bound-state energy levels of in InAs/GaAs quantum dots is calculated using the effective mass approximation. A one- and four- band method is applied to the calculation of electron and hole wavefunctions respectively, with an empirical Hamiltonian being employed in the latter case. The strength of optical transitions between the bound states is calculated using the Fermi golden rule. The effect of the quantum dot dimensions on the energy levels and transition strengths is investigated. It is found that a strong direct transition between the ground intermediate state and the conduction band can be promoted by decreasing the quantum dot width from its value in present prototypes. This has the added benefit of reducing the ladder of excited states between the ground state and the conduction band, which may help to reduce thermal escape of electrons from quantum dots: an undesirable phenomenon from the point of view of the open circuit voltage of an intermediate band solar cell. A realistic detailed balance model is developed for quantum dot solar cells, which uses as input the energy levels and transition strengths calculated in the previous task. The model calculates the transition currents between the many intermediate levels and the valence and conduction bands under a given set of conditions. It is distinct from previous idealised detailed balance models, which are used to calculate limiting efficiencies, since it makes realistic assumptions about photon absorption by each transition. The model is used to reproduce published experimental quantum efficiency results at different temperatures, with quite good agreement. The much-studied phenomenon of thermal escape from quantum dots is found to be photonic; it is due to thermal photons, which induce transitions between the ladder of excited states between the ground intermediate state and the conduction band. In the final chapter, the realistic detailed balance model is combined with the diffraction grating simulation method to predict the effect of incorporating a diffraction grating into a quantum dot intermediate band solar cell. Careful optimisation of the grating period is made to balance the enhancement given to the different intermediate transitions, which occur in series. Due to the extremely weak absorption in the quantum dots, it is found that light trapping alone is not sufficient to achieve high subbandgap currents in quantum dot solar cells. Instead, a combination of light trapping and increased quantum dot density is required. Within the radiative limit, a quantum dot solar cell with no light trapping requires a 1000 fold increase in the number of quantum dots to supersede the efficiency of a single-gap reference cell. A quantum dot solar cell equipped with a diffraction grating requires between a 10 and 100 fold increase in the number of quantum dots, depending on the level of parasitic absorption in the rear reflector.

Virtual-bound, filamentary and layered states in a box-shaped quantum dot of square potential form the exact numerical solution of the effective mass Schrodinger equation

The effective mass Schrodinger equation of a QD of parallelepipedic shape with a square potential well is solved by diagonalizing the exact Hamiltonian matrix developed in a basis of separation-of-variables wavefunctions. The expected below bandgap bound states are found not to differ very much from the former approximate calculations. In addition, the presence of bound states within the conduction band is confirmed. Furthermore, filamentary states bounded in two dimensions and extended in one dimension and layered states with only one dimension bounded, all within the conduction band which are similar to those originated in quantum wires and quantum wells coexist with the ordinary continuum spectrum of plane waves. All these subtleties are absent in spherically shaped quantum dots, often used for modeling.

Computation of nonlinear streaky structures in boundary layer flow

In this work, the Reduced Navier Stokes (RNS) are numerically integrated, and used to calculate nonlinear finite amplitude streaks. These structures are interesting since they can have a stabilizing effect and delay the transition to the turbulent regime. RNS formulation is also used to compute the family of nonlinear intrinsic streaks that emerge from the leading edge in absence of any external perturbation. Finally, this formulation is generalized to include the possibility of having a curved bottom wall

PIC computation of electron current collection to a moving bare tether in the mesothermal condition

In tethered satellite technology, it is important to estimate how many electrons a spacecraft can collect from its ambient plasma by a bare electrodynamic tether. The analysis is however very difficult because of the small but significant Geo-magnetic field and the spacecraft’s relative motion to both ions and electrons. The object of our work is the development of a numerical method, for this purpose. Particle-In-Cell (PIC) method, for the calculation of electron current to a positive bare tether moving at orbital velocity in the ionosphere, i.e. in a flowing magnetized plasma under Maxwellian collisionless conditions. In a PIC code, a number of particles are distributed in phase space and the computational domain has a grid on which Poisson equation is solved for field quantities. The code uses the quasi-neutrality condition to solve for the local potential at points in the plasma which coincide with the computational outside boundary. The quasi-neutrality condition imposes ne - ni on the boundary. The Poisson equation is solved in such a way that the presheath region can be captured in the computation. Results show that the collected current is higher than the Orbital Motion Limit (OML) theory. The OML current is the upper limit of current collection under steady collisionless unmagnetized conditions. In this work, we focus on the flowing effects of plasma as a possible cause of the current enhancement. A deficit electron density due to the flowing effects has been worked and removed by introducing adiabatic electron trapping into our model.

Laminar counterflow parallel-plate heat exchangers: Exact and approximate solutions

Multilayered, counterflow, parallel-plate heat exchangers are analyzed numerically and theoretically. The analysis, carried out for constant property fluids, considers a hydrodynamically developed laminar flow and neglects longitudinal conduction both in the fluid and in the plates. The solution for the temperature field involves eigenfunction expansions that can be solved in terms of Whittaker functions using standard symbolic algebra packages, leading to analytical expressions that provide the eigenvalues numerically. It is seen that the approximate solution obtained by retaining the first two modes in the eigenfunction expansion provides an accurate representation for the temperature away from the entrance regions, specially for long heat exchangers, thereby enabling simplified expressions for the wall and bulk temperatures, local heat-transfer rate, overall heat-transfer coefficient, and outlet bulk temperatures. The agreement between the numerical and theoretical results suggests the possibility of using the analytical solutions presented herein as benchmark problems for computational heat-transfer codes.

Exact solution for the conjugate fluid-fluid problem in the thermal entrance region of laminar counterflow heat exchangers

A generalized Lévêque solution is presented for the conjugate fluid–fluid problem that arises in the thermal entrance region of laminar counterflow heat exchangers. The analysis, carried out for constant property fluids, assumes that the Prandtl and Peclet numbers are both large compared to unity, and neglects axial conduction both in the fluids and in the plate, assumed to be thermally thin. Under these conditions, the thermal entrance region admits an asymptotic self-similar description where the temperature varies as a power ϳ of the axial distance, with the particularity that the self-similarity exponent must be determined as an eigenvalue by solving a transcendental equation arising from the requirement of continuity of heat fluxes at the heat conducting wall. Specifically, the analysis reveals that j depends only on the lumped parameter ƙ = (A2/A1)1/3 (α1/α2)1/3(k2/k1), defined in terms of the ratios of the wall velocity gradients, A, thermal diffusivities, α i, and thermal conductivities,k i, of the fluids entering, 1, and exiting, 2, the heat exchanger. Moreover, it is shown that for large (small) values of K solution reduces to the classical first (second) Lévêque solution. Closed-form analytical expressions for the asymptotic temperature distributions and local heat-transfer rate in the thermal entrance region are given and compared with numerical results in the counterflow parallel-plate configuration, showing very good agreement in all cases.

Novel techniques for automorphism group computation

Graph automorphism (GA) is a classical problem, in which the objective is to compute the automorphism group of an input graph. In this work we propose four novel techniques to speed up algorithms that solve the GA problem by exploring a search tree. They increase the performance of the algorithm by allowing to reduce the depth of the search tree, and by effectively pruning it. We formally prove that a GA algorithm that uses these techniques correctly computes the automorphism group of the input graph. We also describe how the techniques have been incorporated into the GA algorithm conauto, as conauto-2.03, with at most an additive polynomial increase in its asymptotic time complexity. We have experimentally evaluated the impact of each of the above techniques with several graph families. We have observed that each of the techniques by itself significantly reduces the number of processed nodes of the search tree in some subset of graphs, which justifies the use of each of them. Then, when they are applied together, their effect is combined, leading to reductions in the number of processed nodes in most graphs. This is also reflected in a reduction of the running time, which is substantial in some graph families.