001/* 002 * $Id: GroebnerBaseSeqPairParallel.java 4059 2012-07-27 11:16:42Z 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 MiReducerSeqPair<C>[] mirs = (MiReducerSeqPair<C>[]) new MiReducerSeqPair[G.size()]; 246 int i = 0; 247 F = new ArrayList<GenPolynomial<C>>(G.size()); 248 while (G.size() > 0) { 249 a = G.remove(0); 250 // System.out.println("doing " + a.length()); 251 List<GenPolynomial<C>> R = new ArrayList<GenPolynomial<C>>(G.size() + F.size()); 252 R.addAll(G); 253 R.addAll(F); 254 mirs[i] = new MiReducerSeqPair<C>(R, a); 255 pool.addJob(mirs[i]); 256 i++; 257 F.add(a); 258 } 259 G = F; 260 F = new ArrayList<GenPolynomial<C>>(G.size()); 261 for (i = 0; i < mirs.length; i++) { 262 a = mirs[i].getNF(); 263 F.add(a); 264 } 265 return F; 266 } 267 268} 269 270 271/** 272 * Reducing worker threads. 273 */ 274class ReducerSeqPair<C extends RingElem<C>> implements Runnable { 275 276 277 private final List<GenPolynomial<C>> G; 278 279 280 private final CriticalPairList<C> pairlist; 281 282 283 private final Terminator fin; 284 285 286 private final ReductionPar<C> red; 287 288 289 private static final Logger logger = Logger.getLogger(ReducerSeqPair.class); 290 291 292 ReducerSeqPair(Terminator fin, List<GenPolynomial<C>> G, CriticalPairList<C> L) { 293 this.fin = fin; 294 this.G = G; 295 pairlist = L; 296 red = new ReductionPar<C>(); 297 } 298 299 300 /** 301 * to string 302 */ 303 @Override 304 public String toString() { 305 return "ReducerSeqPair"; 306 } 307 308 309 public void run() { 310 CriticalPair<C> pair; 311 GenPolynomial<C> S; 312 GenPolynomial<C> H; 313 boolean set = false; 314 int reduction = 0; 315 int sleeps = 0; 316 while (pairlist.hasNext() || fin.hasJobs()) { 317 while (!pairlist.hasNext()) { 318 pairlist.update(); 319 // wait 320 fin.beIdle(); 321 set = true; 322 try { 323 sleeps++; 324 if (sleeps % 10 == 0) { 325 logger.info(" reducer is sleeping"); 326 } else { 327 logger.debug("r"); 328 } 329 Thread.sleep(100); 330 } catch (InterruptedException e) { 331 break; 332 } 333 if (!fin.hasJobs()) { 334 break; 335 } 336 if (Thread.currentThread().isInterrupted()) { 337 throw new RuntimeException("interrupt after sleep"); 338 } 339 } 340 if (!pairlist.hasNext() && !fin.hasJobs()) { 341 break; 342 } 343 if (set) { 344 fin.notIdle(); 345 set = false; 346 } 347 pair = pairlist.getNext(); 348 if (Thread.currentThread().isInterrupted()) { 349 throw new RuntimeException("interrupt after getNext"); 350 } 351 if (pair == null) { 352 pairlist.update(); 353 continue; 354 } 355 if (logger.isDebugEnabled()) { 356 logger.debug("pi = " + pair.pi); 357 logger.debug("pj = " + pair.pj); 358 } 359 S = red.SPolynomial(pair.pi, pair.pj); 360 if (S.isZERO()) { 361 pairlist.record(pair, S); 362 continue; 363 } 364 if (logger.isDebugEnabled()) { 365 logger.debug("ht(S) = " + S.leadingExpVector()); 366 } 367 H = red.normalform(G, S); //mod 368 reduction++; 369 if (H.isZERO()) { 370 pairlist.record(pair, H); 371 continue; 372 } 373 if (logger.isDebugEnabled()) { 374 logger.debug("ht(H) = " + H.leadingExpVector()); 375 } 376 H = H.monic(); 377 // System.out.println("H = " + H); 378 if (H.isONE()) { 379 // pairlist.update( pair, H ); 380 pairlist.putOne(); // not really required 381 synchronized (G) { 382 G.clear(); 383 G.add(H); 384 } 385 fin.allIdle(); 386 return; 387 } 388 if (logger.isDebugEnabled()) { 389 logger.debug("H = " + H); 390 } 391 synchronized (G) { 392 G.add(H); 393 } 394 pairlist.update(pair, H); 395 //pairlist.record( pair, H ); 396 //pairlist.update(); 397 } 398 logger.info("terminated, done " + reduction + " reductions"); 399 } 400} 401 402 403/** 404 * Reducing worker threads for minimal GB. 405 */ 406class MiReducerSeqPair<C extends RingElem<C>> implements Runnable { 407 408 409 private final List<GenPolynomial<C>> G; 410 411 412 private GenPolynomial<C> H; 413 414 415 private final ReductionPar<C> red; 416 417 418 private final Semaphore done = new Semaphore(0); 419 420 421 private static final Logger logger = Logger.getLogger(MiReducerSeqPair.class); 422 423 424 MiReducerSeqPair(List<GenPolynomial<C>> G, GenPolynomial<C> p) { 425 this.G = G; 426 H = p; 427 red = new ReductionPar<C>(); 428 } 429 430 431 /** 432 * to string 433 */ 434 @Override 435 public String toString() { 436 return "MiReducerSeqpair"; 437 } 438 439 440 /** 441 * getNF. Blocks until the normal form is computed. 442 * @return the computed normal form. 443 */ 444 public GenPolynomial<C> getNF() { 445 try { 446 done.acquire(); //done.P(); 447 } catch (InterruptedException e) { 448 throw new RuntimeException("interrupt in getNF"); 449 } 450 return H; 451 } 452 453 454 public void run() { 455 if (logger.isDebugEnabled()) { 456 logger.debug("ht(H) = " + H.leadingExpVector()); 457 } 458 try { 459 H = red.normalform(G, H); //mod 460 done.release(); //done.V(); 461 } catch (RuntimeException e) { 462 Thread.currentThread().interrupt(); 463 //throw new RuntimeException("interrupt in getNF"); 464 } 465 if (logger.isDebugEnabled()) { 466 logger.debug("ht(H) = " + H.leadingExpVector()); 467 } 468 // H = H.monic(); 469 } 470 471}