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