Source code

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