these

THÈSE N

O

3226 (2005)

ÉCOLE POLYTECHNIQUE FÉDÉRALE DE LAUSANNE

PRÉSENTÉE À LA FACULTÉ INFORMATIQUE ET COMMUNICATIONS

Institut des systèmes informatiques et multimédias

SECTION D'INFORMATIQUE

POUR L'OBTENTION DU GRADE DE DOCTEUR ÈS SCIENCES

PAR

ingénieur informaticien diplômé EPF

de nationalité suisse et originaire d'Amden (SG)

acceptée sur proposition du jury:

Prof. E. Sanchez, directeur de thèse

Prof. G. De Micheli, rapporteur

Prof. D. Lavenier, rapporteur

Dr G. Sassatelli, rapporteur

Lausanne, EPFL

2005

TISSU NUMÉRIQUE CELLULAIRE À ROUTAGE ET

CONFIGURATION DYNAMIQUES

Yann THOMA

i

Version abrégée

A l’instar des premiers concepteurs d’avions, l’homme a toujours observé la na-

ture, qui lui a fourni des pistes lors de la création de nouvelles machines ou de nou-

veaux concepts. Les circuits électroniques ne font pas exception, et les trois axes de la

vie que sont l’évolution des espèces (Phylogenèse), le développement de l’organisme

à partir d’une seule cellule (Ontogenèse), ainsi que l’apprentissage dont notre cerveau

est capable (Epigenèse), ont vu nombre de réalisations s’en inspirer.

Ces trois axes, qui forment l’acronyme POE, ont été, pour la plupart des réalisa-

tions, exploités séparément : les principes de l’évolution permettent de résoudre des

problèmes pour lesquels il est difficile d’obtenir une solution de façon déterministe,

des circuits électroniques tirent profit des concepts d’autoréparation du vivant, et les

réseaux de neurones artificiels sont capables d’effectuer efficacement un grand nombre

de tâches. Leur réunion en un seul

tissu

électronique n’a en revanche pas encore vu le

jour.

Concernant la réalisation matérielle de tels systèmes, l’avènement des circuits re-

configurables FPGAs, dont il est possible de redéfinir un nombre quasi infini de fois

le comportement, en a facilité le prototypage. Ils permettent en effet d’accélérer l’exé-

cution d’une tâche, par le parallélisme matériel qu’ils offrent, et ont été grandement

exploités par les chercheurs. Toutefois, ils manquent de plasticité, leur comportement

ne pouvant facilement se modifier lui-même sans une intervention extérieure.

Cette thèse, qui s’insère dans le cadre du projet européen POEtic, se propose de

définir un nouveau circuit électronique reconfigurable, dans l’optique de fournir un

nouveau substrat aux applications bio-inspirées mettant en jeu ces trois axes. Ce cir-

cuit est composé d’un microprocesseur, et d’un tableau d’éléments reconfigurables,

ce dernier ayant été réalisé par nos soins. Les processus évolutifs sont exécutés par

le premier, alors que l’épigenèse et l’ontogenèse prennent place dans le deuxième,

sous la forme d’organismes artificiels multicellulaires. Relativement semblable aux

FPGAs commerciaux actuels, ce sous-système offre cependant de nouvelles caracté-

ristiques intéressantes. Premièrement, les éléments de base du tableau ont la capacité

de reconfigurer partiellement d’autres éléments. Des mécanismes d’auto-réplication et

de différenciation peuvent alors l’exploiter pour laisser un organisme artificiel croître

ou modifier son comportement. Deuxièmement, un niveau de routage distribué offre

la possibilité de créer des connexions entre différentes parties du circuit pendant son

fonctionnement. Les cellules qui y sont implémentées, notamment les neurones artifi-

ciels, peuvent alors initier de nouvelles connexions, de manière à modifier le compor-

tement global du système.

Ce routage distribué, qui constitue l’un des points importants de cette thèse, a vu

la réalisation de plusieurs algorithmes. Basés sur une implémentation parallèle de l’al-

gorithme de Lee, ils sont totalement distribués, c’est-à-dire qu’aucun contrôle global

n’est nécessaire à la création de chemins de données. Quatre algorithmes sont ainsi

définis et décrits matériellement sous la forme d’unités de routage reliées à leurs 3,

4, 6, ou 8 voisines, toutes identiques, qui gèrent les processus de routage. Une ana-

