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