In this thesis, we investigate physical-layer network coding in an L × M × K relay network, where L source nodes want to transmit messages to K sink nodes via M relay nodes. We focus on the information processing at the relay nodes and the compute-and-forward framework. Nested lattice codes are used, which have the property that every linear combination of codewords is a valid codeword. This property is essential for physical-layer network coding. Because the actual network coding occurs on the physical layer, the network coding coefficients are determined by the channel realizations. Finding the optimal network coding coefficients for given channel realizations is a non-trivial optimization problem. In this thesis, we provide an algorithm to find network coding coefficients that result in the highest data rate at a chosen relay. The solution of this optimization problem is only locally optimal, i.e., it is optimal for a particular relay. If we consider a multi-hop network, each potential receiver must get enough linear independent combinations to be able to decode the individual messages. If this is not the case, outage occurs, which results in data loss. In this thesis, we propose a new strategy for choosing the network coding coefficients locally at the relays without solving the optimization problem globally. We thereby reduce the solution space for the relays such that linear independence between their decoded linear combinations is guaranteed. Further, we discuss the influence of spatial correlation on the optimization problem. Having solved the optimization problem, we combine physical-layer network coding with physical-layer secrecy. This allows us to propose a coding scheme to exploit untrusted relays in multi-user relay networks. We show that physical-layer network coding, especially compute-and-forward, is a key technology for simultaneous and secure communication of several users over an untrusted relay. First, we derive the achievable secrecy rate for the two-way relay channel. Then, we enhance this scenario to a multi-way relay channel with multiple antennas. We describe our implementation of the compute-and-forward framework with software-defined radio and demonstrate the practical feasibility. We show that it is possible to use the framework in real-life scenarios and demonstrate a transmission from two users to a relay. We gain valuable insights into a real transmission using the compute-and-forward framework. We discuss possible improvements of the current implementation and point out further work. / In dieser Arbeit untersuchen wir Netzwerkcodierung auf der Übertragungsschicht in einem Relay-Netzwerk, in dem L Quellen-Knoten Nachrichten zu K Senken-Knoten über M Relay-Knoten senden wollen. Der Fokus dieser Arbeit liegt auf der Informationsverarbeitung an den Relay-Knoten und dem Compute-and-Forward Framework. Es werden Nested Lattice Codes eingesetzt, welche die Eigenschaft besitzen, dass jede Linearkombination zweier Codewörter wieder ein gültiges Codewort ergibt. Dies ist eine Eigenschaft, die für die Netzwerkcodierung von entscheidender Bedeutung ist. Da die eigentliche Netzwerkcodierung auf der Übertragungsschicht stattfindet, werden die Netzwerkcodierungskoeffizienten von den Kanalrealisierungen bestimmt. Das Finden der optimalen Koeffizienten für gegebene Kanalrealisierungen ist ein nicht-triviales Optimierungsproblem. Wir schlagen in dieser Arbeit einen Algorithmus vor, welcher Netzwerkcodierungskoeffizienten findet, die in der höchsten Übertragungsrate an einem gewählten Relay resultieren. Die Lösung dieses Optimierungsproblems ist zunächst nur lokal, d. h. für dieses Relay, optimal. An jedem potentiellen Empfänger müssen ausreichend unabhängige Linearkombinationen vorhanden sein, um die einzelnen Nachrichten decodieren zu können. Ist dies nicht der Fall, kommt es zu Datenverlusten. Um dieses Problem zu umgehen, ohne dabei das Optimierungsproblem global lösen zu müssen, schlagen wir eine neue Strategie vor, welche den Lösungsraum an einem Relay soweit einschränkt, dass lineare Unabhängigkeit zwischen den decodierten Linearkombinationen an den Relays garantiert ist. Außerdem diskutieren wir den Einfluss von räumlicher Korrelation auf das Optimierungsproblem. Wir kombinieren die Netzwerkcodierung mit dem Konzept von Sicherheit auf der Übertragungsschicht, um ein Übertragungsschema zu entwickeln, welches es ermöglicht, mit Hilfe nicht-vertrauenswürdiger Relays zu kommunizieren. Wir zeigen, dass Compute-and-Forward ein wesentlicher Baustein ist, um solch eine sichere und simultane Übertragung mehrerer Nutzer zu gewährleisten. Wir starten mit dem einfachen Fall eines Relay-Kanals mit zwei Nutzern und erweitern dieses Szenario auf einen Relay-Kanal mit mehreren Nutzern und mehreren Antennen. Die Arbeit wird abgerundet, indem wir eine Implementierung des Compute-and-Forward Frameworks mit Software-Defined Radio demonstrieren. Wir zeigen am Beispiel von zwei Nutzern und einem Relay, dass sich das Framework eignet, um in realen Szenarien eingesetzt zu werden. Wir diskutieren mögliche Verbesserungen und zeigen Richtungen für weitere Forschungsarbeit auf.

