001/* 002 * $Id: GroebnerBaseParallel.java 5360 2015-12-25 15:33:20Z kredel $ 003 */ 004 005package edu.jas.gb; 006 007 008import java.util.ArrayList; 009import java.util.Collections; 010import java.util.List; 011import java.util.ListIterator; 012import java.util.concurrent.Semaphore; 013 014import org.apache.log4j.Logger; 015 016import edu.jas.poly.ExpVector; 017import edu.jas.poly.GenPolynomial; 018import edu.jas.poly.GenPolynomialRing; 019import edu.jas.poly.PolyUtil; 020import edu.jas.structure.RingElem; 021import edu.jas.util.Terminator; 022import edu.jas.util.ThreadPool; 023 024 025/** 026 * Groebner Base parallel algortihm. Implements a shared memory parallel version 027 * of Groebner bases. 028 * @param <C> coefficient type 029 * @author Heinz Kredel 030 * 031 * @see edu.jas.application.GBAlgorithmBuilder 032 * @see edu.jas.gbufd.GBFactory 033 */ 034 035public class GroebnerBaseParallel<C extends RingElem<C>> extends GroebnerBaseAbstract<C> { 036 037 038 private static final Logger logger = Logger.getLogger(GroebnerBaseParallel.class); 039 040 041 /** 042 * Number of threads to use. 043 */ 044 protected final int threads; 045 046 047 /** 048 * Pool of threads to use. 049 */ 050 protected transient final ThreadPool pool; 051 052 053 /** 054 * Constructor. 055 */ 056 public GroebnerBaseParallel() { 057 this(2); 058 } 059 060 061 /** 062 * Constructor. 063 * @param threads number of threads to use. 064 */ 065 public GroebnerBaseParallel(int threads) { 066 this(threads, new ThreadPool(threads)); 067 } 068 069 070 /** 071 * Constructor. 072 * @param threads number of threads to use. 073 * @param red parallelism aware reduction engine 074 */ 075 public GroebnerBaseParallel(int threads, Reduction<C> red) { 076 this(threads, new ThreadPool(threads), red); 077 } 078 079 080 /** 081 * Constructor. 082 * @param threads number of threads to use. 083 * @param pl pair selection strategy 084 */ 085 public GroebnerBaseParallel(int threads, PairList<C> pl) { 086 this(threads, new ThreadPool(threads), new ReductionPar<C>(), pl); 087 } 088 089 090 /** 091 * Constructor. 092 * @param threads number of threads to use. 093 * @param pool ThreadPool to use. 094 */ 095 public GroebnerBaseParallel(int threads, ThreadPool pool) { 096 this(threads, pool, new ReductionPar<C>()); 097 } 098 099 100 /** 101 * Constructor. 102 * @param pool ThreadPool to use. 103 * @param red Reduction engine 104 */ 105 public GroebnerBaseParallel(int threads, ThreadPool pool, Reduction<C> red) { 106 this(threads, pool, red, new OrderedPairlist<C>()); 107 } 108 109 110 /** 111 * Constructor. 112 * @param red Reduction engine 113 * @param pl pair selection strategy 114 */ 115 public GroebnerBaseParallel(int threads, Reduction<C> red, PairList<C> pl) { 116 this(threads, new ThreadPool(threads), red, pl); 117 } 118 119 120 /** 121 * Constructor. 122 * @param threads number of threads to use. 123 * @param pool ThreadPool to use. 124 * @param red parallelism aware reduction engine 125 * @param pl pair selection strategy 126 */ 127 public GroebnerBaseParallel(int threads, ThreadPool pool, Reduction<C> red, PairList<C> pl) { 128 super(red, pl); 129 if (!(red instanceof ReductionPar)) { 130 logger.warn("parallel GB should use parallel aware reduction"); 131 } 132 if (threads < 1) { 133 threads = 1; 134 } 135 this.threads = threads; 136 this.pool = pool; 137 } 138 139 140 /** 141 * Cleanup and terminate ThreadPool. 142 */ 143 @Override 144 public void terminate() { 145 if (pool == null) { 146 return; 147 } 148 pool.terminate(); 149 } 150 151 152 /** 153 * Cancel ThreadPool. 154 */ 155 @Override 156 public int cancel() { 157 if (pool == null) { 158 return 0; 159 } 160 int s = pool.cancel(); 161 return s; 162 } 163 164 165 /** 166 * Parallel Groebner base using pairlist class. 167 * @param modv number of module variables. 168 * @param F polynomial list. 169 * @return GB(F) a Groebner base of F. 170 */ 171 public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> F) { 172 List<GenPolynomial<C>> G = normalizeZerosOnes(F); 173 G = PolyUtil.<C> monic(G); 174 if (G.size() <= 1) { 175 return G; 176 } 177 GenPolynomialRing<C> ring = G.get(0).ring; 178 if (!ring.coFac.isField()) { 179 throw new IllegalArgumentException("coefficients not from a field"); 180 } 181 PairList<C> pairlist = strategy.create(modv, ring); 182 pairlist.put(G); 183 logger.info("start " + pairlist); 184 185 Terminator fin = new Terminator(threads); 186 for (int i = 0; i < threads; i++) { 187 Reducer<C> R = new Reducer<C>(fin, G, pairlist); 188 pool.addJob(R); 189 } 190 fin.waitDone(); 191 if (Thread.currentThread().isInterrupted()) { 192 throw new RuntimeException("interrupt before minimalGB"); 193 } 194 logger.debug("#parallel list = " + G.size()); 195 G = minimalGB(G); 196 // not in this context // pool.terminate(); 197 logger.info("end " + pairlist); 198 return G; 199 } 200 201 202 /** 203 * Minimal ordered groebner basis, parallel. 204 * @param Fp a Groebner base. 205 * @return minimalGB(F) a minimal Groebner base of Fp. 206 */ 207 @Override 208 public List<GenPolynomial<C>> minimalGB(List<GenPolynomial<C>> Fp) { 209 GenPolynomial<C> a; 210 ArrayList<GenPolynomial<C>> G; 211 G = new ArrayList<GenPolynomial<C>>(Fp.size()); 212 ListIterator<GenPolynomial<C>> it = Fp.listIterator(); 213 while (it.hasNext()) { 214 a = it.next(); 215 if (a.length() != 0) { // always true 216 // already monic a = a.monic(); 217 G.add(a); 218 } 219 } 220 if (G.size() <= 1) { 221 return G; 222 } 223 224 ExpVector e; 225 ExpVector f; 226 GenPolynomial<C> p; 227 ArrayList<GenPolynomial<C>> F; 228 F = new ArrayList<GenPolynomial<C>>(G.size()); 229 boolean mt; 230 while (G.size() > 0) { 231 a = G.remove(0); 232 e = a.leadingExpVector(); 233 234 it = G.listIterator(); 235 mt = false; 236 while (it.hasNext() && !mt) { 237 p = it.next(); 238 f = p.leadingExpVector(); 239 mt = e.multipleOf(f); 240 } 241 it = F.listIterator(); 242 while (it.hasNext() && !mt) { 243 p = it.next(); 244 f = p.leadingExpVector(); 245 mt = e.multipleOf(f); 246 } 247 if (!mt) { 248 F.add(a); // no thread at this point 249 } else { 250 // System.out.println("dropped " + a.length()); 251 } 252 } 253 G = F; 254 if (G.size() <= 1) { 255 return G; 256 } 257 Collections.reverse(G); // important for lex GB 258 259 @SuppressWarnings("cast") 260 MiReducer<C>[] mirs = (MiReducer<C>[]) new MiReducer[G.size()]; 261 int i = 0; 262 F = new ArrayList<GenPolynomial<C>>(G.size()); 263 while (G.size() > 0) { 264 a = G.remove(0); 265 List<GenPolynomial<C>> R = new ArrayList<GenPolynomial<C>>(G.size() + F.size()); 266 R.addAll(G); 267 R.addAll(F); 268 // System.out.println("doing " + a.length()); 269 mirs[i] = new MiReducer<C>(R, a); 270 pool.addJob(mirs[i]); 271 i++; 272 F.add(a); 273 } 274 G = F; 275 F = new ArrayList<GenPolynomial<C>>(G.size()); 276 for (i = 0; i < mirs.length; i++) { 277 a = mirs[i].getNF(); 278 F.add(a); 279 } 280 return F; 281 } 282 283} 284 285 286/** 287 * Reducing worker threads. 288 */ 289class Reducer<C extends RingElem<C>> implements Runnable { 290 291 292 private final List<GenPolynomial<C>> G; 293 294 295 private final PairList<C> pairlist; 296 297 298 private final Terminator fin; 299 300 301 private final ReductionPar<C> red; 302 303 304 private static final Logger logger = Logger.getLogger(Reducer.class); 305 306 307 Reducer(Terminator fin, List<GenPolynomial<C>> G, PairList<C> L) { 308 this.fin = fin; 309 this.fin.initIdle(1); 310 this.G = G; 311 pairlist = L; 312 red = new ReductionPar<C>(); 313 } 314 315 316 /** 317 * to string 318 */ 319 @Override 320 public String toString() { 321 return "Reducer"; 322 } 323 324 325 public void run() { 326 Pair<C> pair; 327 GenPolynomial<C> pi, pj, S, H; 328 //boolean set = false; 329 int reduction = 0; 330 int sleeps = 0; 331 while (pairlist.hasNext() || fin.hasJobs()) { 332 while (!pairlist.hasNext()) { 333 // wait 334 //fin.beIdle(); set = true; 335 try { 336 sleeps++; 337 if (sleeps % 10 == 0) { 338 logger.info(" reducer is sleeping"); 339 } else { 340 logger.debug("r"); 341 } 342 Thread.sleep(100); 343 } catch (InterruptedException e) { 344 fin.allIdle(); 345 logger.info("shutdown " + fin + " after: " + e); 346 //throw new RuntimeException("interrupt 1 in pairlist.hasNext loop"); 347 break; 348 } 349 if (Thread.currentThread().isInterrupted()) { 350 //fin.initIdle(1); 351 fin.allIdle(); 352 logger.info("shutdown after .isInterrupted(): " + fin); 353 //throw new RuntimeException("interrupt 2 in pairlist.hasNext loop"); 354 break; 355 } 356 if (!fin.hasJobs()) { 357 break; 358 } 359 } 360 if (!pairlist.hasNext() && !fin.hasJobs()) { 361 break; 362 } 363 //if ( set ) { 364 //fin.notIdle(); set = false; 365 //} 366 367 fin.notIdle(); // before pairlist get 368 pair = pairlist.removeNext(); 369 if (Thread.currentThread().isInterrupted()) { 370 fin.initIdle(1); 371 throw new RuntimeException("interrupt after removeNext"); 372 } 373 if (pair == null) { 374 fin.initIdle(1); 375 continue; 376 } 377 378 pi = pair.pi; 379 pj = pair.pj; 380 if (logger.isDebugEnabled()) { 381 logger.debug("pi = " + pi); 382 logger.debug("pj = " + pj); 383 } 384 385 S = red.SPolynomial(pi, pj); 386 if (S.isZERO()) { 387 pair.setZero(); 388 fin.initIdle(1); 389 continue; 390 } 391 if (logger.isDebugEnabled()) { 392 logger.debug("ht(S) = " + S.leadingExpVector()); 393 } 394 395 H = red.normalform(G, S); //mod 396 reduction++; 397 if (H.isZERO()) { 398 pair.setZero(); 399 fin.initIdle(1); 400 continue; 401 } 402 if (logger.isDebugEnabled()) { 403 logger.info("ht(H) = " + H.leadingExpVector()); 404 } 405 406 H = H.monic(); 407 // System.out.println("H = " + H); 408 if (H.isONE()) { 409 // putOne not required 410 pairlist.put(H); 411 synchronized (G) { 412 G.clear(); 413 G.add(H); 414 } 415 fin.allIdle(); 416 return; 417 } 418 if (logger.isDebugEnabled()) { 419 logger.debug("H = " + H); 420 } 421 synchronized (G) { 422 G.add(H); 423 } 424 pairlist.put(H); 425 fin.initIdle(1); 426 } 427 fin.allIdle(); 428 logger.info("terminated, done " + reduction + " reductions"); 429 } 430} 431 432 433/** 434 * Reducing worker threads for minimal GB. 435 */ 436class MiReducer<C extends RingElem<C>> implements Runnable { 437 438 439 private final List<GenPolynomial<C>> G; 440 441 442 private GenPolynomial<C> H; 443 444 445 private final ReductionPar<C> red; 446 447 448 private final Semaphore done = new Semaphore(0); 449 450 451 private static final Logger logger = Logger.getLogger(MiReducer.class); 452 453 454 MiReducer(List<GenPolynomial<C>> G, GenPolynomial<C> p) { 455 this.G = G; 456 H = p; 457 red = new ReductionPar<C>(); 458 } 459 460 461 /** 462 * to string 463 */ 464 @Override 465 public String toString() { 466 return "MiReducer"; 467 } 468 469 470 /** 471 * getNF. Blocks until the normal form is computed. 472 * @return the computed normal form. 473 */ 474 public GenPolynomial<C> getNF() { 475 try { 476 done.acquire(); //done.P(); 477 } catch (InterruptedException e) { 478 throw new RuntimeException("interrupt in getNF"); 479 } 480 return H; 481 } 482 483 484 public void run() { 485 if (logger.isDebugEnabled()) { 486 logger.debug("ht(H) = " + H.leadingExpVector()); 487 } 488 try { 489 H = red.normalform(G, H); //mod 490 done.release(); //done.V(); 491 } catch (RuntimeException e) { 492 Thread.currentThread().interrupt(); 493 //throw new RuntimeException("interrupt in getNF"); 494 } 495 if (logger.isDebugEnabled()) { 496 logger.debug("ht(H) = " + H.leadingExpVector()); 497 } 498 // H = H.monic(); 499 } 500 501}