lyse de leurs propriétés nous permet de définir le meilleur algorithme à coupler au

plus efficace des voisinages, en terme de congestion, par rapport au nombre de tran-

ii

sistors nécessaires à leur réalisation. Nous terminons sur le routage en proposant un

cinquième algorithme, qui, contrairement aux quatre précédents, n’est construit que

sur des communications locales entre unités de routage. Il offre ainsi, au prix d’un

coût matériel supplémentaire, une meilleure scalabilité au système complet.

Finalement, le circuit POEtic, sur lequel un de nos algorithmes de routage a été im-

plémenté, a été physiquement réalisé. Nous présentons différents mécanismes POE qui

tirent profit de ses caractéristiques nouvelles et qui peuvent y être embarqués. Parmi

ces mécanismes, nous pouvons citer notamment l’auto-réplication, le matériel évolu-

tif, les systèmes développementaux, et l’autoréparation, qui ont été développés grâce

à un simulateur du circuit, également conçu durant cette thèse.

iii

Abstract

In the design of new machines or in the development of new concepts, mankind has

often observed nature, looking for useful ideas and sources of inspiration. The design

of electronic circuits is no exception, and a considerable number of realizations have

drawn inspiration from three aspects of natural systems : the evolution of species (Phy-

logenesis), the development of an organism starting from a single cell (Ontogenesis),

and learning, as performed by our brain (Epigenesis).

These three axes, grouped under the acronym POE, have for the most part been

exploited separately : evolutionary principles allow to solve problems for which it is

hard to find a solution with a deterministic method, while some electronic circuits draw

inspiration from healing process in living beings to achieve self-repair, and artificial

neural networks have the capability to efficiently execute a wide range of tasks. At this

time, no electronic

tissue

capable of bringing them together seems to exist.

The introduction of reconfigurable circuits called Field Programmable Gate Arrays

(FPGAs), whose behavior can be redefined as often as desired, made prototyping such

systems easier. FPGAs, by allowing a relatively simple implementation in hardware,

can considerably increase the systems’ performance and are thus extensively used by

researchers. However, they lack plasticity, not being able to easily modify themselves

without an external intervention.

This PhD thesis, developed in the framework of the European POEtic project, pro-

poses to define a new reconfigurable electronic circuit, with the goal of supplying a

new substrate for bio-inspired applications that bring all three axes into play. This

circuit is mainly composed of a microprocessor and an array of reconfigurable ele-

ments, the latter having been designed during this thesis. Evolutionary processes are

executed by the microprocessor, while epigenetic and ontogenetic mechanisms are ap-

plied in the reconfigurable array, to entities seen as multicellular artificial organisms.

Relatively similar to current commercial FPGAs, this subsystem offers however some

unique features. First, the basic elements of the array have the capability to partially re-

configure other elements. Auto-replication and differentiation mechanisms can exploit

this capability to let an organism grow or to modify its behavior. Second, a distributed

routing layer allows to dynamically create connections between parts of the circuit at

runtime. With this feature, cells (artificial neurons, for example) implemented in the

reconfigurable array can initiate new connections in order to modify the global system

behavior.

This distributed routing mechanism, one of the major contributions of this thesis,

induced the realization of several algorithms. Based on a parallel implementation of

Lee’s algorithm, these algorithms are totally distributed, no global control being ne-

cessary to create new data paths. Four algorithms have been defined implemented in

hardware in the form of routing units connected to 3, 4, 6, or 8 neighbors. These units

are all identical and are responsible for the routing processes. An analysis of their pro-

perties allows us to define the best algorithm, coupled with the most efficient neighbo-

rhood, in terms of congestion and of the number of transistors needed for a hardware

realization. We finish the routing chapter by proposing a fifth algorithm that, unlike the

previous ones, is constructed only through local interactions between routing units. It

iv

offers a better scalability, at the price of increased hardware overhead.

Finally, the POEtic chip, in which one of our algorithms has been implemented, has

been physically realized. We present different POE mechanisms that take advantage of

its new features. Among these mechanisms, we can notably cite auto-replication, evol-

vable hardware, developmental systems, and self-repair. All of these mechanisms have

been developed with the help of a circuit simulator, also designed in the framework of

this thesis.

Table des matières

Version abrégée

i

Abstract

iii

Remerciements

v

Table des matières

viii

1

Prolégomènes

1

1.1

Réflexions pré-introductives

.

1

1.2

