31
There is one real and one practical reason.
First, MPI was developed at a time when machines had exactly one processor core and when we wanted to couple different machines. It is today used on clusters of tens of thousands of machines, each of which happens to have many cores but the point is that it's still separate machines. Now, a processor core on ...
14
The conjugate gradient method is the provably fastest iterative solver, but only for symmetric, positive-definite systems. What would be awfully convenient is if there was an iterative method with similar properties for indefinite or non-symmetric matrices.
The CG method seeks approximate solutions at each step $k$ within the Krylov subspace
$K_k(A,b) = \{...
12
Good is a relative term, and it will depend on the nature of the problem, the nature of the algorithm, and properties of the hardware involved. The only absolute reference point is ideal scaling (100% efficiency).
You can claim your scaling is good if it is better than what anyone else has achieved for the same problem, or if it's "close" to ideal for ...
10
The Thomas algorithm is very efficient because its operation count is very low and because data accesses are very likely to be cache hits once data is initially read from memory.
There are two loops.
The first loop traverses the data forward. Each element of the lower, main and upper triangle, along with the right-hand-side vector (which is typically ...
10
A long standing favorite benchmark in high performance computing has been the HPLinpack benchmark, which measures the speed of a computer system in floating point operations per second while solving a very large, dense, linear system of equations. It is assumed that the solution takes $2/3n^{3}+2n^{2}$ floating point operations and the tester is allowed to ...
10
If the operation is as trivial as you say, and each node has all the information necessary to carry out the operation, then the communication will be substantially more expensive than recomputing locally on each node. That said, it's a good exercise to write both implementations and compare; experiment is better than the advice of strangers on the internet.
...
9
I'm a happy user of GoogleTest with a C++ MPI code in a CMake/CTest build environment:
CMake automatically installs/links googletest from svn!
adding tests is a one-liner!
writing the tests is easy! (and google mock is very powerful!)
CTest can pass command-line parameters to your tests, and exports data to CDash!
This is how it works. A batch of unit-...
9
Wolfgang Bangerth's answer is totally correct, and I only want to add one practical aspect.
Portability across hardware
Let's say you write a research code from scratch. You have a powerful multi-core shared memory machine at your department which can do the job. If you start out with a thread-based implementation, you can reach good performance on this ...
8
I think some of your issues are more important than others and some of
your emphasis is misplaced. In pursuing overhead, you are in danger of
making your program unmaintainable. It is easier to write a common
program and direct surplus effort somewhere more interesting. I apologize for pontificating like this.
If statements. From a strict programming ...
6
The conjugate gradient method only works to solve the system
$ A x = b $
if $A$ is symmetric and positive-definite (also works for negative definite). The reason it must be symmetric is that conjugate gradient works by minimizing (or maximizing) the function
$ f(x) = \frac{1}{2} x^T A x - b^T x $
Note that the derivative is
$ f'(x) = \frac{1}{2} A^T x ...
6
Bill answered the first part, so I'll only answer the second question. An MPI send is blocking if it does not return until it is safe to modify the send buffer and a receive is blocking if it does not return until the receive buffer contains the newly-received message. In practice, outside of buffered sends (thanks, Hristo Iliev), this implies that ...
6
Always use the correct types as specified by the standard. MPI_Comm for your communicators not int unless you're in Fortran. Etc., etc.
This should be relatively easy. What problems are you really having?
Edited to add in response to update: It looks like the type of childGroup is not an MPI_Group but an MPI_Comm, so you should either fix that or use a ...
6
Bill Barth already gave great advice. My advice is to not read the MPICH or OpenMPI documents. Read the MPI standard instead. As far as standards are concerned, it's actually quite readable. Implementations are, in my experience, quite conforming to the standard, but they add and extend them. These extensions are part of the problem that makes code ...
6
The honest answer is that we don't know. The answer depends heavily on what is actually being run and what code the user has written. As Brian Borchers points out, there's a big difference between two benchmarks where we have all the code and supposedly know what that code is doing, but there's much disagreement about how representative this code is of what ...
6
No. You need to test it to that scale, especially if you have MPI calls within OpenMP regions.
6
The first thing you need to ask yourself: is your problem big enough that the overhead of MPI messaging is less than the work that you save. Your problem size is 10k which is small, but on the other hand you seem to have a dense matrix, so there is a good amount of work.
Next: parallelizing a numerical method may change the mathematics. It looks like you're ...
5
MPI_Probe allows you to test for a message without actually receiving it. You must complete all non-blocking communications with an appropriate communications completion fuction like MPI_Wait and friends, otherwise the runtime will not free up internal resources associated with the communications leading to resource leaks and other problems. For example, you ...
5
My list in no particular order of preference. The interface should:
be header only, without any dependencies but <mpi.h>, and the standard library,
be generic and extensible,
be non-blocking only (if you want to block, then block explicitly, not by default),
allow continuation-based chaining of non-blocking operations,
support extensible and efficient ...
5
An MPI_Barrier can be used to synchronize all processes in a communicator. Each of the processes has to wait till all other processes reach the barrier before all of them can proceed further:
MPI_BARRIER(COMM, IERROR)
Here COMM is the communicator handle and IERROR the error status.
Note that sometimes there are more clever ways to deal with such ...
5
You say that you want an MPI version. Then you need to study the literature, as the distributed memory variant of matrix-matrix product are not a simple parallellization of the sequential version.
The Cannon algorithm is pretty cute if you're on a square processor grid. In each step you rotate the input matrix rows and columns, so that in the end each ...
5
An addition to @Daniel Shapero's answer.
It might also be important to know if there are computations that can lead to different results depending on which machine they are launched (or just vary from launch to launch) – and how sensitive is your code to those fluctuations.
These will be even more pronounced if the cluster you are working on is ...
5
It depends on the communication settings you use for MPI. In blocking communication, MPI has three wait modes.
Aggressive busy wait. This is a kind of default mode. Open MPI, at least, uses this when it thinks it is exactly- or under-subscribed (number of processes<=number of processesors). In this mode processes will never voluntarily give up the ...
4
Use a library such as PETSc or Trilinos. They offer you data structures for parallel linear systems and algorithms that can work on them, such as parallel implementations of CG or GMRES. The PETSc manual provides extensive examples on how to use all of this. I'm quite certain that there's in fact even a tutorial program that already gets you 90% there.
4
There are several MPI-enabled software packages that use the CMake set of tools for testing. The ones that I can think of off the top of my head are Trilinos, VTK and ParaView. I would think that you don't want to assume that the executable needs to be launched with mpirun and/or mpiexec. CMake has support for specifying how to properly launch the executable ...
4
We simply roll our own code in deal.II -- in essence, we tell the framework to execute tests using mpirun -np .... We had previously just used a Makefile-based testing scheme (compile, link, execute test, then compare the output with one that had previously been saved) and you can find this here:
https://svn.dealii.org/branches/releases/Branch-8-0/tests/mpi/...
4
I suggest you take a look at ViennaCL. It's written in c++, leverages template meta programming, and supports OpenCL, CUDA, and OpenMP as backends. Just like Thrust, it has abstraction layers for device and host containers and implements several algorithms, mostly in the area of linear algebra. Although, device integer containers are missing as of version 1....
4
The two books that come to mind are Using MPI and Using Advanced MPI by Gropp and Lusk. They were also released in a 3rd edition last year, so they are very up to date. As others have said, the reference manuals are open and available for free. It's nice to have the books to help you get started and the reference manuals to look up certain details.
4
PETSc does this. See the documentation for MatShell and Section 3.3 in the manual.
4
As Wolfgang observed, you are basically transposing a connectivity matrix: every process $i$ knows row $i$ that states which $j$ values you're sending to. What you're interested in is the columns: the description in column $j$ of everyone that sends to $j$. However, implementing this with an Allgather is overkill: you only need to know the sum of the entries ...
4
That depends on your goal.
For one process it's obvious that $t$ is the wall-time of the entire program launch.
For two processes, you got $t_1$ and $t_2$ which correspond for the walltime on processors 1 and 2.
Usually, one is interested in the total time it took to solve the problem - aka overall walltime, which will be $t=\max(t_1,t_2)$. However, I ...
Only top voted, non community-wiki answers of a minimum length are eligible