Occam is designed for concurrent programming on a network of transputers. AIlocation and partitioning of the program is specified within the source code, binding the program to a specific network. An altemative approach is proposed which completely separates the source code from hardware considerations. Static allocation is performed as a separate phase and should, ideally, be automatic but at present is manual. Complete hardware abstraction requires that non-local, shared communication be provided for, introducing an efficiency overhead which can be minimised by the allocation. The proposal was implemented on a network of IBM PCs, modelled on a transputer network, and implementation issues are discussed

Parallelism is one of the key components of large scale, high performance computing. Extensive use of parallelism has yielded a tremendous increase in the raw processing speed of high performance systems, but parallel problem solving remains difficult. These difficulties are typically solved by building software tools, such as parallel programming environments. Existing parallel programming environments are general purpose and use a broad paradigm. This thesis illustrates that problem specific environments are more beneficial than general purpose environments. A problem specific environment permits the design of the algorithm, while also facilitating definition of the problem. We developed problem specific environments for a simple and a complex class of problems. The simple class consists of two classic graph problems, namely, all pairs shortest path and connected components. The complex class consists of elliptic partial differential equations solved via domain decomposition. Specific problems were solved with the problem specific environments and the general purpose environment, BUILD, which allows the algorithm to be described with a control flow graph. Comparisons between special purpose environments and general purpose environments show that the special purpose environments allow the user to concentrate on the problem, while general purpose environments force the user to think about mapping the problem to the environment rather than solving the problem in parallel. Therefore, we conclude more effort should be spent on building tools and environments for parallel computing that focus specifically on a particular class of problems. / Master of Science

While many parallel programming languages exist, they rarely address programming languages from the issue of communication (implying expressability, and readability). A new language called Explicit Parallel Programming (EPP), attempts to provide this quality by separating the responsibility for the execution of run time actions from the responsibility for deciding the order in which they occur. The ordering of a parallel algorithm is specified in the new EPP language; run time actions are written in FORTRAN and embedded in the EPP code, from which they are later extracted and given to a FORTRAN compiler for compilation. The separation of order and run time actions is taken to its logical extreme in an attempt to evaluate its benefits and costs in the parallel environment. As part of the evaluation, a compiler and executive were implemented on a Sequent Symmetry 881 shared memory multiprocessor computer. The design decisions and difficulties in implementation are discussed at some length, since certain problems are unique to this approach. In the final evaluation, the EPP project asserts that structured, parallel programming languages require a significant amount of interaction with an over-seeing task in order to provide some basic, desirable functions. It also asserts that the description of run time actions (e.g., expression syntax) need not change from the uniprocessor environment to the multiprocessor environment. / Master of Science

Visualization is gaining popularity in the field of Computer Science, especially in areas such as performance evaluation and program animation. In this thesis, we explore the possibility of using visualization to analyze parallel program dynamics. We have developed a visualization system, Chitra for this purpose. Chitra visualizes program execution sequences collected by monitoring parallel and distributed program execution. It provides multiple views to aid in the analysis. Through analysis of program execution sequences, we develop an empirical model, a hybrid stochastic/deterministic model, that describes parallel program behavior. Chitra provides various clues and capabilities that assist in developing an empirical model to fit the observed program behavior. Developing empirical models helps in predicting and evaluation efficiency of parallel programs. A case study of the Dining philosophers problem, a classic resource sharing problem, applies Chitra to develop empirical models for a range of processes. These models help in evaluating efficiency at a range of parameter values, given observations of a few parameters values. Working with Chitra has strengthened our belief that as parallel and distributed programs become more common, visualization systems will have an important role to play in analyzing these programs. / M.S.

