A Execução Condicional Dinâmica (DCE) é uma alternativa para redução dos custos relacionados a desvios previstos incorretamente. A idéia básica é buscar todos os fluxos produzidos por um desvio que obedecem algumas restrições relativas à complexidade e tamanho. Como conseqüência, um número menor de previsões é executado, e assim, um número mais baixo de desvios é incorretamente previsto. Contudo, tal como outras soluções multi-fluxo, o DCE requer uma estrutura de controle mais complexa. Na arquitetura DCE, é observado que várias réplicas da mesma instrução são despachadas para as unidades funcionais, bloqueando recursos que poderiam ser utilizados por outras instruções. Essas réplicas são geradas após o ponto de convergência dos diversos fluxos em execução e são necessárias para garantir a semântica correta entre instruções dependentes de dados. Além disso, o DCE continua produzindo réplicas até que o desvio que gerou os fluxos seja resolvido. Assim, uma seção completa do código pode ser replicado, reduzindo o desempenho. Uma alternativa natural para esse problema é reusar essas seções (ou traços) que são replicadas. O objetivo desse trabalho é analisar e avaliar a efetividade do reuso de valores na arquitetura DCE. Como será apresentado, o princípio do reuso, em diferentes granularidades, pode reduzir efetivamente o problema das réplicas e levar a aumentos de desempenho. / The Dynamic Conditional Execution (DCE) is an alternative to reduce the cost of mispredicted branches. The basic idea is to fetch all paths produced by a branch that obey certain restrictions regarding complexity and size. As a consequence, a smaller number of predictions is performed, and therefore, a lower number branches is mispredicted. Nevertheless, as other multipath solutions, DCE requires a more complex control engine. In a DCE architecture, one may observe that several replicas of the same instruction are dispatched to the functional units, blocking resources that might be used by other instructions. Those replicas are produced after the join point of the paths and are required to guarantee the correct semantic among data dependent instructions. Moreover, DCE continues producing replicas until the branch that generated the paths is resolved. Thus, a whole section of code may be replicated, harming performance. A natural alternative to this problem is the attempt to reuse those replicated sections, namely the replicated traces. The goal of this work is to analyze and evaluate the effectiveness of value reuse in DCE architecture. As it will be presented, the principIe of reuse, in different granularities, can reduce effectively the replica problem and lead to performance improvements.

Ce travail de thèse porte sur la modélisation des phénomènes de propagation affectant les signaux de navigation par satellite en environnement urbain dense avec une focalisation particulière sur les multitrajets et l'aspect large bande du canal de propagation espace/Terre. Le simulateur de canal pseudo temps-réel développé, SCHUN (Simplified CHannel for Urban Navigation), repose sur une approche hybride physico-statistique. La composante statistique de la modélisation permet essentiellement de générer une ville virtuelle à partir de distributions de bâtiments connues. Le reste de la modélisation s'appuie sur une approche physique simplifiée où les interactions ondes électromagnétiques/ville virtuelle reposent d'une part sur un modèle de macro-diffusion à l'échelle des façades, (3CM (Three Component Model)), et d'autre part sur un modèle physique de masquage du trajet direct par les bâtiments. Les principales méthodes numériques sous-jacentes sont l'optique physique et la théorie uniforme de la diffraction. Le simulateur de canal SCHUN ouvre aujourd'hui des perspectives intéressantes pour la modélisation large bande du canal de propagation espace/Terre. Optimisé pour des temps de calcul raisonnables, alliant une composante statistique à une composante physique simplifiée, ce simulateur a été conçu et validé par des mesures expérimentales pour répondre à des besoins de simulation des systèmes à diversité de satellite, diversité de réception, diversité de polarisation ou encore diversité de fréquence pour des applications de navigation par satellite. / This PhD work deals with land mobile satellite channel modelling and addresses the specific issue of satellite navigation systems in urban environments with a particular focus on multipath modelling and wide-band representation of the channel. The developed land mobile satellite channel simulator, SCHUN (Simplified CHannel for Urban Navigation), is based on a hybrid physical-statistical approach satisfying fast computation requirements. The statistical component of the modelling is mainly used during the virtual city synthesis step based on known statistical distributions of building height and street width. The rest of the modelling comes from deterministic methods using simplified electromagnetic interaction models reproducing building macro-scattering (3CM model (Three Component Model)) and building blockage of the direct path. The main underlying electromagnetic methods are the physical optics and the uniform theory of diffraction. The SCHUN simulator now opens interesting perspectives for the modelling of wide-band land mobile satellite propagation channel in dense urban environments. Optimised for pseudo real-time constraints, it uses both physical and statistical approaches. Furthermore, the SCHUN simulator has been designed and validated against measurements to answer specific needs of satellite diversity, receiving diversity, polarisation diversity or frequency diversity for satellite navigation applications.

