001/* 002 * $Id: SolvableGroebnerBaseParallel.java 4104 2012-08-18 10:00:59Z kredel $ 003 */ 004 005package edu.jas.gb; 006 007 008import java.util.ArrayList; 009import java.util.List; 010import java.util.ListIterator; 011import java.util.concurrent.Semaphore; 012 013import org.apache.log4j.Logger; 014 015import edu.jas.poly.ExpVector; 016import edu.jas.poly.GenSolvablePolynomial; 017import edu.jas.poly.GenSolvablePolynomialRing; 018import edu.jas.structure.RingElem; 019import edu.jas.util.Terminator; 020import edu.jas.util.ThreadPool; 021 022 023/** 024 * Solvable Groebner Base parallel algorithm. Implements a shared memory 025 * parallel version of Groebner bases. Threads maintain pairlist. 026 * @param <C> coefficient type 027 * @author Heinz Kredel 028 */ 029 030public class SolvableGroebnerBaseParallel<C extends RingElem<C>> extends SolvableGroebnerBaseAbstract<C> { 031 032 033 private static final Logger logger = Logger.getLogger(SolvableGroebnerBaseParallel.class); 034 035 036 //private static final boolean debug = logger.isDebugEnabled(); 037 038 039 /** 040 * Number of threads to use. 041 */ 042 protected final int threads; 043 044 045 /** 046 * Pool of threads to use. 047 */ 048 protected transient final ThreadPool pool; 049 050 051 /** 052 * Constructor. 053 */ 054 public SolvableGroebnerBaseParallel() { 055 this(2); 056 } 057 058 059 /** 060 * Constructor. 061 * @param threads number of threads to use. 062 */ 063 public SolvableGroebnerBaseParallel(int threads) { 064 this(threads, new ThreadPool(threads)); 065 } 066 067 068 /** 069 * Constructor. 070 * @param threads number of threads to use. 071 * @param pool ThreadPool to use. 072 */ 073 public SolvableGroebnerBaseParallel(int threads, ThreadPool pool) { 074 this(threads, pool, new SolvableReductionPar<C>()); 075 } 076 077 078 /** 079 * Constructor. 080 * @param threads number of threads to use. 081 * @param sred parallelism aware reduction engine 082 */ 083 public SolvableGroebnerBaseParallel(int threads, SolvableReduction<C> sred) { 084 this(threads, new ThreadPool(threads), sred); 085 } 086 087 088 /** 089 * Constructor. 090 * @param threads number of threads to use. 091 * @param pl pair selection strategy 092 */ 093 public SolvableGroebnerBaseParallel(int threads, PairList<C> pl) { 094 this(threads, new ThreadPool(threads), new SolvableReductionPar<C>(), pl); 095 } 096 097 098 /** 099 * Constructor. 100 * @param threads number of threads to use. 101 * @param sred parallelism aware reduction engine 102 * @param pl pair selection strategy 103 */ 104 public SolvableGroebnerBaseParallel(int threads, SolvableReduction<C> sred, PairList<C> pl) { 105 this(threads, new ThreadPool(threads), sred, pl); 106 } 107 108 109 /** 110 * Constructor. 111 * @param threads number of threads to use. 112 * @param pool ThreadPool to use. 113 * @param sred parallelism aware reduction engine 114 */ 115 public SolvableGroebnerBaseParallel(int threads, ThreadPool pool, SolvableReduction<C> sred) { 116 this(threads, pool, sred, new OrderedPairlist<C>()); 117 } 118 119 120 /** 121 * Constructor. 122 * @param threads number of threads to use. 123 * @param pool ThreadPool to use. 124 * @param sred parallelism aware reduction engine 125 * @param pl pair selection strategy 126 */ 127 public SolvableGroebnerBaseParallel(int threads, ThreadPool pool, SolvableReduction<C> sred, 128 PairList<C> pl) { 129 super(sred, pl); 130 if (!(sred instanceof SolvableReductionPar)) { 131 logger.warn("parallel GB should use parallel aware reduction"); 132 } 133 if (threads < 1) { 134 threads = 1; 135 } 136 this.threads = threads; 137 this.pool = pool; 138 } 139 140 141 /** 142 * Cleanup and terminate ThreadPool. 143 */ 144 public void terminate() { 145 if (pool == null) { 146 return; 147 } 148 pool.terminate(); 149 } 150 151 152 /** 153 * Parallel Groebner base using sequential pair order class. Threads 154 * maintain pairlist. 155 * @param modv number of module variables. 156 * @param F polynomial list. 157 * @return GB(F) a Groebner base of F. 158 */ 159 public List<GenSolvablePolynomial<C>> leftGB(int modv, List<GenSolvablePolynomial<C>> F) { 160 GenSolvablePolynomial<C> p; 161 List<GenSolvablePolynomial<C>> G = new ArrayList<GenSolvablePolynomial<C>>(); 162 PairList<C> pairlist = null; 163 int l = F.size(); 164 ListIterator<GenSolvablePolynomial<C>> it = F.listIterator(); 165 while (it.hasNext()) { 166 p = it.next(); 167 if (p.length() > 0) { 168 p = (GenSolvablePolynomial<C>) p.monic(); 169 if (p.isONE()) { 170 G.clear(); 171 G.add(p); 172 return G; // since no threads activated jet 173 } 174 G.add(p); 175 if (pairlist == null) { 176 //pairlist = new OrderedPairlist<C>( modv, p.ring ); 177 pairlist = strategy.create(modv, p.ring); 178 if (!p.ring.coFac.isField()) { 179 throw new IllegalArgumentException("coefficients not from a field"); 180 } 181 } 182 // putOne not required 183 pairlist.put(p); 184 } else { 185 l--; 186 } 187 } 188 if (l <= 1) { 189 return G; // since no threads activated jet 190 } 191 192 Terminator fin = new Terminator(threads); 193 LeftSolvableReducer<C> R; 194 for (int i = 0; i < threads; i++) { 195 R = new LeftSolvableReducer<C>(fin, G, pairlist); 196 pool.addJob(R); 197 } 198 fin.waitDone(); 199 logger.debug("#parallel list = " + G.size()); 200 G = leftMinimalGB(G); 201 // not in this context // pool.terminate(); 202 logger.info("" + pairlist); 203 return G; 204 } 205 206 207 /** 208 * Minimal ordered groebner basis, parallel. 209 * @param Fp a Groebner base. 210 * @return minimalGB(F) a minimal Groebner base of Fp. 211 */ 212 @Override 213 public List<GenSolvablePolynomial<C>> leftMinimalGB(List<GenSolvablePolynomial<C>> Fp) { 214 GenSolvablePolynomial<C> a; 215 ArrayList<GenSolvablePolynomial<C>> G; 216 G = new ArrayList<GenSolvablePolynomial<C>>(Fp.size()); 217 ListIterator<GenSolvablePolynomial<C>> it = Fp.listIterator(); 218 while (it.hasNext()) { 219 a = it.next(); 220 if (a.length() != 0) { // always true 221 // already monic a = a.monic(); 222 G.add(a); 223 } 224 } 225 if (G.size() <= 1) { 226 return G; 227 } 228 229 ExpVector e; 230 ExpVector f; 231 GenSolvablePolynomial<C> p; 232 ArrayList<GenSolvablePolynomial<C>> F; 233 F = new ArrayList<GenSolvablePolynomial<C>>(G.size()); 234 boolean mt; 235 while (G.size() > 0) { 236 a = G.remove(0); 237 e = a.leadingExpVector(); 238 239 it = G.listIterator(); 240 mt = false; 241 while (it.hasNext() && !mt) { 242 p = it.next(); 243 f = p.leadingExpVector(); 244 mt = e.multipleOf(f); 245 } 246 it = F.listIterator(); 247 while (it.hasNext() && !mt) { 248 p = it.next(); 249 f = p.leadingExpVector(); 250 mt = e.multipleOf(f); 251 } 252 if (!mt) { 253 F.add(a); // no thread at this point 254 } else { 255 // System.out.println("dropped " + a.length()); 256 } 257 } 258 G = F; 259 if (G.size() <= 1) { 260 return G; 261 } 262 263 SolvableMiReducer<C>[] mirs = (SolvableMiReducer<C>[]) new SolvableMiReducer[G.size()]; 264 int i = 0; 265 F = new ArrayList<GenSolvablePolynomial<C>>(G.size()); 266 while (G.size() > 0) { 267 a = G.remove(0); 268 // System.out.println("doing " + a.length()); 269 List<GenSolvablePolynomial<C>> R = new ArrayList<GenSolvablePolynomial<C>>(G.size() + F.size()); 270 R.addAll(G); 271 R.addAll(F); 272 mirs[i] = new SolvableMiReducer<C>(R, a); 273 pool.addJob(mirs[i]); 274 i++; 275 F.add(a); 276 } 277 G = F; 278 F = new ArrayList<GenSolvablePolynomial<C>>(G.size()); 279 for (i = 0; i < mirs.length; i++) { 280 a = mirs[i].getNF(); 281 F.add(a); 282 } 283 return F; 284 } 285 286 287 /** 288 * Solvable Extended Groebner base using critical pair class. 289 * @param modv module variable number. 290 * @param F solvable polynomial list. 291 * @return a container for an extended left Groebner base of F. 292 */ 293 public SolvableExtendedGB<C> extLeftGB(int modv, List<GenSolvablePolynomial<C>> F) { 294 throw new UnsupportedOperationException("parallel extLeftGB not implemented"); 295 } 296 297 298 /** 299 * Twosided Groebner base using pairlist class. 300 * @param modv number of module variables. 301 * @param Fp solvable polynomial list. 302 * @return tsGB(Fp) a twosided Groebner base of F. 303 */ 304 @SuppressWarnings("unchecked") 305 public List<GenSolvablePolynomial<C>> twosidedGB(int modv, List<GenSolvablePolynomial<C>> Fp) { 306 if (Fp == null || Fp.size() == 0) { // 0 not 1 307 return new ArrayList<GenSolvablePolynomial<C>>(); 308 } 309 GenSolvablePolynomialRing<C> fac = Fp.get(0).ring; // assert != null 310 //List<GenSolvablePolynomial<C>> X = generateUnivar( modv, Fp ); 311 List<GenSolvablePolynomial<C>> X = fac.univariateList(modv); 312 //System.out.println("X univ = " + X); 313 List<GenSolvablePolynomial<C>> F = new ArrayList<GenSolvablePolynomial<C>>(Fp.size() * (1 + X.size())); 314 F.addAll(Fp); 315 GenSolvablePolynomial<C> p, x, q; 316 for (int i = 0; i < Fp.size(); i++) { 317 p = Fp.get(i); 318 for (int j = 0; j < X.size(); j++) { 319 x = X.get(j); 320 q = p.multiply(x); 321 q = sred.leftNormalform(F, q); 322 if (!q.isZERO()) { 323 F.add(q); 324 } 325 } 326 } 327 //System.out.println("F generated = " + F); 328 List<GenSolvablePolynomial<C>> G = new ArrayList<GenSolvablePolynomial<C>>(); 329 PairList<C> pairlist = null; 330 int l = F.size(); 331 ListIterator<GenSolvablePolynomial<C>> it = F.listIterator(); 332 while (it.hasNext()) { 333 p = it.next(); 334 if (p.length() > 0) { 335 p = (GenSolvablePolynomial<C>) p.monic(); 336 if (p.isONE()) { 337 G.clear(); 338 G.add(p); 339 return G; // since no threads are activated 340 } 341 G.add(p); 342 if (pairlist == null) { 343 //pairlist = new OrderedPairlist<C>( modv, p.ring ); 344 pairlist = strategy.create(modv, p.ring); 345 if (!p.ring.coFac.isField()) { 346 throw new IllegalArgumentException("coefficients not from a field"); 347 } 348 } 349 // putOne not required 350 pairlist.put(p); 351 } else { 352 l--; 353 } 354 } 355 //System.out.println("G to check = " + G); 356 if (l <= 1) { // 1 ok 357 return G; // since no threads are activated 358 } 359 Terminator fin = new Terminator(threads); 360 TwosidedSolvableReducer<C> R; 361 for (int i = 0; i < threads; i++) { 362 R = new TwosidedSolvableReducer<C>(fin, X, G, pairlist); 363 pool.addJob(R); 364 } 365 fin.waitDone(); 366 logger.debug("#parallel list = " + G.size()); 367 G = leftMinimalGB(G); 368 // not in this context // pool.terminate(); 369 logger.info("" + pairlist); 370 return G; 371 } 372 373} 374 375 376/** 377 * Reducing left worker threads. 378 * @param <C> coefficient type 379 */ 380class LeftSolvableReducer<C extends RingElem<C>> implements Runnable { 381 382 383 private final List<GenSolvablePolynomial<C>> G; 384 385 386 private final PairList<C> pairlist; 387 388 389 private final Terminator pool; 390 391 392 private final SolvableReductionPar<C> sred; 393 394 395 private static final Logger logger = Logger.getLogger(LeftSolvableReducer.class); 396 397 398 private static final boolean debug = logger.isDebugEnabled(); 399 400 401 LeftSolvableReducer(Terminator fin, List<GenSolvablePolynomial<C>> G, PairList<C> L) { 402 pool = fin; 403 this.G = G; 404 pairlist = L; 405 sred = new SolvableReductionPar<C>(); 406 } 407 408 409 @SuppressWarnings("unchecked") 410 public void run() { 411 Pair<C> pair; 412 GenSolvablePolynomial<C> S; 413 GenSolvablePolynomial<C> H; 414 boolean set = false; 415 int reduction = 0; 416 int sleeps = 0; 417 while (pairlist.hasNext() || pool.hasJobs()) { 418 while (!pairlist.hasNext()) { 419 // wait 420 pool.beIdle(); 421 set = true; 422 try { 423 sleeps++; 424 if (sleeps % 10 == 0) { 425 logger.info(" reducer is sleeping"); 426 } else { 427 logger.debug("r"); 428 } 429 Thread.sleep(100); 430 } catch (InterruptedException e) { 431 break; 432 } 433 if (!pool.hasJobs()) { 434 break; 435 } 436 } 437 if (!pairlist.hasNext() && !pool.hasJobs()) { 438 break; 439 } 440 if (set) { 441 pool.notIdle(); 442 set = false; 443 } 444 pair = pairlist.removeNext(); 445 if (pair == null) { 446 continue; 447 } 448 if (debug) { 449 logger.debug("pi = " + pair.pi); 450 logger.debug("pj = " + pair.pj); 451 } 452 S = sred.leftSPolynomial((GenSolvablePolynomial<C>) pair.pi, (GenSolvablePolynomial<C>) pair.pj); 453 if (S.isZERO()) { 454 continue; 455 } 456 if (debug) { 457 logger.debug("ht(S) = " + S.leadingExpVector()); 458 } 459 H = sred.leftNormalform(G, S); //mod 460 reduction++; 461 if (H.isZERO()) { 462 continue; 463 } 464 if (debug) { 465 logger.debug("ht(H) = " + H.leadingExpVector()); 466 } 467 H = (GenSolvablePolynomial<C>) H.monic(); 468 // System.out.println("H = " + H); 469 if (H.isONE()) { 470 pairlist.putOne(); // not really required 471 synchronized (G) { 472 G.clear(); 473 G.add(H); 474 } 475 pool.allIdle(); 476 return; 477 } 478 if (debug) { 479 logger.debug("H = " + H); 480 } 481 synchronized (G) { 482 G.add(H); 483 } 484 pairlist.put(H); 485 } 486 logger.info("terminated, done " + reduction + " reductions"); 487 } 488} 489 490 491/** 492 * Reducing twosided worker threads. 493 * @param <C> coefficient type 494 */ 495class TwosidedSolvableReducer<C extends RingElem<C>> implements Runnable { 496 497 498 private final List<GenSolvablePolynomial<C>> X; 499 500 501 private final List<GenSolvablePolynomial<C>> G; 502 503 504 private final PairList<C> pairlist; 505 506 507 private final Terminator pool; 508 509 510 private final SolvableReductionPar<C> sred; 511 512 513 private static final Logger logger = Logger.getLogger(TwosidedSolvableReducer.class); 514 515 516 private static final boolean debug = logger.isDebugEnabled(); 517 518 519 TwosidedSolvableReducer(Terminator fin, List<GenSolvablePolynomial<C>> X, 520 List<GenSolvablePolynomial<C>> G, PairList<C> L) { 521 pool = fin; 522 this.X = X; 523 this.G = G; 524 pairlist = L; 525 sred = new SolvableReductionPar<C>(); 526 } 527 528 529 public void run() { 530 GenSolvablePolynomial<C> p, x; 531 Pair<C> pair; 532 GenSolvablePolynomial<C> S; 533 GenSolvablePolynomial<C> H; 534 boolean set = false; 535 int reduction = 0; 536 int sleeps = 0; 537 while (pairlist.hasNext() || pool.hasJobs()) { 538 while (!pairlist.hasNext()) { 539 // wait 540 pool.beIdle(); 541 set = true; 542 try { 543 sleeps++; 544 if (sleeps % 10 == 0) { 545 logger.info(" reducer is sleeping"); 546 } else { 547 logger.debug("r"); 548 } 549 Thread.sleep(50); 550 } catch (InterruptedException e) { 551 break; 552 } 553 if (!pool.hasJobs()) { 554 break; 555 } 556 } 557 if (!pairlist.hasNext() && !pool.hasJobs()) { 558 break; 559 } 560 if (set) { 561 pool.notIdle(); 562 set = false; 563 } 564 pair = pairlist.removeNext(); 565 if (pair == null) { 566 continue; 567 } 568 if (debug) { 569 logger.debug("pi = " + pair.pi); 570 logger.debug("pj = " + pair.pj); 571 } 572 S = sred.leftSPolynomial((GenSolvablePolynomial<C>) pair.pi, (GenSolvablePolynomial<C>) pair.pj); 573 if (S.isZERO()) { 574 continue; 575 } 576 if (debug) { 577 logger.debug("ht(S) = " + S.leadingExpVector()); 578 } 579 H = sred.leftNormalform(G, S); //mod 580 reduction++; 581 if (H.isZERO()) { 582 continue; 583 } 584 if (debug) { 585 logger.debug("ht(H) = " + H.leadingExpVector()); 586 } 587 H = (GenSolvablePolynomial<C>) H.monic(); 588 // System.out.println("H = " + H); 589 if (H.isONE()) { 590 pairlist.putOne(); // not really required 591 synchronized (G) { 592 G.clear(); 593 G.add(H); 594 } 595 pool.allIdle(); 596 return; 597 } 598 if (debug) { 599 logger.debug("H = " + H); 600 } 601 synchronized (G) { 602 G.add(H); 603 } 604 pairlist.put(H); 605 for (int j = 0; j < X.size(); j++) { 606 x = X.get(j); 607 p = H.multiply(x); 608 p = sred.leftNormalform(G, p); 609 if (!p.isZERO()) { 610 p = (GenSolvablePolynomial<C>) p.monic(); 611 if (p.isONE()) { 612 synchronized (G) { 613 G.clear(); 614 G.add(p); 615 } 616 pool.allIdle(); 617 return; 618 } 619 synchronized (G) { 620 G.add(p); 621 } 622 pairlist.put(p); 623 } 624 } 625 } 626 logger.info("terminated, done " + reduction + " reductions"); 627 } 628} 629 630 631/** 632 * Reducing worker threads for minimal GB. 633 * @param <C> coefficient type 634 */ 635class SolvableMiReducer<C extends RingElem<C>> implements Runnable { 636 637 638 private final List<GenSolvablePolynomial<C>> G; 639 640 641 private GenSolvablePolynomial<C> H; 642 643 644 private final SolvableReductionPar<C> sred; 645 646 647 private final Semaphore done = new Semaphore(0); 648 649 650 private static final Logger logger = Logger.getLogger(SolvableMiReducer.class); 651 652 653 private static final boolean debug = logger.isDebugEnabled(); 654 655 656 SolvableMiReducer(List<GenSolvablePolynomial<C>> G, GenSolvablePolynomial<C> p) { 657 this.G = G; 658 H = p; 659 sred = new SolvableReductionPar<C>(); 660 } 661 662 663 /** 664 * getNF. Blocks until the normal form is computed. 665 * @return the computed normal form. 666 */ 667 public GenSolvablePolynomial<C> getNF() { 668 try { 669 done.acquire(); //done.P(); 670 } catch (InterruptedException e) { 671 } 672 return H; 673 } 674 675 676 public void run() { 677 if (debug) { 678 logger.debug("ht(H) = " + H.leadingExpVector()); 679 } 680 H = sred.leftNormalform(G, H); //mod 681 done.release(); //done.V(); 682 if (debug) { 683 logger.debug("ht(H) = " + H.leadingExpVector()); 684 } 685 // H = H.monic(); 686 } 687 688}