The Foundation of Self-developing Blob Machines for Spatial Computing

Frédéric Gruau 1 Christine Eisenbeis 2 Luidnel Maignan 3
1 LIRMM/HE - Hors Équipe
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 ALCHEMY - Architectures, Languages and Compilers to Harness the End of Moore Years
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France
Abstract : The current trend in electronics is to integrate more and more transistors on a chip and produce massive hardware resources. As a consequence, traditional computing models, which mainly compute in the temporal domain, do not work well anymore since it becomes increasingly difficult to orchestrate these massive-scale hardware resources in a centralized way. Spatial computing is a unifying term that embodies many unconventional computing models and means computing on a relatively homogeneous physical medium made of hardware components, where the communication time is dependent on the euclidean distance between the components (locality constraint). This constraint makes the programming for high performance significantly more complex compared to classical non-spatial hardware because performance now depends on where computation happens in space (mapping problem). Blob computing is a new approach that addresses this parallel computing challenge in a radically new and unconventional way: it decouples the mapping of computations onto the hardware from the software programming while still elegantly exploiting the space of the underlying hardware. Hardware mapping of computations is done by a physical force-based approach that simulates forces between threads of computation (automata). Attractive forces are used to keep automata that need to communicate with each other closer while repulsive forces are used for load balancing. The advantage of theses primitives is that they are simple enough to be implemented on an arbitrary computing medium. They form the basis of a runtime system (RTS) that transforms an arbitrary computing medium into an easier-to-program virtual machine called the blob machine. The basic objects of the blob machine are those automata, and the instructions let automata create new automata in specific ways so as to maintain a hierarchical organisation (which facilitates both the mapping and the programming). We detail the basic instructions of the blob machine and demonstrate their confluence. Programming a spatial medium to perform a given algorithm then boils down to programming the blob machine, provided the RTS is implemented on it. The advantage of this approach is the hardware independency, meaning that the same program can be used on different media. By means of several examples programmed using a high level langage description, we further show that we can efficiently implement most current parallel computing models, such as Single Instruction Multiple Data (SIMD), data parallelism, ''divide and conquer'' parallelism and pipelining which demonstrates parallel expressiveness. On sorting and matrix multiplication algorithms, we also show that our approach scales up optimally with the number of basic hardware components.
Type de document :
Article dans une revue
Physica D: Nonlinear Phenomena, Elsevier, 2008, 237 (9), pp.1282-1301
Liste complète des métadonnées
Contributeur : Frederic Gruau <>
Soumis le : mercredi 8 juillet 2009 - 13:19:20
Dernière modification le : jeudi 11 janvier 2018 - 06:26:09
Document(s) archivé(s) le : mardi 15 juin 2010 - 17:56:35


Fichiers produits par l'(les) auteur(s)


  • HAL Id : lirmm-00402195, version 1


Frédéric Gruau, Christine Eisenbeis, Luidnel Maignan. The Foundation of Self-developing Blob Machines for Spatial Computing. Physica D: Nonlinear Phenomena, Elsevier, 2008, 237 (9), pp.1282-1301. 〈lirmm-00402195〉



Consultations de la notice


Téléchargements de fichiers