Durant la dernière décennie, les systèmes de navigation par satellites ont obtenu une place majeure dans le développement d’application de navigation urbaine et les services associés. L’environnement urbain pose plusieurs défis à la réception des signaux GNSS, comprenant les multi-trajets et le phénomène de blocage des signaux directs, qui peuvent se traduire dans le domaine de la position, par une diminution de la précision de la solution de navigation voire par une indisponibilité de la position. Dans cette situation, la poursuite vectorielle constitue une approche intéressante capable de contrecarrer les effets propres à un environnement urbain tels que les multi-trajets, les réceptions de signaux non directs et les interruptions de signal. Cette thèse s’intéresse particulièrement à la proposition et au design d’une architecture double constellation GPS + Galileo, mono-fréquence L1/E1 VDFLL pour les véhicules routiers en milieu urbain. Concernant la navigation, le VDFLL représente une application concrète de la fusion d’information dû au fait que tous les canaux de poursuite sont contrôlés par le même filtre de navigation sous la forme d’un Filtre de Kalman Étendu (EKF). Le choix de l’architecture double constellation mono-fréquence a pour but d’augmenter le nombre de mesures et garantit une faisabilité bas coût du récepteur mobile. De plus, l’utilisation des signaux de mono-fréquence L1 implique la prise en compte des perturbations causées par la ionosphère. Malgré l’application des modèles de corrections ionosphérique, un résidu d’erreur ionosphérique reste toujours présent. L’originalité de ce travail repose sur l’implémentation d’une architecture VDFLL double constellation capable d’estimer le résidu d’erreurs ionosphériques présent sur les observations reçues. Ce doctorat analyse les avantages apportés par la solution proposée par rapport à la poursuite scalaire au regard de performances de positionnement et de robustesse de poursuite dans le cadre d’une trajectoire de véhicule en milieu urbain et en présence de multi-trajets et de résidus d’erreur ionosphérique. / In the last decade, Global Navigation Satellites Systems (GNSS) have gained a significant position in the development of urban navigation applications and associated services. The urban environment presents several challenges to GNSS signal reception, such as multipath and GNSS Line-of-Sight (LOS) blockage, which are translated in the positioning domain in a decreased navigation solution accuracy up to the lack of an available position. For this matter, Vector Tracking (VT) constitutes a promising approach able to cope with the urban environment-induced effects including multipath, NLOS reception and signal outages. This thesis is particularly focused on the proposal and design of a dual constellation GPS + Galileo single frequency L1/E1 Vector Delay Frequency Lock Loop (VDFLL) architecture for the automotive usage in urban environment. From the navigation point of view, VDFLL represents a concrete application of information fusion, since all the satellite tracking channels are jointly tracked and controlled by the common navigation Extended Kalman filter (EKF). The choice of the dual-constellation single frequency vector tracking architecture ensures an increased number of observations and at the same time allowing the conservation of the low-cost feasibility criteria of the mobile user’s receiver. Moreover, the use of single frequency L1 band signals implies the necessity of taking into account the ionospheric error effect. In fact, even after the application of the ionosphere error correction models, a resultant ionospheric residual error still remains in the received observations. The originality of this work relies on the implementation of a dual-constellation VDFLL architecture, capable of estimating the ionosphere residual error present in the received observations. This dissertation investigates the VDFLL superiority w.r.t the scalar tracking receiver in terms of positioning performance and tracking robustness for a real car trajectory in urban area in the presence of multipath and ionosphere residual error.

