001/*
002 * $Id$
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;
015import java.util.concurrent.Executors;
016import java.util.concurrent.ExecutorService;
017import java.util.concurrent.ThreadPoolExecutor;
018import java.util.concurrent.TimeUnit;
019
020import org.apache.logging.log4j.Logger;
021import org.apache.logging.log4j.LogManager; 
022
023import edu.jas.poly.ExpVector;
024import edu.jas.poly.GenPolynomial;
025import edu.jas.structure.RingElem;
026import edu.jas.util.ChannelFactory;
027import edu.jas.util.DistHashTable;
028import edu.jas.util.DistHashTableServer;
029import edu.jas.util.SocketChannel;
030import edu.jas.util.Terminator;
031
032
033/**
034 * Groebner Base distributed algorithm. Implements a distributed memory parallel
035 * version of Groebner bases. Using pairlist class, distributed tasks do
036 * reduction. Makes some effort to produce the same sequence of critical pairs
037 * as in the sequential version. However already reduced pairs are not rereduced
038 * if new polynomials appear.
039 * @param <C> coefficient type
040 * @author Heinz Kredel
041 * @deprecated no direct alternative 
042 * @see edu.jas.gb.GroebnerBaseDistributedEC
043 * @see edu.jas.gb.GroebnerBaseDistributedHybridEC
044 */
045@Deprecated
046public class GroebnerBaseSeqPairDistributed<C extends RingElem<C>> extends GroebnerBaseAbstract<C> {
047
048
049    private static final Logger logger = LogManager.getLogger(GroebnerBaseSeqPairDistributed.class);
050
051
052    /**
053     * Number of threads to use.
054     */
055    protected final int threads;
056
057
058    /**
059     * Default number of threads.
060     */
061    protected static final int DEFAULT_THREADS = 2;
062
063
064    /**
065     * Pool of threads to use.
066     */
067    protected transient final ExecutorService pool;
068
069
070    /**
071     * Default server port.
072     */
073    protected static final int DEFAULT_PORT = 4711;
074
075
076    /**
077     * Server port to use.
078     */
079    protected final int port;
080
081
082    /**
083     * Constructor.
084     */
085    public GroebnerBaseSeqPairDistributed() {
086        this(DEFAULT_THREADS, DEFAULT_PORT);
087    }
088
089
090    /**
091     * Constructor.
092     * @param threads number of threads to use.
093     */
094    public GroebnerBaseSeqPairDistributed(int threads) {
095        this(threads, Executors.newFixedThreadPool(threads), DEFAULT_PORT);
096    }
097
098
099    /**
100     * Constructor.
101     * @param threads number of threads to use.
102     * @param red parallelism aware reduction engine
103     */
104    public GroebnerBaseSeqPairDistributed(int threads, Reduction<C> red) {
105        this(threads, Executors.newFixedThreadPool(threads), DEFAULT_PORT, red);
106    }
107
108
109    /**
110     * Constructor.
111     * @param threads number of threads to use.
112     * @param port server port to use.
113     * @param red parallelism aware reduction engine
114     */
115    public GroebnerBaseSeqPairDistributed(int threads, int port, Reduction<C> red) {
116        this(threads, Executors.newFixedThreadPool(threads), port, red);
117    }
118
119
120    /**
121     * Constructor.
122     * @param threads number of threads to use.
123     * @param port server port to use.
124     */
125    public GroebnerBaseSeqPairDistributed(int threads, int port) {
126        this(threads, Executors.newFixedThreadPool(threads), port);
127    }
128
129
130    /**
131     * Constructor.
132     * @param threads number of threads to use.
133     * @param pool ExecutorService to use.
134     * @param port server port to use.
135     */
136    public GroebnerBaseSeqPairDistributed(int threads, ExecutorService pool, int port) {
137        this(threads, pool, port, new ReductionPar<C>());
138    }
139
140
141    /**
142     * Constructor.
143     * @param threads number of threads to use.
144     * @param pool ExecutorService to use.
145     * @param port server port to use.
146     * @param red parallelism aware reduction engine
147     */
148    public GroebnerBaseSeqPairDistributed(int threads, ExecutorService pool, int port, Reduction<C> red) {
149        super(red);
150        if (!(red instanceof ReductionPar)) {
151            logger.warn("parallel GB should use parallel aware reduction");
152        }
153        if (threads < 1) {
154            threads = 1;
155        }
156        this.threads = threads;
157        this.pool = pool;
158        this.port = port;
159    }
160
161
162    /**
163     * Cleanup and terminate ExecutorService.
164     */
165    @Override
166    public void terminate() {
167        if (pool == null) {
168            return;
169        }
170        pool.shutdown();
171        try {
172            while (!pool.isTerminated()) {
173                //logger.info("await");
174                boolean rest = pool.awaitTermination(1000L, TimeUnit.MILLISECONDS);
175            }
176        } catch (InterruptedException e) {
177            e.printStackTrace();
178        }
179    }
180
181
182    /**
183     * Distributed Groebner base. Slaves maintain pairlist.
184     * @param modv number of module variables.
185     * @param F polynomial list.
186     * @return GB(F) a Groebner base of F or null, if a IOException occurs.
187     */
188    public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> F) {
189
190        final int DL_PORT = port + 100;
191        ChannelFactory cf = new ChannelFactory(port);
192        cf.init();
193        DistHashTableServer<Integer> dls = new DistHashTableServer<Integer>(DL_PORT);
194        dls.init();
195        logger.debug("dist-list server running");
196
197        GenPolynomial<C> p;
198        //List<GenPolynomial<C>> G = new ArrayList<GenPolynomial<C>>();
199        CriticalPairList<C> pairlist = null;
200        boolean oneInGB = false;
201        //int l = F.size();
202        @SuppressWarnings("unused")
203        int unused;
204        ListIterator<GenPolynomial<C>> it = F.listIterator();
205        while (it.hasNext()) {
206            p = it.next();
207            if (p.length() > 0) {
208                p = p.monic();
209                if (p.isONE()) {
210                    oneInGB = true;
211                    //G.clear();
212                    //G.add(p);
213                    //return G; must signal termination to others
214                }
215                //if (!oneInGB) {
216                //    //G.add(p);
217                //}
218                if (pairlist == null) {
219                    pairlist = new CriticalPairList<C>(modv, p.ring);
220                }
221                // theList not updated here
222                if (p.isONE()) {
223                    unused = pairlist.putOne();
224                } else {
225                    unused = pairlist.put(p);
226                }
227            } else {
228                //l--;
229            }
230        }
231        //if (l <= 1) {
232        //return G; must signal termination to others
233        //}
234
235        logger.debug("looking for clients");
236        //long t = System.currentTimeMillis();
237        // now in DL, uses resend for late clients
238        //while ( dls.size() < threads ) { sleep(); }
239
240        DistHashTable<Integer, GenPolynomial<C>> theList = new DistHashTable<Integer, GenPolynomial<C>>(
241                        "localhost", DL_PORT);
242        theList.init();
243        List<GenPolynomial<C>> G = pairlist.getList();
244        for (int i = 0; i < G.size(); i++) {
245            // no wait required
246            GenPolynomial<C> nn = theList.put(Integer.valueOf(i), G.get(i));
247            if (nn != null) {
248                logger.info("double polynomials {}, nn = {}, G(i) = {}", i, nn, G.get(i));
249            }
250        }
251
252        Terminator fin = new Terminator(threads);
253        ReducerServerSeqPair<C> R;
254        for (int i = 0; i < threads; i++) {
255            R = new ReducerServerSeqPair<C>(fin, cf, theList, pairlist);
256            pool.execute(R);
257        }
258        logger.debug("main loop waiting");
259        fin.waitDone();
260        int ps = theList.size();
261        //logger.debug("#distributed list = {}", ps);
262        // make sure all polynomials arrived: not needed in master
263        // G = (ArrayList)theList.values();
264        G = pairlist.getList();
265        //logger.debug("#pairlist list = {}", G.size());
266        if (ps != G.size()) {
267            logger.info("#distributed list = {} #pairlist list = {}", theList.size(), G.size());
268        }
269        long time = System.currentTimeMillis();
270        List<GenPolynomial<C>> Gp;
271        Gp = minimalGB(G); // not jet distributed but threaded
272        time = System.currentTimeMillis() - time;
273        logger.info("parallel gbmi = {}", time);
274        /*
275        time = System.currentTimeMillis();
276        G = GroebnerBase.<C>GBmi(G); // sequential
277        time = System.currentTimeMillis() - time;
278        logger.info("sequential gbmi = {}", time);
279        */
280        G = Gp;
281        //logger.info("cf.terminate()");
282        cf.terminate();
283        // no more required // pool.terminate();
284        logger.info("theList.terminate()");
285        theList.terminate();
286        logger.info("dls.terminate()");
287        dls.terminate();
288        logger.info("{}", pairlist);
289        return G;
290    }
291
292
293    /**
294     * GB distributed client.
295     * @param host the server runs on.
296     * @throws IOException
297     */
298    public void clientPart(String host) throws IOException {
299
300        ChannelFactory cf = new ChannelFactory(port + 10); // != port for localhost
301        cf.init();
302        SocketChannel pairChannel = cf.getChannel(host, port);
303
304        final int DL_PORT = port + 100;
305        DistHashTable<Integer, GenPolynomial<C>> theList = new DistHashTable<Integer, GenPolynomial<C>>(host,
306                        DL_PORT);
307        theList.init();
308
309        ReducerClientSeqPair<C> R = new ReducerClientSeqPair<C>(pairChannel, theList);
310        R.run();
311
312        pairChannel.close();
313        theList.terminate();
314        cf.terminate();
315        return;
316    }
317
318
319    /**
320     * Minimal ordered groebner basis.
321     * @param Fp a Groebner base.
322     * @return a reduced Groebner base of Fp.
323     */
324    @SuppressWarnings("unchecked")
325    @Override
326    public List<GenPolynomial<C>> minimalGB(List<GenPolynomial<C>> Fp) {
327        GenPolynomial<C> a;
328        ArrayList<GenPolynomial<C>> G;
329        G = new ArrayList<GenPolynomial<C>>(Fp.size());
330        ListIterator<GenPolynomial<C>> it = Fp.listIterator();
331        while (it.hasNext()) {
332            a = it.next();
333            if (a.length() != 0) { // always true
334                // already monic  a = a.monic();
335                G.add(a);
336            }
337        }
338        if (G.size() <= 1) {
339            return G;
340        }
341
342        ExpVector e;
343        ExpVector f;
344        GenPolynomial<C> p;
345        ArrayList<GenPolynomial<C>> F;
346        F = new ArrayList<GenPolynomial<C>>(G.size());
347        boolean mt;
348
349        while (G.size() > 0) {
350            a = G.remove(0);
351            e = a.leadingExpVector();
352
353            it = G.listIterator();
354            mt = false;
355            while (it.hasNext() && !mt) {
356                p = it.next();
357                f = p.leadingExpVector();
358                mt = e.multipleOf(f);
359            }
360            it = F.listIterator();
361            while (it.hasNext() && !mt) {
362                p = it.next();
363                f = p.leadingExpVector();
364                mt = e.multipleOf(f);
365            }
366            if (!mt) {
367                F.add(a);
368            } else {
369                // System.out.println("dropped " + a.length());
370            }
371        }
372        G = F;
373        if (G.size() <= 1) {
374            return G;
375        }
376        Collections.reverse(G); // important for lex GB
377
378        MiReducerServerSeqPair<C>[] mirs = (MiReducerServerSeqPair<C>[]) new MiReducerServerSeqPair[G.size()];
379        int i = 0;
380        F = new ArrayList<GenPolynomial<C>>(G.size());
381        while (G.size() > 0) {
382            a = G.remove(0);
383            // System.out.println("doing " + a.length());
384            List<GenPolynomial<C>> R = new ArrayList<GenPolynomial<C>>(G.size() + F.size());
385            R.addAll(G);
386            R.addAll(F);
387            mirs[i] = new MiReducerServerSeqPair<C>(R, a);
388            pool.execute(mirs[i]);
389            i++;
390            F.add(a);
391        }
392        G = F;
393        F = new ArrayList<GenPolynomial<C>>(G.size());
394        for (i = 0; i < mirs.length; i++) {
395            a = mirs[i].getNF();
396            F.add(a);
397        }
398        return F;
399    }
400
401}
402
403
404/**
405 * Distributed server reducing worker threads.
406 * @param <C> coefficient type
407 */
408
409class ReducerServerSeqPair<C extends RingElem<C>> implements Runnable {
410
411
412    private final Terminator pool;
413
414
415    private final ChannelFactory cf;
416
417
418    private SocketChannel pairChannel;
419
420
421    private final DistHashTable<Integer, GenPolynomial<C>> theList;
422
423
424    //private List<GenPolynomial<C>> G;
425    private final CriticalPairList<C> pairlist;
426
427
428    private static final Logger logger = LogManager.getLogger(ReducerServerSeqPair.class);
429
430
431    ReducerServerSeqPair(Terminator fin, ChannelFactory cf, DistHashTable<Integer, GenPolynomial<C>> dl,
432                    CriticalPairList<C> L) {
433        pool = fin;
434        this.cf = cf;
435        theList = dl;
436        //this.G = G;
437        pairlist = L;
438    }
439
440
441    @SuppressWarnings("unchecked")
442    public void run() {
443        logger.debug("reducer server running");
444        try {
445            pairChannel = cf.getChannel();
446        } catch (InterruptedException e) {
447            logger.debug("get pair channel interrupted");
448            e.printStackTrace();
449            return;
450        }
451        if (logger.isDebugEnabled()) {
452            logger.debug("pairChannel = {}", pairChannel);
453        }
454        CriticalPair<C> pair;
455        //GenPolynomial<C> pi;
456        //GenPolynomial<C> pj;
457        //GenPolynomial<C> S;
458        GenPolynomial<C> H = null;
459        boolean set = false;
460        boolean goon = true;
461        int polIndex = -1;
462        int red = 0;
463        int sleeps = 0;
464
465        // while more requests
466        while (goon) {
467            // receive request
468            logger.debug("receive request");
469            Object req = null;
470            try {
471                req = pairChannel.receive();
472            } catch (IOException e) {
473                goon = false;
474                e.printStackTrace();
475            } catch (ClassNotFoundException e) {
476                goon = false;
477                e.printStackTrace();
478            }
479            //logger.debug("received request, req = {}", req);
480            if (req == null) {
481                goon = false;
482                break;
483            }
484            if (!(req instanceof GBSPTransportMessReq)) {
485                goon = false;
486                break;
487            }
488
489            // find pair
490            if (logger.isDebugEnabled()) {
491                logger.debug("find pair");
492                logger.debug("pool.hasJobs() {} pairlist.hasNext() {}", pool.hasJobs(), pairlist.hasNext());
493            }
494            while (!pairlist.hasNext()) { // wait
495                pairlist.update();
496                if (!set) {
497                    pool.beIdle();
498                    set = true;
499                }
500                if (!pool.hasJobs() && !pairlist.hasNext()) {
501                    goon = false;
502                    break;
503                }
504                try {
505                    sleeps++;
506                    if (sleeps % 10 == 0) {
507                        logger.info(" reducer is sleeping");
508                    }
509                    Thread.sleep(100);
510                } catch (InterruptedException e) {
511                    goon = false;
512                    break;
513                }
514            }
515            if (!pairlist.hasNext() && !pool.hasJobs()) {
516                goon = false;
517                break; //continue; //break?
518            }
519            if (set) {
520                set = false;
521                pool.notIdle();
522            }
523
524            pair = pairlist.getNext();
525            /*
526             * send pair to client, receive H
527             */
528            if (logger.isDebugEnabled()) {
529                logger.debug("send pair = {}", pair);
530                logger.info("theList keys {}", theList.keySet());
531            }
532            if (logger.isDebugEnabled()) {
533                logger.info("inWork {}", pairlist.inWork());
534            }
535            GBSPTransportMess msg = null;
536            if (pair != null) {
537                msg = new GBSPTransportMessPairIndex(pair);
538            } else {
539                msg = new GBSPTransportMess(); //End();
540                // goon ?= false;
541            }
542            try {
543                pairChannel.send(msg);
544            } catch (IOException e) {
545                e.printStackTrace();
546                goon = false;
547                break;
548            }
549            // use idle time to update pairlist
550            pairlist.update();
551            //logger.debug("#distributed list = {}", theList.size());
552            //logger.debug("receive H polynomial");
553            Object rh = null;
554            try {
555                rh = pairChannel.receive();
556            } catch (IOException e) {
557                e.printStackTrace();
558                goon = false;
559                break;
560            } catch (ClassNotFoundException e) {
561                e.printStackTrace();
562                goon = false;
563                break;
564            }
565            if (logger.isDebugEnabled()) {
566                logger.info("received H polynomial rh = {}", rh);
567            }
568            if (rh == null) {
569                if (pair != null) {
570                    polIndex = pairlist.record(pair, null);
571                    //pair.setZero();
572                }
573                pairlist.update();
574            } else if (rh instanceof GBSPTransportMessPoly) {
575                // update pair list
576                red++;
577                H = ((GBSPTransportMessPoly<C>) rh).pol;
578                //logger.info("H = {}", H);
579                if (H == null) {
580                    if (pair != null) {
581                        polIndex = pairlist.record(pair, null);
582                        //pair.setZero();
583                    }
584                    pairlist.update();
585                } else {
586                    if (H.isZERO()) {
587                        polIndex = pairlist.record(pair, H);
588                        //pair.setZero();
589                    } else {
590                        if (H.isONE()) {
591                            // pool.allIdle();
592                            pairlist.putOne();
593                            theList.put(Integer.valueOf(0), H);
594                            goon = false;
595                            //break;
596                        } else {
597                            polIndex = pairlist.record(pair, H);
598                            // not correct:
599                            // polIndex = pairlist.getList().size(); 
600                            // pairlist.update();
601                            // polIndex = pairlist.put( H );
602                            // use putWait ? but still not all distributed
603                            theList.put(Integer.valueOf(polIndex), H);
604                        }
605                    }
606                }
607            } else {
608                if (pair != null) {
609                    polIndex = pairlist.record(pair, null);
610                    //pair.setZero();
611                }
612                if (logger.isDebugEnabled()) {
613                    logger.debug("invalid message {}", rh);
614                }
615            }
616        }
617        logger.info("terminated, done {} reductions", red);
618
619        /*
620         * send end mark to client
621         */
622        logger.debug("send end");
623        try {
624            pairChannel.send(new GBSPTransportMessEnd());
625        } catch (IOException e) {
626            if (logger.isDebugEnabled()) {
627                e.printStackTrace();
628            }
629        }
630        pool.beIdle();
631        pairChannel.close();
632    }
633
634}
635
636
637/**
638 * Distributed GB transport message.
639 */
640
641class GBSPTransportMess implements Serializable {
642
643
644    /**
645     * toString.
646     */
647    @Override
648    public String toString() {
649        return "" + this.getClass().getName();
650    }
651}
652
653
654/**
655 * Distributed GB transport message for requests.
656 */
657
658class GBSPTransportMessReq extends GBSPTransportMess {
659
660
661    public GBSPTransportMessReq() {
662    }
663}
664
665
666/**
667 * Distributed GB transport message for termination.
668 */
669
670class GBSPTransportMessEnd extends GBSPTransportMess {
671
672
673    public GBSPTransportMessEnd() {
674    }
675}
676
677
678/**
679 * Distributed GB transport message for polynomial.
680 */
681
682class GBSPTransportMessPoly<C extends RingElem<C>> extends GBSPTransportMess {
683
684
685    /**
686     * The polynomial for transport.
687     */
688    public final GenPolynomial<C> pol;
689
690
691    /**
692     * GBSPTransportMessPoly.
693     * @param p polynomial to transferred.
694     */
695    public GBSPTransportMessPoly(GenPolynomial<C> p) {
696        this.pol = p;
697    }
698
699
700    /**
701     * toString.
702     */
703    @Override
704    public String toString() {
705        return super.toString() + "( " + pol + " )";
706    }
707}
708
709
710/**
711 * Distributed GB transport message for pairs.
712 */
713
714class GBSPTransportMessPair<C extends RingElem<C>> extends GBSPTransportMess {
715
716
717    public final CriticalPair<C> pair;
718
719
720    /**
721     * GBSPTransportMessPair.
722     * @param p pair for transfer.
723     */
724    public GBSPTransportMessPair(CriticalPair<C> p) {
725        this.pair = p;
726    }
727
728
729    /**
730     * toString.
731     */
732    @Override
733    public String toString() {
734        return super.toString() + "( " + pair + " )";
735    }
736}
737
738
739/**
740 * Distributed GB transport message for index pairs.
741 */
742
743class GBSPTransportMessPairIndex extends GBSPTransportMess {
744
745
746    public final Integer i;
747
748
749    public final Integer j;
750
751
752    /**
753     * GBSPTransportMessPairIndex.
754     * @param p pair for transport.
755     */
756    public GBSPTransportMessPairIndex(CriticalPair p) {
757        if (p == null) {
758            throw new NullPointerException("pair may not be null");
759        }
760        this.i = Integer.valueOf(p.i);
761        this.j = Integer.valueOf(p.j);
762    }
763
764
765    /**
766     * GBSPTransportMessPairIndex.
767     * @param i first index.
768     * @param j second index.
769     */
770    public GBSPTransportMessPairIndex(int i, int j) {
771        this.i = Integer.valueOf(i);
772        this.j = Integer.valueOf(j);
773    }
774
775
776    /**
777     * GBSPTransportMessPairIndex.
778     * @param i first index.
779     * @param j second index.
780     */
781    public GBSPTransportMessPairIndex(Integer i, Integer j) {
782        this.i = i;
783        this.j = j;
784    }
785
786
787    /**
788     * toString.
789     */
790    @Override
791    public String toString() {
792        return super.toString() + "( " + i + "," + j + " )";
793    }
794}
795
796
797/**
798 * Distributed clients reducing worker threads.
799 */
800
801class ReducerClientSeqPair<C extends RingElem<C>> implements Runnable {
802
803
804    private final SocketChannel pairChannel;
805
806
807    private final DistHashTable<Integer, GenPolynomial<C>> theList;
808
809
810    private final ReductionPar<C> red;
811
812
813    private static final Logger logger = LogManager.getLogger(ReducerClientSeqPair.class);
814
815
816    ReducerClientSeqPair(SocketChannel pc, DistHashTable<Integer, GenPolynomial<C>> dl) {
817        pairChannel = pc;
818        theList = dl;
819        red = new ReductionPar<C>();
820    }
821
822
823    @SuppressWarnings("unchecked")
824    public void run() {
825        if (logger.isDebugEnabled()) {
826            logger.debug("pairChannel = {} reducer client running", pairChannel);
827        }
828        CriticalPair<C> pair = null;
829        GenPolynomial<C> pi;
830        GenPolynomial<C> pj;
831        GenPolynomial<C> S;
832        GenPolynomial<C> H = null;
833        //boolean set = false;
834        boolean goon = true;
835        int reduction = 0;
836        //int sleeps = 0;
837        Integer pix;
838        Integer pjx;
839
840        while (goon) {
841            /* protocol:
842             * request pair, process pair, send result
843             */
844            // pair = (Pair) pairlist.removeNext();
845            Object req = new GBSPTransportMessReq();
846            if (logger.isDebugEnabled()) {
847                logger.debug("send request = {}", req);
848            }
849            try {
850                pairChannel.send(req);
851            } catch (IOException e) {
852                goon = false;
853                e.printStackTrace();
854                break;
855            }
856            if (logger.isDebugEnabled()) {
857                logger.debug("receive pair, goon = {}", goon);
858            }
859            Object pp = null;
860            try {
861                pp = pairChannel.receive();
862            } catch (IOException e) {
863                goon = false;
864                if (logger.isDebugEnabled()) {
865                    e.printStackTrace();
866                }
867                break;
868            } catch (ClassNotFoundException e) {
869                goon = false;
870                e.printStackTrace();
871            }
872            if (logger.isDebugEnabled()) {
873                logger.info("received pair = {}", pp);
874            }
875            H = null;
876            if (pp == null) { // should not happen
877                //logger.debug("received pair = {}", pp);
878                continue;
879            }
880            if (pp instanceof GBSPTransportMessEnd) {
881                goon = false;
882                continue;
883            }
884            if (pp instanceof GBSPTransportMessPair || pp instanceof GBSPTransportMessPairIndex) {
885                pi = pj = null;
886                if (pp instanceof GBSPTransportMessPair) {
887                    pair = ((GBSPTransportMessPair<C>) pp).pair;
888                    if (pair != null) {
889                        pi = pair.pi;
890                        pj = pair.pj;
891                        //logger.debug("pair: pix = {}", pair.i
892                        //               + ", pjx = {}", pair.j);
893                    }
894                }
895                if (pp instanceof GBSPTransportMessPairIndex) {
896                    pix = ((GBSPTransportMessPairIndex) pp).i;
897                    pjx = ((GBSPTransportMessPairIndex) pp).j;
898                    //logger.info("waiting for pix = {}", pix);
899                    pi = theList.getWait(pix);
900                    //logger.info("waiting for pjx = {}", pjx);
901                    pj = theList.getWait(pjx);
902                    //logger.info("pix = {}, pjx = {}", pix, pjx);
903                }
904
905                if (pi != null && pj != null) {
906                    if (logger.isDebugEnabled()) {
907                        logger.info("pi = {}, pj = {}", pi.leadingExpVector(), pj.leadingExpVector());
908                    }
909                    S = red.SPolynomial(pi, pj);
910                    //System.out.println("S   = {}", S);
911                    if (S.isZERO()) {
912                        // pair.setZero(); does not work in dist
913                        H = S;
914                    } else {
915                        if (logger.isDebugEnabled()) {
916                            logger.debug("ht(S) = {}", S.leadingExpVector());
917                        }
918                        H = red.normalform(theList, S);
919                        reduction++;
920                        if (H.isZERO()) {
921                            // pair.setZero(); does not work in dist
922                        } else {
923                            H = H.monic();
924                            if (logger.isDebugEnabled()) {
925                                logger.info("ht(H) = {}", H.leadingExpVector());
926                            }
927                        }
928                    }
929                }
930            } else {
931                if (logger.isDebugEnabled()) {
932                    logger.debug("invalid message = {}", pp);
933                }
934                try {
935                    Thread.sleep(100);
936                } catch (InterruptedException e) {
937                    e.printStackTrace();
938                }
939            }
940
941            // send H or must send null
942            //logger.debug("#distributed list = {}", theList.size());
943            if (logger.isDebugEnabled()) {
944                logger.info("send H polynomial = {}", H);
945            }
946            try {
947                pairChannel.send(new GBSPTransportMessPoly<C>(H));
948            } catch (IOException e) {
949                goon = false;
950                e.printStackTrace();
951                break;
952            }
953        }
954        logger.info("terminated, done {} reductions", reduction);
955        pairChannel.close();
956    }
957}
958
959
960/**
961 * Distributed server reducing worker threads for minimal GB Not jet distributed
962 * but threaded.
963 */
964
965class MiReducerServerSeqPair<C extends RingElem<C>> implements Runnable {
966
967
968    private final List<GenPolynomial<C>> G;
969
970
971    private GenPolynomial<C> H;
972
973
974    private final Semaphore done = new Semaphore(0);
975
976
977    private final Reduction<C> red;
978
979
980    private static final Logger logger = LogManager.getLogger(MiReducerServerSeqPair.class);
981
982
983    MiReducerServerSeqPair(List<GenPolynomial<C>> G, GenPolynomial<C> p) {
984        this.G = G;
985        H = p;
986        red = new ReductionPar<C>();
987    }
988
989
990    /**
991     * getNF. Blocks until the normal form is computed.
992     * @return the computed normal form.
993     */
994    public GenPolynomial<C> getNF() {
995        try {
996            done.acquire(); //done.P();
997        } catch (InterruptedException e) {
998        }
999        return H;
1000    }
1001
1002
1003    public void run() {
1004        if (logger.isDebugEnabled()) {
1005            logger.debug("ht(H) = {}", H.leadingExpVector());
1006        }
1007        H = red.normalform(G, H); //mod
1008        done.release(); //done.V();
1009        if (logger.isDebugEnabled()) {
1010            logger.debug("ht(H) = {}", H.leadingExpVector());
1011        }
1012        // H = H.monic();
1013    }
1014}
1015
1016
1017/**
1018 * Distributed clients reducing worker threads for minimal GB. Not jet used.
1019 */
1020
1021class MiReducerClientSeqPair<C extends RingElem<C>> implements Runnable {
1022
1023
1024    private final List<GenPolynomial<C>> G;
1025
1026
1027    private GenPolynomial<C> H;
1028
1029
1030    private final Reduction<C> red;
1031
1032
1033    private final Semaphore done = new Semaphore(0);
1034
1035
1036    private static final Logger logger = LogManager.getLogger(MiReducerClientSeqPair.class);
1037
1038
1039    MiReducerClientSeqPair(List<GenPolynomial<C>> G, GenPolynomial<C> p) {
1040        this.G = G;
1041        H = p;
1042        red = new ReductionPar<C>();
1043    }
1044
1045
1046    /**
1047     * getNF. Blocks until the normal form is computed.
1048     * @return the computed normal form.
1049     */
1050    public GenPolynomial<C> getNF() {
1051        try {
1052            done.acquire(); //done.P();
1053        } catch (InterruptedException u) {
1054            Thread.currentThread().interrupt();
1055        }
1056        return H;
1057    }
1058
1059
1060    public void run() {
1061        if (logger.isDebugEnabled()) {
1062            logger.debug("ht(H) = {}", H.leadingExpVector());
1063        }
1064        H = red.normalform(G, H); // mod
1065        done.release(); //done.V();
1066        if (logger.isDebugEnabled()) {
1067            logger.debug("ht(H) = {}", H.leadingExpVector());
1068        }
1069        // H = H.monic();
1070    }
1071}