Aluno: Marcelo Corrêa de Bittencourt
Orientador: Prof. Dr. André Inácio Reis
Título: Comparing different And-Inverter-Graph Data structures
Linha de Pesquisa: Microeletrônica
Data: 21/03/2018
Hora: 14h45min.
Local: Prédio 43412 AUD-1 (Auditório 1), Instituto de Informática.
Banca Examinadora:
Prof. Dr. Sergio Bampi (UFRGS)
Profª. Drª. Fernanda Gusmão de Lima Kastensmidt (UFRGS)
Prof. Dr. Paulo Francisco Butzen (FURG via videoconferência)
Presidente da Banca: Prof. Dr. André Inácio Reis
Astract: In this work we have implemented and compared four different data structures for And-Inverter-Graphs. Our goal was to verify in practice that the implementation of AIGs as an integer index based unidirectional data structure presents in practice a superior performance compared to other implementations. This has been verified in practice through the results presented in the previous chapter. We believe this superior performance comes from three characteristics. First, using integer indexes instead of pointers results in a more compact data structure, because integers have 32 bits, while pointers have 64 bits. Using integer indexes results then in a more compact data structure. Second, using a data structure that is unidirectional also reduces the memory consumption, as references are stored in a single direction (backwards). Sometimes this requires some creativity, to implement algorithms with unidirectional references. Third, using vectors (instead of pointers) results in more memory locality, as vector elements are stored contiguously.
Keywords: Electronic Design Automation, Data Structures, And-Inverter-Graphs