Hot answers tagged

38

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 ...


18

The simple example from electromagnetics (EM) would be performing a parallel frequency sweep for a frequency-domain simulation, say, full-wave extraction of network parameters (S, Y, Z, etc) for a device. Since the simulation for each frequency point is highly independent from another, the simulation can be embarrassingly parallelized across different cores, ...


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 ...


13

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 ...


13

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 ...


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

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 ...


11

High-quality video encoding is something like this. The search space is so huge that it requires branching to prune it rapidly, but GPUs are terrible at that. Modern CPU short-vector SIMD works well for this, working on contiguous chunks of 16 to 64 bytes of data. And while still being tightly coupled to the CPU core which can branch efficiently on SIMD ...


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. ...


9

GPUs work with the model SIMD (single instruction multiple data) i.e. they execute an instruction over multiple data. To give an idea: under CUDA technology when you have got an if-then-else condition the two branches are executed in sequence over the respective data. In your question, the condition to favor a CPU suggests a MISD or MIMD model, i.e. ...


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

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 (...


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 ...


8

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-...


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 ...


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 ...


6

When it comes to playing chess and other complex turn-based games using the MiniMax algorithm, then GPU acceleration is either not viable or only viable for a couple minor sub-problems. Chess engines need to evaluate a very large number of moves to find out which one results in a position which is best for the AI. How does the AI know that one position is ...


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 ...


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 ...


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