Thesis (PhD) -- Stellenbosch University, 1991. / ENGLISH ABSTRACT: This dissertation investigates the moment method solution of electromagnetic radiation and scattering problems using parallel computers. In particular, electromagnetically large problems with arbitrary geometries are considered. Such problems require a large number of unknowns to obtain adequate approximate solutions, and make great computational demands. This dissertation considers in detail the efficient exploitation of the potential offered by parallel computers for solving such problems, and in particular the class of local memory Multiple Instruction, Multiple Data systems. A brief history of parallel computing is presented. Methods for quantifying the efficiency of parallel algorithms are reviewed. The use of pseudo-code for documenting algorithms is discussed and a pseudo-code notation is defined that is used in later chapters. A new parallel conjugate gradient algorithm, suitable for the solution of general systems of linear equations with complex values, is presented. A method is described to handle efficiently the Hermitian transpose of the matrix required by the algorithm. Careful attention is paid to the theoretical analysis of the algorithm's parallel properties (in particular, speed-up and efficiency). Pseudo-code is presented for the algorithms. Timing results for a moment method code, running on a transputer array and using this conjugate gradient solver, are presented and compared to the theoretical predictions. A parallel LU algorithm is described and documented in pseudo-code. A new graphical description of the algorithm is presented that simplifies the identification of the parallelism and the analysis of the algorithm. The use of formal methods for extracting parallelism via the use of invariants is presented and new examples given. The speed-up and efficiency of the algorithm are analyzed theoretically, using new methods that are simpler than those described in the literature. Techniques for optimizing the efficiency of parallel algorithms are introduced, and illustrated with pseudo-code. New parallel forward and backward substitution algorithms using the data distribution required for the parallel LV algorithm are described, and documented with pseudo-code. Results obtained with a Occam 2 moment method code running on a transputer array using these parallel LU solver and substitution algorithms are presented and compared with the theoretical predictions. PARNEC, a new Occam 2 implementation of the thin-wire core of NEC2, is discussed. The basic 'theory of NEC2 is reviewed. Problems with early attempts at combining Occam and FORTRAN are reported. Methodologies for re-coding an old code written in an unstructured language in a. modern structured language are discussed. Methods of parallelizing the matrix generation are discussed. The accuracy of large moment method formulations is investigated, as is the effect of machine precision on the solutions. The use of the biconjugate gradient method to accelerate convergence is briefly considered and rejected. The increased size of problem that can be handled by PARNEC, running on a transputer array, is demonstrated. Conclusions are dra.wn regarding the contributions of this dissertation to the development of efficient parallel electromagnetic moment method algorithms. / AFRIKAANSE OPSOMMING: Hierdie proefskrif ondersoek die momentmetode oplossing van elektromagnetiese straling- en strooiingprobleme d.m.v. multiverwerkers. In besonder, elektromagneties groot probleme met arbitrere geometriee word beskou. Sulke probleme vereis 'n groot aantal onbekendes om 'n voldoende benaderde oplossing te kry, en stel groot berekenings vereistes. Hierdie proefskrif beskou in detail die doeltreffende benutting van die potensiaal wat multiverwerkers vir sulke problem hied, in besonder die klas van lokale geheue Veelvoudige Instruksie, Veelvoudige Data stelsels. 'n Kort geskiedenis van multiverwerkers word gegee. Metodes vir die kwantifisering van die effektiwiteit van multiverwerkers word hersien. Die . gebruik van pseudokode vir die dokumentering van algoritmes word bespreek en 'n pseudokode notasie word gedefinieer wat gebruik word in latere hoofstukke. 'n Nuwe parallelle toegevoegde helling-algoritme wat geskik is vir die oplossing van algemene stelsels van lineere vergelykings word aangebied. 'n Metode word beskryf om op 'n doeltreffende wyse die Hermitiese transponent van die matriks, wat deur die algoritme benodig word, te hanteer. Sorgvuldige aandag word aan die teoretiese analise van die paralleleienskappe van die algoritme gegee (in die besonder, versnelling en doeltreffendheid). Pseudokode word aangebied vir die algoritmes. Resultate vir die looptyd van 'n momentmetode program, wat op 'n transputerskikking loop, word gegee en vergelyk met die teoretiese voorspellings. 'n Parallelle L U algoritme word beskryf en gedokumenteer in pseudokode. 'n Nuwe grafiese beskrywing van die algoritme, wat die identifikasie van parallelisme en die analise van die algoritme vergemaklik, word gegee. Die gebruik van formele metodes vir die onttrekking van parallelisme d.m.v. invariante word getoon en nuwe voorbeelde word gegee. Die versnelling en doeltreffendheid van die algoritme word teoreties geanaliseer, d.m.v. nuwe metodes wat eenvoudiger is as die wat in die literatuur beskryf word. Tegnieke vir die optimering van die doeltreffendheid van parallelle algoritmes word ingevoer, en gelllustreer met pseudokode. Nuwe parallelle voor- en truwaarts-substitusie algoritmes wat die data verspreiding van die parallelle LU algoritme gebruik word beskryf, en gedokumenteer met pseudokode. Resultate verkry met 'n Occam 2 momentmetode program wat op 'n transputerskikking loop en die parallelle L U en substit'usie algoritmes gebruik, word gegee en vergelyk met teoretiese voorspellings. PARNEC, 'n nuwe Occam 2 implementering van die dun-draad kern van NEC2, word bespreek. Die basiese teorie van NEC2 word opgesom. Verslag word gedoen oor probleme met vroee pogings orh Occam en FORTRAN te kombineer. Metodes om 'n ou program, geskryf in 'n ongestruktureerde taal, in 'n moderne gestruktureerde taal te herskryf word bespreek. Metodes om die matriksopwekking te paralleliseer word bespreek. Die akkuraatheid van groot momentmetode formulerings word ondersoek, asook die effek van masjienpresisie op die oplossings. Die gebruik van die dubbeltoegevoegde helling-metode om konvergensie te versnel word kortliks beskou en verwerp. Die vergrote probleemgrootte, wat met PARNEC op- 'n transputerskikking uitgevoer kan word, word gedemonstreer. Gevolgtrekkings word gemaak rakende die bydraes van hierdie proefskrif tot die ontwikkeling van doeltreffende parallelle elektromagnetiese momentmetode algoritmes.

