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
Measuring Similarity between Logical Arguments
Automated Reasoning
Monday 06 March 2023 - 00:00
Salle : 0 - 650
Victor David .............................................

Imputing Out-of-Vocabulary Embeddings with LOVE Ma
Data-Centric Languages and Systems
Monday 20 February 2023 - 00:00
Salle : 455 - PCRI-N
Lihu Chen .............................................

On the Interplay between Software Product Lines an
Automated Reasoning
Tuesday 18 October 2022 - 14:15
Salle : 2013 - DIG-Moulon
Vander Alves .............................................

Combining randomized and observational data: Towar
Automated Reasoning
Thursday 13 October 2022 - 10:30
Salle : 2011 - DIG-Moulon
Bénédicte Colnet .............................................

New Achievements of Artificial Intelligence in Mul
Automated Reasoning
Tuesday 11 October 2022 - 14:15
Salle : 2013 - DIG-Moulon
.............................................