Since the creation of the system Navstar/GPS, several sources of observation errors went identified and studied by the scientific community, like as solution of ambiguities, delay ionospheric and non clock synchronous. The problem of the mistake caused by the multipath, however, persists as a challenge, especially for applications that demand larger accuracy and precision. In the case of Brazil, with the promulgation in 2001 of the Law 10267 of the National Cadaster of Rural Properties, this challenge have a specific feature, therefore it influences the applicability of the new cadastral system. The manufacturing companies of GPS receivers has been making great investments in research in that meaning, especially in level of project of receivers. This work analyses the applied technologies in two models of GPS receivers quite a lot used in the State of Rio Grande do Sul, BR, in other words, Ashtech Promark2 and Leica GS20, as well as to analyze the success of those technologies in level of representative field conditions of the reality of geodetic surveys in the State. The results show great potential of use of those receivers to certification works by Instituto Nacional de Colonização e Reforma Agrária (INCRA), as well as they evidences limit situations in that the employment of the same ones is not advised. / Desde a criação do sistema Navstar/GPS, várias fontes de erros nas observáveis foram sendo identificadas e estudadas pela comunidade científica, tais como a solução de ambigüidades, o atraso ionosférico e o não sincronismo de relógios. O problema do erro causado pelo multicaminho, no entanto, persiste como um desafio, especialmente para aplicações que exigem maior acurácia e precisão. No caso do Brasil, com a promulgação em 2001 da Lei 10267 que institui o Cadastro Nacional de Imóveis Rurais, este desafio passou a ter uma conotação específica, pois influencia a aplicabilidade do novo sistema cadastral. As empresas fabricantes de receptores GPS tem feito grandes investimentos em pesquisa nesse sentido, especialmente em nível de projeto dos seus receptores. A presente pesquisa busca estudar as tecnologias aplicadas em dois modelos de receptores GPS bastante utilizados no Estado do Rio Grande do Sul que são, o Ashtech Promark2 e o Leica GS20, bem como analisar o sucesso dessas tecnologias em nível de condições de campo representativas da realidade do georreferenciamento no Estado. Os resultados mostram grande potencial de uso desses receptores para trabalhos de certificação junto ao INCRA, bem como evidenciam situações limites em que o emprego dos mesmos fica prejudicado.

Esta tese apresenta DCE, ou Execução Dinâmica Condicional, como uma alternativa para reduzir o custo da previsão incorreta de desvios. A idéia básica do modelo apresentado é buscar e executar todos os caminhos de desvios que obedecem à certas restrições no que diz respeito a complexidade e tamanho. Como resultado, tem-se um número menor de desvios sendo previstos e consequentemente um número menor de desvios previstos incorretamente. DCE busca todos os caminhos dos desvios selecionados evitando quebras no fluxo de busca quando estes desvios são buscados. Os caminhos buscados dos desvios selecionados são então executados mas somente o caminho correto é completado. Nesta tese nós propomos uma arquitetura para executar múltiplos caminhos dos desvios selecionados. A seleção dos desvios ocorre baseada no tamanho do desvio e em outras condições. A seleção de desvios simples e complexos permite a predicação dinâmica destes desvios sem a necessidade da existência de um conjunto específico de instruções nem otimizações especiais por parte do compilador. Além disso, é proposta também uma técnica para reduzir a sobrecarga gerada pela execução dos múltiplos caminhos dos desvios selecionados. O desempenho alcançado atinge níveis de até 12% quando um previsor de desvios Local é usado no DCE e um previsor Global é usado na máquina de referência. Quando ambas as máquinas empregam previsão Local, há um aumento de desempenho da ordem de 3-3.5%. / This thesis presents DCE, or Dynamic Conditional Execution, as an alternative to reduce the cost of mispredicted branches. The basic idea is to fetch all paths produced by a branch that obey certain restrictions regarding complexity and size. As a result, a smaller number of predictions is performed, and therefore, a lesser number of branches are mispredicted. DCE fetches through selected branches avoiding disruptions in the fetch flow when these branches are fetched. Both paths of selected branches are executed but only the correct path commits. In this thesis we propose an architecture to execute multiple paths of selected branches. Branches are selected based on the size and other conditions. Simple and complex branches can be dynamically predicated without requiring a special instruction set nor special compiler optimizations. Furthermore, a technique to reduce part of the overhead generated by the execution of multiple paths is proposed. The performance achieved reaches levels of up to 12% when comparing a Local predictor used in DCE against a Global predictor used in the reference machine. When both machines use a Local predictor, the speedup is increased by an average of 3-3.5%.

