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