(Reported to unkwown date) Programming computing media

-- Frédéric Gruau (LRI)

Time: 14:30 -- Location: LRI, 445

summary: We consider computing media consisting of billions of small identical Processing Elements (PE) communicating locally in space, and with an homogeneous and isotropic distribution. Computing media can scale arbitrary in size. Thus, they represent parallel architectures whose power can grow without limit. However, programming computing media is difficult.

In general, mapping a particular algorithm on a parallel architecture is not an easy task. In the case of computing media, the difficulty is much higher, due to the simplicity of each PEs, and the locality of the connections between PEs. The spatial location of PEs must be taken into account, because information propagates from one PE to the next nearby PEs. What is feasible though, is to simulate physical laws. This is due to the isotropic and uniform distribution of PEs in space. Our road-map is to simulate an "empowering" artificial physics in 2D-space, that will implement a virtual machine facilitating programming.

This artificial physics simulates simplified membrane-agents, dividing and constantly homogenizing by exerting repulsive forces between each other. Two adjacent membranes can also be connected, in which case an attractive force maintain them nearby. The dynamic unfolding of the membrane-network resembles the biological cellular developmental process whereby an initial ancestor cell develops repeatedly.

The development is driven by a flow of instructions sent by an outside host, through the border of the computing medium. Those instructions determine when and where division occurs, and how membranes get connected to each other, so as to match the need of generic families of parallel algorithms: 1- For systolic algorithms based on nested loops operating on arrays, the network developed must be a regular systolic grid; 2- For the divide-and-conquer algorithms, it must be a set of encapsulated membranes representing the dynamic tree of divide-and-conquer calls.

During this talk, we will present the rule implementing membranes, and increasingly complex examples of developments. In particular we will show the development of the regular grid. The behavior is mathematically correct when the network of PEs in the computing medium is a maximal planar graph. For the moment, though, we have simulation running only for Hexagonal Cellular Automata (CA) which are easier and quicker to simulate than the general case. The resulting rule is quite complex: 77 bits of state and 13878 gates per PEs, up to now. This implied the development of a compiler of CA-rules to reach an acceptable simulation speed.

Category: seminars
Tags: Team seminar combinatorics