Cellular-neural algorithms: asynchronous versus synchronous modes of execution.

List of the participants:
Summary:

A new model of massive distributed computations, termed a Cellular-Neural Algorithm, is synthesized of two models of fine-grained parallel computations: Artificial Neural Network and Parallel Substitution Algorithm. The latter is the most theoretically advanced model of the class of computational models with the cellular parallelism. The new model - Cellular-Neural Algorithm - can be perceived as a neural network enriched with the possibility of internal control of computation.

Two pure modes of operation of neural networks are touched upon in the literature: synchronous and asynchronous. These modes of operation have pros and cons. In the asynchronous mode, a neural network evolves to a minimum of neural network energy with a minimal step (which is attractive for finishing stages of the search for solution and not so attractive for starting stages). In the synchronous mode, a neural network evolves with great steps, jumping across minima (put the contents in above brackets in reverse). In addition, in the synchronous mode, each neuron changes its state in accordance with energy of local transition rather than with energy of global transition, and a network changes its state with invalid information about state transition (which can prove to be a "two steps forward and one step backward" process).

It is of interest to find a compromise between the synchronous and the asynchronous (the parallel and the sequential) in order that to develop a mixed synchronous-asynchronous mode of operation showing advantages of the pure modes. That can be made for the possibility to change a mode of operation of a cellular-neural network during a computation process. The conventional architectures of neural networks do not have such a property.

The aim of the project is to study various modes (with one or other extent of synchroneity and asynchroneity) of operation of a deterministic and a stochastic model of cellular-neural networks. Based on a knowledge of various modes, it is interesting, for example, to investigate the effect of the synchronous steps at the beginning of the computation process on the possibility to avoid the dependence of the solution upon an initial state of a deterministic neural network. Or, yet further question, to find such a mixed mode in which the "two steps forward and one step backward" process could be corrected.

List of publications:

  1. S.Achasova, O.Bandman, V.Markova, S.Piskunov. Parallel Substitution Algorithm. Theory and Application. // - World Scientific: Singapore, 1994. 220pp.
  2. S.M.Achasova, O.L.Bandman. Correctness of Distributed Computational Processes.// (Russia). - Novosibirsk: Nauka, 1990. 250p.
  3. S.M.Achasova. Correctness of Interpretations of Parallel Substitution Systems. // J. New Gener. Comput. Syst. 4 (1991) 1, 19 - 27.
  4. S.M.Achasova. Correctness of Synchronized Cellular Computations. // Proceeding of the International Conference "Parallel Computing Technologies", Obninsk, Russia, Aug 30 - Sept 4, 1993, p. 543-556.
  5. S.M.Achasova. Synchronous-Asynchronous Cellular Computations. // Lect. Notes in Comput. Sci., 964, 1995, p. 1-6.
  6. S.M.Achasova. Correctness of Cellular Computations in the Pyramid and the Hypercube Spaces // Programmirovanie, 1995, 4, p. 3-12.
  7. S.M.Achasova. Cellular-Neural Combinatorial Optimization Algorithms. // Proceedings of the Conference "New Information Technologies in Discrete Structures Study". Ekaterinburg, 1996. - P. 156 - 161.

Please contact Dr. Svetlana Achasova for all the questions concerning these researches and publications.
E-mail: achasova@ssd.sscc.ru
Last update: July 8, 1996