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