
Séminaire d'équipe(s) Graphs, ALgorithms and Combinatorics 


Programming computing media (reporté)
Frédéric Gruau
18 September 2020, 14:30
Salle/Bat : 445/PCRIN
Contact :
Activités de recherche : Combinatorics
Résumé :
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 roadmap is to simulate an "empowering" artificial physics in 2Dspace, that will implement a virtual machine facilitating programming.
This artificial physics simulates simplified membraneagents, 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 membranenetwork 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 divideandconquer algorithms, it must be a set of
encapsulated membranes representing the dynamic tree of
divideandconquer 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 CArules to reach an acceptable simulation speed.
Pour en savoir plus :




