Faculté informatique et communications IC, Section d'informatique, Institut des systèmes informatiques et multimédias ISIM

Amorphous membrane blending : from regular to irregular cellular computing machines

Teuscher, Christof ; Mange, Daniel (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2004 ; no 2925.

Add to personal list
    Summary
    The von Neumann architecture was first expressed in 1945 and has largely dominated in many variants and refinements computer science for more than half a century. Alternative architectures always occupied a marginal place only, despite a growing need for new concepts and paradigms in computer science. Biologically-inspired engineering applies biological concepts to the design of novel computing machines and algorithms. This can lead to the creation of new machines, endowed with properties usually associated with the living world: adaptation, evolution, growth and development, fault-tolerance, self-replication or cloning, reproduction, etc. Most of these approaches are based on well established theories such as artificial neural networks, evolutionary algorithms, and cellular automata. The work presented in this thesis takes an alternative path and proposes concepts for novel and unconventional biologically-inspired machines. The approach is mainly motivated by the insight that tomorrow's computational substrates and environments might be very different from what we know today. Some of tomorrow's computers might be embedded in the paint that covers your desk or printed on a sheet of paper by means of a special ink. Most of such pervasive computing concepts have some common elements: (1) the computer's basic elements are very simple, identical, and available in a huge number, (2) the interactions between the elements are purely local, (3) the elements as well as the interconnections are unreliable, and (4) there is no global control mechanism available. This thesis is mainly based on the unification of the following three domains of research: (1) amorphous computing, (2) membrane systems, and (3) blending. An amorphous computer is a massive parallel machine made up of myriads of simple, unreliable, and identical elements, distributed randomly on a surface and interconnected locally by unreliable connections. Membrane systems are theoretical models inspired by biochemistry-based on regions bounded by membranes. The hierarchical membrane structures contain artificial chemistries, consisting in objects and reactions, which allow to do computations. Blending is a framework of cognitive science which tries to explain how we deal with mental concepts and how creative thinking emerges. First, an introduction of traditional bio-inspired machines and hardware is provided. This part also includes the presentation of a first implementation of a membrane system on reconfigurable hardware and a description of the cellular automata machine entitled BioWall, with its applications. Random boolean networks as well as several theoretical considerations and practical results are then used to introduce irregular computational structures. The C-Blending approach represents an novel computational blending method intended for membrane systems and artificial chemistries. In order to implement membrane systems on amorphous computers, the Circuit Amorphous Computer as well as special membrane systems, termed aP and aB membrane systems, are proposed. The ultimate concept proposed and studied consists in a unification of membrane systems, amorphous computers, and computational C-Blending. The unification of the three concepts results in several interesting properties. The cellular structures allow to create dynamical hierarchies and growing systems whereas the artificial chemistries represent an ideal mean to compute on the potentially imperfect and irregular hardware of an amorphous computer. Finally, the computational blending proposed describes an inventive method to create, organize, and adapt membrane systems. The characteristics and limits of the concepts proposed are analyzed and validated using various examples and toy applications. The thesis concludes with the definition of the Circuit Amorphous Computer and the Amorphon architecture, which might constitute the minimal element of tomorrow's computing machines.
    Résumé
    Depuis les débuts de l'informatique moderne, la quasi totalité des ordinateurs sont conçus selon l'architecture de von Neumann, présentée en 1945. Les peu nombreuses architectures alternatives n'ont occupé qu'une place marginale parmi les systèmes informatiques, malgré un besoin croissant de nouveaux concepts et paradigmes. Les approches théoriques et machines informatiques dites bio-inspirées s'inspirent des systèmes biologiques pour se doter de propriétés originales, propres aux seuls êtres vivants: adaptation, apprentissage, évolution, croissance, tolérance aux pannes, autoréparation, etc. Ces machines se basent principalement sur des approches bien établies et connues comme les réseaux de neurones artificiels, les algorithmes évolutifs et les automates cellulaires. La présente thèse vise à prendre une direction originale en proposant des concepts pour de nouvelles machines bio-inspirées. La principale motivation pour cette voie alternative vient du fait que le substrat et l'environnement de certains futures ordinateurs sera très différent de ce que nous connaissons aujourd'hui. Un ordinateur de demain sera peut-être intégré dans la peinture qui couvre votre table ou pourra être imprimé sur une feuille de papier à l'aide d'une encre spéciale. Ces nouveaux substrats ont tous plusieurs éléments en commun: (1) les éléments de base de l'ordinateur sont simples, identiques, et présents en très grand nombre, (2) les interactions entre ces éléments sont purement locales, (3) les éléments ainsi que les interconnexions ne sont pas fiables, et (4) il n'y a pas de contrôle global. Cette thèse se base principalement sur trois domaines de recherche: (1) les ordinateurs amorphes, (2) les systèmes membranaires et (3) le blending. Les ordinateurs amorphes sont des machines massivement parallèles constituées d'éléments simples, potentiellement imparfaits, distribués aléatoirement sur une surface, et interconnectés de manière local et aléatoire. Un système membranaire est un modèle théorique — inspiré par la biochimie — basé sur des régions définies par des membranes qui contiennent des objets effectuant du calcul selon des règles prédéfinies. Le modèle représente ainsi une sorte de chimie artificielle. Le blending, théorie provenant des sciences cognitives, essaie d'expliquer comment nous traitons les concepts et comment nos pensées créatives émergent. La thèse commence par une introduction aux machines et matériel bio-inspirés, incluant une première réalisation de systèmes membranaires sur une structure reconfigurable régulière, ainsi que la présentation de la machine cellulaire BioWall et ses différentes applications. Les réseaux binaires aléatoires ainsi que plusieurs plusieurs considérations et résultats théoriques autour de ce modèle sont utilisés pour introduire et motiver des structures computationelles aléatoires et irrégulieres. Le C-Blending présente une méthode originale d'application des principes du blending à des systèmes membranaires et à des chimies artificielles. Pour réaliser des systèmes membranaires sur un ordinateur amorphe, le Circuit Amorphous Computer ainsi que les systèmes membranaires de type aP et aB sont détaillés. L'ultime concept proposé consiste en une réalisation unifiée des systèmes membranaires aP et aB — organisés et adaptés par la méthode du C-Blending — sur un ordinateur amorphe. L'unification des trois concepts présente plusieurs propriétés intéressantes. Les structures cellulaires permettent la création de hiérarchies dynamiques et de systèmes qui se développent, tandis que la chimie artificielle offre un moyen de computation idéal et performant dans le milieu incertain et irrégulier de l'ordinateur amorphe. Le blending, quant à lui, représente une méthode originale pour la création, l'adaptation et l'organisation de systèmes membranaires. Les caractéristiques et limites des concepts proposés sont analysées et plusieurs exemples et applications valident les idées introduites à l'aide de simulations. La thèse se conclut par la définition de l'architecture du Circuit Amorphous Computer et de l'Amorphon, l'élément minimal qui pourrait être à la base des architectures des ordinateurs de demain.