No description available.

This thesis presents several algorithms that update the vertex separation of a tree after the tree is modified; the vertex separation of a graph measures the largest number of vertices to the left of and including a vertex that are adjacent to vertices to the right of the vertex, when the vertices in the graph are arranged in the best possible linear ordering. Vertex separation was introduced by Lipton and Tarjan and has since been applied mainly in VLSI design. The tree is modified by either attaching another tree or removing a subtree. The first algorithm handles the special case when another tree is attached to the root, and the second algorithm updates the vertex separation after a subtree of the root is removed. The last two algorithms solve the more general problem when subtrees are attached to or removed from arbitrary vertices; they have good running time performance only in the amortized sense. The running time of all our algorithms is sublinear in the number of vertices in the tree, assuming certain information is precomputed for the tree. This improves upon current algorithms by Skodinis and Ellis, Sudborough, and Turner, both of which have linear running time for this problem. Lower and upper bounds on the vertex separation of a general graph are also derived. Furthermore, analogous bounds are presented for the cutwidth of a general graph, where the cutwidth of a graph equals the maximum number of edges that cross over a vertex, when the vertices in the graph are arranged in the best possible linear ordering.

Le but de ce travail est d'utiliser les simulations du type vertex afin d'étudier l'effet de l'orientation cristallographique sur la cinétique de la restauration dans l'alliage binaire Al-0,1%Mn. La caractérisation de la cinétique de la restauration dans un polycristal déformé par laminage à froid a été faite à l'aide des mesures de microdureté sur les échantillons recuits à quatre températures pendant différentes durées. Le modèle de restauration développé par Vandermeer et al a été appliqué pour estimer l'énergie d'activation pour la restauration. Plusieurs problèmes ont été rencontrés pendant l'application du modèle, dus à la complexité de ses équations, et également l'amplification de l'incertitude des mesures expérimentales par les termes exponentiels qui figurent dans le modèle. Le simulations vertex de la croissance des sous-grains ont été faites avec les propriétés du matériau trouvées dans la littérature. Les microstructures de déformation des monocristaux orientés Brass et Goss ont été reproduites dans les simulations. Les résultats des simulations étaient en bon accord avec les résultats expérimentaux d'Albou et al. Le faible taux de la croissance des sous-grains dans la microstructure Brass a été à cause de la présence des sous-joints de faible désorientation. La microstructure Goss contient des bandes avec les sous-joints de fortes désorientations, et en conséquent, fortes mobilités, qui entrainent la croissance des sous-grains dans cette structure. Ainsi, il a été établi que l'effet de l'orientation cristallographique est présent dans la microstructure de déformation, les sous-joints ainsi créés et la distribution de désorientations.

Modern graphics accelerators have embedded programmable components in the form of vertex and fragment shading units. Current APIs permit specification of the programs for these components using an assembly-language level interface. Compilers for high-level shading languages are available but these read in an external string specification, which can be inconvenient. It is possible, using standard C++, to define an embedded high-level shading language. Such a language can be nearly indistinguishable from a special-purpose shading language, yet permits more direct interaction with the specification of textures and parameters, simplifies implementation, and enables on-the-fly generation, manipulation, and specification of shader programs. An embedded shading language also permits the lifting of C++ host language type, modularity, and scoping constructs into the shading language without any additional implementation effort.

This thesis presents several algorithms that update the vertex separation of a tree after the tree is modified; the vertex separation of a graph measures the largest number of vertices to the left of and including a vertex that are adjacent to vertices to the right of the vertex, when the vertices in the graph are arranged in the best possible linear ordering. Vertex separation was introduced by Lipton and Tarjan and has since been applied mainly in VLSI design. The tree is modified by either attaching another tree or removing a subtree. The first algorithm handles the special case when another tree is attached to the root, and the second algorithm updates the vertex separation after a subtree of the root is removed. The last two algorithms solve the more general problem when subtrees are attached to or removed from arbitrary vertices; they have good running time performance only in the amortized sense. The running time of all our algorithms is sublinear in the number of vertices in the tree, assuming certain information is precomputed for the tree. This improves upon current algorithms by Skodinis and Ellis, Sudborough, and Turner, both of which have linear running time for this problem. Lower and upper bounds on the vertex separation of a general graph are also derived. Furthermore, analogous bounds are presented for the cutwidth of a general graph, where the cutwidth of a graph equals the maximum number of edges that cross over a vertex, when the vertices in the graph are arranged in the best possible linear ordering.

