Browsing by Subject "C++"
Now showing 1 - 9 of 9
Results Per Page
Sort Options
Item A Scalable Framework for Parallelizing Sampling-Based Motion Planning Algorithms(2014-04-29) Jacobs, Samson AdeMotion planning is defined as the problem of finding a valid path taking a robot (or any movable object) from a given start configuration to a goal configuration in an environment. While motion planning has its roots in robotics, it now finds application in many other areas of scientific computing such as protein folding, drug design, virtual prototyping, computer-aided design (CAD), and computer animation. These new areas test the limits of the best sequential planners available, motivating the need for methods that can exploit parallel processing. This dissertation focuses on the design and implementation of a generic and scalable framework for parallelizing motion planning algorithms. In particular, we focus on sampling-based motion planning algorithms which are considered to be the state-of-the-art. Our work covers the two broad classes of sampling-based motion planning algorithms--the graph-based and the tree-based methods. Central to our approach is the subdivision of the planning space into regions. These regions represent sub- problems that can be processed in parallel. Solutions to the sub-problems are later combined to form a solution to the entire problem. By subdividing the planning space and restricting the locality of connection attempts to adjacent regions, we reduce the work and inter-processor communication associated with nearest neighbor calculation, a critical bottleneck for scalability in existing parallel motion planning methods. We also describe how load balancing strategies can be applied in complex environments. We present experimental results that scale to thousands of processors on different massively parallel machines for a range of motion planning problems.Item Eigen value solver in C++ for a 3D photonic crystal(2006-12) Mohandas, Prakash; Chen, Ray T.A simulation study of the modes of propagation through a 3D photonic crystal using a C++ eigen value solver is presented in this work. The valid modes of propagation through a photonic crystal can be obtained by equating the field equations across the crystal boundary, which when rearranged gives rise to a complex eigen value problem. A 2D photonic crystal would yield a comparatively simple solution but the work in this thesis looks at a 3D photonic crystal which introduces a multifold of solutions. The enormity of the solution space of this problem demands that the simulation be run on a larger environment than a PC. C++ being the most compatible coding language for advanced multi processor computing systems became the obvious choice as the simulation platform. The problem of conventional computational engines such as MATLAB not having the memory capability or the speed on a PC is the primary motivation for the development of a C++ computational model. This thesis approaches the problem in multiple steps such as generating a fourier coefficient matrix for the boundary equation, solving for all the eigen values inside the crystal. The eigen values solver in this work is setup for a symmetric 3D photonic crystal. The code allows enough room for extension of the work to ultimately obtaining the valid modes in the nonsymmetric crystal.Item Epidemic dynamics in heterogeneous populations(2012-08) Hladish, Thomas Joseph; Meyers, Lauren Ancel; Wilke, Claus O.; Bull, James J.; Keitt, Timothy H.; Sawyer, Sara L.Epidemiological models traditionally make the assumption that populations are homogeneous. By relaxing that assumption, models often become more complicated, but better representations of the real world. Here we describe new computational tools for studying heterogeneous populations, and we examine consequences of two particular types of heterogeneity: that people are not all equally likely to interact, and that people are not all equally likely to become infected if exposed to a pathogen. Contact network epidemiology provides a robust and flexible paradigm for thinking about heterogeneous populations. Despite extensive mathematical and algorithmic methods, however, we lack a programming framework for working with epidemiological contact networks and for the simulation of disease transmission through such networks. We present EpiFire, a C++ applications programming interface and graphical user interface, which includes a fast and efficient library for generating, analyzing and manipulating networks. EpiFire also provides a variety of traditional and network-based epidemic simulations. Heterogeneous population structure may cause multi-wave epidemics, but urban populations are generally assumed to be too well mixed to have such structure. Multi-wave epidemics are not predicted by simple models, and are particularly problematic for public health officials deploying limited resources. Using a unique empirical interaction network for 103,000 people in Montreal, Canada, we show that large, urban populations may feature sufficient community structure to drive multi-wave dynamics, and that highly connected individuals may play an important role in whether communities are synchronized. Finally, we show that heterogeneous immunity is an important determinant of influenza epidemic size. While many epidemic models assume a homogeneously susceptible population and describe dynamics for one season, the trans-seasonal dynamics of partially immunizing diseases likely play a critical role in determining both future epidemic size and pathogen evolution. We present a multi-season network model of a population exposed to a pathogen conferring partial cross-immunity that decays over time. We fit the model to 25 years of influenza-like illness epidemic data from France using a novel Bayesian technique. Using conservative priors, we estimate important epidemiological quantities that are consistent with empirical studies.Item Lifting the Abstraction Level of Compiler Transformations(2013-08-08) Tang, XiaolongProduction compilers implement optimizing transformation rules for built-in types. What justifies applying these optimizing rules is the axioms that hold for built-in types and the built-in operations supported by these types. Similar axioms also hold for user-defined types and the operations defined on them, and therefore justify a set of optimization rules that may apply to user-defined types. Production compilers, however, do not attempt to construct and apply these optimization rules to user-defined types. Built-in types together the axioms that apply to them are instances of more general algebraic structures. So are user-defined types and their associated axioms. We use the technique of generic programming, a programming paradigm to design efficient, reusable software libraries, to identify the commonality of classes of types, whether built-in or user-defined, convey the semantics of the classes of types to compilers, design scalable and effective program analysis for them, and eventually apply optimizing rules to the operations on them. In generic programming, algorithms and data structures are defined in terms of such algebraic structures. The same definitions are reused for many types, both built-in and user-defined. This dissertation applies generic programming to compiler analyses and transformations. Analyses and transformations are specified for general algebraic structures, and they apply to all types, both built-in and primitive types.Item Ratchet : a prototype change-impact analysis tool with dynamic test selection for C++ code(2011-05) Asenjo, Alejandro; Khurshid, Sarfraz; Kim, MiryungUnderstanding the impact of changes made daily by development teams working on large-scale software products is a challenge faced by many organizations nowadays. Development efficiency can be severely affected by the increase in fragility that can creep in as products evolve and become more complex. Processes, such as gated check-in mechanisms, can be put in place to detect problematic changes before submission, but are usually limited in effectiveness due to their reliance on statically-defined sets of tests. Traditional change-impact analysis techniques can be combined with information gathered at run-time in order to create a system that can select tests for change verification. This report provides the high-level architecture of a system, named Ratchet, that combines static analysis of C++ programs, enabled by the reuse of the Clang compiler frontend, and code-coverage information gathered from automated test runs, in order to automatically select and schedule tests that exercise functions and methods possibly affected by the change. Prototype implementations of the static-analysis components of the system are provided, along with a basic evaluation of their capabilities through synthetic examples.Item Rejuvenating C++ Programs through Demacrofictation(2012-12-04) Aditya Kumar, -As we migrate software to new versions of programming languages, we would like to improve the style of its design and implementation by replacing brittle idioms and abstractions with the more robust features of the language and its libraries. This process is called source code rejuvenation. In this context, we are interested in replacing C preprocessor macros in C++ programs with C++11 declarations. The kinds of problems engendered by the C preprocessor are many and well known. Because the C preprocessor operates on the token stream independently from the host language?s syntax, its extensive use can lead to hard-to-debug semantic errors. In C++11, the use of generalized constant expressions, type deduction, perfect forwarding, lambda expressions, and alias templates eliminate the need for many previous preprocessor-based idioms and solutions. Additionally, these features can be used to replace macros from legacy code providing better type safety and reducing software-maintenance efforts. In order to remove the macros, we have established a correspondence between different kinds of macros and the C++11 declarations to which they could be trans- formed. We have also developed a set of tools to automate the task of demacrofying C++ programs. One of the tools suggest a one-to-one mapping between a macro and its corresponding C++11 declaration. Other tools assist in carrying out iterative application of refactorings into a software build and generating rejuvenated programs. We have applied the tools to seven C++ libraries to assess the extent to which these libraries might be improved by demacrofication. Results indicate that between 52% and 98% of potentially refactorable macros could be transformed into C++11 declarations.Item simCUDA: A C++ based CUDA simulation framework(2016-05) Das, Abhishek; Gerstlauer, Andreas, 1970-; Touba, Nur AThe primary objective of this thesis is to develop a CUDA simulation framework (simCUDA) that effectively maps the existing application written in CUDA to be executed on top of standard multi-core CPU architectures. This is done by specifically annotating the application at the source level itself, and making the relevant changes required for the application to run in a similar and functionally equivalent manner on a multi-core CPU as it would run in a CUDA-supported GPU. The simulation framework has been developed using C++11 threads, which provides an abstraction for a thread of execution, as well as several classes and class templates for mutexes, condition variables, and locks, to be used for their management. As an extension to the simulation framework, the basic block sequence of execution on a per thread basis is also computed for analysis. This information can in turn be used to derive the basic block sequence of execution on a per warp basis, and thus emulate and replicate real-world behavior of a GPU.Item Simplifying the Analysis of C++ Programs(2013-08-14) Solodkyy, YuriyBased on our experience of working with different C++ front ends, this thesis identifies numerous problems that complicate the analysis of C++ programs along the entire spectrum of analysis applications. We utilize library, language, and tool extensions to address these problems and offer solutions to many of them. In particular, we present efficient, expressive and non-intrusive means of dealing with abstract syntax trees of a program, which together render the visitor design pattern obsolete. We further extend C++ with open multi-methods to deal with the broader expression problem. Finally, we offer two techniques, one based on refining the type system of a language and the other on abstract interpretation, both of which allow developers to statically ensure or verify various run-time properties of their programs without having to deal with the full language semantics or even the abstract syntax tree of a program. Together, the solutions presented in this thesis make ensuring properties of interest about C++ programs available to average language users.Item Traversal, Case Analysis, and Lowering for C++ Program Analysis(2010-01-14) Wagner, Luke A.To work effectively, programmers need tools to support their typical development activities, such as the creation, analysis, and transformation of source code. Analysis and transformation tools can be difficult to write for modern programming languages and, without a reusable framework, each tool must separately implement nontrivial algorithms like name lookup and type checking. This thesis describes an extension to one such framework, named Pivot, that focuses on programs written in C++. This extension, named Filter, assists the tool builder in traversal, case analysis, and lowering of the data structure representing C++ programs. Comparisons described in the thesis show a 2-4x code reduction when solving basic problems (e.g., searching for uses of a given declaration) using the extension and a performance overhead that drops below 2x for larger problems (e.g., checking C++ layout compatibility).