Дисертації з теми "Parallel and sequential regions"
Щоб переглянути інші типи публікацій з цієї теми, перейдіть за посиланням: Parallel and sequential regions.
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся з топ-50 дисертацій для дослідження на тему "Parallel and sequential regions".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Переглядайте дисертації для різних дисциплін та оформлюйте правильно вашу бібліографію.
1
Thornley, John William Chandy K. Mani Chandy K. Mani. "A parallel programming model with sequential semantics /." Diss., Pasadena, Calif. : California Institute of Technology, 1996. http://resolver.caltech.edu/CaltechETD:etd-01042008-085720.
Повний текст джерела
2
Manthey, Norbert. "Towards Next Generation Sequential and Parallel SAT Solvers." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2015. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-158672.
Повний текст джерелаАнотація:
This thesis focuses on improving the SAT solving technology. The improvements focus on two major subjects: sequential SAT solving and parallel SAT solving.
To better understand sequential SAT algorithms, the abstract reduction system Generic CDCL is introduced. With Generic CDCL, the soundness of solving techniques can be modeled. Next, the conflict driven clause learning algorithm is extended with the three techniques local look-ahead, local probing and all UIP learning that allow more global reasoning during search. These techniques improve the performance of the sequential SAT solver Riss. Then, the formula simplification techniques bounded variable addition, covered literal elimination and an advanced cardinality constraint extraction are introduced. By using these techniques, the reasoning of the overall SAT solving tool chain becomes stronger than plain resolution. When using these three techniques in the formula simplification tool Coprocessor before using Riss to solve a formula, the performance can be improved further.
Due to the increasing number of cores in CPUs, the scalable parallel SAT solving approach iterative partitioning has been implemented in Pcasso for the multi-core architecture. Related work on parallel SAT solving has been studied to extract main ideas that can improve Pcasso. Besides parallel formula simplification with bounded variable elimination, the major extension is the extended clause sharing level based clause tagging, which builds the basis for conflict driven node killing. The latter allows to better identify unsatisfiable search space partitions. Another improvement is to combine scattering and look-ahead as a superior search space partitioning function. In combination with Coprocessor, the introduced extensions increase the performance of the parallel solver Pcasso. The implemented system turns out to be scalable for the multi-core architecture. Hence iterative partitioning is interesting for future parallel SAT solvers.
The implemented solvers participated in international SAT competitions. In 2013 and 2014 Pcasso showed a good performance. Riss in combination with Copro- cessor won several first, second and third prices, including two Kurt-Gödel-Medals. Hence, the introduced algorithms improved modern SAT solving technology.
3
Howells, Paul. "Communicating sequential processes with flexible parallel termination semantics." Thesis, University of Westminster, 2005. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.433839.
Повний текст джерела
4
Goldberg, Andrew Vladislav. "Efficient graph algorithms for sequential and parallel computers." Thesis, Massachusetts Institute of Technology, 1987. http://hdl.handle.net/1721.1/14912.
Повний текст джерелаАнотація:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1987.MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING.
Bibliography: p. 117-123.
by Andrew Vladislav Goldberg.
Ph.D.
5
Kercher, James P. Baer Tomas. "On parallel and sequential dissociations in energy selected ions." Chapel Hill, N.C. : University of North Carolina at Chapel Hill, 2006. http://dc.lib.unc.edu/u?/etd,577.
Повний текст джерелаАнотація:
Thesis (Ph. D.)--University of North Carolina at Chapel Hill, 2006.Title from electronic title page (viewed Oct. 10, 2007). "... in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the Department of Chemistry." Discipline: Chemistry; Department/School: Chemistry.
6
Wang, Ting. "Algorithms for parallel and sequential matrix-chain product problem." Ohio : Ohio University, 1997. http://www.ohiolink.edu/etd/view.cgi?ohiou1184355429.
Повний текст джерела
7
Tabirca, Sabin Marius. "Sequential and parallel aspects of the maximum flow problem." Thesis, Brunel University, 1998. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.391747.
Повний текст джерела
8
Arigu, Moses Azimeh. "Parallel and sequential algorithms for hyperbolic partial differential equations." Thesis, Brunel University, 1993. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.357705.
Повний текст джерела
9
Kapsalis, A. "Genetic algorithms : sequential and parallel implementations and case studies." Thesis, University of East Anglia, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.318080.
Повний текст джерелаАнотація:
Practical issues concerning the implementation and application of genetic algorithms to a number of optimisation problems are the main subjects dealt with in this thesis. Genetic algorithms (GAs) are an attractive class of computational models that attempt to mimic the mechanisms of natural evolution to solve problems in a wide variety of domains. A general purpose genetic algorithm toolkit is developed and applied to the Steiner Problem in Graphs and the Radio Link Frequency Assignment Problem. The toolkit is then extended to cover a large number of parallel genetic algorithm models which are then compared. Solutions for the two case studies are presented with each of the parallel GAs. The thesis begins with a general introduction to genetic algorithms. Holland's original genetic algorithm is described and it's workings illustrated on a simple function minimisation problem. The notion of a schema or similarity template as a basic building block in genetic algorithms is introduced and the schema theory presented. A description of important theoretical results is given and the introduction to genetic algorithms continues with practical issues that are dealt with in the second chapter. The basic components of a modern genetic algorithm are outlined and examples for important components, as found in the Jiterature, are given. The second chapter concludes with the description of a number of applications of genetic algorithms to areas such as function optimisation, combinatorial optimisation, genetic programming, process control and classifier systems. In Chapter 3, the sequential GA toolkit, GAmeter, is described. The General Search paradigm around which the toolkit is implemented is introduced. Notable characteristics of the genetic algorithms kernel and the user interface are mentioned. A popular function optimisation problem is used to illustrate important aspects of genetic algorithms and aspects specific to the toolkit. The Steiner Tree problem in graphs is the first of two case studies examined in detail in this thesis. This is a popular NP-complete problem with a range of applications in areas such as communications, scheduling and printed circuit design. A survey of standard techniques, such as simplification methods, exact algorithms and heuristics is given. Two possible representations for solving it using genetic algorithms are described and applied to a well-known set of problems. Chapter 4 concludes with a comparison of the best GA technique with other heuristics for this problem. The Radio Link Frequency Assignment Problem, described in Chapter 5, is the second case study investigated in this thesis. Genetic algorithms were applied to this problem as part of a EUCLID (European Cooperation for the Long Term in Defence) funded multi-national study to compare exact and heuristic techniques for hard combinatorial problems associated with military applications. A number of approaches used to solve this highly constrained, hard problem for genetic algorithms are described. These include a range of new genetic operators and catalytic terms that are added to the fitness function. Apart from the direct approach to solving this problem using genetic algorithms, for which the majority of operators and catalytic terms apply, an indirect approach which combines genetic algorithms with backtracking is described. The possibility of using a meta genetic algorithm to chose the best of a multitude of options, e.g. genetic operators and parameter settings for a GA applied to the Radio Link Frequency Assignment Problem is investigated. Results are reported for two sets of problems that were used by all participants in this project. An overview of the techniques investigated for this project is given and the chapter concludes with comparisons between all these techniques. In Chapter 6, an overview of general aspects in parallel processing is given. Parallel computer architectures, parallel programming paradigms and performance measurement are the main subjects dealt with in this chapter. Special emphasis is given to material relevant to the investigation on parallel genetic algorithms, presented in the following chapter. In Chapter 7, parallel genetic algorithms are examined in some detail. A number of parallel GA models are described and classified according to whether they are designed around the sequential GA or around a more natural model. A ParallelSequential General Search paradigm is presented that unifies the various parallel models and is used to extend the GA toolkit into a parallel GA toolkit for a parallel system based on Transputers. The parallel GA models are applied to problems from both of the case studies considered in this thesis. A comparison between the various parallel GA models concludes this chapter. The thesis finishes with a summary of a number of conclusions drawn from this research together with some suggestions for how this work may be continued in the future.
10
Newton, Matthew. "Sequential and parallel algorithms for low-crossing graph drawing." Thesis, Loughborough University, 2007. https://dspace.lboro.ac.uk/2134/12944.
Повний текст джерелаАнотація:
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.
11
Chishti, Fida H. "Finite element based thermal analysis : sequential and parallel methods." Thesis, University of East Anglia, 1993. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.359799.
Повний текст джерела
12
Ford, Of The. "Parallel worlds : attribute-defined regions in global human geography /." Thesis, Connect to resource online, 2009. http://hdl.handle.net/1805/2004.
Повний текст джерелаАнотація:
Thesis (M.S.)--Indiana University, 2009.Department of Geography, Indiana University-Purdue University Indianapolis (IUPUI). Advisor(s): Owen J. Dwyer, Jeffrey S. Wilson, Scott M. Pegg. Includes vitae. Includes bibliographical references (leaves 135-168).
13
Liu, Xuan. "Sequential and parallel algorithms for sequence analysis problems in bioinformatics." Thesis, Loughborough University, 2008. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.506205.
Повний текст джерела
14
Bae, Sung Eun. "Sequential and Parallel Algorithms for the Generalized Maximum Subarray Problem." Thesis, University of Canterbury. Computer Science and Software Engineering, 2007. http://hdl.handle.net/10092/1202.
Повний текст джерелаАнотація:
The maximum subarray problem (MSP) involves selection of a segment of consecutive array elements that has the largest possible sum over all other segments in a given array. The efficient algorithms for the MSP and related problems are expected to contribute to various applications in genomic sequence analysis, data mining or in computer vision etc. The MSP is a conceptually simple problem, and several linear time optimal algorithms for 1D version of the problem are already known. For 2D version, the currently known upper bounds are cubic or near-cubic time. For the wider applications, it would be interesting if multiple maximum subarrays are computed instead of just one, which motivates the work in the first half of the thesis. The generalized problem of K-maximum subarray involves finding K segments of the largest sum in sorted order. Two subcategories of the problem can be defined, which are K-overlapping maximum subarray problem (K-OMSP), and K-disjoint maximum subarray problem (K-DMSP). Studies on the K-OMSP have not been undertaken previously, hence the thesis explores various techniques to speed up the computation, and several new algorithms. The first algorithm for the 1D problem is of O(Kn) time, and increasingly efficient algorithms of O(K² + n logK) time, O((n+K) logK) time and O(n+K logmin(K, n)) time are presented. Considerations on extending these results to higher dimensions are made, which contributes to establishing O(n³) time for 2D version of the problem where K is bounded by a certain range. Ruzzo and Tompa studied the problem of all maximal scoring subsequences, whose definition is almost identical to that of the K-DMSP with a few subtle differences. Despite slight differences, their linear time algorithm is readily capable of computing the 1D K-DMSP, but it is not easily extended to higher dimensions. This observation motivates a new algorithm based on the tournament data structure, which is of O(n+K logmin(K, n)) worst-case time. The extended version of the new algorithm is capable of processing a 2D problem in O(n³ + min(K, n) · n² logmin(K, n)) time, that is O(n³) for K ≤ n/log n For the 2D MSP, the cubic time sequential computation is still expensive for practical purposes considering potential applications in computer vision and data mining. The second half of the thesis investigates a speed-up option through parallel computation. Previous parallel algorithms for the 2D MSP have huge demand for hardware resources, or their target parallel computation models are in the realm of pure theoretics. A nice compromise between speed and cost can be realized through utilizing a mesh topology. Two mesh algorithms for the 2D MSP with O(n) running time that require a network of size O(n²) are designed and analyzed, and various techniques are considered to maximize the practicality to their full potential.
15
Wilson, Janet Kirsten. "Procedures for sequential and parallel automatic adaptive tetrahedral mesh generation." Thesis, Heriot-Watt University, 1997. http://hdl.handle.net/10399/1171.
Повний текст джерела
16
Dang, Florian. "Sequential/parallel reusability study on solving Hamilton-Jacobi-Bellman equations." Thesis, Versailles-St Quentin en Yvelines, 2015. http://www.theses.fr/2015VERS027V/document.
Повний текст джерелаАнотація:
La simulation numérique est indissociable du calcul haute performance. Ces vingt dernières années,l'informatique a connu l'émergence d'architectures parallèles multi-niveaux. Exploiter efficacement lapuissance de calcul de ces machines peut s'avérer être une tâche délicate et requérir une expertise à la foistechnologique sur des notions avancées de parallélisme ainsi que scientifique de part la nature même desproblèmes traités.Le travail de cette thèse est pluri-disciplinaire s'appuyant sur la conception d'une librairie de calculparallèle réutilisable pour la résolution des équations Hamilton-Jacobi-Bellman. Ces équations peuventse retrouver dans des domaines diverses et variés tels qu'en biomédical, géophysique, ou encore robotiqueen l'occurence sur les applications de planification de mouvement et de reconstruction de formestri-dimensionnelles à partir d'images bi-dimensionnelles. Nous montrons que les principaux algorithmesnumériques amenant a résoudre ces équations telles que les méthodes de type fast marching, ne sont pasappropriés pour être efficaces dans un contexte parallèle. Nous proposons la méthode buffered fast iterativequi permet d'obtenir une scalabilité parallèle non obtenue jusqu'alors. Un des points sensibles relevésdans cette thèse est de parvenir à trouver une recette de compromis entre abstraction, performance etmaintenabilité afin de garantir non seulement une réutilisabilitédans le sens classique du domaine de génielogiciel mais également en terme de réutilisabilité séquentielle/parallèleNumerical simulation is strongly bound with high performance computing. Programming scientificsoftwares requires at the same time good knowledge on the mathematical numerical models and alsoon the techniques to make them efficient on today's computers. Indeed, these last twenty years, wehave experienced the rising of multi-level parallel architectures. The work in this thesis dissertation ismultidisciplinary by designing a reusable parallel numerical library for solving Hamilton-Jacobi-Bellmanequations. Such equations are involved in various fields such as in biomedical, geophysics or robotics. Inparticular, we will show interests in path planning and shape from shading applications. We show thatthe methods to solve these equations such as the widely used fast marching method, are not designedto be used effciently in a parallel context. We propose a buffered fast iterative method which givesan interesting parallel scalability. This dissertation takes interest in the challenge to find compromisesbetween abstraction, performance and maintainability in order to combine both software reusability andalso sequential/parallel reusability. We propose code abstraction allowing algorithmic and data genericitywhile trying to keep a maintainable and performant code potentially parallelizable
17
Lima, Joubert de Castro. "Sequential and parallel approaches to reduce the data cube size." Instituto Tecnológico de Aeronáutica, 2009. http://www.bd.bibl.ita.br/tde_busca/arquivo.php?codArquivo=786.
Повний текст джерелаАнотація:
Since the introduction of Data Warehouse (DW) and Online Analytical Processing (OLAP) technologies, efficient computation of data cubes has become one of the most relevant and pervasive problems in the DW area. The data cube operator has exponential complexity; therefore, the materialization of a data cube involves both huge amount of memory and substantial amount of time for its generation. Reducing the size of data cubes, without loss of generality, thus becomes one of the essential aspects for achieving effective OLAP services. Previous approaches reduce substantially the cube size using graph representations. A data cube can be viewed as a set of sub-graphs. In general, the approaches eliminate prefix redundancy and part of suffix redundancy of a data cube. In this work, we propose three major contributions to reduce the data cube size: MDAG, MCG and p-Cube Approaches. The MDAG approach eliminates the wildcard all (*), which represents an entire aggregation, from the cube representation, using the dimensional ID. It also uses the internal nodes to reduce the cube representation height, number of branches and number of common suffixed nodes. Unfortunately, the MDAG approach just reduces the data cube suffix redundancy, so in order to complete eliminate prefix/suffix redundancies we propose the MCG approach. The MCG approach produces a full cube with a reduction ratio of 70-90% when compared to a Star full cube representation. In the same scenarios, the new Star approach, proposed in 2007, reduces only 10-30%, Dwarf 30-50% and MDAG 40-60% of memory consumption when compared to Star approach. Our approaches are, on average, 20-50% faster than Dwarf and Star approaches. In this work, we also propose a parallel cube approach, named p-Cube. The p-Cube approach improves the runtime of Star, MDAG and MCG approaches, while keeping their low memory consumption benefits. The p-Cube approach uses an attribute-based data cube decomposition strategy which combines both task and data parallelism. It uses the dimensions attribute values to partition the data cube into a set of disjoint sub-cubes with similar size. The p-Cube approach provides similar memory consumption among its threads. Its logical design can be implemented in shared-memory, distributed-memory and hybrid architectures with minimal adaptation.
18
Felizardo, Rui Miguel Meireles. "A study on parallel versus sequential relational fuzzy clustering methods." Master's thesis, Faculdade de Ciências e Tecnologia, 2011. http://hdl.handle.net/10362/5663.
Повний текст джерелаАнотація:
Dissertação para obtenção do Grau de Mestre em Engenharia InformáticaRelational Fuzzy Clustering is a recent growing area of study. New algorithms have been developed,as FastMap Fuzzy c-Means (FMFCM) and the Fuzzy Additive Spectral Clustering Method(FADDIS), for which it had been obtained interesting experimental results in the corresponding founding works. Since these algorithms are new in the context of the Fuzzy Relational clustering community, not many experimental studies are available. This thesis comes in response to the need of further investigation on these algorithms, concerning a comparative experimental study from the two families of algorithms: the parallel and the sequential versions. These two families of algorithms differ in the way they cluster data. Parallel versions extract clusters simultaneously from data and need the number of clusters as an input parameter of the algorithms, while the sequential versions extract clusters one-by-one until a stop condition is verified, being the number of clusters a natural output of the algorithm. The algorithms are studied in their effectiveness on retrieving good cluster structures by analysing the quality of the partitions as well as the determination of the number of clusters by applying several validation measures. An extensive simulation study has been conducted over two data generators specifically constructed for the algorithms under study, in particular to study their robustness for data with noise. Results with benchmark real data are also discussed. Particular attention is made on the most adequate pre-processing on relational data, in particular on the pseudo-inverse Laplacian transformation.
19
SURENDIRANATH, SUDHA. "ACCELERATING DNA SEQUENTIAL ANALYSIS EXPLOITING PARALLEL HARDWARE AND RECONFIGURABLE COMPUTING." University of Cincinnati / OhioLINK, 2005. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1131856327.
Повний текст джерела
20
Thompson, R. T. "Fast sequential and parallel methods for solving multistage stochastic linear programmes." Thesis, University of Essex, 1998. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.387829.
Повний текст джерела
21
Surendiranath, Sudha. "Accelerating DNA sequential analysis through exploiting parallel hardware and reconfigurable computing." Cincinnati, Ohio : University of Cincinnati, 2005. http://www.ohiolink.edu/etd/view.cgi?acc%5Fnum=ucin1131856327.
Повний текст джерела
22
Cinel, Sertac. "Sequential And Parallel Heuristic Algorithms For The Rectilinear Steiner Tree Problem." Master's thesis, METU, 2006. http://etd.lib.metu.edu.tr/upload/12607896/index.pdf.
Повний текст джерелаАнотація:
The Steiner Tree problem is one of the most popular graph problems and has many application areas. The rectilinear version of this problem, introduced by Hanan, has taken special attention since it addresses a fundamental matter in &ldquoPhysical Design&rdquo
phase of the Very Large Scale Integrated (VLSI) Computer Aided Design (CAD) process. The Rectilinear Steiner Tree Problem asks for a minimum length tree that interconnects a given set of points by only horizontal and vertical line segments, enabling the use of extra points. There are various exact algorithms. However the problem is NP-complete hence approximation algorithms have to be used especially for large instances. In this thesis work, first a survey on heuristics for the Rectilinear Steiner Tree Problem is conducted and then two recently developed successful algorithms, BGA by Kahng et. al. and RST by Zhou have been studied and investigated deeply. Both algorithms have subproblems, most of which have individual backgrounds in literature. After an analysis of BGA and RST, the thesis proposes a modification on RST, which leads to a faster and non-recursive version. The efficiency of the modified algorithm has been validated by computational tests using both random and VLSI benchmark instances. A partially parallelized version of the modified algorithm is also proposed for distributed computing environments. It is implemented using MPI (message passing interface) middleware and the results of comparative tests conducted on a cluster of workstations are presented. The proposed distributed algorithm has also proved to be promising especially for large problem instances.
23
Louis, Pierre-Yves, and Jean-Baptiste Rouquier. "Time-to-Coalescence for interacting particle systems : parallel versus sequential updating." Universität Potsdam, 2009. http://opus.kobv.de/ubp/volltexte/2011/4945/.
Повний текст джерелаАнотація:
Studying the influence of the updating scheme for MCMC algorithm on spatially extended models is a well known problem. For discrete-time interacting particle systems we study through simulations the effectiveness of a synchronous updating scheme versus the usual sequential one. We compare the speed of convergence of the associated Markov chains from the point of view of the time-to-coalescence arising in the coupling-from-the-past algorithm. Unlike the intuition, the synchronous updating scheme is not always the best one. The distribution of the time-to-coalescence for these spatially extended models is studied too.
24
Gumel, Abba Babandi. "Parallel and sequential algorithms for second-order parabolic equations with applications." Thesis, Brunel University, 1993. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.385802.
Повний текст джерела
25
Tener, Greg. "ATTACKS ON DIFFICULT INSTANCES OF GRAPH ISOMORPHISM: SEQUENTIAL AND PARALLEL ALGORITHMS." Doctoral diss., University of Central Florida, 2009. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/2631.
Повний текст джерелаАнотація:
The graph isomorphism problem has received a great deal of attention on both theoretical and practical fronts. However, a polynomial algorithm for the problem has yet to be found. Even so, the best of the existing algorithms perform well in practice; so well that it is challenging to find hard instances for them. The most efficient algorithms, for determining if a pair of graphs are isomorphic, are based on the individualization-refinement paradigm, pioneered by Brendan McKay in 1981 with his algorithm nauty. Nauty and various improved descendants of nauty, such as bliss and saucy, solve the graph isomorphism problem by determining a canonical representative for each of the graphs. The graphs are isomorphic if and only if their canonical representatives are identical. These algorithms also detect the symmetries in a graph which are used to speed up the search for the canonical representative--an approach that performs well in practice. Yet, several families of graphs have been shown to exist which are hard for nauty-like algorithms. This dissertation investigates why these graph families pose difficulty for individualization-refinement algorithms and proposes several techniques for circumventing these limitations. The first technique we propose addresses a fundamental problem pointed out by Miyazaki in 1993. He constructed a family of colored graphs which require exponential time for nauty (and nauty's improved descendants). We analyze Miyazaki's construction to determine the source of difficulty and identify a solution. We modify the base individualization-refinement algorithm by exploiting the symmetries discovered in a graph to guide the search for its canonical representative. This is accomplished with the help of a novel data structure called a guide tree. As a consequence, colored Miyazaki graphs are processed in polynomial time--thus obviating the only known exponential upper-bound on individualization-refinement algorithms (which has stood for the last 16 years). The preceding technique can only help if a graph has enough symmetry to exploit. It cannot be used for another family of hard graphs that have a high degree of regularity, but possess few actual symmetries. To handle these instances, we introduce an adaptive refinement method which utilizes the guide-tree data structure of the preceding technique to use a stronger vertex-invariant, but only when needed. We show that adaptive refinement is very effective, and it can result in dramatic speedups. We then present a third technique ideally suited for large graphs with a preponderance of sparse symmetries. A method was devised by Darga et al. for dealing with these large and highly symmetric graphs, which can reduce runtime by an order of magnitude. We explain the method and show how to incorporate it into our algorithm. Finally, we develop and implement a parallel algorithm for detecting the symmetries in, and finding a canonical representative of a graph. Our novel parallel algorithm divides the search for the symmetries and canonical representative among each processor, allowing for a high degree of scalability. The parallel algorithm is benchmarked on the hardest problem instances, and shown to be effective in subdividing the search space.Ph.D.
School of Electrical Engineering and Computer Science
Engineering and Computer Science
Computer Science PhD
26
Drakos, Nikos. "Sequential and parallel execution of logic programs with dependency directed backtracking." Thesis, University of Leeds, 1990. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.277238.
Повний текст джерела
27
Xingyu, Luo, and Zhang Qishan. "A PARALLEL -SEQUENTIAL SEARCH ALGORITHM IN A HIGH DYNAMIC GPS RECEIVER." International Foundation for Telemetering, 2002. http://hdl.handle.net/10150/607533.
Повний текст джерелаАнотація:
International Telemetering Conference Proceedings / October 21, 2002 / Town & Country Hotel and Conference Center, San Diego, CaliforniaIt is need to design acquisition and tracking for code loop and carrier loop to detect the high dynamic Global Position System (GPS) signal. Acquiring signal quickly and shortening acquisition time in the cold case are key technology of a high dynamic GPS receiver. Moreover, fast acquisition of C/A code is the base of code tracking and carrier acquisition and tracking. This paper describes elements and implementation of a new parallel-sequential search Algorithm to acquire C/A code of the high dynamic GPS signal. And combined with a 12-channel correlator named GP2021 produced by GEC Co., the arithmetic implementation to acquire C/A code of the high dynamic GPS signal used sequential search based on DSP technology is also given.
28
Irani, Kashmira M. "Preconditioned sequential and parallel conjugate gradient algorithms for homotopy curve tracking." Thesis, Virginia Tech, 1990. http://hdl.handle.net/10919/41971.
Повний текст джерелаАнотація:
There are algorithms for finding zeros or fixed points of nonlinear systems of equations
that are globally convergent for almost all starting points, i.e., with probability one.
The essence of all such algorithms is the construction of an appropriate homotopy map and
then tracking some smooth curve in the zero set of this homotopy map. HOMPACK is
a mathematical software package implementing globally convergent homotopy algorithms
with three different techniques for tracking a homotopy zero curve, and has separate routines
for dense and sparse Jacobian matrices. The HOMPACK algorithms for sparse Jacobian
matrices use a preconditioned conjugate gradient algorithm for the computation of the kernel
of the homotopy Jacobian matrix, a required linear algebra step for homotopy curve
tracking. Variants of the conjugate gradient algorithm along with different preconditioners
are implemented in the context of homotopy curve tracking and compared with Craig's preconditioned
conjugate gradient method used in HOMPACK. In addition, a parallel version
of Craig's method with incomplete LU factorization preconditioning is implemented on a
shared memory parallel computer with various levels and degrees of parallelism (e.g., linear
algebra, function and Jacobian matrix evaluation, etc.). An in-depth study is presented
for each of these levels with respect to the speedup in execution time obtained with the
parallelism, the time spent implementing the parallel code and the extra memory allocated
by the parallel algorithm.
Master of Science
29
Higiro, Julius Didier. "MANAGING PENDING EVENTS IN SEQUENTIAL & OPTIMISTIC PARALLEL DISCRETE EVENT SIMULATIONS." Miami University / OhioLINK, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=miami1512034353883027.
Повний текст джерела
30
Nair, Rajesh. "On improving parallel pattern single fault propagation for synchronous sequential circuits." Thesis, This resource online, 1994. http://scholar.lib.vt.edu/theses/available/etd-06302009-040508/.
Повний текст джерела
31
Tener, Greg Daniel. "Attacks on difficult instances of graph isomorphism sequential and parallel algorithms /." Orlando, Fla. : University of Central Florida, 2009. http://purl.fcla.edu/fcla/etd/CFE0002894.
Повний текст джерела
32
Chen, Y. "Formal methods for global synchrony." Thesis, University of Oxford, 2001. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.365295.
Повний текст джерела
33
Nyholm, Joel. "A study about differences in performance with parallel and sequential sorting algorithms." Thesis, Blekinge Tekniska Högskola, Institutionen för programvaruteknik, 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:bth-21469.
Повний текст джерелаАнотація:
Background: Sorting algorithms are an essential part of computer science. With the use of parallelism, these algorithms performance can improve. Objectives: To assess parallel sorting algorithms performance compared with their sequential counterparts and see what contextual factors make a difference in performance. Methods: An experiment was made with quicksort, merge sort, load-balanced parallel merge sort and hyperquicksort. These algorithms executed on Ubuntu 20.10 and Windows 10 Home with three data sets, small (106 integers), medium (5 106 integers) and large (107 integers). Each algorithm executed 1 000 times per data set within each operating system resulting in 6 000 executions per sorting algorithm. Results: With the data from the executions, it was concluded that hyperquicksort had the fastest execution time. On average load-balanced parallel merge sort had the slowest execution time. The fastest operating system was Ubuntu 20.10, all but one algorithm executed faster on Ubuntu. Conclusions: The results showed that the fastest algorithm was hyperquicksort, but other conclusions also arose. The data set size correlated with both the execution time and speedup for a given parallel sorting algorithm. When the data set size increased, both the execution time and the speedup increased.
34
Tiew, Chin-Yaw. "On improving the performance of parallel fault simulation for synchronous sequential circuits." Thesis, This resource online, 1993. http://scholar.lib.vt.edu/theses/available/etd-03042009-040323/.
Повний текст джерела
35
Ren, Ruichao. "Accelerating Markov chain Monte Carlo simulation through sequential updating and parallel computing." Diss., Restricted to subscribing institutions, 2007. http://proquest.umi.com/pqdweb?did=1428844711&sid=1&Fmt=2&clientId=1564&RQT=309&VName=PQD.
Повний текст джерела
36
Hemmelmayr, Vera. "Sequential and parallel large neighborhood search algorithms for the periodic location routing problem." Elsevier, 2015. http://dx.doi.org/10.1016/j.ejor.2014.11.024.
Повний текст джерелаАнотація:
We propose a large neighborhood search (LNS) algorithm to solve the periodic location routing problem (PLRP). The PLRP combines location and routing decisions over a planning horizon in which customers require visits according to a given frequency and the specific visit days can be chosen. We use parallelization strategies that can exploit the availability of multiple processors. The computational results show that the algorithms obtain better results than previous solution methods on a set of standard benchmark instances from the literature.
37
Karnick, Amol S. "High speed 3D ultrasound reconstruction : a comparative study between parallel and sequential processors." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape11/PQDD_0024/MQ50628.pdf.
Повний текст джерела
38
Sahib, Shahrin. "Realisation of the Parallel Communicating Sequential Code methodology and its automatic code generators." Thesis, University of Sheffield, 1995. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.319418.
Повний текст джерела
39
Reid, James F. "Sequential and parallel algorithms for decomposing partially occluded one and two-dimensional texts." Thesis, King's College London (University of London), 2001. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.368886.
Повний текст джерела
40
Elamvazuthi, Chandran. "The evolution of the PCSC methodology and its toolset." Thesis, University of Sheffield, 1995. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.296816.
Повний текст джерела
41
Courbin, Pierre. "Scheduling sequential or parallel hard real-time pre-emptive tasks upon identical multiprocessor platforms." Thesis, Paris Est, 2013. http://www.theses.fr/2013PEST1081/document.
Повний текст джерелаАнотація:
L'ordonnancement de tâches sur un système temps réel dur correspond à trouver une façon de choisir, à chaque instant, quelle tâche doit être exécutée sur le processeur pour que chacune ait le temps de terminer son travail avant son échéance. Ce problème, dans le contexte monoprocesseur, est déjà bien étudié et permet des applications sur des systèmes en production (aérospatiale, bourse etc.). Aujourd'hui, les plateformes multiprocesseur se sont généralisées et ont amené de nombreuses questions telles que l'utilisation efficace de tous les processeurs. Dans cette thèse, nous explorons les approches existantes pour résoudre ce problème. Nous étudions tout d'abord l'approche par partitionnement qui consiste à utiliser les recherches existantes en ramenant ce problème à plusieurs systèmes monoprocesseur. Ici, nous proposons un algorithme générique dont les paramètres sont adaptables en fonction de l'objectif à atteindre. Nous étudions ensuite l'approche par semi-partitionnement qui permet la migration d'un nombre restreint de tâches. Nous proposons une solution avec des migrations restreintes qui pourrait être assez simplement implémentée sur des systèmes concrets. Nous proposons ensuite une solution avec des migrations non restreintes qui offre de meilleurs résultats mais est plus difficile à implémenter. Enfin, les programmeurs utilisent de plus en plus le concept de tâches parallèles qui peuvent utiliser plusieurs processeurs en même temps. Ces tâches sont encore peu étudiées et nous proposons donc un nouveau modèle pour les représenter. Nous étudions les ordonnanceurs possibles et nous définissons une façon de garantir l'ordonnançabilité de ces tâches pour deux d'entre euxThe scheduling of tasks on a hard real-time system consists in finding a way to choose, at each time instant, which task should be executed on the processor so that each succeed to complete its work before its deadline. In the uniprocessor case, this problem is already well studied and enables us to do practical applications on real systems (aerospace, stock exchange etc.). Today, multiprocessor platforms are widespread and led to many issues such as the effective use of all processors. In this thesis, we explore the existing approaches to solve this problem. We first study the partitioning approach that reduces this problem to several uniprocessor systems and leverage existing research. For this one, we propose a generic partitioning algorithm whose parameters can be adapted according to different goals. We then study the semi-partitioning approach that allows migrations for a limited number of tasks. We propose a solution with restricted migration that could be implemented rather simply on real systems. We then propose a solution with unrestricted migration which provides better results but is more difficult to implement. Finally, programmers use more and more the concept of parallel tasks that can use multiple processors simultaneously. These tasks are still little studied and we propose a new model to represent them. We study the possible schedulers and define a way to ensure the schedulability of such tasks for two of them
42
Baumstark, Lewis Benton Jr. "Extracting Data-Level Parallelism from Sequential Programs for SIMD Execution." Diss., Georgia Institute of Technology, 2004. http://hdl.handle.net/1853/4823.
Повний текст джерелаАнотація:
The goal of this research is to retarget multimedia programs written in sequential languages (e.g., C) to architectures with data-parallel execution capabilities. Image processing algorithms often have a high potential for data-level parallelism, but the artifacts imposed by the sequential programming language (e.g., loops, pointer variables) can obscure the parallelism and prohibit generation of efficient parallel code. This research presents a program representation and recognition approach for generating a data parallel program specification from sequential source code and retargeting it to data parallel execution mechanisms. The representation is based on an extension of the multi-dimensional synchronous dataflow model of computation. A partial recognition approach identifies and transforms only those program elements that hinder parallelization while leaving other computational elements intact. This permits flexibility in the types of programs that can be retargeted, while avoiding the complexity of complete program recognition.
This representation and recognition process is implemented in the PARRET system, which is used to extract the high-level specification of a set of image-processing programs. From this specification, code is generated for Intels SSE2 instruction set and for the SIMPil processor. The results demonstrate that PARRET can exploit, given sufficient parallel resources, the maximum available parallelism in the retargeted applications. Similarly, the results show PARRET can also exploit parallelism on architectures with hardware-limited parallel resources.
It is desirable to estimate potential parallelism before undertaking the expensive process of reverse engineering and retargeting. The goal is to narrow down the search space to a select set of loops which have a high likelihood of being data-parallel. This work also presents a hybrid static/dynamic approach, called DLPEST, for estimating the data-level parallelism in sequential program loops. We demonstrate the correctness of the DLPESTs estimates, show that estimates for programs of 25 to 5000 lines of code can be performed in under 10 minutes and that estimation time scales sub-linearly with input program size.
43
Manthey, Norbert [Verfasser], Steffen [Akademischer Betreuer] Hölldobler, and Armin [Akademischer Betreuer] Biere. "Towards Next Generation Sequential and Parallel SAT Solvers / Norbert Manthey. Gutachter: Steffen Hölldobler ; Armin Biere." Dresden : Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2015. http://d-nb.info/1069092452/34.
Повний текст джерела
44
Evans, Greg. "Concurrent processing of visual and auditory information : an assessment of parallel versus sequential processing models /." Title page, contents and summary only, 1994. http://web4.library.adelaide.edu.au/theses/09PH/09phe922.pdf.
Повний текст джерела
45
Liu, Quanquan. "Red-blue and standard pebble games : complexity and applications in the sequential and parallel models." Thesis, Massachusetts Institute of Technology, 2017. http://hdl.handle.net/1721.1/113129.
Повний текст джерелаАнотація:
Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2017.This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (pages 73-76).
Pebble games are games played on directed acyclic graphs involving placing and moving pebbles on nodes of the graph according to a certain set of rules. The standard pebble game (also known as the black pebble game) is the first of such games played on DAGs. The game itself involves three simple rules: a pebble can be placed on any leaf node (a node without any predecessors), a pebble can be moved or placed on a non-leaf node if all of its predecessors are pebbled, and a pebble can be deleted from any node at any time. Generally, the standard pebble game is used to model space-bounded computation. Each node represents a result of a computation and placing a pebble on a node represents performing a deterministic computation of a result using previously computed results. The standard pebble game has been used in a variety of applications including register allocation, VLSI design, compilers, and, more recently, propositional proof complexity and memory-hard functions. Much previous research has been done in analyzing the computational complexity of the standard pebble game in a variety of settings. It has been shown previously that computing an optimal strategy using the standard pebbling game on any given DAG is PSPACE-hard [GLT79]. Furthermore, it was more recently shown that the standard pebble game is hard to approximate to any constant additive factor [CLNV15]. In this thesis, we present a simpler proof of the result presented in [CLNV15] and strengthen the result to include any polynomial additive factor. In particular, we strengthen the result to show that it is PSPACE-hard to determine the minimum number of pebbles to any n1-[epsilon] additive factor for any [epsilon]. The red-blue pebble game was introduced by [JWK81] as a model of I/O complexity and is also played on DAGs. Despite its importance in applications such as data access complexity and more recently to I/O-complexity in multi-level memory hierarchies [CRSS16], little is known about the computational complexity of determining the minimum number of red pebbles and transitions used when pebbling a given DAG using the rules of the game. In this thesis, we show that the red-blue pebble game is PSPACE-hard and that the red-blue pebble game with no deletions and allowing overwrites is NP-Complete. We also show that the red-blue pebble game parameterized by the number of transitions, k is ...W[1]-hard. In addition to the stated hardness results, we also introduce a graph family that takes (nk) time to pebble given k constant number of pebbles. This graph family partially answers an open question posed in [Nor15] regarding whether such a family that meets the O(nk) time upper bound exists for constant k pebbles. Furthermore, the graph family can be generalized for any k < [square root of]n Given k pebbles where k = w(1), the pebbling time is ... for any graphs with n nodes in this family. Finally, we present a new complexity measure, called decremental complexity, based on the sequential and parallel pebbling models. This complexity measure is concerned with the decrease in pebbling time when switching from the sequential to the parallel model of pebbling any given graph with n nodes using the minimum number of pebbles. Graphs with low decremental complexity have potential applications in proofs of work/space and memory-hard functions. In this thesis, we determine the decremental complexity of several common families of graphs as well as composite graphs consisting of many copies of instances of these families.
by Quanquan Liu.
M. Eng.
46
ROSSETI, ISABEL CRISTINA MELLO. "SEQUENTIAL AND PARALLEL STRATEGIES OF GRASP WITH PATH-RELINKING FOR THE 2-PATH NETWORK DESIGN PROBLEM." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2003. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=4365@1.
Повний текст джерелаАнотація:
CONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICOSeja G= (V, E) um grafo não-orientado com custos não- negativos em suas arestas e D um conjunto de pares origem - destino. Um 2-caminho entre nós (s,t)é um caminho de s a t formado por , no máximo, 2 arestas. O problema de síntese de redes com 2-caminhos (2PNDP) consiste em encontrar um subconjunto de arestas com custo mínimo que contenha um 2- caminho entre as extremidades dea cada para origem- destino pertencente a D. Apicações deste problema encontram-se no projeto de redes de comunicação, onde caminhos com poucas arestas são desejáveis para garantir alta confiabilidade e pequenos atrasos. A metaheurística GRASP é um processo multipartida para resolver problemas combinatórios, cujas iterações consistem de duas fases, uma fase de construção e outra de busca local. O algoritmo retorna a melhor solução encontrada depois de um número determinado de iterações.Aplica-se a técnica de reconexão por caminhos ao final de cada iteração GRASP para melhorar a qualidade das soluções. Implementações paralelas de metaheurística são muito robustas. A maior parte das implementações paralelas da metaheurística GRASP segue uma estratégia do tipo independente , baseada na distribuição balanceada das iterações pelos processadores. No caso de estratégias colaboradtivas, os processadores trocam e compartilham informações coletadas ao longo da trajetória que cada um deles investiga. Neta tese são desenvolvidas heurísticas seqüenciais e paralelas para 2PNDP. São analisadas variantes e combinações de GRASP e reconexão por caminhos , comparando-se os resultados obtidos pelos algoritmos descritos na literatura. Heurísticas GRASP paralelas com reconexão por caminhos são avaliadas e comparadas para verificar qual o papel que a colaboração entre os processadores desempenha na qualidade das soluções e nos tempos de processamento. Procura-se também estudar a melhor maneira de desenvolver implementações paralelas , para se utilizar da melhor forma possível os recursos computacionais e reduzir conflitos de memória e comunicação.
Let G = ( V, E) be a connected undirected graph , where V is the set of nodes and E denotes the set of edges. A 2- path between nodes (s,t)is a sequence of a most two edges connecting them. Given a non-negative weight function associated with edges of G and a set D of origin- destination pairs of nodes, the 2-path network design problem (2PNDP) consists in finding a minimum weighted subset of edges containing a 2-path between the extremities of every origin-destination pair in D. Applications can be found in the design of communication networks , in which paths with few edges are sought to enforce high reliability and small delays. The GRASP metaheuristic is a multistart process , in which each iteration consists of two phases : construction and local search. The best solution found after a fixed number of iterations is returned. Path- relinking is applied as an attempt to improve the solutions found at the of each GRASP iteration. Parallel implementations of metaheuistics ara very robust. Typical parallelizations of GRASP correspond to multiple-walk independent-thread strategies, based on the balanced distribuiton of the iterations over the processors. In the case of multiple-walk cooperative-thread strategies, the processors exchange and share information collected along the trajectories that they investigate. In this thesis, sequential and parallel heuristics are developed for 2PNDP. Variants and combinations of GRASP with path-relinking are analysed by comparing the results of the proposed algorithms with those obtained by others algoritms described in the literature. Parallel GRASP with pathrelinking heuristcs are compared to investigate the influence of the cooperation among processors in terms of solution quality and processing time. We also explore different strategies to optimize the parallel implementations, to make better use of the computational resources and to reduce communication and memory conflicts.
47
Hedenström, Felix. "Trial Division : Improvements and Implementations." Thesis, KTH, Skolan för datavetenskap och kommunikation (CSC), 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-211090.
Повний текст джерелаАнотація:
Trial division is possibly the simplest algorithm for factoring numbers.The problem with Trial division is that it is slow and wastes computationaltime on unnecessary tests of division. How can this simple algorithms besped up while still being serial? How does this algorithm behave whenparallelized? Can a superior serial and a parallel version be combined intoan even more powerful algorithm?To answer these questions the basics of trial divisions where researchedand improvements where suggested. These improvements where later im-plemented and tested by measuring the time it took to factorize a givennumber.A version using a list of primes and multiple threads turned out to bethe fastest for numbers larger than 10 10 , but was beaten when factoringlower numbers by its serial counterpart. A problem was detected thatcaused the parallel versions to have long allocation times which slowedthem down, but this did not hinder them much.Trial division är en av de enklaste algoritmerna när det kommer till attfaktorisera tal. Problemet med trial division är att det är relativt långsamtoch att det gör onödiga beräkningar. Hur kan man göra denna algoritmsnabbare utan att inte göra den seriell? Hur beter sig algoritmen när denär parallelliserad? Kan en förbättrad seriell sedan bli parallelliserad?För att besvara dessa frågor studerades trial division och dess möjligaförbättringar. Dessa olika förbättringar implementerades i form av flerafunktioner som sedan och testades mot varandra.Den snabbaste versionen byggde på att använda en lista utav primtaloch trådar för att minimera antal ’trials’ samt att dela upp arbetet. Denvar dock inte alltid snabbast, då den seriella versionen som också användeen lista av primtal var snabbare för siffror under 10 10 . Sent upptäck-tes ett re-allokeringsproblem med de parallella implementationerna, meneftersom de ändå var snabbare fixades inte detta problemet.
48
Lee, Yin Nam. "Sequential and parallel solutions of the convoy movement problem using branch-and-bound and heuristic hybrid techniques." Thesis, University of East Anglia, 1995. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.296564.
Повний текст джерела
49
Van, Huyssteen Salomon Stephanus. "Parallel paradigms in optimal structural design." Thesis, Stellenbosch : Stellenbosch University, 2011. http://hdl.handle.net/10019.1/18017.
Повний текст джерелаАнотація:
Thesis (MScEng)--Stellenbosch University, 2011.ENGLISH ABSTRACT: Modern-day processors are not getting any faster. Due to the power consumption limit of frequency scaling, parallel processing is increasingly being used to decrease computation time. In this thesis, several parallel paradigms are used to improve the performance of commonly serial SAO programs. Four novelties are discussed: First, replacing double precision solvers with single precision solvers. This is attempted in order to take advantage of the anticipated factor 2 speed increase that single precision computations have over that of double precision computations. However, single precision routines present unpredictable performance characteristics and struggle to converge to required accuracies, which is unfavourable for optimization solvers. Second, QP and dual are statements pitted against one another in a parallel environment. This is done because it is not always easy to see which is best a priori. Therefore both are started in parallel and the competing threads are cancelled as soon as one returns a valid point. Parallel QP vs. dual statements prove to be very attractive, converging within the minimum number of outer iterations. The most appropriate solver is selected as the problem properties change during the iteration steps. Thread cancellation poses problems caused by threads having to wait to arrive at appropriate checkpoints, thus su ering from unnecessarily long wait times because of struggling competing routines. Third, multiple global searches are started in parallel on a shared memory system. Problems see a speed increase of nearly 4x for all problems. Dynamically scheduled threads alleviate the need for set thread amounts, as in message passing implementations. Lastly, the replacement of existing matrix-vector multiplication routines with optimized BLAS routines, especially BLAS routines targeted at GPGPU technologies (graphics processing units), proves to be superior when solving large matrix-vector products in an iterative environment. These problems scale well within the hardware capabilities and speedups of up to 36x are recorded.
AFRIKAANSE OPSOMMING: Hedendaagse verwerkers word nie vinniger nie as gevolg van kragverbruikingslimiet soos die verwerkerfrekwensie op-skaal. Parallelle prosesseering word dus meer dikwels gebruik om berekeningstyd te laat daal. Verskeie parallelle paradigmas word gebruik om die prestasie van algemeen sekwensiële optimeringsprogramme te verbeter. Vier ontwikkelinge word bespreek: Eerste, is die vervanging van dubbel presisie roetines met enkel presisie roetines. Dit poog om voordeel te trek uit die faktor 2 spoed verbetering wat enkele presisie berekeninge het oor dubbel presisie berekeninge. Enkele presisie roetines is onvoorspelbaar en sukkel in meeste gevalle om die korrekte akkuraatheid te vind. Tweedens word QP teen duale algoritmes in ’n parallel omgewing gebruik. Omdat dit nie altyd voor die tyd maklik is om te sien watter een die beste gaan presteer nie, word almal in parallel begin en die mededingers word dan gekanselleer sodra een terugkeer met ’n geldige KKT punt. Parallele QP teen duale algoritmes blyk om baie aantreklik te wees. Konvergensie gebeur in alle gevalle binne die minimum aantal iterasies. Die mees geskikte algoritme word op elke iterasie gebruik soos die probleem eienskappe verander gedurende die iterasie stappe. “Thread” kanseleering hou probleme in en word veroorsaak deur “threads” wat moet wag om die kontrolepunte te bereik, dus ly die beste roetines onnodig as gevolg van meededinger roetines was sukkel. Derdens, verskeie globale optimerings word in parallel op ’n “shared memory” stelsel begin. Probleme bekom ’n spoed verhoging van byna vier maal vir alle probleme. Dinamiese geskeduleerde “threads” verlig die behoefte aan voorafbepaalde “threads” soos gebruik word in die “message passing” implementerings. Laastens is die vervanging van die bestaande matriks-vektor vermenigvuldiging roetines met geoptimeerde BLAS roetines, veral BLAS roetines wat gerig is op GPGPU tegnologië. Die GPU roetines bewys om superieur te wees wanneer die oplossing van groot matrix-vektor produkte in ’n iteratiewe omgewing gebruik word. Hierdie probleme skaal ook goed binne die hardeware se vermoëns, vir die grootste probleme wat getoets word, word ’n versnelling van 36 maal bereik.
50
Lim, Choon Kee. "Hypercube machine implementation of low-level vision algorithms." Ohio : Ohio University, 1989. http://www.ohiolink.edu/etd/view.cgi?ohiou1182864143.
Повний текст джерела