Process scheduling in DSC and the large sparse linear systems challenge (Q1895417)

The DSC system for distributing large scale symbolic computations over a network of UNIX computers was introduced by A. Díaz et al. [Proc. 1991 Internat. Symp. Symbolic Algebraic Comput. (ACM Press, New York) (1991)]. The present paper, a preliminary version of which appeared in Design and implementation of symbolic computation systems [Lect. Notes Comput. Science 722 (1993)], describes recent changes to DSC. The most important modification concerns the subtask-to-process allocation schedule, which now takes into account the CPU load and memory usage of participating machines, as well as estimates of the requirements of the subtasks as supplied by the application program. Other modifications include the introduction of a co-routine mechanism to enable a finer-grained parallelism and two-way communication between the subtask and the parent process; and the possibility to employ a user-supplied port number, so that several users can now independently set up individual DSC servers. Two large experiments are described in this improved setting. The first experiment involves a distributed implementation of the Goldwasser-Kilian/Atkin primality test -- see \textit{A. O. L. Atkin} and \textit{F. Morain} [Math. Comput. 61, No. 203, 29-68 (1993; Zbl 0792.11056)]. In this, a number of 1111 decimal digits was proved prime in a period of about 2 months, using some 20 computers. The second experiment solves a homogeneous system of linear equations over a finite field, where the coefficient matrix is given as a black-box linear function, using a method of \textit{D. Coppersmith} [Math. Comput. 62, No. 205, 333-350 (1994; Zbl 0805.65046)]. A linear system with over 245,000 equations, over 250,000 unknowns and over 11 million nonzero entries over \(GF(2)\) was solved in this way.