From Amorphous to Spatial Computing - Workshop
Paris, France, July 7-8, 2008
Paris, France, July 7-8, 2008
Up to recent years, performance gains in microprocessors have mainly been obtained by a continuous increase of the clock frequency of a single centralized computing processor. Mainly because of power dissipation issues, this recipe can no longer be exploited. The alternative consists in splitting/parallelizing computations between numerous computation units/elements. Hence, recent general purpose computers are already composed of several computing elements (e.g. 8 cores for the new Intel Nehalem microprocessor or 9 cores for the IBM/Sony/Toshiba’s Cell microprocessor found in the PS3). Considering plausible future technologies (nanotubes, biological entities, quantum devices), there is a general consensus that this trend will continue and that future computing devices will be composed of a huge number of computing elements, spread in a more or less disordered way in 2D or 3D. Controlling such massively parallel systems at low costs necessitates the development of new decentralized and locally-expressed algorithms. Furthermore, in such “computing media”, communication time increases with the Euclidean distance between the elements. These issues put a very strong constraint on locality and represent a great challenge for programming. In particular, a key issue consists in understanding how to deﬁne local primitives (the program) so as to obtain a given emerging behavior at the global scale (the computation result). Obviously, this problematic is in direct line with the ﬁeld of Complex Systems.
The aim of Amorphous Computing is to identify useful programming methodologies that will enable us to engineer the emergent behavior of a large number of locally interacting computing elements. To cope with the above considerations, the computing elements are constrained to be asynchronous, irregularly located in space, unreliable, communicating by local broadcasts only, having limited resources and sharing the same program. The issue addressed by Amorphous Computing is thus: “How to write programs or controllers to reliably produce coherent global behaviors under these constraints?”
This research ﬁeld was originally developed at the end of the 90’s at MIT, AI Lab by D. Coore, R. Nagpal and R. Weiss (http://www-swiss.ai.mit.edu/projects/amorphous). It has disseminated since in a number of countries (including EU and France) and various disciplinary ﬁelds. While its original inspiration rather relied on biological development and embryogenesis (gradients and diﬀusion), it progressively opened up to other backgrounds such as cellular automata, lattice-gas models, self-developing cellular networks or multi-agent systems. Among its main achievements are the formulations of local, decentralized, robust and spatial algorithms for a limited scope of applications, such as hop counts ﬁnding (distance between agents), computation of spatial coordinate systems in the computing elements space, building predeﬁned 2D spatial patterns, the computation of Voronoļ diagrams or Origami folds. Furthermore, these approaches yielded the development of speciﬁc programming languages, such as the Growing Point Language or Origami Shape Language, as well as dedicated virtual machine frameworks (Blob computing).
In the late 90’s, Amorphous Computing suﬀered from a lack of visibility as to what could be the hardware support of the computing media it considers. However, the development of recent technologies such as nanotechnologies (carbon nanotubes) and, most notably the recent advances in Synthetic Biology that make the possibility of programming biological cells a reality, announce the advent of “spatial computing media” for a near future and strongly reinforce the pertinence of the issues raised by Amorphous Computing.
Submission: June 9, 2008
Notification: June 16, 2008
Workshop: July 7 and 8, 2008