Lectures de tesis doctorals
Anunci del darrer pas cap al doctorat: la lectura.
Logic Synthesis Techniques for High-Speed Circuits.
Doctorand: David Bañeres Besora
Director: Jordi Cortadella Fortuny i Mike Kishinevsky
Resum: La complexitat està augmentant considerablement en el disseny de nous sistemes electrònics en tecnologies DSM (deep sub-micron). La sÃntesi de nous circuits requereix cada vegada tècniques més elaborades per complir amb les especificacions del disseny i per ser utilitzables en el disseny de circuits de grans dimensions. Una de les fases en el disseny d'un circuit VLSI és la sÃntesis lògica. Aquesta tesi descriu diversos mètodes en aquesta fase per complir amb un dels principals objectius dintre del disseny: optimitzar la velocitat dels circuits.
En aquesta tesi es pretén diverses contribucions. Primer, un "solver" de relacions Booleanes. Una relació Booleana és capaç de capturar més flexibilitat que tècniques basades en "don't cares".
La segona contribució és un nou algorisme per partir un circuit en un conjunt de clústers basats en el concepte de dominadors. Quan els algorismes d'optimització s'apliquen en aquests clústers, la partició generada ofereix millors possibilitats per una reestructuració del circuit de cara a optimitzar la velocitat del mateix comparat amb altres tècniques de partició basades en "mincut".També es presenta un nou mètode de descomposició multi nivell basat en el "solver" de relacions Booleanes. L'objectiu és una descomposició orientada a millorar la velocitat del circuit. Les funcions es descomposen utilitzant una petita llibreria de portes lògiques per millorar el rendiment (velocitat) del circuit.
Finalment, es descriu una nova tècnica per millorar les interconnexions tenint en compte el "layout" del circuit. Aquesta tècnica combina duplicació de portes i inserció de buffers amb "placement" incremental. Aquest mètode, que és molt semblant al principi de "Engineering Change Order" (ECO), millora de forma incremental el disseny del circuit realitzant petites modificacions damunt del "placement" actual.
Dia: 19 de febrer del 2008
Hora: 11:00h
Lloc: Sala del Llac del Rectorat. Campus Nord. Edifici R.
Doctorand: Jean Pierre Charalambos
Resum: Amb l'objectiu de realitzar una eficient visualització interactiva de models geomètrics, que poden arribar a comprendre diversos milions de polÃgons, és clau reduir substancialment la quantitat de dades processades. Els mètodes LOD ("level-of-detail") permeten efectuar una agressiva reducció de les dades enviades a la GPU, a expenses de sacrificar una mica la qualitat visual. Particularment, els mètodes HLOD ("hierarchical level-of-detail") en els quals es precomputen LODs als diferents nivells d'una jerarquia espaial donada, ha demostrat ser l'enfoc més adient per a la visualització interactiva d'aquest tipus de models. Ademés de suportar en forma directa algoritmes "out-of-core" els mètodes HLODs permeten efectuar una cà rrega òptima de les dades entre la CPU i la GPU.
Seguint el mateix objectiu, un enfoc ortogonal a l'anterior és "occlusion culling" (descart per oclusió). Respecte a un punt de vista donat es busca descartar de forma eficient les parts invisibles de l'escena i visualitzar només les seves parts visibles. Els mètodes més recents que pertanyen a aquesta categoria fan servir HOQs ("hardware occlusion queries").
Els efectes relatius a HLODs i occlusion culling poden combinar-se de forma efectiva. Primer, es possible descartar aquells nodes de la jerarquia que resultin invisibles. Segon, per als nodes visibles, es possible fer servir els resultats dels HOQs com part integral de la condició de refinament de la jerarquia: d'acord amb el grau de visibilitat d'un node donat, i tenint en compte un fenomen de la percepció anomenat "visual masking", és factible determinar quan no hi hauria un guany apreciable en l'aparença final de la imatge obtinguda si el node fos refinat posteriorment. En aquest cas, HOQs permeten reduir encara de forma més agressiva el total de primitives visualitzades. Tot i aixÃ, degut a la latència present entre el moment d'iniciar el HOQ i la disponibilitat del seu resultat, l'ús directe de HOQs en les condicions de refinament resulten sent una font d'estancament de la CPU, allò que a la seva vegada redundaria en un apreciable desaprofitament de la GPU.
En aquesta tesi presentem una innovadora mètrica que fa servir informació de visibilitat (determinada a partir de HOQs) com part integrant de la condició de refinament d'un model HLOD. També contribuïm amb un innovador algoritme per travessar la jerarquia del HLOD que permet treure el mà xim profit d'aquesta mètrica. A partir d'una rutina bà sica de predicció de la condició de refinament del HLOSD, l'algoritme minimitza l'estancament de la CPU i permet obtenir, aixÃ, un millor aprofitament de la GPU.
Les principals propietats exposades en el nostre enfoc combinat són:
- Millor rendiment amb la mateixa qualitat visual: mitjançant el nostre sistema es possible visualitzar un menor nombre de primitives (no per això la tècnica de occlusion culling deixa de ser conservativa) amb una pèrdua mÃnima en la qualitat visual del model.
- Generalitat: la nostra mètrica suporta qualsevol tipus de HLOD.
- Ús integral dels resultats obtinguts en HOQs: la nostra mètrica aprofita de forma completa la informació obtinguda mitjançant HOQs.
- Aprofitament integral de la coherència espai-temporal inherent a les representacions jerà rquiques.
- Implementació directa.
Dia: 20 de febrer del 2008
Hora: 10:00h
Lloc: Aula Biblioteca.
Secció ETSEIB de LSI. ESTSEIB
Avda. Diagonal 647, 8è
08028 Barcelona.
Evolutionary Algorithms and de Novo Peptide Design
Doctorand: Ignasi Belda.
Directors: Drs. Ernest Giralt i Fransesc Xavier Llorà .
Tutoria: Dra. Angela Nebot.
Resum: La present tesi adreça el problema biomèdic del disseny automà tic de lligands peptÃdics que s'uneixen a dianes terapèutiques proteiques. Per assolir aquest objectiu, utilitzem algorismes evolutius que fan evolucionar poblacions de pèptids. Els algorismes evolutius comencen la cerca amb un conjunt de pèptids aleatoris−individus−i, aleshores, aplicant les regles evolutives−supervivència del més fort, transmissió dels carà cters genotÃpics als descendents, etc−van explorant l'espai de cerca de manera implÃcitament paral•lela. La funció de fitness que determina el grau d'adaptació al medi de cada individu−és a dir, la funció a optimitzar−és l'energia lliure d'interacció entre el pèptid sent explorat i la proteïna diana. Aquesta energia s'obté a través de simulacions de docking pèptid-proteïna.
En la present tesi s'estudien diferents implementacions dels algorismes evolutius i diverses extensions que poden incrementar llur potència de cà lcul en certs escenaris, com els algorismes evolutius paral•lels, algorismes evolutius multimodals, tècniques d'herència de fitness, o evolució d'individus de mida variable. Finalment, la metodologia desenvolupada−ENPDA (Evolutionary de Novo Peptide Design Algorithm)−és aplicada al disseny de pèptids que puguen reconèixer importants dianes terapèutiques, com la proteïna p53, la prolil oligopeptidasa, la ADN girasa, el MHC H-2Kb, i un model de fibril•les ß amiloide (1-42).
Entre les extensions dels algorismes evolutius desenvolupades i provades cal mencionar, la paral•lelització a dos nivells realitzada sobre els algorismes evolutius, la qual aporta una escalabilitat quasi lineal; els algorismes evolutius multimodals, els que dirigeixen la cerca cap a un espai divers des del punt de vista molecular; les tècniques d'herència de fitness, que, teòricament, s'espera que aporten una gran acceleració al procés evolutiu, però no ha estat pas aixà en ENPDA, degut a les hipòtesis exposades més endavant; i l'evolució d'individus de mida variable, la qual prepara als algorismes evolutius a adaptar, dinà micament, la mida dels pèptids dissenyats a la mida de la zona de la proteïna en que va a unir-se el pèptid.
D'altra banda, en aquesta tesi també es desenvolupa una tecnologia de mineria de dades per poder extreure nou coneixement de manera automà tica de bases de dades biomèdiques. La metodologia és aplicada i validada en dos conjunts de dades completament diferents: lligands peptÃdics i la base de dades de toxicologia de l'empresa AstraZeneca. En aquest procés d'extracció de coneixement s'utilitzen també algorismes evolutius per tal de fer evolucionar un conjunt de regles que descriuen i generalitzen els patrons observats. A continuació, s'apliquen una sèrie d'operacions computacionals per tal de detectar i filtrar les condicions significatives. I finalment, el conjunt de condicions significatives és interpretat i és el que conforma el cos del nou coneixement extret de manera automà tica.
Dia: 10 de març
Hora: 11h
Lloc: Aula Fèlix Serratosa
Parc CientÃfic de Barcelona.
C/ Josep Samitier, 1-5
8028 Barcelona.
