Dissertations / Theses on the topic 'Parallel Automata'
To see the other types of publications on this topic, follow the link: Parallel Automata.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Parallel Automata.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Vollweiler, Marcel [Verfasser]. "Systems of Parallel Communicating Restarting Automata / Marcel Vollweiler." Kassel : Universitätsbibliothek Kassel, 2013. http://d-nb.info/1043824987/34.
Full text
2
Slotta, Douglas J. "Structural Design Using Cellular Automata." Thesis, Virginia Tech, 2001. http://hdl.handle.net/10919/33368.
Full textAbstract:
Traditional parallel methods for structural design do not scale well. This thesis discusses
the application of massively scalable cellular automata (CA) techniques to structural design.
There are two sets of CA rules, one used to propagate stresses and strains, and one to
perform design analysis. These rules can be applied serially, periodically, or concurrently,
and Jacobi or Gauss-Seidel style updating can be done. These options are compared with
respect to convergence, speed, and stability.Master of Science
3
Xu, Hao, and 許浩. "On the computational ability of cellular automata." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2002. http://hub.hku.hk/bib/B31226942.
Full text
4
Xu, Hao. "On the computational ability of cellular automata /." Hong Kong : University of Hong Kong, 2002. http://sunzi.lib.hku.hk/hkuto/record.jsp?B25155088.
Full text
5
Torbey, Sami. "Towards a framework for intuitive programming of cellular automata." Thesis, Kingston, Ont. : [s.n.], 2007. http://hdl.handle.net/1974/929.
Full text
6
Wang, Zhengping. "A parallel implementation of a cellular automata based earthquake model." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1997. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp04/mq22145.pdf.
Full text
7
Šoustar, Jakub. "Syntaktická analýza založená na systémech hlubokých zásobníkových automatů." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2017. http://www.nusl.cz/ntk/nusl-363793.
Full textAbstract:
This thesis investigates deep pushdown automata and introduces their modification called controlled deep pushdown automata. Distributed deep pushdown automata systems and parallel communicating deep pushdown automata systems are described. Their accepting power and properties are investigated and several variants are introduced. This thesis proves that the accepting power of one such variant of parallel communicating deep pushdown automata systems is equal to the accepting power of Turing machines. A method for syntactical analysis based on the previously introduced automata systems is described.
8
Castro, Antonio Paulo. "Dynamic water quality modeling using cellular automata." Diss., This resource online, 1996. http://scholar.lib.vt.edu/theses/available/etd-06062008-151210/.
Full text
9
Krčmář, Radim. "Regulované systémy automatů." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2016. http://www.nusl.cz/ntk/nusl-255359.
Full textAbstract:
This thesis defines and studies two new types of automata, cooperating distributed pushdown automata systems (CDPDAS) and parallel communicating pushdown automata systems (PCPDAS). CDPDAS and PCPDAS adapt the main concept of cooperating distributed grammar systems (CDGS) and parallel communicating automata systems (PCPDAS), respectively. CDPDAS are proven to have the same power as PDA and this thesis further explores the reason why CDPDAS do not increase power while CDGS do and introduces an automata system inspired by CDPDAS that does increase the power. PCGS have similar power as CDGS, but PCPDAS are equvalent with TM, which is proven by creating a communication protocol to access a second stack.
10
Kučera, Jiří. "A Combination of Automata and Grammars." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2013. http://www.nusl.cz/ntk/nusl-236222.
Full textAbstract:
V této práci byly zavedeny a studovány nové systémy formálních modelů, zvané stavově synchronizované automatové systémy stupně n . Výpočet je v těchto prezentovaných systémech řízen pomocí slov patřících do konečného řídícího jazyka, kde každé slovo z tohoto jazyka je složeno ze stavů komponent systému. Dále byla v této práci studována výpočetní síla zavedených systémů. Praktické použití zavedených systémů bylo demonstrováno na příkladu z oblasti překladu přirozených jazyků a dále na příkladu z oblasti paralelního překladu.
11
Louis, Pierre-Yves. "Coupling, space and time Mixing for parallel stochastic dynamics." Universität Potsdam, 2004. http://opus.kobv.de/ubp/volltexte/2011/5156/.
Full textAbstract:
We first introduce some coupling of a finite number of Probabilistic Cellular
Automata dynamics (PCA), preserving the stochastic ordering. Using this tool, for a general attractive probabilistic cellular automata on SZd, where S is finite, we prove that a condition (A) is equivalent to the (time-) convergence towards equilibrium of this Markovian parallel dynamics, in the uniform norm, exponentially fast. This condition (A) means the exponential decay of the influence from the boundary for the invariant measures of the system restricted to finite ‘box’-volume. For a class of reversible PCA dynamics on {−1, +1}Zdwith a naturally associated Gibbsian potential ϕ, we prove that a Weak Mixing condition for ϕ implies the validity of the assumption (A); thus the ‘exponential ergodicity’ of the dynamics towards the unique Gibbs measure associated to ϕ holds. On some particular examples of this PCA class, we verify that our assumption (A) is weaker than the Dobrushin-Vasershtein ergodicity condition. For some special PCA, the ‘exponential ergodicity’ holds as soon as there is no phase transition.
12
Bujtor, Ferenc Péter [Verfasser], and Walter [Akademischer Betreuer] Vogler. "Modal Interface Automata: A Theory for Heterogeneous Specification of Parallel Systems / Ferenc Péter Bujtor ; Betreuer: Walter Vogler." Augsburg : Universität Augsburg, 2018. http://d-nb.info/1172634912/34.
Full text
13
Yu, Di. "An Application Developed for Simulation of Electrical Excitation and Conduction in a 3D Human Heart." Scholar Commons, 2013. http://scholarcommons.usf.edu/etd/4620.
Full textAbstract:
This thesis first reviews the history of General Purpose computing Graphic Processing Unit (GPGPU) and then introduces the fundamental problems that are suitable for GPGPU algorithm. The architecture of GPGPU is compared against modern CPU architecture, and the fundamental difference is outlined. The programming challenges faced by GPGPU and the techniques utilized to overcome these issues are evaluated and discussed.
The second part of the thesis presents an application developed with GPGPU technology to simulate the electrical excitation and conduction in a 3D human heart model based on cellular automata model. The algorithm and implementation are discussed in detail and the performance of GPU is compared against CPU.
14
Korkmaz, Ozan. "Inverse Dynamics Control Of Flexible Joint Parallel Manipulators." Master's thesis, METU, 2006. http://etd.lib.metu.edu.tr/upload/3/12608084/index.pdf.
Full textAbstract:
The purpose of this thesis is to develop a position control method for parallel manipulators so that the end effector can follow a desired trajectory specified in the task space where joint flexibility that occurs at the actuated joints is also taken into consideration.
At the beginning of the study, a flexible joint is modeled, and the equations of motion of the parallel manipulators are derived for both actuator variables and joint variables by using the Lagrange formulation under three assumptions regarding dynamic coupling between the links and the actuators. These equations of motion are transformed to an input/output relation between the actuator torques and the actuated joint variables to achieve the trajectory tracking control. Moreover, the singular configurations of the parallel manipulators are explained.
As a case study, a three degree of freedom, two legged planar parallel manipulator is simulated considering joint flexibility. The structural damping of the active joints, viscous friction at the passive joints and the rotor damping are also considered throughout the study. Matlab®and Simulink®
softwares are used for the simulations. The results of the simulations reveal that steady state errors are negligibly small and good tracking performances can be achieved.
15
Ozdemir, Mustafa. "Inverse Dynamics Control Of Parallel Manipulators Around Singular Configurations." Master's thesis, METU, 2008. http://etd.lib.metu.edu.tr/upload/3/12609212/index.pdf.
Full textAbstract:
In this thesis, a technique for the motion of parallel manipulators through drive singularities is investigated. To remedy the problem of unbounded inverse dynamics solution in the neighborhood of drive singularities, an inverse dynamics controller which uses a conventional inverse dynamics control law outside the neighborhood of singularities and switches to the mode based on the formerly derived modified equations inside the neighborhood of singularities is proposed. As a result, good tracking performance is obtained while the actuator forces remain within the saturation limits of the actuators around singular configurations.
16
Martinek, Dominik. "Simulace fyzikálních jevů s využitím celulárních automatů." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2010. http://www.nusl.cz/ntk/nusl-237104.
Full textAbstract:
This master's thesis deals with modelling and simulation of physical phenomena by cellular automata. The basic methods which model physical phenomena is enumerated and descibed in this thesis. One of the important part of this thesis is a set of demonstration models. Each model is focused on one selected area of physical phenomena. All models are described by transtition rules and the procedure of derivation of these rules is also presented here. There rules were used in implemented models. Another part of this thesis contains of a simulation application for these models. The real application had been implemented in accord with this design and it has been used to perform the simulation experiments with exemplary models. Results of the simulation experiments are discussed in conclusion of this thesis. One exemplary model had also been adapted for parallel processing. The performances on a computer with different count of working processors were measured and are also discussed in the conclusion of this thesis
17
Bartůněk, Petr. "Knihovna operací nad konečnými automaty." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2010. http://www.nusl.cz/ntk/nusl-237128.
Full textAbstract:
This work deals with two basic operations over finite automata. Determination of nondeterministic finite automata and minimization of deterministic finite automata. For these two operations I proposed sequential algorithms that are parallelizable. I deal mainly with finding the speedup of SSE instructions, or use the OpenMP library. The trend today is mainly in increasing the number of processors, so I propose parallel algorithms for multiple processors. When searching for the optimal solution, I will be to examine other ways to achieve speedup, for example efficient saving of the data structures in memory.
18
Truong, Tuyen Phong. "Simulation and compiler support for communication and mobility for environment sensing." Thesis, Brest, 2018. http://www.theses.fr/2018BRES0048/document.
Full textAbstract:
Les transmissions radio à longue portée et basse énergie ouvrent de nouveaux champs d'application pour les capteurs, en particulier pour la surveillance de l'environnement. Le protocole radio LoRa permet, par exemple, de connecter des capteurs à une distance pouvant aller jusqu'à dix kilomètres en ligne de visée. Cependant, la grande surface couverte amène plusieurs difficultés, telles que le placement spatial en regard de la topologie géographique, ou la variabilité de la latence des communications. Le positionnement dans I'environnement comporte également des contraintes liées à I'intérêt des points de mesure du phénomène physique. Les critères de conception de ces réseaux tranchent donc avec les méthodes existantes (disques) quand on s'attaque aux terrains complexes. Cette thèse décrit des techniques de simulation basées sur I'analyse géographique cellulaire pour calculer les couvertures radio à longue portée et déduire les caractéristiques radios dans ces situations. Comme la propagation radio n'est qu'un cas particulier de phénomènes physiques, on montre qu'une approche unifiée cellulaire permet de caractériser beaucoup de comportements physiques potentiels. Le cas des fortes pluies et des inondations est étudié. L'analyse de la géographie est réalisée en utilisant des outils de segmentation pour produire des systèmes cellulaires qui sont à leur tour traduits en code pour des calculs de haute performance. La thèse fournit des résultats d'expériences de terrain complexes pratiques en utilisant LoRa, permettant de qualifier l'exactitude de la simulation des couvertures, et les caractéristiques d'ordonnancement des communications. Nous produisons des tables de performance pour les simulations sur les unités de traitement graphique (GPUs) qui montrent que le choix d'une algorithmique parallèle est pertinent sur ces problèmesLong-range radio transmissions open new sensor application fields, in particular for environment monitoring. For example, the LoRa radio protocol enables to connect remote sensors at distance as long as ten kilometers in a line-of-sight. However, the large area covered also brings several difficulties, such as the placement of sensing devices in regard to topology in geography, or the variability of communication latency. Sensing the environment also carries constraints related to the inlerest of sensing points in relation with a physical phenomenon. Thus criteria for designs are evolving a lot from the existing methods, especially in complex terrains. This thesis describes simulation techniques based on geography analysis to compute long-range radio coverages and radio characteristics in these situations. As radio propagation is just a particular case of physical phenomena, it is shown how a unified approach also allows to characterize the behavior of potential physical risks. The case of heavy rainfall and flooding is investigated. Geography analysis is achieved using segmentation tools to produce cellular systems which are in turn translated into code for high-þerformance computations. The thesis provides results from practical complex terrain experiments using LoRa which confirm the accuracy of the simulation, and scheduling characteristics for sample networks. Performance tables are produced for these simulations on current Graphics Processing Units (GPUs)
19
Kucuk, Ali. "The Multi - Objective Path Placement Optimization Of Parallel Kinematic Machines." Master's thesis, METU, 2013. http://etd.lib.metu.edu.tr/upload/12615533/index.pdf.
Full textAbstract:
The aim of this study is to obtain optimal position and orientation of a trajectory frame with respect to the fixed frame of the manipulator. The work path which is given in the trajectory frame is also constrained in the workspace of the 3 &ndashPRS parallel kinematic machine. In the analysis, forward and inverse kinematics solutions are derived as well as the inverse dynamics model using Lagrange&rsquo
s Method. Several algorithms governing the motion of the manipulator are developed. Moreover, optimization goals are defined and evaluated with the genetic algorithm.
20
Teitelbaum, Aryeh Roberto, and a_hay@jct ac il. "Arts'Codes: A New Methodology for the Development of Real-Time Embedded Applications for Control Systems." RMIT University. Accounting and Law, 2007. http://adt.lib.rmit.edu.au/adt/public/adt-VIT20071219.094115.
Full textAbstract:
Embedded real-time applications have to allow interaction between the control computer and the controlled environment. Controlling the environment requires in particular to take into account its time constraints and critical logical conditions. One of the main programmer efforts in real-time application's development is to trace the incoming events, and to perform reactions based on the current system status, according to the application requirements. All this have to be handled, although external events may come in the middle of a critical reaction, which may disturb it. This problem involves two difficulties: X The cognitive efforts to percept the problem, and consequently to express the solution. X The correct translation of this solution to code. Two requirements were defined in this research in order to achieve high-quality performance: clearness and robustness, clearness in the design, and robustness in the execution. In this work the author proposes a methodology and a tool for real-time application's development that uses or implies an innovated form of design based on natural-cognitive researches. This design method has clear compilation's rules to produce an Object-Oriented light-code, suitable for embedded platforms. These compilation's rules introduce to the code implicit security and synchronization's elements, to support robust execution. In this methodology, clear development phases were defined, using a high-degree of reuse and even polymorphism, which were emphasized in the research. Several existing ideas were improved/adapted and synthesized together with the author's innovation, creating the Arts'Codes method for real-time application development. The work includes cognitive evaluations, assuring the natural skills of the design. Arts'Codes method proposes a natural VPL (Visual Programming Language) for real-time applications, based on hierarchic components. This VPL is built on a minimum of diagrams: one for the static architecture and one for the dynamic behaviour, with a similar restricted notation at all levels. These two diagrams (static architecture and dynamic behaviour) are interleaved in a unified view. This method was implemented by building a suitable graphic editor, which automatically compiles the applications diagrams in a light and robust Object-Oriented code (based on Parallel Automata FSM), and by building an execution compact software platform. Furthermore, the parallel automata FSM are translated automatically in PTL temporal formula defining the goals and the behaviours of the components, permitting to prove a-priory that the components behaviours are consistent to their goals. The execution platform is based on a restricted implementation of the synchrony hypothesis and on a powerful model of execution: the parallel automata FSM. These Parallel Automata describe the dynamic behaviours of the components and allows implementing run-time exceptions handling too. In addition, the research proposes a tri-processor execution hardware platform, which supports a hybrid synchronous/multi-threading execution. This method will contribute to versatile, clear and robust real-time application's development.
21
Kumar, Anand. "Efficient and Private Processing of Analytical Queries in Scientific Datasets." Scholar Commons, 2013. http://scholarcommons.usf.edu/etd/4822.
Full textAbstract:
Large amount of data is generated by applications used in basic-science research and development applications. The size of data introduces great challenges in storage, analysis and preserving privacy. This dissertation proposes novel techniques to efficiently analyze the data and reduce storage space requirements through a data compression technique while preserving privacy and providing data security.
We present an efficient technique to compute an analytical query called spatial distance histogram (SDH) using spatiotemporal properties of the data. Special spatiotemporal properties present in the data are exploited to process SDH efficiently on the fly. General purpose graphics processing units (GPGPU or just GPU) are employed to further boost the performance of the algorithm.
Size of the data generated in scientific applications poses problems of disk space requirements, input/output (I/O) delays and data transfer bandwidth requirements. These problems are addressed by applying proposed compression technique. We also address the issue of preserving privacy and security in scientific data by proposing a security model. The security model monitors user queries input to the database that stores and manages scientific data. Outputs of user queries are also inspected to detect privacy breach. Privacy policies are enforced by the monitor to allow only those queries and results that satisfy data owner specified policies.
22
Benítez, César Manuel Vargas. "Contributions to the study of the protein folding problem using bioinspired computation and molecular dynamics." Universidade Tecnológica Federal do Paraná, 2015. http://repositorio.utfpr.edu.br/jspui/handle/1/1211.
Full textAbstract:
O Problema de Dobramento de Proteínas (PDP) é considerado um dos desafios abertos mais importantes da Biologia e Bioinformática. Nesta tese, uma nova abordagem para simular os pathways de dobramento de proteínas é proposta onde, ao invés de utilizar a estrutura tridimensional da proteína, os estados de dobramento são representados por Mapas de Contatos (MC). Autômatos Celulares bidimensionais (2D-CA) são utilizados para simular o processo de dobramento, onde cada configuração representa um estado de dobramento e é obtida em relação ao seu estado predecessor e uma regra de transição. Determinar uma regra de transição para um dado comportamento dinâmico representa uma tarefa complexa. Portanto, é apresentada uma abordagem distribuida baseada em Programação de Expressão Gênica, chamada pGEP-CA. Funções de fitness específicas, baseadas em medidas de similaridade e simetria, são propostas. Também, um algoritmo heterogêneo paralelo Ecologicamente-inspirado é proposto. Este algoritmo, chamado pECO, é utilizado na reconstrução de estruturas a partir de MCs, usando o modelo 3D-AB off-lattice. De acordo com o nosso conhecimento, é apresentada a primeira aplicação de Dinâmica Molecular (DM) ao PFP, usando o mesmo modelo de proteínas. Experimentos foram realizados para verificar a adequabilidade das abordagens propostas. Além disto, uma breve análise sobre o balanceamento de carga de processamento das arquiteturas paralelas é apresentada. Os resultados mostram que as abordagens obtiveram resultados coerentes, sugerindo que são adequadas para o problema. As regras de transição induzidas pelo pGEP-CA são capazes de gerar 2D-CA que representam MCs corretamente. Sobre a abordagem pECO, os resultados demonstram que a combinação de abordagens evolucionárias concorrentes se beneficia do efeito da coevolução e das diferentes estratégias de busca. Além disto, pode ser observado que a abordagem de DM é capaz de levar a conformações que mimetizam propriedades biológicas, como a formação do núcleo hidrofóbico e os movimentos de respiração (breathing) das proteínas. Também foi observado que o processamento paralelo é essencial, permitindo a obtenção de resultados em tempos de processamento razoáveis. Finalmente, as conclusões e diversas direções de pesquisa são apresentadas.The Protein Folding Problem (PFP) is considered one of the most important open cha- llenges in Biology and Bioinformatics. In this thesis, a novel approach for simulating the protein folding pathways is proposed where, instead using the three-dimensional structure of the protein, the folding states are represented by Contact Maps (CM). A two-dimensional Cellular Automata (2D-CA) evolver is used to simulate the fol- ding process, where each configuration represents a folding state and it is obtained according to its predecessor and a transition rule. Since finding transition rules for simulating a dynamic behavior is a very difficult task, it is proposed a distributed Gene-Expression Programming (GEP)-based approach, called pGEP-CA. Specific fit- ness functions, based on similarity and symmetry measures, are proposed. Futhermore, a heterogeneous parallel Ecology-inspired algorithm is proposed. This algorithm, called pECO, is used for reconstructing the structures from the CMs, using the 3D-AB off-lattice model. Moreover, to the best of our knowledge, it is presented the first application of Molecular Dynamics (MD) to the PFP, using the same model of proteins. Experiments were done to evaluate the adequacy of the proposed approaches. Also, a brief analysis of the load balancing of the parallel architectures is presented. Results show that the approaches obtained coherent results, suggesting their adequacy for the problem. The induced transition rules by the pGEP-CA are able to generate 2D-CA that represent CMs correctly. Concerning the pECO approach, results show that the combination of concurrent evolutionary approaches took advantage of both the coevolution effect and the different search strategies. In addition, it can be observed that the MD approach is capable of displaying biological features such as the hydrophobic core formation and the protein breathing motion. Furthermore, it is observed that parallel processing was not only justified but also essential for obtaining results in reasonable processing time. Finally, concluding remarks and several research directions for future works are presented.
23
Ziadi, Djelloul. "Algorithmique parallèle et séquentielle des automates." Rouen, 1996. http://www.theses.fr/1996ROUES003.
Full textAbstract:
Cette thèse constitue un point de départ pour une programmation parallèle des automates. Elle combine une approche séquentielle et une approche parallèle (sur le modèle PRAM) de l'analyse de ces algorithmes. On y trouve un nouvel algorithme séquentiel optimal de conversion d'une expression rationnelle en un automate ainsi que sa parallélisation (également optimale) un test d'appartenance d'un mot à un langage rationnel est développé, fournissant un algorithme parallèle efficace. Un algorithme séquentiel optimal, original de minimisation d'automate déterministe est décrit. De nouvelles techniques algorithmiques sont introduites tout au long de cette étude qui met en évidence l'apport réciproque des deux algorithmiques, séquentielle et parallèle.
24
Tachon, Thibaut. "Génération automatique de code parallèle isochrone." Thesis, Orléans, 2019. http://www.theses.fr/2019ORLE3098.
Full textAbstract:
Depuis la stagnation de la fréquence d’horloge des processeurs, l’accroissement de la puissance de calcul a dépendu entièrement de l’accroissement du nombre d’unités de calcul. Plus que la difficulté algorithmique impliquée par l’écriture de tout programme séquentiel, la programmation parallèle demande au programmeur de gérer de nombreuses unités de calcul, incluant leurs tâches et leurs interactions. Pour alléger le fardeau du programmeur, cette thèse propose deux approches différentes de génération automatique de code parallèle. Le modèle parallèle isochrone BSP possède des propriétés intéressantes telles que son modèle de coût qui en font la cible de notre génération de code parallèle. Les automates et expressions régulières sont souvent choisis pour modéliser les calculs séquentiels et leurs parallélisation devrait, à long terme, aboutir à de solides fondations pour la génération de code parallèle. Pour notre approche principale, nous développons la théorie des automates BSP avec leur génération et détermination. Cette théorie est utilisée dans une nouvelle méthode pour la recherche de motif à l’aide d’expressions régulières. Notre autre approche propose un langage spécifique au domaine des réseaux de neurones où la composition fonctionnelle d’un petit nombre de primitives facilite le développement, la maintenance et la définition formelle du langage par rapport aux approches existantesSince we are in an era of processor clock stagnation, computing power growth has been relying on parallel computing. More than the algorithmic difficulty involved in any program writing, parallel computing additionally requires the programmer to manage numerous processing units including their tasks and interactions. In order to alleviate the parallel programmer’s burden, this thesis proposes two different approaches for automatic parallel code generation. The bulk-synchronous parallel (BSP) model provides good properties such as its cost model and is therefore chosen as the target of our parallel code generation.Automata and regular expressions are often chosen to model sequential computation and their parallelization will lead to a strong foundation for general parallel code generation. For our main approach, we develop the theory of BSP automata with their generation and determinization. This theory is used in a novel method for parallel regular expression matching.As another approach, we propose a domain specific language for programming neural nets where the functional composition of only a few primitives eases development, maintenance and formal definition of the language compared to existing approaches
25
Klüppelholz, Sascha. "Verification of Branching-Time and Alternating-Time Properties for Exogenous Coordination Models." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2012. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-86211.
Full textAbstract:
Information and communication systems enter an increasing number of areas of daily lives. Our reliance and dependence on the functioning of such systems is rapidly growing together with the costs and the impact of system failures. At the same time the complexity of hardware and software systems extends to new limits as modern hardware architectures become more and more parallel, dynamic and heterogenous. These trends demand for a closer integration of formal methods and system engineering to show the correctness of complex systems within the design phase of large projects.
The goal of this thesis is to introduce a formal holistic approach for modeling, analysis and synthesis of parallel systems that potentially addresses complex system behavior at any layer of the hardware/software stack. Due to the complexity of modern hardware and software systems, we aim to have a hierarchical modeling framework that allows to specify the behavior of a parallel system at various levels of abstraction and that facilitates designing complex systems in an iterative refinement procedure, in which more detailed behavior is added successively to the system description. In this context, the major challenge is to provide modeling formalisms that are expressive enough to address all of the above issues and are at the same time amenable to the application of formal methods for proving that the system behavior conforms to its specification. In particular, we are interested in specification formalisms that allow to apply formal verification techniques such that the underlying model checking problems are still decidable within reasonable time and space bounds.
The presented work relies on an exogenous modeling approach that allows a clear separation of coordination and computation and provides an operational semantic model where formal methods such as model checking are well suited and applicable. The channel-based exogenous coordination language Reo is used as modeling formalism as it supports hierarchical modeling in an iterative top-down refinement procedure. It facilitates reusability, exchangeability, and heterogeneity of components and forms the basis to apply formal verification methods. At the same time Reo has a clear formal semantics based on automata, which serve as foundation to apply formal methods such as model checking.
In this thesis new modeling languages are presented that allow specifying complex systems in terms of Reo and automata models which yield the basis for a holistic approach on modeling, verification and synthesis of parallel systems. The second main contribution of this thesis are tailored branching-time and alternating time temporal logics as well as corresponding model checking algorithms. The thesis includes results on the theoretical complexity of the underlying model checking problems as well as practical results. For the latter the presented approach has been implemented in the symbolic verification tool set Vereofy. The implementation within Vereofy and evaluation of the branching-time and alternating-time model checker is the third main contribution of this thesis.
26
Aronsson, Peter. "Automatic Parallelization of Equation-Based Simulation Programs." Doctoral thesis, Linköping : Department of Computer and Information Science, Linköping University, 2006. http://www.bibl.liu.se/liupubl/disp/disp2006/tek1022s.pdf.
Full text
27
Dai, Jiehua. "Automatic Parallel Memory Address Generation for Parallel DSP Computing." Thesis, Linköping University, Department of Electrical Engineering, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-11110.
Full textAbstract:
The concept of Parallel Vector (scratch pad) Memories (PVM) was introduced as one solution for Parallel Computing in DSP, which can provides parallel memory addressing efficiently with minimum latency. The parallel programming more efficient by using the parallel addressing generator for parallel vector memory (PVM) proposed in this thesis. However, without hiding complexities by cache, the cost of programming is high. To minimize the programming cost, automatic parallel memory address generation is needed to hide the complexities of memory access.
This thesis investigates methods for implementing conflict-free vector addressing algorithms on a parallel hardware structure. In particular, match vector addressing requirements extracted from the behaviour model to a prepared parallel memory addressing template, in order to supply data in parallel from the main memory to the on-chip vector memory.
According to the template and usage of the main and on-chip parallel vector memory, models for data pre-allocation and permutation in scratch pad memories of ASIP can be decided and configured. By exposing the parallel memory access of source code, the memory access flow graph (MFG) will be generated. Then MFG will be used combined with hardware information to match templates in the template library. When it is matched with one template, suited permutation equation will be gained, and the permutation table that include target addresses for data pre-allocation and permutation is created. Thus it is possible to automatically generate memory address for parallel memory accesses.
A tool for achieving the goal mentioned above is created, Permutator, which is implemented in C++ combined with XML. Memory access coding template is selected, as a result that permutation formulas are specified. And then PVM address table could be generated to make the data pre-allocation, so that efficient parallel memory access is possible.
The result shows that the memory access complexities is hiden by using Permutator, so that the programming cost is reduced.It works well in the context that each algorithm with its related hardware information is corresponding to a template case, so that extra memory cost is eliminated.
28
Amrane, Amazigh. "Posets série-parallèles transfinis : automates, logiques et théories équationnelles." Thesis, Normandie, 2020. http://www.theses.fr/2020NORMR102.
Full textAbstract:
Nous étudions dans cette thèse des structures généralisant la notion classique de mot. Elles sont construites à partir d’un ensemble partiellement ordonné (partially ordered set ou poset) vérifiant les propriétés suivantes : — elles ne contiennent pas 4 éléments distincts x, y, z, t dont l’ordre relatif est exactement x < y, z < y, z < t (posets dits sans N) ; — les chaînes sont des ordres linéaires dénombrables et dispersés ; — les antichaînes sont finies ; et chaque élément est étiqueté par une lettre d’un alphabet fini. De manière équivalente, la classe des posets que nous considérons est la plus petite construite à partir du poset vide et du singleton, fermée par les produits séquentiel et parallèle finis, et le produit ω et son renversé −ω (posets série-parallèles). Elle est une généralisation à la fois des posets série-parallèles finis étiquetés, en y ajoutant l’infinitude, et des mots transfinis, en affaiblissant l’ordre total des éléments en ordre partiel. En informatique, les posets série-parallèles finis trouvent leur intérêt dans la modélisation des processus concurrents basés sur les primitives fork/join, et les mots transfinis dans l’étude de la récursivité. Les langages rationnels de ces posets étiquetés sont définis à partir d’expressions et d’automates équivalents introduits par Bedon et Rispal, qui généralisent le cas des mots transfinis (Bruyère et Carton) et celui des posets finis (Lodaya et Weil). Dans cette thèse nous les étudions du point de vue de la logique. Nous généralisons en particulier le théorème de Büchi, Elgot et Trakhtenbrot, établissant pour le cas des langages de mots finis l’égalité entre la classe des langages rationnels et celle des langages définissables en logique monadique du second ordre (MSO). La logique mise en oeuvre est une extension de MSO par de l’arithmétique de Presburger. Nous nous intéressons également à certaines variétés d’algèbres de posets. Nous montrons que l’algèbre dont l’univers est la classe des posets série-parallèles transfinis et dont les opérations sont les produits séquentiel et parallèle finis et les produits (resp. puissances) ω et − ω est libre dans la variété correspondante V (resp. V 0). Nous en déduisons la liberté de la même algèbre sans le produit parallèle ou le produit − ω. Enfin, nous montrons que la théorie équationnelle de V 0 est décidable. Ce sont notamment des généralisations de résultats similaires de Bloom et Choffrut pour la variété d’algèbres de mots de longueur inférieure à ω!, de Choffrut et Ésik pour la variété d’algèbres de posets sans N dont les antichaînes sont finies et les chaînes sont de longueur inférieure à ω! et ceux de Bloom et Ésik pour la variété d’algèbres de mots sur les ordres linéaires dénombrables et dispersésWe study in this thesis structures extending the classical notion of word. They are built from a partially ordered set (poset) verifying the following properties : — they do not contain 4 distinct elements x, y, z, t whose relative order is exactly x < y, z < y, z < t (posets called N-free) ; — their chains are countable and scattered linear orderings ; — their antichains are finite ; and each element is labeled by a letter of a finite alphabet. Equivalently, the class of posets which we consider is the smallest one built from the empty poset and the singleton, and being closed under sequential and parallel products, and ω product and its backward ordering −ω (series-parallel posets). It is a generalization of both of finite series-parallel labeled posets, by adding infinity, and transfinite words, by weakening the total ordering of the elements to a partial ordering. In computer science, series-parallel posets find their interest in modeling concurrent processes based on fork/join primitives, and transfinite words in the study of recursion. The rational languages of these labeled posets are defined from expressions and equivalent automata introduced by Bedon and Rispal, which generalize thecase of transfinite words (Bruyère and Carton) and the one of finite posets (Lodaya and Weil). In this thesis we study such structures from the logic point of view. In particular, we generalize the Büchi-Elgot-Trakhtenbrot theorem, establishing in the case of finite words the correspondence between the class of rational languages and the one of languages definable in monadic second order logic (MSO). The implemented logic is an extension of MSO by Presburger arithmetic. We focus on some varieties of posets algebras too. We show that the algebra whose universe is the class of transfinite series-parallel posets and whose operations are the sequential and parallel products and the ω and −ω products (resp. powers) is free in the corresponding variety V (resp. V 0). We deduce the freeness of the same algebra without parallel or −ω product. Finally, we showthat the equational theory of V 0 is decidable. These results are, in particular, generalizations of similar results of Bloom and Choffrut on the variety of algebras of words whose length are less than ω!, of Choffrut and Ésik on the variety of algebras of N-free posets whose antichains are finite and whose chains are less than ω! and those of Bloom and Ésik on the variety of algebras of words indexed by countable and scattered linear orderings
29
Johnson, Robert David. "Parallel analytic tableaux systems." Thesis, Queen Mary, University of London, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.362777.
Full text
30
Katiker, Rushikesh. "Automatic generation of dynamic parallel architectures." Click here for download, 2007. http://proquest.umi.com/pqdweb?did=1475182071&sid=1&Fmt=2&clientId=3260&RQT=309&VName=PQD.
Full text
31
Carr, David A. "Towards automatic parallel game engine architectures." abstract and full text PDF (UNR users only), 2009. http://0-gateway.proquest.com.innopac.library.unr.edu/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:1464428.
Full text
32
Henriksson, Lovisa, and Victor Lundell. "Self Parking Robot : Automated Parallel Parking." Thesis, KTH, Maskinkonstruktion (Inst.), 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-226666.
Full textAbstract:
The purpose of this report is to examine how a self parallelparking robot performs using a pre defined parkingpath, compared to recommendations manual parking. Toexamine this a robot capable of parallel parking have beenconstructed.The project is divided into two parts; construction ofthe vehicle and the software which controls it. The design ofthe vehicle is based on a rear wheel driven car with Ackermannsteering. Localisation of a parking spot, parking andautomatic stopping at an unexpected obstacle is handledwith the help of three distance sensors.The robot was successful in 85% of the test conducted.Syftet med denna rapport är att undersöka hur bra en självparkeranderobot presterar när den fickparkerar med en förprogrammeradväg, jämfört med rekommedationer manuellparkering. För att undersöka detta har en robot kapabeltill att fickparkera konstruerats.Projektet består av två delar; konstruktion av roboten,samt mjukvaran som kontrollerar den. Konstruktionenär baserad på en bakhjulsdriven bil med Ackermannstyrning.Lokalisering av parkeringsplats, parkering samt automatisktstopp vid oväntat hinder hanteras med hjälp av trestycken avståndssensorer.Roboten var framgångsrik i 85% av testerna som utfördes
33
Dorman, Andrei. "Concurrency in Interaction Nets and Graph Rewriting." Phd thesis, Université Paris-Nord - Paris XIII, 2013. http://tel.archives-ouvertes.fr/tel-00937224.
Full textAbstract:
Ce travail est une étude approfondie de la concurrence dans les extensions non-déterministes des réseaux d'interaction de Lafont (langage graphique qui représente, lui, le calcul fonctionnel). Ces extensions sont de trois sortes : les réseaux multirègles, multiports et multifils, et leurs combinaisons donnent ainsi sept types de réseaux. Un premier travail consiste à déterminer une bonne sémantique pour pouvoir comparer ces extensions. On cherche à définir un sémantique opérationnelle structurelle sur les réseaux en se basant sur des technique connues de réécriture des graphes, plus particulièrement celle de " double-pushout with borrowed contexts ". Nous définissons à partir de cette méthode un système d'étiquetage des transitions donné par des règles de dérivations dans le style des langages de processus qui sont le paradigme principal pour étudier les systèmes de calcul concurrents. Nous définissons de plus une sémantique observationnelle sur les réseaux basée sur une notion paramétrique de barbe, qui permet enfin de donner avec précision une notion de traduction entre systèmes. On considère qu'une extension est plus expressive qu'une autre si tout langage de la seconde peut être traduit dans un langage de la première. Ceci nous permet de classer l'ensemble des extensions de manière hiérarchique en trois groupe selon la possibilité de traduire un système de réseau dans un autre. Du plus fort au plus faible : les réseaux contenant des multiports ; ensuite ceux contenant des multifils; enfin les réseaux multirègles. Ceci nous permet de donner un langage universel pour les réseaux dont l'étude donne un point de vue neuf sur les briques fondamentales de la concurrence.
34
Williams, Kenneth Peter. "Evolutionary algorithms for automatic parallelization." Thesis, University of Reading, 1998. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.265665.
Full text
35
Diarra, Rokiatou. "Automatic Parallelization for Heterogeneous Embedded Systems." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLS485.
Full textAbstract:
L'utilisation d'architectures hétérogènes, combinant des processeurs multicoeurs avec des accélérateurs tels que les GPU, FPGA et Intel Xeon Phi, a augmenté ces dernières années. Les GPUs peuvent atteindre des performances significatives pour certaines catégories d'applications. Néanmoins, pour atteindre ces performances avec des API de bas niveau comme CUDA et OpenCL, il est nécessaire de réécrire le code séquentiel, de bien connaître l’architecture des GPUs et d’appliquer des optimisations complexes, parfois non portables. D'autre part, les modèles de programmation basés sur des directives (par exemple, OpenACC, OpenMP) offrent une abstraction de haut niveau du matériel sous-jacent, simplifiant ainsi la maintenance du code et améliorant la productivité. Ils permettent aux utilisateurs d’accélérer leurs codes séquentiels sur les GPUs en insérant simplement des directives. Les compilateurs d'OpenACC/OpenMP ont la lourde tâche d'appliquer les optimisations nécessaires à partir des directives fournies par l'utilisateur et de générer des codes exploitant efficacement l'architecture sous-jacente. Bien que les compilateurs d'OpenACC/OpenMP soient matures et puissent appliquer certaines optimisations automatiquement, le code généré peut ne pas atteindre l'accélération prévue, car les compilateurs ne disposent pas d'une vue complète de l'ensemble de l'application. Ainsi, il existe généralement un écart de performance important entre les codes accélérés avec OpenACC/OpenMP et ceux optimisés manuellement avec CUDA/OpenCL. Afin d'aider les programmeurs à accélérer efficacement leurs codes séquentiels sur GPU avec les modèles basés sur des directives et à élargir l'impact d'OpenMP/OpenACC dans le monde universitaire et industrielle, cette thèse aborde plusieurs problématiques de recherche. Nous avons étudié les modèles de programmation OpenACC et OpenMP et proposé une méthodologie efficace de parallélisation d'applications avec les approches de programmation basées sur des directives. Notre expérience de portage d'applications a révélé qu'il était insuffisant d'insérer simplement des directives de déchargement OpenMP/OpenACC pour informer le compilateur qu'une région de code particulière devait être compilée pour être exécutée sur la GPU. Il est essentiel de combiner les directives de déchargement avec celles de parallélisation de boucle. Bien que les compilateurs actuels soient matures et effectuent plusieurs optimisations, l'utilisateur peut leur fournir davantage d'informations par le biais des clauses des directives de parallélisation de boucle afin d'obtenir un code mieux optimisé. Nous avons également révélé le défi consistant à choisir le bon nombre de threads devant exécuter une boucle. Le nombre de threads choisi par défaut par le compilateur peut ne pas produire les meilleures performances. L'utilisateur doit donc essayer manuellement différents nombres de threads pour améliorer les performances. Nous démontrons que les modèles de programmation OpenMP et OpenACC peuvent atteindre de meilleures performances avec un effort de programmation moindre, mais les compilateurs OpenMP/OpenACC atteignent rapidement leur limite lorsque le code de région déchargée a une forte intensité arithmétique, nécessite un nombre très élevé d'accès à la mémoire globale et contient plusieurs boucles imbriquées. Dans de tels cas, des langages de bas niveau doivent être utilisés. Nous discutons également du problème d'alias des pointeurs dans les codes GPU et proposons deux outils d'analyse statiques qui permettent d'insérer automatiquement les qualificateurs de type et le remplacement par scalaire dans le code sourceRecent years have seen an increase of heterogeneous architectures combining multi-core CPUs with accelerators such as GPU, FPGA, and Intel Xeon Phi. GPU can achieve significant performance for certain categories of application. Nevertheless, achieving this performance with low-level APIs (e.g. CUDA, OpenCL) requires to rewrite the sequential code, to have a good knowledge of GPU architecture, and to apply complex optimizations that are sometimes not portable. On the other hand, directive-based programming models (e.g. OpenACC, OpenMP) offer a high-level abstraction of the underlying hardware, thus simplifying the code maintenance and improving productivity. They allow users to accelerate their sequential codes on GPU by simply inserting directives. OpenACC/OpenMP compilers have the daunting task of applying the necessary optimizations from the user-provided directives and generating efficient codes that take advantage of the GPU architecture. Although the OpenACC / OpenMP compilers are mature and able to apply some optimizations automatically, the generated code may not achieve the expected speedup as the compilers do not have a full view of the whole application. Thus, there is generally a significant performance gap between the codes accelerated with OpenACC/OpenMP and those hand-optimized with CUDA/OpenCL. To help programmers for speeding up efficiently their legacy sequential codes on GPU with directive-based models and broaden OpenMP/OpenACC impact in both academia and industry, several research issues are discussed in this dissertation. We investigated OpenACC and OpenMP programming models and proposed an effective application parallelization methodology with directive-based programming approaches. Our application porting experience revealed that it is insufficient to simply insert OpenMP/OpenACC offloading directives to inform the compiler that a particular code region must be compiled for GPU execution. It is highly essential to combine offloading directives with loop parallelization constructs. Although current compilers are mature and perform several optimizations, the user may provide them more information through loop parallelization constructs clauses in order to get an optimized code. We have also revealed the challenge of choosing good loop schedules. The default loop schedule chosen by the compiler may not produce the best performance, so the user has to manually try different loop schedules to improve the performance. We demonstrate that OpenMP and OpenACC programming models can achieve best performance with lesser programming effort, but OpenMP/OpenACC compilers quickly reach their limit when the offloaded region code is computed/memory bound and contain several nested loops. In such cases, low-level languages may be used. We also discuss pointers aliasing problem in GPU codes and propose two static analysis tools that perform automatically at source level type qualifier insertion and scalar promotion to solve aliasing issues
36
García, Almiñana Jordi. "Automatic data distribution for massively parallel processors." Doctoral thesis, Universitat Politècnica de Catalunya, 1997. http://hdl.handle.net/10803/5981.
Full textAbstract:
Massively Parallel Processor systems provide the required computational power to solve most large scale High Performance Computing applications. Machines with physically distributed memory allow a cost-effective way to achieve this performance, however, these systems are very diffcult to program and tune. In a distributed-memory organization each processor has direct access to its local memory, and indirect access to the remote memories of other processors. But the cost of accessing a local memory location can be more than one order of magnitude faster than accessing a remote memory location. In these systems, the choice of a good data distribution strategy can dramatically improve performance, although different parts of the data distribution problem have been proved to be NP-complete.The selection of an optimal data placement depends on the program structure, the program's data sizes, the compiler capabilities, and some characteristics of the target machine. In addition, there is often a trade-off between minimizing interprocessor data movement and load balancing on processors. Automatic data distribution tools can assist the programmer in the selection of a good data layout strategy. These use to be source-to-source tools which annotate the original program with data distribution directives.
Crucial aspects such as data movement, parallelism, and load balance have to be taken into consideration in a unified way to efficiently solve the data distribution problem.
In this thesis a framework for automatic data distribution is presented, in the context of a parallelizing environment for massive parallel processor (MPP) systems. The applications considered for parallelization are usually regular problems, in which data structures are dense arrays. The data mapping strategy generated is optimal for a given problem size and target MPP architecture, according to our current cost and compilation model.
A single data structure, named Communication-Parallelism Graph (CPG), that holds symbolic information related to data movement and parallelism inherent in the whole program, is the core of our approach. This data structure allows the estimation of the data movement and parallelism effects of any data distribution strategy supported by our model. Assuming that some program characteristics have been obtained by profiling and that some specific target machine features have been provided, the symbolic information included in the CPG can be replaced by constant values expressed in seconds representing data movement time overhead and saving time due to parallelization. The CPG is then used to model a minimal path problem which is solved by a general purpose linear 0-1 integer programming solver. Linear programming techniques guarantees that the solution provided is optimal, and it is highly effcient to solve this kind of problems.
The data mapping capabilities provided by the tool includes alignment of the arrays, one or two-dimensional distribution with BLOCK or CYCLIC fashion, a set of remapping actions to be performed between phases if profitable, plus the parallelization strategy associated.
The effects of control flow statements between phases are taken into account in order to improve the accuracy of the model. The novelty of the approach resides in handling all stages of the data distribution problem, that traditionally have been treated in several independent phases, in a single step, and providing an optimal solution according to our model.
37
Tregidgo, R. W. S. "Parallel processing and automatic postal address recognition." Thesis, University of Essex, 1992. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.304946.
Full text
38
Prager, Richard William. "Parallel processing networks for automatic speech recognition." Thesis, University of Cambridge, 1987. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.238443.
Full text
39
Noual, Mathilde. "Mises à jour de réseaux d'automates." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2012. http://tel.archives-ouvertes.fr/tel-00726560.
Full textAbstract:
Cette thèse s'intéresse aux évènements et aux ordonnancements d'évènements se produisant au sein de réseaux d'éléments conceptuels prédéterminés. Dans ces réseaux, les éléments, appelés plutôt "automates", s'incitent les uns les autres à changer d'état en accord avec des règles prédéfinies qui, précisément, définissent le (fonctionnement du) réseau. Lorsqu'un automate se conforme effectivement aux influences qu'il reçoit de la part des autres, on dit que son état est mis à jour. Les évènements élémentaires considérés sont les changements d'états des automates. Définir un mode de mise à jour pour l'ensemble des automates d'un réseau permet de sélectionner certains évènements parmi l'ensemble de ceux qui sont a priori possibles. Cela permet aussi d'organiser et d'ordonner les évènements les uns par rapport aux autres de façon, par exemple, à imposer que des évènements indépendants se produisent simultanément ou simplement, de manière assez rapprochée pour qu'aucun autre événement ne puisse se produire pendant leur occurrence. Informellement, les modes de mise à jour peuvent donc être interprétés comme l'expression d'influences extérieures au réseau interdisant certains changements, ou alors comme la formalisation d'une version relâchée et relative de l'écoulement de temps. Cette thèse propose d'étudier leur influence sur le comportement des réseaux. Et afin de distinguer cette influence de celle de la structure des réseaux, elle commence par mettre en évidence le rôle de certains motifs structurels. Après ça, elle s'intéresse en particulier à l'information "encodée" dans une séquence de mises à jour et à l'impact du synchronisme dans celles-ci.
40
Grente, Theo. "Caractérisation et programmation en théorie des langages et en logique des classes de complexité efficace des automates cellulaires." Thesis, Normandie, 2020. http://www.theses.fr/2020NORMC214.
Full textAbstract:
Les automates cellulaires constituent le modèle de calcul parallèle et local par excellence.Comme pour tout modèle du parallélisme, leur programmation est réputée difficile. La puissance de calcul des automates cellulaires, modèle le plus simple du parallélisme, est attestée par le fait que nombre de problèmes significatifs sont calculés en temps minimal, appelé temps-réel, surautomate cellulaire.Principal résultat de cette thèse, on démontre des liens exacts (des équivalences) entre d’un côté la complexité descriptive, essentiellement la définissabilité en logique du second ordre existentiel sur des formules de Horn, de l’autre les classes de complexité en temps-réel des automates cellulaires.Au-delà de cette caractérisation en logique de la complexité en temps minimal, la thèse établit une méthode de programmation parallèle. Cette méthode consiste dans un premier temps à programmer dans nos logiques de Horn l’induction résolvant un problème, puis dans un secondtemps, à appliquer un processus automatique aboutissant au programme de l’automate cellulaire résolvant le problème. Pour justifier l’intérêt de la méthode, la thèse présente un ensemble de programmes logiques pour une variété représentative de problèmes classiques connus pour êtrecalculables en temps-réel sur automates cellulaires.Par ailleurs, toujours en passant par nos logiques, on prouve divers résultats liant le temps-réel des automates cellulaires et les grammaires formelles. Typiquement, tout langage généré par une grammaire algébrique et, plus généralement, une grammaire conjonctive d’Okhotin, est reconnu en temps-réel sur un automate cellulaire de dimension 2Cellular automata constitute the model of parallel and local computation by excellence.As for any model of parallelism, their programming is known to be difficult. The computingpower of cellular automata, the simplest model of parallelism, is attested by the fact that manysignificant problems are computed in minimal time, called real-time, on cellular automata.The main result of this thesis is the demonstration of exact links (equivalences) between, on onehand, the descriptive complexity, essentially the definability in existential second order logic on Horn formulas, and, on the other hand, the real-time complexity classes of cellular automata.Beyond this characterization in logic of the complexity in minimal time, the thesis establishes a method of parallel programming. This method consists first of all in programming in our Horn ogics the induction solving a problem, then in a second step, in applying an automatic process leading to the program of the cellular automaton solving the problem. To justify the interest of the method, the thesis presents a set of logic programs for a representative variety of classical problems known to be computable in real-time on cellular automata.In addition, we prove various results linking the real time of cellular automata and formal grammars. Typically, any language generated by an algebraic grammar and, more generally, an Okhotin conjunctive grammar, is recognized in real-time on a 2-dimensional cellular automaton
41
Chen, Xian. "Automatic parallelisation for a class of URE problems." Thesis, University of Newcastle Upon Tyne, 1995. http://hdl.handle.net/10443/1974.
Full textAbstract:
This thesis deals with the methodology and software of automatic parallelisation for numerical supercomputing and supercomputers. Basically, we focus on the problem of Uniform Recurrence Equations (URE) which exists widely in numerical computations. vVepropose a complete methodology of automatic generation of parallel programs for regular array designs. The methodology starts with an introduction of a set of canonical dependencies which generates a general modelling of the various URE problems. Based on these canonical dependencies, partitioning and mapping methods are developed which gives the foundation of the universal design process. Using the theoretical results we propose the structures of parallel programs and eventually generate automatically parallel codes which run correctly and efficiently on transputer array. The achievements presented in this thesis can be regarded as a significant progress in the area of automatic generation of parallel codes and regular (systolic) array design. This methodology is integrated and self-contained, and may be the only practical working package in this area.
42
Fleurisson, Romain. "Modélisation multi-échelle parallélisée pour la prédiction de structures de grains dendritiques couplant les éléments finis, un automate cellulaire et un réseau de paraboles." Thesis, Paris Sciences et Lettres (ComUE), 2019. http://www.theses.fr/2019PSLEM028/document.
Full textAbstract:
La modélisation multi-échelle des procédés de solidification présente un grand intérêt pour les industries. Toutefois, il est difficile de coupler les phénomènes prenant place à de multiples échelles pour obtenir des simulations quantitatives à grande échelle. Ceci est réalisé en combinant trois méthodes : les éléments finis (FE), un automate cellulaire (CA) et la méthode Parabolic Thick Needle(PTN). La méthode FE permet une résolution des équations de conservation écrites pour des quantités moyennées, ce qui est adapté aux calculs de grands domaines. Elle permet la description macroscopique des transferts de chaleur et de masse. De plus, la méthode CA permet de suivre le développement de l’enveloppe de chaque grain dendritique à une échelle mésoscopique. Le couplage de ces deux méthodes est le modèle CAFE et il a démontré son efficacité pour simuler quantitativement la solidification et notamment la transition colonnaire - équiaxe. Le Dendritic Needle Network (DNN) est une méthode mésoscopique introduite récemment. Celle-ci s’appuie sur la conservation de la masse de soluté à proximité des pointes dendritiques pour calculer avec précision leur cinétique de croissance. Comme cette méthode repose sur l’estimation directe du gradient de composition à l’interface solide/liquide, le régime de croissance n’est plus supposé stationnaire. Nous introduisons la méthode Parabolic Thick Needle PTN reprenant la méthode de croissance du DNN pour une pointe. Elle est implémentée avec une méthode des éléments finis pour résoudre le flux de soluté est largement validé par rapport aux résultats analytiques provenant de la solution d’Ivantsov. Le couplage du CAFE avec la cinétique de croissance provenant du PTN permet d’obtenir un modèle unique de solidification s’appuyant sur 3 échelles. La grille CA gère à la fois la forme des enveloppes des grains et les mécanismes de ramification. Le maillage FE est utilisé pour résoudre les problèmes de flux et de conservation de masse et d’énergie à la fois à l’échelle de la couche de soluté de la pointe et à l’échelle du domaine simulé. Ceci est rendu possible grâce à une stratégie de remaillage anisotrope multi-critères. Diverses simulations démontrent les capacités du modèle. Les pistes d’amélioration sont développées pour espérer, à terme, une simulation 3D d’expériences de laboratoireMultiscale modelling of solidification processes is of great interest for industries. However coupling the multiple scale phenomena to reach quantitative large simulations is challenging. This is achieved using a combination of three methods : the Finite Element (FE), the Cellular Automaton (CA) and the Parabolic Thick Needle (PTN). The FE method provides a solution of the conservation equations, written for volume average quantities, that is suitable for large domain size computations. It serves for macroscopic description of heat and mass transfers. Additionally, the CA method tracks the development of the envelope of each individual dendritic grain at a mesoscopic scale. The coupling of these two methods is the CAFE model and was demonstrated to provide efficient and quantitative simulations of the columnar-to-equiaxed transition for instance. The Dendritic Needle Network (DNN) is another mesoscopic method recently introduced. It uses solute mass balance considerations in the vicinity of the tip of the dendrites to compute accurately the growth kinetics. Because it relies on adirect estimation of the composition gradient at the solid-liquid interface, steady state growth regime is no longer assumed. We introduce the Parabolic Thick Needle (PTN) method inspired from the DNN’s computed growth idea for one dendritetip. Its implementation with a FE method to solve the solute flow is extensively validated against analytical results given by the Ivantsov solution. Coupling CAFE with PTN computed growth kinetics provides a unique solidification model. The CA grid handles both the shape of the grain envelopes and branching mechanisms. The FE mesh is used to solve flux and conservation of mass and energy at both the scale of the dendrite tip solute layer and the domain dimensions. It is possible thanks to adaptive remeshing strategies. Various simulations demonstrate the capabilities of the model. The improvement areas are being developed in order to hope, in the long term, for 3D simulation laboratory experiments
43
Li, Li. "Model-based automatic performance diagnosis of parallel computations /." view abstract or download file of text, 2007. http://proquest.umi.com/pqdweb?did=1335366371&sid=1&Fmt=2&clientId=11238&RQT=309&VName=PQD.
Full textAbstract:
Thesis (Ph. D.)--University of Oregon, 2007.Typescript. Includes vita and abstract. Includes bibliographical references (leaves 119-123). Also available for download via the World Wide Web; free to University of Oregon users.
44
Ikei, Mitsuru. "Automatic program restructuring for distributed memory multicomputers." Full text open access at:, 1992. http://content.ohsu.edu/u?/etd,191.
Full text
45
Barbosa, Jorge Luis Victoria. "Granlog : um modelo para analise automatica de granulosidade na programacao em logica." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 1996. http://hdl.handle.net/10183/21343.
Full textAbstract:
A exploração do paralelismo na programação em lógica e considerada uma alternativa para simplificação da programação de maquinas paralelas e para aumento do desempenho de programas em lógica. Desta forma, a integração da programação em lógica e sistemas paralelos tornou-se nos últimos anos um centro de atenções da comunidade ciêntifica. Dentre os problemas que devem ser solucionados para exploração adequada do paralelismo, encontra-se a analise de granulosidade. A análise de granulosidade determina o tamanho dos grãos, ou seja, a complexidade dos módulos que devendo ser executados seqüencialmente num único processador. Basicamente, esta analise consiste de uma refinada identificação dos grãos, visando a máxima eficiência na exploração do paralelismo. Neste sentido, devem ser realizadas considerações sobre dependências, complexidade dos grãos e custos envolvidos na paralelização. Recentemente, a analise de granulosidade na programação em lógica tem recebido atenção especial por parte dos pesquisadores. Os grãos podem ser identificados pelo programador através de primitivas de programação ou podem ser detectados automaticamente pelo sistema paralelo. Na programação em lógica, a exploração automática do paralelismo é estimulada, devido ao paralelismo implícito existente na avaliação das expressões lógicas. Além disso, a programação em lógica permite uma clara distinção entre a semântica e o controle da linguagem, proporcionando uma abordagem distinta entre a descrição do problema e o caminho para obtenção das soluções. A detecção automática do paralelismo permite o aproveitamento de programas já existentes, alem de liberar o programador do encargo de paralelizar o problema. Este trabalho dedica-se ao estudo da analise automática de granulosidade na programação em lógica. O texto propõe um modelo para geração de informações de granulosidade, denominado GRANLOG (GRanularty ANalyzer for LOGic Programming). O GRANLOG realiza uma analise estática de um programa em 16aica. Dessa analise resulta o programa granulado, ou seja, o programa original acrescido da anotação de granulosidade. Esta anotação contem diversas informações que contribuem de forma significativa com a exploração adequada do paralelismo na programação em lógica. Durante o desenvolvimento do GRANLOG foram exploradas diversas áreas de pesquisa da programação em lógica, dentre as quais destacam-se: analise de modos, analise de tipos, análise de medidas para mensuração do tamanho de termos, interpretação abstrata, analise de dependências e analise de complexidade. A integração destes t6picos torna o GRANLOG uma rica fonte de pesquisa. Além disso, a organização modular da proposta permite o aprimoramento independente de suas partes, tornando a estrutura do modelo uma base para o desenvolvimento de novos trabalhos. Além do modelo, o texto descreve a implementação de um protótipo e propõe duas aplicações para as informações de granulosidade, ou seja, auxilio a decisões de escalonamento e simulação da execução de programas. O texto apresenta ainda uma proposta para integração do GRANLOG a um modelo para execução paralela de programas em lógica, denominado OPERA. O OPERA dedica-se a exploração do paralelismo na programação em lógica e possui atualmente um protótipo para execução paralela de programas em lógica em redes de computadores. Os bons resultados obtidos com a integração OPERA-GRANLOG demonstram a relevância das informações geradas pelo modelo proposto neste trabalho. Encontra-se ainda neste texto uma proposta para inclusão do GRANLOG numa interface gráfica, denominada XOPERA. Esta interface permite a execução do protótipo OPERA e, a partir deste trabalho, gerencia também o protótipo GRANLOG. A inclusão da gerencia do GRANLOG na interface XOPERA, contribui de forma substancial para a integração OPERA-GRANLOG.The exploitation of parallelism in logic programming is considered an alternative for simplifying the task of programming parallel machines. Also, it provides a way to increase the performance of logic programs. Because of this, integrating parallel systems with parallel programmin g has been a topic of much interest in the scientific comunity, in the last years. Among the problems that must be solved for the adequate exploitation of parallelism, there is the granularity analysis. Granularity analysis determines the size of the grains, that is, the complexity of the modules that must be sequentially executed in a single processor. Basically, this analysis consists of a refined identification of the grains, aiming the maximum efficiency in the parallelism exploitation. In this sense, considerations must be taken about dependencies, grain complexity and costs involved in the parallelizing process. Recently, many researchers have given special attention to the granularity analysis of logic programming. The grains may be identified by the programmer via programming primitives, or they may be automatically detected by the parallel system. In logic programming, the automatic exploitation of parallelism is stimulated, because of the implicit parallelism that exists in the evaluation of the logic expressions. Besides, logic programming allows a clear distinction between the semantics and the control of the language, providing a distinct approach between the problem description and the way to obtain the results. The automatic detection of parallelism permits the utilization of already written programs, also freeing the programmer from parallelizing the program by hand. This work is dedicated to the study of automatic granularity analysis in logic programming. The text proposes a model for generating granularity informations, called GRANLOG (GRanularity Analyzer for LOGic Programming). GRANLOG performs a static analysis of a logic program. From this analysis, it results a granulated program, that is, the original program increased by the granularity annotation. This annotation has several informations that contribute in a significant way to the adequate exploitation of parallelism in logic programming. During the development of GRANLOG, several research areas have been explored, namely, mode analysis, type analysis, measure analysis for measuring the size of terms, abstract interpretation, dependencies analysis and complexity analysis. The integration of these topics makes GRANLOG a good source for researchs. Besides, the modular organization proposed permits the independent improvement of its parts, making of the model structure, a base for the development of new works. Besides the model, the text describes the implementation of a prototype and proposes two applications for the granularity informations, namely, help in scheduling decisions and program execution simulation. It also presents a proposal for integrating GRANLOG to a parallel logic execution model for logic programming, called OPERA. OPERA is dedicated to the exploitation of parallelism in logic programming and, at the present time, has a prototype for parallel execution of logic programming in computer networks. The good results obtained by integrating OPERA and GRANLOG show the importance of the information generated by the model proposed in this work. There is, also, in this work, a proposal for including GRANLOG in a graphical interface, called XOPERA. This interface allows the execution of the OPERA prototype and, from now on, also manaaes the GRANLOG prototype. The inclusion of GRANLOG in the XOPERA interfaces substantially contributes to the OPERAGRANLOG intearation.
46
Törnfeldt, Tobias. "Graph Similarity, Parallel Texts, and Automatic Bilingual Lexicon Acquisition." Thesis, Linköping University, Department of Mathematics, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-11550.
Full textAbstract:
In this masters’ thesis report we present a graph theoretical method used for automatic bilingual lexicon acquisition with parallel texts. We analyze the concept of graph similarity and give an interpretation, of the parallel texts, connected to the vector space model. We represent the parallel texts by a directed, tripartite graph and from here use the corresponding adjacency matrix, A, to compute the similarity of the graph. By solving the eigenvalue problem ρS = ASAT + ATSA we obtain the self-similarity matrix S and the Perron root ρ. A rank k approximation of the self-similarity matrix is computed by implementations of the singular value decomposition and the non-negative matrix factorization algorithm GD-CLS. We construct an algorithm in order to extract the bilingual lexicon from the self-similarity matrix and apply a statistical model to estimate the precision, the correctness, of the translations in the bilingual lexicon. The best result is achieved with an application of the vector space model with a precision of about 80 %. This is a good result and can be compared with the precision of about 60 % found in the literature.
47
Chong, Michael Wai Hing. "Subword units and parallel processing for automatic speech recognition." Thesis, University of Cambridge, 1990. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.335663.
Full text
48
Silveira, Jaime Kirch da. "Parallel SAT solvers and their application in automatic parallelization." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2014. http://hdl.handle.net/10183/95373.
Full textAbstract:
Desde a diminuição da tendência de aumento na frequência de processadores, uma nova tendência surgiu para permitir que softwares tirem proveito de harwares mais rápidos: a paralelização. Contudo, diferente de aumentar a frequência de processadores, utilizar parallelização requer um tipo diferente de programação, a programação paralela, que é geralmente mais difícil que a programação sequencial comum. Neste contexto, a paralelização automática apareceu, permitindo que o software tire proveito do paralelismo sem a necessidade de programação paralela. Nós apresentamos aqui duas propostas: SAT-PaDdlinG e RePaSAT. SAT-PaDdlinG é um SAT Solver DPLL paralelo que roda em GPU, o que permite que RePaSAT utilize esse ambiente. RePaSAT é a nossa proposta de uma máquina paralela que utiliza o Problema SAT para paralelizar automaticamente código sequencial. Como uma GPU provê um ambiente barato e massivamente paralelo, SAT-PaDdlinG tem como objetivo prover esse paralelismo massivo a baixo custo para RePaSAT, como para qualquer outra ferramenta ou problema que utilize SAT Solvers.Since the slowdown in improvement in the frequency of processors, a new tendency has arisen to allow software to take advantage of faster hardware: parallelization. However, different from increasing the frequency of processors, using parallelization requires a different kind of programming, parallel programming, which is usually harder than common sequential programming. In this context, automatic parallelization has arisen, allowing software to take advantage of parallelism without the need of parallel programming. We present here two proposals: SAT-PaDdlinG and RePaSAT. SAT-PaDdlinG is a parallel DPLL SAT Solver on GPU, which allows RePaSAT to use this environment. RePaSAT is our proposal of a parallel machine that uses the SAT Problem to automatically parallelize sequential code. Because GPU provides a cheap, massively parallel environment, SATPaDdlinG aims at providing this massive parallelism and low cost to RePaSAT, as well as to any other tool or problem that uses SAT Solvers.
49
SEYD, DARWISH IYAD. "Etude et realisation d'un automate cellulaire opto-electronique parallele." Paris 11, 1991. http://www.theses.fr/1991PA112331.
Full textAbstract:
Les automates cellulaires, composes d'un grand nombre de processeurs elementaires, permettent un traitement rapide et efficace de certaines algorithmes. Le present travail etudie la possibilite d'une implantation parallele d'un tel automate sur un circuit integre avec des entrees optiques en utilisant des photodiodes integrees et un illuminateur de tableaux et des sorties opto-electroniques avec des modulateurs a puits quantiques multiples. Differents composants ont ete etudies et realises dans ce but: illuminateur de tableaux realise sur un hologramme en utilisant l'effet d'imagerie de talbot. Une amelioration des aberrations chromatiques est proposee en changeant les conditions d'enregistrement; circuit electronique integree vlsi contenant un seul processeur elementaire avec des photodiodes integrees pour les entrees optiques et les plots de sortie speciaux pour les modulateurs; modulateurs opto-electroniques a puits quantiques multiples. Un montage experimental a ete realise en eclairant une photodiode avec une diode laser a 999 nm. L'estimation des performances de l'automate propose montre sa haute capacite de calcul et de connexion
50
Zhao, Jie. "Une approche combinée langage-polyédrique pour la programmation parallèle hétérogène." Thesis, Paris Sciences et Lettres (ComUE), 2018. http://www.theses.fr/2018PSLEE062.
Full textAbstract:
De nos jours, l'optimisation des compilateurs est de plus en plus mise à l'épreuve par la diversité des langages de programmation et l'hétérogénéité des architectures. Le modèle polyédrique est un puissant cadre mathématique permettant aux programmes d’exploiter la parallélisation automatique et l’optimisation de la localité, jouant un rôle important dans le domaine de l’optimisation des compilateurs. Une limite de longue date du modèle réside dans sa restriction aux programmes affines à contrôle statique, ce qui a entraîné une demande émergente de prise en charge d'extensions non affines. Cela est particulièrement aigu dans le contexte d'architectures hétérogènes où une variété de noyaux de calcul doivent être analysés et transformés pour répondre aux contraintes des accélérateurs matériels et pour gérer les transferts de données à travers des espaces mémoire. Nous explorons plusieurs extensions non affines du modèle polyhédral, dans le contexte d'un langage intermédiaire bien défini combinant des éléments affines et syntaxiques. D'un côté, nous expliquons comment les transformations et la génération de code pour des boucles avec des limites de boucle dynamiques non dépendantes des données et dynamiques sont intégrées dans un cadre polyédrique, élargissant ainsi le domaine applicable de la compilation polyédrique dans le domaine des applications non affines. D'autre part, nous décrivons l'intégration du pavage en recouvrement pour les calculs de pochoir dans un cadre polyhédral général, en automatisant les transformations non affines dans la compilation polyhédrique. Nous évaluons nos techniques sur des architectures de CPU et de GPU, en validant l'efficacité des optimisations en effectuant une comparaison approfondie des performances avec des frameworks et des librairies écrites à la pointe de la technologieNowadays, optimizing compilers are increasingly challenged by the diversity of programming languages and heterogeneity of architectures. The polyhedral model is a powerful mathematical framework for programs to exploit automatic parallelization and locality optimization, playing an important role in the field of optimizing compilers. A long standing limitation of the model has been its restriction to static control affine programs, resulting in an emergent demand for the support of non-affine extensions. This is particularly acute in the context of heterogeneous architectures where a variety of computation kernels need to be analyzed and transformed to match the constraints of hardware accelerators and to manage data transfers across memory spaces. We explore multiple non-affine extensions of the polyhedral model, in the context of a welldefined intermediate language combining affine and syntactic elements. On the one hand, we explain how transformations and code generation for loops with non-affine, data-dependent and dynamic loop bounds are integrated into a polyhedral framework, extending the applicable domain of polyhedral compilation in the realm of non-affine applications. On the other hand, we describe the integration of overlapped tiling for stencil computations into a general polyhedral framework, automating non-affine transformations in polyhedral compilation. We evaluate our techniques on both CPU and GPU architectures, validating the effectiveness of the optimizations by conducting an in-depth performance comparison with state-of-the-art frameworks and manually-written libraries