Optimisations des chemins de données arithmétiques par l'utilisation de plusieurs systèmes de numération

Y. Dumonteix

LIP6 2001/026: THÈSE de DOCTORAT de l'UNIVERSITÉ PARIS 6 LIP6 / LIP6 research reports
228 pages - Octobre/October 2001 - French document.

Get it : 1729 Ko /Kb

Contact : par mail / e-mail

Thème/Team: Architecture des Systèmes Intégrés et Micro-Électronique

Titre français : Optimisations des chemins de données arithmétiques par l'utilisation de plusieurs systèmes de numération
Titre anglais : Arithmetic datapath optimisation using several number systems

Résumé : Cette thèse présente l'intégration de nouveaux systèmes de représentations des nombres, plus précisément les systèmes de notations redondantes, dans le flot de conception de coeurs de calculs. Les travaux effectués se découpent en trois phases. La première est consacrée à l'introduction des systèmes de notations redondantes aux côtés des systèmes de notations classiques. A cet effet nous avons défini une nouvelle arithmétique qualifiée de mixte. Celle-ci répond aux problèmes liés à l'usage simultané des notations classiques et redondantes. Elle a donné lieu au développement de nouveaux opérateurs très performants capables de tenir compte de toutes les combinaisons de notations classiques/redondantes sur leurs entrées/sorties. Les trois opérations élémentaires que sont l'addition, la somme et la multiplication, ont été étudiées. Nous distinguons le cas particulier de l'ajout de deux opérandes (addition) du cas général de l'ajout de trois opérandes et plus (somme). Ces diverses opérations ont été réalisées sous formes de générateurs où la taille, le signe et la notation de chacune des opérandes ainsi que l'algorithme de calcul utilisé sont paramétrables. La deuxième phase a eut pour objectif de déterminer l'impact de l'arithmétique mixte dans la conception de chemins de données. L'étude porte sur la redéfinition des enchaînements combinatoires et séquentiels entre opérateurs et sur l'utilisation d'arbres d'additions (somme). Cette seconde phase a permis d'identifier des règles d'optimisations génériques liées à l'usage d'opérateurs arithmétiques dans une architecture. La troisième phase est consacrée à la prise en compte de nouveaux systèmes de représentations dans la la synthèse d'architecture. Nous nous intéressons essentiellement à la phase de traduction comportements -_ structures physiques. L'objectif est de proposer une méthode de projection équivalente à celle utilisée dans la synthèse bas niveau, incorporant en plus les opérateurs ari!
thmétiques et le savoir-faire lié à leur usage. Pour répondre à ces particularités, la projection ne se fait pas directement vers une bibliothèque de cellules pré-caractérisées, mais vers des générateurs d'architectures. Cette dernière phase a donné lieu à la définition d'une méthodologie de conception de chemins de données basée sur l'utilisation de générateurs de fonctions élémentaires et à la spécification d'un outil d'aide à la conception de chemins de données. Ce dernier permet de définir un chemin de données par une description simplifiée.

Abstract : This thesis presents the integration of redundant number representations in arithmetic circuit design flow. The work is divided in three parts. The first part is dedicated to the introduction of the redundant number systems in addition to the classical number systems. For that purpose we have defined a new arithmetic, named __it mixed arithmetic_, which takes into account the problems of the simultaneous use of classic and redundant notations. We have also developed a set of new operators which ensure all the possible input / output combinations in redundant and classical notations. The three elementary operations : addition (two operands), sum (more than two operands) and multiplication, have been studied. For each one we have created a generator. The generation parameter list is composed of the size, the sign and the notation of all inputs/outputs, and of the computation algorithm to use. The aim of the second part is to study the impact of the mixed arithmetic in data path design. The analysis concerns the choice of the notations used between the different operators of an architecture. Combinatorial and sequential chains have been studied. The analysis also applies to the use of the addition tree properties (sum properties). This part allowed us to identify several generic rules of arithmetic optimizations in arithmetic circuit design. The third part is dedicated to the introduction of the mixed arithmetic in the architecture synthesis. We are essentially interested in the behavioral-to-structural conversion. The goal is to propose a mapping phase taking into account the arithmetic operators and our knowledge in their usage. Therefore, the mapping is not directly based on standard cells but on a generator set. These generators build the operator architectures ( standard cells based netlist ) depending on the context. For this last part, first we present a arithmetic data path synthesis methodology using basic function generators then we p!
ropose the specification of a data path synthesis aid tool. The defined tool input is a simplified data path description.

Mots-clés : Arithmétique des ordinateurs, systèmes classiques de numération, systèmes redondants de numération, algorithmes et opérateurs arithmétiques, optimisations arithmétiques, synthèse de chemins de données arithmétiques

Key-words : Computer arithmetic, classical number systems, redundant number systems, arithmetic operators and algorithms, arithmetic optimization, arithmetic datapath synthesis

Publications internes LIP6 2001 / LIP6 research reports 2001

Responsable Éditorial / Editor :Francois.Dromard@lip6.fr