### Diacoptics - Nonlinear Network Tearing for Transputer System Implementation

#### Synopsis

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.

#### The Algorithm

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 implementation

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.

#### References

• 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 Paral­lel 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