A Execução Condicional Dinâmica (DCE) é uma alternativa para redução dos custos relacionados a desvios previstos incorretamente. A idéia básica é buscar todos os fluxos produzidos por um desvio que obedecem algumas restrições relativas à complexidade e tamanho. Como conseqüência, um número menor de previsões é executado, e assim, um número mais baixo de desvios é incorretamente previsto. Contudo, tal como outras soluções multi-fluxo, o DCE requer uma estrutura de controle mais complexa. Na arquitetura DCE, é observado que várias réplicas da mesma instrução são despachadas para as unidades funcionais, bloqueando recursos que poderiam ser utilizados por outras instruções. Essas réplicas são geradas após o ponto de convergência dos diversos fluxos em execução e são necessárias para garantir a semântica correta entre instruções dependentes de dados. Além disso, o DCE continua produzindo réplicas até que o desvio que gerou os fluxos seja resolvido. Assim, uma seção completa do código pode ser replicado, reduzindo o desempenho. Uma alternativa natural para esse problema é reusar essas seções (ou traços) que são replicadas. O objetivo desse trabalho é analisar e avaliar a efetividade do reuso de valores na arquitetura DCE. Como será apresentado, o princípio do reuso, em diferentes granularidades, pode reduzir efetivamente o problema das réplicas e levar a aumentos de desempenho. / The Dynamic Conditional Execution (DCE) is an alternative to reduce the cost of mispredicted branches. The basic idea is to fetch all paths produced by a branch that obey certain restrictions regarding complexity and size. As a consequence, a smaller number of predictions is performed, and therefore, a lower number branches is mispredicted. Nevertheless, as other multipath solutions, DCE requires a more complex control engine. In a DCE architecture, one may observe that several replicas of the same instruction are dispatched to the functional units, blocking resources that might be used by other instructions. Those replicas are produced after the join point of the paths and are required to guarantee the correct semantic among data dependent instructions. Moreover, DCE continues producing replicas until the branch that generated the paths is resolved. Thus, a whole section of code may be replicated, harming performance. A natural alternative to this problem is the attempt to reuse those replicated sections, namely the replicated traces. The goal of this work is to analyze and evaluate the effectiveness of value reuse in DCE architecture. As it will be presented, the principIe of reuse, in different granularities, can reduce effectively the replica problem and lead to performance improvements.

Esta tese apresenta DCE, ou Execução Dinâmica Condicional, como uma alternativa para reduzir o custo da previsão incorreta de desvios. A idéia básica do modelo apresentado é buscar e executar todos os caminhos de desvios que obedecem à certas restrições no que diz respeito a complexidade e tamanho. Como resultado, tem-se um número menor de desvios sendo previstos e consequentemente um número menor de desvios previstos incorretamente. DCE busca todos os caminhos dos desvios selecionados evitando quebras no fluxo de busca quando estes desvios são buscados. Os caminhos buscados dos desvios selecionados são então executados mas somente o caminho correto é completado. Nesta tese nós propomos uma arquitetura para executar múltiplos caminhos dos desvios selecionados. A seleção dos desvios ocorre baseada no tamanho do desvio e em outras condições. A seleção de desvios simples e complexos permite a predicação dinâmica destes desvios sem a necessidade da existência de um conjunto específico de instruções nem otimizações especiais por parte do compilador. Além disso, é proposta também uma técnica para reduzir a sobrecarga gerada pela execução dos múltiplos caminhos dos desvios selecionados. O desempenho alcançado atinge níveis de até 12% quando um previsor de desvios Local é usado no DCE e um previsor Global é usado na máquina de referência. Quando ambas as máquinas empregam previsão Local, há um aumento de desempenho da ordem de 3-3.5%. / This thesis presents DCE, or Dynamic Conditional Execution, as an alternative to reduce the cost of mispredicted branches. The basic idea is to fetch all paths produced by a branch that obey certain restrictions regarding complexity and size. As a result, a smaller number of predictions is performed, and therefore, a lesser number of branches are mispredicted. DCE fetches through selected branches avoiding disruptions in the fetch flow when these branches are fetched. Both paths of selected branches are executed but only the correct path commits. In this thesis we propose an architecture to execute multiple paths of selected branches. Branches are selected based on the size and other conditions. Simple and complex branches can be dynamically predicated without requiring a special instruction set nor special compiler optimizations. Furthermore, a technique to reduce part of the overhead generated by the execution of multiple paths is proposed. The performance achieved reaches levels of up to 12% when comparing a Local predictor used in DCE against a Global predictor used in the reference machine. When both machines use a Local predictor, the speedup is increased by an average of 3-3.5%.

