<p>Visualization of porous media is of great importance to several scientific fields, including the petroleum technology. The topic of this thesis arises from our collaborations with The Center for Integrated Operations in the Petroleum Industry. By being able to quickly analyze properties of porous rocks, they can get a better understanding of how to efficiently harvest oil since oil is typically held and stored within rock pores. The petroleum industry typically uses Computed Tomography (CT) technology to scan rock samples for their internal structures. The resulting data is loaded into a computer program that generates 3D models of the rocks describing the 3D nature of its' internal structure. The scan data created from these scans will in most case contain inaccuracies due to artifacts created while scanning. In this thesis, we develop an application that interactively helps the user localizes the rock and pores in the CT scan data, allowing the user to create an image with a more accurate representation of the pores. We use digital image processing techniques to do an initial localization of the elements in the scan. The artifacts are then reduced by allowing the user to drag and pull on the line-data specifying the pores. Our implementation then uses this new representation to construct a 3D volume image that can be used in geophysical applications, like Schlumberger Petrel, for further analysis and simulation. The volume rendering part of our implementations builds directly on the authors project work with Eirik Ola Aksnes on GPU Techniques for Porous Rock Visualization completed last fall (2008).</p>

<p>Sosial interaksjon er en nødvendig ting i dagens samfunn, og folk vi gjerne vite hvor vennene deres er. Denne oppgaven beskriver et system som kan motta lokasjonsinformasjon fra brukere og sender den ut til ønskede parter. Systemet er inndelt i forskjellige soner hvor hver er knyttet opp mot et fysisk område. En bruker har en hjemme-sone som har ansvar for alltid å holde den nyeste informasjonen til brukeren, sånn som hvem det er som skal ha lokasjonsoppdateringene han sender inn. Når en bruker beveger seg på tvers av soner vil den nødvendige informasjonen til brukeren blir sendt med til den nye sonen han går inn i for at den nye sonen kan være ansvarlig for å sende ut all informasjon. Men hjemmesonen har fortsatt oversikt over hvor brukeren er, og er ansvarlig i en situasjon hvor en bruker beveger seg på tvers av to soner så den nye sonen får riktig informasjon og passer på at den gamle sonen blir fortalt at brukere har forlatt den.</p>

<p>The availability of cheap computers with outstanding single-processor performance coupled with Ethernet and the development of open MPI implementations has led to a drastic increase in the number of HPC clusters. This, in turn, has led to many new HPC users. Ideally, all users are proficient programmers that always optimize their programs for the specific architecture they are running on. In practice, users only invest enough effort that their program runs correctly. While we would like to teach all HPC users how to be better programmers, we realize most users consider HPC a tool and would like to focus on their application problem. To this end, we present a new method for automatically optimizing any application's communication. By protecting the memory associated with MPI_Send, MPI_Recv and MPI_Sendrecv requests, we can let the request continue in the background as MPI_Isend or MPI_Irecv while the application is allowed to continue in the belief the request is finished. Once the data is accessed by the application, our protection will ensure we wait for the background transfer to finish before allowing the application to continue. Also presented is an alternate method with less overhead based on recognizing series of requests made between computation phases. We allow the requests in such a chain to overlap with each other, and once the end of such a chain of requests is reached, we wait for all the requests to complete. All of this is done without any user intervention at all. The method can be dynamically injected at runtime, which makes it applicable to any MPI program in binary form. We have implemented a 2D parallel red-black SOR PDE solver, which due to its alternating red and black cell transfers represents a "worst case" communication pattern for MPI programs with 2D data domain decomposition. We show that our new method will greatly improve the efficiency of this application on a cluster, yielding performance close to that of manual optimization.</p>

