HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Self-developing blob machines for spatial computing: the foundations

Frédéric Gruau 1, 2, 3, 4 Christine Eisenbeis 1, 4 Luidnel Maignan 4, 1
4 ALCHEMY - Architectures, Languages and Compilers to Harness the End of Moore Years
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : Technology can now produce massive hardware resources, large enough so that it becomes increasingly difficult to organize it in a centralized way. Spatial computing proposes to model such huge hardware as a relatively homogeneous computing medium satisfying a locality constraint: communication time is related to geometric distance. While the constraint is weak enough to allow arbitrary scalability, it is strong enough to make the tasks of programming and mapping significantly more complex; programming thus becomes the central problem. We propose a two level programming approach: at low level, a run time system layer runs on the computing medium and transforms it into a virtual machine, called the blob machine; at high level, programs run on this more expressive virtual machine. The system layer is implemented on the computing medium as a local rule that manages distributed objects similar to membranes and filament channels; system calls are distributed primitives that allow objects to be created or deleted. The physical interpretation of the objects allows the implementation on arbitrary spatial computing medium. This layer is responsible for placing the objects in the space and does it by simulating physical forces. Each object is controlled by a FSA (Finite State Automaton) whose output actions are the object primitives (creation \& deletion). The set of FSAs together with the communication pathways implied by the topology of encapsulated membranes and channels, define a network of FSA that can self develop. This ``self-developing network of FSA'' is the formal definition of the blob machine. We present this blob machine, and how to program it using a higher level language description. We illustrate the execution of many examples of small and simple programs that cover a wide spectrum of parallel paradigms, including SIMD, data parallelism, Divide and Conquer and pipelining. Usually, if the problem needs a space of O(n), the time complexity can be reduced to O(n^{1/d}) where d is the dimensionality of the computing medium: 2D, or 3D. In some cases the same program runs optimally for any value of d, in other cases, the dimensionality must be considered. Citation about a computer using physical objects as primitives, like blobs and channels, which has given us inspiration: `The kinematic model [of self reproducing machine] deals with the geometric-kinematic problems of movement, contact, positioning, fusing and cutting'', John Von Neumann, Theory of Self-Reproducing Automata, 1966.
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Thursday, February 28, 2008 - 12:07:05 PM
Last modification on : Friday, February 4, 2022 - 3:30:11 AM
Long-term archiving on: : Tuesday, September 21, 2010 - 3:55:48 PM


Files produced by the author(s)


  • HAL Id : inria-00258845, version 2


Frédéric Gruau, Christine Eisenbeis, Luidnel Maignan. Self-developing blob machines for spatial computing: the foundations. [Research Report] RR-6457, INRIA. 2008. ⟨inria-00258845v2⟩



Record views


Files downloads