FR2675923A1

FR2675923A1 - Architecture of massively parallel computer system

Info

Publication number: FR2675923A1
Application number: FR9105100A
Authority: FR
Inventors: Yonter Eric
Original assignee: Individual
Current assignee: Individual
Priority date: 1991-04-25
Filing date: 1991-04-25
Publication date: 1992-10-30

Abstract

La description consiste à exposer une architecture de système de traitement de l'information composée de l'assemblage de processeurs standards connectés en parallèle à travers des CAD (=BUS), sous forme de matrice à deux dimensions. Le système complet et opérationnel peut être composé de 1 ou plusieurs blocs élémentaires (1024 blocs au maximum), chacun ayant au minimum 64 processeurs connectés sous forme de grille bi-dimensionnelle de 8 X 8. L'idée fondamentale sous-jacente à ce système est de réunir dans un ensemble matériel les trois facteurs suivants: - employer des processeurs classiques (standards de l'industrie) en grand nombre, - réaliser des connexions en matrice de rXr (l'exemple de bloc de 64 processeurs est donnée avec r = 8), - utiliser des CAD (chemins d'acheminement des données) parallèles à l'opposé des liaisons séries simples.The description consists in exposing an information processing system architecture made up of the assembly of standard processors connected in parallel through CAD (= BUS), in the form of a two-dimensional matrix. The complete and operational system can be composed of 1 or more elementary blocks (1024 blocks maximum), each having at least 64 processors connected in the form of two-dimensional grid of 8 X 8. The fundamental idea underlying this system is to bring together in a hardware set the following three factors: - use classic processors (industry standards) in large number, - make connections in matrix of rXr (the example of block of 64 processors is given with r = 8), - use parallel CAD (data routing paths) as opposed to simple serial links.

Description

ARCHITECTURE DE SYSTEME INFORMATIQUE MASSIVEMENT
PARALLELE.ARCHITECTURE OF COMPUTER SYSTEM MASSIVELY
PARALLEL.

Introduction
La présente description concerne l'architecture d'un système informatique basée sur la mise en parallèle de processeurs classiques.Introduction
The present description relates to the architecture of a computer system based on the paralleling of conventional processors.

Il existe actuellement cinq grandes tendances concernant la mise en commun de la puissance de traitement des processeurs (figure 1), leur but étant essentiellement d'obtenir, dans la mesure du possible, l'addition (ou l'accumulation) des puissances de traitement réparties sur chaque unité. Ces architectures vont de l'interconnexion des grands systèmes (figure 1.I) jusqu'à la réalisation des machines massivement parallèles à grains très fins (figure 1.V). Dans les modèles intermédiaires, on trouve des systèmes informatiques basés sur l'assemblage des cartes électroniques (figure 1.il), des réseaux de microordinateurs (figure 1.III) et des systèmes basés sur la mise en commun des micro processeurs classiques (figure 1.IV). L'architecture de système parallèle, objet de cet exposé, fait partie du quatrième groupe. There are currently five major trends in the pooling of processing power of processors (Figure 1), their main purpose being to obtain, as far as possible, the addition (or accumulation) of processing power. spread over each unit. These architectures range from the interconnection of large systems (Figure 1.I) to the realization of massively parallel machines with very fine grains (Figure 1.V). In the intermediate models, there are computer systems based on the assembly of electronic cards (Figure 1.il), microcomputer networks (Figure 1.III) and systems based on the pooling of conventional micro processors (Figure 1.IV). The parallel system architecture, which is the subject of this presentation, belongs to the fourth group.

Pour chacune des cinq tendances d'architectures, on considère que l'un des problèmes fondamentaux réside dans la définition d'un modèle d'interconnexion des éléments répartis. For each of the five architectural trends, it is considered that one of the fundamental problems lies in the definition of a model of interconnection of distributed elements.

Le dispositif, selon l'architecture exposée, permet, par un agencement particulier des ses éléments, une nette amélioration des communications qui existent au sein d'un système parallèle. Ainsi, il devient possible de constituer un système parallèle de taille importante, ensuite d'exploiter pleinement la puissance totale d'un tel ensemble. The device, according to the architecture exposed, allows, by a particular arrangement of its elements, a significant improvement in communications that exist within a parallel system. Thus, it becomes possible to constitute a large parallel system, then to fully exploit the total power of such a set.

Description générale d'un système parallèle
Dans le domaine des systèmes informatiques parallèles, une définition complète passe par la mise en évidence des trois entités suivantes
(i)- La description globale du système (ses limites physiques ou spatiales, énumération de son étendue).General description of a parallel system
In the field of parallel computer systems, a complete definition involves highlighting the following three entities
(i) - The overall description of the system (its physical or spatial limits, enumeration of its extent).

(ii)- La description des composantes du système (définition du concept de la taille du grain). (ii) - The description of the system components (definition of the concept of grain size).

(iii)- La modélisation de l'interconnexion de ses éléments (autrement dit, la topologie de l'ensemble). (iii) - The modeling of the interconnection of its elements (in other words, the topology of the set).

