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