Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 22

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

help Ogranicz wyniki do:
first rewind previous Strona / 2 next fast forward last
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.
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.
EN
In this paper, load balancing mechanisms in a parallel algorithm of vascular network development are investigated. The main attention is focused on the perfusion process (connection of new cells to vascular trees) as it is the most time demanding part of the vascular algorithm. We propose several techniques that aim at balancing load among processors, decreasing their idle time and reducing the communication overhead. The core solution is based on the centralized dynamic load balancing approach. The model behaviors are analyzed and a tradeoff between the different mechanisms is found. The proposed mechanisms are implemented on a computing cluster with the use of the message passing interface (MPI) standard. The experimental results show that the introduced improvements provide a more efficient solution and consequently further accelerate the simulation process.
PL
W artykule rozważane są mechanizmy zrównoważające obciążenie w równoległym algorytmie rozwoju sieci naczyń krwionośnych. Główną uwagę zwrócono na proces perfuzji (podłączanie nowych komórek do drzew krwionośnych) jako, że proces ten jest najbardziej czasochłonnym fragmentem rozpatrywanego algorytmu. Zaproponowane przez autorów rozwiązania mają na celu zrównoważenie obciążenia pomiędzy procesorami, skrócenie ich czasu bezczynności oraz zredukowanie narzutu komunikacyjnego. Jądro rozwiązania jest oparte na scentralizowanym dynamicznym podejściu równoważenia obciążenia. Zachowania modelu zostały przeanalizowane i kompromis pomiędzy różnymi technikami został zaproponowany. Przedstawione mechanizmy zostały zaimplementowane na klastrze obliczeniowym przy wykorzystaniu standardu MPI. Otrzymane rezultaty jednoznacznie pokazuja˛ iż wprowadzone usprawnienia zapewniają bardziej efektywne rozwiązanie co w konsekwencji pozwala na jeszcze większe przyśpieszenie procesu symulacji.
7
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.
8
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).
EN
The advantages of the parallelism of genetically controlled slope stability evaluations are presented. The determination of the general solution, taking into account the minimization of R and T functions using multicriterial optimization method, is described. The calculations were performed on a cluster of computers using the Parallel Virtual Machine and the Parallel Genetic Algorithm. The efficiency and accuracy of calculations based on synchronous and parallel information processing were analyzed by comparisons to the best solution obtained for the example of slope, presented in the previous part of this paper.
PL
Przedstawiono zalety współbieżności genetycznie sterowanych obliczeń stateczności zboczy. Opisano metodę wyznaczania globalnego rozwiązania opartą na minimalizacji funkcjonałów R i T przy wykorzystaniu optymalizacji wielokryterialnej. Obliczenia przeprowadzono na zestawie komputerów wykorzystując Równoległą Maszynę Wirtualną oraz Równoległy Algorytm Genetyczny. Przeanalizowano efektywność i dokładność obliczeń opartych na współbieżnym i równoległym przetwarzaniu informacji porównując wyniki z najlepszym rozwiązaniem przykładowego zbocza, prezentowanego w poprzedniej części niniejszego artykułu.
PL
W pracy opisane są równoległe algorytmy poszukiwania z zabronieniami, dedykowane gniazdowemu problemowi z ograniczeniem bez czekania. Proponowane algorytmy zbudowane są z nadrzędnego algorytmu bazującego na wspomnianej technice oraz sterowanego algorytmu konstrukcyjnego. Poszukiwania ograniczone są tylko do rozwiązań możliwych do wygenerowania przez wspomniany algorytm konstrukcyjny. W pracy przedstawia się analizę porównawczą zaproponowanych algorytmów.
EN
This paper deals with parallel tabu search algorithms for a job shop problem with a no-wait constraint and a makespan criterion. The proposed algorithms consist of a master algorithm based on the mentioned technique and slave constructive algorithm. This approach reduces the number of solutions to check only to solutions that can be generated by means of the constructive algorithm. In this paper a comparative analysis of the proposed algorithms is presented.
EN
The paper is concerned with global optimization techniques and their parallel implementation. We describe an integrated software platform GOOL-PV (Global Optimization Object-oriented Library-Parallel Version) that provides the tools for solving complex optimization problems on parallel and multi-core computers or computer clusters. Finally, we present the comparative study of sequential and parallel global optimization algorithms based on numerical results for a standard set of multimodal functions.
PL
W artykule zaprezentowano koncepcję wielopopulacyjnego algorytmu ewolucyjnego realizującą mechanizm samoadaptacji, wykorzystujący technologię inteligentnych agentów. Technologia ta, wkraczająca w obszary inżynierii oprogramowania, obliczeń równoległych, systemów rozproszonych i sztucznej inteligencji, znajduje coraz szersze zastosowanie. Wykorzystanie jej w konstrukcji hybrydowych metod przybliżonych należy do aktualnego nurtu badań naukowych. Współbieżna realizacja wielu algorytmów ewolucyjnych pozwala na ich wzajemną komunikację, w celu udostępnienia informacji dotyczącej nie tylko uzyskanych rozwiązań, ale oceny aktualnie wykorzystywanych elementów konstrukcyjnych algorytmu, wartości parametrów oraz dodatkowych parametrów, charakteryzujących historię przebiegu i eksploracji przestrzeni rozwiązań. W oparciu o uzyskaną informację algorytmy (wątki) mogą w zróżnicowany sposób zmodyfikować swoje dotychczasowe działanie.
EN
The paper presents intelligent agent approach to multipopulation evolutionary algorithm with self-adaptation. The approach is based on different areas as software engineering, parallel and distributed systems and artificial intelligence. This technology belongs to up to date researches in the construction of hybrid approximate methods.
PL
W pracy rozpatrujemy problem przepływowy z kryterium minimalizacji sumy czasów zakończenia zadań (F\\Csum). Przedstawiamy algorytm równoległy oparty na metodzie scatter search. 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 scatter search method. Obtained results are compared to the best known from the literature.
16
Content available remote Parallel implementation of a quantum computing simulator
EN
In this paper the specialized software called quantum computation simulator is presented. Basic properties of quantum computation simulations are discussed. The algorithm of parallel implementation of a vector state transformation is presented also. Some examples of the presented software application are shown.
PL
Przedstawiono przykład programu komputerowego, służącego do analizy pól elektromagnetycznych wielkiej częstotliwości. Program zawiera algorytmy równoległe, umożliwiające uruchomienie go w środowisku wieloprocesorowym, zawierającym bibliotekę komunikacyjną MPI (Message Passing Interface). Do analizy pól elektromagnetycznych wykorzystano metodę FDTD (Finite Difference Time Domain) wyposażoną w algorytm dekompozycji przestrzeni. Zamieszczono wyniki badań wydajności programu równoległego.
EN
The present article shows the example of an application, implemented in a multiprocessor computational environment, enabling the analysis of the high frequency electromagnetic waves propagation. This. programme is based on parallel algorithms which enable its execution in the multiprocessor environment equipped with the Message Passing Interface communication library. In order to analyze the electromagnetic field distribution, the Finite Difference Time Domain Method equipped with space domain decomposition algorithm was used. In the final part of the paper, the results of the efficiency of the parallel algorithm were included.
18
Content available remote Parallel algorithm for system of differential equations integration
EN
The new approach to calculate dynamic behavior of large-scale systems, separated on subsystems is presented. Parallelization efficiency of computing process is described.
PL
W pracy rozpatrywany jest permutacyjny problem przepływowy z minimalizacją czasu wykonywania zadań. Przedstawiamy algorytmy (sekwencyjny i równoległy) oparte na metodzie symulowanego wyżarzania. W ich konstrukcji wykorzystano idee bloków z drogi krytycznej oraz dolne oszacowania wartości funkcji celu, a także różne schematy schładzania oraz funkcje akceptacji. Algorytmy testujemy na przykładach zaczerpniętych z pracy Taillarda [22].
EN
This paper deals with the classic permutation flow shop scheduling problem with the make-span criterion. We describe an approximation algorithms (sequential and parallel) based on simulated annealing method. We research various accepting functions and cooling schedules.We propose neighbourhood using so called blocks of jobs on a critical path and also using lower bound of cost function.
EN
Problem of scheduling a single machine to minimize total weighted late job can be described as follows: there are n jobs to be processed, each job has an integer processing time, a weight and a due date. The objective is to minimize the total weighted late job, where the late job is performed after its due date. The problem belongs to the class of NP-hard problems. In the paper, we propose sequential and parallel (for SIMD model computing) branch and bound algorithms based on elimination criteria. Finally, the computation results and discussion of the performance of algorithms are presented.
PL
W pracy zajmujemy się problemem optymalizacji kolejności wykonywania zadań na jednej maszynie, w którym kryterium optymalności jest suma kosztów zadań spóźnionych. Jest on oznaczany przez n|1||Sigma wiUi i należy do klasy problemów silnie NP-zupełnych. Przedstawiamy algorytm równoległy (dla modelu SIMD) oparty na metodzie podziału i oszacowań, w którym wykorzystano kryteria eliminacyjne.
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ć.