This work presents an automatic cost-analysis system for an implicitly parallel skeletal programming language. Although deducing interesting dynamic characteristics of parallel programs (and in particular, run time) is well known to be an intractable problem in the general case, it can be alleviated by placing restrictions upon the programs which can be expressed. By combining two research threads, the “skeletal” and “shapely” paradigms which take this route, we produce a completely automated, computation and communication sensitive cost analysis system. This builds on earlier work in the area by quantifying communication as well as computation costs, with the former being derived for the Bulk Synchronous Parallel (BSP) model. We present details of our shapely skeletal language and its BSP implementation strategy together with an account of the analysis mechanism by which program behaviour information (such as shape and cost) is statically deduced. This information can be used at compile-time to optimise a BSP implementation and to analyse computation and communication costs. The analysis has been implemented in Haskell. We consider different algorithms expressed in our language for some example problems and illustrate each BSP implementation, contrasting the analysis of their efficiency by traditional, intuitive methods with that achieved by our cost calculator. The accuracy of cost predictions by our cost calculator against the run time of real parallel programs is tested experimentally. Previous shape-based cost analysis required all elements of a vector (our nestable bulk data structure) to have the same shape. We partially relax this strict requirement on data structure regularity by introducing new shape expressions in our analysis framework. We demonstrate that this allows us to achieve the first automated analysis of a complete derivation, the well known maximum segment sum algorithm of Skillicorn and Cai.

The purpose of this study is to determine a model for analysis of integrating solar generation to the electric grid .The model is then used in determining Harmonics of Integrating solar panels to the electric grid that are based on parallel or series combination of solar cells. To study integration of solar generation to the grid, we have used solar series and solar parallel models in EMTP (Electro Magnetic Transient Program) real time simulation software. When integrating solar generation models to the grid, due to DC to AC conversion and due to variation of solar energy intensity, the electric utility shall experience undesired harmonics that may impact quality of service to other customers in the grid. This study identifies one method of analysis for determining harmonic content of solar panels before solar generation can be integrated in to the electric grid.

No description available.

The problem of efficient parallelization of 2D Ising spin systems requires realistic algorithmic design and implementation based on an understanding of issues from computer science and statistical physics. In this work, we not only consider fundamental parallel computing issues but also ensure that the major constraints and criteria of 2D Ising spin systems are incorporated into our study. This realism in both parallel computation and statistical physics has rarely been reflected in previous research for this problem. In this thesis,we designed and implemented a variety of parallel algorithms for both sweep spin selection and random spin selection. We analyzed our parallel algorithms on a portable and general parallel machine model, namely the LogP model. We were able to obtain rigorous theoretical run-times on LogP for all the parallel algorithms. Moreover, a guiding equation was derived for choosing data layouts (blocked vs. stripped) for sweep spin selection. In regards to random spin selection, we were able to develop parallel algorithms with efficient communication schemes. We analyzed randomness of our schemes using statistical methods and provided comparisons between the different schemes. Furthermore, algorithms were implemented and performance data gathered and analyzed in order to determine further design issues and validate theoretical analysis. / Master of Science