A wireless relay network consists of multiple source nodes, multiple destination nodes, and possibly many relay nodes in between to facilitate its transmission. It is clear that the performance of such networks highly depends on information for- warding strategies adopted at the relay nodes. This dissertation studies a particular information forwarding strategy called compute-and-forward. Compute-and-forward is a novel paradigm that tries to incorporate the idea of network coding within the physical layer and hence is often referred to as physical layer network coding. The main idea is to exploit the superposition nature of the wireless medium to directly compute or decode functions of transmitted signals at intermediate relays in a net- work. Thus, the coding performed at the physical layer serves the purpose of error correction as well as permits recovery of functions of transmitted signals. For the bidirectional relaying problem with Gaussian channels, it has been shown by Wilson et al. and Nam et al. that the compute-and-forward paradigm is asymptotically optimal and achieves the capacity region to within 1 bit; however, similar results beyond the memoryless case are still lacking. This is mainly because channels with memory would destroy the lattice structure that is most crucial for the compute-and-forward paradigm. Hence, how to extend compute-and-forward to such channels has been a challenging issue. This motivates this study of the extension of compute-and-forward to channels with memory, such as inter-symbol interference. The bidirectional relaying problem with parallel Gaussian channels is also studied, which is a relevant model for the Gaussian bidirectional channel with inter-symbol interference and that with multiple-input multiple-output channels. Motivated by the recent success of linear finite-field deterministic model, we first investigate the corresponding deterministic parallel bidirectional relay channel and fully characterize its capacity region. Two compute-and-forward schemes are then proposed for the Gaussian model and the capacity region is approximately characterized to within a constant gap. The design of coding schemes for the compute-and-forward paradigm with low decoding complexity is then considered. Based on the separation-based framework proposed previously by Tunali et al., this study proposes a family of constellations that are suitable for the compute-and-forward paradigm. Moreover, by using Chinese remainder theorem, it is shown that the proposed constellations are isomorphic to product fields and therefore can be put into a multilevel coding framework. This study then proposes multilevel coding for the proposed constellations and uses multistage decoding to further reduce decoding complexity.

Visualization of volumetric data has always been useful in big va- riety of ways, for example computer tomography (CT) and magnet resonance tomography (MRT) are two major applications of this sorts of algorithms. Since volumetric data has no limitation regarding the shape of the object that ordinary mesh algorithms has we can fully reconstruct anything using the Marching cubes algorithm. New tech- niques allow us to implement this algorithm by new and exible means. Here we will use the latest of DirectX technology to run marching cubes in realtime using compute shaders. / kristoffer.swe@gmail.com

The game industry have always looked for rendering techniques that makes the games as good looking and realistic as possible. The common approach is to use triangles built up by vertices and apply many different techniques to make it look as good as possible. When triangles are used to draw objects, there is always edges and those edges often make the objects look less realistic than desired. To reduce these visible edges the amount of triangles for an object have to be increased, but with more triangles more processing power from the graphics cards is needed. Another way to approach rendering is ray tracing which can render an extremely photo realistic image but to the cost of unbearable low performance if you would use it in a realtime application. The reason raytracing is so slow is the massive amount of calculations that needs to be made. In DirectX 11 a few new shaders where announced and one of them were the compute shader, the compute shader allows you to calculate data on the graphics card which is not bound to the pipeline. The compute shader allows you to use the hundreds of cores that the graphic card has and is therefore well suited for a raytracing algorithm. One application is used to see if the hypothesis is correct. A flag is used to define if the application runs on the CPU and the GPU. The same algorithm is used in both versions. Three test where done on each processing unit to confirm the hypothesis. Three more tests where done on the GPU to see how the performance scaled on the GPU depending on the number of rendered objects. The tests proved throughout that the compute shader performs considerably better than the CPU when running our ray tracing algorithm.

Modelling and rendering natural phenomena, such as rain, is an important aspect of creating a realistic driving simulator. Rain is a crucial issue when driving in the real world as it for instance obstructs the driver’s vision. The difficulty is to implement it in a visually appealing way while simultaneously making it look realistic and keeping the computational cost low. In this report, a GPGPU (general-purpose computing on graphical processing units) based approach is presented where the final product is a rain simulation rendered onto a 2D texture, which can then be applied to a surface. The simulated raindrops interact with gravity, wind, a windshield wiper as well as with each other, and are then used to distort the background behind them in a convincing manner. The simulation takes into account multiple physical properties of raindrops and is shown to be suitable to run in real-time. The result is presented in form of a visual demonstration. In conclusion, even though the final simulation is still in its first iteration, it clearly highlights what can be accomplished by utilizing the GPU and the benefits of using a texture-based approach. The appropriate simulation approach will however always depend on the characteristics of the problem and the limitations of the hardware.