Large-scale heterogeneous distributed computing environments (such as Computational Grids and Clouds) offer the promise of access to a vast amount of computing resources at a relatively low cost. In order to ease the application development and deployment on such complex environments, high-level parallel programming languages exist that need to be supported by sophisticated runtime systems. One of the main problems that these runtime systems need to address is dynamic load balancing that ensures that no resources in the environment are underutilised or overloaded with work. This thesis deals with the problem of obtaining good speedups for irregular applications on heterogeneous distributed computing environments. It focuses on workstealing techniques that can be used for load balancing during the execution of irregular applications. It specifically addresses two problems that arise during work-stealing: where thieves should look for work during the application execution and how victims should respond to steal attempts. In particular, we describe and implement a new Feudal Stealing algorithm and also we describe and implement new granularity-driven task selection policies in the SCALES simulator, which is a work-stealing simulator developed for this thesis. In addition, we present the comprehensive evaluation of the Feudal Stealing algorithm and the granularity-driven task selection policies using the simulations of a large class of regular and irregular parallel applications on a wide range of computing environments. We show how the Feudal Stealing algorithm and the granularity-driven task selection policies bring significant improvements in speedups of irregular applications, compared to the state-of-the-art work-stealing algorithms. Furthermore, we also present the implementation of the task selection policies in the Grid-GUM runtime system [AZ06] for Glasgow Parallel Haskell (GpH) [THLPJ98], in addition to the implementation in SCALES, and we also present the evaluation of this implementation on a large set of synthetic applications.

published_or_final_version / Computer Science / Master / Master of Philosophy

The primary purpose of this work is to study, implement and analyze the performance of parallel algorithms related to subsequence problems. The problems include string to string correction problem, to determine the longest common subsequence problem and solving the sum-range-product, 1 —D pattern matching, longest non-decreasing (non-increasing) (LNS) and maximum positive subsequence (MPS) problems. The work also includes studying the techniques and issues involved in developing parallel applications. These algorithms are implemented on the Sequent Multiprocessor System. The subsequence problems have been defined, along with performance metrics that are utilized. The sequential and parallel algorithms have been summarized. The implementation issues which arise in the process of developing parallel applications have been identified and studied.

Automatic generation of starvation-free semaphore solutions to general mutual exclusion problems is discussed. A reduction approach is introduced for recognizing edge-solvable problems, together with an O(N^2) algorithm for graph reduction, where N is the number of nodes. An algorithm for the automatic generation of starvation-free edge-solvable solutions is presented. The solutions are proved to be very efficient. For general problems, there are two ways to generate efficient solutions. One associates a semaphore with every node, the other with every edge. They are both better than the standard monitor—like solutions. Besides strong semaphores, solutions using weak semaphores, weaker semaphores and generalized semaphores are also considered. Basic properties of semaphore solutions are also discussed. Tools describing the dynamic behavior of parallel systems, as well as performance criteria for evaluating semaphore solutions are elaborated.

M.Sc. (Computer Science) / This report is primarily concerned with highlighting fmdings of a research recently undertaken towards completing the requirements for the M.Sc. degree of 1994 at the Rand Afrikaans University (RAU). The research is aimed at striving to investigate what benefits (if any) exist in Object-Oriented Parallel Systems. The area of research revolves around the Object-Oriented Parallel Paradigm (OOPP) which is currently under development by the author. One primary aim of this research is to investigate numerous current trends in Object-Oriented Parallel Systems and Language Developments with the objective of providing an indication as to whether the Object-Oriented methodology can be (or has been) successfully married with existing Parallel Processing mechanisms. New benefits may come about while attempting to combine these methodologies, and this expectation will also be reflected upon. The Object-Oriented methodology allows a system designer the ability to approach a problem with a good degree of problem space understanding; while Parallel Processing allows the system designer the ability to create extremely fast algorithms for solving problems amenable to Parallel Processing techniques. The question we attempt to answer is whether the Object-Oriented methodology can be successfully married to the Parallel Processing field (whilst maintaining a high degree of benefits encountered in both methodologies) so as to gain the best of both worlds. Certain papers have laid claim to their proposed system encompassing both the Object-Oriented methodology, as well as the Parallel Processing methodology. In view of this fact, we shall furthermore examine papers to see if any of these systems are candidates for successfully marrying Object-Oriented and Parallel Processing into one homogeneous body. Criticism will be given on the shortcomings of unsuccessful candidates. Based on the findings of the research, the report will culminate to the proposal of the Object-Oriented Parallel Paradigm (OOPP). OOPP will speculate on the most probable features that system designers can expect to see in an almost ideal Object-Oriented Parallel System. It is very important at this stage to mention that, at its current state of development, OOPP is only a paradigm; thus OOPP should be viewed merely as an abstract model intended to establish a solid foundation for building more formal Object-Oriented Parallel Methodologies. Furthermore, OOPP is intended to be suitable for present day systems and amenable (possibly with a few minor adjustments) to future systems. The author trusts OOPP to generate sufficient interest to warrant further research being commissioned. In this event, OOPP should be expected to undergo modifications and enhancements...