No presente trabalho, estudamos alguns conceitos relacionados ao desenvolvimento de programas paralelos, algumas formas de aplicar computação paralela em métodos de otimização contínua e dois métodos que envolvem o uso de otimização. O primeiro método que apresentamos, chamado PUMA (Pointwise Unconstrained Minimization Approach), recupera constantes óticas e espessuras de filmes finos a partir de valores de transmitância. O problema de recuperação é modelado como um problema inverso e resolvido com auxílio de um método de otimização. Através da paralelização do PUMA viabilizamos a recuperação empírica de constantes e espessuras de sistemas compostos por até dois filmes sobrepostos. Relatamos aqui os resultados obtidos e discutimos o desempenho da versão paralela e a qualidade dos resultados obtidos. O segundo método estudado tem o objetivo de obter configurações iniciais de moléculas para simulações de dinâmica molecular e é chamado PACKMOL. O problema de obter uma configuração inicial de moléculas é modelado como um problema de empacotamento e resolvido com o auxílio de um método de otimização. Construímos uma versão paralela do PACKMOL e mostramos os ganhos de desempenho obtidos com a paralelização. / In this work we studied some concepts of parallel programming, some ways of using parallel computing in continuous optimization methods and two optimization methods. The first method we present is called PUMA (Pointwise Unconstrained Minimization Approach), and it retrieves optical constants and thicknesses of thin films from transmitance data. The problem of retrieve thickness and optical constants is modeled as an inverse problem and solved with aid of an optimization method. Through the paralelization of PUMA we managed to retrieve optical constants and thicknesses of thin films in structures with one and two superposed films. We describe some results and discuss the performance of the parallel PUMA and the quality of the retrievals. The second studied method is used to build an initial configuration of molecules for molecular dynamics simulations and it is called PACKMOL. The problem of create an initial configuration of molecules is modeled as a packing problem and solved with aid of an optimization method. We developed a parallel version of PACKMOL and we show the obtained performance gains.

by Lui Hung Ngai. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2000. / Includes bibliographical references (leaves 56-[59]). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Thesis Overview --- p.3 / Chapter 2 --- Background & Related work --- p.4 / Chapter 2.1 --- Scheduling problem in ATM switch --- p.4 / Chapter 2.2 --- Traffic Scheduling in output-buffered switch --- p.5 / Chapter 2.3 --- Traffic Scheduling in Input buffered Switch --- p.16 / Chapter 3 --- Deadline-ordered Parallel Iterative Matching (DLPIM) --- p.22 / Chapter 3.1 --- Introduction --- p.22 / Chapter 3.2 --- Switch model --- p.23 / Chapter 3.3 --- Deadline-ordered Parallel Iterative Matching (DLPIM) --- p.24 / Chapter 3.3.1 --- Motivation --- p.24 / Chapter 3.3.2 --- Algorithm --- p.26 / Chapter 3.3.3 --- An example of DLPIM --- p.28 / Chapter 3.4 --- Simulation --- p.30 / Chapter 4 --- DLPIM with static scheduling algorithm --- p.41 / Chapter 4.1 --- Introduction --- p.41 / Chapter 4.2 --- Static scheduling algorithm --- p.42 / Chapter 4.3 --- DLPIM with static scheduling algorithm --- p.48 / Chapter 4.4 --- An example of DLPIM with static scheduling algorithm --- p.50 / Chapter 5 --- Conclusion --- p.54 / Bibliography --- p.56

Clustering techniques play an important role in exploratory pattern analysis, unsupervised pattern recognition and image segmentation applications. Clustering algorithms are computationally intensive in nature. This thesis proposes new parallel algorithms for Single Link and Complete Link hierarchical clustering. The parallel algorithms have been mapped on a SIMD machine model with a linear interconnection network. The model consists of a linear array of N (number of patterns to be clustered) processing elements (PEs), interfaced to a host machine and the interconnection network provides inter-PE and PE-to-host/host-to-PE communication. For single link clustering, each PE maintains a sorted list of its first logN nearest neighbors and the host maintains a heap of the root elements of all the PEs. The determination of the smallest entry in the distance matrix and update of the distance matrix is achieved in O(logN) time. In the case of complete link clustering, each PE maintains a heap data structure of the inter pattern distances. This significantly reduces the computation time for the determination of the smallest entry in the distance matrix during each iteration, from O(N2) to O(N), as the root element in each PE gives its nearest neighbor. The proposed algorithms are faster and simpler than previously known algorithms for hierarchical clustering. For clustering a data set with N patterns, using N PEs, the computation time for the single link clustering algorithm is shown to be O(NlogN) and the time complexity for the complete link clustering algorithm is shown to be O(N2). The parallel algorithms have been verified through simulations on the Intel iPSC/2 parallel machine.

Thesis (Ph. D.)--Ohio State University, 2006. / Title from first page of PDF file. Includes bibliographical references (p. 161-168).

