Hybrid error control techniques to improve data communication performance for noisy channels have been extensively studied. However, a growing concern in communication system design is the impact of delay due to retransmissions and/or delay-prone technologies on system performance. Previous analyses have not considered various delay aspects of a hybrid error control system. Efficient error control techniques which are able to provide improved coding gain and throughput by promptly matching the error correction coding capability with the changing channel conditions have yet to be developed and investigated. In this thesis, delay-related performance characteristics are investigated for asynchronous time division multiplexing links. Two different methods based on an imbedded Markov chain model are developed and applied to the system with a noisy feedback channel, yielding analytical expressions for the buffer occupancy and the block delay. A recursive expression for packet loss probability for systems with a finite transmitter buffer is obtained. The concept of delay-limited error control coding is introduced for real-time communications. Performance improvement by truncation of a type-II hybrid-ARQ protocol with one retransmission is investigated in detail. It is shown that the truncated protocol has a bounded delay and bounded queue length under typical communication traffic conditions. The error performance of the truncated protocol is further analyzed for various mobile fading channels. Matched-rate hybrid error control coding for both adaptive and non-adaptive cases is also studied. A new adaptive error control protocol using Reed-Solomon codes is proposed. The protocol uses novel feedback transmissions to achieve faster estimation of channel states. Numerical optimization is carried out by introducing overall throughput and modified throughput as efficiency criteria. Based on channel bit error rate measurement, optimum overall throughput is obtained with minimum implementation complexity. Our general conclusions are: (1) Both delay and packet loss can be greatly reduced by incorporating a Reed-Solomon code into the data-link protocol for noisy channels. (2) The truncated hybrid error control protocol can provide coding gain improvement and reduced delay over the conventional (untruncated) protocol. (3) Throughput efficiency of a type-I or type-II hybrid-ARQ protocol can be significantly improved by using the proposed matched-rate error control techniques. / Graduate

No description available.

The distribution of real-time multimedia streams is seen nowadays as the next step forward for the Internet. One of the most obvious uses of such streams is to support telephony over the Internet, replacing and improving traditional telephony. This thesis investigates the development and deployment of services in two Internet telephony environments, namely CINEMA (Columbia InterNet Extensible Multimedia Architecture) and VOCAL (Vovida Open Communication Application Library), both based on the Session Initiation Protocol (SIP) and open-sourced. A classification of services is proposed, which divides services into two large groups: basic and advanced services. Basic services are services such as making point-to-point calls, registering with the server and making calls via the server. Any other service is considered an advanced service. Advanced services are defined by four categories: Call Related, Interactive, Internetworking and Hybrid. New services were implemented for the Call Related, Interactive and Internetworking categories. First, features involving call blocking, call screening and missed calls were implemented in the two environments in order to investigate Call-related services. Next, a notification feature was implemented in both environments in order to investigate Interactive services. Finally, a translator between MGCP and SIP was developed to investigate an Internetworking service in the VOCAL environment. The practical implementation of the new features just described was used to answer questions about the location of the services, as well as the level of required expertise and the ease or difficulty experienced in creating services in each of the two environments. / KMBT_363 / Adobe Acrobat 9.54 Paper Capture Plug-in

Cette thèse porte sur l'élaboration d'un micro-noyau original de type hyperviseur, appelé Ker-ONE, permettant de gérer la virtualisation pour des systèmes embarqués sur des plateformes de type SoC et fournissant un environnement pour les machines virtuelles en temps réel. Nous avons simplifié l'architecture du micro-noyau en ne gardant que les caractéristiques essentielles requises pour la virtualisation, et fortement réduit la complexité de la conception du noyau. Sur cette base, nous avons mis en place un mécanisme capable de gérer des ressources reconfigurables dans un système supportant des machines virtuelles. Les accélérateurs matériels reconfigurables sont mappés en tant que dispositifs classiques dans chaque machine. Grâce à une gestion efficace de la mémoire dédiée, nous détectons automatiquement le besoins de ressources et permettons une allocation dynamique des ressources sur FPGA. Suite à diverses expériences et évaluations sur la plateforme Zynq-7000, combinant ARM et ressources FPGA, nous avons montré que Ker-ONE ne dégrade que très peu les performances en termes de temps d'exécution. Les surcoûts engendrés peuvent généralement être ignorés dans les applications réelles. Nous avons également étudié l'ordonnançabilité temps réel dans les machines virtuelles. Les résultats montrent que le respect de l'échéance des tâches temps réel est garanti. Nous avons également démontré que le noyau proposé est capable d'allouer des accélérateurs matériels très rapidement. / This thesis describes an original micro-kernel that manages virtualization and that provides an environment for real-time virtual machines. We have simplified the micro-kernel architecture by only keeping critical features required for virtualization, and massively reduced the kernel design complexity. Based on this micro-kernel, we have introduced a framework capable of DPR resource management in a virtual machine system. DPR accelerators are mapped as ordinary devices in each VM. Through dedicated memory management, our framework automatically detects the request for DPR resources and allocates them dynamically. According to various experiments and evaluations on the Zynq-7000 platform we have shown that Ker-ONE causes very low virtualization overheads, which can generally be ignored in real applications. We have also studied the real-time schedulability in virtual machines. The results show that RTOS tasks are guaranteed to be scheduled while meeting their intra-VM timing constraints. We have also demonstrated that the proposed framework is capable of virtual machine DPR allocation with low overhead.