A Execução Condicional Dinâmica (DCE) é uma alternativa para redução dos custos relacionados a desvios previstos incorretamente. A idéia básica é buscar todos os fluxos produzidos por um desvio que obedecem algumas restrições relativas à complexidade e tamanho. Como conseqüência, um número menor de previsões é executado, e assim, um número mais baixo de desvios é incorretamente previsto. Contudo, tal como outras soluções multi-fluxo, o DCE requer uma estrutura de controle mais complexa. Na arquitetura DCE, é observado que várias réplicas da mesma instrução são despachadas para as unidades funcionais, bloqueando recursos que poderiam ser utilizados por outras instruções. Essas réplicas são geradas após o ponto de convergência dos diversos fluxos em execução e são necessárias para garantir a semântica correta entre instruções dependentes de dados. Além disso, o DCE continua produzindo réplicas até que o desvio que gerou os fluxos seja resolvido. Assim, uma seção completa do código pode ser replicado, reduzindo o desempenho. Uma alternativa natural para esse problema é reusar essas seções (ou traços) que são replicadas. O objetivo desse trabalho é analisar e avaliar a efetividade do reuso de valores na arquitetura DCE. Como será apresentado, o princípio do reuso, em diferentes granularidades, pode reduzir efetivamente o problema das réplicas e levar a aumentos de desempenho. / The Dynamic Conditional Execution (DCE) is an alternative to reduce the cost of mispredicted branches. The basic idea is to fetch all paths produced by a branch that obey certain restrictions regarding complexity and size. As a consequence, a smaller number of predictions is performed, and therefore, a lower number branches is mispredicted. Nevertheless, as other multipath solutions, DCE requires a more complex control engine. In a DCE architecture, one may observe that several replicas of the same instruction are dispatched to the functional units, blocking resources that might be used by other instructions. Those replicas are produced after the join point of the paths and are required to guarantee the correct semantic among data dependent instructions. Moreover, DCE continues producing replicas until the branch that generated the paths is resolved. Thus, a whole section of code may be replicated, harming performance. A natural alternative to this problem is the attempt to reuse those replicated sections, namely the replicated traces. The goal of this work is to analyze and evaluate the effectiveness of value reuse in DCE architecture. As it will be presented, the principIe of reuse, in different granularities, can reduce effectively the replica problem and lead to performance improvements.

Abstract High radio capacity is one of the main targets in wireless network planning. The characteristics of the broadband radio channel pose serious challenges for achieving this goal. This thesis views the capacity problem from two frameworks. In the first, the effective user capacity in advanced direct sequence wideband code-division multiple-access (DS-CDMA) radio networks is evaluated. Sensitivity to various imperfections in key system parameters is studied. The analysis is based on a mathematical foundation that presents complex signal models and enables evaluation of the performance losses due to parameter estimation errors and multipath fading. The effective number of users supported in a cell is restricted by the multiple access interference (MAI) in the same cell (intracell interference) and overall background noise. The studied wideband CDMA receiver structures comprise conventional rake receivers with both the maximal ratio combining (MRC) and equal gain combining (EGC) schemes that can be supplemented with either linear decorrelating or nonlinear successive cancellation-based multiuser detectors and M-antenna spatial diversity. The second framework focuses on direct sequence spread spectrum-based ultra wideband (UWB) indoor communications. Cochannel interference limited capacity is evaluated against the outage probability criterion in exponentially decaying lognormal multipath fading channels. Distance-dependence and spatial distribution of users is taken into account at different spatial cell configurations. Only moderate complexity partial rake receivers with noncoherent combining are employed. Total interference is composed of interpath, multipath, intracell, and intercell interference contributions. Lognormal sum approximations and simulations are used to evaluate distributions of the desired and interfering signals. The impact of the timing errors at the receiver monopulse correlation is studied. The numerical results for the wideband CDMA framework show that effective user capacity and sensitivity depend critically on the joint impact of nonidealities in system parameters (e.g., channel profile, severity of fading, receiver algorithms). User capacities of the studied multiuser enhanced receivers were more prone to these impairments than those of the simpler single user receivers. The results should be used for network planning and optimization. The numerical results of the UWB framework suggest that, even in the multipath rich channel, the optimal number of rake fingers can be less than half of the significant multipaths. Differences between circular, square, and hexagonal cell models proved to be minor with respect to link distance distributions. The derived link distance statistics are useful tools in the analytic piconet dimensioning and optimization.

In this thesis, an investigation of the performance of multipath routing in Wireless Sensor Networks (WSN) is performed. The communication in the network under study is to take place from individual nodes to the sink node. The investigation involved multipath finding methods in WSN. Also, it involves investigating the weight assignment, traffic splitting and route selection methods for the different paths discovered by each node in the WSN. Also, a comparison between Hybrid Routing Protocol, Source Routing Protocol and Diffusion Routing Protocol is performed. A simple traffic routing algorithm for each routing protocol has been developed to conceptualize how the network traffic is routed on a set of active paths. The investigation of the Hybrid, Source and Diffusion Routing Protocol involved using multiple paths simultaneously to transmit messages that belong to the same flow by using a weight assigned to each path and transmit each message as a whole. Finally, the power consumption and the QoS in terms of message delays for a WSN were investigated and compared between different protocols.