Functional timing analysis of VLSI circuits containing complex gates

The recent advances in CMOS technology have allowed for the fabrication of transistors with submicronic dimensions, making possible the integration of tens of millions devices in a single chip that can be used to build very complex electronic systems. Such increase in complexity of designs has originated a need for more efficient verification tools that could incorporate more appropriate physical and computational models. Timing verification targets at determining whether the timing constraints imposed to the design may be satisfied or not. It can be performed by using circuit simulation or by timing analysis. Although simulation tends to furnish the most accurate estimates, it presents the drawback of being stimuli dependent. Hence, in order to ensure that the critical situation is taken into account, one must exercise all possible input patterns. Obviously, this is not possible to accomplish due to the high complexity of current designs. To circumvent this problem, designers must rely on timing analysis. Timing analysis is an input-independent verification approach that models each combinational block of a circuit as a direct acyclic graph, which is used to estimate the critical delay. First timing analysis tools used only the circuit topology information to estimate circuit delay, thus being referred to as topological timing analyzers. However, such method may result in too pessimistic delay estimates, since the longest paths in the graph may not be able to propagate a transition, that is, may be false. Functional timing analysis, in turn, considers not only circuit topology, but also the temporal and functional relations between circuit elements. Functional timing analysis tools may differ by three aspects: the set of sensitization conditions necessary to declare a path as sensitizable (i.e., the so-called path sensitization criterion), the number of paths simultaneously handled and the method used to determine whether sensitization conditions are satisfiable or not. Currently, the two most efficient approaches test the sensitizability of entire sets of paths at a time: one is based on automatic test pattern generation (ATPG) techniques and the other translates the timing analysis problem into a satisfiability (SAT) problem. Although timing analysis has been exhaustively studied in the last fifteen years, some specific topics have not received the required attention yet. One such topic is the applicability of functional timing analysis to circuits containing complex gates. This is the basic concern of this thesis. In addition, and as a necessary step to settle the scenario, a detailed and systematic study on functional timing analysis is also presented.

Um Estudo de técnicas de aceleração para algoritmos de análise de timing funcional baseados em geração automática de teste

Este trabalho tem como objetivo estudar e avaliar técnicas para a aceleração de algoritmos de análise de timing funcional (FTA - Functional Timing Analysis) baseados em geração automática de testes (ATPG – Automatic Test Generation). Para tanto, são abordados três algoritmos conhecidos : algoritmo-D, o PODEM e o FAN. Após a análise dos algoritmos e o estudo de algumas técnicas de aceleração, é proposto o algoritmo DETA (Delay Enumeration-Based Timing Analysis) que determina o atraso crítico de circuitos que contêm portas complexas. O DETA está definido como um algoritmo baseado em ATPG com sensibilização concorrente de caminhos. Na implementação do algoritmo, foi possível validar o modelo de computação de atrasos para circuitos que contêm portas complexas utilizando a abordagem de macro-expansão implícita. Além disso, alguns resultados parciais demonstram que, para alguns circuitos, o DETA apresenta uma pequena dependência do número de entradas quando comparado com a dependência no procedimento de simulação. Desta forma, é possível evitar uma pesquisa extensa antes de se encontrar o teste e assim, obter sucesso na aplicação de métodos para aceleração do algoritmo.

Comparative and functional genome analysis of fungi for development of the protein production host Trichoderma reesei

