Estruturas computacionais para reconstrução de imagem em tomografia

Abstract

O trabalho descrito nesta tese centra-se na investigação de uma estrutura computacional paralela, de tipo MIMD, para reconstrução de imagem em tomografia de transmissão de raios-X e tomografia de emissão simples. O principal objectivo a atingir foi a obtenção de bons desempenhos a baixo preço de maneira a que se torne possível uma redução importante nos custos da parte computacional. Embora diversos métodos de reconstrução sejam estudados, uma atenção especial e devotada ao algoritmo das retroprojecções filtradas, tendo para o efeito sido desenvolvida uma “package” de simulação, já que se pretendeu basear nele a solução a apresentar. As propriedades de paralelismo no tempo, inerentes a esta classe de algoritmos, levaram a considerar topologias de processamento de memória distribuída onde se procura estabelecer uma correspondência tão perfeita quanto possível entre as diferentes etapas de cálculo e os diversos nós do sistema. No entanto, a noção de paralelismo no espaço não foi abandonada, tendo-se sempre procurado algoritmos que viabilizassem a transformação de cada etapa de cálculo numa organização passível de decomposição num conjunto de processos, mais ou menos independentes, executados em paralelo. A arquitectura de processamento escolhida pode ser descrita como constituindo um sistema distribuído de memória partilhada em que a sincronização e comunicação entre processos residentes em módulos de processamento distintos se realiza preferencialmente por um esquema de passagem de mensagens, implementado localmente por variáveis partilhadas. Um executivo distribuído de passagem de mensagens foi desenvolvido e instalado em cada um dos módulos de processamento do sistema. O seu elemento principal é um gestor de comunicações, formado por sete processos de sistema que cooperam entre si de modo a fornecer ao utilizador um controlo tão alargado quanto possível sobre a execução das diferentes tarefas. Uma preocupação mantida ao longo de todo o processo foi promover condições que permitissem criar ao programador de aplicações um “interface” simples e eficiente com o ambiente operacional, facilmente incorporável no desenho das suas aplicações distribuídas. Assim, optou-se por construir uma biblioteca de extensão para a linguagem C em que estão disponíveis três classes principais de primitivas: primitivas de comunicação e sincronização entre processos baseadas em mensagens, primitivas de reserva e libertação de espaço em memória comum e primitivas de sincronização para acesso a recursos comuns, definidos pelo utilizador, também em memória comum. Um sistema formado por quatro módulos de processamento e quatro memórias comuns foi construído para avaliar a adequação da arquitectura proposta à reconstrução tomográfica. Os resultados obtidos permitiram verificar um ganho na velocidade de cálculo de cerca de 3 relativamente à versão sequencial. Extrapolações efectuadas permitiram ainda concluir que se o número de módulos de processamento for aumentado, um ganho de quase mais uma ordem de grandeza pode ser conseguido.

This work describes the design of a parallel computing system, MIMD type, suited for image reconstruction in X-ray transmission tomography and single photon emission tomography. The main requirement was to accomplish a good price / performance trade-off so that strong cost reductions might be possible. While several reconstruction methods are examined, special attention is devoted to the filterbackprojection algorithm. A simulation package has been specifically developed, since it was decided to base the solution in it. Time parallelism properties, which are typical of this class of algorithms, have led to contemplate distributed memory topologies where one tries to assign the different computational stages to different system nodes along the information flow. However, the consideration of space parallelism was not put aside. One of the greatest concerns was to look for algorithms which could organize each computational stage in a structure that enabled a parallel implementation through a group of processes run in a more or less independent way. The chosen architecture may be described as constituting a distributed shared memory topology where synchronization and communication among processes residing in different processing nodes is mainly carried out by a message-passing scheme, implemented locally through shared variables. A distributed shared memory executive was developed and installed in each of the system processing nodes. Its main component is the communication manager, a group of seven system processes which cooperate closely in order to present the user with a friendly environment for the, as wide as possible, control of the different tasks under execution. Another concern kept all along the design stage was to create a simple and efficient interface with the operational environment that the application programmer could easily incorporate into his or her distributed applications. Thus, an extension library to the C language was built which offers three main classes of system calls: message-based process communication and synchronization, shared memory space allocation and freeing and common user-defined resources syncronization, also in shared memory. A system with four processing nodes and four common memories was built to assess the suitability of the proposed architecture for tomographic reconstruction. Results obtained show a processing speed gain of about 3, when one compares to the sequential version of the same algorithm run in one of the processing nodes. Extrapolation studies that were carried out also show that if the number of processing nodes is increased, a speed gain of almost an order of magnitude may be achieved.