Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
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/PCRI-N
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 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.

Pour en savoir plus :
Séminaires
Programming computing media (reporté)
Combinatorics
Friday 18 September 2020 - 14:30
Salle : 445 - PCRI-N
Frédéric Gruau .............................................

Large-scale Spectral Clustering for GPU-based Plat
High-performance computing
Tuesday 24 March 2020 - 10:30
Salle : 465 - PCRI-N
Guanlin He .............................................

Recherche Opérationnelle à Google
Stochastic Combinatorial Optimization
Thursday 12 March 2020 - 14:30
Salle : 445 - PCRI-N
Laurent Perron .............................................

Forum dev-LRI
Wednesday 05 February 2020 - 14:00
Salle : 455 - PCRI-N
Erik Bray .............................................

Quantum at LRI
Quantum computing
Tuesday 04 February 2020 - 09:00
Salle : 465 - PCRI-N
.............................................