Filamentous fungi of the subphylum Pezizomycotina are well known as protein and secondary metabolite producers. Various industries take advantage of these capabilities. However, the molecular biology of yeasts, i.e. Saccharomycotina and especially that of Saccharomyces cerevisiae, the baker's yeast, is much better known. In an effort to explain fungal phenotypes through their genotypes we have compared protein coding gene contents of Pezizomycotina and Saccharomycotina. Only biomass degradation and secondary metabolism related protein families seem to have expanded recently in Pezizomycotina. Of the protein families clearly diverged between Pezizomycotina and Saccharomycotina, those related to mitochondrial functions emerge as the most prominent. However, the primary metabolism as described in S. cerevisiae is largely conserved in all fungi. Apart from the known secondary metabolism, Pezizomycotina have pathways that could link secondary metabolism to primary metabolism and a wealth of undescribed enzymes. Previous studies of individual Pezizomycotina genomes have shown that regardless of the difference in production efficiency and diversity of secreted proteins, the content of the known secretion machinery genes in Pezizomycotina and Saccharomycotina appears very similar. Genome wide analysis of gene products is therefore needed to better understand the efficient secretion of Pezizomycotina. We have developed methods applicable to transcriptome analysis of non-sequenced organisms. TRAC (Transcriptional profiling with the aid of affinity capture) has been previously developed at VTT for fast, focused transcription analysis. We introduce a version of TRAC that allows more powerful signal amplification and multiplexing. We also present computational optimisations of transcriptome analysis of non-sequenced organism and TRAC analysis in general. Trichoderma reesei is one of the most commonly used Pezizomycotina in the protein production industry. In order to understand its secretion system better and find clues for improvement of its industrial performance, we have analysed its transcriptomic response to protein secretion stress conditions. In comparison to S. cerevisiae, the response of T. reesei appears different, but still impacts on the same cellular functions. We also discovered in T. reesei interesting similarities to mammalian protein secretion stress response. Together these findings highlight targets for more detailed studies.

Integrative functional genomics analysis of sustained polyploidy phenotypes in breast cancer cells identifies an oncogenic profile for GINS2

Aneuploidy is among the most obvious differences between normal and cancer cells. However, mechanisms contributing to development and maintenance of aneuploid cell growth are diverse and incompletely understood. Functional genomics analyses have shown that aneuploidy in cancer cells is correlated with diffuse gene expression signatures and that aneuploidy can arise by a variety of mechanisms, including cytokinesis failures, DNA endoreplication and possibly through polyploid intermediate states. Here, we used a novel cell spot microarray technique to identify genes with a loss-of-function effect inducing polyploidy and/or allowing maintenance of polyploid cell growth of breast cancer cells. Integrative genomics profiling of candidate genes highlighted GINS2 as a potential oncogene frequently overexpressed in clinical breast cancers as well as in several other cancer types. Multivariate analysis indicated GINS2 to be an independent prognostic factor for breast cancer outcome (p = 0.001). Suppression of GINS2 expression effectively inhibited breast cancer cell growth and induced polyploidy. In addition, protein level detection of nuclear GINS2 accurately distinguished actively proliferating cancer cells suggesting potential use as an operational biomarker.

An efficient reduction algorithm for computation of interconnect delay variability for statistical timing analysis in clock tree planning

In this paper, we propose a novel and efficient algorithm for modelling sub-65 nm clock interconnect-networks in the presence of process variation. We develop a method for delay analysis of interconnects considering the impact of Gaussian metal process variations. The resistance and capacitance of a distributed RC line are expressed as correlated Gaussian random variables which are then used to compute the standard deviation of delay Probability Distribution Function (PDF) at all nodes in the interconnect network. Main objective is to find delay PDF at a cheaper cost. Convergence of this approach is in probability distribution but not in mean of delay. We validate our approach against SPICE based Monte Carlo simulations while the current method entails significantly lower computational cost.

Implications of program phase behavior on timing analysis

Knowledge about program worst case execution time (WCET) is essential in validating real-time systems and helps in effective scheduling. One popular approach used in industry is to measure execution time of program components on the target architecture and combine them using static analysis of the program. Measurements need to be taken in the least intrusive way in order to avoid affecting accuracy of estimated WCET. Several programs exhibit phase behavior, wherein program dynamic execution is observed to be composed of phases. Each phase being distinct from the other, exhibits homogeneous behavior with respect to cycles per instruction (CPI), data cache misses etc. In this paper, we show that phase behavior has important implications on timing analysis. We make use of the homogeneity of a phase to reduce instrumentation overhead at the same time ensuring that accuracy of WCET is not largely affected. We propose a model for estimating WCET using static worst case instruction counts of individual phases and a function of measured average CPI. We describe a WCET analyzer built on this model which targets two different architectures. The WCET analyzer is observed to give safe estimates for most benchmarks considered in this paper. The tightness of the WCET estimates are observed to be improved for most benchmarks compared to Chronos, a well known static WCET analyzer.

Vibrational spectroscopy and density functional theory analysis of 3-O-caffeoylquinic acid

