Ograniczanie wyników
Czasopisma help
Autorzy help
Lata help
Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 32

Liczba wyników na stronie
first rewind previous Strona / 2 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  parallel algorithm
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 2 next fast forward last
EN
The paper discusses a two-machine flow shop problem with minimization of the sum of tardiness costs, being a a generalization of the popular NP-hard single-machine problem with this criterion. We propose the introduction of new elimination block properties allowing for accelerating the operation of approximate algorithms of local searches, solving this problem and improving the quality of solutions determined by them.
EN
We parallelized the sequential algorithm of the four-body correlation function if eachcombination of two pairs(i, j)and(k, l) was averaged over the time in a separate calculation thread. The generator of pairs used as the input for this algorithm was also parallelized and connected with the 4-body correlation function calculations. We used our algorithm to accelerate extremely intensive calculations of the 4-body polarizability anisotropy correlation functions,which were very important to estimate the interaction induced light scattering spectrum. The resulting C code was used to test our algorithm on Graphics Processing Units (GPUs) with the Compute Unified Device Architecture (CUDA) technology from NVIDIA®Corporation. Asa result, we achieved 12 times the acceleration of the 4-body correlation function calculations in comparison to the Central Processing Unit (CPU) core. The peak performance of the GPU calculations was registered at the level of 19 times faster than the CPU core. We also found thatacceleration depended on the memory consumption. In the single precision mode, the relative error between the CPU and GPU calculations was found to be within 0.1%
EN
An effective sequential algorithm and two parallel algorithms for generating combinations without repetitions of m out n of objects, represented by Boolean vectors, are proposed. One of them allows one to calculate starting and ending combinations for the subset, generated by each computing processor. The second algorithm firstly generates short (m-component) vectors on several computing processors. After that, by using special [n/m]-component vectors, it connects the short vectors into n-component Boolean vectors, each of which containing of exactly m units.
EN
The subject of this work is the new idea of blocks for the cyclic flow shop problem with setup times, using multiple patterns with different sizes determined for each machine constituting optimal schedule of cities for the traveling salesman problem (TSP). We propose to take advantage of the Intel Xeon Phi parallel computing environment during so-called ’blocks’ determination basing on patterns, in effect significantly improving the quality of obtained results.
EN
In this paper there is considered a flexible job shop problem of operations scheduling. The new, very fast method of determination of cycle time is presented. In the design of heuristic algorithm there was the neighborhood inspired by the game of golf applied. Lower bound of the criterion function was used in the search of the neighborhood.
EN
The paper presents two options of the parallel algorithm for finding the shortest covering of a large Boolean matrix, where the decomposition of the initial matrix into matrices of smaller sizes is based on the partitioning of rows. The parallel algorithm COVMB contains sequential algorithms for partitioning of initial m × n Boolean matrix on submatrices, building special matrices, summering of the shortest coverings of special Boolean matrices with smaller sizes as well as the sequential algorithm SECNOP for finding the shortest coverings of smaller Boolean matrices.
PL
Artykuł przedstawia projekt oraz implementację równoległego algorytmu RANSAC w architekturze CUDA w zadaniu rejestracji chmur punktów na potrzeby manipulacji obiektami codziennego użytku. Na początku pracy krótko omówiono szeregową wersję algorytmu oraz wspomniano o kilku jego modyfikacjach znanych z literatury, po czym przeprowadzono rozumowanie projektowe a następnie implementacyjne wersji równoległej. Testy porównawcze udowodniły poprawność działania algorytmu przy jednoczesnym kilkudziesięciokrotnym zysku czasowym. Wynikiem pracy jest realizacja znalezienia lokalnego układu współrzędnych obserwowanego obiektu na scenie w czasie bliskim czasowi rzeczywistemu. Kod źródłowy programu udostępniono w Internecie jako część projektu Heuros.
EN
In this paper a project and implementation of the parallel RANSAC algorithm in CUDA architecture are presented. The goal is to register point clouds for munipulation of everyday object as fast as possible. In the beginning a serial algorithm with a variety of modifications from the literature is introduced whereupon the idea and CUDA implementation details are discussed. The comparative test has proven the proper working of the implementation together with a significant program execution acceleration. The result is finding local coordinate system of the object in the scene in the near real-time conditions. The source code is shared in the Internet as a part of the Heuros system.
PL
W artykule przedstawiono równoległy algorytm estymacji parametrów składowych sinusoidalnych złożonego sygnału. Proponowany algorytm umożliwia rozpoznanie składowych sygnału również w warunkach, gdy dysponujemy ograniczoną liczbą losowo pobranych próbek tego sygnału. Zbadany został czas pracy zaproponowanego algorytmu w funkcji liczby równocześnie uruchomionych wątków. Do testowania zostały zastosowane komputery o różnej liczbie rdzeni procesora, obsługiwanych wątków oraz zmiennoprzecinkowych jednostek wykonawczych. Wyniki eksperymentu pokazują, że proponowany algorytm może pracować efektywnie, nawet jeśli liczba wątków obliczeniowych przekracza liczbę jednostek wykonawczych procesora, na którym pracuje. W artykule zostały również zarysowane kierunki dalszych badań nad udoskonaleniem przedstawionego algorytmu.
EN
The paper presents a parallel algorithm for parameter estimation of sinusoidal components of a complex signal. The proposed algorithm can identify the signal components when the number of available samples of the signal is limited. The proposed algorithm was tested on test computers equipped with different number of processor cores and floating point units. The experimental results show that the proposed algorithm can work efficiently even if the number of threads exceeds the number of processor cores. Directions for further research are outlined.
PL
Artykuł prezentuje zastosowanie równoległych algorytmów ewolucyjnych w optymalizacji konstrukcji. Zaproponowano i przetestowano wielowątkowe algorytmy ewolucyjne w dwóch wariantach, synchronicznym i asynchronicznym oparte na klasycznym algorytmie ewolucyjnym (AE). W obydwu wariantach testowano działanie algorytmów z wykorzystaniem pojedynczego wieloprocesorowego komputera oraz z wykorzystaniem wielokomputerowego klastra obliczeniowego. Eksperymenty obliczeniowe wykonano dla różnych zadań jedno i wielokryterialnej optymalizacji konstrukcji, w tym modelowanych metodą elementów skończonych (MES). Przeprowadzono obliczenia między innymi dla układu dwóch sprężyn obciążonych zmienną siłą, belki wielostopniowej, płyty o złożonym układzie obciążeń. Wygenerowane wyniki wskazują, iż zastosowanie przetwarzania równoległego umożliwia zwiększenie efektywności obliczeń ze względu na dokładność i czas obliczeń oraz uniezależnia wyniki optymalizacji od niewłaściwie dobranych parametrów algorytmu ewolucyjnego.
EN
This paper presents the application of parallel evolutionary algorithms for design optimization. There are two versions synchronous and asynchronous multithreads evolutionary algorithms proposed and tested. In both variants all experiments were done using a single multiprocessor computer and a computing cluster. Computational experiments were carried out for various single and multi-criteria design optimization problems, including modeled by finite element method (FEM). As examples there were considered and presented three problems, the set of two springs, the 6-th step beam and the plate with holes. Generated results indicate that the use of parallel processing can increase the efficiency of computation due to the accuracy and the computation time.
EN
Parallel algorithm for solving systems of ordinary differential equations (ODEs) for Nvidia CUDA technology has been developed. This algorithm is based on concept of dividing systems of equations into individual equations or groups of equations which then are solved by separate threads. This article demonstrates initial results and analysis of working time of the algorithm in few examples of its application.
EN
The paper presents two parallel algorithms for finding the rank of a rectangular matrix and two parallel algorithms for generation of combinations without repetitions represented by Boolean vectors, that are used in an algorithm for finding the rank of a rectangular matrix .
EN
The influence of the co-operation frequency of threads in a parallel heuristic algorithm to solve the vehicle routing problem with time windows on the accuracy of solutions is investigated. The accuracy of solutions is defined as their proximity to the best known solutions of Gehring and Homberger's benchmarking tests. Two adaptive co-operation schemes are proposed and experimentally evaluated.
PL
Wyznaczanie tras dla pojazdów z oknami czasowymi (ang. vehicle routing problem with time windows) jest problemem optymalizacji dyskretnej należącym do klasy problemów NP-trudnych. Istnieją metody heurystyczne rozwiązywania problemu, pozwalające wyznaczyć w rozsądnym czasie rozwiązania nieoptymalne o koszcie bliskim kosztowi rozwiązania optymalnego, takie jak symulowane wyżarzanie, przeszukiwanie tabu, algorytmy genetyczne czy algorytmy memetyczne. Wprzypadku algorytmów dwustopniowych, w pierwszej fazie minimalizowana jest liczba tras, a w fazie drugiej całkowita przebyta odległość. Flota składa się z pojazdów o jednakowej, zdefiniowanej pojemności, która nie może zostać przekroczona, a obsługa klientów musi rozpocząć się w czasie trwania ich okien czasowych.
EN
The methods of the tolerance ellipsoidal estimation for the tasks of synthesis of the tolerances to parameters of radio-electronic circuits and possibility of its parallelization are considered. These methods are the result of the task of estimation the solutions of an interval system of linear algebraic equations (ISLAE) which is built according to given criteria of optimality. The numerical algorithm is proposed for solving the tolerance ellipsoidal estimation tasks with a possibility of parallelization.
EN
In the paper we propose a new framework for the distributed tabu search algorithm designed to be executed with the use of a multi-GPU cluster, in which cluster of nodes are equipped with multicore GPU computing units. The proposed methodology is designed specially to solve difficult discrete optimization problems, such as a flexible job shop scheduling problem, which we introduce as a case study used to analyze the efficiency of the designed synchronous algorithm.
EN
The paper presents two algorithms of parallelization of computations for lossless data compression. It is proposed as a parallel algorithm for Huffman coding and a parallel algorithm for coding of a set of numbers by the family of arithmetic progressions.
PL
W pracy jest rozpatrywany silnie NP-trudny hybrydowy problem szeregowania zadań z równoległymi maszynami, zwany w literaturze elastycznym problemem gniazdowym. Głównym celem pracy jest wskazanie metody przeglądania otoczeń, dla złożonych problemów optymalizacji dyskretnej, z wykorzystaniem środowiska obliczeń równoległych. Aby proces ten przyśpieszyć, zastosowano szacowanie wartości funkcji celu (zamiast liczenia wartości dokładnej). Pozwoliło to znacznie przyśpieszyć obliczenia przy niewielkim pogorszeniu się wartości wyznaczanych rozwiązań.
EN
The aim of this paper is to show how to determine the neigh-borhood of the complex diserete optimization problem and how to search it in the parallel environment, this being illustrated by an example of the hybrid scheduling, more precisely a flexible job shop problem. We present a parallel single-walk approach in this respect. A theoretical analysis based on PRAM model of parallel computing has been made. We propose a cost-optimal method of neighborhood generation parallelization.
17
Content available remote Sekwencyjne i równolegle algorytmy znajdowania podciągów
PL
Pierwsza cześć niniejszej pracy poświęcona jest problemowi najdłuższego podciągu rosnącego (LIS) oraz jego wariantom (podciąg otrzymuje sie z ciągu przez usuniecie zera bądź większej liczby symboli). Problem ten znajduje zastosowania m.in. w bioinformatyce do uliniawiania genomów, wyszukiwania nowych genów. Pierwszym z wariantów problemu LIS rozważanym w niniejszej pracy jest problem podciągów rosnących, które są pod pewnymi względami ekstremalne. Kolejnym wariantem jest problem podciągu rosnącego o zadanym pochyleniu. Dalsze dwa warianty to problemy cyklicznych podciągów rosnących oraz podciągów rosnących w oknie ustalonego rozmiaru ciągu wejściowego. Dla tych ostatnich wariantów zaproponowano w pracy wykorzystanie reprezentacji ciągu za pomocą pokrycia zachłannego oraz opracowano wydajne algorytmy łączenia takich pokryć. Algorytmy te są kluczowe do efektywnego rozwiązywania wspomnianych problemów. Druga cześć pracy dotyczy problemu najdłuższego wspólnego podciągu i jego wariantów. Zastosowania tych problemów są bardzo liczne i dotyczą przede wszystkim porównywania ciągów w celu oceny ich podobieństwa. Dla problemu LCS niezmienniczego względem transpozycji LCTS) zaproponowano kilka algorytmów sekwencyjnych, które, jak wynika z eksperymentów praktycznych, okazały sie znacznie szybsze od algorytmów istniejących. Dla problemu ukierunkowanego LCS (CLCS) zaproponowano algorytmy sekwencyjne, również szybsze od dotychczas istniejących. Ponadto, zaproponowano dla tego problemu pierwszy algorytm równoległości bitowej. Dla problemu scalonego LCS (MerLCS) zaproponowano pierwszy algorytm równoległości bitowej, który w eksperymentach praktycznych okazał sie kilkudziesięciokrotnie szybszy od znanych algorytmów. Dla problemów LCS, LCTS, CLCS zaproponowano także algorytmy równoległe przeznaczone do wykonywania w procesorach graficznych. Dla wszystkich algorytmów proponowanych w niniejszej pracy przeprowadzono analizę złożoności czasowej i pamięciowej w przypadku pesymistycznym(dla niektórych także w przypadku średnim). Dzięki temu często można było wykazać, ze proponowane algorytmy są także najszybsze w sensie asymptotycznym.
EN
The first part of this work is on the longest increasing subsequence problem (LIS) and its variants (a subsequence can be obtained from a sequence by removing zero or more symbols). The problem has applications in bioinformatics, e.g., in sequence alignment, searching new genes. The first variant of the LIS problem, which is considered in this work, is a problem of longest increasing subsequences that are extremal from some point of view. Next variant is a slope-constrained longest increasing subsequence problem. The last two discussed variants of the LIS problem are a longest increasing cyclic subsequence problem (LICS) and a longest increasing subsequence in a sliding window problem (LISW). The algorithms for the recent two problems use cover representation of a sequence. Original algorithms for cover merging are crucial to the proposed algorithms for the LICS and LISW problems. The second part of this work is on the longest common subsequence problem (LCS) and its variants. The applications of these problems are numerous and concentrate mainly on the sequence comparison. For the transposition-invariant LCS problem (LCTS), a few sequential algorithms were proposed. Experiments show that they are much faster than the existing algorithms. For the constrained LCS problem (CLCS), a few sequential algorithms were also proposed. They are faster than the known algorithms. Moreover, for the CLCS problem, the first bit-parallel algorithm was invented. For the merged LCS problem (MerLCS), a bit parallel algorithm, tens times faster than the existing algorithms was proposed. For the LCS, LCTS, CLCS problems also algorithms for graphical processors were invented. All the proposed algorithms were analysed and their time and space complexities in the worst case were determined. For some algorithms the average case was also analysed. Obtained time complexities allow to show that the proposed algorithms are usually faster than the existing algorithms also in an asymptotic sense.
18
Content available remote Implementation and speed up of a parallel algorithm for the cauchy problem
EN
The speed up of a parallel algorithm with respect to sequential one for the case of the Cauchy problem. Four various known numerical methods are applied for solving of the problem. For each method a speed up function is determined. Then a really speed up is given for various number of used processors and points processed by a single processor. The algorithm was implemented on the platform MS .NET in MS Visual C# using a distributed calculation. The obtained results of the really speed up are comparable with theoretical speed up function. The numerical results indicate that efficiency of the parallel computations increases with the number of arithmetical operations needed for one step of used numerical methods.
PL
W pracy rozpatrujemy problem przepływowy z kryterium minimalizacji sumy czasów zakończenia zadań (F\\Csum). Przedstawiamy hybrydowy algorytm równoległy oparty na metodzie symulowanego wyżarzania z elementami algorytmu genetycznego. Otrzymane wyniki porównujemy z najlepszymi znanymi w literaturze.
EN
In the paper we consider flow shop problem with the criterion of minimalization of the sum of job's finishing times (F\\Csum). We present the parallel algorithm based on the simulated annealing method. Obtained results are compared to the best known from the literature.
PL
W pracy rozpatrywany jest ogólny problem kolejnościowy z równoległymi maszynami (flexible job shop problem), w którym dany jest zbiór zadań oraz zbiór maszyn. Maszyny tego samego typu (rodzaju), tj. o tych samych własnościach funkcjonalnych (które jednak mogą mieć różne parametry techniczne, takie jak na przykład wydajność) tworzą gniazdo. Do rozwiązania problemu proponujemy podejście dwupoziomowe - meta2heurystykę. Algorytm równoległy testowany jest na 128-procesorowej karcie GPU.
EN
We consider a double-level metaheuristic optimization algorithm in this paper. The algorithm proposed here includes two major modules: the machine selection module, which is executed sequentially, and the operation scheduling module executed in parallel. On each level a metaheuristic algorithm is used, so we call this method meta2heuristics. We carry out computational experiment using 128-processors Graphics Processing Unit (GPU).
first rewind previous Strona / 2 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.