License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06361.4
URN: urn:nbn:de:0030-drops-10240
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2007/1024/
Go to the corresponding Portal

Gruau, Fréderic ; Christine Eisenbeis

Programming self developing blob machines for spatial computing.

pdf-format:
06361.GruauFredric.Paper.1024.pdf (0.7 MB)

Abstract

This is a position paper introducing blob computing: A Blob is a generic primitive used to structure a uniform computing substrate into an easier-to-program parallel virtual machine. We find inherent limitations in the main trend of today's parallel computing, and propose an alternative unifiying model trying to combine both scalability and programmability. We seek to program a uniform computing medium such as fine grain 2D cellular automata, or more generally coarse grain 2D grids of Processing Elements, using two levels:

In the first "system level", a local rule or run time system is implemented on the computing medium. It can maintain global connected regions called blobs. Blobs can be encapsulated. A blob is similar to a deformable elastic membrane filled with a gas of atoms. (elementary empty blobs). Blobs are interconnected using channels, which act as a spring to bring connected blobs closer to each other. The system implements in a distributed way: movement, duplication and deletion of blobs and channels. It can also propagate waves to communicate signals intra-blob, or inter-blob.

In the second "programmable level", each blob and channel contains a finite state automaton, with output instruction triggering duplication or deletion. Execution starts with a single ancestor blob that duplicates and creates channels repeatedly, thus generating a network of automata. It installs a higher level virtual machine on top of a low level uniform computing medium. This "blob machine" is an example of "self developing automata network".

We present in detail, the blob machine, and how to program it using a higher level language called blob ml. We illustrate the execution of many examples of small programs They all exhibits optimal complexity results, under some reasonable hypothesis concerning the -not yet finished to implement – system level, and considering the model of VLSI complexity.

BibTeX - Entry

@InProceedings{gruau_et_al:DagSemProc.06361.4,
  author =	{Gruau, Fr\'{e}deric and Christine Eisenbeis},
  title =	{{Programming self developing blob machines for spatial computing.}},
  booktitle =	{Computing Media and Languages for Space-Oriented Computation},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6361},
  editor =	{Andr\'{e} DeHon and Jean-Louis Giavitto and Fr\'{e}dric Gruau},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2007/1024},
  URN =		{urn:nbn:de:0030-drops-10240},
  doi =		{10.4230/DagSemProc.06361.4},
  annote =	{Keywords: Cellular automata, amorphous computing, blob machine, blob computing, massive parallelism, graph rewriting, parallism, parallel langage}
}

Keywords: Cellular automata, amorphous computing, blob machine, blob computing, massive parallelism, graph rewriting, parallism, parallel langage
Collection: 06361 - Computing Media and Languages for Space-Oriented Computation
Issue Date: 2007
Date of publication: 31.05.2007

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI