The one- and two-sided bipartite graph drawing problem alms to find a layout of a bipartite graph, with vertices of the two parts placed on parallel imaginary lines, that has the minimum number of edge-crossings. Vertices of one part are in fixed positions for the one-sided problem, whereas all vertices are free to move along their lines in the two-sided version. Many different heuristics exist for finding approximations to these problems, which are NP-hard. New sequential and parallel methods for producing drawings with low edgecrossings are investigated and compared to existing algorithms, notably Penalty Minimisation and Sifting, the current leaders. For the one-sided problem, new methods that include those based on simple stochastic hillclimbing, simulated annealing and genet.ic algorithms were tested. The new block-crossover genetic algorithm produced very good results with lower crossings than existing methods, although it tended to be slower. However, time was a secondary aim, the priority being to achieve low numbers of crossings. This algorithm can also be seeded with the output of an existing algorithm to improve results; combining with Penalty Minimisation in this way improved both the speed and number of crossings. Four parallel methods for the one-sided problem have been created, although two were abandoned because they gave bad results for even simple graphs. The other two methods, based on stochastic hill-climbing, produced acceptable results in faster times than similar sequential methods. PVM was used as the parallel communication system. Two new heuristics were studied for the two-sided problem, for which the only known existing method is to apply one-sided algorithms iteratively. The first is based on a heuristic for the linear arrangment problem; the second is a method of performing stochastic hill-climbing on two sides. A way of applying anyone-sided algorithm iteratively was also created. The linear arrangement method based on the Koren-Harel multi-scale algorithm achieved the best results, outperforming iterative Barycentre (previously the best method) and iterative Penalty Minimisation. Another area of this work created three new heuristics for the k-planar drawing problem where k > 1. These are the first known practical algorithms to solve this problem. A sequential genetic algorithm based on TimGA is devised to work on k-planar graphs. Two parallel algorithms, one island model and the other a 'mesh' model, are also given. Comparison of results for k = 2 indicate that the parallel island method is better than the other two methods. MPI was used for the parallel communication. Overall, 14 new methods are introduced, of which 10 were developed into working algorithms. For the one-sided bipartite graph drawing problem the new block-crossover genetic algorithm can produce drawings with lower crossings than the current best available algorithms. The parallel methods do not perform as well as the sequential ones, although they generally achieved the same results faster. All of the new two-sided methods worked well; the weighted two-sided swap stochastic hill-climbing method was comparable to the existing best method, iterative Barycentre, and generally produced drawings with lower crossings, although it suffered with needing a good termination condition. The new methods based on the linear arrangement problem consistently produced drawings with lower crossings than iterative Barycentre, although they were nearly always slower. A new parallel algorithm for the k-planar drawing problem, based on the island model, generally created drawings with the lowest edge-crossings, although no algorithms were known to exist to make comparisons.

Made available in DSpace on 2015-05-14T12:36:46Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 3331001 bytes, checksum: ea8e995295d4e5afdb8c4ddea63e5358 (MD5) Previous issue date: 2014-01-31 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / With the increase of data volume and the latent necessity of turn them into knowledge and information, arises the need to develop techniques able to perform the data analysis in a timely and efficient manner. Neural networks promotes an data analysis that is able to classify and predict information. However, the natural model of parallel computing proposed by neural networks, requires techniques of implementation with high processing power. The evolution of parallel hardware provides an environment with ever growing computational power. The GPU is a hardware that is able to process parallel implementations in a efficient way and at low cost. Therefore, this paper provides a technique of parallel implementation of neural networks with GPU processing and seeks to achieve an comparative analysis between different implementation techniques found in literature and the technique proposed in this paper. / Com a crescente expansão do volume de dados disponíveis e a latente necessidade de transformá-los em conhecimento e informação, faz-se necessário o desenvolvimento de técnicas capazes de realizar a análise destes dados em tempo hábil e de uma maneira eficiente. Redes Neurais promovem uma análise de dados capaz de classificá-los, como também, predizem informações sobre estes. Entretanto, Redes Neurais propõem um modelo natural de computação paralela que requer técnicas de implementação com alto poder de processamento. A crescente evolução do hardware paralelo oferece ambientes com poder computacional cada vez mais robusto. A GPU classifica-se como hardware capaz de processar implementações paralelas de uma maneira eficiente e a um custo em constante redução. Sendo assim, é apresentada uma técnica de implementação paralela de Redes Neurais com processamento em GPU. Este realiza uma análise comparativa entre diferentes técnicas de implementação encontradas na literatura e a técnica proposta neste trabalho.

