Fractura de Polígonos Complejos

Abstract

Uno 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.