Tag Info

64

GPU hardware has two particular strengths: raw compute (FLOPs) and memory bandwidth. Most difficult computational problems fall into one of these two categories. For example, dense linear algebra (A * B = C or Solve[Ax = y] or Diagonalize[A], etc) falls somewhere on the compute/memory bandwidth spectrum depending on system size. Fast Fourier transforms (...

37

I'll try to summarize my experiences obtained in the course of developing ViennaCL, where we have CUDA and OpenCL backends with mostly 1:1 translations of a lot of compute kernels. From your question I'll also assume that we are mostly taking about GPUs here. Performance Portability. First of all, there is no such thing as performance-portable kernels in ...

22

Problems which have a high arithmetic intensity and regular memory access patterns are typically easy(ier) to implement on GPUs, and perform well on them. The basic difficulty in having high performance GPU code is that you have a ton of cores, and you want them to all be utilized to their full potency as much as possible. Problems which have irregular ...

17

Double precision is fairly common on newer GPUs. For instance I own a NVIDIA GTX560 Ti (fairly low end when it comes to computing) that has no issue running ViennaCL in double precision. From here (section 4) it appears all NVIDIA cards from GTX4xx onward support double precision natively. I would guess that the GROMACS information is simply outdated.

17

The first thing is to recognize that you can do this using BLAS. If you data matrix is $X = [x_1 x_2 x_3 ...] \in \mathbb{R}^{m\times n}$ (each $x$ is a column vector corresponding to one measurement; rows are trials), then you can write the covariance as:  C_{ij} = E[x_i,x_j] - E[x_i] E[x_j] = \frac{1}{n} \sum_k x_{ik} x_{jk} - \frac{1}{n^2} \left(\sum_k ...

15

This is not intended as an answer on its own but rather an addition to the other answers by maxhutch and Reid.Atcheson. To get the best out of GPUs your problem does not only need to be highly (or massively) parallel, but also the core algorithm that will be executed on the GPU, should be as small as possible. In OpenCL terms this is mostly referred as the ...

12

There are some differences, however they aren't necessarily in hardware or specs. Note that this is all information I have gained from forums or news releases, so take it all with a grain of salt. The first is the "scalability and reliability" (source). The K20 was designed to sit in a cluster system and run at full tilt 24/7. The Titan is more designed ...

12

tl;dr: My general impression from the literature is that speedups are modest (if they exist). The main kernel you'll see in these methods is a sparse-direct method (e.g., sparse LU, sparse LDLT), and memory accesses are irregular; these characteristics don't favor use of GPUs. Also, parallel IPMs are in their infancy. I still suspect people will work on GPU ...

11

Probably a more technical addition to the previous replies: CUDA (i.e. Nvidia) GPUs can be described as a set of processors that work autonomously on 32 threads each. The threads in each processor work in lock-step (think SIMD with vectors of length 32). Although the most tempting way to work with GPUs is to pretend that absolutely everything runs in lock-...

11

Ultimately, naive brute-force KNN is an $O(n^2)$ algorithm, while kd-tree is $O(n \log n)$, so at least in theory, kd-tree will eventually win out for a large enough $n$. In practice, the leading constants for a GPU implementation may be vastly different --- we may be comparing $0.0001n^2$ vs $1000n\log n$ --- so it may indeed be the case that the former ...

10

DifferentialEquations.jl library is a library for a high level language (Julia) which has tools for automatically transforming the ODE system to an optimized version for parallel solution on GPUs. There are two forms of parallelism that can be employed: array-based parallelism for large ODE systems and parameter parallelism for parameter studies on ...

9

I can't answer the second half of your question as far as other implementations out there but I can provide some insight as to the challenges. For reference, I personally used ViennaCL on a nVidia GTX 560 Ti with 2GB of memory for my benchmarks. Over serial code on a mid-range i5, I saw speed-ups for dense matrix multiplications of approximately 40x. For ...

9

What am I missing here? Most of the broader issues with your proposal are covered in What are the current obstacles to reaching exascale computing?. I think the cost and power analysis you've done is a lower bound at best: you've calculated the cost it would take to buy 100,000 GPUs, and you can't run anything on a GPU that isn't plugged into anything. ...

8

If this actually works, and it seems to, that'd be awesome because we can get a lot of undocumented data about the cache of a GPU. A frustrating aspect of high performance computing research is digging through all the undocumented instruction sets and architecture features when trying to tune code. In HPC, the proof is in the benchmark, whether it is High ...

8

For [CU]BLAS, there is a wrapper called 'thunking' in the CUDA toolkit (src/fortran_thunking.{c,h}) that takes pointers from CPU memory and does all the GPU allocation/copying for you. You can plug it into your code with a preprocessor statements like #define ZGEMV CUBLAS_ZGEMV #define ZGEMM CUBLAS_ZGEMM ... For LAPACK, Magma has CPU-side interfaces for ...

7

In broad terms, algorithms that run faster on the GPU are ones where you are doing the same type of instruction on many different data points. An easy example to illustrate this is with matrix multiplication. Suppose we are doing the matrix computation $A \times B = C$ A simple CPU algorithm might look something like //starting with C = 0 for (...

7

In addition to Geoff's great points: Single versus double precision The Radeon's quoted performance is single precision, but HPC benchmarks generally measure double precision (including the Tianhe-2 number). The Radeon has poor double precision performance, but if you buy a card focusing on double precision, expect to take at least a factor of 3 hit on ...

7

Several points I want to mention (with an encouragement to other CompSci users that are more familiar with Java specifics to give additional, more Java related answers): The solution of a system of linear equations and inversion of the matrix are two very different things. You almost never should explicitly invert the matrix. One should use one form of the ...

7

One issue that you should be aware of is that NVIDIA has a market segmentation strategy in which it sells relatively inexpensive GPU's to the gaming and graphics workstation markets (GeForce and Quadro) and different higher-priced models (Tesla) to the high-performance computing market. The GPU's sold for use in gaming and graphics have limited double-...

6

GPUs are sensitive beasts. Although Nvidia's beefiest card can theoretically execute any of the operations you listed 100x faster than the fastest CPU, about a million things can get in the way of that speedup. Every part of the relevant algorithm, and of the program which runs it, has to be extensively tweaked and optimized in order to get anywhere near ...

6

If you work at an institution in the US or have collaborators at one, you should look into the XSEDE program. This is a federation of the National Science Foundation funded supercomputing centers in the US which provides compute cycles on a variety of large-scale machines to open science research in the US. There are a couple of machines with GPU resources ...

6

You may want to look into Boost's odeint library and Thrust. They can be combined as discussed here.

6

A 100,0000 by 100,000 symmetric dense matrix in single precision requires 20 gigabytes of memory (storing only the upper triangle) or 40 gigabytes of memory for double precision. Thus it is too large to fit within the memory of available GPU's. In order to solve this problem using GPU acceleration you'd have to develop an algorithm that sends smaller ...

6

There are plenty of finite element libraries out there that satisfy most of your criteria. In no particular order, I would mention deal.II (my own project), libMesh, and FEniCS. All three are large, are libraries, are well documented, are well established with large user bases. All three are actively maintained and are about as fast as you would a general ...

6

CUDA is a non-trivial advantage for NVIDIA. Most of the benchmarks I have seen (ViennaCL Benchmarks for reference) show that CUDA does better than OpenCL by up to an order of magnitude. At the large problem sizes, the two are fairly comparable. Also, NVIDIA has the advantage that no matter whether you end up using OpenCL or CUDA, you can very quickly ...

6

In general, the AMD line of GPUs are faster for integer based calculations, whereas NVIDIA are faster for floating point. NVIDIA also has CUDA (like Godric mentioned) which is a bit easier to work with, and has a very good library support, including cuBLAS, cuFFT and Thrust which make many things far easier to code. CUDA is not itself faster than OpenCL, ...

6

This may have gone unnoticed in the comments under the original question, but computing $10^9!$ yields a number with 8.5 billion digits, that is it is on the order of $10^{9\cdot 10^9}$. Given that $10^{9\cdot 10^9}=1000^{3\cdot 10^9} \approx 1024^{3\cdot 10^9}=(2^{10})^{3\cdot 10^9}=2^{3\cdot 10^{10}}$, you need approximately $3\cdot 10^{10}$ bits, or ...

5

I have used Thrust in my linked cluster expansion project. Depending on the situation, Thrust can perform as well as or better than a low level implementation that you roll yourself (in particular, the reduce kernel has been working quite well for me). However Thrust's generic nature and flexibility means it sometimes has to do a lot of extra copying, array ...

5

Let me focus only on CUDA and BLAS. Speedup over an host BLAS implementation is not a good metric to assess throughput, since it depends on too many factors, although I agree that speedup is usually what one cares about. If you look at the benchmarks published by NVIDIA and take into account that the Tesla M2090 has 1331 Gigaflops (single precision) and ...

Only top voted, non community-wiki answers of a minimum length are eligible