A.28 Parallelization with MPtcp links

In this example, we demonstrate how MPtcp 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, a priory one can not predict which one of the two commands is faster. This very much depends on the (input) example. Therefore, we use MPtcp 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 "omdi 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 = "MPtcp:fork","MPtcp:fork";         // 1.

open(l_fglm); open(l_hilb);

write(l_hilb, quote(system("pid")));                    // 2.
write(l_fglm, quote(system("pid")));
int pid_hilb,pid_fglm = read(l_hilb),read(l_fglm);

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

while ((! status(l_hilb, "read", "ready", 1)) &&        // 4.
       (! status(l_fglm, "read", "ready", 1))) {}

if (status(l_hilb, "read", "ready"))
{
  "stdhilb won !!!!"; size(read(l_hilb));
  close(l_hilb); pid_fglm = system("sh","kill "+string(pid_fglm));
}
else                                                    // 5.
{
  "stdfglm won !!!!"; size(read(l_fglm));
  close(l_fglm); pid_hilb = system("sh","kill "+string(pid_hilb));
}
→ stdfglm won !!!!
→ 9

Some explanatory remarks are in order:

1. Instead of using links of the type MPtcp:fork, we alternatively could use MPtcp:launch 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. Unfortunately, MPtcp links do not offer means to (asynchronously) interrupt or kill an attached (i.e., launched or forked) process. Therefore, we explicitly need to get the process id numbers of the competing SINGULAR processes, so that we can "kill" the looser later.
3. 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 MPtcp:launch 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).
4. We go into a "sleepy" loop and wait until one of the two children finished the computation. That is, the current process checks approximately once per second the status of one of the connecting links, and sleeps (i.e., suspends its execution) in the intermediate time.
5. 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, since it can not be terminated through the link while it is still computing.