PhD Thesis

 

PhD Candidate: David Bañeres Besora.

Advisor: Jordi Cortadella Fortuny and Mike Kishinevsky.

Summary: Complexity in the design of electronic systems is significantly increasin in DSM technologies. Synthesis requires more powerful techniques to meet the specification constraints and capable to run in afforable time in the larger designs. One of the phases in VLSI design is logic synthesis. This thesis introduces several methods in this phase to meet one of the primary objectives in circuit design: timing optimization.

Several contributions are presented. First, a solver of Boolean relations has been developed. A Boolean relation is able to capture more flexibility than conventional approaches based on don't cares. this work received the best paper award in the design Automation Conference (DAC'04).

The second contribution is a new partitioning algorithm based on the concept of vertex dominator. When optimization algorithms are applied on these clusters, this partition affers more possibilities for restructuring towards delay minimization compared to other techniques based on min-cut.

A multi-level decomposition approach is also defined using the solver of Boolean relations: a timing-driven n-way decomposition. functions are decomposed to improve the performance (speed) using a small library of multi-input gates.

Finally, an integrated approach for layout-aware interconnect optimization is presented. This technique combines gate duplication and buffer insertion in the same framework with incremental placement. Similar to the principle of the Engineering Change Order (ECO), the circuit is incrementally improved by performing small modifications using fanout optimization techniques on top of the current placement.

Date: February the 19th, 2008

Time: 11:00h

Place: Sala del llac del Rectorat. Campus Nord. Edifici R.

PhD Candidate: Jean Pierre Charalambos.

Advisor: Dr. Eduardo Romero and Dr. Michael Wimmer.

Summary: In order to achieve interactive rendering of complex models comprising several millions of polygons, the amount of processed data has to be substantially reduced. Level-of-detail (LOD) methods allow the amount of data sent to the GPU to be aggressively reduced at the expences of sacrificing image quality. Hierarchical level-of-detail (HLOD) methods have proved particulary capable of interactive visualisation of huge data sets by precomputing levels-of-detail at different levels of a spatial hierarchy. HLODs support out-of-core algorithms in straightforward way and allow an optimal balance between CPU and GPU load during rendering.

Occlusion culling represents an orthogonal approach for reducing the amount of rendered primitives. Occlusion culling methods aim to quickly cull the invisible part of the model and render only its visible part. Most recent methods use hardware occlusion queries (HOQs) to achieve this task.

The effects of HLODs and occlusion culling can be successfully combined. Firstly, nodes which are completely invisible can be culled. Secondly, HOQ results can be used for visible nodes when refining an HLOD model; according to the degree of visibility of a node and the visual masking perceptual phenomenon, then it could be determined taht there would be no gain in the final appearance of the image obtained if the node were further refined. In the latter case, HOQs allow more agressive culling of the HLOD hierarchy, further reducing the amount of rendered primitives. However, due to the latency between issuing an HOQ and the availability of its result, the direct use of HOQs for refinement criteria cause CPU stalls and GPU starvation.

This thesis introduces a novel error metric, taking visisbility information (gathered from HOQs) as an integral part of refining an HLOD model, this being the first approach within this context to the best of our knowledge. A novel traversal algorithm for HLOD refinement is also presented for taking full advantage of the introduced HOQ-based error metric. The algorithm minimises CPU stalls and GPU starvation by predicting HLOD refinement conditions using spatio-temporal coherence of visibility.

Some properties of the combined approach presented here involve improved performance having the same visual quality (with our occlusion culling technique still remained conservative). Our error metric supports both polygon-based and point-based HLODs, ensuring full use of HOQ results (our error metrics take full advantage of the information gathered in HOQs). Our traversal algorithm makes full use of the spatial and temporal coherency inherent in hierarchical representations. Our approach can be straightforwardly implemented.

Date: February the 20th, 2008

Time: 10:00h

Place: Aula Biblioteca

           Secció ETSEIB de LSI. ESTSEIB

           Avda. Diagonal 647, 8è

           08028 Barcelona.

PhD Candidate: Ignasi Belda.

Advisors: Drs. Ernest Giralt and Fransesc Xavier Llorà.

Tutor: Dra. Angela Nebot.

Summary: The present thesis addresses the specific biomedical problem of the automated design of peptide ligands that bind therapeutic protein targets. To achieve this, we use evolutionary algorithms that evolve peptide populations. Evolutionary algorithms start the search with random peptides−individuals−, and then, by applying evolutionary rules−survival of fitness, genotypic inheritance, etc. −explore the space in an implicitly parallel manner. The fitness function that determines the fitness of each individual−in other words, the function to be optimized−is the free energy of binding between the peptide ligand being evaluated and the target protein. This energy is obtained through peptide-protein docking simulations.

In this thesis I study several implementations of evolutionary algorithms and some extensions that amplify evolutionary computational capacities, such as parallel evolutionary algorithms, multimodal evolutionary algorithms, fitness inheritance techniques, and variable length individuals evolution. Finally, the methodology−ENPDA (Evolutionary de Novo Peptide Design Algorithm)−is applied to the design of peptides that can recognize biomedical important targets, such as, the proteins p53, prolyl oligopeptidase, DNA gyrase, and MHC H-2Kb, as well as a model of amyloid-ß (1-42) fibril.

Among the developed and tested extensions of the evolutionary algorithms, there is the two-leveled parallelization performed on the evolutionary algorithms, with an almost linear scalability; the multimodal evolutionary algorithms developed, which lead the evolutionary process towards a molecular diverse search; the fitness inheritance techniques, that, theoretically, are expected to speed up in a great manner the evolutionary process, but it does not happen in ENPDA, due to the hypothesis explained later on; and the variable length individuals evolution, which prepares ENPDA to dynamically adapt peptide size to each protein surface patch.

I also develop a data mining technology which automatically extracts new knowledge from biomedical databases. The methodology is applied and validated in two different data sets: one comprising a group of peptide ligands, and the other, comprising AstraZeneca's hERG toxicology database. In this knowledge extraction process I also use evolutionary algorithms to evolve a set of rules that describe and generalize hidden patterns of the databases. I do this by applying a set of computational operations which detect and filter significant conditions. Finally, this set of significant conditions is interpreted, and the new knowledge is automatically generated thereof.

Date: 10th of March

Time: 11h

Place: Aula Fèlix Serratosa
          Parc Científic de Barcelona
          c/ Josep Samitier, 1-5
          080028 Barcelona.

ilapuente@lsi.upc.edu