There is no problem in parallelizing the solver as you want to do. I am currently writing an example in the documentation. I will make another post very soon.
Gilles

I am facing a very strange problem. Whenever I am solving an example with default solver it takes around 125 seconds to search for atleast one solution. When I am parallelizing it using 4 instances of solver it takes around 30 seconds to search the first solution. Technically if I use 8 instances of solver it should be able to find it in less time (if not half). But following is what I get.

with 4 parallel instances of default solver:

number of solutions from solver 1=156
cpu time used=60.404s.
number of cells=470
number of solutions from solver 2=0
cpu time used=60.376s.
number of cells=426
number of solutions from solver 3=0
cpu time used=60.396s.
number of cells=458
number of solutions from solver 4=0
cpu time used=4.256s.
number of cells=8

From 8 instances I get follwing results:

number of solutions from solver 1=0
cpu time used=150.016s.
number of cells=1412
number of solutions from solver 2=0
cpu time used=150.204s.
number of cells=1180
number of solutions from solver 3=0
cpu time used=150.08s.
number of cells=1436
number of solutions from solver 4=0
cpu time used=150.012s.
number of cells=1284
number of solutions from solver 5=0
cpu time used=64.236s.
number of cells=508
number of solutions from solver 6=0
cpu time used=9.156s.
number of cells=34
number of solutions from solver 7=0
cpu time used=3.632s.
number of cells=4
number of solutions from solver 8=0
cpu time used=3.092s.
number of cells=2

Further I am sharing the files including .bch file and 2 versions of parallel solvers with 8 (par8.cpp and binary) and 4 (par4.cpp and binary). I am not able to figure out where I am wrong. One more thing? #pragma omp parallel generates exactly parallel threads? The reason I am confused is that if I pass a time limit to all solver for 60 seconds they all should together be terminated after 60 seconds. Which is not the case as they take time_limit * no of instances of solvers which are being generated. So if there are 4 solvers and I passed 60 seconds time limit they will never terminate exactly after 60 seconds and terminal will be on hold for around 5-6 minutes.

Any solution ? Following is the link to my dropbox folder where I have placed the files.

Technically if I use 8 instances of solver it should be able to find it in less time (if not half)

Unfortunately, no. It is possible that 8 solvers take more time than 4. The reason is that by splitting 8 times the initial box in a specific way, you change the way the combinatorial search is performed. And this can turn to be less efficient even if each of the 8 solvers has 50% less space to explore.

One more thing? #pragma omp parallel generates exactly parallel threads?

I don't know but this is not the good place for asking this question, I think you can find the answer in some forums specialized on parallel processing.

if I pass a time limit to all solver for 60 seconds they all should together be terminated after 60 seconds

Again, I'm not an expert in parallel computing but I guess It depends on the number of cores you have on your processor. If you have as many cores as solvers, yes. But otherwise, the time spent by one processor will be shared by, say, two solvers and since each solver can spend up to 60 seconds of computation, the overall time spent by this core will be 120 seconds. Does this answer your question?

Other thing, I am not 100% sure that the Timer class we use in Ibex supports several threads. This may be another explanation.

I guess you are right about the timing class, it seems that it does't support several threads, the evidence for this is that, even if I assign differetn threads to different cores (I am using system with 32 cores) and set time_limit to 10 sec it still takes 1:20 secounds to terminate for four solvers. Which is a clear evidence (given the fact that I have tested it multiple times) that multiple instances cannot be executed in parallel. Is it possible to modify that timer class?

The second thing is that, I just realised that If I generated multiple instances of defaultsolver the only process which is generating more overhead is generating solvers and passing them a coppy of system to solve which is:
DefaultSolver s1(sys1,prec);
DefaultSolver s2(sys2,prec);
DefaultSolver s3(sys3,prec);
DefaultSolver s4(sys4,prec);

It consumes around 2 minutes but after that the parallel search is quick. The only flaw is the overhead time for creating these four solvers. Is there any way to parallelize it ? or reduce this time to few seconds?

Around 1000 constraints, and 112 variables. I have made a small program which assigns different instances of the solver to different threads and bind those threads cores, I can share that case study just in case you are intrested to add that to tutorial it may be benificial for users as it provides me a nice speed up.

zenno

Mon, 08/25/2014 - 17:42

Permalink

## Hi Usman,

Hi Usman,

There is no problem in parallelizing the solver as you want to do. I am currently writing an example in the documentation. I will make another post very soon.

Gilles

usmanrauf85

Mon, 08/25/2014 - 21:27

Permalink

## Dr. Gilles

Thank you very much, I will be waiting for that.

--Usman

zenno

Mon, 08/25/2014 - 22:57

Permalink

## Here is the example :

Here is the example :

http://www.ibex-lib.org/doc/strategy.html#parallelizing-search

Best regards

Gilles

usmanrauf85

Sat, 08/30/2014 - 00:43

