001/* 002 * $Id: GroebnerBaseDistributed.java 5245 2015-05-01 14:03:06Z kredel $ 003 */ 004 005package edu.jas.gb; 006 007 008import java.io.IOException; 009import java.util.ArrayList; 010import java.util.Collections; 011import java.util.List; 012import java.util.ListIterator; 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.ChannelFactory; 020import edu.jas.util.DistHashTable; 021import edu.jas.util.DistHashTableServer; 022import edu.jas.util.SocketChannel; 023import edu.jas.util.Terminator; 024import edu.jas.util.ThreadPool; 025 026 027/** 028 * Groebner Base distributed algorithm. Implements a distributed memory parallel 029 * version of Groebner bases. Using pairlist class, distributed tasks do 030 * reduction, one communication channel per task. 031 * @param <C> coefficient type 032 * @author Heinz Kredel 033 * @deprecated use GroebnerBaseDistributedEC 034 */ 035 036@Deprecated 037public class GroebnerBaseDistributed<C extends RingElem<C>> extends GroebnerBaseAbstract<C> { 038 039 040 private static final Logger logger = Logger.getLogger(GroebnerBaseDistributed.class); 041 042 043 /** 044 * Number of threads to use. 045 */ 046 protected final int threads; 047 048 049 /** 050 * Default number of threads. 051 */ 052 protected static final int DEFAULT_THREADS = 2; 053 054 055 /** 056 * Pool of threads to use. <b>Note:</b> No ComputerThreads for one node 057 * tests 058 */ 059 protected transient final ThreadPool pool; 060 061 062 /** 063 * Default server port. 064 */ 065 protected static final int DEFAULT_PORT = 4711; 066 067 068 /** 069 * Server port to use. 070 */ 071 protected final int port; 072 073 074 /** 075 * Constructor. 076 */ 077 public GroebnerBaseDistributed() { 078 this(DEFAULT_THREADS, DEFAULT_PORT); 079 } 080 081 082 /** 083 * Constructor. 084 * @param threads number of threads to use. 085 */ 086 public GroebnerBaseDistributed(int threads) { 087 this(threads, new ThreadPool(threads), DEFAULT_PORT); 088 } 089 090 091 /** 092 * Constructor. 093 * @param threads number of threads to use. 094 * @param port server port to use. 095 */ 096 public GroebnerBaseDistributed(int threads, int port) { 097 this(threads, new ThreadPool(threads), port); 098 } 099 100 101 /** 102 * Constructor. 103 * @param threads number of threads to use. 104 * @param pool ThreadPool to use. 105 * @param port server port to use. 106 */ 107 public GroebnerBaseDistributed(int threads, ThreadPool pool, int port) { 108 this(threads, pool, new OrderedPairlist<C>(), port); 109 } 110 111 112 /** 113 * Constructor. 114 * @param threads number of threads to use. 115 * @param pl pair selection strategy 116 * @param port server port to use. 117 */ 118 public GroebnerBaseDistributed(int threads, PairList<C> pl, int port) { 119 this(threads, new ThreadPool(threads), pl, port); 120 } 121 122 123 /** 124 * Constructor. 125 * @param threads number of threads to use. 126 * @param pool ThreadPool to use. 127 * @param pl pair selection strategy 128 * @param port server port to use. 129 */ 130 public GroebnerBaseDistributed(int threads, ThreadPool pool, PairList<C> pl, int port) { 131 super(new ReductionPar<C>(), pl); 132 if (threads < 1) { 133 threads = 1; 134 } 135 this.threads = threads; 136 this.pool = pool; 137 this.port = port; 138 } 139 140 141 /** 142 * Cleanup and terminate ThreadPool. 143 */ 144 @Override 145 public void terminate() { 146 if (pool == null) { 147 return; 148 } 149 pool.terminate(); 150 } 151 152 153 /** 154 * Distributed Groebner base. 155 * @param modv number of module variables. 156 * @param F polynomial list. 157 * @return GB(F) a Groebner base of F or null, if a IOException occurs. 158 */ 159 public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> F) { 160 161 final int DL_PORT = port + 100; 162 ChannelFactory cf = new ChannelFactory(port); 163 cf.init(); 164 DistHashTableServer<Integer> dls = new DistHashTableServer<Integer>(DL_PORT); 165 dls.init(); 166 logger.debug("dist-list server running"); 167 168 GenPolynomial<C> p; 169 List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>(); 170 PairList<C> pairlist = null; 171 boolean oneInGB = false; 172 //int l = F.size(); 173 @SuppressWarnings("unused") 174 int unused; 175 ListIterator<GenPolynomial<C>> it = F.listIterator(); 176 while (it.hasNext()) { 177 p = it.next(); 178 if (p.length() > 0) { 179 p = p.monic(); 180 if (p.isONE()) { 181 oneInGB = true; 182 G.clear(); 183 G.add(p); 184 //return G; must signal termination to others 185 } 186 if (!oneInGB) { 187 G.add(p); 188 } 189 if (pairlist == null) { 190 //pairlist = new OrderedPairlist<C>(modv, p.ring); 191 pairlist = strategy.create(modv, p.ring); 192 if (!p.ring.coFac.isField()) { 193 throw new IllegalArgumentException("coefficients not from a field"); 194 } 195 } 196 // theList not updated here 197 if (p.isONE()) { 198 unused = pairlist.putOne(); 199 } else { 200 unused = pairlist.put(p); 201 } 202 } else { 203 //l--; 204 } 205 } 206 //if (l <= 1) { 207 //return G; must signal termination to others 208 //} 209 210 logger.debug("looking for clients"); 211 //long t = System.currentTimeMillis(); 212 // now in DL, uses resend for late clients 213 //while ( dls.size() < threads ) { sleep(); } 214 215 DistHashTable<Integer, GenPolynomial<C>> theList = new DistHashTable<Integer, GenPolynomial<C>>( 216 "localhost", DL_PORT); 217 theList.init(); 218 List<GenPolynomial<C>> al = pairlist.getList(); 219 for (int i = 0; i < al.size(); i++) { 220 // no wait required 221 GenPolynomial<C> nn = theList.put(Integer.valueOf(i), al.get(i)); 222 if (nn != null) { 223 logger.info("double polynomials " + i + ", nn = " + nn + ", al(i) = " + al.get(i)); 224 } 225 } 226 227 Terminator fin = new Terminator(threads); 228 ReducerServer<C> R; 229 for (int i = 0; i < threads; i++) { 230 R = new ReducerServer<C>(fin, cf, theList, G, pairlist); 231 pool.addJob(R); 232 } 233 logger.debug("main loop waiting"); 234 fin.waitDone(); 235 int ps = theList.size(); 236 logger.debug("#distributed list = " + ps); 237 // make sure all polynomials arrived: not needed in master 238 // G = (ArrayList)theList.values(); 239 G = pairlist.getList(); 240 if (ps != G.size()) { 241 logger.info("#distributed list = " + theList.size() + " #pairlist list = " + G.size()); 242 } 243 long time = System.currentTimeMillis(); 244 List<GenPolynomial<C>> Gp; 245 Gp = minimalGB(G); // not jet distributed but threaded 246 time = System.currentTimeMillis() - time; 247 logger.info("parallel gbmi = " + time); 248 /* 249 time = System.currentTimeMillis(); 250 G = GroebnerBase.<C>GBmi(G); // sequential 251 time = System.currentTimeMillis() - time; 252 logger.info("sequential gbmi = " + time); 253 */ 254 G = Gp; 255 logger.debug("cf.terminate()"); 256 cf.terminate(); 257 // no more required // pool.terminate(); 258 logger.info("theList.terminate()"); 259 theList.terminate(); 260 logger.info("dls.terminate()"); 261 dls.terminate(); 262 logger.info("" + pairlist); 263 return G; 264 } 265 266 267 /** 268 * GB distributed client. 269 * @param host the server runns on. 270 * @throws IOException 271 */ 272 public void clientPart(String host) throws IOException { 273 274 ChannelFactory cf = new ChannelFactory(port + 10); // != port for localhost 275 cf.init(); 276 SocketChannel pairChannel = cf.getChannel(host, port); 277 278 final int DL_PORT = port + 100; 279 DistHashTable<Integer, GenPolynomial<C>> theList = new DistHashTable<Integer, GenPolynomial<C>>(host, 280 DL_PORT); 281 theList.init(); 282 283 ReducerClient<C> R = new ReducerClient<C>(pairChannel, theList); 284 R.run(); 285 286 pairChannel.close(); 287 theList.terminate(); 288 cf.terminate(); 289 return; 290 } 291 292 293 /** 294 * Minimal ordered groebner basis. 295 * @param Fp a Groebner base. 296 * @return a reduced Groebner base of Fp. 297 */ 298 @SuppressWarnings("cast") 299 @Override 300 public List<GenPolynomial<C>> minimalGB(List<GenPolynomial<C>> Fp) { 301 GenPolynomial<C> a; 302 ArrayList<GenPolynomial<C>> G; 303 G = new ArrayList<GenPolynomial<C>>(Fp.size()); 304 ListIterator<GenPolynomial<C>> it = Fp.listIterator(); 305 while (it.hasNext()) { 306 a = it.next(); 307 if (a.length() != 0) { // always true 308 // already monic a = a.monic(); 309 G.add(a); 310 } 311 } 312 if (G.size() <= 1) { 313 return G; 314 } 315 316 ExpVector e; 317 ExpVector f; 318 GenPolynomial<C> p; 319 ArrayList<GenPolynomial<C>> F; 320 F = new ArrayList<GenPolynomial<C>>(G.size()); 321 boolean mt; 322 323 while (G.size() > 0) { 324 a = G.remove(0); 325 e = a.leadingExpVector(); 326 327 it = G.listIterator(); 328 mt = false; 329 while (it.hasNext() && !mt) { 330 p = it.next(); 331 f = p.leadingExpVector(); 332 mt = e.multipleOf(f); 333 } 334 it = F.listIterator(); 335 while (it.hasNext() && !mt) { 336 p = it.next(); 337 f = p.leadingExpVector(); 338 mt = e.multipleOf(f); 339 } 340 if (!mt) { 341 F.add(a); 342 } else { 343 // System.out.println("dropped " + a.length()); 344 } 345 } 346 G = F; 347 if (G.size() <= 1) { 348 return G; 349 } 350 Collections.reverse(G); // important for lex GB 351 352 MiReducerServer<C>[] mirs = (MiReducerServer<C>[]) new MiReducerServer[G.size()]; 353 int i = 0; 354 F = new ArrayList<GenPolynomial<C>>(G.size()); 355 while (G.size() > 0) { 356 a = G.remove(0); 357 // System.out.println("doing " + a.length()); 358 List<GenPolynomial<C>> R = new ArrayList<GenPolynomial<C>>(G.size() + F.size()); 359 R.addAll(G); 360 R.addAll(F); 361 mirs[i] = new MiReducerServer<C>(R, a); 362 pool.addJob(mirs[i]); 363 i++; 364 F.add(a); 365 } 366 G = F; 367 F = new ArrayList<GenPolynomial<C>>(G.size()); 368 for (i = 0; i < mirs.length; i++) { 369 a = mirs[i].getNF(); 370 F.add(a); 371 } 372 return F; 373 } 374 375} 376 377 378/** 379 * Distributed server reducing worker threads. 380 * @param <C> coefficient type 381 */ 382 383class ReducerServer<C extends RingElem<C>> implements Runnable { 384 385 386 private final Terminator pool; 387 388 389 private final ChannelFactory cf; 390 391 392 private SocketChannel pairChannel; 393 394 395 private final DistHashTable<Integer, GenPolynomial<C>> theList; 396 397 398 //private List<GenPolynomial<C>> G; 399 private final PairList<C> pairlist; 400 401 402 private static final Logger logger = Logger.getLogger(ReducerServer.class); 403 404 405 ReducerServer(Terminator fin, ChannelFactory cf, DistHashTable<Integer, GenPolynomial<C>> dl, 406 List<GenPolynomial<C>> G, PairList<C> L) { 407 pool = fin; 408 this.cf = cf; 409 theList = dl; 410 //this.G = G; 411 pairlist = L; 412 } 413 414 415 public void run() { 416 logger.debug("reducer server running"); 417 try { 418 pairChannel = cf.getChannel(); 419 } catch (InterruptedException e) { 420 logger.debug("get pair channel interrupted"); 421 e.printStackTrace(); 422 return; 423 } 424 if (logger.isDebugEnabled()) { 425 logger.debug("pairChannel = " + pairChannel); 426 } 427 Pair<C> pair; 428 //GenPolynomial<C> pi; 429 //GenPolynomial<C> pj; 430 //GenPolynomial<C> S; 431 GenPolynomial<C> H = null; 432 boolean set = false; 433 boolean goon = true; 434 int polIndex = -1; 435 int red = 0; 436 int sleeps = 0; 437 438 // while more requests 439 while (goon) { 440 // receive request 441 logger.debug("receive request"); 442 Object req = null; 443 try { 444 req = pairChannel.receive(); 445 } catch (IOException e) { 446 goon = false; 447 e.printStackTrace(); 448 } catch (ClassNotFoundException e) { 449 goon = false; 450 e.printStackTrace(); 451 } 452 //logger.debug("received request, req = " + req); 453 if (req == null) { 454 goon = false; 455 break; 456 } 457 if (!(req instanceof GBTransportMessReq)) { 458 goon = false; 459 break; 460 } 461 462 // find pair 463 logger.debug("find pair"); 464 while (!pairlist.hasNext()) { // wait 465 if (!set) { 466 pool.beIdle(); 467 set = true; 468 } 469 if (!pool.hasJobs() && !pairlist.hasNext()) { 470 goon = false; 471 break; 472 } 473 try { 474 sleeps++; 475 if (sleeps % 10 == 0) { 476 logger.info(" reducer is sleeping"); 477 } 478 Thread.sleep(100); 479 } catch (InterruptedException e) { 480 goon = false; 481 break; 482 } 483 } 484 if (!pairlist.hasNext() && !pool.hasJobs()) { 485 goon = false; 486 break; //continue; //break? 487 } 488 if (set) { 489 set = false; 490 pool.notIdle(); 491 } 492 493 pair = pairlist.removeNext(); 494 /* 495 * send pair to client, receive H 496 */ 497 logger.debug("send pair = " + pair); 498 GBTransportMess msg = null; 499 if (pair != null) { 500 msg = new GBTransportMessPairIndex(pair); 501 } else { 502 msg = new GBTransportMess(); //End(); 503 // goon ?= false; 504 } 505 try { 506 pairChannel.send(msg); 507 } catch (IOException e) { 508 e.printStackTrace(); 509 goon = false; 510 break; 511 } 512 logger.debug("#distributed list = " + theList.size()); 513 Object rh = null; 514 try { 515 rh = pairChannel.receive(); 516 } catch (IOException e) { 517 e.printStackTrace(); 518 goon = false; 519 break; 520 } catch (ClassNotFoundException e) { 521 e.printStackTrace(); 522 goon = false; 523 break; 524 } 525 //logger.debug("received H polynomial"); 526 if (rh == null) { 527 if (pair != null) { 528 pair.setZero(); 529 } 530 } else if (rh instanceof GBTransportMessPoly) { 531 // update pair list 532 red++; 533 H = ((GBTransportMessPoly<C>) rh).pol; 534 if (logger.isDebugEnabled()) { 535 logger.debug("H = " + H); 536 } 537 if (H == null) { 538 if (pair != null) { 539 pair.setZero(); 540 } 541 } else { 542 if (H.isZERO()) { 543 pair.setZero(); 544 } else { 545 if (H.isONE()) { 546 // pool.allIdle(); 547 polIndex = pairlist.putOne(); 548 GenPolynomial<C> nn = theList.put(Integer.valueOf(polIndex), H); 549 if (nn != null) { 550 logger.info("double polynomials nn = " + nn + ", H = " + H); 551 } 552 goon = false; 553 break; 554 } 555 polIndex = pairlist.put(H); 556 // use putWait ? but still not all distributed 557 GenPolynomial<C> nn = theList.put(Integer.valueOf(polIndex), H); 558 if (nn != null) { 559 logger.info("double polynomials nn = " + nn + ", H = " + H); 560 } 561 } 562 } 563 } 564 } 565 logger.info("terminated, done " + red + " reductions"); 566 567 /* 568 * send end mark to client 569 */ 570 logger.debug("send end"); 571 try { 572 pairChannel.send(new GBTransportMessEnd()); 573 } catch (IOException e) { 574 if (logger.isDebugEnabled()) { 575 e.printStackTrace(); 576 } 577 } 578 pool.beIdle(); 579 pairChannel.close(); 580 } 581 582} 583 584 585/** 586 * Distributed clients reducing worker threads. 587 */ 588 589class ReducerClient<C extends RingElem<C>> implements Runnable { 590 591 592 private final SocketChannel pairChannel; 593 594 595 private final DistHashTable<Integer, GenPolynomial<C>> theList; 596 597 598 private final ReductionPar<C> red; 599 600 601 private static final Logger logger = Logger.getLogger(ReducerClient.class); 602 603 604 ReducerClient(SocketChannel pc, DistHashTable<Integer, GenPolynomial<C>> dl) { 605 pairChannel = pc; 606 theList = dl; 607 red = new ReductionPar<C>(); 608 } 609 610 611 public void run() { 612 logger.debug("pairChannel = " + pairChannel + " reducer client running"); 613 Pair<C> pair = null; 614 GenPolynomial<C> pi; 615 GenPolynomial<C> pj; 616 GenPolynomial<C> S; 617 GenPolynomial<C> H = null; 618 //boolean set = false; 619 boolean goon = true; 620 int reduction = 0; 621 //int sleeps = 0; 622 Integer pix; 623 Integer pjx; 624 625 while (goon) { 626 /* protocol: 627 * request pair, process pair, send result 628 */ 629 // pair = (Pair) pairlist.removeNext(); 630 Object req = new GBTransportMessReq(); 631 logger.debug("send request = " + req); 632 try { 633 pairChannel.send(req); 634 } catch (IOException e) { 635 goon = false; 636 e.printStackTrace(); 637 break; 638 } 639 logger.debug("receive pair, goon = " + goon); 640 Object pp = null; 641 try { 642 pp = pairChannel.receive(); 643 } catch (IOException e) { 644 goon = false; 645 if (logger.isDebugEnabled()) { 646 e.printStackTrace(); 647 } 648 break; 649 } catch (ClassNotFoundException e) { 650 goon = false; 651 e.printStackTrace(); 652 } 653 if (logger.isDebugEnabled()) { 654 logger.debug("received pair = " + pp); 655 } 656 H = null; 657 if (pp == null) { // should not happen 658 continue; 659 } 660 if (pp instanceof GBTransportMessEnd) { 661 goon = false; 662 continue; 663 } 664 if (pp instanceof GBTransportMessPair || pp instanceof GBTransportMessPairIndex) { 665 pi = pj = null; 666 if (pp instanceof GBTransportMessPair) { 667 pair = ((GBTransportMessPair<C>) pp).pair; 668 if (pair != null) { 669 pi = pair.pi; 670 pj = pair.pj; 671 //logger.debug("pair: pix = " + pair.i 672 // + ", pjx = " + pair.j); 673 } 674 } 675 if (pp instanceof GBTransportMessPairIndex) { 676 pix = ((GBTransportMessPairIndex) pp).i; 677 pjx = ((GBTransportMessPairIndex) pp).j; 678 pi = theList.getWait(pix); 679 pj = theList.getWait(pjx); 680 //logger.info("pix = " + pix + ", pjx = " +pjx); 681 } 682 683 if (pi != null && pj != null) { 684 S = red.SPolynomial(pi, pj); 685 //System.out.println("S = " + S); 686 if (S.isZERO()) { 687 // pair.setZero(); does not work in dist 688 } else { 689 if (logger.isDebugEnabled()) { 690 logger.debug("ht(S) = " + S.leadingExpVector()); 691 } 692 H = red.normalform(theList, S); 693 reduction++; 694 if (H.isZERO()) { 695 // pair.setZero(); does not work in dist 696 } else { 697 H = H.monic(); 698 if (logger.isInfoEnabled()) { 699 logger.info("ht(H) = " + H.leadingExpVector()); 700 } 701 } 702 } 703 } 704 } 705 706 // send H or must send null 707 if (logger.isDebugEnabled()) { 708 logger.debug("#distributed list = " + theList.size()); 709 logger.debug("send H polynomial = " + H); 710 } 711 try { 712 pairChannel.send(new GBTransportMessPoly<C>(H)); 713 } catch (IOException e) { 714 goon = false; 715 e.printStackTrace(); 716 } 717 } 718 logger.info("terminated, done " + reduction + " reductions"); 719 pairChannel.close(); 720 } 721}