Ph.D. thesis no. 1264, EPFL, Lausanne (CH), 1994.
Research on artificial neural networks (ANNs) has been carried out for more than five decades. A renewed interest appeared in the 80's with the finding of powerful models like J. Hopfield's recurrent networks, T. Kohonen's selforganizing feature maps, and the backpropagation rule. At that time, there was no platform that was at the same time versatile enough for any ANN model to be implemented and fast enough to solve large problems. Supercomputers were the sole exception to this rule, but were prohibitively expensive for most applications. However, both research scientists and application engineers clearly identified the need for such a computing power. This triggered many projects in the field.
In parallel, research on multiprocessor systems started during the 60's. Systolic arrays have been proposed in 1979 as a means to fully exploit the possibilities of VLSI. Two previous theses, by F. Blayo and C. Lehmann, have studied the use of bidimensional systolic arrays for neural computation. At first, the presented system, called GENES, has been designed for the Hopfield model. Extensions to other ANNs have also been proposed.
The goal of the present thesis is to study, design, build, and analyze an efficient accelerator for neural computation. In a first step, the GENES architecture has been extended towards generality and efficiency. This includes a thorough analysis of ANN models, of other neural computers, and of previous GENES implementations. The result of this work is the GENES IV integrated circuit, whose architecture has been codesigned by P. Ienne and the author. The main part of this thesis discusses the architecture, the design and the analysis of the MANTRA I machine, a neural computer based on a GENES IV array with up to 40 × 40 processing elements (PEs). The delta rule (and hence the Perceptron and Adaline rules), the backpropagation rule, the Hopfield model, and the Kohonen model can be implemented on this system. Although not a generic system, such a machine may be regarded as a multimodel neural computer. A prototype has been running for a year and is used daily by software designers.
Several novel features distinguish the MANTRA I machine from other neural systems. First, it belongs to the few existing neural computers, contrary to the majority of implementations, which are specific to an application or to an algorithm. The machine does not hardwire any algorithm, but provides the necessary primitives to implement the target models. This is a key feature for research, since several algorithms or versions of an algorithm can be tested on a problem. It is an important aspect for applications as well, because different ANN models are often cascaded to solve a problem.
The GENES IV array - that is, the computing core of the MANTRA I machine - features synapselevel parallelism (i.e., one real or virtual PE is allocated per synapse or neural connection), while most other systems exploit only neuronlevel parallelism (i.e., one PE per neuron). Hence, this system aims at a much finer parallelism grain and is well suited for massively parallel architectures.
The problem size that can be computed by a neural accelerator should not be limited by the hardware (except for memory size). Therefore, it is essential to support timesharing of PEs. On the MANTRA I machine, this is achieved by the concept of virtual arrays. Matrices are divided into submatrices that can be mapped onto the physical array, which is then timeshared among them. An efficient mechanism has been implemented to swap submatrices in background, while some other computation is performed.
Since systolic arrays are pipelined systems, it is important to avoid emptying and refilling them too often, in order to keep the hardware utilization rate high. Therefore, a systolic instruction flow has been implemented, so that each instruction follows the data for which it has been issued.
Like any SIMD system, the MANTRA I machine is composed of a parallel or SIMD module and a control module. The SIMD module consists of the GENES IV array and a set of dedicated units designed for the computation that scales with the number of neurons and would poorly fit on a bidimensional array. A complex system of FIFOs and memories sustains the required input/output streams for the systolic array.
The control module is a complete SISD system. Its tasks are (1) to control the SIMD module by dispatching instructions, (2) to manage data input and output, (3) to communicate with the external world, and (4) to perform data pre and postprocessing. The SIMD instructions are of the very long instruction word (VLIW) type. Synchronization between the two modules is achieved by an instruction FIFO.
The performance of the MANTRA I machine has been analyzed using the delta rule. Measurements show that the sustained performance is very close to its peak value, as long as the problem fits in the memory banks connected to the GENES IV array. Experiments have also been run to investigate the impact of the constraints imposed by the hardware on the convergence of algorithms.
Finally, the use of systolic arrays as neural accelerators is discussed in the light of the experience acquired with the GENES IV array and the MANTRA I machine. The weaknesses of the machine are analyzed, and several solutions are proposed to avoid them in a future design. A general discussion of the future of neural computers concludes this thesis.
La recherche dans le domaine des réseaux de neurones artificiels (RNA) s'étend sur plus de cinq décennies. Elle a suscité un regain d'intérêt dans les années 80 avec la mise au point de modèles tels que les réseaux récurrents de J. Hopfield, les cartes autoorganisatrices de T. Kohonen et la règle de la rétropropagation du gradient. A cette époque, il n'existait aucun système à la fois suffisamment souple pour que n'importe quel modèle de RNA puisse être implanté et suffisamment rapide pour résoudre des problèmes importants. Les superordinateurs étaient la seule exception à cette règle, mais leur prix était prohibitif pour la plupart des applications. Cependant, tant les chercheurs que les ingénieurs ont clairement identifié le besoin d'une telle puissance de calcul. Ce fut le point de départ de nombreux projets dans ce domaine.
En parallèle, la recherche dans le domaine des ordinateurs multiprocesseurs a débuté dans les années 60. Les tableaux systoliques ont été proposés en 1979 comme moyen d'exploiter au mieux les possibilités du VLSI. Dans deux thèses précédentes, F. Blayo and C. Lehmann ont étudié l'utilisation de tableaux systoliques bidimensionnels pour le calcul neuronal. Le système presenté, appelé GENES, a d'abord été conçu pour le modèle de Hopfield. Des extensions à d'autre RNA ont également été proposées.
Le but de la présente thèse est d'étudier, de concevoir, de construire et d'analyser un accélérateur de calcul neuronal efficace. Dans un premier temps, l'architecture de GENES a été étendue en vue d'offrir un champ d'application plus vaste et une plus grande efficacité. Cette étape comprend une analyse approfondie des modèles de RNA, d'autres ordinateurs neuronaux et des implantations précédentes de GENES. Le résultat de ce travail est le circuit intégré GENES IV, conçu conjointement par P. Ienne et l'auteur. La partie principale de cette thèse étudie l'architecture, la réalisation et l'analyse de la machine MANTRA I, un ordinateur neuronal basé sur un tableau GENES IV d'au plus 40 × 40 processeurs élémentaires (PE). La règle delta (et donc les règles du Perceptron et de l'Adaline), la règle de la rétropropagation du gradient, le modèle de Hopfield et le modèle de Kohonen peuvent être implantés sur ce système. Bien que n'étant pas un système générique, une telle machine peut être qualifiée d'ordinateur neuronal multimodèles. Un prototype est fonctionnel depuis une année et utilisé quotidiennement par les concepteurs du logiciel.
Différentes caractéristiques distinguent la machine MANTRA I d'autres systèmes neuronaux. D'abord, elle fait partie des quelques ordinateurs neuronaux existants, au contraire de la majorité des réalisations, qui sont spécifiques à une application ou à un modèle. Aucun algorithme n'est câblé dans la machine, mais celleci fournit les primitives nécessaires à l'implantation des modèles visés. Il s'agit là d'une caractéristique essentielle pour la recherche, puisque plusieurs algorithmes ou versions d'un algorithme peuvent être testés sur un problème. C'est également un point important pour les applications, puisque différents modèles de RNA sont souvent utilisés conjointement pour résoudre un problème.
Le tableau systolique GENES - c'estàdire le coeur de la machine MANTRA I - vise un parallélisme au niveau des synapses (c'estàdire qu'un PE réel ou virtuel est alloué par synapse ou connexion vers un neurone), alors que la plupart des autres systèmes exploitent seulement le parallélisme au niveau des neurones (un PE par neurone). Ce système vise donc un grain de parallélisme beaucoup plus fin et convient donc bien comme architecture massivement parallèle.
La taille des problèmes qui peuvent être calculés par un accélérateur neuronal ne devrait pas être limitée par le système (mis à part la taille de la mémoire). Il est donc essentiel de permettre le partage des PE dans le temps. Avec la machine MANTRA I, ceci est possible grâce au concept de tableaux virtuels. Les matrices sont divisées en sousmatrices de la taille du tableau physique, qui est alors partagé entre elles dans le temps. Un mécanisme efficace permet l'échange de sousmatrices en arrièreplan, tandis que d'autres calculs sont effectués.
Comme les tableaux systoliques sont des systèmes en pipeline, il est important d'éviter de les vider et remplir trop souvent, afin de maintenir un taux d'utilisation élevé. À cet effet, un flux systolique d'instructions a été implanté, afin que chaque instruction suive les données pour lesquelles elle a été prévue.
Comme tout système SIMD, la machine MANTRA I est composée d'un module parallèle ou SIMD et d'un module de contrôle. Le module SIMD est formé du tableau GENES IV et d'une série d'unités spécialisées conçues pour les opérations qui sont proportionnelles au nombre de neurones et qui auraient été mal adaptées à une mise en oeuvre au moyen d'un tableau bidimensionnel. Un système complexe de FIFOs et de mémoires fournit les flux d'entrée et de sortie nécessaires au tableau systolique.
Le module de contrôle est un système SISD complet. Ses tâches sont (1) de contrôler le module SIMD en générant ses instructions, (2) de gérer l'entrée et la sortie de données, (3) de communiquer avec le monde extérieur et (4) d'effectuer le pré et posttraitement des données. Les instructions pour la partie SIMD sont codées horizontalement (VLIW). La synchronisation entre les deux modules est assurée par une FIFO d'instructions.
Les performances de la machine MANTRA I ont été analysées à l'aide de la règle delta. Les mesures montrent que cellesci sont très proches de leurs valeurs de pointe, pour autant que le problème ne dépasse pas la capacité des banques de mémoire connectées au tableau GENES IV. Une autre série d'expériences a permis d'évaluer l'impact des contraintes imposées par la machine sur la convergence des algorithmes.
Finalement, l'utilisation de tableaux systoliques comme accélérateurs neuronaux est discutée à la lumière de l'expérience acquise avec le tableau GENES IV et la machine MANTRA I. Les faiblesses de la machine sont analysées et plusieurs solutions sont proposées pour les éviter dans une nouvelle version. Une discussion générale sur le futur des ordinateurs neuronaux clôt cette thèse.