Asynchronous bus interface units to AMBA AHB are designed so that an OpenGL ES 2.0 vertex shader can communicate with other hardware units via AHB bus under different working frequencies. The first design is to directly implement an asynchronous AHB wrapper for the vertex shader. The other two designs are based on Open Core Protocol (OCP) to allow for more flexibility. The hardware intellectual property (IP), vertex shader in this thesis, to OCP asynchronous unit is designed so that the IP can be developed independently with different bus protocols as long as the OCP-to-bus interface is provided for a particular bus protocol. With the help of asynchronous IP-to-OCP and OCP-to-AHB interface units, the vertex shader IP can operate at different frequencies from the AHB bus. Furthermore, the same vertex shader (VS) can be connected to other bus protocol (such as AXI) of different frequencies if the OCP-to-AXI interface is provided because the the asynchronous VS-to-OCP have been designed in this thesis.

Graphics processing unit (GPU) designs usually adopts various computer architecture techniques to boost the computation speed, including single-instruction multiple data (SIMD), very-long-instruction word (VLIW), multi-threading, and/or multi-core. In OpenGL ES 2.0, user programmable vertex shader (VS) hardware unit can be designed using vectored SIMD computation unit so that it can efficiently compute the matrix-vector multiplication, one of the key operations in vertex transformation. Recently, high-performance GPU, such as Telsa series from nVidia, is designed with many-core architectures with each core responsible for scalar operations. The intention is to allow for efficient execution of general-purpose computations in addition to the specialized graphics computations. In this thesis, we design a scalar-based multi-threaded GPU design that is composed of four scalar processors, one special-function unit, and can execute multi-threaded instructions. We use the example of vertex transformation to demonstrate execution efficiency of the scalar-based multi-threaded GPU. We also make comparison with the vector-based SIMD GPU.

Parameterized NP-hard problems are NP-hard problems that are associated with special variables called parameters. One example of the problem is to find simple paths of length k in a graph, where the integer k is the parameter. We call this problem the p-path problem. The p-path problem is the parameterized version of the well-known NP-complete problem - the longest simple path problem. There are two main reasons why we study parameterized NP-hard problems. First, many application problems are naturally associated with certain parameters. Hence we need to solve these parameterized NP-hard problems. Second, if parameters take only small values, we can take advantage of these parameters to design very effective algorithms. If a parameterized NP-hard problem can be solved by an algorithm of running time in form of f(k)nO(1), where k is the parameter, f(k) is independent of n, and n is the input size of the problem instance, we say that this parameterized NP-hard problem is fixed parameter tractable (FPT). If a problem is FPT and the parameter takes only small values, the problem can be solved efficiently (it can be solved almost in polynomial time). In this dissertation, first, we introduce several techniques that can be used to design efficient algorithms for parameterized NP-hard problems. These techniques include branch and bound, divide and conquer, color coding and dynamic programming, iterative compression, iterative expansion and kernelization. Then we present our results about how to use these techniques to solve parameterized NP-hard problems, such as the p-path problem and the pd-feedback vertex set problem. Especially, we designed the first algorithm of running time in form of f(k)nO(1) for the pd-feedback vertex set problem. Thus solved an outstanding open problem, i.e. if the pd-feedback vertex set problem is FPT. Finally, we will introduce how to use parameterized algorithm techniques to solve the signaling pathway problem and the motif finding problem from bioinformatics.

We propose a novel branch-and-price (B&P) approach to solve the maximum weighted independent set problem (MWISP). Our approach uses clones of vertices to create edge-disjoint partitions from vertex-disjoint partitions. We solve the MWISP on sub-problems based on these edge-disjoint partitions using a B&P framework, which coordinates sub-problem solutions by involving an equivalence relationship between a vertex and each of its clones. We present test results for standard instances and randomly generated graphs for comparison. We show analytically and computationally that our approach gives tight bounds and it solves both dense and sparse graphs quite quickly.

<p>The company where this thesis was formulated constructs VR applications for the medical environment. The hardware used is ordinary dektops with consumer level graphics cards and haptic devices. In medicin some operations require microscopes or cameras. In order to simulate these in a virtual reality environment for educational purposes, the effect of depth of field or focus have to be considered. </p><p>A working algorithm that generates this optical occurence in realtime, stereo rendered computer graphics is presented in this thesis. The algorithm is implemented in OpenGL and C++ to later be combined with a VR application simulating eye-surgery which is built with OpenGL Optimizer. </p><p>Several different approaches are described in this report. The call for realtime stereo rendering (~60 fps) means taking advantage of the graphics hardware to a great extent. In OpenGL this means using the extensions to a specific graphic chip for better performance, in this case the algorithm is implemented for a GeForce3 card. </p><p>To increase the speed of the algorithm much of the workload is moved from the CPU to the GPU (Graphics Processing Unit). By re-defining parts of the ordinary OpenGL pipeline via vertex programs, a distance-from-focus map can be stored in the alpha channel of the final image with little time loss. </p><p>This can effectively be used to blend a previously blurred version of the scene with a normal render. Different techniques to quickly blur a renderedimage is discussed, to keep the speed up solutions that require moving data from the graphics card is not an option.</p>