The IEEE 802.3aq standard recommends a multi-tap decision feedback equalizer be implemented to remove inter-symbol interference and additive system noise from data transmitted over a 10 Gigabit per Second (10 Gbps) multi-mode fiber-optic link (MMF). The recommended implementation produces a design in an analog process. This design process is difficult, time consuming, and is expensive to modify if first pass silicon success is not achieved. Performing the majority of the design in a well-characterized digital process with stable, evolutionary tools reduces the technical risk. ASIC design rule checking is more predictable than custom tools flows and produces regular, repeatable results. Register Transfer Language (RTL) changes can also be relatively quickly implemented when compared to the custom flow. However, standard cell methodologies are expected to achieve clock rates of roughly one-tenth of the corresponding analog process. The architecture and design for a parallel linear equalizer and decision feedback equalizer are presented. The presented design demonstrates an RTL implementation of 10 GHz filters operating in parallel at 625 MHz. The performance of the filters is characterized by testing the design against a set of 324 reference channels. The results are compared against the IEEE standard group s recommended implementation. The linear equalizer design of 20 taps equalizes 88 % of the reference channels. The decision feedback equalizer design of 20 forward and 1 reverse tap equalizes 93 % of the reference channels. Analysis of the unequalized channels in performed, and areas for continuing research are presented.

This dissertation maps various kernels and applications to a spectrum of programming models and architectures and also presents architecture-aware algorithms for different systems. The kernels and applications discussed in this dissertation have widely varying computational characteristics. For example, we consider both dense numerical computations and sparse graph algorithms. This dissertation also covers emerging applications from image processing, complex network analysis, and computational biology. We map these problems to diverse multicore processors and manycore accelerators. We also use new programming models (such as Transactional Memory, MapReduce, and Intel TBB) to address the performance and productivity challenges in the problems. Our experiences highlight the importance of mapping applications to appropriate programming models and architectures. We also find several limitations of current system software and architectures and directions to improve those. The discussion focuses on system software and architectural support for nested irregular parallelism, Transactional Memory, and hybrid data transfer mechanisms. We believe that the complexity of parallel programming can be significantly reduced via collaborative efforts among researchers and practitioners from different domains. This dissertation participates in the efforts by providing benchmarks and suggestions to improve system software and architectures.

The investigation of new parallel algorithms for MIMD computers requires some postprocessing facilities for quickly evaluating the behavior of those algorithms We present two kinds of visualization tool implementations for 2D and 3D finite element applications to be used on a parallel computer and a host workstation.

Thesis (Ph. D.)--State University of New York at Binghamton, Thomas J. Watson School of Engineering and Applied Science, Department of Systems Science and Industrial Engineering, 2009. / Includes bibliographical references.

Not available / text

Daugelyje mokslo sričių susiduriama su uždaviniais, kuriuos išspręsti esamais kompiuteriais užtruktų nepriimtinai ilgai arba neįmanoma dėl tų uždavinių dydžio ir skaičiavimų apimties. Lygiagrečiaisiais skaičiavimais siekiame spręsti uždavinius greičiau, arba spręsti didesnius uždavinius. Tačiau tiek lygiagrečiųjų algoritmų sudarymas, tiek jų programinis realizavimas yra sudėtingi procesai, reikalaujantys daug žinių ir įgūdžių. Taupant laiką ir pastangas, yra kuriami lygiagretinimo įrankiai, lengvinantys įvairių lygiagrečiųjų programų ar metodikų naudojimą. Šeimininkas – darbininkai algoritmai yra dažnai naudojami ir paplitę įvairiose lygiagrečiųjų skaičiavimų srityse. Lygiagrečiųjų ���eimininkas – darbininkai algoritmų programų kūrimo automatizavimas palengvina daugelio uždavinių sprendimą. Šeimininkas – darbininkai algoritmas efektyvus vykdant tiek homogeniniuose, tiek heterogeniniuose lygiagrečiuosiuose kompiuteriuose. Duomenims tarp procesorių perduoti naudojamos duomenų perdavimo bibliotekos sparčiai vystomos. Nemažai anksčiau kurtų lygiagretinimo įrankių naudoja PVM duomenų perdavimo biblioteką. Išpopuliarėjus MPI duomenų perdavimo bibliotekai aktualu pritaikyti įrankius jos naudojimui. Daug praktinių uždavinių gali būti formuluojami kaip optimizavimo uždaviniai. Daugelis optimizavimo uždavinių sudėtingi ir reikalaujantys daug skaičiavimų. Šakų ir rėžių algoritmo principai taikomi kuriant tikslius ir euristinius algoritmus optimizavimo uždavinių sprendimui. Optimizavimo... [to full text] / Parallel computations are used in many areas where large computation amounts are required and/or faster response is critical. The development of parallel algorithms and parallel programming are complicated and require additional knowledge. To ease the parallel programming and algorithm parallelization many tools are developed. One class of such tools is algorithm templates. The idea of algorithm templates is to separate the problem specific and general parts of the algorithm. The general part can be implemented as a reusable module. The problem specific part of the algorithm should be implemented by the user. When these ideas are used for parallel programming, the template has to specify the main parts of the parallel algorithm: partitioning, communications, mapping, synchronization. Master – slave algorithms are very popular and widely used in parallel programming. It is efficient both for homogeneous and heterogeneous parallel computers. Parallelization tools of master – slave algorithms using popular communication libraries are useful. Many problems of engineering, economics and other fields are formulated as optimization problems. Optimization problems are often complicated and computation intensive. Therefore the creation of automatic parallelization tools of popular branch and bound optimization algorithms is relevant. Grillage type foundations are popular in case of weak grounds. It consists of beams that are supported by piles or reside on other beams. In order to... [to full text]