Intel® oneAPI Threading Building Blocks
Ask questions and share information about adding parallelism to your applications when using this threading library.
2479 Discussions

Using an mpz_t (from gmp) as iteration space

lancekimbrough
Beginner
1,652 Views

I'm trying to parallelize a program that deals with very large numbers (using the GNU MP library). I would like to use the GMP integer (mpz) type as the iterator. The basic loop form, in my standard serial program is....

[cpp]#include  
#include

using namespace std;

int main () {

mpz_class i; // loop iterator
mpz_class imin; // minimum loop iterator
mpz_class imax; // maximum loop iterator

imin="1000000000000000000";
imax="1000000000000000010";

for (i=imin; i // perform calculations with "i"...
cout << i << endl;
}

return 0;
}[/cpp]

This serial version works just fine.

I've been trying to figure out a way to use this same form with TBB, but I'm having a difficult time. I fear I'll have to create my own iteration space (but I'm not sure if I know c++ well enough yet to do that). I've been trying to use the standard blocked_range, but can not seem to get it to work. I thought I might ask here if anyone knows of a way to use an mpz type with the blocked_range class before I attempt to create my own iteration space.

My code (that fails to compile) in attempts to use an mpz_t in the iteration space is....

[cpp]

#include  
#include
#include "tbb/task_scheduler_init.h"
#include "tbb/blocked_range.h"
#include "tbb/parallel_for.h"


using namespace tbb;
using namespace std;


class PMPZ {
public:
void operator()( const blocked_range& range ) const {
mpz_class i;
for(i=range.begin(); i cout << i << "n";
}
}
};

void ParallelMPZ(mpz_t bb, mpz_t ee) {
PMPZ mpztest;
parallel_for(blocked_range(bb, ee, 1000), mpztest );
}

int main() {
task_scheduler_init init;

mpz_class b;
b="100000000000000000000";

mpz_class e;
e="100000000000000000100";

ParallelMPZ(b.get_mpz_t(), e.get_mpz_t());

return 0;
}[/cpp]

I've tried using mpz_class as the iteration type (rather than mpz_t) as well, but can't seem to get anything to work. I think the problem is more fundamental, in that the mpz_class (and mpz_t) objects are arrays, which the blocked_range seems to have trouble with. When I attempt to compile, I get the following....

/opt/intel/tbb/2.0/include/tbb/blocked_range.h: In instantiation of tbb::blocked_range<__mpz_struct [1]>:
parallelformpz.cpp:16: instantiated from here
/opt/intel/tbb/2.0/include/tbb/blocked_range.h:53: error: function returning an array
/opt/intel/tbb/2.0/include/tbb/blocked_range.h:56: error: function returning an array
/opt/intel/tbb/2.0/include/tbb/blocked_range.h:96: error: function returning an array
parallelformpz.cpp: In member function void PMPZ::operator()(const tbb::blocked_range<__mpz_struct [1]>&) const:
parallelformpz.cpp:16: error: const class tbb::blocked_range<__mpz_struct [1]> has no member named begin
parallelformpz.cpp:16: error: const class tbb::blocked_range<__mpz_struct [1]> has no member named end
/opt/intel/tbb/2.0/include/tbb/blocked_range.h: In constructor tbb::blocked_range::blocked_range(Value, Value, size_t) [with Value = __mpz_struct [1]]:
parallelformpz.cpp:24: instantiated from here
/opt/intel/tbb/2.0/include/tbb/blocked_range.h:47: error: incompatible types in assignment of __mpz_struct* to __mpz_struct [1]
/opt/intel/tbb/2.0/include/tbb/blocked_range.h:47: error: incompatible types in assignment of __mpz_struct* to __mpz_struct [1]
/opt/intel/tbb/2.0/include/tbb/blocked_range.h: In constructor tbb::blocked_range::blocked_range(tbb::blocked_range&, tbb::split) [with Value = __mpz_struct [1]]:
/opt/intel/tbb/2.0/include/tbb/parallel_for.h:60: instantiated from tbb::task* tbb::internal::start_for::execute() [with Range = tbb::blocked_range<__mpz_struct [1]>, Body = PMPZ, Partitioner = tbb::simple_partitioner]
parallelformpz.cpp:39: instantiated from here
/opt/intel/tbb/2.0/include/tbb/blocked_range.h:85: error: do_split was not declared in this scope
/opt/intel/tbb/2.0/include/tbb/blocked_range.h:85: error: array used as initializer

Does anyone have any idea how I can use the mpz object type as an iterator? I appreciate any help!

Best Regards,
Lance

0 Kudos
7 Replies
AJ13
New Contributor I
1,652 Views

It won't work. First, I changed your mpz_t to mpz_class, since mpz_t is not going to have C++ operators overidden that I know of. For instance, what is mpz_t x; mpz_t y = "1100"; x = y+1; going to evaluate to? This should be defined for something like TBB Ranges to work, which uses templates.

Anyhew, the culprit here is that the blocked_range uses a size_t to determine the actual size of the range. In your case, this won't work because size_t will not always have enough bits to represent the absurdly large numbers you are working with.