L'utilisation de la virtualisation dans le domaine des serveurs d'entreprise est aujourd'hui une méthode courante. La virtualisation est une technique qui permet de faire fonctionner sur une seule machine réelle plusieurs systèmes d'exploitation. Cette technique est train d'être adoptée dans le développement des systèmes embarqués suite à la disponibilité de nouveaux processeurs classiquement destiné à ce domaine. Cependant, il y a une différence de contraintes entre les applications d'entreprise et les applications embarquées, celleci doivent respecter des contraintes de temps-réel en réalisant leurs tâches. Dans nos travaux de recherche nous avons étudié l'impact de la virtualisation sur un système d'exploitation temps-réel. Nous avons mesuré le surcoût et la latence des fonctions internes du système d'exploitation déployé sur une machine virtuelle, et nous les avons comparés à celles du système installé sur une machine réelle. Les résultats ont montré que ces métriques sont plus élevées lorsque la virtualisation est utilisée. Notre analyse a révélé que la puce électronique doit inclure des mécanismes matériels qui assistent le logiciel de contrôle des machines virtuelles afin de réduire le surcoût de la virtualisation, mais il est aussi essentiel de choisir une politique d'allocation des ressources efficace afin de garantir le respect des contraintes de temps-réel demandées par les machines virtuelles. Notre second axe de recherche concerne la transformation d'un modèle de simulation d'un système d'exploitation vers des programmes exécutables sur un système-sur-puce. Cette transformation doit également préserver une caractéristique offerte par ce modèle qui est la facilité de configuration des techniques d'allocation de ressources. Pour transformer le modèle de système d'exploitation nous avons utilisé des techniques de l'ingénierie-dirigée par les modèles. Où dans un premier temps le modèle initiale est transformé vers un autre modèle, ensuite ce second modèle est à son tour transformé automatiquement en un code source. Pour assurer la configuration du système d'exploitation finale nous avons utilisé une librairie placée entre le système d'exploitation et l'application afin d'identifier les besoins de celle-ci en termes de ressources et adapter le système à ces besoins. L'évaluation des performances de la librairie a démontré la viabilité de l'approche. / In the domain of server and mainframe systems, virtualizing a computing system's physical resources to achieve improved sharing and utilization has been well established for decades. Full virtualization of all system resources makes it possible to run multiple guest operating systems on a single physical platform. Recently, the availability of full virtualization on physical platforms that target embedded systems creates new use-cases in the domain of real-time embedded systems. In this dissertation we use an existing “virtual machines monitor” to evaluate the performance of a real-time operating system. We observed that the virtual machine monitor affects the internal overheads and latencies of the guest OS. Our analysis revealed that the hardware mechanisms that allow a virtual machine monitor to provide an efficient way to virtualize the processor, the memory management unit, and the input/output devices, are necessary to limit the overhead of the virtualization. More importantly, the scheduling of virtual machines by the VMM is essential to guarantee the temporal constraints of the system and have to be configured carefully. In a second work and starting from a previous project aiming at allowing a system designer to explore a software-hardware codesign of a solution using high-level simulation models, we proposed a methodology that allows the transformation of a simulation model into a binary executable on a physical platform. The idea is to provide the system designer with the necessary tools to rapidly explore the design space and validate it, and then to generate a configuration that could be used directly on top of a physical platform. We used a model-driven engineering approach to perform a model-to-model transformation to convert the simulation model into an executable model. And we used a middleware able to support a variety of the resources allocation techniques in order to implement the configuration previously selected by the system designer at simulation phase. We proposed a prototype that implements our methodology and validate our concepts. The results of the experiments confirmed the viability of this approach.

