<  Back to the Polytechnique Montréal portal

An iterated tabu search algorithm for the design of fir filters

Katayoon Moazzami

Masters thesis (2011)

[img]
Preview
Download (1MB)
Cite this document: Moazzami, K. (2011). An iterated tabu search algorithm for the design of fir filters (Masters thesis, École Polytechnique de Montréal). Retrieved from https://publications.polymtl.ca/755/
Show abstract Hide abstract

Abstract

« RÉSUMÉ : Les systèmes modernes de télécommunication sans fils occupent une place majeure dans la société actuelle. Dans les dernières années, la complexité des outils qui en découlent n'a cessé d'augmenter car, en plus de prendre en charge les tâches basiques de communication vocale, ceux-ci doivent également supporter une quantité croissante de modules et d'applications parallèles (connexion internet, capture vidéo, guidage par satellite, etc.). En conséquence, l'évolution rapide subie par ces outils qui, dans la majorité des cas, sont alimentés par batteries, a singulièrement accru l'importance du rôle joué par la consommation énergétique, et a ainsi fait de l'efficacité énergétique et de l'informatique éco-responsable des caractéristiques essentielles dans les développements récents de la micro-éléctronique. Afin d'offrir une solution à ces problèmes énergétiques, une partie des recherches s'est focalisée sur la conception de filtres numériques efficaces. Les filtres numériques sont la pierre angulaire de tous les systèmes de traitement de signal numérique. Chaque filtre est implanté par un circuit intégré, qui, lui-même, est composé d'une liste d'éléments de base incluant des additionneurs, des multiplicateurs, des inverseurs, etc. La piste principale suivie par les chercheurs dans le but de réduire la quantité d'énergie consommée par les filtres numériques propose de remplacer les multiplicateurs dans les circuits par des éléments moins énergivores, tels que des additionneurs, des décaleurs et des inverseurs. L'objectif des méthodes introduites dans ce sens consiste généralement à remplacer les multiplicateurs tout en utilisant le moins d'additionneurs possible. En effet, en l'absence de multiplicateurs dans les circuits, les additionneurs deviennent l'élément le plus demandant en ressource énergétique. Dans les faits, la quantité d'additionneurs contenue dans un circuit sans multiplicateurs, aussi connue comme son coût en additionneurs, est communément utilisée afin d'estimer sa consommation énergétique. Nos travaux se concentrent sur la conception de filtres numériques sans multiplicateurs énergétiquement efficaces. Ils se décomposent en deux contributions majeures: un nouveau modèle de représentation efficace des circuits intégrés, et un algorithme innovateur destiné à la conception de filtres numériques efficaces. Dans un premier temps, notre modélisation des circuits sous la forme de graphes pondérés a l'avantage d'offrir une représentation concise des circuits intégrés, tout en annulant la symétrie présente dans les modèles de représentation actuels.Dans un second temps, notre métaheuristique, qui combine à la fois une recherche tabou et une recherche tabou itérée, offre un contrôle direct du niveau d'énergie consommée par le circuit qu'elle construit, en fixant la quantité d'additionneurs qu'il contient avant le démarrage du processus de conception. En outre, contrairement aux méthodes existantes, notre approche ne se réfère à aucune architecture spécifique afin de concevoir un circuit. Ce degré de liberté permet à notre méthode d'atteindre une optimisation plus globale de la structure du circuit en comparaison des autres méthodes et, ainsi, de posséder un contrôle plus précis de sa consommation énergétique. L'algorithme proposé est testé sur un jeu de données contenant plus de 700 filtres de complexité variée. Les résultats obtenus démontrent les performances élevées de notre approche car, en se basant sur le coût en additionneurs, dans plus de 99% des cas, notre méthode conçoit des filtres numériques avec un niveau de consommation énergétique total équivalent au niveau induit uniquement par l'architecture à laquelle les méthodes actuelles se réfèrent. En parallèle, notre méthode fournit également un meilleur contrôle de la longueur de mot interne dans les circuits, qui représente un autre aspect crucial de leur efficacité énergétique. La comparaison avec l'algorithme Heuristic cumulative benefit (Hcub) qui, à ce jour, est la méthode la plus performante montre que les filtres construits par notre algorithme utilisent 55% moins d'additionneurs que Hcub, tout en réduisant la taille de ces additionneurs de 33%. Ces améliorations sont obtenues au simple coût d'une augmentation de 17% du nombre de délais dans les circuits. Cependant, la consommation énergétique d'un délai étant de l'ordre de 20% de celle d'un additionneur, si l'on considère le nombre et la taille des additionneurs ainsi que la quantité de délais inclus dans nos circuits afin d'estimer leur consommation énergétique, on peut s'attendre à une économie globale de l'ordre de 65% en comparaison de la meilleure méthode actuelle.»----------«ABSTRACT : In today's modern society, we rely on wireless telecommunication devices that use applications and modules to perform many different tasks and are growing in their complexity day by day. Consequently, the fast evolution of these devices, which, most of the time, are battery-powered, drastically increased the importance of their energy consumption and made energy efficiency and green computing essential features of recent developments in microelectronics. To deal with the related issues, many researchers have focused their attention to designing energy-efficient digital filters, which are essential building blocks of all digital signal processing systems. Any digital filter is implemented by an integrated circuit composed by a list of basic elements, including adders, multipliers, shifts, etc. One of the paths that researchers have followed in order to decrease the amount of energy used by the integrated circuits was to replace the multipliers in the circuit structure with less energy-consuming elements such as adders, shifts and inverters. The goal of these methods is usually to perform the replacement of multipliers while using the least amount of adders, as, for multiplierless circuits, adders become the most energy-consuming elements. In fact, the quantity of adders contained in a multiplierless circuit, also known as its adder cost, is commonly used as an estimate of its power consumption. In our research we focus on energy-efficient multiplierless filters. Our work has two main contributions: a new model to efficiently represent integrated circuits, and an innovative algorithm to design efficient digital filters. On one hand, the main advantage of our new graph-based model is that it is able to represent any integrated circuit in a concise form, while avoiding symmetry in the representation. On the other hand, our metaheuristic, that combines both a tabu search and an iterated tabu search, offers a direct control of the level of energy consumed by the circuits it constructs, by fixing the number of adders that they contain. Besides, unlike other existing methods used for designing multiplierless filters, our approach does not refer to any specific architecture in the corresponding circuit structure. This degree of freedom allows our method to have a more globalized view on the optimization of circuit structure compared to the other methods, and thus, a better control on its power consumption. The proposed algorithm is tested on a benchmark containing more than 700 filters of different orders of complexity. The obtained results demonstrate the high accuracy of the proposed approach as, based on the adder cost estimation, in more than $99\%$ of the cases our method designs integrated circuits with a level of energy consumption equivalent to those implied only by the most accurate circuit architectures from which existing algorithms build their circuits, and absolutely no deviation from the desired filtering specifications. In parallel, our method also provides a better control of the internal wordlength in the circuits, which is another crucial point to improve the energy-efficiency. The comparison to the current state-of-the-art algorithm Heuristic cumulative benefit (Hcub) when designing all the benchmark filters shows that filters constructed with our algorithm are using 55% less adders than Hcub, while decreasing their size by 33%. This improvement can be reached at the cost of an increase of 17% in the number of delays in the circuits. However, by considering the number and the size of adders used in the circuit as well as the quantity of delays it contains as an estimate of the power consumed by the circuit, assuming that the energy consumption of a delay is in the order of 20% of the consumption of an adder, we can approximately expect an overall energy saving of 65% in our circuits compared to the best current method.

Open Access document in PolyPublie
Department: Département de mathématiques et de génie industriel
Academic/Research Directors: Michel Gendreau and François Gagnon
Date Deposited: 26 Mar 2012 15:15
Last Modified: 27 Jun 2019 16:49
PolyPublie URL: https://publications.polymtl.ca/755/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only