Singular

A.1.8 Parallelization with ssi links

In this example, we demonstrate how ssi links can be used to parallelize computations.

To compute a standard basis for a zero-dimensional ideal in the lexicographical ordering, one of the two powerful routines stdhilb (see stdhilb) and stdfglm (see stdfglm) should be used. However, in general one cannot predict which one of the two commands is faster. This very much depends on the (input) example. Therefore, we use ssi links to let both commands work on the problem independently and in parallel, so that the one which finishes first delivers the result.

The example we use is the so-called "omndi example". See Tim Wichmann; Der FGLM-Algorithmus: verallgemeinert und implementiert in Singular; Diplomarbeit Fachbereich Mathematik, Universitaet Kaiserslautern; 1997 for more details.

ring r=0,(a,b,c,u,v,w,x,y,z),lp;
ideal i=a+c+v+2x-1, ab+cu+2vw+2xy+2xz-2/3,  ab2+cu2+2vw2+2xy2+2xz2-2/5,
ab3+cu3+2vw3+2xy3+2xz3-2/7, ab4+cu4+2vw4+2xy4+2xz4-2/9, vw2+2xyz-1/9,
vw4+2xy2z2-1/25, vw3+xyz2+xy2z-1/15, vw4+xyz3+xy3z-1/21;

link l_hilb,l_fglm = "ssi:fork","ssi:fork";         // 1.

open(l_fglm); open(l_hilb);

write(l_hilb, quote(stdhilb(i)));                       // 2.
write(l_fglm, quote(stdfglm(eval(i))));

list L=list(l_hilb,l_fglm);                             // 3.
int l_index=waitfirst(L);

if (l_index==1)
{
  "stdhilb won !!!!"; size(read(L[1]));
  close(L[1]); close(L[2]);
}
else                                                    // 4.
{
  "stdfglm won !!!!"; size(read(L[2]));
  close(L[1]); close(L[2]);
}
==> stdfglm won !!!!
==> 9

1. Instead of using links of the type ssi:fork, we alternatively could use ssi:tcp links such that the two "competing" SINGULAR processes run on different machines. This has the advantage of "true" parallel computing since no resource sharing is involved (as it usually is with forked processes).

2. Notice how quoting is used in order to prevent local evaluation (i.e., local computation of results). Since we "forked" the two competing processes, the identifier i is defined and has identical values in both child processes. Therefore, the innermost eval can be omitted (as is done for the l_hilb link), and only the identifier i needs to be communicated to the children. However, when ssi:tcp links are used, the inner evaluation must be applied so that actual values, and not the identifiers are communicated (as is done for the l_fglm link in our example).

3. We wait until one of the two children finished the computation. The main process sleeps (i.e., suspends its execution) in the intermediate time.

4. The child which has won delivers the result and is terminated with the usual close command. The other child which is still computing needs to be terminated by an explicit (i.e., system) kill command if running on a different computer. For ssi:fork a close is sufficient.