11,882 research outputs found
Transactional coherence and consistency
No full textent sets of rules known as m e m o ry c o n - sistency models. Over the years, these models haveprogressed from easy-to-understand but sometimes performance-limiting sequential consistency schemes to more modern schemes such as relaxed consistency. The complex interaction of coherence, synchronization, and consistency makes the job Lance Hammond Brian D. Carlstrom Vicky Wong Michael Chen Christos Kozyrakis Kunle Olukotun Stanford University TCC S M P L I F I E S PARA L L E L HARDWAR E AND SO F T WAR E D E S I GN BY E L M NAT NG T H E N E E D F OR CONV E N T ONA L CACH E COH E R E NC E AND CONS S T E NCY MOD E L S AND L E T T I NG P ROGRAMM E RS PARA L L E L I Z E A W D E RANG E O F A P P L I CAT ONS W T H A S M P L E , L OCK -F R E E T RANSAC T ONA L MOD E L . TRANSACTIONAL COHERENCE AND CONSISTENCY: SIMPLIFYING PARALLEL HARDWARE AND SOFTWARE Published by the IEEE Computer Society 0272-1732/04/$20.00 # 2004 IEEE of parallel programming difficult. Existing a p p roache
Interconnection networks for parallel and distributed computing
Get PDFParallel computers are generally either shared-memory machines or distributed- memory machines. There are currently technological limitations on shared-memory architectures and so parallel computers utilizing a large number of processors tend tube distributed-memory machines. We are concerned solely with distributed-memory multiprocessors. In such machines, the dominant factor inhibiting faster global computations is inter-processor communication. Communication is dependent upon the topology of the interconnection network, the routing mechanism, the flow control policy, and the method of switching. We are concerned with issues relating to the topology of the interconnection network. The choice of how we connect processors in a distributed-memory multiprocessor is a fundamental design decision. There are numerous, often conflicting, considerations to bear in mind. However, there does not exist an interconnection network that is optimal on all counts and trade-offs have to be made. A multitude of interconnection networks have been proposed with each of these networks having some good (topological) properties and some not so good. Existing noteworthy networks include trees, fat-trees, meshes, cube-connected cycles, butterflies, Möbius cubes, hypercubes, augmented cubes, k-ary n-cubes, twisted cubes, n-star graphs, (n, k)-star graphs, alternating group graphs, de Bruijn networks, and bubble-sort graphs, to name but a few. We will mainly focus on k-ary n-cubes and (n, k)-star graphs in this thesis. Meanwhile, we propose a new interconnection network called augmented k-ary n- cubes. The following results are given in the thesis.1. Let k ≥ 4 be even and let n ≥ 2. Consider a faulty k-ary n-cube Q(^k_n) in which the number of node faults f(_n) and the number of link faults f(_e) are such that f(_n) + f(_e) ≤ 2n - 2. We prove that given any two healthy nodes s and e of Q(^k_n), there is a path from s to e of length at least k(^n) - 2f(_n) - 1 (resp. k(^n) - 2f(_n) - 2) if the nodes s and e have different (resp. the same) parities (the parity of a node Q(^k_n) in is the sum modulo 2 of the elements in the n-tuple over 0, 1, ∙∙∙ , k - 1 representing the node). Our result is optimal in the sense that there are pairs of nodes and fault configurations for which these bounds cannot be improved, and it answers questions recently posed by Yang, Tan and Hsu, and by Fu. Furthermore, we extend known results, obtained by Kim and Park, for the case when n = 2.2. We give precise solutions to problems posed by Wang, An, Pan, Wang and Qu and by Hsieh, Lin and Huang. In particular, we show that Q(^k_n) is bi-panconnected and edge-bipancyclic, when k ≥ 3 and n ≥ 2, and we also show that when k is odd, Q(^k_n) is m-panconnected, for m = (^n(k - 1) + 2k - 6’ / ‘_2), and (k -1) pancyclic (these bounds are optimal). We introduce a path-shortening technique, called progressive shortening, and strengthen existing results, showing that when paths are formed using progressive shortening then these paths can be efficiently constructed and used to solve a problem relating to the distributed simulation of linear arrays and cycles in a parallel machine whose interconnection network is Q(^k_n) even in the presence of a faulty processor.3. We define an interconnection network AQ(^k_n) which we call the augmented k-ary n-cube by extending a k-ary n-cube in a manner analogous to the existing extension of an n-dimensional hypercube to an n-dimensional augmented cube. We prove that the augmented k-ary n-cube Q(^k_n) has a number of attractive properties (in the context of parallel computing). For example, we show that the augmented k-ary n-cube Q(^k_n) - is a Cayley graph (and so is vertex-symmetric); has connectivity 4n - 2, and is such that we can build a set of 4n - 2 mutually disjoint paths joining any two distinct vertices so that the path of maximal length has length at most max{{n- l)k- (n-2), k + 7}; has diameter [(^k) / (_3)] + [(^k - 1) /( _3)], when n = 2; and has diameter at most (^k) / (_4) (n+ 1), for n ≥ 3 and k even, and at most [(^k)/ (_4) (n + 1) + (^n) / (_4), for n ^, for n ≥ 3 and k odd.4. We present an algorithm which given a source node and a set of n - 1 target nodes in the (n, k)-star graph S(_n,k) where all nodes are distinct, builds a collection of n - 1 node-disjoint paths, one from each target node to the source. The collection of paths output from the algorithm is such that each path has length at most 6k - 7, and the algorithm has time complexity O(k(^3)n(^4))
Analysis of a Nuclear Reactor Boilure Closure Unit Through Development of a 3D Parallel Finite Element Code
Get PDFThree dimensional (3D) finite element analysis (FEA) allows the mechanical integrity of complex structures
to be estimated with some confidence. This research is concerned with extending an existing parallel
FEA code. This code has been run on up to 16 processors on Durham University’s high performance computing
(HPC) cluster and two different parallel linear solvers have been compared. A key feature of the
work has been to develop tools for structural analyses. An automatic mesh refinement program has been
written, the Zienkiewicz and Zhu error estimator has been coded for 3D hexahedral meshes and post
processing techniques have been used to calculate and visualise principal stress data and peak stress
criteria. This project also reports on three peak stress envelopes used to assess the condition of a concrete
sub-structure.
The development of this parallel code has enabled the deformation behaviour of a key component of
a nuclear rector vessel to be determined. The BCU is a prestressed cylindrical concrete vessel (depth
of 1.73m and diameter of 3.37m) sealing the top of a boilers housed within the walls of the reactor. In
recent years possible problems have been identified at the Hartlepool and Heysham I Advance Gas-Cooled
nuclear reactors (AGR) with respect to the structural condition of the BCU (in particular the condition
of the prestressed circumferential wires designed to maintain the BCU in a state of compression). This
problem provides an interesting case study for this project. Four different BCU meshes have been used
containing either 40201 or 321608 elements (the elements are either 8 or 20-noded hexahedral elements).
Three different load cases have been used to model the BCU. The results of the analyses confirm that the
circumferential pre-stressing is vital in order to keep the BCU is a state of compression and operating
under safe working conditions. These results have been confirmed using principal stress plots and three
different peak stress envelopes. The results show that when the pre-stressing is released approximately
one quarter of the elements contain stresses at Gauss points which exceed the peak strength of the
concrete. This suggests that under these extreme conditions the BCU’s structural integrity has been
severely compromised, concrete rupture is possible and the nuclear reactor is no-longer safe to operate
Tabu Search with two approaches to parallel flowshop evaluation on CUDA platform
Get PDFThe introduction of NVidia's powerful Tesla GPU hardware and Compute Unified Device Architecture (CUDA) platform enable many-core parallel programming. As aresult, existing algorithms implemented on aGPU can run many times faster than on modern CPUs. Relatively little research has been done so far on GPU implementations of discrete optimisation algorithms. In this paper, two approaches to parallel GPU evaluation of the Permutation Flowshop Scheduling Problem, with makespan and total flowtime criteria, are proposed. These methods can be employed in most population-based algorithms, e.g. genetic algorithms, Ant Colony Optimisation, Particle Swarm Optimisation, and Tabu Search. Extensive computational experiments, on Tabu Search for Flowshop with both criteria, followed by statistical analysis, confirm great computational capabilities of GPU hardware. AGPU implementation of Tabu Search runs up to 89 times faster than its CPU counterpart
Analysis and design of massively parallel channel estimation algorithms on graphic cards
Get PDFThe necessity of accurate channel estimation for coherent multiuser detectors is well known. Indeed they are based on the assumption that signals are perfectly estimated, and this is never completely achieved in practice. Furthermore, practical transmitters and receivers are affected by many non-idealities like strong phase noise, and thus the task of channel estimation is all the more challenging. Another notorious issue is the high computational complexity of multiuser techniques. This project has devoted significant attention for massively parallel receiver architectures and the possibility to parallelize channel estimation algorithms. Nvidia CUDA graphic cards are especially well-suited to address problems that can be expressed as data parallel computations. This task is very challenging and ambitious, since the usage of such cards for receiver design is still at its infant stage.
This thesis describes the work carried out at German Aerospace Center (DLR) where a real-world multiuser detector is studied. The desired goals were the following: fine tuning of the already existing channel estimation algorithm; exploration of the factor graph approach in order to improve the estimation quality and to develop algorithms suitable to be parallelized; parallel implementation of the algorithms on CUDA graphic card.
All these points have been covered. Two different improvements for the already implemented phase estimator are proposed. Both are based on the same approximation of the Wiener-Levy phase model and assume the same knowledge at the receiver.
By adopting the factor graph approach, we present two existing algorithms for the phase estimation in a new parallel fashion and we show that, at the same time, they improve the estimation quality, and they are suitable to be parallelized on the board.
The performance improvement for all estimators proposed in terms of Mean Square Error are validated through several simulation campaigns carried out in different scenarios, most of them characterized by strong phase noise and low signal-to-noise ratios. Finally we present several parallel phase estimation algorithms working on CUDA graphic card and we show that, in some cases, we are in presence of a massive parallelization in which is achieved a speedup more than 200 times compared to the serial implementation. The results obtained represent a starting point for the implementation of a Parallel Iterative Receiver to be inserted in the existing multiuser detector and completely executed on CUDA graphic car
Massively parallel computing in Java
No full textAlthough Java was not specifically designed for the computationally intensive numeric applications that are the typical fodder of highly parallel machines, its widespread popularity and portability make it an interesting candidate vehicle for massively parallel programming. With the advent of high-performance optimizing Java compilers, the open question is: How can Java programs best exploit massive parallelism? The authors have been contemplating this question via libraries of Java-routines for specifying and coordinating parallel codes. It would be most desirable to have these routines written in 100%-Pure Java; however, a more expedient solution is to provide Java wrappers (stubs) to existing parallel coordination libraries, such as MPI. MPI is an attractive alternative, as like Java, it is portable. We discuss both approaches here. In undertaking this study, we have also identified some minor modifications of the current language specification that would make 100%-Pure Java parallel programming more natural
Exploiting Immunological Metaphors in the Development of Serial, Parallel and Distributed Learning Algorithms
Get PDFThis thesis examines the use of immunological metaphors in building serial, parallel, and distributed learning algorithms. It offers a basic study in the development of biologically-inspired algorithms which merge inspiration from biology with known, standard computing technology to examine robust methods of computing. This thesis begins by detailing key interactions found within the immune system that provide inspiration for the development of a learning system. It then exploits the use of more processing power for the development of faster algorithms. This leads to the exploration of distributed computing resources for the examination of more biologically plausible systems. This thesis offers the following main contributions. The components of the immune system that exhibit the capacity for learning are detailed. A framework for discussing learning algorithms is proposed. Three properties of every learning algorithm-memory, adaptation, and decision-making-are identified for this framework, and traditional learning algorithms are placed in the context of this framework. An investigation into the use of immunological components for learning is provided. This leads to an understanding of these components in terms of the learning framework. A simplification of the Artificial Immune Recognition System (AIRS) immune-inspired learning algorithm is provided by employing affinity-dependent somatic hypermutation. A parallel version of the Clonal Selection Algorithm (CLONALG) immune learning algorithm is developed. It is shown that basic parallel computing techniques can provide computational benefits for this algorithm. Exploring this technology further, a parallel version of AIRS is offered. It is shown that applying these same parallel computing techniques to AIRS, while less scalable than when applied to CLONALG, still provides computational gains. A distributed approach to AIRS is offered, and it is argued that this approach provides a more biologically appealing model. The simple distributed approach is proposed in terms of an initial step toward a more complex, distributed system. Biological immune systems exhibit complex cellular interactions. The mechanisms of these interactions, while often poorly understood, hint at an extremely powerful information processing/problem solving system. This thesis demonstrates how the use of immunological principles coupled with standard computing technology can lead to the development of robust, biologically inspired learning algorithms
Parallel algorithms in cryptoanalysis.
No full textThe title of this work is “Parallel algorithms in cryptoanalysis”. The main idea of this individual final work of Master studies is to research parallel algorithms and Grid usages effectivity in cryptoanalysis. In the beginning of the work author provides the information on existing parallel programming methods, existing cryptosistems, symetric encrypt decrypt algoriphm and their hacking possibilities. In the second part of work author carrying out cryptoanalysis of DES cryptographies algorithms and choosing a parallel algorithm, based on MPI protocol to the future researches and experiments. Further based on cryptoanalysis of DES cryptographies algorithms results author describing experiment which is necessary to achived the main work goal. The received results of work and formulated conclusion finish research and show, that all collected information is analyzed, and the purposes put by the author are executed. In the closing part of the work author presents the main results of the work and suggests some recommendations
Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable
No full textThere has been significant recent interest in parallel graph processing due to the need to quickly analyze the large graphs available today. Many graph codes have been designed for distributed memory or external memory. However, today even the largest publicly-available real-world graph (the Hyperlink Web graph with over 3.5 billion vertices and 128 billion edges) can fit in the memory of a single commodity multicore server. Nevertheless, most experimental work in the literature report results on much smaller graphs, and the ones for the Hyperlink graph use distributed or external memory. Therefore, it is natural to ask whether we can efficiently solve a broad class of graph problems on this graph in memory.
This paper shows that theoretically-efficient parallel graph algorithms can scale to the largest publicly-available graphs using a single machine with a terabyte of RAM, processing them in minutes. We give implementations of theoretically-efficient parallel algorithms for 20 important graph problems. We also present the interfaces, optimizations, and graph processing techniques that we used in our implementations, which were crucial in enabling us to process these large graphs quickly. We show that the running times of our implementations outperform existing state-of-the-art implementations on the largest real-world graphs. For many of the problems that we consider, this is the first time they have been solved on graphs at this scale. We have made the implementations developed in this work publicly-available as the Graph Based Benchmark Suite (GBBS).</jats:p
Optimal Design of Planar Paraller Manipulators 3 RRR Through Lower Energy Consumption
No full textOrganised by: Cranfield UniversityIn most existing studies, the solutions of planar parallel manipulators are restricted to a feasible region of solution. This research provides an optimal solution in link dimension of planar parallel manipulators to a defined trajectory and structure of the links, minimizing the mechanical energy of the manipulator.An algorithm will be obtained that allows adequate dimensioning of the manipulator for a specific task, by means of a passive reconfiguration. With this method most of the energy is used by the manipulator to execute a task, not for the manipulator’s movement. The process is illustrated with an example.Mori Seiki – The Machine Tool Compan
- …
