001/*
002 * $Id: GroebnerBaseParallel.java 5360 2015-12-25 15:33:20Z kredel $
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;
013
014import org.apache.log4j.Logger;
015
016import edu.jas.poly.ExpVector;
017import edu.jas.poly.GenPolynomial;
018import edu.jas.poly.GenPolynomialRing;
019import edu.jas.poly.PolyUtil;
020import edu.jas.structure.RingElem;
021import edu.jas.util.Terminator;
022import edu.jas.util.ThreadPool;
023
024
025/**
026 * Groebner Base parallel algortihm. Implements a shared memory parallel version
027 * of Groebner bases.
028 * @param <C> coefficient type
029 * @author Heinz Kredel
030 * 
031 * @see edu.jas.application.GBAlgorithmBuilder
032 * @see edu.jas.gbufd.GBFactory
033 */
034
035public class GroebnerBaseParallel<C extends RingElem<C>> extends GroebnerBaseAbstract<C> {
036
037
038    private static final Logger logger = Logger.getLogger(GroebnerBaseParallel.class);
039
040
041    /**
042     * Number of threads to use.
043     */
044    protected final int threads;
045
046
047    /**
048     * Pool of threads to use.
049     */
050    protected transient final ThreadPool pool;
051
052
053    /**
054     * Constructor.
055     */
056    public GroebnerBaseParallel() {
057        this(2);
058    }
059
060
061    /**
062     * Constructor.
063     * @param threads number of threads to use.
064     */
065    public GroebnerBaseParallel(int threads) {
066        this(threads, new ThreadPool(threads));
067    }
068
069
070    /**
071     * Constructor.
072     * @param threads number of threads to use.
073     * @param red parallelism aware reduction engine
074     */
075    public GroebnerBaseParallel(int threads, Reduction<C> red) {
076        this(threads, new ThreadPool(threads), red);
077    }
078
079
080    /**
081     * Constructor.
082     * @param threads number of threads to use.
083     * @param pl pair selection strategy
084     */
085    public GroebnerBaseParallel(int threads, PairList<C> pl) {
086        this(threads, new ThreadPool(threads), new ReductionPar<C>(), pl);
087    }
088
089
090    /**
091     * Constructor.
092     * @param threads number of threads to use.
093     * @param pool ThreadPool to use.
094     */
095    public GroebnerBaseParallel(int threads, ThreadPool pool) {
096        this(threads, pool, new ReductionPar<C>());
097    }
098
099
100    /**
101     * Constructor.
102     * @param pool ThreadPool to use.
103     * @param red Reduction engine
104     */
105    public GroebnerBaseParallel(int threads, ThreadPool pool, Reduction<C> red) {
106        this(threads, pool, red, new OrderedPairlist<C>());
107    }
108
109
110    /**
111     * Constructor.
112     * @param red Reduction engine
113     * @param pl pair selection strategy
114     */
115    public GroebnerBaseParallel(int threads, Reduction<C> red, PairList<C> pl) {
116        this(threads, new ThreadPool(threads), red, pl);
117    }
118
119
120    /**
121     * Constructor.
122     * @param threads number of threads to use.
123     * @param pool ThreadPool to use.
124     * @param red parallelism aware reduction engine
125     * @param pl pair selection strategy
126     */
127    public GroebnerBaseParallel(int threads, ThreadPool pool, Reduction<C> red, PairList<C> pl) {
128        super(red, pl);
129        if (!(red instanceof ReductionPar)) {
130            logger.warn("parallel GB should use parallel aware reduction");
131        }
132        if (threads < 1) {
133            threads = 1;
134        }
135        this.threads = threads;
136        this.pool = pool;
137    }
138
139
140    /**
141     * Cleanup and terminate ThreadPool.
142     */
143    @Override
144    public void terminate() {
145        if (pool == null) {
146            return;
147        }
148        pool.terminate();
149    }
150
151
152    /**
153     * Cancel ThreadPool.
154     */
155    @Override
156    public int cancel() {
157        if (pool == null) {
158            return 0;
159        }
160        int s = pool.cancel();
161        return s;
162    }
163
164
165    /**
166     * Parallel Groebner base using pairlist class.
167     * @param modv number of module variables.
168     * @param F polynomial list.
169     * @return GB(F) a Groebner base of F.
170     */
171    public List<GenPolynomial<C>> GB(int modv, List<GenPolynomial<C>> F) {
172        List<GenPolynomial<C>> G = normalizeZerosOnes(F);
173        G = PolyUtil.<C> monic(G);
174        if (G.size() <= 1) {
175            return G;
176        }
177        GenPolynomialRing<C> ring = G.get(0).ring;
178        if (!ring.coFac.isField()) {
179            throw new IllegalArgumentException("coefficients not from a field");
180        }
181        PairList<C> pairlist = strategy.create(modv, ring);
182        pairlist.put(G);
183        logger.info("start " + pairlist);
184
185        Terminator fin = new Terminator(threads);
186        for (int i = 0; i < threads; i++) {
187            Reducer<C> R = new Reducer<C>(fin, G, pairlist);
188            pool.addJob(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("end   " + 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("cast")
260        MiReducer<C>[] mirs = (MiReducer<C>[]) new MiReducer[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            List<GenPolynomial<C>> R = new ArrayList<GenPolynomial<C>>(G.size() + F.size());
266            R.addAll(G);
267            R.addAll(F);
268            // System.out.println("doing " + a.length());
269            mirs[i] = new MiReducer<C>(R, a);
270            pool.addJob(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 Reducer<C extends RingElem<C>> implements Runnable {
290
291
292    private final List<GenPolynomial<C>> G;
293
294
295    private final PairList<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 = Logger.getLogger(Reducer.class);
305
306
307    Reducer(Terminator fin, List<GenPolynomial<C>> G, PairList<C> L) {
308        this.fin = fin;
309        this.fin.initIdle(1);
310        this.G = G;
311        pairlist = L;
312        red = new ReductionPar<C>();
313    }
314
315
316    /**
317     * to string
318     */
319    @Override
320    public String toString() {
321        return "Reducer";
322    }
323
324
325    public void run() {
326        Pair<C> pair;
327        GenPolynomial<C> pi, pj, S, H;
328        //boolean set = false;
329        int reduction = 0;
330        int sleeps = 0;
331        while (pairlist.hasNext() || fin.hasJobs()) {
332            while (!pairlist.hasNext()) {
333                // wait
334                //fin.beIdle(); set = true;
335                try {
336                    sleeps++;
337                    if (sleeps % 10 == 0) {
338                        logger.info(" reducer is sleeping");
339                    } else {
340                        logger.debug("r");
341                    }
342                    Thread.sleep(100);
343                } catch (InterruptedException e) {
344                    fin.allIdle();
345                    logger.info("shutdown " + fin + " after: " + e);
346                    //throw new RuntimeException("interrupt 1 in pairlist.hasNext loop");
347                    break;
348                }
349                if (Thread.currentThread().isInterrupted()) {
350                    //fin.initIdle(1);
351                    fin.allIdle();
352                    logger.info("shutdown after .isInterrupted(): " + fin);
353                    //throw new RuntimeException("interrupt 2 in pairlist.hasNext loop");
354                    break;
355                }
356                if (!fin.hasJobs()) {
357                    break;
358                }
359            }
360            if (!pairlist.hasNext() && !fin.hasJobs()) {
361                break;
362            }
363            //if ( set ) {
364            //fin.notIdle(); set = false;
365            //}
366
367            fin.notIdle(); // before pairlist get
368            pair = pairlist.removeNext();
369            if (Thread.currentThread().isInterrupted()) {
370                fin.initIdle(1);
371                throw new RuntimeException("interrupt after removeNext");
372            }
373            if (pair == null) {
374                fin.initIdle(1);
375                continue;
376            }
377
378            pi = pair.pi;
379            pj = pair.pj;
380            if (logger.isDebugEnabled()) {
381                logger.debug("pi    = " + pi);
382                logger.debug("pj    = " + pj);
383            }
384
385            S = red.SPolynomial(pi, pj);
386            if (S.isZERO()) {
387                pair.setZero();
388                fin.initIdle(1);
389                continue;
390            }
391            if (logger.isDebugEnabled()) {
392                logger.debug("ht(S) = " + S.leadingExpVector());
393            }
394
395            H = red.normalform(G, S); //mod
396            reduction++;
397            if (H.isZERO()) {
398                pair.setZero();
399                fin.initIdle(1);
400                continue;
401            }
402            if (logger.isDebugEnabled()) {
403                logger.info("ht(H) = " + H.leadingExpVector());
404            }
405
406            H = H.monic();
407            // System.out.println("H   = " + H);
408            if (H.isONE()) {
409                // putOne not required
410                pairlist.put(H);
411                synchronized (G) {
412                    G.clear();
413                    G.add(H);
414                }
415                fin.allIdle();
416                return;
417            }
418            if (logger.isDebugEnabled()) {
419                logger.debug("H = " + H);
420            }
421            synchronized (G) {
422                G.add(H);
423            }
424            pairlist.put(H);
425            fin.initIdle(1);
426        }
427        fin.allIdle();
428        logger.info("terminated, done " + reduction + " reductions");
429    }
430}
431
432
433/**
434 * Reducing worker threads for minimal GB.
435 */
436class MiReducer<C extends RingElem<C>> implements Runnable {
437
438
439    private final List<GenPolynomial<C>> G;
440
441
442    private GenPolynomial<C> H;
443
444
445    private final ReductionPar<C> red;
446
447
448    private final Semaphore done = new Semaphore(0);
449
450
451    private static final Logger logger = Logger.getLogger(MiReducer.class);
452
453
454    MiReducer(List<GenPolynomial<C>> G, GenPolynomial<C> p) {
455        this.G = G;
456        H = p;
457        red = new ReductionPar<C>();
458    }
459
460
461    /**
462     * to string
463     */
464    @Override
465    public String toString() {
466        return "MiReducer";
467    }
468
469
470    /**
471     * getNF. Blocks until the normal form is computed.
472     * @return the computed normal form.
473     */
474    public GenPolynomial<C> getNF() {
475        try {
476            done.acquire(); //done.P();
477        } catch (InterruptedException e) {
478            throw new RuntimeException("interrupt in getNF");
479        }
480        return H;
481    }
482
483
484    public void run() {
485        if (logger.isDebugEnabled()) {
486            logger.debug("ht(H) = " + H.leadingExpVector());
487        }
488        try {
489            H = red.normalform(G, H); //mod
490            done.release(); //done.V();
491        } catch (RuntimeException e) {
492            Thread.currentThread().interrupt();
493            //throw new RuntimeException("interrupt in getNF");
494        }
495        if (logger.isDebugEnabled()) {
496            logger.debug("ht(H) = " + H.leadingExpVector());
497        }
498        // H = H.monic();
499    }
500
501}