Cette thèse est une contribution à la problématique de la simulation d'événements rares. A partir de l'étude des méthodes de Splitting, un nouveau cadre théorique est développé, indépendant de tout algorithme. Ce cadre, basé sur la définition d'un processus ponctuel associé à toute variable aléatoire réelle, permet de définir des estimateurs de probabilités, quantiles et moments sans aucune hypothèse sur la variable aléatoire. Le caractère artificiel du Splitting (sélection de seuils) disparaît et l'estimateur de la probabilité de dépasser un seuil est en fait un estimateur de la fonction de répartition jusqu'au seuil considéré. De plus, les estimateurs sont basés sur des processus ponctuels indépendants et identiquement distribués et permettent donc l'utilisation de machine de calcul massivement parallèle. Des algorithmes pratiques sont ainsi également proposés.Enfin l'utilisation de métamodèles est parfois nécessaire à cause d'un temps de calcul toujours trop important. Le cas de la modélisation par processus aléatoire est abordé. L'approche par processus ponctuel permet une estimation simplifiée de l'espérance et de la variance conditionnelles de la variable aléaoire résultante et définit un nouveau critère d'enrichissement SUR adapté aux événements rares / This thesis address the issue of extreme event simulation. From a original understanding of the Splitting methods, a new theoretical framework is proposed, regardless of any algorithm. This framework is based on a point process associated with any real-valued random variable and lets defined probability, quantile and moment estimators without any hypothesis on this random variable. The artificial selection of threshold in Splitting vanishes and the estimator of the probability of exceeding a threshold is indeed an estimator of the whole cumulative distribution function until the given threshold. These estimators are based on the simulation of independent and identically distributed replicas of the point process. So they allow for the use of massively parallel computer cluster. Suitable practical algorithms are thus proposed.Finally it can happen that these advanced statistics still require too much samples. In this context the computer code is considered as a random process with known distribution. The point process framework lets handle this additional source of uncertainty and estimate easily the conditional expectation and variance of the resulting random variable. It also defines new SUR enrichment criteria designed for extreme event probability estimation.

京都大学 / 新制・課程博士 / 博士(情報学) / 甲第23544号 / 情博第774号 / 新制||情||132(附属図書館) / 京都大学大学院情報学研究科先端数理科学専攻 / (主査)准教授 藤原 宏志, 教授 磯 祐介, 教授 田口 智清 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

Tato diplomová práce se zabývá vývojem a implementací algoritmu pro detekci QR kódů s integrací do platformy ROS a výpočty běžícími na grafické kartě. Z rešerše současně dostupných nástrojů a technik je vybrán vhodný postup a algoritmus je napsán jako modul v programovacím jazyce Python, který je snadno integrovatelný do ROS. Ke zprostředkování výpočtů na vícejádrovém hardware, jako jsou grafické karty či vícejádrové procesory, je využita knihovna OpenCL.

The goal of this diploma thesis was to create four laboratory exercises for the subject "Parallel Data Processing", where students will try on the options and capabilities of Apache Spark as a parallel computing platform. The work also includes basic setup and use of Apache Kafka technology and NoSQL Apache Cassandra database. The other two lab assignments focus on working with a Travelling Salesman Problem. The first lab was designed to demonstrate the difficulty of a task where the student will face an exponential increase in complexity. The second task consists of an optimization algorithm to solve the problem in cluster. This algorithm is subjected to performance measurements in clusters. The conclusion of the thesis contains recommendations for optimization as well as comparison of running with different number of computing devices.

