Dissertations / Theses on the topic 'Parallelisation'
To see the other types of publications on this topic, follow the link: Parallelisation.
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 'Parallelisation.'
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
Schuilenburg, Alexander Marius. "Parallelisation of algorithms." Master's thesis, University of Cape Town, 1990. http://hdl.handle.net/11427/22211.
Full textAbstract:
Most numerical software involves performing an extremely large volume of algebraic computations. This is both costly and time consuming in respect of computer resources and, for large problems, often super-computer power is required in order for results to be obtained in a reasonable amount of time. One method whereby both the cost and time can be reduced is to use the principle "Many hands make light work", or rather, allow several computers to operate simultaneously on the code, working towards a common goal, and hopefully obtaining the required results in a fraction of the time and cost normally used. This can be achieved through the modification of the costly, time consuming code, breaking it up into separate individual code segments which may be executed concurrently on different processors. This is termed parallelisation of code. This document describes communication between sequential processes, protocols, message routing and parallelisation of algorithms. In particular, it deals with these aspects with reference to the Transputer as developed by INMOS and includes two parallelisation examples, namely parallelisation of code to study airflow and of code to determine far field patterns of antennas. This document also reports on the practical experiences with programming in parallel.
2
Calinescu, Radu C. "Architecture-independent loop parallelisation." Thesis, University of Oxford, 1998. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.299406.
Full text
3
Orange, David Joseph. "Parallelisation on MIMD architectures." Thesis, University of Liverpool, 1992. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.317211.
Full text
4
Nagy, Lesleis. "Parallelisation of micromagnetic simulations." Thesis, University of Edinburgh, 2016. http://hdl.handle.net/1842/20433.
Full textAbstract:
The field of paleomagnetism attempts to understand in detail the the processes of the Earth by studying naturally occurring magnetic samples. These samples are quite unlike those fabricated in the laboratory. They have irregular shapes; they have been squeezed and stretched, heated and cooled and subjected to oxidation. However micromagnetic modelling allows us to simulate such samples and gain some understanding of how a paleomagnetic signal is acquired and how it is retained. Micromagnetics provides a theory for understanding how the domain structure of a magnetic sample alters subject to what it is made from and the environment that it is in. It furnishes the mathematics that describe the energy of a given domain structure and how that domain structure evolves in time. Combining micromagnetics and ever increasing computer power, it has been possible to produce simulations of small to medium size grains within the so-called single to pseudo single domain state range. However processors are no longer built with increasing speed but with increasing parallelism and it is this that must be exploited to model larger and larger paleomagnetic samples. The purpose of the work presented here is twofold. Firstly a micromagnetics code that is parallel and scalable is presented. This code is based on FEniCS, an existing finite element framework, and is shown to run on ARCHER the UK’s national supercomputing service. The strategy of using existing libraries and frameworks allow future extension and inclusion of new science in the code base. In order to achieve scalability, a spatial mapping technique is used to calculate the demagnetising field - the most computationally intensive part of micromagnetic calculations. This allows grain geometries to be partitioned in such a way that no global communication is required between parallel processes - the source of favourable scaling behaviour. The second part of the theses presents an exploration of domain state evolution in increasing sizes of magnetite grains. This simulation, whilst a first approximation that excludes magneto-elastic effects, is the first attempt to map out the transition from pseudo-single domain states to multi domain states using a full micromagnetic simulation.
5
Zhou, Ruoyu. "Guided automatic binary parallelisation." Thesis, University of Cambridge, 2018. https://www.repository.cam.ac.uk/handle/1810/274753.
Full textAbstract:
For decades, the software industry has amassed a vast repository of pre-compiled libraries and executables which are still valuable and actively in use. However, for a significant fraction of these binaries, most of the source code is absent or is written in old languages, making it practically impossible to recompile them for new generations of hardware. As the number of cores in chip multi-processors (CMPs) continue to scale, the performance of this legacy software becomes increasingly sub-optimal. Rewriting new optimised and parallel software would be a time-consuming and expensive task. Without source code, existing automatic performance enhancing and parallelisation techniques are not applicable for legacy software or parts of new applications linked with legacy libraries. In this dissertation, three tools are presented to address the challenge of optimising legacy binaries. The first, GBR (Guided Binary Recompilation), is a tool that recompiles stripped application binaries without the need for the source code or relocation information. GBR performs static binary analysis to determine how recompilation should be undertaken, and produces a domain-specific hint program. This hint program is loaded and interpreted by the GBR dynamic runtime, which is built on top of the open-source dynamic binary translator, DynamoRIO. In this manner, complicated recompilation of the target binary is carried out to achieve optimised execution on a real system. The problem of limited dataflow and type information is addressed through cooperation between the hint program and JIT optimisation. The utility of GBR is demonstrated by software prefetch and vectorisation optimisations to achieve performance improvements compared to their original native execution. The second tool is called BEEP (Binary Emulator for Estimating Parallelism), an extension to GBR for binary instrumentation. BEEP is used to identify potential thread-level parallelism through static binary analysis and binary instrumentation. BEEP performs preliminary static analysis on binaries and encodes all statically-undecided questions into a hint program. The hint program is interpreted by GBR so that on-demand binary instrumentation codes are inserted to answer the questions from runtime information. BEEP incorporates a few parallel cost models to evaluate identified parallelism under different parallelisation paradigms. The third tool is named GABP (Guided Automatic Binary Parallelisation), an extension to GBR for parallelisation. GABP focuses on loops from sequential application binaries and automatically extracts thread-level parallelism from them on-the-fly, under the direction of the hint program, for efficient parallel execution. It employs a range of runtime schemes, such as thread-level speculation and synchronisation, to handle runtime data dependences. GABP achieves a geometric mean of speedup of 1.91x on binaries from SPEC CPU2006 on a real x86-64 eight-core system compared to native sequential execution. Performance is obtained for SPEC CPU2006 executables compiled from a variety of source languages and by different compilers.
6
Jouvelot, Pierre. "Parallelisation semantique : une approche denotationnelle non-standard pour la parallelisation de programmes imperatifs sequentiels." Paris 6, 1986. http://www.theses.fr/1986PA066559.
Full textAbstract:
Notre principe consiste a voir les transformations de programmes introduites par la parllelisation comme definissant des semantiques denotationnelles non-standards du langage de programmation. Nous montrons comment utiliser ce concept pour detecter, dans un langage imperatif simplifie all, des instructions complexes parallelisables, reconnaitre des reductions et prendre en compte certains programmes avec indirections
7
Botinčan, Matko. "Formal verification-driven parallelisation synthesis." Thesis, University of Cambridge, 2018. https://www.repository.cam.ac.uk/handle/1810/274136.
Full textAbstract:
Concurrency is often an optimisation, rather than intrinsic to the functional behaviour of a program, i.e., a concurrent program is often intended to achieve the same effect of a simpler sequential counterpart, just faster. Error-free concurrent programming remains a tricky problem, beyond the capabilities of most programmers. Consequently, an attractive alternative to manually developing a concurrent program is to automatically synthesise one. This dissertation presents two novel formal verification-based methods for safely transforming a sequential program into a concurrent one. The first method---an instance of proof-directed synthesis---takes as the input a sequential program and its safety proof, as well as annotations on where to parallelise, and produces a correctly-synchronised parallelised program, along with a proof of that program. The method uses the sequential proof to guide the insertion of synchronisation barriers to ensure that the parallelised program has the same behaviour as the original sequential version. The sequential proof, written in separation logic, need only represent shape properties, meaning we can parallelise complex heap-manipulating programs without verifying every aspect of their behaviour. The second method proposes specification-directed synthesis: given a sequential program, we extract a rich, stateful specification compactly summarising program behaviour, and use that specification for parallelisation. At the heart of the method is a learning algorithm which combines dynamic and static analysis. In particular, dynamic symbolic execution and the computational learning technique grammar induction are used to conjecture input-output specifications, and counterexample-guided abstraction refinement to confirm or refute the equivalence between the conjectured specification and the original program. Once equivalence checking succeeds, from the inferred specifications we synthesise code that executes speculatively in parallel---enabling automated parallelisation of irregular loops that are not necessary polyhedral, disjoint or with a static pipeline structure.
8
Boulet, Pierre. "Outils pour la parallelisation automatique." Lyon, École normale supérieure (sciences), 1996. http://www.theses.fr/1996ENSL0013.
Full textAbstract:
La parallelisation automatique est une des approches visant a une plus grande facilite d'utilisation des ordinateurs paralleles. La parallelisation consiste a prendre un programme ecrit pour une machine sequentielle (qui n'a qu'un processeur) et de l'adapter a une machine parallele. L'interet de faire faire cette parallelisation automatiquement par un programme appele paralleliseur est qu'on pourrait alors reutiliser tout le code deja ecrit en fortran pour machine sequentielles, apres parallelisation, sur des machines paralleles. Nous n'y sommes pas encore, mais on s'en approche. C'est dans ce cadre que se situe mon travail. Une moitie approximativement de ma these est consacre a la realisation d'un logiciel qui parallelise automatiquement une classe reduite de programmes (les nids de boucles uniformes qui utilisent des translations comme acces aux tableaux de donnees) en hpf (high performance fortran). J'insiste surtout sur la partie generation de code hpf, qui est la partie la plus novatrice de ce programme. Outre la realisation de bouclettes, ma contribution au domaine est aussi theorique avec une etude sur un partitionnement des donnees appele pavage par des parallelepipedes et une etude de l'optimisation des calculs d'expressions de tableaux dans le langage high performance fortran. Le pavage est une technique permettant d'optimiser la taille des taches qu'on repartit sur les processeurs pour diminuer le temps passe en communications. L'evaluation d'expressions de tableaux est une etape d'optimisation du compilateur parallele (le programme qui traduit le code parallele ecrit dans un langage de haut niveau comme hpf en code machine directement executable par l'ordinateur parallele)
9
Tournavitis, Georgios. "Profile-driven parallelisation of sequential programs." Thesis, University of Edinburgh, 2011. http://hdl.handle.net/1842/5287.
Full textAbstract:
Traditional parallelism detection in compilers is performed by means of static analysis and more specifically data and control dependence analysis. The information that is available at compile time, however, is inherently limited and therefore restricts the parallelisation opportunities. Furthermore, applications written in C – which represent the majority of today’s scientific, embedded and system software – utilise many lowlevel features and an intricate programming style that forces the compiler to even more conservative assumptions. Despite the numerous proposals to handle this uncertainty at compile time using speculative optimisation and parallelisation, the software industry still lacks any pragmatic approaches that extracts coarse-grain parallelism to exploit the multiple processing units of modern commodity hardware. This thesis introduces a novel approach for extracting and exploiting multiple forms of coarse-grain parallelism from sequential applications written in C. We utilise profiling information to overcome the limitations of static data and control-flow analysis enabling more aggressive parallelisation. Profiling is performed using an instrumentation scheme operating at the Intermediate Representation (Ir) level of the compiler. In contrast to existing approaches that depend on low-level binary tools and debugging information, Ir-profiling provides precise and direct correlation of profiling information back to the Ir structures of the compiler. Additionally, our approach is orthogonal to existing automatic parallelisation approaches and additional fine-grain parallelism may be exploited. We demonstrate the applicability and versatility of the proposed methodology using two studies that target different forms of parallelism. First, we focus on the exploitation of loop-level parallelism that is abundant in many scientific and embedded applications. We evaluate our parallelisation strategy against the Nas and Spec Fp benchmarks and two different multi-core platforms (a shared-memory Intel Xeon Smp and a heterogeneous distributed-memory Ibm Cell blade). Empirical evaluation shows that our approach not only yields significant improvements when compared with state-of- the-art parallelising compilers, but comes close to and sometimes exceeds the performance of manually parallelised codes. On average, our methodology achieves 96% of the performance of the hand-tuned parallel benchmarks on the Intel Xeon platform, and a significant speedup for the Cell platform. The second study, addresses the problem of partially sequential loops, typically found in implementations of multimedia codecs. We develop a more powerful whole-program representation based on the Program Dependence Graph (Pdg) that supports profiling, partitioning and codegeneration for pipeline parallelism. In addition we demonstrate how this enhances conventional pipeline parallelisation by incorporating support for multi-level loops and pipeline stage replication in a uniform and automatic way. Experimental results using a set of complex multimedia and stream processing benchmarks confirm the effectiveness of the proposed methodology that yields speedups up to 4.7 on a eight-core Intel Xeon machine.
10
Bratvold, Tore Andreas. "Skeleton-based parallelisation of functional programs." Thesis, Heriot-Watt University, 1994. http://hdl.handle.net/10399/1355.
Full text
11
Rybin, Pavel. "Speculative parallelisation with dynamic data structures." Thesis, University of Manchester, 2010. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.525935.
Full text
12
Silber, Georges-André. "Parallelisation automatique par insertion de directives." Lyon, École normale supérieure (sciences), 1999. http://www.theses.fr/1999ENSL0139.
Full textAbstract:
Dans cette these, nous nous sommes places dans le cadre de la parallelisation automatique par insertion de directives, c'est-a-dire des transformations de code au niveau du code source ou le parallelisme est exprime par des directives donnees au compilateur. Ce document expose trois apports a ce domaine. Les deux premiers apports sont des extensions au modele polyedrique de representation des nids de boucles imbriquees. La premiere extension se situe au niveau de la fonction objective. Notre objectif est la recherche de boucles completement permutables, transformation necessaire a une transformation appelee tiling permettant de modifier le grain de la parallelisation. La deuxieme extension presente un nouveau type de graphe, le graphe des dependances mixte, permettant de traiter les codes a controle non statique, c'est-a-dire les codes ou des expressions de structures de controle (if ou do) sont impliquees dans des dependances de donnees. En utilisant ce graphe, nous presentons une methode pour introduire de la memoire temporaire, ce qui permet de casser les antidependances impliquant des structures de controle. Le troisieme apport de cette these est un outil appele nestor destine a faciliter l'implantation de transformations source a source de programmes fortran. Une extension de l'algorithme de parallelisation d'allen, callahan et kennedy utilisant le graphe des dependances mixte a ete implantee dans notre outil.
13
Gdura, Youssef Omran. "A new parallelisation technique for heterogeneous CPUs." Thesis, University of Glasgow, 2012. http://theses.gla.ac.uk/3406/.
Full textAbstract:
Parallelization has moved in recent years into the mainstream compilers, and the demand for parallelizing tools that can do a better job of automatic parallelization is higher than ever. During the last decade considerable attention has been focused on developing programming tools that support both explicit and implicit parallelism to keep up with the power of the new multiple core technology. Yet the success to develop automatic parallelising compilers has been limited mainly due to the complexity of the analytic process required to exploit available parallelism and manage other parallelisation measures such as data partitioning, alignment and synchronization. This dissertation investigates developing a programming tool that automatically parallelises large data structures on a heterogeneous architecture and whether a high-level programming language compiler can use this tool to exploit implicit parallelism and make use of the performance potential of the modern multicore technology. The work involved the development of a fully automatic parallelisation tool, called VSM, that completely hides the underlying details of general purpose heterogeneous architectures. The VSM implementation provides direct and simple access for users to parallelise array operations on the Cell’s accelerators without the need for any annotations or process directives. This work also involved the extension of the Glasgow Vector Pascal compiler to work with the VSM implementation as a one compiler system. The developed compiler system, which is called VP-Cell, takes a single source code and parallelises array expressions automatically. Several experiments were conducted using Vector Pascal benchmarks to show the validity of the VSM approach. The VP-Cell system achieved significant runtime performance on one accelerator as compared to the master processor’s performance and near-linear speedups over code runs on the Cell’s accelerators. Though VSM was mainly designed for developing parallelising compilers it also showed a considerable performance by running C code over the Cell’s accelerators.
14
Mak, Jonathan Chee Heng. "Facilitating program parallelisation : a profiling-based approach." Thesis, University of Cambridge, 2011. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.609451.
Full text
15
BOURGET, DANIEL. "Compilation et parallelisation d'un langage sans variable." Paris 6, 1989. http://www.theses.fr/1989PA066673.
Full textAbstract:
Cette these decrit la compilation et la parallelisation d'un langage applicatif sans variables fonde sur la theorie des combinateurs: graal. Le langage ada a servi de support pour l'ecriture du compilateur. Le choix pour la generation du code du compilateur s'est egalement porte sur le langage ada afin de faciliter l'interfacage de programmes ecrits dans les deux langages. Nous offrons la possibilite de definir des fonctions ecrites dans le langage graal a l'interieur d'unite de programme ada. Nous avons ajoute au langage graal la notion de paquetage. La parallelisation du langage graal sur une machine a architecture von neumann a permis de mettre en evidence sa puissance de parallelisation. C'est l'utilisateur qui definit son propre degre de parallelisme, ou a defaut, il est possible d'avoir acces a une parallelisation automatique de toutes les fonctions susceptibles d'etre parallelisees. La version du compilateur sur transputer a mis en evidence les caracteres insuffisants de programmation repartie du langage ada
16
Collard, Jean-François, and L. BOUGE. "Parallelisation automatique des programmes a controle dynamique." Paris 6, 1995. http://www.theses.fr/1995PA066056.
Full textAbstract:
La parallelisation automatique de programmes imperatifs se limite generalement aux programmes a controle statique, c'est-a-dire aux programmes dont l'ensemble des operations et les dependances de donnees entre ces dernieres peuvent etre connus exactement lors de la compilation. Ces programmes sont typiquement des nids de boucles for. Dans ce cadre, un modele elegant de parallelisation a ete elabore ces dernieres annees, modele base sur la determination d'un echeancier d'execution des operations, ou ordonnancement. Le but de cette these est d'etendre ce modele aux programmes dont le flot de controle ne peut etre decrit lors de la compilation. Plus precisement, l'etude se restreint aux programmes dont le dynamisme du controle est du a la presence de boucles while et de tests. Dans ces circonstances, l'ensemble des operations ne peut plus etre predit et les dependances liees aux acces aux tableaux ne peuvent plus etre connues avec precision. De plus, lorsque les dependances de controle inhibent le parallelisme, nous proposons de ne pas tenir compte de ces dependances et d'executer les operations de maniere anticipee ou speculative. L'ordonnancement devra gerer l'imprecision des dependances de donnees et, eventuellement, le caractere speculatif de certaines executions
17
Dion, Michèle. "Alignement et distribution pour la parallelisation automatique." Lyon, École normale supérieure (sciences), 1996. http://www.theses.fr/1996ENSL0014.
Full textAbstract:
La programmation de machines massivement paralleles est difficile pour l'utilisateur non specialiste et le developpement de techniques automatisant partiellement l'ecriture de programmes paralleles est devenue une necessite. Les problemes d'ordonnancement et d'allocation sont connus pour etre difficiles mais, dans le cas des boucles imbriquees qui sont au cur de la plupart des programmes de calcul scientifique , il est possible d'elaborer des algorithmes efficaces et d'etudier leur optimalite. A l'heure actuelle, il n'existe aucun compilateur-paralleliseur performant. La plupart des langages pour machines paralleles sont des langages a parallelisme explicites pour lesquels l'utilisateur specifie ainsi bien la repartition des donnees et des calculs que les communications entre processeurs. Les informatiens ont tente d'apporter une reponse a ce probleme d'environnement de programmation des machines paralleles en proposant le langage hpf (high performance fortran) qui semble devenir une norme. On se dirige ainsi vers un langage dans lequel l'utilisateur peut specifier, a l'aide de directives d'aide a la compilation, l'allocation des donnees et le parallelisme de certaines boucles. Le compilateur tente d'optimiser l'execution du programme en tenant compte des directives, l'efficacite du code final depend fortement des indications donnees par l'utilisateur. Ces directives ont ete choisies parce que jugees importantes pour aider le compilateur a generer un code efficace. Cependant, le probleme de trouver les bonnes allocations de donnees et d'extraire le parallelisme present dans le code initial est laisse a l'utilisateur. L'objectif de ma these est de pouvoir generer automatiquement, a la compilation, des directives de repartition des donnees et d'alignement des tableaux conduisant a des communications efficaces
18
Labidi, Mohamed Khalil. "Parallelisation of hybrid metaheuristics for COP solving." Thesis, Paris Sciences et Lettres (ComUE), 2018. http://www.theses.fr/2018PSLED029/document.
Full textAbstract:
L’Optimisation Combinatoire (OC) est un domaine de recherche qui est en perpétuel changement. Résoudre un problème d’optimisation combinatoire (POC) consiste essentiellement à trouver la ou les meilleures solutions dans un ensemble des solutions réalisables appelé espace de recherche qui est généralement de cardinalité exponentielle en la taille du problème. Pour résoudre des POC, plusieurs méthodes ont été proposées dans la littérature. On distingue principalement les méthodes exactes et les méthodes d’approximation. Ne pouvant pas viser une résolution exacte de problèmes NP-Complets lorsque la taille du problème dépasse une certain seuil, les chercheurs on eu de plus en plus recours, depuis quelques décennies, aux algorithmes dits hybrides (AH) ou encore à au calcul parallèle. Dans cette thèse, nous considérons la classe POC des problèmes de conception d'un réseau fiable. Nous présentons un algorithme hybride parallèle d'approximation basé sur un algorithme glouton, un algorithme de relaxation Lagrangienne et un algorithme génétique, qui produit des bornes inférieure et supérieure pour les formulations à base de flows. Afin de valider l'approche proposée, une série d'expérimentations est menée sur plusieurs applications: le Problème de conception d'un réseau k-arête-connexe avec contrainte de borne (kHNDP) avec L=2,3, le problème de conception d'un réseau fiable Steiner k-arête-connexe (SkESNDP) et ensuite deux problèmes plus généraux, à savoir le kHNDP avec L >= 2 et le problème de conception d'un réseau fiable k-arête-connexe (kESNDP). L'étude expérimentale de la parallélisation est présentée après cela. Dans la dernière partie de ce travail, nous présentons deux algorithmes parallèles exactes: un Branch-and-Bound distribué et un Branch-and-Cut distribué. Une série d'expérimentation a été menée sur une grappe de 128 processeurs, et des accélération intéressantes ont été atteintes pour la résolution du problèmes kHNDP avec k=3 et L=3Combinatorial Optimization (CO) is an area of research that is in a constant progress. Solving a Combinatorial Optimization Problem (COP) consists essentially in finding the best solution (s) in a set of feasible solutions called a search space that is usually exponential in cardinality in the size of the problem. To solve COPs, several methods have been proposed in the literature. A distinction is made mainly between exact methods and approximation methods. Since it is not possible to aim for an exact resolution of NP-Complete problems when the size of the problem exceeds a certain threshold, researchers have increasingly used Hybrid (HA) or parallel computing algorithms in recent decades. In this thesis we consider the COP class of Survivability Network Design Problems. We present an approximation parallel hybrid algorithm based on a greedy algorithm, a Lagrangian relaxation algorithm and a genetic algorithm which produces both lower and upper bounds for flow-based formulations. In order to validate the proposed approach, a series of experiments is carried out on several applications: the k-Edge-Connected Hop-Constrained Network Design Problem (kHNDP) when L = 2,3, The problem of the Steiner k-Edge-Connected Network Design Problem (SkESNDP) and then, two more general problems namely the kHNDP when L >= 2 and the k-Edge-Connected Network Design Problem (kESNDP). The experimental study of the parallelisation is presented after that. In the last part of this work, we present a two parallel exact algorithms: a distributed Branch-and-Bound and a distributed Branch-and-Cut. A series of experiments has been made on a cluster of 128 processors and interesting speedups has been reached in kHNDP resolution when k=3 and L=3
19
Lewis, Tim. "Static dependency analysis of recursive structures for parallelisation." Thesis, University of Edinburgh, 2005. http://hdl.handle.net/1842/24832.
Full textAbstract:
A new approach is presented for the analysis of dependencies in complex recursive data structures with pointer linkages that can be determined statically, at compile time. The pointer linkages in a data structure are described by the programmer in the form of two-variable Finite State Automata (2FSA) which supplements the code that operates over the data structure. Some flexibility is possible in that the linkages can specify a number of possible target nodes for a pointer. An analysis method is described to extract data dependency information, also in the form of 2FSAs, from the recursive code that operates over these structures. For restricted, simple forms of recursion these data dependencies are exact; but, in general, heuristics are presented which provide approximate information. This method uses a novel technique that approximates the transitive closure of these 2FSA relations. In the context of dependency analysis, approximations must be ‘safe' in that they are permitted to overestimate dependencies thereby including spurious ones, but none must be missed. A test is developed that permits the safety of these approximate solutions to be validated. When a recursive program is partitioned into a number of separate threads by the programmer this dependency information can be used to synchronise the access to the recursive structure. This ensures that the threads execute correctly in parallel, enabling a multithreaded version of the code to be constructed. A multithreaded Micronet processor architecture was chosen as a target for this approach. Front- and back-ends of a compiler were developed to compile these multithreaded programs into executables for this architecture, which were then run on a simulation of the processor. The timing results for selected benchmarks are used to demonstrate that useful parallelism can be extracted.
20
Ehlers, Thorsten [Verfasser]. "SAT and CP - Parallelisation and Applications / Thorsten Ehlers." Kiel : Universitätsbibliothek Kiel, 2017. http://d-nb.info/113755522X/34.
Full text
21
Abbas, Naeem. "Runtime Parallelisation Switching for MPEG4 Encoder on MPSoC." Thesis, KTH, Elektronik- och datorsystem, ECS, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-144038.
Full textAbstract:
The recent development for multimedia applications on mobile terminals raised the need for flexible and scalable computing platforms that are capable of providing considerable (application specific) computational performance within a low cost and a low energy budget. The MPSoC with multi-disciplinary approach, resolving application mapping, platform architecture and runtime management issues, provides such multiple heterogeneous, flexible processing elements. In MPSoC, the run-time manager takes the design time exploration information as an input and selects an active Pareto point based on quality requirement and available platform resources, where a Pareto point corresponds to a particular parallelization possibility of target application. To use system’s scalability at best and enhance application’s flexibility a step further, the resource management and Pareto point selection decisions need to be adjustable at run-time. This thesis work experiments run-time Pareto point switching for MPEG-4 encoder. The work involves design time exploration and then embedding of two parallelization possibilities of MPEG-4 encoder into one single component and enabling run-time switching between parallelizations, to give run-time control over adjusting performance-cost criteria and allocation de-allocation of hardware resources at run-time. The newer system has the capability to encode each video frame with different parallelization. The obtained results offer a number of operating points on Pareto curve in between the previous ones at sequence encoding level. The run-time manager can improve application performance up to 50% or can save memory bandwidth up to 15%, according to quality request.
22
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.
23
Cook, Andrew. "Using proof in transformation synthesis for automatic parallelisation." Thesis, Heriot-Watt University, 2001. http://hdl.handle.net/10399/462.
Full text
24
ROUSSEL-RAGOT, PIERRE. "La methode du recuit simule : acceleration et parallelisation." Paris 6, 1990. http://www.theses.fr/1990PA066305.
Full textAbstract:
La methode du recuit simule est une technique d'optimisation puissante et simple a mettre en uvre, qui a prouve son efficacite pour la recherche de solutions optimales ou proches de l'optimum dans de nombreuses applications pratiques. Mais, meme si l'on utilise des profils de recuit bien adaptes, le temps de calcul peut se reveler trop important. Plusieurs methodes de parallelisation de l'algorithme ont ete proposees, mais elles s'ecartent du comportement sequentiel de l'algorithme. Nous presentons une methode de parallelisation de l'algorithme du recuit simule independante du probleme, qui possede les memes qualites de convergence que l'algorithme sequentiel. Nous introduisons deux modes de parallelisation, suivant la valeur de la temperature, et nous modelisons analytiquement leur comportement, ce qui permet de prevoir l'acceleration de la methode quel que soit le probleme. Nous presentons en outre une architecture de processeur specialise qui permet d'accelerer l'execution de l'algorithme pour un probleme de placement simplifie. Les performances de l'algorithme parallele sont evaluees sur un probleme de placement simplifie a l'aide d'un reseau de transputers et les modeles ont ete compares aux resultats des experiences
25
Powell, Daniel Christopher. "Lightweight speculative support for aggressive auto-parallelisation tools." Thesis, University of Edinburgh, 2015. http://hdl.handle.net/1842/10566.
Full textAbstract:
With the recent move to multi-core architectures it has become important to create the means to exploit the performance made available to us by these architectures. Unfortunately parallel programming is often a difficult and time-intensive process, even to expert programmers. Auto-parallelisation tools have aimed to fill the performance gap this has created, but static analysis commonly employed by such tools are unable to provide the performance improvements required due to lack of information at compile-time. More recent aggressive parallelisation tools use profiled-execution to discover new parallel opportunities, but these tools are inherently unsafe. They require either manual confirmation that their changes are safe, completely ruling out auto-parallelisation, or they rely upon speculative execution such as software thread-level speculation (SW-TLS) to confirm safe execution at runtime. SW-TLS schemes are currently very heavyweight and often fail to provide speedups for a program. Performance gains are dependent upon suitable parallel opportunities, correct selection and configuration, and appropriate execution platforms. Little research has been completed into the automated implemention of SW-TLS programs. This thesis presents an automated, machine-learning based technique to select and configure suitable speculation schemes when appropriate. This is performed by extracting metrics from potential parallel opportunities and using them to determine if a loop is suitable for speculative execution and if so, which speculation policy should be used. An extensive evaluation of this technique is presented, verifying that SW-TLS configuration can indeed be automated and provide reliable performance gains. This work has shown that on an 8-core machine, up to 7.75X and a geometric mean of 1.64X speedups can be obtained through automatic configuration, providing on average 74% of the speedup obtainable through manual configuration. Beyond automated configuration, this thesis explores the idea that many SW-TLS schemes focus too heavily on recovery from detecting a dependence violation. Doing so often results in worse than sequential performance for many real-world applications, therefore this work hypothesises that for many highly-likely parallel candidates, discovered through aggressive parallelisation techniques, would benefit from a simple dependence check without the ability to roll back. Dependence violations become extremely expensive in this scenario, however this would be incredibly rare. With a thorough evaluation of the technique this thesis confirms the hypothesis whilst achieving speedups of up to 22.53X, and a geometric mean of 2.16X on a 32-core machine. In a competitive scheduling scenario performance loss can be restricted to at least sequential speeds, even when a dependence has been detected. As a means to lower costs further this thesis explores other platforms to aid in the execution of speculative error checking. Introduced is the use of a GPU to offload some of the costs to during execution that confirms that using an auxiliary device is a legitimate means to obtain further speedup. Evaluation demonstrates that doing so can achieve up to 14.74X and a geometric mean of 1.99X speedup on a 12-core hyperthreaded machine. Compared to standard CPU-only techniques this performs slightly slower with a geometric mean of 0.96X speedup, however this is likely to improve with upcoming GPU designs. With the knowledge that GPU’s can be used to reduce speculation costs, this thesis also investigates their use to speculatively improve execution times also. Presented is a novel SW-TLS scheme that targets GPU-based execution for use with aggressive auto-parallelisers. This scheme is executed using a competitive scheduling model, ensuring performance is no lower than sequential execution, whilst being able to provide speedups of up to 99X and on average 3.2X over sequential. On average this technique outperformed static analysis alone by a factor of 7X and achieved approximately 99% of the speedup obtained from manual parallel implementations and outperformed the state-of-the-art in GPU SW-TLS by a factor of 1.45.
26
Hewitt, Neil. "Parallelisation and use of large-scale atomic structure codes." Thesis, Queen's University Belfast, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.337040.
Full text
27
Mazzoni, Christophe. "Construction d'un modele numerique de terrain : methodes et parallelisation." Paris 11, 1995. http://www.theses.fr/1995PA112220.
Full textAbstract:
Le but de ce travail est de reduire le temps de traitement necessaire a la production d'un modele numerique de terrain (mnt) en utilisant un calculateur parallele. C'est une collaboration entre l'institut geographique national (ign) et le laboratoire d'electronique de technique et d'instrumentation (leti) du commissariat a l'energie atomique francais. L'ign a developpe un outil de production de mnt qui sont utilises en cartographie. L'element cle du systeme est un correlateur, programme qui determine automatiquement les paires de points homologues issus du couple stereoscopique traite. Ce traitement requiert une importante puissance de calcul qu'un calculateur parallele de type simd (single instruction, multiple data) comme sympati-2 developpe au leti peut fournir. Ce calculateur est integre et commercialise dans le systeme de vision openvision. Tout en conservant la philosophie du programme sequentielle, nous avons cherche a exploiter le parallelisme de donnees du programme. Notre analyse a mis en evidence un point bloquant important lie a la faiblesse du couplage entre le processeur scalaire d'openvision et le calculateur parallele. Nous proposons des solutions pour renforcer le couplage scalaire-parallele. Pour accelerer davantage le traitement nous avons evalue l'apport procure par symphonie, calculateur simd, successeur de sympati-2. D'autre part nous avons elabore une approche multi-correlateurs qui repose sur une parallelisation de type parallelisme de controle, pour lequel une structure parallele mimd (multiple instruction, multiple data) est adaptee. Enfin, nous dressons les grandes lignes d'une architecture de type multi-simd qui concilie nos deux approches paralleles. Cette architecture offre la capacite d'apprehender tous les niveaux de traitement d'images par le couplage fort entre le processeur scalaire et le processeur parallele simd. Elle est flexible par sa modularite, et le reseau de communication lui assure une fiabilite qui interesse les systemes sensibles
28
Ammarguellat, Zahira. "Restructuration des programmes fortran en vue de leur parallelisation." Paris 6, 1988. http://www.theses.fr/1988PA066021.
Full textAbstract:
La phase preliminaire de restructuration proposee consiste a transformer les programmes de sorte qu'ils n'utilisent que des if, while et affectations. Ces while pouvant representer des boucles do cachees, une phase de standardisation des listes d'indices de boucles est necessaire
29
DUPONT, DE DINECHIN BENOIT. "Parallelisation de code et architectures superscalaires a controle statique." Paris 6, 1991. http://www.theses.fr/1991PA066722.
Full textAbstract:
La comprehension fine des phenomenes mis en jeu dans l'execution superscalaire est difficile, parce qu'elle necessite de faire intervenir les concepts et techniques de trois domaines habituellement separes : compilation / parallelisation automatique, ordonnancement / recherche operationnelle, architecture des calculateurs / technologie d'implementation. Dans cette these, nous commencons par rassembler et mettre en relation les elements pertinents de ces trois domaines, afin d'isoler les principes actifs de l'execution superscalaire. Cette connaissance est alors appliquee a la conception d'une architecture baptisee stacs (static control superscalar), dont une implementation est en cours au laboratoire masi. Mots cles : architecture des calculateurs, processeurs superscalaires, ordonnancement de code, propriete polycyclique, memoires paralleles, systemes memoire premiers, parallelisation automatique, supercompilation.
30
Paul, Christian. "Etudes sur la parallelisation d'algorithmes de gestion de production." Nantes, 1993. http://www.theses.fr/1993NANT2098.
Full textAbstract:
Cette etude sur la parallelisation d'applications dans le cadre des problemes de gestion de production a ete menee en deux temps. Dans un premier temps nous nous sommes attaches a presenter les diverses approches permettant de resoudre des problemes de performance a l'aide du parallelisme. Ainsi apres avoir constitue un corpus d'applications candidates, nous avons selectionne un ensemble de criteres permettant de guider les choix de parallelisation. Conjointement a ces premieres investigations, nous avons etudie le modele des problemes de satisfaction de contraintes (csp). Ce dernier presentait un interet dans la resolution parallele de problemes de planification et d'ordonnancement. Dans un deuxieme temps, nous avons envisage une solution pour les problemes de planification et d'ordonnancement, qui ont ete abordes par le biais du langage prolog. Par rapport au langage de base, nous avons etudie deux jeux de primitives. Le premier permet de gerer explicitement le parallelisme au sein d'un programme prolog. Le second permet d'utiliser la puissance des contraintes en domaines finis
31
Chen, Xinuo. "Parallelisation for data-intensive applications over peer-to-peer networks." Thesis, University of Warwick, 2009. http://wrap.warwick.ac.uk/3640/.
Full textAbstract:
In Data Intensive Computing, properties of the data that are the input for an application decide running performance in most cases. Those properties include the size of the data, the relationships inside data, and so forth. There is a class of data intensive applications (BLAST, SETI@home, Folding@Home and so on so forth) whose performances solely depend on the amount of input data. Another important characteristic of those applications is that the input data can be split into units and these units are not related to each other during the runs of the applications. This characteristic helps this class of data intensive applications to be parallelised in the way where the input data is split into units and application runs on different computer nodes for certain portion of the units. SETI@home and Folding@Home have been successfully parallelised over peer-to-peer networks. However, they suffer from the problems of single point of failure and poor scalability. In order to solve these problems, we choose BLAST as our example data intensive applications and parallelise BLAST over a fully distributed peer-to-peer network. BLAST is a popular bioinformatics toolset which can be used to compare two DNA sequences. The major usage of BLAST is searching a query of sequences inside a database for their similarities so as to identify whether they are new. When comparing single pair of sequences, BLAST is efficient. However, due to growing size of the databases, executing BLAST jobs locally produces prohibitively poor performance. Thus, methods for parallelising BLAST are sought. Traditional BLAST parallelisation approaches are all based on clusters. Clusters employ a number of computing nodes and high bandwidth interlinks between nodes. Cluster-based BLAST exhibits higher performance; nevertheless, clusters suffer from limited resources and scalability problems. Clusters are expensive, prohibitively so when the growth of the sequence database are taken into account. It involves high cost and complication when increasing the number of nodes to adapt to the growth of BLAST databases. Hence a Peer-to-Peer-based BLAST service is required. This thesis demonstrates our parallelisation of BLAST over Peer-to-Peer networks (termed ppBLAST), which utilises the free storage and computing resources in the Peer-to-Peer networks to complete BLAST jobs in parallel. In order to achieve the goal, we build three layers in ppBLAST each of which is responsible for particular functions. The bottom layer is a DHT infrastructure with the support of range queries. It provides efficient range-based lookup service and storage for BLAST tasks. The middle layer is the BitTorrent-based database distribution. The upper layer is the core of ppBLAST which schedules and dispatches task to peers. For each layer, we conduct comprehensive research and the achievements are presented in this thesis. For the DHT layer, we design and implement our DAST-DHT. We analyse balancing, maximum number of children and the accuracy of the range query. We also compare the DAST with other range query methodology and state that if the number of children is adjusted to more two, the performance of DAST overcomes others. For the BitTorrent-like database distribution layer, we investigate the relationship between the seeding strategies and the selfish leechers (freeriders and exploiters). We conclude that OSS works better than TSS in a normal situation.
32
Chao, Daphne (Yu Fen). "MDRIP: A Hybrid Approach to Parallelisation of Discrete Event Simulation." Thesis, University of Canterbury. Computer Science and Software Engineering, 2006. http://hdl.handle.net/10092/1076.
Full textAbstract:
The research project reported in this thesis considers Multiple Distributed Replications in Parallel (MDRIP), a hybrid approach to parallelisation of quantitative stochastic discrete-event simulation. Parallel Discrete-Event Simulation (PDES) generally covers distributed simulation or simulation with replicated trials. Distributed simulation requires model partitioning and synchronisation among submodels. Simulation with replicated trials can be executed on-line by applying Multiple Replications in Parallel (MRIP). MDRIP has been proposed for overcoming problems related to the large size of simulated models and their complexity, as well as with the problem of controlling the accuracy of the final simulation results. A survey of PDES investigates several primary issues which are directly related to the parallelisation of DES. A secondary issue related to implementation efficiency is also covered. Statistical analysis as a supporting issue is described. The AKAROA2 package is an implementation of making such supporting issue effortless. Existing solutions proposed for PDES have exclusively focused on collecting of output data during simulation and conducting analysis of these data when simulation is finished. Such off-line statistical analysis of output data offers no control of statistical errors of the final estimates. On-line control of statistical errors during simulation has been successfully implemented in AKAROA2, an automated controller of output data analysis during simulation executed in MRIP. However, AKAROA2 cannot be applied directly to distributed simulation. This thesis reports results of a research project aimed at employing AKAROA2 for launching multiple replications of distributed simulation models and for on-line sequential control of statistical errors associated with a distributed performance measure; i.e. with a performance measure which depends on output data being generated by a number of submodels of distributed simulation. We report changes required in the architecture of AKAROA2 to make MDRIP possible. A new MDRIP-related component of AKAROA2, a distributed simulation engine mdrip engine, is introduced. Stochastic simulation in its MDRIP version, as implemented in AKAROA2, has been tested in a number of simulation scenarios. We discuss two specific simulation models employed in our tests: (i) a model consisting of independent queues, and (ii) a queueing network consisting of tandem connection of queueing systems. In the first case, we look at the correctness of message orderings from the distributed messages. In the second case, we look at the correctness of output data analysis when the analysed performance measures require data from all submodels of a given (distributed) simulation model. Our tests confirm correctness of our mdrip engine design in the cases considered; i.e. in models in which causality errors do not occur. However, we argue that the same design principles should be applicable in the case of distributed simulation models with (potential) causality errors.
33
BENAICHOUCHE, MOHAMED. "Parallelisation des methodes de recherche arborescente dans des environnements distribues." Paris 6, 1996. http://www.theses.fr/1996PA066029.
Full textAbstract:
L'utilisation de plusieurs processeurs sur machine distribuee, permet d'augmenter la capacite maximale en termes de temps de calcul et d'espace memoire. Neanmoins, il apparait que cette capacite supplementaire est rarement pleinement utilisee du fait de la difficulte considerable d'assurer un equilibrage de charge de travail entre les processeurs. En effet, si certains processeurs restent inactifs ou sous-utilises alors que d'autres ont une charge de travail importante, il est evident que le temps global d'execution sera loin d'etre le meilleur que l'on puisse obtenir. C'est pourquoi, l'etude de l'equilibrage de la charge de travail entre les processeurs, s'avere capitale si l'on veut ameliorer les performances de la machine parallele. Cette these contribue a l'etude d'une repartition equitable dans des environnements distribues, d'une charge de travail. Une strategie d'equilibrage de charge dynamique avec de nouveaux criteres de declenchement sont alors developpes, et un nouveau modele de controle de la charge multi-control est propose. La validation experimentale du modele et l'importance du controle de charge multi-control sont illustrees, par des resolutions distribuees de problemes d'optimisation combinatoire. Pour elargir notre travail a un univers plus important de machines paralleles et d'applications, un modele theorique du b&b distribue avec equilibrage de charge est propose. Cette etude a ete realisee sur la machine distribuee paragon d'intel, et a permis de contribuer au developpement d'une bibliotheque d'aide au developpement d'applications de type branch-and-bound (bob) pour des problemes aussi bien de minimisation que de maximisation dans des environnements distribues
34
Cudel, Christophe. "Parallelisation d'algorithmes de compression d'images sur un reseau de transputers." Reims, 1995. http://www.theses.fr/1995REIMS021.
Full textAbstract:
Le sujet de cette these est l'implantation d'algorithmes de compression d'images sur un reseau de transputers. Le memoire est organise en 4 parties qui traitent: du parallelisme, des architectures multiprocesseurs, et de la modelisation algorithmique par un graphe flot de donnees conditionne. De l'implantation sur un reseau de transputers d'un algorithme de suivi de contours par codage de freeman (compression d'images binaires). De l'implantation d'un algorithme de compression d'images avec la transformee d'hadamard. De l'implantation d'un algorithme de compression d'images avec la transformee en ondelettes. Cette partie presente notamment l'apport des reseaux de neurones pour la prediction d'images au sein d'une modulation d'impulsions codees differentielle (micd). Ce travail qui est une contribution au theme adequation algorithme architecture montre l'interet de la modelisation d'algorithmes par un graphe flot de donnees conditionne et de l'outil d'aide a l'implantation syndex, developpe a l'inria. Il montre egalement l'apport des reseaux de neurones pour la compression d'images fixes
35
Baloglu, Maximilian Volkan. "Parallelisation and Performance Analysis of a TreeSPH Code for Galaxy Simulations." Thesis, KTH, Numerisk analys, NA, 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-147340.
Full textAbstract:
In cosmological simulations, the Lagrangian method Smoothed Particle Hydrodynamics is often applied to cover gas dynamics and combined with tree algorithms for long-range potentials like the Barnes-Hut method to include self-gravity and derive the nearest neighbour lists efficiently. In this thesis, a so-called TreeSPH code is parallelized by using MPI and subsequently the performance is analysed. For the domain decomposition to the processes, the structure of an octree is examined and space filling curves are applied to achieve well-working dynamical load balancing. For an efficient parallel SPH calculation, a novel method with a localised boundary handling is proposed to reduce communication overheadInom kosmologiska simulationer är den Lagrangianska metoden Smoothed Particle Hydrodynamics en vanligt förekommande metod för att täcka gasdynamik och kombineras med trädalgortimer för långdistanspotentialer, exempelvis Barnes-Huts metod för att inkludera självgravitation och effektivt konstruera listor med de närmaste grannarna. I detta examensarbete parallelliseras en så kallad TreeSPH-kod med hjälp av MPI, därefter analyseras prestandan. Gällande domändekomposition av processerna så undersöks strukturen av en octree där rymdfyllande kurvor appliceras för att uppnå en väl fungerande dynamisk lastbalansering. För en effektiv parallell SPH beräkning föreslås en ny metod med lokal randbehandling för att reducera kommunikation.
36
TAWBI, NADIA. "Parallelisation automatique : estimation des durees d'execution et allocation statique de processeurs." Paris 6, 1991. http://www.theses.fr/1991PA066355.
Full textAbstract:
L'objectif de cette these est de generer un programme parallele efficace a partir d'un programme sequentiel dans lequel on a detecte le parallelisme. L'approche adoptee est statique et consiste a distribuer le code aux differents processeurs en inserant des primitives de synchronisation pour respecter les contraintes de precedence. C'est un probleme d'allocation de processeurs et d'ordonnancement. Afin de la resoudre, les heuristiques recuit simule et tabou ont ete utilisees et comparees. L'ordonnancement a ete effectue par un algorithme de liste. L'estimation des durees d'execution des parties du code est basee sur la sommation des durees des instructions elementaires et le comptage des iterations de boucles. Ce probleme se ramene a compter les points a coordonnees entieres dans un polyedre convexe borne. Les boucles constituent la partie de code qui consomme le plus de temps et dont le parallelisme est le plus rentable. Une methode de parallelisation des boucles est presentee
37
ADLE, ROXANE. "Outils de parallelisation automatique des programmes denses pour les structures creuses." Evry-Val d'Essonne, 1999. http://www.theses.fr/1999EVRY0007.
Full textAbstract:
La programmation parallele d'algorithmes d'algebre lineaire sur les architectures paralleles a ete etudiee pour resoudre des systemes denses. Les etudes menees sur les outils de compilation et sur les methodes algorithmes cernent le probleme et proposent des solutions adaptees aux machines paralleles. Sur des tailles de problemes suffisantes, les machines paralleles offrent une alternative aux machines vectorielles qui sont reconnues pour leur efficacite de traitement sur ce type de problemes. Le but de ce travail est de paralleliser des programmes sequentiels utilisant des structures de donnees denses et obtenir des programmes paralleles possedant des structures de donnees creuses. Ce qui a motive ces recherches est que les calculs sur les matrices creuses contiennent plus de parallelisme que les memes calculs effectues sur des matrices denses. Cette propriete existe a cause de la valeur nulle de certains elements et a pour consequence l'elimination de certaines dependances. En effet, le calcul de dependance est base sur le calcul d'un acces memoire commune a deux instructions. Il est possible de raffiner cette notion en y incluant la notion de la modification d'etat. Effectivement, si l'execution de l'une des deux instructions ne modifie pas l'etat de la cellule, alors la dependance peut etre brisee. Dans le cadre du creux, ce type de parallelisme specifique peut etre utilise a cause des proprietes d'absorption et de neutralite de zero. Cependant, le calcul des dependances sur les programmes possedant une structure de donnees creuse est difficile a cause des indirections dans ces dernieres. Dans ce travail, ce probleme a ete contourne en faisant le calcul des dependances sur le programme dense tout en prenant en compte la structure de la matrice creuse pour detecter les dependances inutiles. De cette maniere, un graphe de dependance plus reduit que celui calcule avec les conditions de bernstein a ete obtenu. Apres ces calculs, le programme ainsi que la matrice creuse sont donnes au compilateur creux mt1 (de bik et wishoff a l'universite de leiden, hollande) et est transforme en un programme creux parallele.
38
Dussert, Nathalie. "Parallelisation d'un langage fonctionnel selon le modèle a flots de données." Paris, ENST, 1996. http://www.theses.fr/1996ENST0043.
Full textAbstract:
Toute la puissance du modèle à flots de données vient du fait qu'il exploite le parallélisme intrinsèque d'un programme en dispensant le programmeur de spécifier les taches exécutables en parallèle. Ce modèle de calcul est ainsi bien approprie pour étudier la parallèlisation d'un langage fonctionnel : notre étude a pour objectif de proposer et de comparer plusieurs modes de parallèlisation automatique de programmes graal, un langage fonctionnel sans variable. Nous considérons une architecture à flots de données de base qui n'intègrera pas les dernières avancées des machines dataflow ; en effet nous cherchons à mettre en évidence l'influence de la granularité des taches et du nombre d'unités de calcul sur l'exploitation du parallélisme en faisant abstraction des caractéristiques physiques de la machine sous-jacente. Notre premier mode de parallèlisation exhibe des taches de granularité fine, au niveau des primitives du langage ; il sera notre référence pour les comparaisons. Nous envisageons ensuite un mode 2 qui regroupe les primitives selon deux critères de dépendance de données. Le problème est alors de généraliser ces regroupements de fonctions à des opérations qui ne soient pas uniquement des primitives. Il semble intéressant de mettre dans une seule tache une partie du code d'une fonction si le temps de calcul de la tache reste relativement faible. Il nous faut donc pouvoir estimer la complexité asymptotique d'une fonction. Nous proposons et mettons en œuvre des heuristiques qui permettent de calculer automatiquement une complexité. Nous avons ainsi pour chaque fonction un ordre de grandeur de sa complexité en temps. Nous avons alors choisi une borne de complexité. Toute fonction de complexité inferieure a cette borne sera compilée et pourra être incluse dans une tache compilée ; tandis que les fonctions de complexité supérieure ou égale a cette borne verront leur code scinde en plusieurs taches.
39
Chantemargue, Fabrice, and Jean Gallice. "Segmentation d'images par approche de type division-fusion : schemas de parallelisation." Clermont-Ferrand 2, 1991. http://www.theses.fr/1991CLF21395.
Full textAbstract:
Cette these traite d'un probleme fondamental pour le developpement de systemes de vision artificielle, a savoir la parallelisation d'algorithmes de traitement d'images presentant des temps d'execution prohibitifs vis-a-vis du contexte applicatif. Le choix s'est porte sur la methode de type division-fusion. Frequemment employee en segmentation d'images par extraction de regions. Ce travail repose sur la modelisation algorithmique de cette methode, qui consiste en l'utilisation de criteres pour segmenter l'image. La recherche de criteres, quant a elle, n'est pas abordee ici. C'est pourquoi cette etude est generale et peut etre reprise dans diverses applications telles que la segmentation selon des criteres de luminance, de chrominance, de texture, ou de mouvement,. . . Deux aspects apparaissent dans ce memoire. Le premier aspect concerne la parallelisation algorithmique de la technique de division-fusion, par approche ferme de processeurs, en vue de l'implantation sur une machine parallele mind. Le deuxieme aspect est une consequence de l'etude de la parallelisation de la phase de fusion. Il consiste, a partir de la modelisation algorithmique de celle-ci, a proposer deux nouvelles approches se pretant mieux au parallelisme. Les travaux sont valides par application a la segmentation en regions selon des criteres de mouvement
40
Loechner, Vincent. "Contribution a l'etude des polyedres parametres et applications en parallelisation automatique." Strasbourg 1, 1997. http://www.theses.fr/1997STR13242.
Full textAbstract:
La premiere partie de cette these est consacree a l'etude de la parallelisation de systemes d'equations recurrentes affines parametres. Un systeme d'equations recurrentes est equivalent a un nid de boucles a assignation unique. Ce travail donne en particulier une methode de recherche des fonctions de cadencement et d'allocation par variable permettant de minimiser les communications dans le reseau de processeurs cible. Les contraintes de comptabilite entre cadencement et allocation sont egalement prises en compte. Le modele geometrique utilise depuis de nombreuses annees dans l'analyse de dependances de nids de boucles ou de systemes d'equations recurrentes repose sur l'utilisation de polyedres convexes. Lorsque le systeme d'equations recurrentes est parametre, les polyedres sont parametres. La necessite de connaitre les sommets de polyedres parametres est mise en evidence dans cette premiere partie. La deuxieme partie est une etude des polyedres parametres et de leur utilisation dans le domaine de la parallelisation automatique. Une methode originale de recherche des sommets de polyedres parametres, valides par domaines sur les parametres, y est notamment decrite. Le deuxieme chapitre de cette partie presente quelques applications de ces resultats en parallelisation automatique.
41
Größlinger, Armin. "The challenges of non-linear parameters and variables in automatic loop parallelisation /." kostenfrei, 2009. http://www.opus-bayern.de/uni-passau/volltexte/2009/1789/.
Full text
42
Legrand, Pascal. "Schemas de parallelisation d'applications de traitement d'images sur la machine parallele transvision." Clermont-Ferrand 2, 1995. http://www.theses.fr/1995CLF21740.
Full textAbstract:
La programmation de calculateurs paralleles dedies a la vision artificielle est un probleme delicat sans outil adapte a cet effet. L'utilisateur est astreint a decrire explicitement le partage des operations et les communications inter-processeurs. Les travaux presentes dans ce memoire sont relatifs a la caracterisation de methodes de parallelisation d'applications de traitements d'images pour une machine mimd a memoire distribuee developpee au lasmea: transvision. Ces travaux sont une etape preliminaire vers la definition d'un environnement d'aide a la programmation parallele. Ce memoire est constitue de 6 chapitres. Apres une presentation de machines paralleles de vision, le chapitre 1 presente une taxinomie des operateurs de bas et moyen niveaux. Le chapitre 2 presente une chaine complete de segmentation d'images au sens contour et d'extraction de groupements perceptifs de segments. Chaque etape de traitement est decrite precisement. Le chapitre 3 decrit la parallelisation de cette chaine de traitements, decomposee selon cinq taches de complexite equivalente. La parallelisation de chaque tache est decrite ainsi que la mise en uvre de l'integralite de cette application. L'extension du schema de parallelisation est abordee et trois evolutions possibles sont presentees en fin de chapitre. Les chapitres 4 et 5 presentent deux autres chaines de traitements et les schemas de parallelisation proposes pour une machine mimd a memoire distribuee. Dans le chapitre 6, nous presentons une synthese des schemas de parallelisation abordes a l'occasion de cette these
43
David, Pierre. "Analyse semantique des programmes en langage c en vue de leur parallelisation." Paris 6, 1991. http://www.theses.fr/1991PA066088.
Full textAbstract:
Les recherches dans le domaine de la parallelisation automatique se sont concentrees sur le langage fortran. Or, ce langage souffre de defauts qui le rendent inadapte a un certain nombre de problemes. Le but de notre etude est la detection automatique de parallelisme en langage c. Le probleme est complexe puisque le langage c dispose de nombreuses constructions destinees a faciliter une ecriture optimisee sur une architecture traditionnelle, et en particulier les pointeurs, l'arithmetique sur ces pointeurs et les expressions avec effets de bord. Notre approche consiste a desoptimiser le programme pour en faciliter l'analyse semantique. Dans un premier temps, nous definissons un sous-ensemble du langage c sans appel de fonctions ni coercitions, mais en acceptant toutes les expressions avec effets de bord. L'absence de coercitions nous permet de definir une structuration de la memoire suivant le systeme de types du langage. Dans un deuxieme temps, nous transformons les boucles for, qui ont en langage c une semantique tres complexe, en boucles while, puis nous retirons les effets de bord des expressions. Enfin, nous procedons a une evaluation symbolique du programme pour un extraire une suite de transformations, c'est-a-dire des substitutions gardees par des expressions logiques. Ce calcul est direct et precis pour les sequences lineaires, mais nous devons proceder a des approximations pour les boucles. Un des sous-produits de cette analyse est l'identification de celles des boucles while qui ont une semantique de boucle do de fortran. A partir de la, il nous est possible de nous interfacer avec un paralleliseur classique
44
Kouicem, Nadia. "Parallelisation de l'algorithme du recuit simule : implantation et analyse de plusieurs algorithmes." Paris 5, 1992. http://www.theses.fr/1992PA05S011.
Full textAbstract:
La technique du recuit simule est une methode stochastique qui permet la resolution de problemes d'optimisation complexes. Malheureusement, cette methode demande souvent un temps de calcul important. La parallelisation de l'algorithme de recuit simule a permis de remedier a ce probleme. Cependant, les algorithmes paralleles proposes sont tres dependants du probleme a resoudre et des qu'une nouvelle application se presente le choix de l'algorithme parallele puis de son adaptation se pose. Pour pallier cet inconvenient, nous avons generalise divers algorithmes paralleles de recuit simule en vue de les rendre independants du probleme d'optimisation traite. Dans une premiere phase, nous avons defini un probleme test, qui a permis une etude comparative de divers algorithmes paralleles. Nous avons degage des proprietes generales concernant les temps de calcul et la qualite des solutions obtenues. Nous avons etabli des modeles de temps de calcul pour chaque algorithme implante. L'implantation des algorithmes a ete realisee sur un reseau de transputers.
45
Mans, Bernard. "Contribution a l'algorithmique non numerique parallele : parallelisation de methodes de recherche arborescentes." Paris 6, 1992. http://www.theses.fr/1992PA066239.
Full textAbstract:
Le but de cette these est d'etudier la parallelisation des methodes de resolution des problemes d'optimisation combinatoire reputes np-difficiles: les problemes de recherche arborescente par separation et evaluation ou branch and bound. Elle est composee de trois parties complementaires. Dans la premiere partie, nous presentons les differentes definitions essentielles au branch and bound. Le parallelisme intrinseque a cette methode est degage et un modele d'evaluation de performances des branch and bound paralleles est introduit, (chapitre 1). Les differents phenomenes d'anomalies d'acceleration et la limite des solutions connues sont presentes dans le chapitre 2. Le chapitre 3 pose les problemes classiques souleves par l'implementation parallele. La deuxieme partie s'attache a proposer des solutions a des problemes primordiaux: 1) les anomalies d'accelerations, (chapitre 5); des bornes serrees ainsi qu'une propriete de predisposition aux anomalies sont introduites et permettent des choix precis parmi differentes regles, 2) la granularite du travail alloue aux processeurs, (chapitre 6); les gains et surcouts mis en evidence pour un procede de separation polytomique permettent de prouver son interet, 3) l'acces aux donnees partagees, (chapitre 7); des structures de donnees bien adaptees au branch and bound sont etudiees et comparees; pour resoudre la contention d'acces a la memoire, les operations de bases sur ces structures sont rendues concurrentes; leurs performances sont conservees et le surcout d'implementation reduit par une methode de marquage, 4) l'equilibrage de charge des reseaux d'interconnexion de processeurs, (chapitre 8); une nouvelle fonction de charge et une regle de decision d'equilibrage s'adaptant d'elle-meme a l'evolution de la resolution sont developpees et conduisent a la description d'un branch and bound distribue. Enfin, dans la troisieme partie, nous testons ces solutions en concevant des branch and bound paralleles efficaces pour deux problemes reputes difficiles: 1) l'affectation quadratique, chapitre 9, ou les problemes de granularite et d'acces aux donnees sont importants, 2) le sac-a-dos multidimensionnel, chapitre 10, ou l'interet d'une separation polytomique pour la granularite se confirme
46
MALLET, OLIVIER. "Interpretation abstraite appliquee a la compilation et la parallelisation en programmation logique." Palaiseau, École polytechnique, 1992. http://www.theses.fr/1992EPXX0011.
Full textAbstract:
L'interpretation abstraite est une technique puissante d'analyse semantique qui permet la detection de proprietes dynamiques. Elle repose sur la notion d'abstraction (ou approximation) qui remplace les elements du domaine habituel - dit concret - par ceux du domaine abstrait. Nous presentons une semantique deductive de prolog, qui approche la semantique operationnelle standard et possede une propriete de compositionnalite grace a l'utilisation de l'espace des termes quotiente par la relation de renommage et grace a une decomposition de l'operateur d'unification en deux parties independantes. Puis nous proposons pour cette semantique un interprete abstrait generique, c'est-a-dire qui necessite pour une analyse donnee un nombre tres limite d'informations decrivant le domaine et les operateurs abstraits. Cet interprete est implemente en c, fonctionne avec precision et efficacite, et n'est pas restreint aux treillis abstraits de hauteur finie. Nous utilisons ensuite cet outil pour detecter certaines familles de proprietes, et expliquons comment un compilateur ou un repartiteur de programmes prolog peut tirer parti de telles informations
47
Bolis, Alessandro. "Fourier spectral/hp element method : investigation of time-stepping and parallelisation strategies." Thesis, Imperial College London, 2013. http://hdl.handle.net/10044/1/25140.
Full textAbstract:
As computer hardware has evolved, the time required to perform numerical simulations has reduced, allowing investigations of a wide range of new problems. This thesis focuses on algorithm optimization, to minimize run-time, when solving the incompressible Navier-Stokes equations. Aspects affecting performance related to the discretisation and algorithm parallelization are investigated in the context of high-order methods. The roles played by numerical approximations and computational strategies are highlighted and it is recognized that a versatile implementation provides additional benefits, allowing an ad-hoc selection of techniques to fit the needs of heterogeneous computing environments. We initially describe the building blocks of a spectral/hp element and pure spectral method and how they can be encapsulated and combined to create a 3D discretisation, the Fourier spectral/hp element method. Time-stepping strategies are also described and encapsulated in a flexible framework based on the General Linear Method. After implementing and validating an incompressible Navier-Stokes solver, two canonical turbulent flows are analyzed. Afterward a 2D hyperbolic equation is considered to investigate the efficiency of low- and high-order methods when discretising the spatial and temporal derivatives. We perform parametric studies, monitoring accuracy and CPU-time for different numerical approximations. We identify optimal discretisations, demonstrating that high-order methods are the computationally fastest approach to attain a desired accuracy for this problem. Following the same philosophy, we investigate the benefits of using a hybrid parallel implementation. The message passing model is introduced to parallelize different kernels of an incompressible Navier-Stokes solver. Monitoring the parallel performance of these strategies the most efficient approach is highlighted. We also demonstrate that hybrid parallel solutions can be used to significantly extend the strong scalability limit and support greater parallelism.
48
Didier, Keryan. "Contributions to the safe and efficient parallelisation of hard real-time systems." Electronic Thesis or Diss., Sorbonne université, 2019. http://www.theses.fr/2019SORUS485.
Full textAbstract:
L'implémentation de systèmes temps-réel implique de nombreuses étapes qui sont jusqu'aujourd'hui faites manuellement. La complexité de tels systèmes et celle des plateformes matérielles sur lesquelles ils s'exécutent rendent de plus en plus difficile d'assurer la correction de ces étapes de conception (en particulier dans de cadre d'exécutions sur plateformes multi-cœurs). Cela rend l'automatisation de tout le processus d'implémentation inévitable. Cette thèse propose une méthode de parallélisation automatique de systèmes temps-réel. La méthode rapproche les domaines du temps-réel et de la compilation en intégrant les étapes de parallélisation, d'ordonnancement, d'allocation mémoire et de génération de code autour d'une analyse et d'un modèle temporel précis qui s'appuient sur des hypothèses fortes sur la plateforme d'exécution et la forme du code généré. Cette thèse propose également un modèle d'implémentation pour du logiciel flot-de-données multithreadé. En utilisant la même base formelle que précédemment (les formalismes flot-de-données synchrones), un modèle représente une implémentation multithreadé dans un langage comme Lustre, étendu avec des annotations de mapping. Cette modélisation permet un raisonnement formel de toutes les décisions d'implémentation et nous proposons une approche vers la preuve de correction de leur fonctionnalité en rapport à leurs spécificationsThe implementation of hard real-time systems involves a lot of steps that are traditionally manual. The growing complexity of such systems and hardware platforms on which they are executed makes increasingly difficult to ensure the correctness of those steps, in particular for the timing properties of the system on multi-core platform. This leads to the need for automation of the whole implementation process. In this thesis, we provide a method for automatic parallel implementation of real-time systems. The method bridge the gap between real-time systems implementation and compilation by integrating parallelization, scheduling, memory allocation, and code generation around a precise timing model and analysis that rely on strong hypothesis on the execution platform and the form of the generated code. The thesis also provides an implementation model for dataflow multithreaded software. Using the same formal ground as the first contribution, the dataflow synchronous formalisms, the model represents multithreaded implementations in a Lustre-like language extended with mapping annotations. This model allows formal reasoning on the correctness of all the mapping decisions used to build the implementation. We propose an approach toward the proof of correctness of the functionality of the implementation with respect to the functional specifications
49
ORTEGA-AGUILAR, AGUSTIN RAYMUNDO. "Parallelisation d'un langage fonctionnel sur une machine parallele avec une architecture non conventionnelle." Paris 6, 1995. http://www.theses.fr/1995PA066421.
Full textAbstract:
Cette these decrit la parallelisation du langage applicatif graal sur une architecture non conventionnelle, telle que la machine armen. Graal est un langage fonctionnel base sur la theorie de combinateurs. Son principe fondamental est la notion de forme fonctionnelle. L'implementation parallele de graal a ete effectuee sous la forme d'un interprete qui s'occupe d'evaluer directement les expressions donnees par l'utilisateur. Les expressions paralleles sont evaluees par l'ensemble de processeurs constituant la machine. La reduction des expressions sequentielles se fait dans le meme processeur, que la ou elles sont lues. Le principe utilise pour la construction de l'interprete est celui de la reduction de graphe. Un mecanisme explicite de gestion d'expressions parallelisees a ete cree. Des etats ont ete definis pour effectuer cette gestion. Une nouvelle instruction, notee par, a ete ajoutee dans le noyau de base de la version parallele de graal. Elle permet la parallelisation de fonctions et d'expressions. Puisque cette instruction ne fait pas reference a un processeur specifique, les programmes ainsi parallelises sont alors independants du nombre de processeurs et de la topologie de la machine. Une couche de programmation a ete construite au-dessus de graal pour la creation d'une version parallele de scheme. Les fonctions scheme sont transformees en code graal parallele. Un mecanisme d'abstraction de variables a ete propose a cet effet. Il a ete programme en graal ce qui le rend transparent pour l'utilisateur. Il doit faire appel a une fonction de l'interprete quand il veut passer au mode scheme. Il est possible de melanger du code graal et du code scheme
50
DUMAY, ALAIN. "Traitement des indexations non lineaires en parallelisation automatique : une methode de linearisation contextuelle." Paris 6, 1992. http://www.theses.fr/1992PA066461.
Full textAbstract:
Les methodes de resolution des systemes de contrainte aux collisions, elabores pour detecter les dependances entre instructions partageant une variable indicee, reposent sur l'hypothese de linearite de ces systemes. Nous proposons une methode pour lever en partie cette hypothese dans les etudes de dependances intra nid de boucles comme inter nids. L'examen des contextes de programmation les plus courants, conduisant a des systemes de contrainte aux collisions non lineaires, nous permet de constater que les expressions non lineaires sont en general des fonctions des compte-tours des boucles et des parametres de structure du programme. Il est possible de les lineariser en substituant les termes non lineaires par des symboles sur lesquels des contraintes peuvent etre introduites, d'une part a l'aide d'une base de regles de production de contraintes selon la forme du terme et d'un bloc-notes, d'autre part en etudiant leur difference entre deux iterations d'une boucle. Une fois ces expressions linearisees, le systeme de contrainte aux collisions peut-etre resolu par les algorithmes habituels. Cette methode est d'abord developpee pour etudier les dependances intra nids de boucles, puis etendue aux etudes inter nids de boucles que nous ramenons par la construction d'un nid de boucle virtuel commun a une etude intra nid. Son application demande dans tous les cas la mise sous forme canonique du programme qui est realisee dans une phase prealable plus generale de prenormalisation