I want to reduce the calculation time for a time-consuming integral by splitting the integration range. I'm using C++, Windows, and a quad-core Intel i7 CPU.
How can I split it into 4 parallel computations?
+3
A:
What is your integration algorithm?
Mathematically, integral over range is sum of integrals over parts, so parallelization seems trivial.
Pavel Radzivilovsky
2010-04-13 11:38:13
Mathematically, it's an infinite sum which would explain the time-consuming part ;) Seriously, in real-world use the algorithms used are more complex then simply `std::accumulate()`
MSalters
2010-04-13 12:18:33
well, beware of summing floating point numbers. loses precision.
Pavel Radzivilovsky
2010-04-13 13:43:21
Thanks for response. The integration is just summing over values but, I think I am in deeper trouble: The code is written in Borland c++ v5.02 and apparently I first have to migrate to a compiler that supports parallel computing. I will put this question separately...
Iman
2010-04-16 15:53:55
A:
I suggest you look at intel's thread building blocks.
http://www.threadingbuildingblocks.org/
and especially parallel_reduce.
Andreas Brinck
2010-04-13 11:40:25
You're right. Since it is about development under Windows, I assume that Visual C++ is used for compilation...
Cătălin Pitiș
2010-04-13 12:00:33
+1
A:
As others have said, and I'm sure you would know integration is summation, parellization should be easy I know you are using C++, but is using go a possibility? It is very easy to use goroutines to do this type of job. But I understand if this code is going to a customer you would be reluctant to use go as it is still untested in the wild. If it is a personal project go for it (no pun intended).
hhafez
2010-04-13 11:45:44
A:
The problem you'll have is boundary conditions.
It's easy to think that numerical quadrature can be broken up into several domains, but you don't know what the internal boundary conditions are.
Breaking an integral up into subdomains starts sounding like a finite element, finite difference, or boundary element solution. You've taken a complex domain, broken into to pieces, turned it into a matrix, and solved it given the boundary conditions you know.
I don't think this is as simple as breaking the domain into subdomains and assigning each one to a processor, but I could be wrong.
duffymo
2010-04-13 12:11:45
+1
A:
Tackle this in 2 parts:
1) What approach to parallelisation are you going to take: MPI, OpenMP, threads, what-have-you ? and
2) How to modify the algorithm.
On a quad-core Windows machine, I'd suggest OpenMP as my answer to the first part of this. The answer to the second part depends on what algorithm you are using. If, for example, you are using the Monte Carlo technique, parallelisation is trivial. If you're using numerical quadrature of some sort, it's a lot less trivial to ensure that none of the corner cases that others have identified become serious problems. However, if you can exclude pathological integrals it shouldn't be prohibitively difficult
High Performance Mark
2010-04-13 12:33:29
A:
You can calculate the integral using the Trapezoidal rule (or any other of the Newton-Cotes formulas). To get a better result, you can segment the interval and use the Trapezoidal rule for each segment. The formula can be found in the linked article.
Since each calculation is independent of the other, you can execute them in parallel. The easiest way to do this is OpenMP (as mentioned above).
Tobias Langner
2010-04-13 13:09:32