Hard real-time systems in robotics, space and military missions, and control devices are specified with stringent and critical time constraints. On the other hand, soft real-time applications arising from multimedia, telecommunications, Internet web services, and games are specified with more lenient constraints. Real-time systems can also be distinguished in terms of their implementation into preemptive and non-preemptive systems. In preemptive systems, tasks are often preempted by higher priority tasks. Non-preemptive systems are gaining interest for implementing soft-real applications on multithreaded platforms. In this dissertation, I propose a new algorithm that uses a two-level scheduling strategy for scheduling non-preemptive soft real-time tasks. Our goal is to improve the success ratios of the well-known earliest deadline first (EDF) approach when the load on the system is very high and to improve the overall performance in both underloaded and overloaded conditions. Our approach, known as group-EDF (gEDF), is based on dynamic grouping of tasks with deadlines that are very close to each other, and using a shortest job first (SJF) technique to schedule tasks within the group. I believe that grouping tasks dynamically with similar deadlines and utilizing secondary criteria, such as minimizing the total execution time can lead to new and more efficient real-time scheduling algorithms. I present results comparing gEDF with other real-time algorithms including, EDF, best-effort, and guarantee scheme, by using randomly generated tasks with varying execution times, release times, deadlines and tolerances to missing deadlines, under varying workloads. Furthermore, I implemented the gEDF algorithm in the Linux kernel and evaluated gEDF for scheduling real applications.

En Réalité Virtuelle (RV), le sens haptique accroît l’immersion d’un utilisateur dans un Environnement Virtuel (EV) avec lequel il interagit en temps réel. Dans cette thèse, nous proposons des approches pour améliorer l’interaction haptique à deux mains avec des EV. Nous abordons d’abord des problèmes avec l’interaction bimanuelle dans des EV avec des interfaces à effecteur unique. Nous proposons une technique d’interaction nommée la double bulle pour l’exploration d’EV avec une combinaison de contrôle en position et en vitesse. Nous présentons aussi une technique de manipulation nommée prise magnétique qui facilite la saisie d’objets virtuels avec des proxys rigides simples. Des modes de contrôle communs sont utilisés pour améliorer la saisie et l’exploration simultanées. Une évaluation utilisateur a été réalisée pour mesurer l’efficacité de ces techniques. Nous nous intéressons ensuite au calcul de surfaces de contact. Nous proposons une technique nommée god-finger pour rendre des surfaces similaires à celles générées par des doigts à partir d’un unique point de contact. Elle est basée sur un simple parcours de la géométrie locale de l’objet en contact, et est donc moins coûteuse que des méthodes de simulation de corps souples. La méthode est adaptée pour l’interaction avec des proxys rigides simples ou plus complexes, ainsi qu’avec des objets rigides ou déformables, y compris avec des surfaces rugueuses. Une méthode de rendu visuel donne un retour à l’utilisateur sur la forme de la surface de contact. Enfin, nous abordons la résolution de contacts durant la manipulation dextre d’objets virtuels avec des doigts souples. Le calcul des mécaniques de contact est amélioré en agrégeant les multiples contraintes de contact concernées. Une méthode de distribution de pression non uniforme sur la surface de contact adapte la réponse lors d’un contact contre des arêtes pointues. Nous utilisons le modèle de frottement de Coulomb- Contensou pour simuler efficacement le frottement en torsion. L’approche est évaluée avec un modèle de main déformable pour de l’interaction en temps réel. Les travaux présentés dans ce manuscrit ouvrent de nouvelles perspectives dans le contexte de l’haptique bimanuelle et de la RV, en permettant une interaction plus naturelle avec des EV plus complexes. / In Virtual Reality (VR), the haptic sense increases the immersion of users in a Virtual Environment (VE) with which they interact in real time. In this Ph.D thesis, we propose contributions to improve two-handed interaction in haptics with VEs. We first address issues with bimanual interaction in VEs using haptic devices with single effectors. We propose an interaction technique called double bubble for exploration of VEs through a combination of position and rate control. We also present a manipulation technique called magnetic pinch which facilitates the grasping of virtual objects with simple rigid proxies. Simultaneous grasping and exploration of the VE is enhanced using common control modes. A user evaluation was conducted to assess the efficiency of these techniques. We then focus on improving the computation of contact surfaces. We propose a god-finger method to render finger padlike surfaces from a single contact point. It relies on a simple scan of the local geometry of the object in contact, and is this less costly than soft body simulation methods. The method is adapted for interaction using simple or more complex rigid virtual proxies, and with rigid or deformable objects, including rough surfaces. A visual rendering method provides feedback on the shape of the contact surface. Finally, we address the resolution of contacts during dexterous manipulation of virtual objects through soft fingers. The computation of contact mechanics is improved by aggregating the multiple contact constraints involved. A method for nonuniform pressure distribution over the contact surface adapts the response when touching sharp edges. We use the Coulomb-Contensou friction model to efficiently simulate torsional friction. The approach is evaluated with a deformable hand model for real time interaction. The contributions of this manuscript open novel perspectives in the context of bimanual haptics and VR, allowing more natural interaction with more complex VEs.