Unfortunately, you have no choice but to design your own Range. Not to worry, this isn't so hard. The manual has some good documentation, and we're here to help you if you get stuck :-)

If you need live help, I hang out on #tbb on irc.freenode.net.

0 Kudos
lancekimbrough
Beginner
1,652 Views
Quoting - AJ

It won't work. First, I changed your mpz_t to mpz_class, since mpz_t is not going to have C++ operators overidden that I know of. For instance, what is mpz_t x; mpz_t y = "1100"; x = y+1; going to evaluate to? This should be defined for something like TBB Ranges to work, which uses templates.

Anyhew, the culprit here is that the blocked_range uses a size_t to determine the actual size of the range. In your case, this won't work because size_t will not always have enough bits to represent the absurdly large numbers you are working with.

Unfortunately, you have no choice but to design your own Range. Not to worry, this isn't so hard. The manual has some good documentation, and we're here to help you if you get stuck :-)

If you need live help, I hang out on #tbb on irc.freenode.net.

Thanks AJ. I really appreciate the help. So, in light of knowing that I'll have to create my own Range, I've been trying to implement the simple "TrivialIntegerRange" from the TBB O'Reilly book (Example 3-17 on pg 46), and use it to split up a simple range of integers. I thought I'd try to get this to work (and get a grasp of implementing a simple range), and then try to extend it into using the MPZ class.

Well, I finally got the simple integer range to work, but sometimes I get some strange values on output. Here is the code...

[cpp]#include  
#include
#include "tbb/task_scheduler_init.h"
#include "tbb/parallel_for.h"
#include "tbb/tbb_stddef.h"

using namespace tbb;
using namespace std;


// int range over which to iterate.
class TrivialIntegerRange {
public:
int lower;
int upper;

TrivialIntegerRange(int begin, int end) :
lower(begin), upper(end)
{}

bool empty() const {return lower==upper;}
bool is_divisible() const {return upper>lower+1;}
TrivialIntegerRange( TrivialIntegerRange& r, split) {
int m = (r.lower+r.upper)/2;
lower = m;
upper = r.upper;
r.upper=m;
}
};


class PMPZ {
public:
void operator()( const TrivialIntegerRange& range ) const {

for(int i=range.lower; i cout << i << "n";
}
}
};

void ParallelMPZ(int bb, int ee) {
PMPZ mpztest;
parallel_for(TrivialIntegerRange(bb, ee), mpztest );
}

int main() {
task_scheduler_init init;

// beginning iterator
int b = 100;

// ending iterator
int e = 200;

ParallelMPZ(b, e);

return 0;
}[/cpp]

When I run it, I sometimes get the full list of numbers from 100 to 199 (in the order expected from recursion), but sometimes I'll get a strange value (and empty lines) in the middle of some of the numbers, such as...

100
150101
102

103
104
105
106
107
108
151109
152
153
154
155
156
157
158
159
160
...

First of all, why 150101? And then an empty line after 102? What's going on here? I wonder if it's accessing memory where it shouldn't? It's strange that sometimes it works perfectly and sometimes I get these strange values. I'm thinking it has something to do with how the range is split up, but I'm a little lost...

0 Kudos
Alexey-Kukanov
Employee
1,652 Views
Quoting - lancekimbrough
First of all, why 150101? And then an empty line after 102? What's going on here? I wonder if it's accessing memory where it shouldn't? It's strange that sometimes it works perfectly and sometimes I get these strange values. I'm thinking it has something to do with how the range is split up, but I'm a little lost...

What you see is just fine for parallel code that prints something into cout. 150101 is likely 150 followed by 101, the empty line after 102 should actually be after 150, asn so on. The code was truly executed in parallel thus all this mess; cout does not synchronize outputs done simultaneously from different threads (or might be it does, but on too low the level); so syncronize the calls on your own(e.g. with tbb::spin_mutex), as you would syncronize updates to a global variable.

0 Kudos
Dmitry_Vyukov
Valued Contributor I
1,652 Views
Quoting - lancekimbrough
[cpp]        for(int i=range.lower; i            cout << i << "n";
[/cpp]

Try "printf("%dn", i);" instead.

0 Kudos
RafSchietekat
Valued Contributor III
1,652 Views

printf() also requires synchronisation, methinks. You could increase the odds in your favour by flushing, which stderr does implicitly (I think), but I have seen no guarantees (otherwise pray tell).

0 Kudos
Dmitry_Vyukov
Valued Contributor I
1,652 Views
Quoting - Raf Schietekat

printf() also requires synchronisation, methinks. You could increase the odds in your favour by flushing, which stderr does implicitly (I think), but I have seen no guarantees (otherwise pray tell).

My C/C++ library implementation internally synchronizes printf() calls. So if string is outputted via single printf() call, then it's undividable on the screen.

0 Kudos
robert_jay_gould
Beginner
1,652 Views
Quoting - Dmitriy V'jukov

My C/C++ library implementation internally synchronizes printf() calls. So if string is outputted via single printf() call, then it's undividable on the screen.

My printf() also works ok on Windows and Unix, however on Solaris it buffers up many lines before printing, which is confusing at time.

0 Kudos
Reply