No description available.

No description available.

Giessen, Universiẗat, Diss., 2001.

Typescript (photocopy). / Digitized by Kansas Correctional Industries

<p>In this thesis, we design frameworks for efficient and accurate floating point computation. The principle underlying our frameworks is making information usually discarded in the hardware, specifically, in the floating point unit, visible to the programmer. The programmer, or automated tools that we developed, can use this information to make accuracy/performance improvements or tradeoffs. </p><p>We make the error of floating point additions architecturally visible to programmers and experimentally demonstrate that programmers can use this error to improve the accuracy of their applications or improve the application's performance without affecting the accuracy of the final result. To free programmers from having to manually instrument their code, we develop a compiler pass to automate this process.</p><p>We also design a framework to profile applications to measure undesirable numerical behavior at the floating point operation level. We develop a debugger that programmers can use to find variables with "bad" behavior. In addition, we present a profile driven mixed precision analysis framework that heuristically determines the precision of all variables in an application based on their numerical behavior. We experimentally evaluate the mixed precision analysis to show that it can generate a range of results with different accuracies and precisions.</p> / Dissertation

<p> The Boolean Satisfiability Problem (SAT) is a canonical decision problem originally shown to be NP-complete in Cook's seminal work on the theory of computational complexity. The SAT problem is one of several computational tasks identified by researchers as core problems in computer science. The existence of an efficient decision procedure for SAT would imply P = NP. However, numerous algorithms and techniques for solving the SAT problem have been proposed in various forms in practical settings. Highly efficient solvers are now actively being used, either directly or as a core engine of a larger system, to solve real-world problems that arise from many application domains. These state-of-the-art solvers use the Davis-Putnam-Logemann-Loveland (DPLL) algorithm extended with Conflict-Driven Clause Learning (CDCL). Due to the practical importance of SAT, building a fast SAT solver can have a huge impact on current and prospective applications. The ultimate contribution of this thesis is improving the state of the art of CDCL by understanding and exploiting the empirical characteristics of how CDCL works on real-world problems. The first part of the thesis shows empirically that most of the unsatisfiable real-world problems solvable by CDCL have a refutation proof with near-constant width for the great portion of the proof. Based on this observation, the thesis provides an unconventional perspective that CDCL solvers can solve real-world problems very efficiently and often more efficiently just by maintaining a small set of certain classes of learned clauses. The next part of the thesis focuses on understanding the inherently different natures of satisfiable and unsatisfiable problems and their implications on the empirical workings of CDCL. We examine the varying degree of roles and effects of crucial elements of CDCL based on the satisfiability status of a problem. Ultimately, we propose effective techniques to exploit the new insights about the different natures of proving satisfiability and unsatisfiability to improve the state of the art of CDCL. In the last part of the thesis, we present a reference solver that incorporates all the techniques described in the thesis. The design of the presented solver emphasizes minimality in implementation while guaranteeing state-of-the-art performance. Several versions of the reference solver have demonstrated top-notch performance, earning several medals in the annual SAT competitive events. The minimal spirit of the reference solver shows that a simple CDCL framework alone can still be made competitive with state-of-the-art solvers that implement sophisticated techniques outside the CDCL framework.</p>

<p> This thesis presents a new security policy enforcer designed for securing parallel computation on CUDA GPUs. We show how the very features that make a GPGPU desirable have already been utilized in existing exploits, fortifying the need for security protections on a GPGPU. An aspect weaver was designed for CUDA with the goal of utilizing aspect-oriented programming for security policy enforcement. Empirical testing verified the ability of our aspect weaver to enforce various policies. Furthermore, a performance analysis was performed to demonstrate that using this policy enforcer provides no significant performance impact over manual insertion of policy code. Finally, future research goals are presented through a plan of work. We hope that this thesis will provide for long term research goals to guide the field of GPU security.</p>

published_or_final_version / abstract / Computer Science / Master / Master of Philosophy

published_or_final_version / Computer Science and Information Systems / Master / Master of Philosophy

In this thesis, we make several significant achievements towards defining a medial axis based shape descriptor which is compact, yet discriminative. First, we propose a novel medial axis spectral shape descriptor called the medial axis spectrum for a 2D shape, which applies spectral analysis directly to the medial axis of a 2D shape. We extend the Laplace-Beltrami operator onto the medial axis of a 2D shape, and take the solution to an extended Laplacian eigenvalue problem defined on this axis as the medial axis spectrum. The medial axis spectrum of a 2D shape is certainly more efficient to compute than spectral analysis of a 2D region, since the efficiency of solving the Laplace eigenvalue problem strongly depends on the domain dimension. We show that the medial axis spectrum is invariant under uniform scaling and isometry of the medial axis. It could also overcome the medial axis noise problem automatically, due to the incorporation of the hyperbolic distance metric. We also demonstrate that the medial axis spectrum inherits several advantages in terms of discriminating power over existing methods. Second, we further generalize the medial axis spectrum to the description of medial axes of 3D shapes, which we call the medial axis spectrum for a 3D shape. We develop a newly defined Minkowski-Euclidean area ratio inspired by the Minkowski inner product to characterize the geometry of the medial axis surface of a 3D mesh. We then generalize the Laplace-Beltrami operator to the medial axis surface, and take the solution to an extended Laplacian eigenvalue problem defined on the surface as the medial axis spectrum. As the 2D case, the medial axis spectrum of a 3D shape is invariant under rigid transformation and isometry of the medial axis, and is robust to shape boundary noise as shown by our experiments. The medial axis spectrum is finally used for 3D shape retrieval, and its superiority over previous work is shown by extensive comparisons. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy