DOMAINE TECHNIQUE GENERAL La présente invention se rapporte au domaine des architectures parallèles.

Plus précisément, elle concerne un procédé d'utilisation d'une mémoire partagée par plusieurs applications ou plusieurs tâches. ETAT DE L'ART

Les architectures parallèles sont devenues le paradigme dominant des systèmes informatiques depuis quelques années, le traitement simultané d'une pluralité de tâches démultipliant des performances.

Cependant, un des problèmes que le parallélisme pose est la gestion d'espace mémoire, en particulier mémoire vive. La première solution est que chaque unité de calcul dispose d'un espace de stockage propre (on parle de mémoire « distribuée »). Ce système est toutefois inutilement cher -car il faut prévoir en n exemplaires une mémoire de taille surdimensionnée pour éviter des problèmes de dépassement de capacité (« overflow »)-, et nécessite que soit prévu un lourd système de communication entre les mémoires.

Alternativement à la mémoire distribuée, on trouve la mémoire dite « partagée », c'est-à-dire co-utilisée par les différentes unités de calcul, ce qui évite les inconvénients susmentionnés. L'accès à une même mémoire par deux processus ou plus nécessite cependant quelques précautions. D'un point de vue matériel, il est nécessaire d'interdire la lecture d'une zone de mémoire si une autre tâche est en train de la réécrire sous peine de lire un curieux mélange, et réciproquement. Le processus de lecture est en effet plus rapide que celui d'écriture. En outre, deux écritures simultanées ne peuvent être autorisées, sinon on risque une situation de « concurrence », dont le résultat est imprévisible. Seules deux lectures simultanées ne posent pas de problème.

On voit donc la nécessité d'un système de gestion de l'accès à une mémoire partagée entre deux tâches ou plus.

Pour résoudre ce genre de problème, une possibilité est d'utiliser des verrous, c'est-à-dire de pouvoir bloquer, en une seule instruction, tous les processus tentant d'accéder à une donnée jusqu'à ce que le verrou soit libéré. Cette technique ralentit ainsi l'exécution parallèle, et est parfois source de bugs : si on a deux taches nécessitant deux variables, et que la première tâche verrouille la première variable pendant que la seconde tâche verrouille la seconde variable, alors les deux tâches seront indéfiniment bloquées dans ce que l'on appelle une « étreinte fatale », ou « deadlock » en anglais.

Certaines méthodes de programmation appelées « Non-blocking synchronization » cherchent à éviter d'utiliser ces verrous. Elles sont néanmoins encore plus difficiles à mettre en œuvre et nécessitent la mise en place de structures de données très particulières.

Les systèmes d'exploitation modernes parviennent à contourner le problème en évitant soigneusement toute interférence d'un processus sur l'autre. Ce contrôle implique une gestion draconienne de l'ensemble des ressources d'un ordinateur en amont de la mémoire. Cela signifie cependant qu'une tâche d'une machine d'un premier type ne peut partager une mémoire avec une tâche d'une machine d'un second type sans utiliser un mécanisme d'interface complexe. On dit en effet que la gestion de mémoire est « machine-dépendante ».

Le seul mécanisme « machine-indépendant » et normalisé qu'il existe à l'heure actuelle est IPC (Inter-Process Communication). Cependant, IPC trouve sa limite dans le paramétrage du noyau du système d'exploitation. En effet, en général IPC est limité à la gestion de 4096 blocs de taille maximale de 32 Mo, et à 1656 files de messages pour une distribution de Linux. Cela est insuffisant pour partager les mémoires de plus d'une dizaine de machines interconnectées par un bus applicatif.

Par ailleurs il existe une API (interface de programmation) réservée au calcul scientifique et au HPC (Hight Performance Computing) dénommée OpenMP qui est du type SPMD (Single Programme Multiple Data), c'est-à-dire que OpenMP ne s'applique qu'entre les tâches d'une même application. Bien que basée sur le multi-threading, OpenMP n'a pas de solution pour le parallélisme sur une architecture distribuée, et n'a pas de solution pour la parallélisation automatique. Elle demande au programmeur de prendre les précautions nécessaires concernant les synchronisations et les étreintes fatales éventuelles. Cette API nécessite un complément comme MPI (Message Passing Interface) mais qui est elle- même machine dépendante.

Il y a donc un besoin en un nouveau procédé machine-indépendant de gestion sécurisée d'une mémoire partagée qui soit bien plus efficace et flexible que les techniques connues.

PRESENTATION DE L'INVENTION La présente invention vise à résoudre ces difficultés en proposant un procédé d'utilisation par une tâche d'une mémoire partagée entre une pluralité d'unités de traitement de données connectées par un bus applicatif, ladite tâche étant exécutée par l'une des unités de traitement de données, le procédé étant caractérisé en ce qu'il comprend des étapes de :

