Tesis Doctoral
DOI
https://doi.org/10.11606/T.3.2016.tde-25082016-074902
Documento
Autor
Nombre completo
Renato Seiji Tavares
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2016
Director
Tribunal
Tsuzuki, Marcos de Sales Guerra (Presidente)
Rubio, Wilfredo Montealegre
Henriques, Marco Aurélio Amaral
Lima, Raúl González
Silva, Olavo Luppi
Título en portugués
Reconstrução de imagens por tomografia por impedância elétrica utilizando recozimento simulado massivamente paralelizado.
Palabras clave en portugués
Algoritmos paralelos
CUDA
GPU
Otimização estocástica
Problemas inversos
Processamento de imagens
Recozimento simulado
Tomografia
Resumen en portugués
A tomografia por impedância elétrica é uma modalidade de imageamento médico recente, com diversas vantagens sobre as demais modalidades já consolidadas. O recozimento simulado é um algoritmo que apresentada qualidade de solução, mesmo com a utilização de uma regularização simples e sem informação a priori. Entretanto, existe a necessidade de reduzir o tempo de processamento. Este trabalho avança nessa direção, com a apresentação de um método de reconstrução que utiliza o recozimento simulado e paralelização massiva em GPU. A paralelização das operações matriciais em GPU é explicada, com uma estratégia de agendamento de threads que permite a paralelização efetiva de algoritmos, até então, considerados não paralelizáveis. Técnicas para sua aceleração são discutidas, como a heurística de fora para dentro. É proposta uma nova representação de matrizes esparsas voltada para as características da arquitetura CUDA, visando um melhor acesso à memória global do dispositivo e melhor utilização das threads. Esta nova representação de matriz mostrou-se vantajosa em relação aos formatos mais utilizados. Em seguida, a paralelização massiva do problema inverso da TIE, utilizando recozimento simulado, é estudada, com uma proposta de abordagem híbrida com paralelização tanto em CPU quanto GPU. Os resultados obtidos para a paralelização do problema inverso são superiores aos do problema direto. A GPU satura em aproximadamente 7.000 nós, a partir do qual o ganho em desempenho é de aproximadamente 5 vezes. A utilização de GPUs é viável para a reconstrução de imagens de tomografia por impedância elétrica.
Título en inglés
Image reconstruction through electrical impedance tomography using massively parallelized simulated annealing.
Palabras clave en inglés
CUDA
Electrical impedance tomography
GPU
Parallelized algorithms
Simulated annealing
Resumen en inglés
Electrical impedance tomography is a new medical imaging modality with remarkable advatanges over other stablished modalities. Simulated annealing is an algorithm that renders quality solutions despite the use of simple regularization methods and the absence of a priori information. However, it remains the need to reduce its processing time. This work takes a step in this direction, presenting a method for the reconstruction of EIT images using simulated annealing and GPU parallelization. The parallelization of matrix operations in GPU is explained, with a thread scheduling strategy that allows the effective parallelization of not-yet effectively parallelized algorithms. There are strategies for improving its performance, such as the presented outside-in heuristic. It is proposed a new sparse matrix representation focused on the CUDA architecture characteristics, with improved global memory access patterns and thread efficiency. This new matrix representation showed several advantages over the most common formats. The massive parallelization of the TIE's inverse problem using simulated annealing is studied, with a proposed hybrid approach that uses parallelization in both CPU and GPU. Results showed that the performance gain for the inverse problem is higher than the one obtained for the forward problem. The GPU device saturates with meshes of size of approximately 7,000 nodes, with a performance gain around 5 times faster than serial implementations. GPU parallelization may be used for the reconstruction of electrical impedance tomography images.
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Fecha de Publicación
2016-08-26
ADVERTENCIA: El material descrito abajo se refiere a los trabajos derivados de esta tesis o disertación. El contenido de estos documentos es responsabilidad del autor de la tesis o disertación.
- Tavares, R. S., Martins, T. C., and Tsuzuki, M. S. G. Electrical Impedance Tomography Reconstruction Through Simulated Annealing using a New Outside-in Heuristic and GPU Parallelization [doi:10.1088/1742-6596/407/1/012015]. Journal of Physics. Conference Series [online], 2012, vol. 407, p. 1-15.
- Tavares, R. S., Martins, T. C., and Tsuzuki, M. S. G. Simulated Annealing with Adaptive Neighborhood: a Case Study in Off-Line Robot Path Planning [doi:10.1016/j.eswa.2010.08.084]. Expert Systems with Applications [online], 2011, vol. 38, p. 2951-2965.
- Martins, T. C., et al. Comparison of Different Techniques for Electrical Impedance Tomography Reconstruction Using Simulated Annealing and GPU Parallelization [doi:10.2316/P.2013.791-041]. In The 10th IASTED International Conference on Biomedical Engineering, Innsbruck, 2013. Proceedings of the 10th IASTED International Conference on Biomedical Engineering.Alberta : IASTED, 2013.
- Tavares, R. S., Martins, T. C., and Tsuzuki, M. S. G. Electrical Impedance Tomography Image Reconstruction through Simulated Annealing using GPU Parallelization and Outside-In Heuristic. In 3rd International Conference on Engineering Optimization, Rio de Janeiro, 2012. Proceedings of the 3rd International Conference on Engineering Optimization.Rio de Janeiro, 2012.
- Tavares, R. S., Martins, T. C., and Tsuzuki, M. S. G. Electrical Impedance Tomography Reconstruction Through Simulated Annealing with a New Outside-In Heuristic. In 1st Latin American Conference on Bioimpedance, Joinville, 2012. Proceedings of the 1st Latin American Conference on Bioimpedance.Joinville : UDESC, 2012.