Density functional theory (DFT) calculations are being performed to investigate the geometric, vibrational, and electronic properties of the chlorogenic acid isomer 3-CQA (1R,3R,4S,5R)-3-{(2E)-3-(3,4-dihydroxyphenyl)prop-2-enoyl]oxy}-1,4, 5-trihydroxycyclohexanecarboxylic acid), a major phenolic compound in coffee. DFT calculations with the 6-311G(d,p) basis set produce very good results. The electrostatic potential mapped onto an isodensity surface has been obtained. A natural bond orbital analysis (NBO) has been performed in order to study intramolecular bonding, interactions among bonds, and delocalization of unpaired electrons. HOMO-LUMO studies give insights into the interaction of the molecule with other species. The calculated HOMO and LUMO energies indicate that a charge transfer occurs within the molecule. (C) 2012 Elsevier B.V. All rights reserved.

Functional metagenomic analysis of the human gut microbiome to identify novel salt tolerance genes

The ability to adapt to and respond to increases in external osmolarity is an important characteristic that enables bacteria to survive and proliferate in different environmental niches. When challenged with increased osmolarity, due to sodium chloride (NaCl) for example, bacteria elicit a phased response; firstly via uptake of potassium (K+), which is known as the primary response. This primary response is followed by the secondary response which is characterised by the synthesis or uptake of compatible solutes (osmoprotectants). The overall osmotic stress response is much broader however, involving many diverse cellular systems and processes. These ancillary mechanisms are arguably more interesting and give a more complete view of the osmotic stress response. The aim of this thesis was to identify novel genetic loci from the human gut microbiota that confer increased tolerance to osmotic stress using a functional metagenomic approach. Functional metagenomics is a powerful tool that enables the identification of novel genes from as yet uncultured bacteria from diverse environments through cloning, heterologous expression and phenotypic identification of a desired trait. Functional metagenomics does not rely on any previous sequence information to known genes and can therefore enable the discovery of completely novel genes and assign functions to new or known genes. Using a functional metagenomic approach, we have assigned a novel function to previously annotated genes; murB, mazG and galE, as well as a putative brp/blh family beta-carotene 15,15’-monooxygenase. Finally, we report the identification of a completely novel salt tolerance determinant with no current known homologues in the databases. Overall the genes identified originate from diverse taxonomic and phylogenetic groups commonly found in the human gastrointestinal (GI) tract, such as Collinsella and Eggerthella, Akkermansia and Bacteroides from the phyla Actinobacteria, Verrucomicrobia and Bacteroidetes, respectively. In addition, a number of the genes appear to have been acquired via lateral gene transfer and/or encoded on a prophage. To our knowledge, this thesis represents the first investigation to identify novel genes from the human gut microbiota involved in the bacterial osmotic stress response.

A Transit Timing Analysis of Mine RISE Light Curves of the Exoplanet System TrES-3

We present nine newly observed transits of TrES-3, taken as part of a transit timing program using the RISE instrument on the Liverpool Telescope. A Markov-Chain Monte Carlo analysis was used to determine the planet star radius ratio and inclination of the system, which were found to be R-p/R-star = 0.1664(-0.0018)(+0.0011) and i = 81.73(-0.04)(+0.13), respectively, consistent with previous results. The central transit times and uncertainties were also calculated, using a residual-permutation algorithm as an independent check on the errors. A re-analysis of eight previously published TrES-3 light curves was conducted to determine the transit times and uncertainties using consistent techniques. Whilst the transit times were not found to be in agreement with a linear ephemeris, giving chi(2) = 35.07 for 15 degrees of freedom, we interpret this to be the result of systematics in the light curves rather than a real transit timing variation. This is because the light curves that show the largest deviation from a constant period either have relatively little out-of-transit coverage or have clear systematics. A new ephemeris was calculated using the transit times and was found to be T-c(0) = 2454632.62610 +/- 0.00006 HJD and P = 1.3061864 +/- 0.0000005 days. The transit times were then used to place upper mass limits as a function of the period ratio of a potential perturbing planet, showing that our data are sufficiently sensitive to have probed sub-Earth mass planets in both interior and exterior 2:1 resonances, assuming that the additional planet is in an initially circular orbit.

A transit timing analysis of seven RISE light curves of the exoplanet system HAT-P-3