(a) Affectation par le bus applicatif à la tâche d'un triplet de ressources comprenant un sémaphore, une zone de mémoire partagée et une file d'attente, le sémaphore indiquant un état de blocage de la tâche, la zone de mémoire partagée étant une partition d'un premier bloc de mémoire partagée, un descripteur de la zone de mémoire partagé étant stocké dans un deuxième bloc de mémoire partagé, ledit deuxième bloc étant dédié au stockage de descripteurs du premier bloc de mémoire partagée. (b) Lorsque le bus applicatif constate que ladite zone de mémoire partagée affectée est libre et/ou que la tâche est passée en tête de la file d'attente, modification du sémaphore de sorte à indiquer un état de libération de la tâche;

(c) Utilisation par l'unité de traitement de données de ladite zone de mémoire partagée affectée pour l'exécution de la tâche ;

(d) Libération de l'espace du second bloc de mémoire partagée alloué au stockage du descripteur de la zone de mémoire partagée.

Selon d'autres caractéristiques avantageuses et non limitatives de l'invention :

• la partition du premier bloc affectée en tant que zone de mémoire partagée pour la tâche est générée dynamiquement en fonction d'une taille d'espace mémoire demandée par l'unité de traitement de données ;

• le premier bloc de mémoire partagée est structuré en un ensemble d'unités de taille égale appelées « pages » référencées chacune par un indice, la partition de la mémoire partagée affectée en tant que zone de mémoire partagée pour la tâche étant un ensemble de pages, ledit descripteur de la zone de mémoire partagée étant une table de pages contenant les indices des pages composant ladite partition ;

• une table de pages contenant les indices des pages composant une partition est représentée dans le second bloc de mémoire par une liste chaînée de couples, chaque couple comprenant un indice de page et le déplacement mémoire à effectuer dans le second bloc pour atteindre le prochain couple de la liste chaînée ;

• l'étape (a) comprend l'obtention d'un triplet d'identifiants à partir d'une clé IPC, le triplet de ressources affecté à la tâche étant identifié par le triplet d'identifiants ;

· chaque identifiant est un nombre entier unique pour chaque type de ressource du triplet ; • la tâche est associée à une première instruction et une deuxième instruction, la première instruction étant une instruction non-bloquante de demande de l'exécution de la tâche et la deuxième instruction étant une instruction bloquante de retour du résultat de l'exécution de la tâche, l'étape (a) étant mise en œuvre suite au lancement de la première instruction, et l'étape (d) étant mise en œuvre suite au lancement de la seconde instruction.

Selon un deuxième aspect, l'invention concerne un procédé d'exécution parallèle d'un processus informatique par une pluralité d'unités de traitement de données connectées par un bus applicatif, le processus étant écrit sous la forme d'un enchaînement de tâches, chaque tâche étant une action élémentaire exécutable par une unité de traitement donnée à laquelle ledit bus applicatif est connecté, les tâches étant ordonnées en fonction d'éventuelles contraintes de dépendance vis-à-vis d'autres tâches, la méthode d'exécution parallèle respectant l'ordre indiqué par la table d'ordonnancement, l'exécution de chaque tâche comprenant la mise en œuvre du procédé d'utilisation par la tâche d'une mémoire partagée par lesdites d'unités de traitement de données selon le premier aspect de l'invention.

Selon d'autres caractéristiques avantageuses et non limitatives de l'invention :

• l'exécution d'une pluralité de tâches (T) comprend la mise en œuvre du procédé d'utilisation par la tâche d'une mémoire partagée par lesdites d'unités de traitement de données selon le premier aspect de l'invention, le lancement de la deuxième instruction d'une telle tâche (T) étant fait de façon synchrone avec la demande d'exécution d'une deuxième tâche (T2) ayant une contrainte de dépendance vis-à-vis de la première tâche (T). Selon un troisième aspect, l'invention concerne un système comprenant une pluralité d'unités de traitement de données mettant en œuvre le procédé selon le premier ou le deuxième aspect de l'invention, au moins une mémoire connectée à une unité de traitement de données, et une entrée recevant la pluralité de tâches à exécuter.

PRESENTATION DES FIGURES

D'autres caractéristiques et avantages de la présente invention apparaîtront à la lecture de la description qui va suivre d'un mode de réalisation préférentiel. Cette description sera donnée en référence aux dessins annexés dans lesquels :

- la figure 1 a représente une architecture de bus applicatif ;

- la figure 1 b représente une architecture de terminal de bus applicatif ;

- la figure 2 représente le passage d'une clé IPC vers un triplet d'identifiants de ressources IPC ;

- la figure 3 représente un exemple de premier bloc illustrant le phénomène de fragmentation ;

- la figure 4a représente un exemple de premier bloc paginé et le deuxième bloc associé ;

- la figure 4b illustre le problème du compactage dans le deuxième bloc de la figure 4a ;

- la figure 5 représente le mécanisme de demande/réponse sur un canal automatiquement synchronisé.

DESCRIPTION DETAILLEE D'UN MODE DE REALISATION