Motivations POEtiques . . .

.

2

1.3

Contributions . . .

.

4

1.4

Contenu de la thèse

.

5

2

De la configuration des circuits électroniques

7

2.1

Processeur

.

8

2.2

ASIC .

.

9

2.2.1

A la demande

.

9

2.2.2

Prédiffusés

.

9

2.2.3

Pré-caractérisés . . .

.

1

2.2.4

A réseau structuré

.

1

2.2.5

Limitations

.

1

2

2.3

Technologies de programmation

.

1

2

2.3.1

Masque . .

.

1

2

2.3.2

Fusible . .

.

1

3

2.3.3

Antifusible

.

1

3

2.3.4

EPROM . .

.

1

4

2.3.5

EEPROM/Flash . . .

.

1

5

2.3.6

SRAM . .

.

1

5

2.3.7

Résumé . .

.

1

6

2.4

Circuits logiques programmables

.

1

7

2.4.1

SPLD . . .

.

1

7

2.4.2

CPLD . . .

.

1

9

2.5

FPIC . .

.

2

0

2.6

FPGAs .

.

2

0

ix

x

TABLE DES MATIÈRES

2.6.1

XC2000 . .

.

2

1

2.6.2

XC6200 . .

.

2

3

2.6.3

Architecture MUX versus LUT

.

2

4

2.6.4

Technologies de programmation

.

2

5

2.6.5

Accroissement de complexité

.

2

6

2.6.6

Fabricants .

.

2

8

2.6.7

Placement/Routage .

.

3

2

2.6.8

FPGA versus ASIC .

.

3

2

2.7

Conclusion

.

3

De la bio-inspiration

35

3.1

Le modèle POE . .

.

3

6

3

.

2

L

a

v

i

e

n

3

a

x

e

s

.

3

7

3.2.1

Phylogenèse

.

3

7

3.2.2

Ontogenèse

.

4

2

3.2.3

Epigenèse .

.

4

3.3

Les Systèmes artificiels en 3 axes

.

4

5

3.3.1

Phylogenèse

.

4

5

3.3.2

Ontogenèse

.

5

1

3.3.3

Epigenèse .

.

5

3

3.4

Combinaisons . . .

.

6

0

3.4.1

PO

.

6

0

3.4.2

PE

.

6

1

3.4.3

OE

.

6

2

3.4.4

POE

.

6

2

3.5

Le projet POEtic .

.

6

2

3.5.1

Nomenclature

.

6

3

3.5.2

Architecture POEtic

.

6

3

3.5.3

Pourquoi un nouveau circuit ? .

.

6

5

4

Le routage au fil des ans

67

4.1

Pourquoi un plus court chemin ?

.

6

7

4.2

Aparté naturel . . .

.

6

8

4.2.1

Les fourmis

.

6

8

4.2.2

Les bulles de savon .

.

6

9

4.2.3

Le gaz, le son, la lumière

.

7

0

4.2.4

De la ficelle

.

7

0

4.3

Les Bases théoriques

.

7

1

4.3.1

Arbre de poids minimal

.

7

1

4.3.2

Plus court chemin . .

.

7

3

4.3.3

Algorithme de Lee .

.

7

8

4.3.4

Variations sur Lee

.

8

1

4.3.5

A* et algorithmes évolués . . .

.

8

7

4.4

Approches Matérielles . . .

.

8

4.4.1

Routage de FPGA .

.

8

9

4.4.2

Coprocesseur

.

8

9

4.4.3

Processeur

.

9

0

4.4.4

SIM

D

.

9

0

TABLE DES MATIÈRES

xi

4.4.5

MIMD . .

.

9

0

4.4.6

Analogique

.

9

0

4.4.7

Tableau de cellules pour la réalisation de circuits . .

.

9

1

4.4.8

Tableau de cellules pour du matériel bio-inspiré . . .

.

9

4

4.5

Conclusion

.

9

5

Le routage distribué

97

5.1

Concept

.

9

7

5.2

Principes

.

9

5.3

Hypothèses

.

1

0

5.4

Premières solutions

.

1

0

5.4.1

Algorithme direct . .

.

1

0

1

5.4.2

Algorithme à adressage relatif direct . . .

.

1

0

2

5.4.3

Algorithme à adressage relatif indirect . .

.

1

0

3

5.5

HIDRA

.

1

0

4

5.5.1

Algorithme

.

1

0

6