We present seven light curves of the exoplanet system HAT-P-3, taken as part of a transit timing programme using the rapid imager to search for exoplanets instrument on the Liverpool Telescope. The light curves are analysed using a Markov chain Monte Carlo algorithm to update the parameters of the system. The inclination is found to be i = 86.75+0.22-0.21°, the planet-star radius ratio to be Rp/R* = 0.1098+0.0010-0.0012 and the stellar radius to be R* = 0.834+0.018-0.026Rsolar, consistent with previous results but with a significant improvement in the precision. Central transit times and uncertainties for each light curve are also determined, and a residual permutation algorithm is used as an independent check on the errors. The transit times are found to be consistent with a linear ephemeris, and a new ephemeris is calculated as Tc(0) = 2454856.70118 +/- 0.00018 HJD and P = 2.899738 +/- 0.000007 d. Model timing residuals are fitted to the measured timing residuals to place upper mass limits for a hypothetical perturbing planet as a function of the period ratio. These show that we have probed for planets with masses as low as 0.33 and 1.81 M? in the interior and exterior 2:1 resonances, respectively, assuming the planets are initially in circular orbits.

ENHANCING MULTISCALE FRACTAL DESCRIPTORS USING FUNCTIONAL DATA ANALYSIS

This work presents a novel approach in order to increase the recognition power of Multiscale Fractal Dimension (MFD) techniques, when applied to image classification. The proposal uses Functional Data Analysis (FDA) with the aim of enhancing the MFD technique precision achieving a more representative descriptors vector, capable of recognizing and characterizing more precisely objects in an image. FDA is applied to signatures extracted by using the Bouligand-Minkowsky MFD technique in the generation of a descriptors vector from them. For the evaluation of the obtained improvement, an experiment using two datasets of objects was carried out. A dataset was used of characters shapes (26 characters of the Latin alphabet) carrying different levels of controlled noise and a dataset of fish images contours. A comparison with the use of the well-known methods of Fourier and wavelets descriptors was performed with the aim of verifying the performance of FDA method. The descriptor vectors were submitted to Linear Discriminant Analysis (LDA) classification method and we compared the correctness rate in the classification process among the descriptors methods. The results demonstrate that FDA overcomes the literature methods (Fourier and wavelets) in the processing of information extracted from the MFD signature. In this way, the proposed method can be considered as an interesting choice for pattern recognition and image classification using fractal analysis.

Functional data analysis approaches for genotype-phenotype association studies from next-generation sequencing

Next-generation DNA sequencing platforms can effectively detect the entire spectrum of genomic variation and is emerging to be a major tool for systematic exploration of the universe of variants and interactions in the entire genome. However, the data produced by next-generation sequencing technologies will suffer from three basic problems: sequence errors, assembly errors, and missing data. Current statistical methods for genetic analysis are well suited for detecting the association of common variants, but are less suitable to rare variants. This raises great challenge for sequence-based genetic studies of complex diseases.^ This research dissertation utilized genome continuum model as a general principle, and stochastic calculus and functional data analysis as tools for developing novel and powerful statistical methods for next generation of association studies of both qualitative and quantitative traits in the context of sequencing data, which finally lead to shifting the paradigm of association analysis from the current locus-by-locus analysis to collectively analyzing genome regions.^ In this project, the functional principal component (FPC) methods coupled with high-dimensional data reduction techniques will be used to develop novel and powerful methods for testing the associations of the entire spectrum of genetic variation within a segment of genome or a gene regardless of whether the variants are common or rare.^ The classical quantitative genetics suffer from high type I error rates and low power for rare variants. To overcome these limitations for resequencing data, this project used functional linear models with scalar response to develop statistics for identifying quantitative trait loci (QTLs) for both common and rare variants. To illustrate their applications, the functional linear models were applied to five quantitative traits in Framingham heart studies. ^ This project proposed a novel concept of gene-gene co-association in which a gene or a genomic region is taken as a unit of association analysis and used stochastic calculus to develop a unified framework for testing the association of multiple genes or genomic regions for both common and rare alleles. The proposed methods were applied to gene-gene co-association analysis of psoriasis in two independent GWAS datasets which led to discovery of networks significantly associated with psoriasis.^