Brevet FR2308141A1 — publié le 19761112

La présente invention a pour objet un système de manipulation: d'un fichier d'informations en vue de son reclassement, Un tel fichier se présente sous la forme d'une suite, désordonnée à un degré plus ou moins grand, de codes d'éléments, ou articles, qu'il 8 sagit de faire reclasser par les moyens automatiques dont peut disposer un équipement de traitement de données classique, Un tel outil est doté dXune unité centrale qui, sur exécution d'un programme, peut commander la lecture d'informations codées présentes sur un support externe, un flpériphériquell, et entrer ces informations en une mémoire centrale de l'unité* Pour les fichiers, ce périphérique est tel qu'une bande magnétique dont la lecture ne peut s'effectuer que par séquences, d'un bloc de données chacune, introduites dans la mémoire centrale par l'intermédiaire d'un tampon de la capacité d'un bloc. Après quoi, ou plus précisément au fur et à mesure du remplissage de la mémoire centrale par des transferts successifs des contenus consécutifs du tampon, l'unité centrale commande le traitement des informations et ceci en ayant la possibilité de faire appel à des mémoires auxiliaires, constituant alors des "supports de manoeuvre" et qui consistent en d'autres périphériques, disques ou tambours magnétiques notamment, qui sont eux dtun type à possibilité d'accès direct, à savoir qulils sont adressables sinon par emplacement individuel d'information codée mais tout au moins par zones.Dans le cas des périphériques à disques magnétiques, chaque zone est usuellement dite un "cylin- dre ou un "secteur de cylindre. Un périphérique de ce genre comporte une pluralité de disques, cnregistrés le plus souvent en double-face, chaque face étant équipée d'un groupe de têtes d'écriture-lecture et ces groupes de têtes étant, en commun, liés à des bras qui peuvent les déplacer dans la direction radiale. L'accès de ce périphérique incorpore un tampon. Un programme de traitement et manipulation de fichiers est, de façon générale, établi pour "trier" les informations codées de ses articles selon certains critères et les ordonner selon une séquence pré-définie des dits critères. Après le tri, le fichier remis en ordre est transféré sur un support externe final, un peri- phérique de même nature que celui dont il a été extrait. Usuellement, les critères susdits se réduisent à un seul, à savoir une clé de classification dont le code existe en celui de chaque information identifiant un article du fichier lu et qui accompagnera l'information tout au long de sa manipulation et de sa "recopie". Le rendement, d'un autre point de vue l'économie, d'un système de ce genre peut s'estimer en considérant deux données principales, à savoir le temps total d'occupation de l'unité centrale et la durée d'occupation de la mémoire centrale de données de la dite unité. Le temps d'occupation de l'unité centrale peut être réduit dans les équipements qui sont dotés de mémoires de travail, microprogrammées par exemple. Un microprogramme de tri selon un al gorithme répétitif libère l'unité centrale après appel à une telle mémoire de travail opérant en microprocesseur et transfert de la commande à ce processeur auxiliaire. La durée d'occupation de la mémoire de données est donc le facteur le plus important car cette mémoire doit être normalement partagée entre plusieurs taches dont les exécutions sont régies par l'unité centrale à travers ces microprocesseurs.Un fichier usuel dépasse la capacité dé la mémoire de données, ou tout au moins l'atteint0 Il serait donc particulière- ment avantageux, et c'est là un des buts de l'invention, d'établir un système de manipulation de fichier qui réduise au mieux les temps d"occupation de la mémoire centrale, Or, le système présentement utilisé le plus souvent pour la manipulation d'un fichier en vue du reclassement des articles qut il contient ne parait pas satisfaire R une telle condition.Ce système débute par la création, à partir des informations lues, de monotonies, c'est à dire d'ensembles non-disjoints et strictement ordonnés des articles du fichier, C'est là une opération de tri interne qui occupe entièrement la mémoire centrale meme si elle recourt ,pour la facilité, à des supports de manoeuvre. Elle néces-site en effet l'accès à tout instant à l'ensemble des informations déjà lues, même alors que ces informations ont été reclassées à un Certain degré. A cette opération, ou phase, de tri interne, qui se présente usuellement sous la forme d'un tournoi avec remplacement, le micro programme fait succéder une phase de fusion des monotonies, opérant en autant de passes que de besoin jusqutà la création d'une monotonie unique en laquelle la totalité des articles du fichier est reclassée dans l'ordre des clés de ces articles, que cet ordre soit d'ailleurs croissant ou décroissant0 Pour chaque passe d fusion, on a recours aux supports de manoeuvre. Comme les en sembles à fusionner doivent ouvroir etre simultanément consultés, la mémoire centrale est,de fait, encore toujours occupée.Une troisième phase opère ensuite pour transférer la monotonie unique du fichier reclassé sur le support externe qui est, lui, d'accès uniquement séquentiel. Des algorithmes de régie de la fusion ont été établis pour en réduire la durée. Cette réduction n'est en fait appréciable que lorsque l'équipement informatique utilisé pour outil ne peut tra vailler qu'en programmation unique. Elle perd son intérêt lorsque l'équipement travaille en multi-programmation, ce qui est maintenant le cas le plus fréquent.Le temps d'occupation réel de la mémoire centrale dans l'exploitation de ce système de tri bloque le fonctionnement de la multî-programmation:-# Ene remarque importante est que ce système usuel ne tire aucun parti du fait que les supports de maneeuvre sont, comme sus rappel4 d'accès direct, sont adressables par zones de mémoire, En autre but de 11 invention est de tirer parti des possibilités d1acc#s direct des supports de manoeuvre pour développer un sjstè me qui réduise au mieux, donc optimise, les temps d'occupation de la mémoire centrale même si la durée totale de la manipulation du fichier n'en est pas raccourci pour autant ou minimise la taille de la mémoire occupée nécessaire pour un meme -temps total de manipulation du fichier. Selon la présente invention, un système de manipulation de fichier pour son reclassement en un système informatique comprenant une mémoire de données opérant en liaison avec des supports de manoeuvre adressables en accès direct, se caractérise essentiellement en ce qu'en une première phase, des moyens forment, par un processus de distribution des articles au fur et à mesure de leur introduction en mémoire centrale, des sous-ensembles disjoints entre eux et seulement définis par une proximité des va- leurs de clés de leurs articles sur un certain nombre de bits des codes de ces clés sans nour autant que les articles soient ordonnés en chacun de ces sous-ensembles, qu'en cette première phase, des moyens examinent en permanence les parties des sous-ensembles en formation et lorsqu'une telle partie atteint le double de la taille du tampon des supports de manoeuvre, la subdivise en deux parties de sous-ensembles ayant chacun une plus grande proximité des clés de leurs articles par la concordance de valeur d'un bit additionnel de leurs clés, qu'en cette première phase, des moyens répondent à tout débordement de la mémoire centrale par le transfert aux supports de manoeuvre: des parties de sou-s-ensembles de la taille du tampon selon leur rang d'ancienneté de formation dans la mémoire centrale et dans 11 ordre naturel des adresses de bloc de ces supports et qu'à chaque transfert ces moyens mémorisent en une table les couples de données adresse de bloc/critère de proximité"des articles qu'il reçoit'::, qu'en cette première phase en core et une fois le fichier épuisé, des moyens explorent cette table pour rappeler en mémoire centrale ceux des sous-ensekbles de même critère de proximité qui dépassent-une taille prédéterminée et en re-distribuer les articles en sous-ensembles de plus grande proximité mais ne dépassant par cette taille et les retransférer en supports de manoeuvre et, en ce qu'en qu'en une seconde-phase alors, des moyens rappellent chaque sous-ensemble en mémoire centrale dans un ordre déterminé des critères de proximité, en-ordonnent le contenu et, une fois ses articles ainsi rangés, le transfère au support externe final du fichier reclassé0 Pour apprécier directement les avantages d'un système selon l'invention. sur le système antérieur, on peut considérer ce qui suit: La fonction entropie, une notion qui est définie en soi dans la théorie de l'information, s'exprime, pour un fichier de taille P par la relation: (1) E (entropie) = F. log2 F Dans le système antérieur, les monotonies engendrées dans la première phase sont statistiquement d'une longueur 2M, M désignant la taille de la mémoire centrale dont dispose 1 t équipement informatique. On obtient donc, en moyenne, un nombre n de monotonies égal à F/2M.La deuxième phase, qui opère les fusions jusqu'8 11 obtention d'une monotonie unique de la taille F, travaille sur les blocs d'articles alors mémorisés séquentiellement sur les supports de manoeuvre, chaque bloc étant de la taille #du tampon entre la mémoire centrale et les supports de manoeuvre. Chaque passe de cette seconde phase peut fusionner un nombre v de monotonies épal à M7R. En d'autres termes, à chaque passe, le nombre n de monotonies est divisé par le nombre v (qui peut être dit nombre de "voies de fusion"). Le tri-fusion est achevé après un nombre p de passes tel qu'on a:- (2) n/(vP) = 1. Par conséquent, en substituant dans la relation (2) les expressions des facteurs n et v selon les définitions ci-des#sus, on ob tient (3) (s > (F/2M)/ I( = 1. La relation (3) peut aussi s'écrire:- (4) log2 F = log2 2M + po log2 (M/B) Bn voit alors, selon la relation (1), que log2 F est,l'entro- pie à acquérir par article du fichier. Mais on constate aussi que si, dans la phase initiale, la variation d'entropie par article est log2 2M, elle n'est plus que log2 (M/B) en toute passe de fusion de la seconde phase. La conclusion directe est que la mémoire centrale n'est pas exploitée de façon optimale dans les passes de fusion. On doit de plus remarquer que, dans la première phase, celle qUi établit un ordre en chaque bloc pour engendrer les monotonies requises, le terme log2 2M qui y définit la variation d'entropie peut donc se d#écomposer, en fait, selon la relation: (5) logo 2M = log2 (2M/X)+ log2 B Dans un système selon la présente invention, puisqu'aucun ordre n'ést établi dans la phase de distribution des articles dans les sous-ensembles disjoints, la variation entropie moyenne, une fois cette distribution terminée, est par article de log2 (2M/B), Ceci démontre directement une exploitation optimisée de la mémoire: centrale, donc une réduction de son temps d'occupation. Pour exposer l'invention en son détail, on se réfère maintenant aux figures jointes, qui représentent: Fig.l, en rappel, l'organisation d'un système de manipulation de fichier pour son reclassement, selon le système antérieur, Fig.2, l'organisation correspondante d'un système selon la présente invention, Fig.3, un schéma général des moyens mis en oeuvre dans un é- quipement informatique pour un mode préféré d'exécution de l'invention, et, Fig.4, un schéma d'arbre des critères de proximité des clés lors de la distribution. Comme rappelé sur la Fi.1, le système antérieur comporte trois phases. La première opère sur le fichier entrant FE et est gérée par un algorithme de tri "interne" TI pour assurer la création de monotonies telles que sus-définies. La seconde procède à la fusion de ces monotonies, étant régie par un algorithme de fusion AF.Lorsque le test de fin de fusion TWF indique que cette fusion est terminée, la monotonie unique et totale qui en résulte se trouve garée sur les supports de manoeuvre qui ont servi a' de nombreux va-et-vients dans les a eux phases réeédentes. Une troisi ème phase transfère alors le contenu de ces supports de manoeuvre via la mémoire centrale (qui peut en son début, contenir une partie extreme du fichier) au support final FSo Cette troisième phase EPS est indemendante de la seconde, Dès la première phase, il est clair que chaque clé associée à chaque article a du être examinée en la totalité de ses bits, et qu'il en a été de meme dans la seconde phase En contradiction, comme indiqué sur la Fig.2, un système se Ion la présente invention opère en deux phases, 01 et #2, ltune de distribution et 11autre de reclassement ordonné d'articles et d'écriture des groupes d'articles ainsi ordonnés sur le fichier de sortie FS, La première phase se divise en fait en deux opéra- tions, 011 et 0122 la seconde rectifiant quand de besoin le résultat de la première pour assurer la pleine efficacité de ltopéw ration effectuée ensuite dans la phase finale La première phase consiste essentiellement à distribuer les articles au fur et a mesure de leur lecture sur le fichier en tract FE en sous-ensembles d'articles non-ordonnés mais ayant en commun un critère:- celui d'avoir un certain nombre de bits identiques en leurs clés, ce nombre de bits variant, tout au-moins pouvant varier, d'un sous-ensemble à autre, par des moyens qui seront exposés plus loin, la taille de chaque sous-ensemble créé' en cette première phase est maintenue entre B et 2BI, B étant la taille du tampon entre mémoire centrale et supports de manoeuvre, en sorte que, chaque fois que la mémoire centrale est pleine, il existe en elle un certain nombre de groupes d'articles' de la taille B, chacun diune certaine "définition" en nombre de bits communs de leurs clés, ayant chacun séjourné plus ou moins long- temps dans la mémoire depuis leur formation. Ces groupes sont alors transférés, par rang d'ancienneté décroissante, sur les supports de manoeuvre à des adresses de bloc définies en ces supports A chaque transfert, une table no-te le couple de données "défini- ti#n/destination'1,- la destination étant évidemment une adresse de support de manoeuvre Puisque cette première opération s'effectue en plusieurs "passes", étant donné que le fichier est de taille supérieure à celle de la mémoire centrale, il pourra#onc co-eYister r--inalement sur les supports de manoeuvre, des sous-ensembles constitués de "blocs" ou groupes d'articles ayant même définition chacun. Comme dans la phase finale, chaque sous-ensemble défini dans la première -phase doit être traité en une seule "passe" en mémoire centrale pour ordonner les articles, il ne faut pas qu'un tel sous-ensemble ne dépasse pas une certaine taille, celle de la mémoire centrale par exemple.C'est pourquoi, après la première opération de la phase, BU, elle enchaine sur une seconde opération i qui permet de rectifier de tels dépassements Cette seconde opération est réalisée à l'aide de moyens qui, par consultation de la table susdite, rappelle les blocs constituant, ensemble, de tels sousensembles en dépassement de taille et, en cette phase d'itération de distribution, AID, rappelle à chaque fois la première opération AD pour re-subdiviser ce sous-ensemble excessif en au moins deux sous-ensembles vrais, de définitions distinctes, dont la taille individuelle ne dépasse pas celle attribuée pour l'exécu- tion de la seconde phase.Cette redistribution donne lieu à de nouveaux transferts vers les supports de manoeuvre avec modifications appropriées de la table, La seconde phase #2, sur information de fin de distribution TPD, opère alors, touJours par consultation de la table, on rappelant en succession, des supports de manoeuvre, les blocs d'partir clos qui constituent un sous-ensemble directement traitable pour le classement de ses articles.Cet appel est effectué selon un ordre défini, direct ou inverse, des valeurs des définitions des sous-ensembles, Cette phase est donc régie par un algorithme TI/ EPS qui, après chaque réarrangement des articles d'un sous-ensemble, en assure l'écriture sur le fichier de sortie FS avant dlap- peler le sous-ensemble de rang suivant0 Il se peut que, par suite d'une différence de taille entre les blocs de données dans les fi. chiers et dans les supports de manoeuvre, le transfert d'un sousensemble ré-ordonné de la mémoire MC au fichier de sortie FS, un "reste11 demeure en mémoire centrale. On pourra tenir compte de cette donnée pour déterminer la taille maximale des sous-ensembles afin de la rendre aussi multiple de celle des blocs en fi chiera Ce qui peut être directement souligné, c'est que, pour la création des sous-ensembles et pour leur subdivision condition nelle ultérieure, il n'est pas nécessaire dlxaminer le code de clé de chaque article entier, depuis son début, mais seulement les bits décisifs pour son classement en tel ou tel sous-ensemble dans les groupes pro sressivement formés dans la mémoire MC, d'où un gain de temps supplémentaire sur la création des monotonies. Le gain de temps apporté par le système selon l'invention, donc la réduction de la durée d'occupation de la mémoire centrale, est toutefois fondamentalement dû, comme on peut déjà s'en rendre compte, -à- une exploitation optimale de cette mémoire en chacune des "pasees" de distribution sus-énoncéese La Fig.3 schématise à un degré suffisant pour la compréhen- sion de 1 invention, son mode de mise en pratique et sa reproduc- tîbilité par quiconque versé dans l'art de l'informatique, les moyens utiles et particuliers de son exploitation. Le matériel n'en est toutefois pas détaillé car chacun de ces éléments est classique en lui-même et en son fonctionnement propre. La mémoire (MC), de taille M, est adressable en emplacements dont chacun peut contenir un code d'article complet (y compris sa clé) et un mot de chaînage de cet article sur un autre. On a moins tré. en RA le registre d'adresse usuel d'une telle mémoire. Par un tampon BF, un fichier sur bande magnétique FE peut être lu et un fichier sur bande magnétique FS peut être écrit. Par un tampon BM les transferts peuvent être assurés entre la mémoire centrale et des supports de manoeuvre consistant par exemple en un équipement de disques magnétiques, de Dl à Dp. Chaque mot lu dans le tampon: BF passe par un registre d'4criture-lecture Rel.Chaque mot échangé entre la mémoire centrale. et les mémoires de manoeuvre (MM) passe par un registre d'écriture-lecture REL, La mémoire de manoeuvre -( > S) est, par exemple, adressable par cylindres-. Pour simplifier l'exposé, on considère de plus que pua mani- pulation du fichier a recours à un processeur de gestion micropro gramméZuPG en lequel est affecté le programme de tri. à partir de l'unité centrale (UC), non figurée Pour simplifier encore, on considère que ce processeur est équipé de trois mémoires de com mande, éléments firmware ME0ll, w 12 et ME02 pour la régie des trois opérations correspondantes de l'algorithme de la Fig.2. La constitution de ces trois éléments ne sera pas détaillée plus avant, ce qui serait, ici, inutile. A la mémoire (MC) sont, pour la mise en oeuvre de l'invention associées deux tables ayant avec les éléments firmware des liaisons indiquées au schéma en double trait et dont les natures et fonctions seront précisées plus loin. La première, Ti, répertorie en premier lieu, au fur et à mesure de- l'entrée en mémoire du fichier et la distribution de ses articles sous la commande de #1K#11et de fac on évolutive, les définitions des groupes formés pour la constitution des sous-ensembles.Contrairement en effet à une distribution classique d'articles à des destinations fixées à l'avance, la "définition" qui régit la formation de chaque grouse d'articles dans un système selon la présente invention n'est ni prédéterminée ni même fixe dans le temps, elle évolue au contraire dans le temps en fonction même des codes de clé lus dans les codes d'articles au fur et à mesure de leur introduction en mémoire centrale tant du tampon BF que du tampon BM, selon les stades de la distribution tels que définis plus haut. Chaque entrée de la table Ti mémorise donc, en déf, un code défini par un certain nombre de bits de clé sur lesquels les codes de clé CC des articles de cette entrée sont identiques.La valeur du premier bit de clé au delà de la définition divise tout groupe en deux sous-groupes, le premier est identifié par la valeur o de ce bit additionnel, le second est identifié par la valeur 1 de ce même bit additionnel0 Sauf en tout début de processus, chaque entrée de la table Tl n'est remplie qu' une fois un groupe "constitue" par au moins B articles, étant la taille en articles du tampon BM vers les mémoires de manoeuvre (MM).Dans l'entrée concernée de la table T1 est alors écrite, en un emplacement sgo l'adresse en (MC) du premier article du groupe qui débute le sous-groupe dont le premier bit de clé au delà de la définition déf est de valeur 0, et en un emplacement 1* Le nombre d'articles appartenant au sous-groupe sgo est écrit dans un emplacement debo de la table et le nombre d'articles ap partenant au sous-groupe sgl est écrit dans un emplacement debl 'de la même entrée de la table, Ces nombres sont tenus à jour, en d'autres termes, dans la suite du processus de distribution, tout nouvel article de la définition déf donne lieu à une incrémentation du contenu de soit debo soit debl selon le cars. Chaque fois que le contenu d'un de ces emplacements "déborde", ctest à dire atteint la valeur , il délivre un signal qui, reçu en MK#11, ro- voque une interruntion du processus nour faire entrer l'algorithme de rédie de cet élément en une routine de subdivision du groupe telle qu'on la précisera plus loi, On a dit que chaque emplacement en (MC) attribué à un article du fichier comportait un mot fte chaînae de cet article sur un au tre. Mais, comme visible en regardant la FiC#4, qui montre "l'ar bre" des troupes développés au cours de la '#istribiition, chaque nouveau groupe formé doit être chaîné sur le groupe dont il est issu par division. Chaque entrée de table Ti comprend pour cela un emplacement ch qui motorise le mot de chafnage de son premier article Chaque entre dé la table T1 comporte, en outre, un emplacement anc pour définir l'ancienneté de l'existence du groupe dans la mémoire (MC), donc en fait l'instant de formation du groupe. L'information anc peut être fournie par un compteur "temps" asso cié à PG ou directement à MK#11 et dont l'information est mémorisée a l'écriture de l'entrée en table Tl du groupe, Pour simplifier, ce compteur peut être incrémenté d'une unité à chaque introduction d'un groupe dans la table T1, le marquage d'un temps réel n'étant pas impératif en soi. La seconde table, T2, est plus simple:- elle ne mémorise que chaque couple de donnes définition/destination, dèf/des, c'est à dire, en plus c air, l'identification par sa définition d'un grou- pe qui a été formé en (MC) et qui est transféré aux sunports de manoeuvre à une destination définie par une adresse physique de ces supports Au registre d'écriture-lecture Rel des codes provenant du tampon BF est associe, un circuit analyse ANC du code de clé CC de chaque mot passant en ce registre.Cette analyse permet à MK#11 de décider 1affecter l'article à l'un des groupes définis dans la table Tl, et meme à un des deux sous-groupes de cette entrée, donc d'incrémenter d'une unité le contenu de debo ou debl selon ie cas. Ln 131us, le mot de chaînage est adjoint au code de cet article. Tant qu'aucun débordement n'est signalé, le processus se poursuit, d'article en article. Lorsqu'un des sous-groupes déborde, c'est donc outil peut constituer à lui seul un groupe qui se situera au niveau de définition immédiatement plus élevé dans l'arbre.Ce signal interrompt la lecture des articles et le sousroute concerné est constitué en groupe par l'introduction de ses caractéristiques dans une entrée de la table T1:- définition pro rre accrue d'un chiffre, nombresd'articles en enses deux sous-grou ces alors définis par les valeurs des bits de clé inimédiatement extérieurs à sa définition, adresses de ses sous-groupes ainsi déterminés et, naturellement, son nouveau chaînage et sa nouvelle "ancienneté". Puisqu'il reste moins de B articles dans le groupe origine du nouveau, ce groupe doit donc être supprimé en tant que tel et ses articles sont individuellement re-examinés gour être répartis en d'autres groupes déjà existants.En lsune et l'autre opérations, les chaînages des articles sont modifiés en conséquence. Un examen de "l'arbre" de la Fig.4 montre qu'en début de manipulation et dépouillement d'un fichier, peut être admise la formation d'un groupe temporaire comprenant moins de B articles, si la taille du tampon BF est inférieure à la taille du tampon BM, ou même de plusieurs. ainsi, au cours de 1 introduction des articles du fichier FE dans le système, des groupes se créent puis disparaissent au profit de groupes de définitions de plus en plus poussées selon les codes de clé des articles introduits, ceci jusqu'à ce qu'un évène- ment se produise, a savoir le "débordement de la mémoire (MC) ce qui est signalé à -MK0ll par l'activation de la sortie d'un circuit DBM prévu à cet effet.Ce signal provoque une interruption de la lecture des articles et NK0ll entre en une routine de consultation de la table TI pour y déterminer, en rang dXaneienneté décroissante celles des entrées montrant qu'il existe en (MC) des blocs de taille Nk chacun d'une définition donnée. nu plus ancien au plus récents chacun de ces blocs sera transféré en supports de manoeuvre à une adresse notée en destination des en même temps que sadéfinition de dans la table T2* Les adresses que peut choisir ME pour de tels transferts en supports de manoeuvre (MM) sont libres et, si désiré, peut être assuré un reclassement des groupes de même définition en T1 pour que leurs adresses en supports de manoeuvre se suivent et qu'e, de plus, les groupes en lesquels sont prélevés les blocs soient, pour la détermination de ces adresses, sélectionnés selon leur chaînage eh. Cette possibilité, d'exploitation optionnelle, est, lorsqu'appliquée, susceptible d'accélérer par la suite les opérations de recherche et rappel des blocs d'un même sous-ensemble en mémoire centrale dans la phase régie par MK#12 tout au moins, et même dans la phase régie par MK#2, car un- tel rangement d'adresses en (MM) permettra de réduire au mieux les déplacements des bras porte-têtes des disques. X chaque transfert d'un "bloc" extrait d'un groupe, ce groupe est détruit puisqu'il n'y reste plus B articles. A chaque trans- fert par suite, la routine susdite doit procéder à la redistribuw tion des articles restants dans les autres groupes, de la même fa çon qu'il a été décrit pour les subdivisions de groupes Et si une telle redistri#Iution provoque un débordement en un emplacement debo ou debl d'une entrée de la table TI, la routine de redistri bution est, elle-même, interrolllpue pour la routine de subdivision, du groupe concerné, avant que, cette derniers acquittée, elle puisse reprendre, jusqu'à son propre acquittement qui rappelle la routine de consultation et transfert, et ainsi de suite. Une fois les transferts terminés, la lecture du fichier entrant FE peut reprendre et la distribution se poursuivre comme sus-décrit, jus qu'à l'apparition d'un nouveau signal de débordement en DBM, et ainsi de suite, en boucle, jusqu'à épuisement du fichier, Puisque la première phase 01 s'opère en plusieurs "passes' puisque la fichier est d'une taille F normalement très supérieure à celle de la mémoire centrale, il existera donc en fin de la pre- mière distribution dans les supports de manoeuvre des sous-ensembles, chacun déterminé par des blocs de même définition def, qui peuvent dépasser la taille M de la m & qoire centrale0 De tels sousensembles excessifs ne pourraient être traités en une seule passe en mémoire centrale au cours de la phase ~2* L'acquittement de passe dono la commande à MK#12. L'algorithme de ~12 procède à une exploration de la table T2 et, puisque chaque bloc en (MM) com# prend un nombre déterminé et constant d'articles du fichier, il lui est aisé de déterminer# si un sous-ensemble d'une définition déf donnée dépasse ou non la taille M.Si cette consultation démontre un tel débordement, les blocs qui constituent ce sous-ensemble sont rappelés en mémoire centrale, la sortie du circuit And ayant été "vraie" pour une définition def déterminée, dont il a également reçu le code, pour que cette consultation de T2 puisse avoir commodément lieu par voie associative, MK0ll est, pour cette réintroduction, rappelée et selon le même processus que décrit pour l'introduotion et la distribution des articles du fichier de la phase 011 re-distribue les articles en groupes de définitions plus poussées, et ce, en autant de passes entre supports de manoeuvre et mémoire centrale que de besoin. On peut considérer que li registre BEL est, pour cela, soit relié au circuit d'analyse de clés ANC, soit est, tout simplement, confondu avec Rel puisque BEL et Rel peuvent ne pas être simultanémént exploités. Après chaque redistribution des articles d'un sous-ensemble en débordement vis à vis de M, MK#11 renvoie la régie d'opérations à MKp12 qui reprend sa consultation de la table T2 avec une autre définition dot, et ainsi de suite. La redistribution terminée, la table T2 donne une représen- tation complète du fichier distribué en de tels sous-ensembles dont chacun peut avoir ses articles ré-ordonnés en une seule passe en mémoire centrale et donc être, caque fois, recopié sur le fichier de sortie FS. La phase #2 sous la régie de MK#2 assure cette dernière opération dont l'algorithme n'a pas besoin dtêtre détaillé puisqu'il consiste à créer une monotonie en chaque sousensemble et que c'est par suite I'algorithme utilisé dans la première phase du système antérieur, puis de "vider't la mémoire centrale sur le fichier à chaque monotonie ainsi crée'#.Le rappel des sous-ensembles est bien évidemment décidé par la consultation de la table T2. R E V E N D I C A T I O N S . 1. - Système de reclassement par un équipement informatique d'un fichier dont les articles sont disponibles pour lecture sé quentielle sur un support pÉriphérique de l'équipement et se présentent chacun avec une clé de classification écrite dans son code, l'équipement incorporant une mémoire de données adressable opérant en liaison avec ledit support par l'intermédiaire d'un tampon et d'un registre d'écriture-lecture et opérant aussi en liaison avec des supports de manoeuvre adressables en accès direct par 11 intermédiaire d'un tampon et d'un registre d'écriture-lecture, système caractérisé en ce qu'il comporte la combinaison de moyens qui, on une première phase opératoire, forment à partir de la lecture séquentielle des articles, des sous-ensembles disjoints non ordonnés d'articles présentant une même définition par l'identité de leurs clés sur un certain nombre de bits, chaque sous-ensemble formé par une telle distribution des articles étant, en fin de cette phase opératoire, d'une taille au plus égale à celle de la mémoire de données et se trouvant mémorisé sur les dits supports de manoeuvre, et de moyens qui, en une seconde phase opératoire, rappellent un nar un, en un ordre établi dans leurs définitions, les sous-ensembles en mémoire de données, en réordonnent les articles et les transferent sur un support périphérique de fichier reclassé. 2, - Système selon la revendication 1, caractérisé en ce qu' en cette première phase opératoire, les dits moyens comprennent la vombillaison : - de moyens d'analyse des cl es de clés des articles entrants pour leur distribution en des groupes de formation de sous-ensembles à définitions de lus on plus poussées, de moyens de test de dé veloppoment de ces groupes jusqu'à une taille double de celle du tampon d'accès des supports de manoeuvre et de moyens rénondant à ne activation de la sortie d'un de ces moyens do test pour extraire du groupe concerné un nouveau groupe de la taille de ce tampon et avant une définition accrue d'un bit de clé, de moyens de détection de débordement de la mémoire de données en articles du fichier, de moyens répondant à toute détection de uéboruement pour transférer en supports de manoeuvre ceux des grouses qui ont alors, en mémoire de données, la taille dudit tamnon et do moyens de mémorisation de la définition et de l'adresse de destination en support de manoeuvre de tout groupe transféré, et, de moyens activés sur épuisement du fichier pour explorer la mémorisation susdite, rappeler en mémoire de données les groupes d'un sous-ensemble dont le nombre total articles dépasse la taille de la mémoire et, à chaque rappel, réactiver les premiers moyens de formation des groupes et leurs transferts en supports de manoeuvre pour créer de nouveaux sous-ensembles chacun de taille au plus égale à celle de la mémoire de données et d'une définition accrue d'au moins un bit de clé* 3. - Système selon la revendication 2, caractérisé en ce que des moyens de mémorisation incorporant une table à entrées multi ples assurent ltaffectàtion d'une entrée à chaque-groupe en forma- tion comprenant au moins autant d'articles de même définition que la taille dudit tampon, y écrivent, outre la dite définition, les adresses en mémoire du premier article du groupe dont le bit de clé au delà de la définition vaut O et du premier article du groupe dont ce bit vaut 1 et tiennent ensuite a' jour les comptes de ces deux catégories d'articles du groupe en des emplacements dont chacun délivre une signal lorsque son compte atteint la taille du tampon. 4. - Système selon la revendication 3, caractérisé en ce que cette table comporte également en chacune de ses entrées, un emplacement de marquage de l'ancienneté de vie du groupe concerné en mémoire de données, les dits moyens de mémorisation déterminant cecode d'ancienneté à partir d'un compteur de formation-de groupes et en ce que les moyens de transfert de groupes en supports de manoeuvre consultent les codes dtancienneté en même temps que les codes d définition pour décider de ltordre des transfeitxde tels groupes. 5. - Système selon la revendication 4, caractérisé en ce que les moyens de formation des groupes à partir des analyses des codes de clfi des articles ajoutent à chaque code d'article un mot de chainage de son adresse sur celle de L'article'précédemment affecté de la même définition et en ce que la dite table comporte égale# ment en chacune de ses entrées un emplacement de marquage du chia; ;~ nage du premier article de ce groupe sur le dernier article du groupe de la définition immédiatement antérieure à la formation de ce groupe, les dits moyens de transfert consultant également le chaînage pour leurs opérations propres, notamment pour la détermination des adresses de destination en supports de manoeuvre, 6. - Système selon la revendication 2 et la revendication 3 caractérisé en ce qu'aux moyens d'extraction d'un groupe en dépas- sement du double de la taille du tampon d'un nouveau groupe de définition accrue d'un bit de clé sont associés des moyens de redistribution des articles restants en d'autres groupes par nouvelle analyse plus pousée de leurs codes de clé.