<p>Virtual reality based surgical simulators offer an elegant approach to enhancing traditional training in surgery. For interactive surgery simulation to be useful, however, there are several requirements needed to be fulfilled. A good visualisation is needed. The physical behavior of an organ must be modeled realistically. Finally there is a need of a device capable of force feedback to realize the possibility of ``feeling'' a virtual object. In this thesis a basic prototype was developed to demonstrate all necessary concepts needed in a surgical simulator. The study was aimed at finding a suitable architecture and design for development of a surgical simulation application which is conceptually clear and easy to comprehend. Moreover, it was considered important that the prototype can provide a good basis for further experimentation. The main focus was on finding a satisfactory method that demonstrates the main concepts, while keeping the complexity as low as possible. In the developed prototype, the visual impression of 3D is present, the haptic feedback works satisfactory, and the physical modelling proved to be feasible for simulating a virtual object. The object oriented design resulted in a compact and clear application, where changes in the implementation can be applied locally without unwanted implications elsewhere in the code. Due to these qualities, implementing multi resolution and cutting was an easy task. Only minor changes to limited parts of the application was needed. This shows its suitability as a starting point for future experimenting and demonstration of consepts, in the field of surgical simulation.</p>

<p>Today's supercomputers often consists of clusters of SMP nodes. Both OpenMP and MPI are programming paradigms that can be used for parallelization of codes for such architectures. OpenMP uses shared memory, and hence is viewed as a simpler programming paradigm than MPI that is primarily a distributed memory paradigm. However, the Open MP applications may not scale beyond one SMP node. On the other hand, if we only use MPI, we might introduce overhead in intra-node communication. In this thesis we explore the trade-offs between using OpenMP, MPI and a mix of both paradigms for the same application. In particular, we look at a physics simulation and parallalize it with both OpenMP and MPI for large-scale simulations on modern supercomputers. A parallel SOR solver with OpenMP and MPI is implemented and the effects of such hybrid code are measured. We also utilize the FFTW-library that includes both system-optimized serial implementations and a parallel OpenMP FFT implementation. These solvers are used to make our existing Particle-In-Cell codes be more scalable and compatible with current programming paradigms and supercomputer architectures. We demonstrate that the overhead from communications in OpenMP loops on an SMP node is significant and increases with the number of CPUs participating in execution of the loop compared to equivalent MPI implementations. To analyze this result, we also present a simple model on how to estimate the overhead from communication in OpenMP loops. Our results are both surprising and should be of great interest to a large class of parallel applications.</p>

<p>This thesis focuses on fault-tolerance for MPI codes on computational clusters. When an application runs on a very large cluster with thousands of processors, there is likely that a process crashes due to a hardware or software failure. Fault-tolerance is the ability of a system to respond gracefully to an unexpected hardware or software failure. A test application which is meant to run for several weeks on several nodes is used in this thesis. The application is a seismic MPI application, written in Fortran90. This application was provided by Statoil, who wanted a fault-tolerant implementation. The original test application had no degree of fault-tolerance --if one process or one node crashed, the entire application also crashed. In this thesis, a collection of fault-tolerant techniques are analysed, including checkpointing, MPI Error handlers, extending MPI, replication, fault detection, atomic clocks and multiple simultaneous failures. Several MPI implementations are described, like MPICH1, MPICH2, LAM/MPI and Open MPI. Next, some fault-tolerant products which are developed at other universities are described, like FT-MPI, FEMPI, MPICH-V including its five protocols, the fault-tolerant functionality of Open MPI, and MPI Error handlers. A fault-tolerant simulator which simulates the application's behaviour is developed. The simulator uses two fault-tolerance methods: FT-MPI and MPI Error handlers. Next, our test application is similarly made fault-tolerant with FT-MPI using three proposed approaches: MPI_Reduce(), MPI_Barrier(), and the final and current implementation: MPI Loop. Tests of the MPI Loop implementation are run on a small and a large cluster to verify the fault-tolerant behaviour. The seismic application survives a crash of n-2 nodes/processes. Process number 0 must stay alive since it acts as an I/O server, and there must be at least one process left to compute data. Processes can also be restarted rather than left out, but the test application needs to be modified to support this.</p>

