Event details

Speaker: Dmitry Zaitsev (University of Derby, UK) developed the analysis of infinite Petri nets with regular structures, the decomposition of Petri nets into clans, the generalised neighbourhood for cellular automata, and the method of synthesising fuzzy logic functions given by tables. He designed the Opera-Topaz software for manufacturing operative planning and control; a new stack of networking protocols, E6, and its implementation within the Linux kernel; and Petri net analysis software Deborah, Adriana, and ParAd. He developed models for TCP, BGP, IOTP protocols, Ethernet, IP, MPLS, PBB, and Bluetooth networks. His current research interests include Petri net theory and its applications in networking, computing, and automated manufacturing. Recently, he started working in the area of exascale computing, applying his theory of clans to speed up solving sparse linear systems on parallel and distributed architectures, as well as developing a novel paradigm of Sleptsov net computing. He has been a co-director of joint projects with China and Austria. Recently, he has been a visiting professor at the Technical University of Dortmund, Germany on a DAAD scholarship; the University of Tennessee, Knoxville, USA on a Fulbright scholarship; Eindhoven University of Technology, Netherlands; Johannes Kepler University, Linz, Austria; Cote D’Azur University, Nice, France; and the Technical University of Darmstadt, Germany. He has published a monograph, four book chapters, and more than a hundred papers, including those listed in JCR and CORE A. He is a senior member of ACM and IEEE. 

Abstract: Solving linear Diophantine systems of equations is applied in discrete-event systems, model checking, formal languages and automata, logic programming, cryptography, networking, signal processing, and chemistry. For modeling discrete systems with Petri nets, a solution in non-negative integer numbers is required, which represents an intractable problem. For this reason, solving such kinds of tasks with significant speedup is highly appreciated. 

We introduce a nearness relation on a set of system’s equations, which transitive closure gives a clan relation. A sparse system is decomposed into a set of its clans. Solving a subsystem for each clan and then the clan composition system gives a speed-up of computations. We design a new solver of linear Diophantine systems, based on the simultaneous and parallel-sequential composition of the system clans, that runs on parallel architectures using a two level parallelization concept based on MPI and OpenMP. A decomposable system is usually represented by a sparse matrix; a minimal clan size of the decomposition restricts the granulation of the technique. A dynamic task-dispatching subsystem is developed for distributing systems on nodes in the process of compositional solution. Computational speedups are obtained on a series of test examples, e.g., illustrating that the best value constitutes up to 45 times speedup obtained on 5 nodes with 20 cores each. For load balancing, aggregation of the minimal clans has been implemented, that yields an additional speed-up. Solving sparse systems over fields of real numbers, using SVD decomposition to obtain basis solutions for clans, also reveals considerable speed-up on real-life tasks from the MatrixMarket repository.