Spelling suggestions: "subject:"awitching algorithm"" "subject:"bewitching algorithm""
1 |
Analysis and optimisation of stable matching in combined input and output queued switchesSchweizer, Andreas January 2009 (has links)
Output queues in network switches are known to provide a suitable architecture for scheduling disciplines that need to provide quality of service (QoS) guarantees. However, todays memory technology is incapable of meeting the speed requirements. Combined input and output queued (CIOQ) switches have emerged as one alternative to address the problem of memory speed. When a switch of this architecture uses a stable matching algorithm to transfer packets across the switch fabric, an output queued (OQ) switch can be mimicked exactly with a speedup of only two. The use of a stable matching algorithm typically requires complex and time-consuming calculations to ensure the behaviour of an OQ switch is maintained. Stable matching algorithms are well studied in the area in which they originally appeared. However, little is presently known on how the stable matching algorithm performs in CIOQ switches and how key parameters are affected by switch size, traffic type and traffic load. Knowledge of how these conditions affect performance is essential to judge the practicability of an architecture and to provide useful information on how to design such switches. Until now, CIOQ switches were likely to be dismissed due to the high complexity of the stable matching algorithm when applied to other applications. However, the characteristics of a stable matching algorithm in a CIOQ switch have not been thoroughly analysed. The principal goal of this thesis is to identify the conditions the stable matching algorithm encounters in a CIOQ switch under realistic operational scenarios. This thesis provides accurate mathematical models based on Markov chains to predict the value of key parameters that affect the complexity and runtime of a stable matching algorithm in CIOQ switches. The applicability of the models is then backed up by simulations. The results of the analysis quantify critical operational parameters, such as the size and number of preference lists and runtime complexity. These provide detailed insights into switch behaviour and useful information for switch designs. Major conclusions to be drawn from this analysis include that the average values of the key parameters of the stable matching algorithm are feasibly small and do not strongly correlate with switch size, which is contrary to the behaviour of the stable matching ii algorithm in its original application. Furthermore, although these parameters have wide theoretical ranges, the mean values and standard deviations are found to be small under operational conditions. The results also suggest that the implementation becomes very versatile as the completion time of the stable matching algorithm is not strongly correlated to the network traffic type; that is, the runtime is minimally affected by the nature of the traffic.
|
2 |
Développement d’un convertisseur analogique-numérique innovant dans le cadre des projets d’amélioration des systèmes d’acquisition de l’expérience ATLAS au LHC / Development of an innovative analog-digital converter chip in the scope of the upgrade of data acquisition infrastructure of the ATLAS experiment at the LHCZeloufi, Mohamed 09 November 2016 (has links)
À l’horizon 2024, l’expérience ATLAS prévoit de fonctionner à des luminosités 10 fois supérieures à la configuration actuelle. Par conséquent, l’électronique actuelle de lecture ne correspondra pas aux conditions de ces luminosités. Dans ces conditions, une nouvelle électronique devra être conçue. Cette mise à niveau est rendue nécessaire aussi par les dommages causés par les radiations et le vieillissement. Une nouvelle carte frontale va être intégrée dans l’électronique de lecture du calorimètre LAr. Un élément essentiel de cette carte est le Convertisseur Analogique-Numérique (CAN) présentant une résolution de 12bits pour une fréquence d’échantillonnage de 40MS/s, ainsi qu’une résistance aux irradiations. Compte tenu du grand nombre des voies, ce CAN doit remplir des critères sévères sur la consommation et la surface. Le but de cette thèse est de concevoir un CAN innovant qui peut répondre à ces spécifications. Une architecture à approximations successives (SAR) a été choisie pour concevoir notre CAN. Cette architecture bénéficie d’une basse consommation de puissance et d’une grande compatibilité avec les nouvelles technologies CMOS. Cependant, le SAR souffre de certaines limitations liées principalement aux erreurs de décisions et aux erreurs d’appariement des capacités du CNA. Deux prototypes de CAN-SAR 12bits ont été modélisés en Matlab afin d’évaluer leur robustesse. Ensuite les conceptions ont été réalisées dans une technologie CMOS 130nm d’IBM validée par la collaboration ATLAS pour sa tenue aux irradiations. Les deux prototypes intègrent un algorithme d’approximations avec redondance en 14 étapes de conversion, qui permet de tolérer des marges d’erreurs de décisions et d’ajouter une calibration numérique des effets des erreurs d’appariement des capacités. La partie logique de nos CAN est très simplifiée pour minimiser les retards de génération des commandes et la consommation d’énergie. Cette logique exécute un algorithme monotone de commutation des capacités du CNA permettant une économie de 70% de la consommation dynamique par rapport à un algorithme de commutation classique. Grâce à cet algorithme, une réduction de capacité totale est aussi obtenue : 50% en comparant notre premier prototype à un seul segment avec une architecture classique. Pour accentuer encore plus le gain en termes de surface et de consommation, un second prototype a été réalisé en introduisant un CNA à deux segments. Cela a abouti à un gain supplémentaire d’un facteur 7,64 sur la surface occupée, un facteur de 12 en termes de capacité totale, et un facteur de 1,58 en termes de consommation. Les deux CAN consomment respectivement une puissance de ~10,3mW et ~6,5mW, et ils occupent respectivement une surface de ~2,63mm2 et ~0,344mm2.Afin d’améliorer leurs performances, un algorithme de correction numérique des erreurs d’appariement des capacités a été utilisé. Des buffers de tensions de référence ont étés conçus spécialement pour permettre la charge/décharge des capacités du convertisseur en hautes fréquences et avec une grande précision. En simulations électriques, les deux prototypes atteignent un ENOB supérieur à 11bits tout en fonctionnant à la vitesse de 40MS/s. Leurs erreurs d’INL simulés sont respectivement +1,14/-1,1LSB et +1,66/-1,72LSB.Les résultats de tests préliminaires du premier prototype présentent des performances similaires à celles d’un CAN commercial de référence sur notre carte de tests. Après la correction, ce prototype atteint un ENOB de 10,5bits et un INL de +1/-2,18LSB. Cependant suite à une panne de carte de tests, les résultats de mesures du deuxième prototype sont moins précis. Dans ces circonstances, ce dernier atteint un ENOB de 9,77bits et un INL de +7,61/-1,26LSB. En outre la carte de tests actuelle limite la vitesse de fonctionnement à ~9MS/s. Pour cela une autre carte améliorée a été conçue afin d’atteindre un meilleur ENOB, et la vitesse souhaitée. Les nouvelles mesures vont être publiées dans le futur. / By 2024, the ATLAS experiment plan to operate at luminosities 10 times the current configuration. Therefore, many readout electronics must be upgraded. This upgrade is rendered necessary also by the damage caused by years of total radiations’ effect and devices aging. A new Front-End Board (FEB) will be designed for the LAr calorimeter readout electronics. A key device of this board is a radiation hard Analog-to-Digital Converter (ADC) featuring a resolution of 12bits at 40MS/s sampling rate. Following the large number of readout channels, this ADC device must display low power consumption and also a low area to easy a multichannel design.The goal of this thesis is to design an innovative ADC that can deal with these specifications. A Successive Approximation architecture (SAR) has been selected to design our ADC. This architecture has a low power consumption and many recent works has shown his high compatibility with modern CMOS scaling technologies. However, the SAR has some limitations related to decision errors and mismatches in capacitors array.Using Matlab software, we have created the models for two prototypes of 12bits SAR-ADC which are then used to study carefully their limitations, to evaluate their robustness and how it could be improved in digital domain.Then the designs were made in an IBM 130nm CMOS technology that was validated by the ATLAS collaboration for its radiation hardness. The prototypes use a redundant search algorithm with 14 conversion steps allowing some margins with comparator’s decision errors and opening the way to a digital calibration to compensate the capacitors mismatching effects. The digital part of our ADCs is very simplified to reduce the commands generation delays and saving some dynamic power consumption. This logic follows a monotonic switching algorithm which saves about70% of dynamic power consumption compared to the conventional switching algorithm. Using this algorithm, 50% of the total capacitance reduction is achieved when one compare our first prototype using a one segment capacitive DAC with a classic SAR architecture. To boost even more our results in terms of area and consumption, a second prototype was made by introducing a two segments DAC array. This resulted in many additional benefits: Compared to the first prototype, the area used is reduced in a ratio of 7,6, the total equivalent capacitance is divided by a factor 12, and finally the power consumption in improved by a factor 1,58. The ADCs respectively consume a power of ~10,3mW and ~6,5mW, and they respectively occupy an area of ~2,63mm2 and ~0,344mm2.A foreground digital calibration algorithm has been used to compensate the capacitors mismatching effects. A high frequency open loop reference voltages buffers have been designed to allow the high speed and high accuracy charge/discharge of the DAC capacitors array.Following electrical simulations, both prototypes reach an ENOB better than 11bits while operating at the speed of 40MS/s. The INL from the simulations were respectively +1.14/-1.1LSB and +1.66/-1.72LSB.The preliminary testing results of the first prototype are very close to that of a commercial 12bits ADC on our testing board. After calibration, we measured an ENOB of 10,5bits and an INL of +1/-2,18LSB. However, due to a testing board failure, the testing results of the second prototype are less accurate. In these circumstances, the latter reached an ENOB of 9,77bits and an INL of +7,61/-1,26LSB. Furthermore the current testing board limits the operating speed to ~9MS/s. Another improved board was designed to achieve a better ENOB at the targeted 40MS/s speed. The new testing results will be published in the future.
|
Page generated in 0.0519 seconds