Permalink

## Dr. Gilles

I am facing a very strange problem. Whenever I am solving an example with default solver it takes around 125 seconds to search for atleast one solution. When I am parallelizing it using 4 instances of solver it takes around 30 seconds to search the first solution. Technically if I use 8 instances of solver it should be able to find it in less time (if not half). But following is what I get.

with 4 parallel instances of default solver:

number of solutions from solver 1=156

cpu time used=60.404s.

number of cells=470

number of solutions from solver 2=0

cpu time used=60.376s.

number of cells=426

number of solutions from solver 3=0

cpu time used=60.396s.

number of cells=458

number of solutions from solver 4=0

cpu time used=4.256s.

number of cells=8

From 8 instances I get follwing results:

number of solutions from solver 1=0

cpu time used=150.016s.

number of cells=1412

number of solutions from solver 2=0

cpu time used=150.204s.

number of cells=1180

number of solutions from solver 3=0

cpu time used=150.08s.

number of cells=1436

number of solutions from solver 4=0

cpu time used=150.012s.

number of cells=1284

number of solutions from solver 5=0

cpu time used=64.236s.

number of cells=508

number of solutions from solver 6=0

cpu time used=9.156s.

number of cells=34

number of solutions from solver 7=0

cpu time used=3.632s.

number of cells=4

number of solutions from solver 8=0

cpu time used=3.092s.

number of cells=2

Following is my parallel section for 8 instances:

and following is the parallel section for 4 instances:

Further I am sharing the files including .bch file and 2 versions of parallel solvers with 8 (par8.cpp and binary) and 4 (par4.cpp and binary). I am not able to figure out where I am wrong. One more thing? #pragma omp parallel generates exactly parallel threads? The reason I am confused is that if I pass a time limit to all solver for 60 seconds they all should together be terminated after 60 seconds. Which is not the case as they take time_limit * no of instances of solvers which are being generated. So if there are 4 solvers and I passed 60 seconds time limit they will never terminate exactly after 60 seconds and terminal will be on hold for around 5-6 minutes.

Any solution ? Following is the link to my dropbox folder where I have placed the files.

https://www.dropbox.com/sh/b81clnf3igm07wb/AAB-iTMWI2Xnp5sXi2MbZ-Zqa?dl=0

Note: Please set precision to 1 using both of the scripts.

Regards,

Usman

zenno

Tue, 09/02/2014 - 14:57

Permalink

## Running times with parallel solvers

Usman,

Unfortunately, no. It is possible that 8 solvers take more time than 4. The reason is that by splitting 8 times the initial box in a specific way, you change the way the combinatorial search is performed. And this can turn to be less efficient even if each of the 8 solvers has 50% less space to explore.

I don't know but this is not the good place for asking this question, I think you can find the answer in some forums specialized on parallel processing.

Again, I'm not an expert in parallel computing but I guess It depends on the number of cores you have on your processor. If you have as many cores as solvers, yes. But otherwise, the time spent by one processor will be shared by, say, two solvers and since each solver can spend up to 60 seconds of computation, the overall time spent by this core will be 120 seconds. Does this answer your question?

Other thing, I am not 100% sure that the Timer class we use in Ibex supports several threads. This may be another explanation.

Regards,

Gilles

usmanrauf85

Thu, 09/04/2014 - 17:28

Permalink

## Dr. Gilles

I guess you are right about the timing class, it seems that it does't support several threads, the evidence for this is that, even if I assign differetn threads to different cores (I am using system with 32 cores) and set time_limit to 10 sec it still takes 1:20 secounds to terminate for four solvers. Which is a clear evidence (given the fact that I have tested it multiple times) that multiple instances cannot be executed in parallel. Is it possible to modify that timer class?

The second thing is that, I just realised that If I generated multiple instances of defaultsolver the only process which is generating more overhead is generating solvers and passing them a coppy of system to solve which is:

DefaultSolver s1(sys1,prec);

DefaultSolver s2(sys2,prec);

DefaultSolver s3(sys3,prec);

DefaultSolver s4(sys4,prec);

It consumes around 2 minutes but after that the parallel search is quick. The only flaw is the overhead time for creating these four solvers. Is there any way to parallelize it ? or reduce this time to few seconds?

Thanks

Usman

zenno

Fri, 09/26/2014 - 12:18

Permalink

## Timer is not thread-safe

I've made a feature request: https://github.com/ibex-team/ibex-lib/issues/51

So, each solver requires around 30 seconds to be created, right? Can you tell me the size of your problem (number of variables/constraints)?

Gilles

usmanrauf85

Thu, 10/23/2014 - 07:56

Permalink

## Dr. Gilles

Around 1000 constraints, and 112 variables. I have made a small program which assigns different instances of the solver to different threads and bind those threads cores, I can share that case study just in case you are intrested to add that to tutorial it may be benificial for users as it provides me a nice speed up.

Thanks,