Diacoptics - Nonlinear Network Tearing for Transputer System Implementation
The research investigates decomposition as a methodological approach to optimisation and control of large
scale systems. Kron's method of decomposing large scale linear systems, referred to in the literature as
network tearing or diakoptics, is a particularly efficient way of calculating a coordinated
solution as it is a direct analytical technique avoiding any iterative re-calculation of subsystem
solutions. Most importantly however, the form of decomposition resulting from
the application of this technique maps directly onto MIMD parallel processing hardware
(such as transputer arrays), enabling an approximately n-fold improvement in the computational
efficiency. The major limitation of the Kron's technique is its requirement of system
linearity which serves to ensure that the magnitude of corrections to subsystem solutions
is not a limiting factor in the solution process.
This research is focused on a development and generalisation of Kron's method of diakoptics applied
to nonlinear systems. The nonlinear systems need to be solved subject to a constraint
that the corrections to partial solutions have restricted magnitude so that the local
mathematical models of subsystems are not invalidated in the process. The system is
solved as a sequence of Newton-Raphson iterations with each iterative correction calculated
as diakoptical coordinated solution to linearised subsystem. In order to facilitate an
efficient use of a parallel processing hardware, the algorithm has been designed to
minimise the data traffic between the subsystem solvers and the coordinating task.
Without detracting from the generality of the algorithm, we discuss it here in the in
the context of water distribution networks, which are large scale, nonlinear systems.
LetÕs consider a system composed of two
subnetworks, as illustrated in Figure 1a. The numerical simulation of such a system
involves the solution of a set of mass balance equations for each node in the system.
The algorithm has been implemented in 3L Parallel Fortran 77 and executed on a
network of transputers. A general structure of the program is illustrated in Figure 2.
Steps 1, 2, 4 and 5 of the algorithm are contained within ÕTask-A CoordinationÕ and
Step 3 is contained within ÕTask-B Subsystem SolutionÕ. Since the copies of task B
are placed on separate transputers, the issue of minimisation of data traffic between
Task-A and -B had to be carefully addressed.
Let's consider a typical network of N nodes, with each node connected to 4 other
nodes in the network. A transfer of nonzero elements of the Jacobian matrix from
Task-A to Task-B would involve sending 5xN real values together with associated
pointers, resulting in a transfer of at least 11xNx4 bytes of data (if a sparse storage
structure such as pointer-column-index is used, or 15xNx4 bytes if it is not).
Instead, in our implementation, the Jacobian matrices are derived locally within
Task-B from network topological data, which require sending of 6xNx4 bytes of data.
Apart from an obvious reduction of a data traffic an additional benefit of concurrent
evaluation of Jacobian matrices has been achieved.
The coordination process, equation (24), requires the knowledge of the inverse of
Jacobians. If implemented directly, this would imply the need to send from Task-B to
Task-A 3xNxNx4 bytes of data! This problem had been noted by other researchers
 but no effective solution was proposed at the time.
Our implementation resolves the problem by stipulating Task-B to evaluate explicitly
selected columns of inverse Jacobian which is all that is needed by Task-A.
By doing so, the required data transfer is reduced to 3xNxCx4 bytes; where C is a
number of inter-subnetwork connections and is much smaller than N. The above
modification resulted in a reduction of data traffic between Task-B and Task-A by a
factor of 10 to 100 for a typical large scale system.
Testing the program on real-life networks, it has been found that the time required by
Task-B depends quasi-linearily on the number of nodes in the subnetwork, and the
time required by Task-A depends quadratically on the number of inter-subnetwork
connections. Since the number of inter-subnetwork connections does not depend on
the network size but only on the number of subsystems and the average node
connectivity, the algorithm offers a potential of significant concurrent processing
gains for large scale systems.
With the reduction of the volume of transferred data, the time spent on
communication constituted approximately 1% of total processing time for a 100 node
system. As the volume of data transmitted between two tasks is linearily proportional
to the network size, the data transfer time will continue to be negligible.
- Kron G., Diakoptics: The piecewise solution to large scale systems, Macdonald, 1963.
- Bowden K., - Kron's Method of Tearing on Transputer Arrays, The Computer Journal, Vol. 33, No.5, 1990
- Bargiela A., Hosseinzaman A., Parallel simulation of nonlinear networks using diakoptics, Proceedings of Int. Conf. on Parallel Computing and Transputer Applications PACTA ‘92, (Eds.) M Valero at.all, Barcelona, Sept. 1992, ISBN 84 87867 138, pp. 1463-1473.
- Argile A., Bargiela A., Using X11 Windows to provide shared task memory in distributed computer systems, , Int. Conf. On Computing and Control in Water Industry, Leicester, 1993.
- Hartley J.K., Bargiela A., Utilisation of smoothing formulae for describing hydraulic relationships in water networks, Int. Conf. On Computing and Control in Water Industry, Leicester, 1993.
- Bargiela A., Parallel and distributed telemetry data processing, Proceedings of Parallel Computing and Transputers Conference, PCAT93, Brisbaine, 1993, ISBN 90 5199 1495, pp. 269-275.
- Hartley J.K., Bargiela A., TPML: Parallel meta-language for scientific and engineering computations using transputers (TPML), Proc. of 2nd Int. Conf. on Software for Supercomputers and Multiprocessors, SMS’94, 1994, pp. 22-31
- Argile A., Bargiela A., XDSM - an X11 based virtual distributed shared memory system, Proc. of 2nd Int. Conf. on Software for Supercomputers and Multiprocessors, SMS’94, Moscow, 1994, pp. 250-259.
- Bargiela A., Pedrycz W., A model of granular data: a design problem with the Tchebyschev FCM, Soft Computing , 9, 3, March 2005, 155-163, doi:10.1007/s00500-003-0339-2
- Cichocki A., Bargiela A., Neural Networks for Solving Linear Inequality Systems, Parallel Computing , Vol.22, No.11, Jan. 1997, pp.1455-1475
- Bargiela, A., Pedrycz, W., (2002), Granular Computing: An Introduction, Kluwer Academic Publishers.
- Bargiela A., Pedrycz W., Tanaka M., (2003), A study of uncertain state estimation, IEEE Trans. on Systems Man and Cybernetics, SMC-A, 33, 3, 288-301.
- Bargiela, A., Pedrycz, W., Hirota, K. (2002), Logic-based granular prototyping, Computers Software and Applications Conference, COMPSAC 2002, Oxford, August 2002.
- Bargiela, A. Pedrycz, W., (2002), Archives of Control Sciences – Special Issue on Granular Computing, ISSN 0004-072X.
- Pedrycz, W., Smith M.H., Bargiela, A. (2000), Granular clustering: A granular signature of data, Proc. 19th Int. (IEEE) Conf. NAFIPS’2000, Atlanta, July 2000, 69-73.
- Pedrycz W., ed. (2001), Granular Computing: An Emerging Paradigm, Physica-Verlag.
- Pedrycz, W., Bargiela, A. (2002), Granular clustering: A granular signature of data, IEEE Trans. on Systems Man and Cybernetics, Vol 32, No. 2, 212-224.
- Pedrycz W, Bargiela A, (2003), Fuzzy fractal dimensions and fuzzy modeling, Information Sciences, 153, 199-216
- Bargiela A., Hosseinzaman A., Parallel simulation of nonlinear networks using diakoptics, in Parallel Computing and Transputer Applications, M. Valero (ed.), IOS Press/CIMNE, Barcelona, 1992, ISBN 84 87867 138, pp. 1463-1473.
Last update: 20/12/95