Le code XTOR-2F simule la dynamique 3D des instabilités MHD bi-fluides de plasmas de tokamaks.La première partie de la thèse a été consacrée à la parallélisation du code XTOR-2F. Le code a été parallélisé significativement malgré la représentation pseudo-spectrale pour les deux directions angulaires, la raideur des équations résolues et l’utilisation d’une décomposition LU exacte afin d’inverser le préconditionneur physique. Le temps d’exécution de la version parallèle est un ordre de grandeur plus petit que la version séquentielle sur un maillage basse résolution. L’accélération croît ensuite avec la taille du maillage. La parallélisation permet également de réaliser des simulations avec des maillages plus grands, autrefois non réalisables par la limitation du stockage en RAM.La seconde partie de la thèse a été consacrée au développement d’une version du code permettant de réaliser des simulations en géométrie à frontière libre, s’approchant de la géométrie des tokamaks expérimentaux de grandes tailles. Les conditions initiales sont fournies par le code d’équilibre CHEASE à l’intérieur du plasma. A l’extérieur du plasma, la solution a été étendue en ajustant le potentiel magnétique avec un ensemble de bobines magnétiques poloïdales externes. Les conditions de bord utilisent des fonctions de Green afin de calculer une matrice de transfert permettant de relier les composantes tangentes et normales du champ magnétique externe à la coque avec la solution interne. Ceci permet de modéliser une coque résistive fine. Cette nouvelle version élargie le domaine d’investigation de XTOR-2F, autrefois restreint aux instabilités internes, aux instabilités externes. Le comportement linéaire du code est validé sur deux familles d’instabilités, les modes axisymétriques n = 0 et les kinks externes n = 1 / m = 2. Afin de valider le comportement non linéaire, des simulations en MHD résistive de modes tearing à bêta nul évoluant vers un état stationnaire ont été réalisées. / The XTOR-2F code simulates the 3D dynamics of full bi-fluid MHD instabilities in tokamak plasmas.The first part of the thesis was dedicated to the parallelisation of XTOR-2F code. The code has been parallelised significantly despite the numerical profile of the problem solved, i.e. a discretisation with pseudo-spectral representations in all angular directions, the stiffness of the two-fluid stability problem in tokamaks, and the use of a direct LU decomposition to invert the physical pre-conditioner. The execution time of the parallelised version is an order of magnitude smaller than the sequential one for low-resolution cases, with an increasing speedup when the discretisation mesh is refined. Moreover, it allows to perform simulations with higher resolutions, previously forbidden because of memory limitations.The second part of the thesis was dedicated to the development of free boundary condition. The original fixed boundary computational domain of the code was generalised to a free-boundary one, thus approaching closely the geometry of today’s and future large experimental devices. The initial conditions are given by the CHEASE equilibrium code inside the plasma. Outside the plasma, fitting the magnetic potential at the CHEASE computation domain boundary with a set of external poloidal magnetic coils extends the solution. The boundary conditions use Green functions to construct a response matrix matching the normal and tangential components of the outside magnetic field with the inside solution. A thin resistive wall can be added to the computational domain. This new numerical setup generalises the investigation field from internal MHD instabilities towards external instabilities. The code linear behaviour is validated with two families of instabilities, n = 0 axisymmetric modes and n = 1/m = 2 external kinks. In order to validate the nonlinear behaviour, nonlinear resistive MHD simulations of tearing modes at zero beta evolving to a stationary state have been performed.

Function optimization---finding the minimum or maximum of a given function---is an extremely challenging problem with applications in physics, economics, machine learning, engineering, and many other fields. While optimization is an active area of research, only a portion of this work acknowledges parallel computation, which is now widely available. Today, anyone with a modest budget can buy a cluster with hundreds of cores, pay for access to a supercomputer with thousands of processors, or at least purchase a laptop with 8 cores. Thus, an algorithm that works well in serial but cannot be parallelized is needlessly inefficient in real-life computationalenvironments.We address these issues in three connected threads of development: a high-level programming framework that makes it possible to create flexible and efficient implementations of optimization algorithms; improvements to an existing algorithm, Particle Swarm Optimization, to make it take better advantage of parallel resources; and a statistical model designed to efficiently use available information in parallel optimization by inferring search directions. Each of these is an essential step toward effective parallel optimization. First, without a suitable high-level programming model, expediency leads to purely serial development with parallel issues only an afterthought. Second, PSO has proven effective for optimization and is an excellent candidate to consider for efficient parallel implementations. Third, a model for inference of search directions is useful for understanding communication in the context of parallel optimization and provides a flexible base for continuing optimization research.

The topology of interconnection networks plays a key role in the performance of parallel computing systems. A new interconnection network called exchanged crossed cube (ECQ) is proposed and analyzed in this paper. We prove that ECQ has the better properties than other variations of the basic hypercube in terms of the smaller diameter, fewer links, and lower cost factor, which indicates the reduced communication overhead, lower hardware cost, and more balanced consideration among performance and cost. Furthermore, it maintains several attractive advantages including recursive structure, high partitionability, and strong connectivity. Furthermore, the optimal routing and broadcasting algorithms are proposed for this new network topology.

No description available.