No description available.

No description available.

No description available.

No description available.

No description available.

No description available.

Kosaraju [Kosaraju 69] and independently ten years later, Guibas, Kung and Thompson [Guibas 79] devised an algorithm (K-GKT) for solving on an array of processors a class of dynamic programming problems of which general context-free language (CFL) recognition is a member. I introduce an extension to K-GKT which allows parsing as well as recognition. The basic idea of the extension is to add counters to the processors. These act as pointers to other processors. The extended algorithm consists of three phases which I call the recognition phase, the marking phase and the parse output phase. I first consider the case of unambiguous grammars. I show that in that case, the algorithm has O(n2log n) space complexity and a linear time complexity. To obtain these results I rely on a counter implementation that allows the execution in constant time of each of the operations: set to zero, test if zero, increment by 1 and decrement by 1. I provide a proof of correctness of this implementation. I introduce the concept of efficient grammars. One factor in the multiplicative constant hidden behind the O(n2log n) space complexity measure for the algorithm is related to the number of non-terminals in the (unambiguous) grammar used. I say that a grammar is k-efficient if it allows the processors to store not more than k pointer pairs. I call a 1-efficient grammar an efficient grammar. I show that two properties that I call nt-disjunction and rhsdasjunction together with unambiguity are sufficient but not necessary conditions for grammar efficiency. I also show that unambiguity itself is not a necessary condition for efficiency. I then consider the case of ambiguous grammars. I present two methods for outputting multiple parses. Both output each parse in linear time. One method has O(n3log n) space complexity while the other has O(n2log n) space complexity. I then address the issue of problem decomposition. I show how part of my extension can be adapted, using a standard technique, to process inputs that would be too large for an array of some fixed size. I then discuss briefly some issues related to implementation. I report on an actual implementation on the I.C.L. DAP. Finally, I show how another systolic CFL parsing algorithm, by Chang, Ibarra and Palis [Chang 87], can be generalized to output parses in preorder and inorder.

In this thesis, a numerical and theoretical investigation of the Pulsed Pressure Chemical Vapour Deposition (PP-CVD) progress is presented. This process is a novel method for the deposition of thin films of materials from either liquid or gaseous precursors. PP-CVD operates in an unsteady manner whereby timed pulsed of the precursor are injected into a continuously evacuated reactor volume. A non-dimensional parameter indicating the extent of continuum breakdown under strong temporal gradients is developed. Experimental measurements, supplemented by basic continuum simulations, reveal that spatio-temporal breakdown of the continuum condition occurs within the reactor volume. This means that the use of continuum equation based solvers for modelling the flow field is inappropriate. In this thesis, appropriate methods are developed for modelling unsteady non-continuum flows, centred on the particle-based Direct Simulation Monte Carlo (DSMC) method. As a first step, a basic particle tracking method and single processor DSMC code are used to investigate the physical mechanisms for the high precursor conversion efficiency and deposition uniformity observed in experimental reactors. This investigation reveals that at soon after the completion of the PP-CVD injection phase, the precursor particles have an approximately uniform distribution within the reactor volume. The particles then simply diffuse to the substrate during the pump-down phase, during which the rate of diffusion greatly exceeds the rate at which particles can be removed from the reactor. Higher precursor conversion efficiency was found to correlate with smaller size carrier gas molecules and moderate reactor peak pressure. An unsteady sampling routine for a general parallel DSMC method called PDSC, allowing the simulation of time-dependent flow problems in the near continuum range, is then developed in detail. Nearest neighbour collision routines are also implemented and verified for this code. A post-processing procedure called DSMC Rapid Ensemble Averaging Method (DREAM) is developed to improve the statistical scatter in the results while minimising both memory and simulation time. This method builds an ensemble average of repeated runs over small number of sampling intervals prior to the sampling point of interest by restarting the flow using either xi a Maxwellian distribution based on macroscopic properties for near equilibrium flows (DREAM-I) or output instantaneous particle data obtained by the original unsteady sampling of PDSC for strongly non-equilibrium flows (DREAM-II). The method is validated by simulating shock tube flow and the development of simple Couette flow. Unsteady PDSC is found to accurately predict the flow field in both cases with significantly reduced run-times over single processor code and DREAM greatly reduces the statistical scatter in the results while maintaining accurate particle velocity distributions. Verification simulations are conducted involving the interaction of shocks over wedges and a benchmark study against other DSMC code is conducted. The unsteady PDSC routines are then used to simulate the PP-CVD injection phase. These simulations reveal the complex flow phenomena present during this stage. The initial expansion is highly unsteady; however a quasi-steady jet structure forms within the reactor after this initial stage. The simulations give additional evidence that the collapse of the jet at the end of the injection phase results in an approximately uniform distribution of precursor throughout the reactor volume. Advanced modelling methods and the future work required for development of the PP-CVD method are then proposed. These methods will allow all configurations of reactor to be modelled while reducing the computational expense of the simulations.

Magnetic resonance imaging (MRI) is a widely employed imaging modality that allows observation of the interior of human body. Compared to other imaging modalities such as the computed tomography (CT), MRI features a relatively long scan time that gives rise to many potential issues. The advent of parallel MRI, which employs multiple receiver coils, has started a new era in speeding up the scan of MRI by reducing the number of data acquisitions. However, the finally recovered images from under-sampled data sets often suffer degraded image quality. This thesis explores methods that incorporate prior knowledge of the image to be reconstructed to achieve improved image recovery in parallel MRI, following the philosophy that ‘if some prior knowledge of the image to be recovered is known, the image could be recovered better than without’. Specifically, the prior knowledge of image sparsity is utilized. Image sparsity exists in different domains. Image sparsity in the image domain refers to the fact that the imaged object only occupies a portion of the imaging field of view; image sparsity may also exist in a transform domain for which there is a high level of energy concentration in the image transform. The use of both types of sparsity is considered in this thesis. There are three major contributions in this thesis. The first contribution is the development of ‘GUISE’. GUISE employs an adaptive sampling design method that achieves better exploitation of image domain sparsity in parallel MRI. Secondly, the development of ‘PBCS’ and ‘SENSECS’. PBCS achieves better exploitation of transform domain sparsity by incorporating a prior estimate of the image to be recovered. SENSECS is an application of PBCS that achieves better exploitation of transform domain sparsity in parallel MRI. The third contribution is the implementation of GUISE and PBCS in contrast enhanced MR angiography (CE MRA). In their applications in CE MRA, GUISE and PBCS share the common ground of exploiting the high sparsity of the contrast enhanced angiogram. The above developments are assessed in various ways using both simulated and experimental data. The potential extensions of these methods are also suggested.

El objetivo de la tesis es la definición de un modelo de ejecución paralelo, que basado en la representación de un algoritmo paralelo con Redes de Petri, permita a un conjunto flexible de procesadores independientes entre sí, ejecutar el algoritmo en forma asíncrona con altos rendimientos y que el programador tenga capacidad de ajustar los parámetros de ejecución en vista de mejoras de rendimiento. Los fundamentos son claros: se desea contar con una herramienta de ejecución de programas paralelos que permita modelar el algoritmo, y pasar del modelo a la ejecución asíncrona preservando el modelo. Las Redes de Petri son la herramienta básica e indiscutiblemente pertinente para lograr el objetivo. Un desafío es cubrir la brecha o gap existente entre el modelado y una ejecución del programa paralelo de rendimientos aceptables y escalables.Para ello, debe existir una vinculación del modelo con un conjunto de unidades de procesamiento que corran en paralelo.