Browsing by Author "Czapinski, Michal"

Now showing 1 - 2 of 2
  • Thumbnail Image
    ItemOpen Access
    Solvers on Advanced Parallel Architectures with Application to Partial Differential Equations and Discrete Optimisation
    (Cranfield University, 2014-05) Czapinski, Michal; Thompson, Chris
    This thesis investigates techniques for the solution of partial differential equations (PDE) on advanced parallel architectures comprising central processing units (CPU) and graphics processing units (GPU). Many physical phenomena studied by scientists and engineers are modelled with PDEs, and these are often computationally expensive to solve. This is one of the main drivers of large-scale computing development. There are many well-established PDE solvers, however they are often inherently sequential. In consequence, there is a need to redesign the existing algorithms, and to develop new methods optimised for advanced parallel architectures. This task is challenging due to the need to identify and exploit opportunities for parallelism, and to deal with communication overheads. Moreover, a wide range of parallel platforms are available — interoperability issues arise if these are employed to work together. This thesis offers several contributions. First, performance characteristics of hybrid CPU-GPU platforms are analysed in detail in three case studies. Secondly, an optimised GPU implementation of the Preconditioned Conjugate Gradients (PCG) solver is presented. Thirdly, a multi-GPU iterative solver was developed — the Distributed Block Direct Solver (DBDS). Finally, and perhaps the most significant contribution, is the innovative streaming processing for FFT-based Poisson solvers. Each of these contributions offers significant insight into the application of advanced parallel systems in scientific computing. The techniques introduced in the case studies allow us to hide most of the communication overhead on hybrid CPU-GPU platforms. The proposed PCG implementation achieves 50–68% of the theoretical GPU peak performance, and it is more than 50% faster than the state-of-the-art solution (CUSP library). DBDS follows the Block Relaxation scheme to find the solution of linear systems on hybrid CPU-GPU platforms. The convergence of DBDS has been analysed and a procedure to compute a high-quality upper bound is derived. Thanks to the novel streaming processing technique, our FFT-based Poisson solvers are the first to handle problems larger than the GPU memory, and to enable multi- GPU processing with a linear speed-up. This is a significant improvement over the existing methods, which are designed to run on a single GPU, and are limited by the device memory size. Our algorithm needs only 6.9 seconds to solve a 2D Poisson problem with 2.4 billion variables (9 GB) on two Tesla C2050 GPUs (3 GB memory).
  • Thumbnail Image
    ItemOpen Access
    Tabu Search with two approaches to parallel flowshop evaluation on CUDA platform
    (Elsevier Science B.V., Amsterdam, 2014-06-10) Czapinski, Michal; Barnes, Stuart
    The introduction of NVidia's powerful Tesla GPU hardware and Compute Unified Device Architecture (CUDA) platform enable many-core parallel programming. As aresult, existing algorithms implemented on aGPU can run many times faster than on modern CPUs. Relatively little research has been done so far on GPU implementations of discrete optimisation algorithms. In this paper, two approaches to parallel GPU evaluation of the Permutation Flowshop Scheduling Problem, with makespan and total flowtime criteria, are proposed. These methods can be employed in most population-based algorithms, e.g. genetic algorithms, Ant Colony Optimisation, Particle Swarm Optimisation, and Tabu Search. Extensive computational experiments, on Tabu Search for Flowshop with both criteria, followed by statistical analysis, confirm great computational capabilities of GPU hardware. AGPU implementation of Tabu Search runs up to 89 times faster than its CPU counterpart.