Adaptive Routing Approaches for Networked Many-Core Systems

Through advances in technology, System-on-Chip design is moving towards integrating tens to hundreds of intellectual property blocks into a single chip. In such a many-core system, on-chip communication becomes a performance bottleneck for high performance designs. Network-on-Chip (NoC) has emerged as a viable solution for the communication challenges in highly complex chips. The NoC architecture paradigm, based on a modular packet-switched mechanism, can address many of the on-chip communication challenges such as wiring complexity, communication latency, and bandwidth. Furthermore, the combined benefits of 3D IC and NoC schemes provide the possibility of designing a high performance system in a limited chip area. The major advantages of 3D NoCs are the considerable reductions in average latency and power consumption. There are several factors degrading the performance of NoCs. In this thesis, we investigate three main performance-limiting factors: network congestion, faults, and the lack of efficient multicast support. We address these issues by the means of routing algorithms. Congestion of data packets may lead to increased network latency and power consumption. Thus, we propose three different approaches for alleviating such congestion in the network. The first approach is based on measuring the congestion information in different regions of the network, distributing the information over the network, and utilizing this information when making a routing decision. The second approach employs a learning method to dynamically find the less congested routes according to the underlying traffic. The third approach is based on a fuzzy-logic technique to perform better routing decisions when traffic information of different routes is available. Faults affect performance significantly, as then packets should take longer paths in order to be routed around the faults, which in turn increases congestion around the faulty regions. We propose four methods to tolerate faults at the link and switch level by using only the shortest paths as long as such path exists. The unique characteristic among these methods is the toleration of faults while also maintaining the performance of NoCs. To the best of our knowledge, these algorithms are the first approaches to bypassing faults prior to reaching them while avoiding unnecessary misrouting of packets. Current implementations of multicast communication result in a significant performance loss for unicast traffic. This is due to the fact that the routing rules of multicast packets limit the adaptivity of unicast packets. We present an approach in which both unicast and multicast packets can be efficiently routed within the network. While suggesting a more efficient multicast support, the proposed approach does not affect the performance of unicast routing at all. In addition, in order to reduce the overall path length of multicast packets, we present several partitioning methods along with their analytical models for latency measurement. This approach is discussed in the context of 3D mesh networks.

Adaptive Markov chain Monte Carlo and Bayesian filtering for state space models

This thesis is concerned with the state and parameter estimation in state space models. The estimation of states and parameters is an important task when mathematical modeling is applied to many different application areas such as the global positioning systems, target tracking, navigation, brain imaging, spread of infectious diseases, biological processes, telecommunications, audio signal processing, stochastic optimal control, machine learning, and physical systems. In Bayesian settings, the estimation of states or parameters amounts to computation of the posterior probability density function. Except for a very restricted number of models, it is impossible to compute this density function in a closed form. Hence, we need approximation methods. A state estimation problem involves estimating the states (latent variables) that are not directly observed in the output of the system. In this thesis, we use the Kalman filter, extended Kalman filter, Gauss–Hermite filters, and particle filters to estimate the states based on available measurements. Among these filters, particle filters are numerical methods for approximating the filtering distributions of non-linear non-Gaussian state space models via Monte Carlo. The performance of a particle filter heavily depends on the chosen importance distribution. For instance, inappropriate choice of the importance distribution can lead to the failure of convergence of the particle filter algorithm. In this thesis, we analyze the theoretical Lᵖ particle filter convergence with general importance distributions, where p ≥2 is an integer. A parameter estimation problem is considered with inferring the model parameters from measurements. For high-dimensional complex models, estimation of parameters can be done by Markov chain Monte Carlo (MCMC) methods. In its operation, the MCMC method requires the unnormalized posterior distribution of the parameters and a proposal distribution. In this thesis, we show how the posterior density function of the parameters of a state space model can be computed by filtering based methods, where the states are integrated out. This type of computation is then applied to estimate parameters of stochastic differential equations. Furthermore, we compute the partial derivatives of the log-posterior density function and use the hybrid Monte Carlo and scaled conjugate gradient methods to infer the parameters of stochastic differential equations. The computational efficiency of MCMC methods is highly depend on the chosen proposal distribution. A commonly used proposal distribution is Gaussian. In this kind of proposal, the covariance matrix must be well tuned. To tune it, adaptive MCMC methods can be used. In this thesis, we propose a new way of updating the covariance matrix using the variational Bayesian adaptive Kalman filter algorithm.

Clinical Learning Environment and Supervision. Development and Validation of the CLES Evaluation Scale

The purpose of the study is: (1) to describe how nursing students' experienced their clinical learning environment and the supervision given by staff nurses working in hospital settings; and (2) to develop and test an evaluation scale of Clinical Learning Environment and Supervision (CLES). The study has been carried out in different phases. The pilot study (n=163) explored the association between the characteristics of a ward and its evaluation as a learning environment by students. The second version of research instrument (which was developed by the results of this pilot study) were tested by an expert panel (n=9 nurse teachers) and test-retest group formed by student nurses (n=38). After this evaluative phase, the CLES was formed as the basic research instrument for this study and it was tested with the Finnish main sample (n=416). In this phase, a concurrent validity instrument (Dunn & Burnett 1995) was used to confirm the validation process of CLES. The international comparative study was made by comparing the Finnish main sample with a British sample (n=142). The international comparative study was necessary for two reasons. In the instrument developing process, there is a need to test the new instrument in some other nursing culture. Other reason for comparative international study is the reflecting the impact of open employment markets in the European Union (EU) on the need to evaluate and to integrate EU health care educational systems. The results showed that the individualised supervision system is the most used supervision model and the supervisory relationship with personal mentor is the most meaningful single element of supervision evaluated by nursing students. The ward atmosphere and the management style of ward manager are the most important environmental factors of the clinical ward. The study integrates two theoretical elements - learning environment and supervision - in developing a preliminary theoretical model. The comparative international study showed that, Finnish students were more satisfied and evaluated their clinical placements and supervision with higher scores than students in the United Kingdom (UK). The difference between groups was statistical highly significant (p= 0.000). In the UK, clinical placements were longer but students met their nurse teachers less frequently than students in Finland. Arrangements for supervision were similar. This research process has produced the evaluation scale (CLES), which can be used in research and quality assessments of clinical learning environment and supervision in Finland and in the UK. CLES consists of 27 items and it is sub-divided into five sub-dimensions. Cronbach's alpha coefficient varied from high 0.94 to marginal 0.73. CLES is a compact evaluation scale and user-friendliness makes it suitable for continuing evaluation.