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