001/* 002 * $Id: GroebnerBaseDistributed.java 4235 2012-10-03 21:17:59Z kredel $ 003 */ 004 005package edu.jas.gb; 006 007 008import java.io.IOException; 009import java.io.Serializable; 010import java.util.ArrayList; 011import java.util.Collections; 012import java.util.List; 013import java.util.ListIterator; 014import java.util.concurrent.Semaphore; 015 016import org.apache.log4j.Logger; 017 018import edu.jas.poly.ExpVector; 019import edu.jas.poly.GenPolynomial; 020import edu.jas.structure.RingElem; 021import edu.jas.util.ChannelFactory; 022import edu.jas.util.DistHashTable; 023import edu.jas.util.DistHashTableServer; 024import edu.jas.util.SocketChannel; 025import edu.jas.util.Terminator; 026import edu.jas.util.ThreadPool; 027 028 029/** 030 * Groebner Base distributed algorithm. Implements a distributed memory parallel 031 * version of Groebner bases. Using pairlist class, distributed tasks do 032 * reduction, one communication channel per task. 033 * @param <C> coefficient type 034 * @author Heinz Kredel 035 * @deprecated use GroebnerBaseDistributedEC 036 */ 037 038public class GroebnerBaseDistributed<C extends RingElem<C>> extends GroebnerBaseAbstract<C> { 039 040 041 private static final Logger logger = Logger.getLogger(GroebnerBaseDistributed.class); 042 043 044 /** 045 * Number of threads to use. 046 */ 047 protected final int threads; 048 049 050 /** 051 * Default number of threads. 052 */ 053 protected static final int DEFAULT_THREADS = 2; 054 055 056 /** 057 * Pool of threads to use. <b>Note:</b> No ComputerThreads for one node 058 * tests 059 */ 060 protected transient final ThreadPool pool; 061 062 063 /** 064 * Default server port. 065 */ 066 protected static final int DEFAULT_PORT = 4711; 067 068 069 /** 070 * Server port to use. 071 */ 072 protected final int port; 073 074 075 /** 076 * Constructor. 077 */ 078 public GroebnerBaseDistributed() { 079 this(DEFAULT_THREADS, DEFAULT_PORT); 080 } 081 082 083 /** 084 * Constructor. 085 * @param threads number of threads to use. 086 */ 087 public GroebnerBaseDistributed(int threads) { 088 this(threads, new ThreadPool(threads), DEFAULT_PORT); 089 } 090 091 092 /** 093 * Constructor. 094 * @param threads number of threads to use. 095 * @param port server port to use. 096 */ 097 public GroebnerBaseDistributed(int threads, int port) { 098 this(threads, new ThreadPool(threads), port); 099 } 100 101 102 /** 103 * Constructor. 104 * @param threads number of threads to use. 105 * @param pool ThreadPool to use. 106 * @param port server port to use. 107 */ 108 public GroebnerBaseDistributed(int threads, ThreadPool pool, int port) { 109 this(threads, pool, new OrderedPairlist<C>(), port); 110 } 111 112 113 /** 114 * Constructor. 115 * @param threads number of threads to use. 116 * @param pl pair selection strategy 117 * @param port server port to use. 118 */ 119 public GroebnerBaseDistributed(int threads, PairList<C> pl, int port) { 120 this(threads, new ThreadPool(threads), pl, port); 121 } 122 123 124 /** 125 * Constructor. 126 * @param threads number of threads to use. 127 * @param pool ThreadPool to use. 128 * @param pl pair selection strategy 129 * @param port server port to use. 130 */ 131 public GroebnerBaseDistributed(int threads, ThreadPool pool, PairList<C> pl, int port) { 132 super(new ReductionPar<C>(), pl); 133 if (threads < 1) { 134 threads = 1; 135 } 136 this.threads = threads; 137 this.pool = pool; 138 this.port = port; 139 } 140 141 142 /** 143 * Cleanup and terminate ThreadPool. 144 */ 145 @Override 146 public void terminate() { 147 if (pool == null) { 148 return; 149 } 150 pool.terminate(); 151 } 152 153 154 /** 155 * Distributed Groebner base. 156 * @param modv number of module variables. 157 * @param F polynomial list. 158 * @return GB(F) a Groebner base of F or null, if a IOException occurs. 159 */ 160 public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> F) { 161 162 final int DL_PORT = port + 100; 163 ChannelFactory cf = new ChannelFactory(port); 164 cf.init(); 165 DistHashTableServer<Integer> dls = new DistHashTableServer<Integer>(DL_PORT); 166 dls.init(); 167 logger.debug("dist-list server running"); 168 169 GenPolynomial<C> p; 170 List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>(); 171 PairList<C> pairlist = null; 172 boolean oneInGB = false; 173 int l = F.size(); 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 @Override 299 public List<GenPolynomial<C>> minimalGB(List<GenPolynomial<C>> Fp) { 300 GenPolynomial<C> a; 301 ArrayList<GenPolynomial<C>> G; 302 G = new ArrayList<GenPolynomial<C>>(Fp.size()); 303 ListIterator<GenPolynomial<C>> it = Fp.listIterator(); 304 while (it.hasNext()) { 305 a = it.next(); 306 if (a.length() != 0) { // always true 307 // already monic a = a.monic(); 308 G.add(a); 309 } 310 } 311 if (G.size() <= 1) { 312 return G; 313 } 314 315 ExpVector e; 316 ExpVector f; 317 GenPolynomial<C> p; 318 ArrayList<GenPolynomial<C>> F; 319 F = new ArrayList<GenPolynomial<C>>(G.size()); 320 boolean mt; 321 322 while (G.size() > 0) { 323 a = G.remove(0); 324 e = a.leadingExpVector(); 325 326 it = G.listIterator(); 327 mt = false; 328 while (it.hasNext() && !mt) { 329 p = it.next(); 330 f = p.leadingExpVector(); 331 mt = e.multipleOf(f); 332 } 333 it = F.listIterator(); 334 while (it.hasNext() && !mt) { 335 p = it.next(); 336 f = p.leadingExpVector(); 337 mt = e.multipleOf(f); 338 } 339 if (!mt) { 340 F.add(a); 341 } else { 342 // System.out.println("dropped " + a.length()); 343 } 344 } 345 G = F; 346 if (G.size() <= 1) { 347 return G; 348 } 349 Collections.reverse(G); // important for lex GB 350 351 MiReducerServer<C>[] mirs = (MiReducerServer<C>[]) new MiReducerServer[G.size()]; 352 int i = 0; 353 F = new ArrayList<GenPolynomial<C>>(G.size()); 354 while (G.size() > 0) { 355 a = G.remove(0); 356 // System.out.println("doing " + a.length()); 357 List<GenPolynomial<C>> R = new ArrayList<GenPolynomial<C>>(G.size() + F.size()); 358 R.addAll(G); 359 R.addAll(F); 360 mirs[i] = new MiReducerServer<C>(R, a); 361 pool.addJob(mirs[i]); 362 i++; 363 F.add(a); 364 } 365 G = F; 366 F = new ArrayList<GenPolynomial<C>>(G.size()); 367 for (i = 0; i < mirs.length; i++) { 368 a = mirs[i].getNF(); 369 F.add(a); 370 } 371 return F; 372 } 373 374} 375 376 377/** 378 * Distributed server reducing worker threads. 379 * @param <C> coefficient type 380 */ 381 382class ReducerServer<C extends RingElem<C>> implements Runnable { 383 384 385 private final Terminator pool; 386 387 388 private final ChannelFactory cf; 389 390 391 private SocketChannel pairChannel; 392 393 394 private final DistHashTable<Integer, GenPolynomial<C>> theList; 395 396 397 //private List<GenPolynomial<C>> G; 398 private final PairList<C> pairlist; 399 400 401 private static final Logger logger = Logger.getLogger(ReducerServer.class); 402 403 404 ReducerServer(Terminator fin, ChannelFactory cf, DistHashTable<Integer, GenPolynomial<C>> dl, 405 List<GenPolynomial<C>> G, PairList<C> L) { 406 pool = fin; 407 this.cf = cf; 408 theList = dl; 409 //this.G = G; 410 pairlist = L; 411 } 412 413 414 public void run() { 415 logger.debug("reducer server running"); 416 try { 417 pairChannel = cf.getChannel(); 418 } catch (InterruptedException e) { 419 logger.debug("get pair channel interrupted"); 420 e.printStackTrace(); 421 return; 422 } 423 if (logger.isDebugEnabled()) { 424 logger.debug("pairChannel = " + pairChannel); 425 } 426 Pair<C> pair; 427 //GenPolynomial<C> pi; 428 //GenPolynomial<C> pj; 429 //GenPolynomial<C> S; 430 GenPolynomial<C> H = null; 431 boolean set = false; 432 boolean goon = true; 433 int polIndex = -1; 434 int red = 0; 435 int sleeps = 0; 436 437 // while more requests 438 while (goon) { 439 // receive request 440 logger.debug("receive request"); 441 Object req = null; 442 try { 443 req = pairChannel.receive(); 444 } catch (IOException e) { 445 goon = false; 446 e.printStackTrace(); 447 } catch (ClassNotFoundException e) { 448 goon = false; 449 e.printStackTrace(); 450 } 451 //logger.debug("received request, req = " + req); 452 if (req == null) { 453 goon = false; 454 break; 455 } 456 if (!(req instanceof GBTransportMessReq)) { 457 goon = false; 458 break; 459 } 460 461 // find pair 462 logger.debug("find pair"); 463 while (!pairlist.hasNext()) { // wait 464 if (!set) { 465 pool.beIdle(); 466 set = true; 467 } 468 if (!pool.hasJobs() && !pairlist.hasNext()) { 469 goon = false; 470 break; 471 } 472 try { 473 sleeps++; 474 if (sleeps % 10 == 0) { 475 logger.info(" reducer is sleeping"); 476 } 477 Thread.sleep(100); 478 } catch (InterruptedException e) { 479 goon = false; 480 break; 481 } 482 } 483 if (!pairlist.hasNext() && !pool.hasJobs()) { 484 goon = false; 485 break; //continue; //break? 486 } 487 if (set) { 488 set = false; 489 pool.notIdle(); 490 } 491 492 pair = pairlist.removeNext(); 493 /* 494 * send pair to client, receive H 495 */ 496 logger.debug("send pair = " + pair); 497 GBTransportMess msg = null; 498 if (pair != null) { 499 msg = new GBTransportMessPairIndex(pair); 500 } else { 501 msg = new GBTransportMess(); //End(); 502 // goon ?= false; 503 } 504 try { 505 pairChannel.send(msg); 506 } catch (IOException e) { 507 e.printStackTrace(); 508 goon = false; 509 break; 510 } 511 logger.debug("#distributed list = " + theList.size()); 512 Object rh = null; 513 try { 514 rh = pairChannel.receive(); 515 } catch (IOException e) { 516 e.printStackTrace(); 517 goon = false; 518 break; 519 } catch (ClassNotFoundException e) { 520 e.printStackTrace(); 521 goon = false; 522 break; 523 } 524 //logger.debug("received H polynomial"); 525 if (rh == null) { 526 if (pair != null) { 527 pair.setZero(); 528 } 529 } else if (rh instanceof GBTransportMessPoly) { 530 // update pair list 531 red++; 532 H = ((GBTransportMessPoly<C>) rh).pol; 533 if (logger.isDebugEnabled()) { 534 logger.debug("H = " + H); 535 } 536 if (H == null) { 537 if (pair != null) { 538 pair.setZero(); 539 } 540 } else { 541 if (H.isZERO()) { 542 pair.setZero(); 543 } else { 544 if (H.isONE()) { 545 // pool.allIdle(); 546 polIndex = pairlist.putOne(); 547 GenPolynomial<C> nn = theList.put(Integer.valueOf(polIndex), H); 548 if (nn != null) { 549 logger.info("double polynomials nn = " + nn + ", H = " + H); 550 } 551 goon = false; 552 break; 553 } 554 polIndex = pairlist.put(H); 555 // use putWait ? but still not all distributed 556 GenPolynomial<C> nn = theList.put(Integer.valueOf(polIndex), H); 557 if (nn != null) { 558 logger.info("double polynomials nn = " + nn + ", H = " + H); 559 } 560 } 561 } 562 } 563 } 564 logger.info("terminated, done " + red + " reductions"); 565 566 /* 567 * send end mark to client 568 */ 569 logger.debug("send end"); 570 try { 571 pairChannel.send(new GBTransportMessEnd()); 572 } catch (IOException e) { 573 if (logger.isDebugEnabled()) { 574 e.printStackTrace(); 575 } 576 } 577 pool.beIdle(); 578 pairChannel.close(); 579 } 580 581} 582 583 584/** 585 * Distributed clients reducing worker threads. 586 */ 587 588class ReducerClient<C extends RingElem<C>> implements Runnable { 589 590 591 private final SocketChannel pairChannel; 592 593 594 private final DistHashTable<Integer, GenPolynomial<C>> theList; 595 596 597 private final ReductionPar<C> red; 598 599 600 private static final Logger logger = Logger.getLogger(ReducerClient.class); 601 602 603 ReducerClient(SocketChannel pc, DistHashTable<Integer, GenPolynomial<C>> dl) { 604 pairChannel = pc; 605 theList = dl; 606 red = new ReductionPar<C>(); 607 } 608 609 610 public void run() { 611 logger.debug("pairChannel = " + pairChannel + " reducer client running"); 612 Pair<C> pair = null; 613 GenPolynomial<C> pi; 614 GenPolynomial<C> pj; 615 GenPolynomial<C> S; 616 GenPolynomial<C> H = null; 617 //boolean set = false; 618 boolean goon = true; 619 int reduction = 0; 620 //int sleeps = 0; 621 Integer pix; 622 Integer pjx; 623 624 while (goon) { 625 /* protocol: 626 * request pair, process pair, send result 627 */ 628 // pair = (Pair) pairlist.removeNext(); 629 Object req = new GBTransportMessReq(); 630 logger.debug("send request = " + req); 631 try { 632 pairChannel.send(req); 633 } catch (IOException e) { 634 goon = false; 635 e.printStackTrace(); 636 break; 637 } 638 logger.debug("receive pair, goon = " + goon); 639 Object pp = null; 640 try { 641 pp = pairChannel.receive(); 642 } catch (IOException e) { 643 goon = false; 644 if (logger.isDebugEnabled()) { 645 e.printStackTrace(); 646 } 647 break; 648 } catch (ClassNotFoundException e) { 649 goon = false; 650 e.printStackTrace(); 651 } 652 if (logger.isDebugEnabled()) { 653 logger.debug("received pair = " + pp); 654 } 655 H = null; 656 if (pp == null) { // should not happen 657 continue; 658 } 659 if (pp instanceof GBTransportMessEnd) { 660 goon = false; 661 continue; 662 } 663 if (pp instanceof GBTransportMessPair || pp instanceof GBTransportMessPairIndex) { 664 pi = pj = null; 665 if (pp instanceof GBTransportMessPair) { 666 pair = ((GBTransportMessPair<C>) pp).pair; 667 if (pair != null) { 668 pi = pair.pi; 669 pj = pair.pj; 670 //logger.debug("pair: pix = " + pair.i 671 // + ", pjx = " + pair.j); 672 } 673 } 674 if (pp instanceof GBTransportMessPairIndex) { 675 pix = ((GBTransportMessPairIndex) pp).i; 676 pjx = ((GBTransportMessPairIndex) pp).j; 677 pi = (GenPolynomial<C>) theList.getWait(pix); 678 pj = (GenPolynomial<C>) theList.getWait(pjx); 679 //logger.info("pix = " + pix + ", pjx = " +pjx); 680 } 681 682 if (pi != null && pj != null) { 683 S = red.SPolynomial(pi, pj); 684 //System.out.println("S = " + S); 685 if (S.isZERO()) { 686 // pair.setZero(); does not work in dist 687 } else { 688 if (logger.isDebugEnabled()) { 689 logger.debug("ht(S) = " + S.leadingExpVector()); 690 } 691 H = red.normalform(theList, S); 692 reduction++; 693 if (H.isZERO()) { 694 // pair.setZero(); does not work in dist 695 } else { 696 H = H.monic(); 697 if (logger.isInfoEnabled()) { 698 logger.info("ht(H) = " + H.leadingExpVector()); 699 } 700 } 701 } 702 } 703 } 704 705 // send H or must send null 706 if (logger.isDebugEnabled()) { 707 logger.debug("#distributed list = " + theList.size()); 708 logger.debug("send H polynomial = " + H); 709 } 710 try { 711 pairChannel.send(new GBTransportMessPoly<C>(H)); 712 } catch (IOException e) { 713 goon = false; 714 e.printStackTrace(); 715 } 716 } 717 logger.info("terminated, done " + reduction + " reductions"); 718 pairChannel.close(); 719 } 720} 721 722 723/** 724 * Distributed server reducing worker threads for minimal GB Not jet distributed 725 * but threaded. 726 */ 727 728class MiReducerServer<C extends RingElem<C>> implements Runnable { 729 730 731 private final List<GenPolynomial<C>> G; 732 733 734 private GenPolynomial<C> H; 735 736 737 private final Semaphore done = new Semaphore(0); 738 739 740 private final Reduction<C> red; 741 742 743 private static final Logger logger = Logger.getLogger(MiReducerServer.class); 744 745 746 MiReducerServer(List<GenPolynomial<C>> G, GenPolynomial<C> p) { 747 this.G = G; 748 H = p; 749 red = new ReductionPar<C>(); 750 } 751 752 753 /** 754 * getNF. Blocks until the normal form is computed. 755 * @return the computed normal form. 756 */ 757 public GenPolynomial<C> getNF() { 758 try { 759 done.acquire(); //done.P(); 760 } catch (InterruptedException e) { 761 } 762 return H; 763 } 764 765 766 public void run() { 767 if (logger.isDebugEnabled()) { 768 logger.debug("ht(H) = " + H.leadingExpVector()); 769 } 770 H = red.normalform(G, H); //mod 771 done.release(); //done.V(); 772 if (logger.isDebugEnabled()) { 773 logger.debug("ht(H) = " + H.leadingExpVector()); 774 } 775 // H = H.monic(); 776 } 777} 778 779 780/** 781 * Distributed clients reducing worker threads for minimal GB. Not jet used. 782 */ 783 784class MiReducerClient<C extends RingElem<C>> implements Runnable { 785 786 787 private final List<GenPolynomial<C>> G; 788 789 790 private GenPolynomial<C> H; 791 792 793 private final Reduction<C> red; 794 795 796 private final Semaphore done = new Semaphore(0); 797 798 799 private static final Logger logger = Logger.getLogger(MiReducerClient.class); 800 801 802 MiReducerClient(List<GenPolynomial<C>> G, GenPolynomial<C> p) { 803 this.G = G; 804 H = p; 805 red = new ReductionPar<C>(); 806 } 807 808 809 /** 810 * getNF. Blocks until the normal form is computed. 811 * @return the computed normal form. 812 */ 813 public GenPolynomial<C> getNF() { 814 try { 815 done.acquire(); //done.P(); 816 } catch (InterruptedException u) { 817 Thread.currentThread().interrupt(); 818 } 819 return H; 820 } 821 822 823 public void run() { 824 if (logger.isDebugEnabled()) { 825 logger.debug("ht(S) = " + H.leadingExpVector()); 826 } 827 H = red.normalform(G, H); //mod 828 done.release(); //done.V(); 829 if (logger.isDebugEnabled()) { 830 logger.debug("ht(H) = " + H.leadingExpVector()); 831 } 832 // H = H.monic(); 833 } 834}