Dans la suite de l'exposé, cette division a été retenue. In the remainder of the presentation, this division was retained.

Figure 1 : Représentation de la classification générale et des tendances actuelles des systèmes informatiques parallèles.Figure 1: Representation of the general classification and current trends of parallel computer systems.

Figure 2 : Présentation de la notion de tronçon et la connexion de cellules à un CAD (BUS) parallèle.Figure 2: Presentation of the notion of section and the connection of cells to a parallel CAD (BUS).

Figure 3 : Présentation d'un bloc élémentaire de 64 cellules (matrice de 8 X 8).Figure 3: Presentation of an elementary block of 64 cells (matrix of 8 X 8).

Figure 4 : Illustration détaillée d'un bloc élémentaire de 8 X 8 cellules (dessin allégé).Figure 4: Detailed illustration of an elementary block of 8 X 8 cells (lightened drawing).

Figure 5 : Un système parallèle composé de 256 processeurs par l'assemblage de 4 blocs de 64 processeurs.Figure 5: A parallel system consisting of 256 processors by assembling 4 blocks of 64 processors.

Figure 6 : Représentation d'une cellule, avec son processeur principal, le routeur et le contrôleur de CAD.Figure 6: Representation of a cell, with its main processor, the router and the CAD controller.

Figure 7 : Illustration des cycles au sein d'un bloc de 64 cellules.Figure 7: Illustration of the cycles within a block of 64 cells.

Figure 8 : Dessin permettant de voir la succession des événements qui se déroulent pendant une phase de communication.Figure 8: Drawing to see the sequence of events that take place during a communication phase.

La description globale du système parallèle
Le système parallèle est un ensemble informatique homogène composé de cellules autonomes et interconnectées. Le premier niveau de groupage des cellules constitue les blocs élémentaires.The overall description of the parallel system
The parallel system is a homogeneous computer set composed of autonomous and interconnected cells. The first level of grouping of cells constitutes the elementary blocks.

1-1 Définition du terme "cellules autonomes" : c'est une structure informatique proche d'une station de travail ou d'un micro-ordinateur personnel avec des fonctionnalités réduites. 1-1 Definition of the term "autonomous cells": it is a computer structure close to a work station or a personal microcomputer with reduced functionalities.

