Exploração de paralelismo na etapa de legalização de circuitos digitais através do uso de estruturas de dados geométricas

Resumo

Após o posicionamento inicial dos elementos de um circuito integrado, estes precisam ser legalizados para considerar regras de fabricação. Algoritmos de legalização devem tratar grandes quantidades de dados, produzindo uma solução determinística, com a menor perturbação possível do posicionamento. Este trabalho propõe o uso da estrutura de dados KD-tree para particionar o circuito viabilizando a legalização em paralelo das partições.