5.5.2

Unité de routage . .

.

1

0

5.6

HIDRA-RC

.

1

2

5

5.7

HIDRA-RT

.

1

2

8

5.8

HIDRA-RTC . . .

.

1

3

0

5.9

HIDRA-L

.

1

3

1

5.9.1

Algorithme

.

1

3

1

5.9.2

Implémentation . . .

.

1

3

6

5.10 Voisinages

.

1

4

3

5.10.1 Switchboxs

.

1

4

5.10.2 Nombre total de transistors . . .

.

1

4

5

5.10.3 4 versus 8 .

.

1

4

5

5.11 Analyse

.

1

4

7

5.11.1 Expérience

.

1

4

8

5.11.2 Temps d’exécution .

.

1

4

9

5.11.3 Longueur de chemins

.

1

5

1

5.11.4 Nombre de multiplexeurs

.

1

5

4

5.11.5 Congestion

.

1

5

6

5.11.6 Théorie de la percolation

.

1

6

4

5.12 Conclusion

.

1

6

7

6

Le Circuit POEtic

171

6.1

Structure globale .

.

1

7

3

6.2

Le sous-système organique .

.

1

7

4

6.3

Les Molécules . . .

.

1

7

5

6.3.1

Mode 4-LUT

.

1

7

6.3.2

Mode 3-LUT

.

1

7

8

6.3.3

Mode Comm

.

1

7

8

6.3.4

Mode Shift Memory

.

1

7

9

6.3.5

Mode Input

.

1

8

0

6.3.6

Mode Output

.

1

8

1

6.3.7

Mode Trigger

.

1

8

2

6.3.8

Mode Configure

. .

.

1

8

4

xii

TABLE DES MATIÈRES

6.3.9

Entrées/sorties . . .

.

1

8

4

6.3.10 Communication intermoléculaire

.

1

8

7

6.3.11 Multiplexeurs d’entrée

.

1

9

0

6.3.12 Bits de configuration et reconfiguration partielle . . .

.

1

9

2

6.3.13 Enable moléculaire .

.

1

9

5

6.3.14 Gestion de la bascule

.

1

9

6

6.3.15 Look-up table

.

1

9

8

6.4

Le routage distribué

.

1

9

8

6.4.1

Routage pseudo-statique

.

1

9

6.4.2

Entrées/sorties et systèmes multi-chip . .

.

2

0

6.4.3

Interface molécule/unité de routage . . .

.

2

0

2

6.5

Le sous-système environnemental

. . .

.

2

0

3

6.6

L’interface du système . . .

.

2

0

6

6.7

Fabrication du circuit

.

2

0

7

6.8

Implémentation de composants de base

.

2

0

8

6.8.1

Le registre à décalage

.

2

0

8

6.8.2

Le compteur

.

2

1

6.8.3

Le compteur-trigger

.

2

1

6.9

Les outils de développement

.

2

1

5

6.9.1

Design

. .

.

2

1

5

6.9.2

Simulation

.

2

1

6

6.10 Conclusion

.

2

1

8

6.10.1 Comparaison

.

2

1

8

6.10.2 Améliorations

.

2

1

9

7

Mécanismes POE

221

7.1

Autoréplication . .

.

2

7.2

Développement . .

.

2

4

7.2.1

Stockage de génome

.

2

5

7.2.2

Croissance

.

2

6

7.2.3

Différenciation . . .

.

2

3

0

7.3

Un exemple concret : le prototype PO .

.

2

3

0

7.3.1

Implémentation physique

.

2

3

1

7.3.2

Structure cellulaire .

.

2

3

1

7.3.3

Mécanisme de développement .

.

2

3

2

7.3.4

Evolution .

.

2

3

4

7.3.5

Remarques conclusives

.

2

3

6

7.4

Matériel évolutif non-contraint

.

2

3

6

7.4.1

La look-up table . .

.

2

3

8

7.4.2

Le switchbox

.

2

3

8

7.4.3

Les entrées

.

2

3

9

7.4.4

Représentation du génome . . .

.

2

3

9

7.4.5

Caractéristiques de l’évolution .

.

2

4

2

7.5

Autres exemples . .

.

2

4

2

7.5.1

Autoréparation . . .

.

2

4

2

7.5.2

Synthèse vocale . . .

.

2

4

3

7.5.3

Neurone à impulsion

.

2

4

7.6

Conclusion

.

2

4