Made available in DSpace on 2016-03-22T17:26:09Z (GMT). No. of bitstreams: 1 Vanessa_Souza_da_Fonseca.pdf: 1687661 bytes, checksum: 6dbf2a6dc47f997aa3e8aa0c8f37aced (MD5) Previous issue date: 2008-08-07 / This research describes the main contributions of the VirD-GM (Virtual Distributed Geometric Machine Model) for the model of parallelism and distribution of the Project D-GM (Distributed Geometric Machine Project). In order to provide the abstractions of the GM model (Geometric Machine) on a platform to support the implementation distributed and / or parallel computations, the middleware EXEHDA (Execution Environment for High Distributed Applications) is considered as the execution environment. The work enabled to create and manage an environment of parallel and directed programming, and promote the implementation, in this environment, of applications developed in the visual environment VPE-GM (Visual Programming Environment for the Geometric Machine Model). These applications are, by nature, parallel and restricted to the study of parallel algorithms for Scientific Computation. The work focuses on the design and construction of the software architecture of the VirD-GM, which is responsible for managing parallel computations obtained by the application of process constructors defined by the GM model. In this context, this research does not only disposes the construction of the structural vision of the project D-GM but also consolidates its integration with the functional vision. It is characterized by an extension of the visual environment VPEGM, which is responsible for the environment development and code generation for the Project D-GM. Among the main contributions, one may consider: (i) formalization of the concepts of concurrency and conflict intermittent with the notions of communication and synchronization of processes, directly related to the space-time structure of the GM model; (ii) modeling and implementation of the loading, management and control structures of the VirD-GM; (iii) implementation and customization of services provided by the EXEHDA; (iv) construction of the levels of applications, support of execution environment and basic systems; (v) data flow control and manipulation of adjacency matrix related to concurrent computations, including the implementation of barriers of synchronization. The prototyping of VirD-GM and avaliaton achieved through the development of test applications have implemented the viability of theoretical-practical approach proposed in Project D-GM / Este trabalho descreve as principais contribuic¸ oes da VirD-GM (Virtual Distributed Geometric Machine Model) para o modelo de distribuic¸ ao e paralelismo do Projeto D-GM (Distributed Geometric Machine Project). Para disponibilizar as abstrac¸ oes do modelo GM (Geometric Machine) em uma plataforma com suporte `a execuc¸ ao distribu ´ıda e/ou concorrente, considera-se o middleware EXEHDA ( Execution Environment for High Distributed Applications) como ambiente de suporte `a execuc¸ ao. O trabalho possibilitou criar e gerenciar um ambiente de programac¸ ao paralela e distribu´ıda, bem como promover a execuc¸ ao, sob este ambiente, das aplicac¸ oes desenvolvidas no ambiente visual VPE-GM (Visual Programming Environment for the Geometric Machine Model). Estas aplicac¸ oes s ao, por natureza, paralelas e direcionadas ao estudo de algoritmos paralelos para a Computac¸ ao Cient´ıfica. O trabalho est´a centrado na concepc¸ ao e construc¸ ao da arquitetura de software da VirD-GM, respons´avel pelo gerenciamento das computac¸ oes paralelas obtidas pela aplicac¸ ao de construtores de processos definidos no modelo GM. Neste contexto, esta dissertac¸ ao n ao s´o viabilizou construc¸ ao da vis ao estrutural do projeto D-GM como tamb´em consolidou sua integrac¸ ao com a vis ao funcional, caracterizada pela extens ao do ambiente VPE-GM, respons´avel pelo ambiente de desenvolvimento e gerac¸ ao de c´odigo para o Projeto D-GM. Dentre as principais contribuic¸ oes, destacam-se: (i) formalizac¸ ao das noc¸ oes de concorr encia e conflito intermitentes com as noc¸ oes de comunicac¸ ao e sincronizac¸ ao de processos, diretamente relacionadas com a estrutura espac¸o-temporal do modelo GM; (ii) definic¸ ao compreendendo a modelagem e implementac¸ ao dos m´odulos de carregamento, gerenciamento e controle da VirD-GM; (iii) estudo, aplicac¸ ao e customizac¸ ao dos servic¸os disponibilizados pelo middleware EXEHDA; (iv) implementac¸ ao das camadas de aplicac¸ ao, de suporte ao ambiente de execuc¸ ao e de sistemas b´asicos; (v) controle do fluxo de dados e manipulac¸ ao das depend encias entre as computac¸ oes concorrentes pelo uso de matrizes de adjac encias, incluindo a implementac¸ ao de barreiras de sincronizac¸ ao, garantindo a correta execuc¸ ao. A prototipac¸ ao da VirD-GM e a avaliac¸ ao obtida com o desenvolvimento de aplicac¸ oes de teste demonstraram a viabilidade da abordagem te´orica-pr´atica proposta no Projeto D-GM

Nous proposons de nouveaux algorithmes et de nouvelles structures de données pour la vérification formelle de systèmes réactifs finis sur architectures parallèles. Ces travaux se basent sur les techniques de vérification model checking. Notre approche cible des architectures multi-processeurs et multi-cœurs, avec mémoire partagée, qui correspondent aux générations de serveurs les plus performants disponibles actuellement.Dans ce contexte, notre objectif principal est de proposer des approches qui soient à la fois efficaces au niveau des performances, mais aussi compatibles avec les politiques de partage dynamique du travail utilisées par les algorithmes de génération d’espaces d'états en parallèle; ainsi, nous ne plaçons pas de contraintes sur la manière dont le travail ou les données sont partagés entre les processeurs.Parallèlement à la définition de nouveaux algorithmes de model checking pour machines multi-cœurs, nous nous intéressons également aux algorithmes de vérification probabiliste. Par probabiliste, nous entendons des algorithmes de model checking qui ont une forte probabilité de visiter tous les états durant la vérification d’un système. La vérification probabiliste permet des gains importants au niveau de la mémoire utilisée, en échange d’une faible probabilité de ne pas être exhaustif; il s’agit donc d’une stratégie permettant de répondre au problème de l’explosion combinatoire / In this thesis, we propose and study new algorithms and data structures for model checking finite-state, concurrent systems. We focus on techniques that target shared memory, multi-cores architectures, that are a current trend in computer architectures.In this context, we present new algorithms and data structures for exhaustive parallel model checking that are as efficient as possible, but also ``friendly'' with respect to the work-sharing policies that are used for the state space generation (e.g. a work-stealing strategy): at no point do we impose a restriction on the way work is shared among the processors. This includes both the construction of the state space as the detection of cycles in parallel, which is is one of the key points of performance for the evaluation of more complex formulas.Alongside the definition of enumerative, model checking algorithms for many-cores architectures, we also study probabilistic verification algorithms. By the term probabilistic, we mean that, during the exploration of a system, any given reachable state has a high probability of being checked by the algorithm. Probabilistic verification trades savings at the level of memory usage for the probability of missing some states. Consequently, it becomes possible to analyze part of the state space of a system when there is not enough memory available to represent the entire state space in an exact manner