The increasing demand for high-capacity and high-speed I/Os is pushing wireline and optical transceivers to a higher aggregate data rate. Multiple lanes of transceivers are monolithically integrated on a single system on chip (SoC), bringing more stringent requirements for the power consumption and area of a single transceiver. Clocking circuits directly determine the transceiver data rate and take a significant portion of the total power consumption. Power-efficient and high-speed data links rely on efficient and high-performance clock generation and distribution. Multi-phase clock generators (MPCGs) and phase interpolators (PIs) are two essential blocks in the local clock generator in each transceiver lane. MPCGs can generate multi-phase sampling clocks to increase the sampling rate of a fixed frequency, or they can generate multi-phase input clocks for the PIs to perform phase shifting. Their design also affects the schemes for global clock generation and distribution. 8-phase PIs improve the interpolation linearity compared to 4-phase PIs. However, their input 8-phase clock generation either requires power-hungry, multi-phase global clock distribution, or a complicated local 8-phase clock generator. Conventional clocking techniques have encountered the tradeoff of the jitter, power and phase accuracy for multi-phase clock generation. Moreover, 8-phase PIs also meet the linearity and speed bottleneck due to technology limitations. In this dissertation, we first discuss ring oscillators for multi-phase clock generation. The tradeoff of jitter and phase accuracy in ring oscillators locked by two-phase (0°/180°) injection is presented. This tradeoff is resolved by using a multi-phase injection-locked ring oscillator (MPIL-ROSC) for multi-phase clock generation. A quadrature delay-locked loop (QDLL) provides the coarse but low-jitter multi-phase injection signals to the MPIL-ROSC, and also tunes the MPIL-ROSC's self-oscillation frequency against process-voltage-temperature (PVT) variations. The MPCG is designed for 8-phase clock generation, and drives an 8-phase PI for clock interpolation. A 65-nm prototype chip shows that an MPIL-ROSC can generate low-jitter and highly accurate 8-phase clocks from 5 GHz to 8 GHz under a 1.1-V to 1.3-V supply variation. Moreover, a 7-bit PI driven by the MPIL-ROSC also achieves a peak-to-peak integral nonlinearity (INLpp) less than 1.90 LSB from 5 GHz to 8 GHz. To further improve the phase interpolation linearity and operation frequency range, a Twin phase interpolator (Twin PI) and a Delta quadrature delay-locked loop (Delta QDLL) are introduced. The phase nonlinearity of a 4-phase, linear-weight PI stems from approximating sinusoidal-weight summation with linear-weight summation. Consequently, the phase deviations are deterministic, sinusoidal, and repeat themselves among different interpolation quadrants. The Twin PI sums up the equalized-amplitude outputs from two, 4-phase PIs with their PI control codes offset by half of the INL "period". The INLs of two PIs have opposite signs to each other, and thus the summation cancels the majority of nonlinearity. The Twin PI achieves very high linearity across a wide operation bandwidth while only needing 4-phase (quadrature) input clocks, which eases the design of its preceding multi-phase clock generator and offers flexibility for global clock generation and distribution scheme. A Delta quadrature delay-locked loop is further proposed for low-jitter and wideband quadrature clock generation from the delay difference of two parallel delay paths with a background analog quadrature tuning loop. A 65-nm prototype chip demonstrates that a Delta QDLL generates quadrature clocks with an accuracy of 0.9° from 3.5 GHz to 11 GHz. The 7-bit Twin PI achieves less-than-1.45-LSB INLpp from 3.5 GHz to 11 GHz. At 7 GHz the INLpp is 0.72 LSB and the integrated fractional spur is as low as -41.7 dBc under -1429ppm clock modulation. To sum up, the proposed multi-phase injection-locked ring oscillators for multi-phase clock generation, and the combination of Twin phase interpolators and Delta quadrature delay-locked loop break the performance limitation of the state-of-the-art clocking circuits. The block-level innovation also offers opportunities to reconsider the global clocking scheme to save power and circuit area at the system level.

No description available.

The design of an I/O Controller capable of processing data in real time in a tactical training simulator is presented. The controller consists of two microprocessor systems that communicate with peripherals by means of programmed I/O, and with the host computer by Direct Memory Access (DMA) and a serial RS232 link. This thesis addresses both the hardware and software aspects of the controller design.