<p>The single core processor stagnated due to four major factors. (1) The lack of instruction level parallelism to exploit, (2) increased power consumption, (3) complexity involved in designing a modern processor, and (4) the gap in performance between memory and the processor. As the gate size has decreased, a natural solution has been to introduce several cores on the same die, creating a chip multicore processor. However, the introduction of chip multicore processors has brought a new set of new challenges such as power consumptions and cache strategies. Although throughly researched in context of super computers, the chip multiprocessor has decreased in physical size, and thus some of the old paradigms should be reevaluated, and new ones found. To be able to research, simulate and experiment on new multicore architectures, simulators and methods of prototyping are needed by the community, and has traditionally been done by software simulators. To help decrease the time between results, and increase the productivity a hardware based method of prototyping is needed. This thesis contributes by presenting a novel multicore architecture with interchangeable and easily customizable units allowing the developers to extend the architecture, rewriting only the subsystem in question. The architecture is implemented in VHDL and has been tested on a Virtex FPGA, utilizing the MicroBlaze microcontroller. Based upon FPGA technologies, the platform has a more accurate nature than a software based simulator. The thesis also shows that a hardware based environment will significantly decrease the time to results.</p>

<p>Seismological applications use a 3D grid to represent the subsea rock structure. Many computations, such as detecting layers of rock in the seismic, can be done using the 3D grid exclusively. However, some algorithms for detecting vertical dislocations in the seismic require computations over a discretized polygon surface imposed over the 3D grid to assist geophysicists in interpreting the seismic data. When using seismological applications on clusters, the 3D grid data is distributed between several cluster nodes. This thesis considers how algorithms involving discretized polygon surfaces can efficiently utilize the parallelism provided by clusters, and provides a general framework such algorithms can utilize. The framework consists of three main parts: 1) efficient caching and transfer of voxels between cluster nodes, 2) efficient discretization or voxelization of polygon surfaces, and 3) efficient load-balancing. First, three algorithms for caching and transferring voxels between nodes are introduced. The strategy which only transfers necessary polygon voxels is shown to be superior in most cases for our workloads, obtaining a speedup of 24.28 over a strategy which caches the bounding volume of the polygon, and a speedup of 2.66 over a strategy which transfers small blocks surrounding each polygon voxel. Second, a new voxelization algorithm which may be suitable for Graphics Processing Units (GPUs) and multi-core CPU implementations is presented. On the GPU, a speedup of 2.14 is obtained over the corresponding algorithm on the CPU. For multi-core architectures without shared memory buses, a speedup of 2.21 is obtained when using 8 cores. Finally, three algorithms for load-balancing the computations are introduced and future work is discussed. Our load-balancing algorithms achieve a speedup of 5.77 compared to not using any load-balancing for our workloads.</p>

<p>This is a Master’s thesis in how to make a tetrahedral mesh for use in a needle insertion simulator. It also describes how it is possible to make the simulator, and how to improve it to make it as realistic as possible. The medical simulator uses a haptic device, a haptic scene graph and a FEM for realistic soft tissue deformation and interaction. In this project a tetrahedral mesh is created from a polygon model, and then the mesh has been loaded into the HaptX haptic scene graph. The objects in the mesh have been made as different haptic objects, and then they have got a simple haptic surface to make it possible to touch them. There has not been implemented any code for the Hybrid Condensed FEM that has been described.</p>

<p>This thesis develops and tests 3D Fast Marching Method (FMM) algorithm and apply these to seismic simulations. The FMM is a general method for monotonically advancing fronts, originally developed by Sethian. It calculates the first arrival time for an advancing front or wave. FMM methods are used for a variety of applications including, fatigue cracks in materials, lymph node segmentation in CT images, computing skeletons and centerlines in 3D objects and for finding salt formations in seismic data. Finding salt formations in seismic data, is important for the oil industry. Oil often flows towards gaps in the soil below a salt formation. It is therefore, important to map the edges of the salt formation, for this the FMM can be used. This FMM creates a first arrival time map, which makes it easier to see the edges of the salt formation. Herrmann developed a 3D parallel algorithm of the FMM testing waves of constant velocity. We implemented and tested his algorithm, but since seismic data typically causes a large variation of the velocities, optimizations were needed to make this algorithm scale. By optimising the border exchange and eliminating much of the roll backs, we delevoped and implemented a much improved 3D FMM which achieved close to theoretical performance, for up to at least 256 nodes on the current supercomputer at NTNU. Other methods like, different domain decompositions for better load balancing and running more FMM picks simultaneous, will also be discussed.</p>