Show simple item record

Professor Guidedc.contributor.advisorRivara Zúñiga, María Ceciliaes_CL
Authordc.contributor.authorJorquera Ahumada, Gastón Ignacio es_CL
Staff editordc.contributor.editorFacultad de Ciencias Físicas y Matemáticases_CL
Staff editordc.contributor.editorDepartamento de Ciencias de la Computaciónes_CL
Associate professordc.contributor.otherTanter, Éric
Associate professordc.contributor.otherGodoy Vega, Eduardo 
Admission datedc.date.accessioned2012-09-12T18:18:06Z
Available datedc.date.available2012-09-12T18:18:06Z
Publication datedc.date.issued2010es_CL
Identifierdc.identifier.urihttp://repositorio.uchile.cl/handle/2250/103912
Abstractdc.description.abstractUno de los procesos del diseño de circuitos integrados digitales es la preparación de la información de las máscaras, o MDP por sus siglas en inglés (Mask Data Preparation). La preparación de máscaras recibe el diseño de un circuito y lo convierte en una secuencia de instrucciones que son leídas por una máquina generadora de máscaras. Este proceso es realizado por una serie de algoritmos, ordenados en forma de pipeline, donde la salida de uno es la entrada del siguiente. Uno de los primeros algoritmos ejecutado es el llamado Windfrac, encargado de particionar, o fracturar, polígonos complejos en conjuntos de rectángulos y trapecios horizontales (cuyos lados paralelos son horizontales). Esta fractura inicial tiene gran importancia ya que, al reducir los distintos posibles polígonos de entrada a sólo rectángulos y trapecios horizontales, los algoritmos ejecutados después pueden ser simplificados e incluso tomar menos tiempo. En esta memoria se estudia y documenta el funcionamiento del algoritmo Windfrac, y se reimplementa de una forma más legible y mantenible. El estudio del algoritmo, el cual fue el tema central y lo que más tiempo ocupó, contempla la revisión de ciertos conceptos geométricos y de geometría computacional necesarios para la total comprensión de éste. Debido a que sólo existe un paper que explica un algoritmo parecido, toda la información acerca de cómo funciona Windfrac debió ser deducido a partir del código fuente mismo, cuya implementación era muy difícil de leer. El funcionamiento fue descifrado, principalmente, utilizando casos de prueba y depuradores para ir viendo, paso a paso, lo que el algoritmo hacía dado un polígono. Una vez entendido el funcionamiento completo de Windfrac se reimplementó teniendo en cuenta legibilidad, mantenibilidad y ciertos detalles para mejorar la calidad de los resultados. La legibilidad y mantenibilidad se lograron con una implementación modular, es decir, utilizando estructuras de datos más especializadas y separando funcionalidades en archivos y funciones. La mejora de la calidad se logró escribiendo código para manejar esos casos particulares. Finalmente, se realiza una discusión acerca del tema en estudio y sobre posibles mejoras que pueden ser llevadas a cabo en el futuro, las cuales podrían tener un gran impacto en el desempeño de la aplicación completa. Y, se concluye que el algoritmo fue satisfactoriamente comprendido y que su reimplementación soluciona los problemas de la implementación antigua.
Lenguagedc.language.isoeses_CL
Publisherdc.publisherUniversidad de Chilees_CL
Publisherdc.publisherCyberDocses_CL
Type of licensedc.rightsJorquera Ahumada, Gastón Ignacioes_CL
Keywordsdc.subjectComputaciónes_CL
Keywordsdc.subjectCircuitos integrados digitaleses_CL
Keywordsdc.subjectAlgoritmos computacionaleses_CL
Keywordsdc.subjectPolígonoses_CL
Keywordsdc.subjectAlgoritmos Windfraces_CL
Keywordsdc.subjectComputación geométricaes_CL
Keywordsdc.subjectFractura de polígonoses_CL
Títulodc.titleFractura de Polígonos Complejoses_CL
Document typedc.typeTesises_CL


Files in this item

Icon

This item appears in the following Collection(s)

Show simple item record