Architecture de bus applicatif

En référence aux figures, le procédé d'utilisation par une tâche d'une mémoire partagée selon l'invention se fait via un bus applicatif. A l'instar des ESB (bus de services d'entreprise), ce bus a avant tout pour fonction de permettre la communication des applications qui à la base ne sont pas pensées pour fonctionner ensemble.

L'architecture du Bus Applicatif (BA) est physiquement répartie sur une constellation de machines. Elle comporte avantageusement les éléments logiciels suivants :

• le Noyau du Bus Applicatif (NBA) idéalement hébergé par une machine dédiée (il n'est pas obligatoire pour les petites et moyennes configurations), chargé de dispatcher et d'ordonnancer les commandes et échanges de données en fonction des priorités, · un Multiplexeur de Bus Applicatif (MBA) par système d'exploitation (en d'autres termes par machine hôte), gérant les ressources partagées (en particulier la ou les unités de traitement, l'espace mémoire, etc.),

• un Terminal de Bus Applicatif (TBA) par application, ce terminal pouvant être un Terminal Maître (Tm) si l'application est directrice ou un Terminal Esclave (Ts) si l'application est contrôlée.

Comme représenté sur la figure 1 a, un bus applicatif peut être interconnecté à un ou plusieurs autres bus via leur noyau (NBA) respectif. Une constellation de machines gérée par un BA sans noyaux ne peut pas être reliée à une autre constellation. Les connexions sont par exemple mise en œuvre sous protocole standard (TCP/IP, ...) avantageusement via des ports facilement admis par les pare-feu, serveurs de domaines et passerelles classiques, sous procédure hautement sécurisée.

Au niveau d'une machine, le BA n'est accessible par une application que via un TBA connecté au MBA local, comme représenté par la figure 1 b.

Chaque application peut lancer des threads et demander au BA de leur fournir également un terminal dédié ce qui permet à deux threads d'interagir.

D'un point de vue pratique chaque terminal est capable d'exploiter en parallèle des demandes-réponses sur des canaux différents. Une « pompe à messages » dédiée permet à ce terminal de prévenir de l'arrivée de données sur tel ou tel canal en provenance de tel ou tel autre terminal. Des applications récentes et/ou adaptées au BA (applications « natives ») peuvent communiquer avec lui en direct au niveau du TBA. Alternativement, les anciennes applications qui ne connaissent pas ce BA sont avantageusement prises en charge (applications « pilotées ») par des interfaces spécifiques de chacune de ces applications, chargées de leur offrir l'adaptation spécifique leur permettant d'intégrer un TBA : les CIA (communication interactive par automate). Un CIA est une sorte de pilote d'accueil disposant des ressources nécessaires aux applications connectées aux terminaux de bus.

Chaque TBA dispose d'une pluralité de canaux de communication avec son application, canaux via lesquels sont faites les demandes d'exécution d'une tâche et le retrait des réponses. A chaque type de demande/réponse, on associe un canal unique. De cette manière, plusieurs échanges peuvent se dérouler en parallèles puisque les canaux seront complètement indépendants.

Le BA offre ainsi la possibilité d'un traitement massivement parallèle de tout processus dont l'exécution est demandée dans un environnement multi-machines multi-cœurs indépendamment des systèmes d'exploitation.

Au niveau local de chaque machine, la communication et l'échange de données entre les différents processus est basée sur le standard IPC.

Ressources IPC

La solution IPC pour le partage sécurisé d'une information nécessite un triplet de « descripteurs » de la tâche :

• Une mémoire proprement dite (en d'autres termes un « bloc »), de longueur quelconque,

• Un dispositif de demande d'accès composé d'une queue de message (où les tâches demanderesses viennent « prendre leur tour » en file d'attente),

• Un dispositif d'autorisation d'accès et de synchronisation : « un sémaphore ». Le fonctionnement d'un triplet décrit ci-avant est le suivant : la tâche désireuse d'utiliser une mémoire dépose sa demande dans la file d'attente correspondante. Elle spécifie l'action (lecture/écriture) et le sémaphore de protection, sorte de feu rouge/vert qui permet de savoir si la mémoire peut être lue/écrite. La tâche est bloquée par ce sémaphore et n'est débloquée par le BA qui libère le sémaphore que lorsque la mémoire est prête à être utilisée et/ou que c'est le tour de la dite tâche d'y accéder.

Si IPC est actuellement insuffisant pour gérer plus d'une dizaine de machines, c'est que les procédés actuels d'utilisation de la mémoire utilisent un triplet par canal.

A supposer une constellation de 10 machines Linux ayant en moyenne 4 TBA offrant chacun eux-mêmes 40 canaux, on obtient un besoin de 1600 blocs de mémoire et autant de sémaphores et files d'attentes. Or ce sont ces dernières qui posent problème, puisque la limite maximum de files de messages est de 1649. On remarque également que plus du tiers du nombre maximum (4096) de blocs mémoires sont déjà utilisés, alors que dans la majorité des cas seule une infime fraction de leur espace alloué est réellement exploitée.

Bien entendu les limites indiquées sont ajustables pour tous les systèmes : on peut modifier ces valeurs et recompiler le noyau du SE. Mais cette manipulation et les dangers qu'elle présente laisse démunis les utilisateurs qui sont très rarement spécialistes des systèmes d'exploitation et bien plus préoccupés par leur processus métier.

Le procédé selon l'invention vise à pouvoir multiplier sensiblement le nombre de machines gérable par IPC sans dépasser pourtant ces limites. L'idée est que tous les canaux d'un TBA se partagent seulement quelques queue de messages, voire une seule, et surtout se partagent la même unique grande mémoire comprenant un ensemble de zones relatives chacune à un canal. La limite en termes de sémaphores (32000) ne pose quant à elle pas de problèmes puisque les sémaphores sont réutilisables.

Ainsi, des constellations de plusieurs centaines de machines deviennent possibles. L'autre grande différence par rapport aux solutions classiques est que le programmeur n'a plus à se soucier ni de sockets, ni de synchronisation ni de gestion des échanges. Le MBA prend tout ceci en charge.

Structure de grande mémoire partagée

Le fait d'avoir une unique file d'attente par TBA ne pose pas de gros problèmes : il suffit que le BA ait instruction de traiter immédiatement toute demande de la part d'une tâche, de sorte à vider la file (qui est de type FIFO) le plus rapidement possible.

En revanche, la gestion « multi-canaux » de la mémoire est plus complexes.

La demanderesse a remarqué que le rapport entre le nombre maximum de files d'attente de messages et celui du nombre de blocs de mémoire partagées est supérieur à deux. Cela permet d'associer à chaque file (et donc à chaque TBA) deux blocs mémoires.

Pour pouvoir mettre en œuvre ce procédé, la mémoire partagée associée à un TBA est composée de deux parties, une partie dédiée au stockage des données des tâches à proprement parler (données sur lesquelles les unités de traitement agissent lors de l'exécution d'une tâche), et une partie dédiée au stockage de descripteurs de la structure de la première partie.

En d'autres termes, le premier bloc associé au TBA est dédié au stockage des données des tâches et il est appelé « bloc de données », et le second bloc associé au TBA est dédié au stockage des descripteurs, et est quant à lui appelé « bloc descriptif ».

Ainsi, au lieu d'associer un bloc mémoire IPC complet à un canal du TBA, on associe une partition du premier bloc, les données permettant d'identifier cette partition (le « descripteur » de cette partition) étant stockées dans le second bloc. Procédé d'utilisation d'une mémoire partagée par une tâche

La première partie du procédé selon l'invention consiste ainsi en l'affectation par le bus applicatif à la tâche d'un triplet de ressources (IPC) comprenant un sémaphore, une zone de mémoire partagée et une file d'attente, le sémaphore indiquant un état de blocage de la tâche, la zone de mémoire partagée étant une partition d'un premier bloc de mémoire partagée, un descripteur de la zone de mémoire partagé étant stocké dans un deuxième bloc de mémoire partagé, ledit deuxième bloc étant dédié au stockage de descripteurs du premier bloc de mémoire partagée.

Lorsque le bus applicatif constate que ladite zone de mémoire partagée affectée est libre (i.e. qu'une tâche précédente n'en a déjà plus besoin) et/ou que la tâche est passée en tête de la file d'attente, le sémaphore est modifié de sorte à indiquer un état de libération de la tâche.

La zone mémoire est alors disponible pour utilisation par l'unité de traitement de données affectée pour l'exécution de la tâche, sans risque que cette utilisation soit perturbée par une autre tâche. Il est à noter que lorsque la mémoire est disponible, elle n'est pas forcément immédiatement utilisée. Par ailleurs, une fois l'exécution de la tâche accomplie, la réponse peut être demandée un peu plus tard. Préparer « à l'avance » les utilisations de mémoire est ainsi une force du procédé selon l'invention. On obtient une accélération effective. Cela sera détaillé davantage dans la suite de la présente description.

L'étape finale du procédé consiste en la libération de l'espace du second bloc de mémoire partagée alloué au stockage du descripteur de la zone de mémoire partagée, afin de nouveau affecté au stockage du descripteur de l'une zone de mémoire partagée qui sera utilisée pour une autre tâche. Affectation d'un triplet de ressources IPC

La gestion de toutes les ressources IPC doit préférentiellement être à la charge d'une seule entité. Cela garantit une gestion homogène par un unique processus créateur. Ce rôle est dévolu au MBA, le multiplexeur du BA.

Pour qu'un processus puisse obtenir une ressource IPC pour chacune de ses tâches, il doit en faire la demande auprès du MBA via un protocole bien défini destiné à optimiser l'utilisation des ressources IPC.

A cette fin, le MBA affecte le triplet de ressources de l'étape (a). On dit que le processus va se loger (login en anglais).

A l'issue de cette demande de logement le processus sera soit refoulé soit accepté. S'il est accepté (login réussi) le MBA va mettre à sa disposition d'un TBA maître (Tm) le triplet.

Le Tm va exploiter ces ressources minimales afin de présenter une collection étendue de canaux logiques d'échanges.

Par ailleurs, tout processus maître logé sur le MBA peut initier d'autres processus dits esclaves qui eux-mêmes peuvent nécessiter un Terminal Esclave (Te) à l'image du Tm. La disparition du maître indique au MBA qu'il peut récupérer les ressources allouées au groupe maître + esclaves.

Une application se loge sur le BA (ensemble des machines reliées par leur MBA). Les applications communiquent entre elles grâce au BA qui gère l'ensemble des ressources partagées.

Par ailleurs, les trois ressources IPC sont avantageusement identifiées par un nombre entier unique au sein du système d'exploitation considéré. Cet identifiant est unique pour chaque type de ressources IPC (sémaphore, mémoire partagée, file de messages). Il peut donc être réutilisé d'un type à l'autre.

Il existe trois façons différentes de générer un identifiant : Identifiant fixe

La façon la plus simple pour plusieurs processus de partager un identifiant est de le fixer. Cependant cette solution est à déconseillée puisque rien ne garantit que cet identifiant ne sera pas utilisé par un processus étranger.

Identifiant calculé par une clé privée

Il est possible de demander au système de calculer un identifiant grâce à une clef. Pour créer une clé en mode privé, il faut passer le drapeau IPC_PRIVATE en premier argument d'une fonction propre au type de ressource IPC et demandant une clef numérique en second argument. Dans ce cas, le système d'exploitation génère automatiquement l'identifiant et garantit son exclusivité.

Néanmoins, le partage de cette ressource reste faisable si le processus créateur met à disposition des autres processus l'identifiant de cette ressource.

Identifiant calculé par une clé dynamique

Si au lieu d'utiliser le drapeau IPC_PRIVATE on donne une clef obtenue par un moyen connu de tous les processus devant partager la ressource, chaque processus pourra alors calculer l'identifiant. C'est la solution avantageusement préférée par l'invention.

Sous Linux, il existe la fonction ftok() qui permet de générer dynamiquement une clé IPC libre en se basant sur deux paramètres : un nom de fichier existant (souvent le nom du projet ou module), et un caractère ascii permettant de singulariser une clef du même module : pour un même nom de fichier, deux clés différentes seront générées ce caractère est différent. Cette fonction rapproche un peu Windows (qui ne travaille qu'avec des noms de fichiers) d'avec Linux.

Que ce soit sous Linux ou sous Windows, la création d'une ressource

IPC nécessite le passage par les deux étapes fondamentales suivantes : Obtention d'identifiant à partir d'une clef (représentée pour le triplet d'identifiants sur la figure 2)

Création de la ressource IPC et obtention d'une référence de la ressource.

L'obtention d'un identifiant est par exemple réalisée par un appel système offert par la bibliothèque Posix IPC (semget, shmget, msgget) ou Windows (CreateSemaphore, MapViewOfFile, CreateMailSIot).

En se basant sur l'identifiant généré dans l'étape précédente, la ressource IPC est créée en passant par une deuxième fonction système réservée à cet effet.

Politiques de partitionnement du premier bloc

Le procédé selon l'invention propose deux politiques différentes de partitionnement d'espace mémoire :

Partitionnement fixe

Cette méthode consiste à diviser l'espace mémoire en plusieurs partitions de même grandeur ou de grandeur différente. La taille et le nombre des partitions sont fixés à l'avance et le partitionnement se fait lors du démarrage du système d'exploitation.

Cette méthode manque beaucoup de flexibilité et cause de la fragmentation interne. En effet, les tailles des mémoires demandées correspondent rarement aux tailles des partitions fixes, et la différence constitue un espace mémoire non exploitable. De plus, si la taille demandée dépasse celle des partitions, des opérations de remplacement de zones mémoires seront envisageables (overlaying).

Partitionnement dynamique

De façon préférentielle la partition du premier bloc affectée en tant que zone de mémoire partagée pour la tâche est générée dynamiquement en fonction d'une taille d'espace mémoire demandée par l'unité de traitement de données.

Le partitionnement dynamique consiste ainsi à créer des zones mémoires qui varient dynamiquement. L'allocation de la mémoire se fait en fonction des demandes de réservation, de libération mais aussi de la taille mémoire disponible. Cette politique d'allocation crée ce qu'on appelle la fragmentation externe, laquelle est due aux partitions non exploitées (la fragmentation interne correspond à la zone libre non exploitée d'une partition, alors que la fragmentation externe correspond aux partitions non attribuées). Néanmoins, l'impact de la fragmentation interne est nettement réduit. La figure 3 illustre le phénomène de fragmentation (interne/externe).

Il est toujours possible de réunir l'ensemble des espaces non exploités en une seule partition, cette technique est connue sous le nom de compaction mémoire. Le compactage de mémoire est fortement déconseillé car il monopolise à la fois : le CPU, La RAM et le bus système durant les opérations de transfert de données.

Politiques d'allocation d'espace mémoire en cas de partitionnement dynamique

Lorsque plusieurs partitions libres sont disponibles, il faut choisir celle qui corresponde au mieux à la demande, si non, créer une nouvelle. Voici quelques exemples d'algorithmes d'allocation : First Fit

On cherche dans la liste des partitions libres la première partition suffisamment grande pour contenir l'espace demandé. Cet algorithme est à la fois rapide et simple à mettre en œuvre mais cause beaucoup de fragmentation externe car les blocs en fin de liste sont difficilement accessibles. Next Fit

Cet algorithme ressemble beaucoup à celui décrit précédemment sauf que la recherche commence depuis la position de la dernière partition choisie.

Best Fit

On cherche la partition dont la taille se rapproche le plus à la taille de l'espace demandé. Cet algorithme a tendance de préserver les grandes partitions au cas où l'on pourrait les exploiter ultérieurement. L'inconvénient de cet algorithme est que la mémoire sera fractionnée en plusieurs petites zones non exploitables.

Worst Fit

On cherche la plus grande partition libre afin d'avoir le plus grand espace non utilisé. Cet espace sera utilisé pour créer des nouvelles partitions.

Buddy System

Cet algorithme considère que les partitions mémoires ont une taille de 2 ⁿ . Lorsqu'il n'y a plus de partions de taille 2 ^x on subdivise une partition de taille 2 ^X+1 , s'il n'y a plus de partitions de taille de taille 2 ^X+1 on découpe une partition de taille 2 ^X+2 et ainsi de suite. Lorsque deux partitions adjacentes de même taille se libèrent, ils seront regroupés en une seule partition de taille deux fois plus grande. Cet algorithme est rapide et constitue un bon compromis entre les avantages et les inconvénients des algorithmes décrits précédemment. Cependant, le fait de devoir arrondir la taille des partitions à une puissance de 2 engendre une certaine fragmentation interne. La table 1 ci-après décrit le déroulement d'un exemple d'une séquence d'allocation mémoire : Taille totale I Mo

Demande A= 1 1 1k 126k 128k 256k 512k

Demande B=230k 128k Î28k 256k 512k

Demande C=52K 128k 64k 64k 256k 512k

Demande D=256k 128k 64k 64k 256k 256k 256k libération B 128k 64k 64k 256k 256k 256k

Libération A 128k 64k 64k 256k 256k 256k

Demande E=80k 128k 64k 64k 256k 256k 256k

Libération C 128k 128k 256k 256k 256k

Libération E 512k 256k 256k libération D IMo

Table 1

Allocation non-contigiie

Les algorithmes vus jusqu'à présent considèrent les partitions comme étant un espace continu. Ces algorithmes engendrent beaucoup de fragmentation interne ou externe. Pour remédier à ce problème, le premier bloc de mémoire partagée est avantageusement structuré en un ensemble d'unités de taille égale appelées « pages » référencées chacune par un indice, la partition de la mémoire partagée affectée en tant que zone de mémoire partagée pour la tâche étant un ensemble de pages, ledit descripteur de la zone de mémoire partagée étant une table de pages contenant les indices des pages composant ladite partition.

En d'autres termes, les espaces d'allocation sont considérés comme étant un espace non-contigu, c'est ce que l'on appelle la pagination.

Le principe de la pagination consiste à structurer l'espace mémoire en un ensemble d'unités de taille égales appelées pages. L'espace mémoire attribué à une partition se composera alors d'un ensemble de pages qui ne sont pas forcément successives. Une partition n'est plus identifiée par son adresse de départ et sa taille mais par l'ensemble des pages qui la compose, ces pages peuvent être organisées sous forme de table appelée table des pages qui décrit la référence à la partition. La figure 4a représente un premier bloc organisé en pages et le second bloc associé.

Le principe de la pagination est souvent combiné avec d'autre notions comme la segmentation (qui permet de regrouper des tables de pages) ou le swaping (utilisation d'espace disque pour chargement et déchargement des pages). Ces techniques constituent les briques de base du concept de mémoire virtuelle qui permet l'exécution des programmes dont la taille dépasse celle de la mémoire réelle. D'une manière générale, l'espace mémoire est souvent mal exploité dans les approches contiguës. En effet, les problèmes de fragmentation interne/externe sont très difficiles à contourner, il y a toujours un compromis entre l'efficacité de l'algorithme déployé et le taux de fragmentation interne/externe. Il n y a pas d'algorithme idéal du moment que l'on se place dans un système fortement dynamique.

Les approches d'allocation non-contigue (à base de pages) permettent une bonne exploitation d'espace d'adressage. Lorsqu'on parle de mémoire virtuelle, la pagination permet aussi :

• Chargement à la demande. Les pages ne sont chargées que lorsqu'elles sont référencées.

• Etendre l'espace d'adressage réel (physique).

• Transparence. L'utilisateur n'a plus à gérer explicitement ses partitions.

La pagination permet d'éliminer complètement le problème de fragmentation externe puisque toutes les pages ont la même taille. Cependant, le problème de fragmentation interne peut se produire dans la dernière page d'une partition si elle n'est pas totalement remplie.

Structure du deuxième bloc

Afin de pouvoir évaluer les performances de notre système, la taille des pages est un critère paramétrable. Sur le plan pratique, la taille des pages est définie en fonction de la taille de données échangées (structures de données). Plus la taille des partitions est petite, plus il y aura de partitions et par conséquent les tables des pages prendront du volume. Il faut toujours trouver le juste milieu entre la taille des pages et la taille globale du premier bloc mémoire IPC.

La navigation dans un bloc mémoire partagée nécessite une connaissance préalable de sa composition : nombre de partitions disponibles, taille des pages mémoires, pages affectées aux partitions allouées, etc. Cette partie constitue la description d'un bloc mémoire, elle peut être soit, intégrée directement dans le même premier bloc (bloc de données), soit intégrée dans le deuxième bloc (bloc descriptif). Chaque partition dans le bloc descriptif correspond comme expliqué à un canal logique.

Mais comme l'on voit sur la figure 4b (qui reprend l'exemple de la figure 4a en cas de suppression du descripteur de la zone de mémoire du premier bloc relative au canal 1 ), la mise en œuvre de l'étape (d) nécessite un compactage mémoire assez lourd si la table des pages d'une partition du premier bloc est elle-même une partition contigue du deuxième bloc.

Le bloc descriptif est avantageusement structuré de manière à éviter au maximum les problèmes liés au compactage de la mémoire, à la fragmentation interne et externe. On évite au maximum le décalage des zones mémoires puisque cette opération est très coûteuse en temps CPU. Pour réaliser cela, une table de pages contenant les indices des pages composant une partition est par exemple représentée dans le second bloc de mémoire par une liste chaînée de couples, chaque couple comprenant un indice de page et le déplacement mémoire (ou « offset ») à effectuer dans le second bloc pour atteindre le prochain couple de la liste chaînée.

La table des pages d'un canal n'est ainsi plus représentée par une partition contigue. Toutes opération de mise à jour sur la partition est faisable par une simple modification des liens de chaînage. Aucun compactage mémoire ne sera alors nécessaire. P-lnstructions

Des méthodes performantes pour découper un processus en une pluralité de tâches et les ordonnancer en vue de leur exécution parallélisée par les différentes unités de traitement de données (processeurs, cœurs, etc.) sont connues. On se référera par exemple aux demandes de brevet FR 2963125 et FR 2963126.

Comme expliqué, la mémoire mise à disposition d'une tâche peut n'être utilisée que bien plus tard, en l'occurrence lorsque l'unité de traitement a effectivement besoin du résultat de la tâche : au moment de la synchronisation. L'utilisation puis la libération de la mémoire peut être vue comme une « réponse » après une « demande ».

Ainsi, un couple d'instructions, appelées « P-instructions », est avantageusement associé à la tâche, la première instruction étant une instruction non-bloquante de demande de l'exécution de la tâche (la « demande ») et la deuxième instruction étant une instruction bloquante de retour du résultat de l'exécution de la tâche (la « réponse »), l'étape (a) étant mise en œuvre suite au lancement de la première instruction, et l'étape (d) étant mise en œuvre suite au lancement de la seconde instruction.

Si on a un processus écrit sous la forme d'un enchaînement de tâches, chaque tâche étant une action élémentaire exécutable par une unité de traitement donnée à laquelle ledit bus applicatif est connecté, les tâches étant ordonnées en fonction d'éventuelles contraintes de dépendance vis-à- vis d'autres tâches, il est possible d'exécuter le processus de façon parallélisée à condition de respecter l'ordre d'ordonnancement pour l'exécution des tâches.

L'invention propose ainsi selon un deuxième aspect un procédé d'exécution parallèle d'un processus informatique par une pluralité d'unités de traitement de données connectées par un bus applicatif, le processus étant écrit sous la forme d'un enchaînement de tâches, chaque tâche étant une action élémentaire exécutable par une unité de traitement donnée à laquelle ledit bus applicatif est connecté, les tâches étant ordonnées en fonction d'éventuelles contraintes de dépendance vis-à-vis d'autres tâches, le procédé d'exécution parallèle respectant l'ordre indiqué par la table d'ordonnancement, l'exécution de chaque tâche comprenant la mise en œuvre du procédé d'utilisation par la tâche d'une mémoire partagée par lesdites d'unités de traitement de données selon le premier aspect de l'invention.

Les P-instructions s'avèrent particulièrement adaptées pour le contrôle de l'enchaînement des tâches, puisqu'il suffit pour obtenir une synchronisation automatique que le lancement de la deuxième instruction d'une tâche (T) soit fait de façon synchrone avec la demande d'exécution (la première instruction dans le cas d'une P-instruction) d'une deuxième tâche (T2) ayant une contrainte de dépendance vis-à-vis de la première tâche (T).

Systèmes

L'invention propose selon un troisième aspect des systèmes pouvant mettre en œuvre les procédés selon le premier ou le deuxième aspect de l'invention.

La première fonctionnalité demandée au bus applicatif est d'assurer l'acheminement de toutes les données entre tous les acteurs de toutes les configurations interconnectées.

Tous les acteurs peuvent être rassemblés dans une seule station, l'unité de traitement du bus applicatif étant celle de la station. Dans ce cas là, le système selon l'invention comprend la station de travail, celle-ci comprenant tout d'abord des moyens d'affichage de données et des moyens de saisie de données. Il peut s'agir classiquement d'un écran et d'un clavier avec une souris. Ce matériel sert tout simplement à mettre en œuvre une ou plusieurs interfaces homme-machine permettant à un utilisateur d'interagir avec le BA, éventuellement en fournissant des processus à exécuter. Le système selon l'invention comprend également une unité de traitement de données, qui est l'unité reliée au bus applicatif, et une mémoire. Pour que le système ait un intérêt, l'unité de traitement doit être de préférence un processeur multicoeur (dans ce cas on la comprendra comme une pluralité d'unité de traitement), c'est-à-dire un processeur qui pourra tirer parti de l'exécution parallèle. La mémoire est avantageusement une unique mémoire partagée.

Cette station de travail héberge le NBA s'il y en a un.

Alternativement le système selon l'invention peut ne pas se contenter d'une seule station de travail, mais comprendre comme expliqué précédemment au moins une machine partenaire. Il peut en outre y avoir plusieurs stations de travail contrôlées par des utilisateurs, les différentes stations ayant chacune une unité de traitement et utilisant les mêmes machines partenaires autour d'un bus applicatif unique.

Le bus applicatif sert de Multiples Stations (usagers) et de Multiples Partenaires (automates) en configuration dite MSMP. Il fonctionne en diverses configurations dites « dégradées » Simple/Multiple Station/Partenaire SSSP, SSMP, MSSP et MSMP. Enfin, le bus applicatif est capable dans toute la mesure du possible de prendre en charge les liaisons du type temps réel nécessaires à certains dispositifs (périphériques, commande de chaînes de production, ...). Il offre ainsi une passerelle entre le monde industriel et le monde du bureau par exemple pour obtenir un tableau temps réel de la production.

Le bus utilise la connectique et les supports physiques existants entre les machines de types habituellement utilisés (serveur de fichiers, serveur Web, Serveur d'applications, etc.). En particulier, deux ports TCP/IP peuvent lui être réservés (12 et 14 ou 3012 et 3014) pour ses communications à débit maximum et optimisé. Les communications sont multiplexées et chaque segment possède une priorité. Les messages de synchronisation des tâches sont les plus prioritaires ainsi que les éventuelles liaisons temps réel.

Les opérations d'ordonnancement du bus applicatif peuvent être le cas échéant traitées par un calculateur, idéalement vectoriel, qui est une unité de traitement de l'une des machines partenaires, qui peut être dédié. Sur de moyennes configurations, une carte graphique située sur un partenaire est utilisée comme GPGPU (General-Purpose computation on Graphics Processing Units). En effet une carte graphique est un calculateur vectoriel complet.

Etant a priori réparti, le bus applicatif fonctionne préférentiellement dans un cadre sécurisé. Le multiplexeur/démultiplexeur est donc muni d'une solide fonction de cryptage. Le système utilisé est un cryptage par clefs aléatoires de longueurs variables et rafraîchies automatiquement. Ainsi toute attaque est déjouée par un changement de clef en un temps plus court que celui demandé par la recherche de clef. Il y a une clef par port et par sens de transmission. La transmission de la nouvelle clef aléatoirement calculée est elle-même sécurisée par la clef précédente. Ainsi, même si la clef initiale (utilisée une unique fois lors du login) est connue, il ne peut être question de pénétrer la suite des échanges.

La solidité de l'ensemble est soumise à un objectif de qualité qui fait que le bus applicatif réalise de façon particulièrement avantageuse un traçage de ses opérations et des transactions. Ce traçage n'est bien entendu pas prioritaire et n'impacte pas les performances de l'ensemble. Il est traité comme une acquisition de données stockées en cache puis sauvegardées dans les temps de plus faible priorité. Un outil annexe peut permettre d'exploiter ces données à la demande et à loisir pour y rechercher l'historique de tout événement ou en extraire toute statistique utile, ou encore permettre le réglage plus précis des paramètres du bus applicatif de façon à en optimiser le fonctionnement pour une configuration donnée.