| Large-scale applications in Science, Engineering can potentially benefit from high performance parallel computing. Many algorithms for various applications have been developed for different parallel architectures of various grain sizes. However, most of these algorithms have been for problems possessing a regular structure. There is a large class of problems where the pattern of data distribution is nonuniform and are called irregular problems. The effective parallel solution of irregular computation poses greater challenges because of the need for facilities for dynamic creation of work and dynamic load balancing.;Memory and synchronization latencies are serious bottlenecks in parallel computing. In the SPMD (Single Program Multiple Data Model), von Neumann style of programming is used and hence irregular computations are hard to program. On the other hand, in fine-grain multithreading models, the program is divided into many small threads and the threads interleaved to achieve maximum parallelism. Communication and synchronization latencies are hidden by overlapping communication with computation by means of threads. Hence, multithreading is considered an appropriate paradigm for irregular applications.;The scope of this thesis is to study the effectiveness of fine-grain multithreaded parallel programming for irregular problems with the focus on algorithmic, design, implementational and performance and theoretical analysis issues. The problems considered for our study are from three different disciplines: Graph Theory, Unstructured Meshes and Image Processing, each having certain unique characteristics and therefore, each algorithm has to be designed according to the features the problem dictates.;In the Graph Theory category, we have developed multithreaded algorithms for the single-source shortest path problem. We have devised a multithreaded approach for the automatic load balancing of adaptive finite element meshes in the unstructured grid category. In the image processing category we have designed algorithms for the Fast Fourier Transform (FFT) and the Wavelet Transform.;The algorithms are implemented on the EARTH (Efficient Architecture for Running THreads) multithreaded architecture. We demonstrate through our results the effectiveness of the multithreading paradigm for performing fine-grain irregular computations. |
