Distributed execution of automata networks on a computing medium: introducing IfAny machines.

Abstract : A computing medium is a set of Processing Elements (PE) homogeneously distributed in space, with connections local in space. PEs are fine grain, and are therefore modeled as Finite State Machine (FSM). In this elementary framework, the interaction between PEs can be defined by a set of instructions, which return a value depending on the neighbor's state. That value is then used as an input to the FSM. This paper studies an instruction set reduced to a single instruction called ''IfAny $q$'' that tests IfAny of the neighbors has a given state $q$. This instruction puts a minimal requirement on hardware: there is no need for addressing channels, communication can be done by local radio broadcasting. An IfAny machine $A$ running on a network tailored for a specific computational task can be executed in parallel on an IfAny medium whose network is fixed and reflects the locality in space. The execution involves an embedding of $A$'s network, and a transformation of $A$'s FSM, adding a 3 states register. We analyse the example of $A$ realizing the addition of $n$ binary numbers. With a carefully chosen network embedding, the resulting parallel execution is optimal in time and space with respect to VLSI complexity. This work demonstrates that IfAny machines can be seen as a rudimentary programming method for computing media. It represents a first step of our long term project which is to realize general purpose parallel computation on a computing medium.
Type de document :
Communication dans un congrès
Unconventional Computation & Natural Computation, 2012, Orleans, France. 2012
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00795958
Contributeur : Frederic Gruau <>
Soumis le : jeudi 31 août 2017 - 09:18:57
Dernière modification le : jeudi 24 mai 2018 - 15:59:21
Document(s) archivé(s) le : jeudi 30 mai 2013 - 04:25:23

Fichier

UCNC2012.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00795958, version 1

Collections

Citation

Gruau Frederic, Luidnel Maignan. Distributed execution of automata networks on a computing medium: introducing IfAny machines.. Unconventional Computation & Natural Computation, 2012, Orleans, France. 2012. 〈hal-00795958〉

Partager

Métriques

Consultations de la notice

324

Téléchargements de fichiers

44