1-2 Définition du mot "interconnectées" : qui consiste en une description de la topologie de l'interconnexion et la nature de l'acheminement des données (qui constitue l'essentiel de cet expose). 1-2 Definition of the word "interconnected": which consists of a description of the topology of the interconnection and the nature of the routing of the data (which constitutes the essence of this exposition).

1-3 Le système parallèle est composé de plusieurs cellules dont le nombre Cn est, d'une façon très générale, donné par l'expression suivante Cn = rt X (2P avec r et n où,
Cn = le nombre total de cellules du système
r = nombre de cellules dans une matrice ou un bloc
avec 8( r 416
(à titre d'exemple, on posera r = 8)
n = un nombre entier quelconque compris entre
Ofn #5
1-4 Dans la pratique, la taille du système parallèle est une des lignes du tableau suivant. Dans ce tableau, on pose r = 8.

1-3 The parallel system is composed of several cells whose number Cn is, in a very general way, given by the following expression Cn = rt X (2P with r and n where,
Cn = the total number of cells in the system
r = number of cells in a matrix or block
with 8 (r 416
(for example, we will ask r = 8)
n = any integer between
Ofn # 5
1-4 In practice, the size of the parallel system is one of the lines in the following table. In this table, we put r = 8.

modèle <SEP> nombre <SEP> de <SEP> i <SEP> <SEP> nombre <SEP> de <SEP> le <SEP> système <SEP> est
<tb> <SEP> processeurs <SEP> blocs <SEP> de <SEP> 64 <SEP> une <SEP> matrice <SEP> de
<tb> <SEP> processeurs
<tb> B1 <SEP> <SEP> - <SEP> 64 <SEP> 1 <SEP> n=O <SEP> i <SEP> <SEP> 8 <SEP> x <SEP> 8
<tb> B4 <SEP> 256 <SEP> 4 <SEP> n=1 <SEP> 16 <SEP> X <SEP> 16
<tb> B16 <SEP> 1024 <SEP> 16 <SEP> n=2 <SEP> 32 <SEP> X <SEP> 32
<tb> B64 <SEP> 4096 <SEP> 64 <SEP> n=3 <SEP> 64 <SEP> X <SEP> 64
<tb> B256 <SEP> 16384 <SEP> 256 <SEP> n=4 <SEP> 128 <SEP> X <SEP> 128
<tb> B1024 <SEP> 65536 <SEP> 1024 <SEP> n=5 <SEP> 256 <SEP> X <SEP> 256
<tb> <SEP> /processeurs <SEP> /blocs <SEP> /processeurs
<tb>
1-5 Le système parallèle est un assemblage de 1 à 1024 blocs élémentaires, chaque bloc étant constitué de r X r processeurs (64 minimum). Le paramètre r est un élément clé; en effet, il désigne le nombre de processeurs montés en parallèle sur un même CAD (=BUS) physique (figure 2). Dans la suite, ce groupage est appelé un "tronçon". Dans un système parallèle, il en existe deux types identiques: les tronçons verticaux et les tronçons horizontaux.model <SEP> number <SEP> of <SEP> i <SEP><SEP> number <SEP> of <SEP> The <SEP> system <SEP> is
<tb><SEP> processors <SEP><SEP> blocks of <SEP> 64 <SEP> a <SEP><SEP> array of
<tb><SEP> processors
<tb> B1 <SEP><SEP> - <SEP> 64 <SEP> 1 <SEP> n = O <SEP> i <SEP><SEP> 8 <SEP> x <SEP> 8
<tb> B4 <SEP> 256 <SEP> 4 <SEP> n = 1 <SEP> 16 <SEP> X <SEP> 16
<tb> B16 <SEP> 1024 <SEP> 16 <SEP> n = 2 <SEP> 32 <SEP> X <SEP> 32
<tb> B64 <SEP> 4096 <SEP> 64 <SEP> n = 3 <SEP> 64 <SEP> X <SEP> 64
<tb> B256 <SEP> 16384 <SEP> 256 <SEP> n = 4 <SEP> 128 <SEP> X <SEP> 128
<tb> B1024 <SEP> 65536 <SEP> 1024 <SEP> n = 5 <SEP> 256 <SEP> X <SEP> 256
<tb><SEP> / <SEP> processors / <SEP> blocks / processors
<Tb>
1-5 The parallel system is an assembly of 1 to 1024 elementary blocks, each block consisting of r X r processors (64 minimum). The parameter r is a key element; indeed, it designates the number of processors mounted in parallel on the same physical CAD (= BUS) (FIG. 2). In the following, this grouping is called a "section". In a parallel system, there are two identical types: the vertical sections and the horizontal sections.

1-6 Sur le dessin de la figure 2, on constate deux ouvertures Oa et Ob partant des cellules situées aux bords du bloc. Ces tronçons sont du même type (et de même constitution) que les tronçons centraux. 1-6 In the drawing of Figure 2, there are two openings Oa and Ob starting cells located at the edges of the block. These sections are of the same type (and of the same constitution) as the central sections.

1-7 En d'autres termes et pour lever toute ambiguïté, un tronçon est constitué de l'attachement en parallèle de r cellules sur un même CAD parallèle dont la description détaillée est donnée dans la suite. 1-7 In other words and to remove any ambiguity, a section consists of the parallel attachment of r cells on the same parallel DAC whose detailed description is given below.

1-8 Le plus petit élément du système parallèle est constitué d'un bloc en une grille bi-dimensionnelle de rXr cellules. La figure 3 illustre un bloc de 64 cellules. 1-8 The smallest element of the parallel system consists of a block in a two-dimensional grid of rXr cells. Figure 3 illustrates a block of 64 cells.

1-9 La synthèse des définitions des paragraphes 1-5, 1-6, 1-7 et 1-8 nous donne un ensemble minimum de 64 processeurs montés en grille bi-dimensionnelle à travers une interconnexion (ou chemin d'acheminement des données) parallèle (figure 4). Cette figure est allégée et réduite à un ensemble de 9 processeurs alors qu'elle représente un bloc de 64 processeurs. 1-9 The synthesis of the definitions in paragraphs 1-5, 1-6, 1-7, and 1-8 gives us a minimum set of 64 processors mounted in a two-dimensional grid across an interconnection (or data path) ) parallel (Figure 4). This figure is lightened and reduced to a set of 9 processors while it represents a block of 64 processors.

1-10 Les modèles de système parallèle proposés au paragraphe 1-4 sont constitués d'un multiple des blocs de 64 processeurs. La figure 5 illustre un exemple de système de 256 processeurs par l'adjonction de 4 blocs élémentaires de 64 processeurs chacun. 1-10 The parallel system models proposed in paragraph 1-4 consist of a multiple of blocks of 64 processors. FIG. 5 illustrates an example system of 256 processors by the addition of 4 elementary blocks of 64 processors each.

1-11 D'après le dessin de la figure 4, on constate qu'il existe 3 types de cellules différentes. 1-11 From the drawing in Figure 4, we see that there are 3 different types of cells.

(i) Cellules qui gèrent 4 CAD (situées aux 4 coins d'un bloc). (Figure 4, élément noté 1). (i) Cells that manage 4 CAD (located at the 4 corners of a block). (Figure 4, item rated 1).

(ii) Cellules qui gèrent 3 CAD (situées sur les bords d'un bloc, sauf aux coins). (Figure 4, élément 2). (ii) Cells that manage 3 CAD (located on the edges of a block, except at the corners). (Figure 4, item 2).

(iii) Cellules qui ne gèrent que 2 CAD (toutes celles qui ne rentrent ni dans la définition (i), ni dans la définition (ii) ). (Figure 4, élément 3). (iii) Cells that only manage 2 CAD (all those that do not fit either the definition (i) or the definition (ii)). (Figure 4, item 3).

Dans les trois cas de figure que l'on vient de décrire, il s'agit d'une structure de CAD identique. In the three cases that have just been described, it is an identical CAD structure.

2
Les composantes du système parallèle
2- Immédiatement en-dessous de la description du système parallèle, on trouve la définition des cellules à proprement dit.2
The components of the parallel system
2- Immediately below the description of the parallel system is the definition of the cells themselves.

2-1 Une cellule est le plus petit élément inseccable, autonome et communiquant d'un système parallèle. Un bloc de taille rXr est compose, dans l'exemple donné, de 64 cellules (figure 3). 2-1 A cell is the smallest element of excellence, autonomous and communicating a parallel system. A block of size rXr is composed, in the example given, of 64 cells (Figure 3).

2-2 Une cellule dispose de 2 fonctionnalités fondamentales
(i) La puissance de traitement (au sens informatique du terme, exemple à base de micro processeurs de 8, 16 ou 32 bits). 2-2 A cell has 2 basic features
(i) The processing power (in the computer sense of the term, example based on micro processors of 8, 16 or 32 bits).

(ii) La gestion des fonctions de routage des informations pour acheminer des données entre les cellules. (ii) Managing information routing functions to route data between cells.

2-3 La puissance de traitement est assurée par une unité centrale, un FPU (unite de calcul en virgule flottante), une mémoire vive et une mémoire morte. 2-3 The processing power is provided by a CPU, an FPU (Floating Point Unit), a RAM and a ROM.

2-4 La partie "routeur" est constituée d'un gestionnaire de CAD (gérant 4 CAD au maximum). Le routeur (figure 6, élément 1), d'un point de vue fonctionnel, est situé entre le processeur principal (figure 6, élément 2) de la cellule et le réseau de 4 ou 3 ou 2 CAD, selon le cas (figure 6, élément 3). Les fonctionnalités du routeur peuvent être assurées par un ou plusieurs boîtiers selon la disponibilité et le degré d'intégration envisageables. 2-4 The "router" part consists of a CAD manager (managing up to 4 CAD). The router (FIG. 6, element 1), from a functional point of view, is located between the main processor (FIG. 6, element 2) of the cell and the network of 4 or 3 or 2 CAD, as the case may be (FIG. 6, item 3). The functionality of the router can be provided by one or more boxes depending on the availability and degree of integration possible.

2-5 Un routeur assure la gestion des accès au CAD du processeur de la cellule ainsi que l'acheminement des données qui transitent éventuellement par son intermédiaire au sein du système parallèle (figure 6). 2-5 A router manages access to the DAC of the cell's processor as well as the routing of data that may pass through it through the parallel system (Figure 6).

3
La description de l'interconnexion
Dans cette partie et conformément à la partie "introduction", on expose une description de la connexion parallèle (CAD).3
The description of the interconnection
In this part and in accordance with the "introduction" part, a description of the parallel connection (CAD) is exposed.

3-1 Le CAD parallèle est composé de deux groupes de signaux. 3-1 The parallel DAC is composed of two groups of signals.

3-1-1 Signaux véhiculant les données (au nombre de 16 lignes). 3-1-1 Signals carrying the data (16 lines in total).

-DB0 à -DB15 Signaux de données et de commandes. -DB0 to -DB15 Data signals and commands.

3-1-2 Signaux de contrôle des activités du CAD, au total 10 lignes. 3-1-2 DAC Activity Control Signals, total 10 lines.

(Signaux actifs à l'état bas, d'où la présence d'un signe de soustraction devant chaque abréviation). (Active signals in the low state, hence the presence of a sign of subtraction in front of each abbreviation).

-RST Signal de remise à zéro. -RST Reset signal.

-INT Signal généré par un routeur pour attirer l'attention des autres routeurs d'un même tronçon. -INT Signal generated by a router to attract the attention of other routers of the same section.

-REQ Signal d'encadrement de transmission des données généré par le routeur destinataire. -REQ Data transmission framing signal generated by the destination router.

-ACK Signal d'encadrement de transmission des données généré par le routeur initiateur. -ACK Data transmission framing signal generated by the initiating router.

-so -S1

Avec le signal S1 ils définissent la nature des signaux présents sur le CAD de données.With signal S1 they define the nature of the signals present on the data CAD.

-BSY Signal d'occupation du CAD. -BSY DAC occupancy signal.

-A Ligne réservée pour les extensions futures. -A Reserved line for future extensions.

-B Ligne réservée. -B Reserved line.

-C Ligne réservée. -C Reserved line.

Tous ces signaux sont bidirectionnels ( ils peuvent être générés soit par le routeur initiateur, soit par le routeur destinataire). All these signals are bidirectional (they can be generated either by the initiating router or by the destination router).

3-2 Lorsqu'un routeur accède au CAD, il peut soit émettre un message unitaire, de longueur variable, destiné à un autre routeur (message individuel), soit émettre un message pour une diffusion générale (message destiné à l'ensemble des routeurs d'un tronçon). 3-2 When a router accesses the DAC, it can either send a unitary message, of variable length, intended for another router (individual message), or send a message for a general broadcast (message intended for all the routers of a stretch).

3-2-1 Les activités relatives à la communication sont indépendantes des activités des processeurs principaux qui constituent le noyau des cellules. 3-2-1 The communication activities are independent of the main processor activities that form the core of the cells.

3-3 Description du protocole des échanges sur le CAD (le fonctionnement du CAD). 3-3 Description of the DAC exchange protocol (the operation of the DAC).

3-3-1 Le protocole qui gère les échanges est du type déterministe, c'est-à-dire qu'il n'existe pas de collision aléatoire sur le CAD. 3-3-1 The protocol that manages the exchanges is of the deterministic type, that is to say that there is no random collision on the CAD.

3-3-2 A partir de la mise sous tension, le routeur de la cellule 0,0 (cellule placée en haut à gauche de chaque bloc de rXr comme décrit au paragraphe 1-8, voir également les figures 3 et 4) initie un cycle qui est décrit de la façon suivante
(i) Un cycle est une suite de séquences d'activités d'accès au CAD (les phases) par les routeurs montés en parallèle sur le-dit CAD.3-3-2 From power-up, the 0.0 cell router (cell located at the top left of each rXr block as described in paragraph 1-8, see also Figures 3 and 4) initiates a cycle that is described as follows
(i) A cycle is a sequence of CAD access activity sequences (phases) by the routers connected in parallel on the so-called CAD.

(ii) Chaque routeur accède à son tour au CAD même en l'absence de message à transmettre et passe explicitement le contrôle au routeur suivant. (ii) Each router in turn accesses the DAC even in the absence of a message to be transmitted and explicitly passes control to the next router.

(iii) A la fin de l'accès du dernier routeur d'un tronçon, le contrôle revient vers la cellule (0,0) du bloc. (iii) At the end of the access of the last router of a section, the control returns to the cell (0,0) of the block.

(iv) La cellule (0,0) est chargée d'initier deux cycles indépendants
-Un cycle pour le tronçon horizontal.(iv) The cell (0,0) is responsible for initiating two independent cycles
-A cycle for the horizontal section.

-Un cycle pour le tronçon vertical. -A cycle for the vertical section.

(v) Au bout d'un certain temps de fonctionnement, du fait de la taille variable des blocs de données, il n'existe plus de synchronisation possible entre les cycles des divers tronçons (figure 7). (v) After a certain time of operation, because of the variable size of the data blocks, there is no longer any possible synchronization between the cycles of the various sections (FIG. 7).

Le dessin de la figure 7 illustre un bloc de 8x8 cellules sur lequel il existe 16 cycles indépendants. The drawing of Figure 7 illustrates a block of 8x8 cells on which there are 16 independent cycles.

3-4 Etude d'une phase
Une phase est constituée d'un certain nombre de signaux générés par un routeur pour gagner le contrôle du
CAD, transférer des données et en finir en relâchant ledit CAD.3-4 Study of a phase
A phase consists of a number of signals generated by a router to gain control of the
CAD, transfer data and finish by releasing the CAD.

Donc une phase est entourée de 2 états du type "CAD libre", situés au début et à la fin de la phase. So a phase is surrounded by 2 states of the type "free CAD", located at the beginning and at the end of the phase.

Schématiquement, la succession des événements est donnée dans le dessin de la figure 8. Les trois colonnes représentent, de la gauche vers la droite, l'activité d'un routeur initiateur, les réactions d'un routeur destinataire et enfin les réactions des autres routeurs présents au même moment sur le CAD. Schematically, the sequence of events is given in the drawing of Figure 8. The three columns represent, from left to right, the activity of an initiating router, the reactions of a destination router and finally the reactions of others routers present at the same time on the CAD.

Claims

1- It is a basic block of computer system architecture characterized,

in that it consists of a certain number of conventional processors (currently available standard products of 8, 16 or 32 bits) whose number lies in a range of 64 to 256 elements,

in that the arrangement of these processors (or their positioning in space with respect to one another) is in the form of a two-dimensional grid (that is to say a matrix),

in that the communications between the said processors are carried out through a parallel CAD (= BUS).

2- A computer system architecture characterized

in that it consists of a number of elementary blocks according to claim 1, whose number is between 1 and 1024,

in that the arrangement of these elementary blocks constitutes a two-dimensional grid,

in that the communications between these blocks take place through a parallel DAC.