<p>This thesis project addresses the need for an interactive, real-time water animation tech-<br> nique that can showcase visually convincing effects such as splashes and breaking waves while<br> being computationally inexpensive. Our method couples SPH and wave equations in a one-<br> way manner to simulate the behavior of water in real-time, leveraging OpenGL’s Compute<br> Shaders for interactive performance and a novel Uniform Grid implementation. Through a<br> review of related literature on real-time simulation methods of fluids, and water animation,<br> this thesis presents a feasible algorithm, animations to showcase interesting water effects,<br> and a comparison of computational costs between SPH, wave equations, and the coupled<br> approach. The program renders a water body with a planar surface and discrete particles.<br> This project aims to provide a solution that can meet the needs of various water animation<br> use-cases, such as games, and movies, by offering a computationally efficient technique that<br> can animate water to behave plausibly and showcase essential effects in real-time.</p>

Recent hardware developments are providing a plethora of alternatives to well-known general-purpose processing units. This development reaches into all major directions, i.e., into high-speed and low latency communications systems, novel memory components as well as a zoo of different processing units in addition to the traditional CPU-style processors. While all developments have great impact on the design of database systems, we will try—in the context of this Kurz Erklärt—to categorize recent advances in the context of processing units and comment on the impact on database systems.

Snö påverkas av en stor mängd aspekter i verkligheten, och verklighetstrogen simulering av snö är resurskrävande. För att förbättra resursåtgången i applikationer simuleras snö på olika sätt beroende på det önskade resultatet. I denna studie undersöks bildfrekvensen i en heuristisk baserad implementation, med målet att ta reda på hur mycket bildfrekvensen påverkas av vilka aspekter som simuleras. Undersökningen utfördes med hjälp av en tredimensionell bergsmiljö, riktad mot användning i realtid. Aspekter som påverkar snösimulering delas in i tre delar, Snösmältning, Nederbörd, samt Förflyttning av snö. Flera utvärderingar utfördes på olika varianter av artefakten, där bildfrekvensen mättes. Utvärderingarna visade ingen märkbar skillnad i bildfrekvens beroende på vilka aspekter som simuleras. Tydliga förändringar uppstod om texturupplösning och polygonantal modifierades istället.

By projecting observed microseismic data backward in time to when fracturing occurred, it is possible to locate the fracture events in space, assuming a correct velocity model. In order to achieve this task in near real-time, a robust computational system to handle backward propagation, or Reverse Time Migration (RTM), is required. We can then test many different velocity models for each run of the RTM. We investigate the use of a Graphics Processing Unit (GPU) based system using Compute Unified Device Architecture for C (CUDA-C) as the programming language. Our preliminary results show a large improvement in run-time over conventional programming methods based on conventional Central Processing Unit (CPU) computing with Fortran. Considerable room for improvement still remains. / text

Nous étudions un protocole de coopération dans les réseaux MIMO à deux sauts : le rotate-and-forward (RF). Dans ces réseaux, la source et la destination ne communiquent qu'à travers une couche de relais. Nous étudions la performance du protocole RF à partir d'une nouvelle métrique appelée gain de coupure. Ce gain nous permet de décrire le comportement de la probabilité de coupure à des valeurs du rapport signal à bruit moyennes et élevées. En utilisant le gain de coupure, nous comparons la performance du RF aux performances d'autres protocoles ayant le même ordre de diversité que le RF. Nous supposons aussi qu'une voie de retour existe entre la destination et les relais et nous donnons un algorithme qui permet d'améliorer les performances du RF en termes de probabilité de coupure en se basant sur la connaissance des gains du canal. Nous considérons un protocole de codage de réseaux au niveau physique : le compute-and-forward (CF). Nous nous intéressons à la maximisation du débit de calcul et nous montrons que c'est équivalent à la recherche du vecteur le plus court dans un réseau de points donné. Tout d'abord, nous implémentons le protocole utilisant des réseaux de points uni-dimensionnels et des gains de canal réels. Nous nous basons sur la fonction de maximum de vraisemblance (ML) pour proposer une technique de décodage quasi-ML et nous montrons que le décodage s'effectue par une approximation Diophantienne inhomogène. Ensuite, nous généralisons certains de ces résultats au cas des réseaux de points multi-dimensionnels et des gains de canal complexes, et nous proposons un critère de construction des codes en réseaux de points qu'on appelle le facteur de platitude.