Search

This thesis describes a new method to solve the security-constrained optimal power flow (SCOPF) by dividing the into base case and contingency cases. The base case solution is found by using generalized Bender Decomposition(GBD) which will divide the problem into master and sub-problem. For contingency cases, each individual case can be solved separately and independently from each other using parallel programing. There are 3 approaches for contingency, using GBD, heuristic, and implementing LODF and PTDF. Test data are from ARPA-E GO Competition Challenge 2 Final Event which consists of 16 synthetic networks and 84 scenarios with varying size from 617 buses to 31777 buses. The extension of the methodology will be discussed further in the thesis.

Machine learning techniques utilize training data samples to help understand, predict, classify, and make valuable decisions for different applications such as medicine, email filtering, speech recognition, agriculture, and computer vision, where it is challenging or unfeasible to produce traditional algorithms to accomplish the needed tasks. Unsupervised ML-based approaches have emerged for building groups of data samples known as data clusters for driving necessary decisions about these data samples and helping solve challenges in critical applications. Data clustering is used in multiple fields, including health, finance, social networks, education, and science. Sequential processing of clustering algorithms, like the K-Means, Minibatch K-Means, and Fuzzy C-Means algorithms, takes a long time, especially with many data samples, regardless of whether the results obtained may be accurate or not.This thesis proposes parallel and distributed computing unsupervised ML techniques to improve the execution time of different ML algorithms. The application of different ML techniques on each system and their specific variations is outlined. Various parallelized unsupervised ML models are developed, implemented, and tested to demonstrate the efficiency, in terms of execution time and accuracy, of the serial methods as compared to the parallelized ones. For that, parallel K-Means, parallel Minibatch K-Means, and Fuzzy parallel C-Means using an MPI model are developed. A distributed time estimation approach is created that utilizes the AWS could computing architecture. The Sequential, Parallel, and distributed approaches of K-Means, Minibatch K-means, and Fuzzy C-Means are investigated to enhance the outcome of the developed models. The strengths and weaknesses of various ML-based algorithms are analyzed.As a case study, a country dataset for multiple organizations is used to provide financial assistance to nations based on socioeconomi and health factors and use K-Means, Minibatch K-Means, and Fuzzy C-Means sequential Parallel and distributing techniques like AWS to analyze the data. We developed a serial, parallel, and distributive computing technology based on ML AWS architecture to determine the most efficient method through comparative analysis and our research investigations to provide K-Means, Minibatch K-Means, and Fuzzy C-Means execution timings. Our results reveal that Minibatch K-Means outperforms the other two clustering methods in sequential execution while outperforming them in parallel execution. It is observed that all the developed models perform better in the sequential model than in the parallel model. This work concludes that execution times reduce when these models are implemented on distributed platforms, i.e., Amazon SageMaker, a cloud computing platform, with no noticeable impact on the accuracy of the developed models.

Parallel programming offers the ability to simultaneously improve the performance and reduce the energy consumption of software running on heterogeneous computing systems. Software developers have long preferred to avoid parallel programming, if possible, for reasons such as perceived difficulty, lack of portability between systems, and the pace of improvement in computer hardware. However, generational changes in computer hardware are now focused on specialized components and increased computational cores, and the continued evolution of these systems places increased emphasis on achieving improvements via the use of these components. This thesis investigates parallel programming techniques that make use of components common to modern heterogeneous systems, and proposes that the difficulty and lack of portability need not be barriers to large improvements. Using a variety of heterogeneous systems, algorithms were implemented and then transformed using multiple cores, SIMD execution units, and GPUs. Reductions in execution time ranging from 71-94% and energy consumption of 76-98% were observed, demonstrating the effectiveness of using specialized components for improved performance and reduced energy consumption.

Water drainage modeling codes need to be updated with parallel simulation capability to leverage modern computational trends. Parallelized finite-difference/volume simulation of 1D networks implies a solution to the network partitioning problem in Graph Theory. Myriad heuristic strategies exist for achieving a valid network partition set, as proving an optimal set is formally intractable. However, water drainage networks have received limited study in the context of network partitioning; existing strategies may not address the particular characteristics of 1D water drainage networks, i.e. directed, acyclic graphs (DAGs) with non-power law connectivity, imbalanced link weights, etc. Additionally, a comparison between partitioning algorithms is ambiguous; partition set quality remains undefined for drainage networks whose parallel simulation complexity scales on the total length of the system and number of inter-processor communications per time-step. Herein, a novel network partitioning algorithm designed for 1D water drainage networks, but valid for all DAGs, is presented. The novel algorithm, BIPquick, uses analogies to flow accumulation for stream delineation to determine partition delineation. BIPquick is shown to compare favorably, on the counts of partition size balance and connectivity, with multi-level partitioning methods, KaHIP and METIS, for a suite of regional-scale river basins in Texas. The critical role of connectivity in determining the quality of a partition set is established in a comparison of low-connectivity (BIPquick) partitioning vs high-connectivity (Link-Balance) partition for a state-of-the-art parallelized Saint-Venant solver, the SWMM5+ hydraulic engine developed by the National Center for Infrastructure Modeling and Management (NCIMM) based at the University of Texas at Austin.

Electronic design automation (EDA) algorithms are essential for circuit designers to handle huge circuits, modeled as graphs or hypergraphs, while meeting tight design schedules. Shortening the turn-around time of EDA algorithms through parallelization is attractive due to multicore machines being ubiquitous and inexpensive for more than a decade. However, parallelizing EDA algorithms effectively is difficult due to the compute irregularity in graph algorithms. In this dissertation, we study the effective parallelization of static timing analysis (STA), the core module for timing-driven EDA algorithms. We first analyze the parallelism within graph-based STA algorithms for synchronous circuits using the operator formulation, and identify suitable schedules for both full and incremental timing update. We then apply the same methodology to path-based STA algorithms for synchronous circuits, and distill out subgraph tagging as a building block for accuracy enhancement in STA. We prototype Blitz, a parallel STA engine built with Galois 6.0, and compare Blitz against the state-of-the-art open source parallel timers to demonstrate our effective parallelization for STA without losing timing accuracy. Finally, we study the parallelization of STA for AND-causal asynchronous circuits. We extract the parallelism available in asynchronous timing algorithms, devise efficient schedules for fast convergence when cyclic dependencies exist, and deploy subgraph tagging in checking asynchronous timing violations. This results in Cyclone, the first parallel STA engine for large asynchronous circuits.

Since the end of Dennard’s scaling, computer architects have fully embraced parallelism to con- tinue improving the performance and energy efficiency of general-purpose processors. Multicore processors with a few to tens of high performance processor cores have been the centerpiece of many computing platforms ranging from mobile devices to data centers. Manycore proces- sors with hundreds or thousands of simple processing elements have demonstrated their ability to achieve even higher throughput and energy efficiency when abundant explicit parallelism exists in the workloads. However, large-scale manycore processors often lack hardware-based cache co- herence. There is a growing trend towards a tighter integration between multicore and manycore processors, forming heterogeneous multi/manycore systems. These systems use heterogeneous cache coherence (HCC) with hardware-based cache coherence within the multicore and software- centric cache coherence with in the manycore. Unfortunately, programming heterogeneous multi/manycore systems to enable collaborative execution is challenging, especially when considering dynamic task parallelism. This thesis uses a combination of light-weight software and hardware techniques to elegantly address this problem. It provides a detailed description of how to imple- ment a work-stealing runtime to enable dynamic task parallelism on heterogeneous cache-coherent systems with a unified task-based programming model. This thesis also proposes direct task steal- ing (DTS), a new technique based on user-level interrupts to bypass the memory system and thus improve the performance and energy efficiency of work stealing. The cycle-level results in this thesis demonstrate that executing dynamic task-parallel applications on a 64-core system (4 big, 60 tiny) with complexity-effective HCC and DTS can achieve: 7× speedup over a single big core; 1.4x speedup over an area-equivalent eight big-core system with hardware-based cache coher- ence; and 21% better performance and similar energy efficiency compared to a 64-core system (4 big, 60 tiny) with full-system hardware-based cache coherence. This thesis also describes a realistic hardware implementation of heterogeneous multi/manycore systems based on an open-source hardware prototyping framework, OpenPiton. Using a VLSI methodology, this thesis shows that the heterogeneous multi/manycore approach achieves 3x hardware parallelism with the same area compared to a traditional homogeneous manycore.

Many programming problems are assumed to require low-level programming approaches, due to highly specific requirements. As such, these problems are solved in low-level programming languages, which require the programmer to specify every detail of execution. This work challenges that view point by developing a series of models and techniques, which enable high-level programming techniques to be applied to low-level problems. OrcO generalized the concept of objects to decouple them from the concurrent structure of the program. This allows programs to be expressed more naturally and be more maintainable because it eliminates adverse coupling between abstraction and concurrency. OrcO allows objects to hide their concurrent structure from clients, and allows clients to access objects in a concurrency-agnostic way. PorcE is a compiler and runtime for a high-level concurrent programming language that attempts to automatically eliminate excess concurrency to produce an optimized concurrent program. It hides the details of the execution from the programmer and asks the programmer to write a maximally concurrent program for it to optimize. PorcE shows both the promise of deparallelizing for performance and the challenges of optimizing programs without programmer provided insight into the programs structure. Lapis 2 is a specification language for concisely expressing the interaction semantics of low-level APIs. Lapis 2 is based on Lapis 1 developed for AvA. Lapis 1 and Lapis 2 can be used to automatically generate compatible API remoting systems for low-level C APIs. In addition, they can be extended to support virtualization specific features, such as resource usage tracking and migration of an application from one physical resource to another. Lapis 2 builds on Lapis 1 and provides a rule system that can abstract away low-level details while still allowing detailed control when required. The rule system dramatically improves reduces the size of API specifications. Lapis does not hide the low-level details, but instead makes it easy to express them clearly and concisely. As such, Lapis 2 enables techniques that are often restricted to high-level managed languages, such as compatible automatic API remoting, to be applied to low-level APIs written in C.

Modular verification of parallel and concurrent software built from reusable data abstractions is a challenging problem. Reasoning about sequential software can be modularized using the specifications of data abstractions, but the need to consider implementation details complicates reasoning about parallel execution.Addressing this challenge requires advancing the state of the art in several ways, beginning with a theoretical foundation. The A/P Calculus for describing the effects of program actions is developed in this dissertation to enable sound modular reasoning about parallel programs with non-interfering parallel sections of operation calls on abstract data types. Building on the calculus and a programming language with clean semantics, a methodology for designing decomposable data abstractions is presented to produce fork-join parallel programs that are manifestly data race free and readily amenable to modular reasoning. A new specification construct, the non-interference contract, is proposed to enhance the specification of data abstractions to hide implementation details and yet facilitate modular reasoning about parallel programs that share objects among processes.As a key first step to transition these results to practice, this dissertation describes Clean++, a discipline for writing software in C++ that leverages move semantics to make ownership transfer the primary data movement operation (as opposed to either deep or shallow copying) and produce programs that are amenable to formal verification with only minimal scaffolding related to pointer manipulation.

Modern atomic physics is increasingly dependent on the results of high-precision calculations to guide experiments and applications, especially in complex atoms with dense spectra. Many cutting-edge applications and experiments use atoms with open-shell electronic structure and strong configuration mixing, which require extremely large numerical bases to treat with any level of accuracy. At the same time, supercomputing clusters have seen huge increases in computational power, driven by increasingly large-scale parallelism across many distributed compute nodes. Consequently, modern atomic structure code must be designed to fully utilise massively-parallel computing resources if they are to keep up with the increasing demands of experimental studies.In this thesis, I present the results of work to modernise the AMBiT atomic structure software, which implements the configuration interaction with many-body perturbation theory (CI+MBPT) method, to take advantage of modern supercomputers. I present a detailed outline of the software engineering processes in converting AMBiT from an MPI-only model of parallelism to a hybrid MPI+OpenMP model, as well as the performance gains resulting from doing so. I show that the increased parallelism allows us to explore numerical saturation of the CI+MBPT method in open-shell atoms for the first time ever --- an investigation would not have been possible without the increased performance capabilities of modern supercomputers.I have applied the new AMBiT to calculations of atomic systems with a variety of electronic structures. Calculations of the highly-charged ions Sn7+-Sn10+, which are of experimental interest for their applications in extreme ultraviolet photolithography for semiconductor fabrication, show that AMBiT is highly efficient for ions with open d-shells. We achieve very close agreement with experimental spectra: CI+MBPT calculations differ from experiments by an average error of less than 1%. Additionally, calculations for two- and three-valent Lr+ and Lr demonstrate that CI+MBPT implemented in AMBiT can accurately calculate the spectra of superheavy elements - systems in which relativistic and QED effects are significant. My calculations for Lr and Lr+ also show that our CI+MBPT implementation is competitive with other cutting-edge methods for relativistic atomic structure calculations.This research shows that the accuracy of the CI+MBPT method, when scaled out to numerical saturation, is competitive with best-in-class methods for atomic structure calculations and can continue to serve as a workhorse for next-generation atomic structure calculations. Following its release, AMBiT has been used by multiple research groups for calculations of highly-charged ion clocks and precision tests for physics beyond the standard model. Furthermore, this research should put AMBiT and CI+MBPT in a strong position to scale up and capitalise on future gains in high-performance computing technology.

This thesis presents a paradigm for accelerating the Cauchy Estimator using high performance computing for discrete linear systems with scalar process and measurement noises. The Cauchy Estimator is developed in such a way that is conducive to parallelization and thus presents an opportunity to leverage the graphics processing unit (GPU) to bring the algorithm closer to a real time environment. This work compartmentalizes the estimator into smaller routines and presents algorithms that were developed to accelerate the computations across several independent terms. First, the serial implementation is given for comparison and to help build intuition. Then, the GPU implementation is given along with the parameter sending and receiving requirements for each function. Simulations demonstrate that parallelization does eventually outpace the serial implementation along with an almost linear scaling in time after each subsequent measurement.

Deterministic parallel programming models are a beacon of hope in the stormy, concurrency-bug-ridden seas of parallel programming. These models guarantee that any parallel execution of a program produces the same results as a sequential execution, implying the absence of any kind of concurrency bugs. However, most existing deterministic models rely on compile-time techniques and on complex program annotations to achieve this goal. While such an approach ensures high performance, it negatively affects the simplicity of a language, making it unsuitable for non-expert programmers. This dissertation explores a relatively uncharted area in the design space of parallel programming models and presents an approach that is deterministic, but relies primarily on runtime checking to guarantee this property. In this programming model, every object plays a role in every concurrent task, for example, the readwrite role or the readonly role. When an object is shared with a new task, it adapts to the new sharing pattern by changing its roles and therefore its behavior, namely, by changing the set of permitted operations that can be performed with this object. This mechanism can be leveraged to prevent interfering accesses from concurrently executing tasks and makes parallel execution deterministic. To this end, the dissertation presents a role-based programming language that includes several novel concepts (role transitions, guarding, slicing) to enable practical deterministic parallel programming. Unlike previous deterministic languages, this language can express a variety of parallel patterns without relying on complex language constructs or rigorous restrictions. A prototype implementation demonstrates that this dynamic approach yields high performance for a range of programs, despite the overhead that stems from the necessary runtime checks. In particular, the implementations of 8 widely used programming problems achieve substantial parallel speedups, as a result of a combination of optimizations specifically tailored towards this programming model. In summary, this dissertation demonstrates that deterministic parallel programming can be realized with a dynamic instead of a static approach, yielding vastly different—and much simpler—language designs.

Abstract: Electromagnetic transient (EMT) simulation, which is widely utilized in power system planning and design, is one of the most complex power system studies that requires detailed modeling of the study system including all frequency-dependent and nonlinear effects. Large-scale EMT simulation is becoming commonplace due to the increasing growth and interconnection of power grids, and the need to study the impact of system events of the wide area network. To cope with enormous computational burden, the massively parallel architecture of the graphics processing unit (GPU) is exploited in this work for large-scale EMT simulation. A fine-grained network decomposition, called shattering network decomposition, is proposed to divide the power system network exploiting its topological and physical characteristics into linear and nonlinear networks, which adapt to the unique features of the GPU-based massive thread computing system. Large-scale systems, up to 240,000 nodes, with typical components, including synchronous machines, transformers, transmission lines and nonlinear elements, are tested and compared with mainstream simulation software to verify the accuracy and demonstrate the speed-up improvement with respect to sequential computation. Power electronic devices are widely utilized in modern power grid, especially for AC/DC converters in HVDC systems. The proposed fine-grained decomposition algorithm can also be applied in the simulation of multiple levels modular multilevel converter (MMC) consisting of Insulated Gate Bipolar Transistors (IGBTs) based on linear and nonlinear switch models, which effectively enhances the simulation performance and extends the system scale by parallelizing the calculation and maintaining the convergence during the computation.

As technology scaling slows down and only provides diminishing improvements in general-purpose processor performance, computing systems are increasingly relying on customized accelerators to meet the performance and energy efficiency requirements of emerging applications. For example, today's mobile SoCs rely on accelerators to perform compute-intensive tasks, and datacenters are starting to deploy accelerators for applications such as web search and machine learning. This trend is expected to continue and future systems will contain more specialized accelerators. However, the traditional hardware-oriented accelerator design methodology is costly and inefficient because it requires significant manual effort in the design process. This development model is unsustainable in the future where a wide variety of accelerators are expected to be designed for a large number of applications. To solve this problem, the development cost of accelerators must be drastically reduced, which calls for more productive design methodologies that can create high-quality accelerators with low manual effort. This thesis addresses the above challenge with architectural frameworks that combine novel accelerator architectures with automated design and optimization frameworks to enable designing high-performance and energy-efficient accelerators with minimal manual effort. Specifically, the first part of the thesis proposes a framework for automatically generating accelerators that can effectively tolerate long, variable memory latencies, which improves performance and reduces design effort by removing the need to manually create data preloading logic. The framework leverages architecture mechanisms such as memory prefetching and access/execute decoupling, as well as automated compiler analysis to generate accelerators that can intelligently preload data needed in the future from the main memory. The second part of the thesis proposes a framework for building parallel accelerators that leverage concepts from task-based parallel programming, which enables software programmers to quickly create high-performance accelerators using familiar parallel programming paradigms, without needing to know low-level hardware design knowledge. The framework uses a computation model that supports dynamic parallelism in addition to static parallelism, and includes a flexible architecture that supports dynamic scheduling to enable mapping a wide range of parallel applications to hardware accelerators and achieve good performance. In addition, we designed a unified language that can be mapped to both software and hardware, enabling programmers to create parallel software and parallel accelerators in a unified framework. The third part of the thesis proposes a framework that enables accelerators to perform intelligent dynamic voltage and frequency scaling (DVFS) to achieve good energy-efficiency for interactive and real-time applications. The framework combines program analysis and machine learning to train predictors that can accurately predict the computation time needed for each job, and adjust the DVFS levels to reduce the energy consumption.

Today, plasma-enhanced chemical vapor deposition (PECVD) remains the dominant processing method for the manufacture of silicon thin films due to inexpensive production and low operating temperatures. Nonetheless, thickness non-uniformity continues to prevent the deposition of high quality thin film layers across large wafer substrates; thickness deviations up to 20% are typical for 200 mm and above wafers. Regardless of industry, be it solar cell production or microelectronic devices, the demand for densely packed die with high quality creates a need for improved modeling and operational strategies. Over the past two decades, a number of research groups have built microscopic models for thin film growth, as well as macroscopic reactor models to approximate the gas phase reaction and transport phenomena present within PECVD systems. Unfortunately, many of the proposed modeling and simulation techniques have been overly simplified in order to reduce computational demands, or fail to capture both the macro- and microscopic domains simultaneously. In order to address persistent issues related to thickness non-uniformity in silicon processing, advanced multiscale models are needed.Motivated by these considerations, novel reactor modeling and operational control strategies are developed in this dissertation. Specifically, a macroscopic reactor scale model is presented which captures the creation of a radio frequency (RF) plasma, transport throughout the reactor domain, and thirty-four dominant plasma-phase reactions. In Chapters 2 and 3, the gas-phase dynamics are approximated using a first principles-based model, whereas the latter half of this dissertation relies on a computational fluid dynamics approach. At the microscopic scale, the complex particle interactions that define the growth of a-Si:H thin film layers are tracked using a hybrid kinetic Monte Carlo algorithm. These scales are linked via a dynamic boundary condition which is updated at the completion of each time step. A computationally efficient parallel programming scheme allows for significantly shortened computational times and solutions to previously infeasible system sizes. Transient batch deposition cycles using the aforementioned multiscale model provide new insight into the operation of PECVD systems; spatial non-uniformity in the concentration of SiH3 and H above the substrate surface is recognized as the primary mechanism responsible for non-uniform thin film product thicknesses. Two key modes are identified to address the aforementioned non-uniformity: (1) run-to-run control of the wafer substrate temperature through the adaptation of an exponentially-weighted moving average algorithm, and (2) the design of new CVD geometries which minimize spatial variations in the concentration of deposition species. These efforts have resulted in optimized PECVD showerhead designs and spatial temperature profiles which limit the thin film thickness non-uniformity to within 1% of the product specification.

The importance of irregular applications such as graph analytics is rapidly growing with the rise of Big Data. However, parallel graph workloads tend to perform poorly on general-purpose chip multiprocessors (CMPs) due to poor cache locality, low compute intensity, frequent synchronization, uneven task sizes, and dynamic task generation. At high thread counts, execution time is dominated by worklist synchronization overhead and cache misses. Researchers have proposed hardware worklist accelerators to address scheduling costs, but these proposals often harden a specific scheduling policy and do not address high cache miss rates. This thesis presents Minnow, a technique that addresses these bottlenecks by augmenting each core in a CMP with a memory throughput-optimized lightweight engine connected through an accelerator interface. These engines offload worklist operations from worker threads, reducing synchronization costs and improving scalability. The engines also perform worklist-directed prefetching, a software prefetching technique that exploits knowledge of upcoming tasks to perform nearly perfectly accurate and timely prefetch operations. In this thesis, we first characterize several graph applications within a popular graph analytics framework to determine their performance and bottlenecks. Next, Minnow and worklist-directed prefetching are discussed in detail, including the Minnow accelerator interface, microarchitecture, and prefetch flow control mechanism. Finally, the benefits of Minnow and worklist-directed prefetching are evaluated within a cycle-accurate microarchitectural simulator.

One of the fundamental problems in parallel programming is that there is no simple programming paradigm that provides mutual exclusion and synchronization with efficient implementation at the same time. For monitor [Hoa74,Han75] (lock-based) systems, only experienced programmers can develop high-performance fine-grained lock-based implementations. Programmers frequently introduce bugs with traditional monitors. Researchers have proposed transactional memory [HM93,ST95], which provides a simple and elegant mechanism for programmers to atomically execute a set of memory operations so that there is no deadlock in transactional memory systems. However, most of transactional memory systems lack conditional synchronization support [WLS14,LW14]. Hence, writing multi-threaded programs with conditional synchronization is rather difficult. In this dissertation, we develop a parallel programming framework that provides simple constructs for mutual exclusion and synchronization as well as efficient implementation.

Abstract: Power electronic devices have been utilized in myriad applications in power system at all voltage and power levels. Accurate and efficient simulation is required for precise control and performance analysis of power electronic converters. Nonlinear physics-based device-level models of power electronic devices, such as insulated-gate bipolar transistor and power diode, have been previously developed to give detailed information of the components. Due to the high frequency switching transients, model complexity and nonlinear device characteristics, the application of physics-based model has hitherto been limited. Massive-thread computing brings up a new concept of dealing with highly complex models using parallel processing. Graphics processors equipped with thousands of compute cores meet the requirement of data and task parallelism for the solution of large-scale power electronic systems containing multiple detailed components while significantly increasing the simulation efficiency. This thesis provides the application of massively parallel processing in large-scale power electronic circuit simulation. Massively parallel modules are developed for the physics-based IGBT and power diode models, in addition, efficient numerical solvers are developed for numerical linear and nonlinear system solution. The implementations are verified for the simulation of modular multi-level converters (MMCs) and compared with commercial device-level simulation software. The results show good agreement, larger-scale computational capability and considerable acceleration.

Abstract: Open Computing Language (OpenCL) is a high-level language that allows developers to produce portable software for heterogeneous parallel computing platforms. OpenCL is available for a variety of hardware platforms, with compiler support being recently expanded to include Field-Programmable Gate Arrays (FPGAs). This work investigates flexible OpenCL designs for the iterative min-sum decoding algorithm for both symmetric and asymmetric Low-Density Parity Check (LDPC) codes over a range of codeword lengths. The computationally demanding LDPC decoding algorithm offers several forms of parallelism that could be exploited by the Altera-Offline-Compiler (AOC version 15.1) for OpenCL. By starting with the recommended design approaches and optimizing based on experimentation, the highest throughput symmetric LDPC decoder produced a maximum corrected codeword throughput of 68.22 Mbps for 32 decoding iterations at the compiler-selected FPGA clock frequency of 163.88 MHz for a length-2048 (3,6)-regular code. Designs for three of the DOCSIS 3.1 [7] standard asymmetric codewords were investigated and implemented using the AOC. The designs prove that OpenCL on FPGAs can produce high-throughput results for industry-sized asymmetric LDPC codes with significantly shorter design time compared to other custom hardware and software applications.

Abstract: Growing system size and complexity along with the large amount of data provided by phasor measurement units (PMUs) are the drivers for accurate state estimation algorithms for online monitoring and operation of power grids. State estimation is the process of estimating unknown state variables in a power grid, which are then used for energy management system (EMS) functions in the control centre. Even with modern computing power, the large volume of computation in the state estimation process is highly time and memory intensive, and a serious bottleneck for online operation and control of the grid. Furthermore, the deployment of new smart grid technologies in communication and smart metering technologies brings new challenges to the state estimation problem. In addition to failure of physical infrastructure, the smart grid is also sensitive to cyber-attacks on its communication layer. Intelligent cyber-attacks can be designed to be unobservable by the traditional bad data detector. Such attacks can significantly impact the decision making process in control centres and can result in potentially catastrophic outcomes. The focus of this research is to design parallel computational algorithms to accelerate dynamic state estimation for both static and dynamic states in large-scale power networks. Moreover, a stochastic model is proposed to guard the system against intelligent cyberattacks. Utilizing the massively parallel architecture of graphic processors and using detailed models of power system components, the proposed research achieved the required accuracy as well as the computational speed-up in the results.

Parallel programming frameworks rapidly evolve to meet the performance demands of High Performance Computing (HPC) applications and the concurrent evolution of supercomputing class system architectures. To meet this demand, standards and specifications that outline the semantics and required capabilities of parallel programming models are being developed by committees of government and industry experts and then implemented by third parties. OpenMP and MPI are particularly prominent examples of such programming models and specifications, and are in common use in the HPC world. Comprehensive testing is required to be sure that any given implementation adheres to the published standard. The type and degree of testing depends on the goals of the developers. In particular, commercial implementations developed by companies for specialized applications (like HPC) will have much more stringent requirements than those for general applications. This thesis describes the development of test suites targeted toward a subset of OpenMP and MPI features, namely processor affinity and thread safety, as implemented in Cray compilers and libraries. These tests, the focus of which were robustness, re-usability, and detailed error output, contributed to software quality for the wide range of applications for which Cray compilers are used, and continue to help Cray ensure correctness in their OpenMP and MPI implementations as their compilers and libraries continue to evolve.

A goal of computer science is to develop practical methods to automate tasks that are otherwise too complex or tedious to perform manually. Complex tasks can include determining a practical algorithm and creating the associated implementation for a given problem specification. Goal-oriented programming can make this systematic. Therefore, we can rely on automated tools to create implementations by expressing the task of creating implementations in terms of goal-oriented programming. To do so, pertinent knowledge must be encoded which requires a notation and language to define relevant abstractions. This dissertation focuses on distributed-memory parallel tensor computations arising from computational chemistry. Specifically, we focus on applications based on the tensor contraction operation of dense, non-symmetric tensors. Creating an efficient algorithm for a given problem specification in this domain is complex; creating an optimized implementation of a developed algorithm is even more complex, tedious, and error-prone. To this end, we encode pertinent knowledge for distributed-memory parallel algorithms for tensor contractions of dense non-symmetric tensors. We do this by developing a notation for data distribution and redistribution that exposes a systematic procedure for deriving a family of algorithms for this operation for which efficient implementations exist. We validate the developed ideas by implementing them in the Redistribution Operations and Tensor Expressions application programming interface (ROTE API) and encoding them into an automated system, DxTer, for systematically generating efficient implementations from problem specifications. Experiments performed on the IBM Blue Gene/Q and Cray XC30 architectures testing generated implementations for the spin-adapted coupled cluster singles and doubles method from computational chemistry demonstrate impact both in terms of performance and storage requirements.

EpiFast is a parallel algorithm for large-scale epidemic simulations, based on an interpretation of the stochastic disease propagation in a contact network. The original EpiFast implementation is based on a master-slave computation model with a focus on distributed memory using message-passing-interface (MPI). However, it suffers from few shortcomings with respect to scale of networks being studied. This thesis addresses these shortcomings and provides two different implementations: Spark-EpiFast based on the Apache Spark big data processing engine and Charm-EpiFast based on the Charm++ parallel programming framework. The study focuses on exploiting features of both systems that we believe could potentially benefit in terms of performance and scalability. We present models of EpiFast specific to each system and relate algorithm specifics to several optimization techniques. We also provide a detailed analysis of these optimizations through a range of experiments that consider scale of networks and environment settings we used. Our analysis shows that the Spark-based version is more efficient than the Charm++ and MPI-based counterparts. To the best of our knowledge, ours is one of the preliminary efforts of using Apache Spark for epidemic simulations. We believe that our proposed model could act as a reference for similar large-scale epidemiological simulations exploring non-MPI or MapReduce-like approaches.

This work details the opportunities and challenges of porting a petascale-capable, MPI-based application LAMMPS to OpenSHMEM. We investigate the major programming challenges stemming from the differences in communication semantics, address space organization, and synchronization operations between the two pro- gramming models. This work provides several approaches to solve those challenges for representative communication patterns in LAMMPS, e.g., by utilizing group synchronization, peer’s buffer status tracking, double buffer strategy and unpacked direct transfer of data. The performance of LAMMPS is evaluated on the Titan HPC system at ORNL. The OpenSHMEM implementations are compared with MPI version in terms of both strong and weak scaling. The results outline that OpenSHMEM provides a rich semantic to implement scalable scientific applications. In addition, the experiments demonstrate that OpenSHMEM can compete with, and often improve on, the optimized MPI implementation.

Many scientific simulation codes represent physical systems by storing dataat a set of discrete points. For example, a weather modeling software applicationmay store data representing temperature, wind velocity, air pressure, humidity,etc. at a set of points in the atmosphere over a portion of the Earth's surface.Similarly, Computational Fluid Dynamics (CFD) software stores data representingfluid velocity, pressure, etc. at discrete points in the domain of the particularproblem being solved. In many simulations, this set of discrete points isa structured grid; i.e., a finite n-dimensional regular lattice.One of the most important steps in many scientific simulations is the solutionof a system of linear equations, where the unknowns of the system correspondto data elements at each of the discrete points used to model the system.If the simulation is based on a structured grid, this linear system willoften have a special structure itself, and this structure may lead tomore efficient techniques for solving the system than can be used forgeneral sparse linear systems.Scientific simulations most often use an iterative technique such asthe Conjugate Gradient Method or GMRES for solving linear systems..It is well known that these iterativetechniques converge much more quickly if a preconditioner is used. The ILU,or Incomplete LU Factorization, preconditioner is a good choice but it isnot parallelizable is a straightforward way.This thesis examines techniques for parallelizing the application of the ILUpreconditioner to linear systems arising from scientific simulations on structured grids.Various techniques are tested and timing results are recorded for different types andsizes of linear systems on structured grids.

A programming model which allows users to program with high productivity and which produces high performance executions has been a goal for decades. This dissertation makes progress towards this elusive goal by describing the design and implementation of the Galois system, a parallel programming model for shared-memory, multicore machines. Central to the design is the idea that scheduling of a program can be decoupled from the core computational operator and data structures. However, efficient programs often require application-specific scheduling to achieve best performance. To bridge this gap, an extensible and abstract scheduling policy language is proposed, which allows programmers to focus on selecting high-level scheduling policies while delegating the tedious task of implementing the policy to a scheduler synthesizer and runtime system. Implementations of deterministic and prioritized scheduling also are described. An evaluation of a well-studied benchmark suite reveals that factoring programs into operators, schedulers and data structures can produce significant performance improvements over unfactored approaches. Comparison of the Galois system with existing programming models for graph analytics shows significant performance improvements, often orders of magnitude more, due to (1) better support for the restrictive programming models of existing systems and (2) better support for more sophisticated algorithms and scheduling, which cannot be expressed in other systems.

Algorithms in new application areas like machine learning and data analytics usually operate on unstructured sparse graphs. Writing efficient parallel code to implement these algorithms is very challenging for a number of reasons. First, there may be many algorithms to solve a problem and each algorithm may have many implementations. Second, synchronization, which is necessary for correct parallel execution, introduces potential problems such as data-races and deadlocks. These issues interact in subtle ways, making the best solution dependent both on the parallel platform and on properties of the input graph. Consequently, implementing and selecting the best parallel solution can be a daunting task for non-experts, since we have few performance models for predicting the performance of parallel sparse graph programs on parallel hardware. This dissertation presents a synthesis methodology and a system, Elixir, that addresses these problems by (i) allowing programmers to specify solutions at a high level of abstraction, and (ii) generating many parallel implementations automatically and using search to find the best one. An Elixir specification consists of a set of operators capturing the main algorithm logic and a schedule specifying how to efficiently apply the operators. Elixir employs sophisticated automated reasoning to merge these two components, and uses techniques based on automated planning to insert synchronization and synthesize efficient parallel code. Experimental evaluation of our approach demonstrates that the performance of the Elixir generated code is competitive to, and can even outperform, hand-optimized code written by expert programmers for many interesting graph benchmarks.

Graphics Processing Units (GPUs) are becoming increasingly popular not only across various scientific communities, but also as integrated data-parallel accelerators on existing multicore processors. Support for massive fine-grained parallelism in contemporary GPUs provides a tremendous amount of computing power. GPUs support thousands of lightweight threads to deliver high computational throughput. Popularity of GPUs is facilitated by easy-to-adopt programming models such as CUDA and OpenCL that aim to ease programmers' efforts while developing parallel GPU applications. However, designing and implementing correct and efficient GPU programs is still challenging since programmers must consider interaction between thousands of parallel threads. Therefore, addressing these challenges is essential for improving programmers' productivity as well as software reliability. Towards this end, this dissertation proposes mechanisms for improving programmability of irregular applications and ensuring correctness of compute kernels.Some applications possess abundant data-level parallelism, but are unable to take advantage of GPU's parallelism. They exhibit irregular memory access patterns to the shared data structures. Programming such applications on GPUs requires synchronization mechanisms such as locks, which significantly increase the programming complexity. Coarse-grained locking, where a single lock controls all the shared resources, although reduces programming efforts, can substantially serialize GPU threads. On the other hand, fine-grained locking, where each data element is protected by an independent lock, although facilitates maximum parallelism, requires significant programming efforts. To overcome these challenges, we propose transactional memory (TM) on GPU that is able to achieve performance comparable to fine-grained locking, while requiring minimal programming efforts. Transactional execution can incur runtime overheads due to activities such as detecting conflicts across thousands of GPU threads and managing a consistent memory state. Thus, in this dissertation we illustrate lightweight TM designs that are capable of scaling to a large number of GPU threads. In our system, programmers simply mark the critical sections in the applications, and the underlying TM support is able to achieve performance comparable to fine-grained locking.Ensuring functional correctness on GPUs that are capable of supporting thousands of concurrent threads is crucial for achieving high performance. However, GPUs provide relatively little guarantee with respect to the coherence and consistency of the memory system. Thus, they are prone to a multitude of concurrency bugs related to inconsistent memory states. Many such bugs manifest as some form of data race condition at runtime. It is critical to identify such race conditions, and mechanisms that aid their detection at runtime can form the basis for powerful tools for enhancing GPU software correctness. However, relatively little attention has been given to explore such runtime monitors. Most prior works focus on the software-based approaches that incur significant overhead. We believe that minimal hardware support can enable efficient data race detection for GPUs. In this dissertation, we propose a hardware-accelerated data race detection mechanism for efficient and accurate data race detection in GPUs. Our evaluation shows that the proposed mechanism can accurately detect data race bugs in GPU programs with moderate runtime overheads.

In order to reach exascale computing capability, accelerators have become a crucial part in developing supercomputers. This work examines the potential of two latest acceleration technologies, Intel Many Integrated Core (MIC) Architecture and Graphics Processing Units (GPUs). This thesis applies three benchmarks under 3 different configurations, MPI+CPU, MPI+GPU, and MPI+MIC. The benchmarks include intensely communicating application, loosely communicating application, and embarrassingly parallel application. This thesis also carries out a detailed study on the scalability and performance of MIC processors under two programming models, i.e., offload model and native model, on the Beacon computer cluster. According to different benchmarks, the results demonstrate different performance and scalability between GPU and MIC. (1) For embarrassingly parallel case, GPU-based parallel implementation on Keeneland computer cluster has a better performance than other accelerators. However, MIC-based parallel implementation shows a better scalability than the implementation on GPU. The performances of native model and offload model on MIC are very close. (2) For loosely communicating case, the performances on GPU and MIC are very close. The MIC-based parallel implementation still demonstrates a strong scalability when using 120 MIC processors in computation. (3) For the intensely communicating case, the MPI implementations on CPUs and GPUs both have a strong scalability. GPUs can consistently outperform other accelerators. However, the MIC-based implementation cannot scale quite well. The performance of different models on MIC is different from the performance of embarrassingly parallel case. Native model can consistently outperform the offload model by ~10 times. And there is not much performance gain when allocating more MIC processors. The increase of communication cost will offset the performance gain from the reduced workload on each MIC core. This work also tests the performance capabilities and scalability by changing the number of threads on each MIC card form 10 to 60. When using different number of threads for the intensely communicating case, it shows different capabilities of the MIC based offload model. The scalability can hold when the number of threads increases from 10 to 30, and the computation time reduces with a smaller rate from 30 threads to 50 threads. When using 60 threads, the computation time will increase. The reason is that the communication overhead will offset the performance gain when 60 threads are deployed on a single MIC card.

Directive-based programming of graphics processing units (GPUs) has recently appeared as a viable alternative to using specialized low-level languages such as CUDA C and OpenCL for general-purpose GPU programming. This technique, which uses directive or pragma statements to annotate source codes written in traditional high-level languages, is designed to permit a unified code base to serve multiple computational platforms and to simplify the transition of legacy codes to new architectures. This work analyzes the popular OpenACC programming standard, as implemented by the PGI compiler suite, in order to evaluate its utility and performance potential in computational fluid dynamics (CFD) applications. Of particular interest is the handling of stencil algorithms, which are an important component of finite-difference and finite-volume numerical methods. To this end, the process of applying the OpenACC Fortran API to a preexisting finite-difference CFD code is examined in detail, and all modifications that must be made to the original source in order to run efficiently on the GPU are noted. Optimization techniques for OpenACC are also explored, and it is demonstrated that tuning the code for a particular accelerator architecture can result in performance increases of over 30%. There are also some limitations and programming restrictions imposed by the API: it is observed that certain useful features of modern Fortran (2003/8) are effectively disabled within OpenACC regions. Finally, a combination of OpenACC and OpenMP directives is used to create a truly cross-platform Fortran code that can be compiled for either CPU or GPU hardware. The performance of the OpenACC code is measured on several contemporary NVIDIA GPU architectures, and a comparison is made between double and single precision arithmetic showing that if reduced precision can be tolerated, it can lead to significant speedups. To assess the performance gains relative to a typical CPU implementation, the execution time for a standard benchmark case (lid-driven cavity) is used as a reference. The OpenACC version is compared against the identical Fortran code recompiled to use OpenMP on multicore CPUs, as well as a highly-optimized C++ version of the code that utilizes hardware aware programming techniques to attain higher performance on the Intel Xeon platforms being tested. Low-level optimizations specific to these architectures are analyzed and it is observed that the stencil access pattern required by the structured-grid CFD code sometimes leads to performance degrading conflict misses in the hardware managed CPU caches. The GPU code, which primarily uses software managed caching, is found to be free from these issues. Overall, it is observed that the OpenACC GPU code compares favorably against even the best optimized CPU version: using a single NVIDIA K20x GPU, the Fortran+OpenACC code is seen to outperform the optimized C++ version by 20% and the Fortran+OpenMP version by more than 100% with both CPU codes running on a 16-core Xeon workstation.

We propose a framework for periodic policy updates of computer controlled agents in an interactive scenario. We use the graphics processing unit (GPU) to accelerate an offline reinforcement learning algorithm which periodically updates an online agent's policy. The main contributions of this work are the use of GPU acceleration combined with a periodic update model to provide reinforcement learning in a performance constrained environment. We show empirically that given certain environment properties, the GPU accelerated implementation provides better performance than a traditional implementation utilizing the central processing unit (CPU). In addition, we show that while an online machine learning algorithm can function in some performance constrained environments, an offline algorithm reduces the performance constraints allowing for application to a wider variety of environments. Finally, we demonstrate combining these techniques to control an agent in the world of Quake III Arena, resulting in a computer controlled agent capable of adapting to different opponents.

As computing hardware moves to multi-core systems, future software needs to be parallelized in order to benefit from increasing computing resources. However, writing a correct parallel program is notoriously difficult, partly because of non-determinism in concurrent program executions. Because thread executions can be interleaved in many ways, a parallel program may produce a non-deterministic outcome even for identical program inputs if threads are not properly synchronized. Such a non-deterministic behavior, if not intentional, is often referred to as a concurrency bug. In this research, a solution is presented for efficient concurrency bug detection and mitigation. As data races are widely used as a way to identify potential concurrency bugs, this research presents an efficient hardware architecture, named RaceSMM, that enables run-time data race detection with high coverage (99%) and minimal performance overhead (4.8% on average). The proposed hardware mechanism is based on the happens-before vector clock algorithm, which is known for its accuracy yet considered to be expensive due to a large amount of meta-data. As the main optimization, the proposed architecture in this research decouples meta-data storage from regular caches so that expensive meta-data is only selectively stored for memory locations that are accessed by multiple threads within a relatively short period where most data races happen. While data races can detect a broad range of concurrency bugs where conflicting memory accesses are not controlled at all, recent studies show that many concurrency bugs are not detectable by data races. Hence, this research introduces a new heuristic for non-race concurrency bug detection, named ordersensitive critical sections, which extends the intuition in data races to capture non-race bugs in practice. The order-sensitive critical sections are defined as a pair of critical sections that can lead to non-deterministic shared memory state depending on the order in which they execute. This research presents a runtime algorithm, named OSCS, that uses the notion of order-sensitive critical sections to detect real-world concurrency bugs. Experiments show OSCS provides a good bug coverage (90%) for both non-race atomicity and ordering violations, with a small number of false positives. Additionally, OSCS can be supported in hardware efficiently while maintaining a high detection coverage (84%) and causing a negligible performance overhead. Finally, to provide a solution to further mitigate concurrency bugs post detection, an efficient deterministic replay scheme for multithreaded programs is introduced based on a concept of commutative critical sections. The commutative critical sections are critical sections in a multithreaded program that can be executed in any order while producing a consistent program output. In this research, we propose a deterministic replay scheme, named CommuteReplay, which allows the commutative critical sections to execute without enforcing an explicit deterministic order between the commutative critical sections to allow a noticeably better replay performance (reducing more than 20% of the overall performance overhead on average).

Shared-memory multi-threaded programming is inherently more difficult than single-threaded programming. The main source of complexity is that, the threads of an application can interleave in so many different ways. To ensure correctness, a programmer has to test all possible thread interleavings, which, however, is impractical. Many rare thread interleavings remain untested in production systems, and they are the major cause for a majority of concurrency bugs. Given that untested interleavings are the major cause of a majority of the concurrency bugs, this dissertation explores two possible ways to tackle concurrency bugs in this dissertation. One is to expose untested interleavings during testing to find concurrency bugs. The other is to avoid untested interleavings during production runs to tolerate concurrency bugs. The key is an efficient and effective way to encode and remember tested interleavings. This dissertation first discusses two hypotheses about concurrency bugs: the small scope hypothesis and the value independent hypothesis. Based on these two hypotheses, this dissertation defines a set of interleaving patterns, called interleaving idioms, which are used to encode tested interleavings. The empirical analysis shows that the idiom based interleaving encoding scheme is able to represent most of the concurrency bugs that are used in the study. Then, this dissertation discusses an open source testing tool called Maple. It memoizes tested interleavings and actively seeks to expose untested interleavings. The results show that Maple is able to expose concurrency bugs and expose interleavings faster than other conventional testing techniques. Finally, this dissertation discusses two parallel runtime system designs which seek to avoid untested interleavings during production runs to tolerate concurrency bugs. Avoiding untested interleavings significantly improve correctness because most of the concurrency bugs are caused by untested interleavings. Also, the performance overhead for disallowing untested interleavings is low as commonly occuring interleavings should have been tested in a well-tested program.

Abstract: Electromagnetic transient (EMT) simulation is widely utilized in power system planning and design. Respecting the detail and complexity of the components models, the electromagnetic transient program (EMTP) demands significant computational power. Increasing with the scale of the system, this requirement has become so prominent that parallel programming techniques are urgently needed in large-scale power system EMT simulation. Improving upon the multithreading parallelism, massive-threading computing is one of the key developments that can increase the EMT computational capabilities substantially when the processing unit has enough hardware cores. Compared to the traditional central processing unit (CPU), the graphic processing unit (GPU) has many more cores with distributed memory which can offer higher data throughput. This thesis describes the conception of the massive-threading parallel EMTP based on GPU for large-scale power systems using compute unified device architecture (CUDA). It defines a new fundamental program framework, relevant basic data structures and efficient data interfaces of the massive-threading parallel EMT simulator. The thesis proposes a series of massive-threading parallel modules for component models including unified linear passive elements module (ULPEM), universal line module (ULM) and universal machine module (UMM); and numerical methods, including Newton-Raphson iteration module (NRIM) and forward-backward substitution with LU factorization module (FBSLUM), used in the EMTP. Without the need for a trade-off between the system scale and the complexity of the component models, all parallel modules proposed above are detailed, universal and unified. In order to fully release the computing power of modern computer system, both data and instructions are based on 64-bit architecture, which guarantee the precision as well as extensibility of the program. The developed MT-EMTP program has been tested on various large-scale power systems of up to 2458 three-phase buses with detailed component modeling. The simulation results and execution times are compared with a mainstream commercial software, EMTPRV r, to show the improvement in performance with equivalent accuracy.

Multi-core, multi-processor, and Graphics Processing Unit (GPU) computer architectures pose significant challenges with respect to the efficient exploitation of parallelism for large-scale, scientific computing simulations. For example, a simulation of the human tonsil at the cellular level involves the computation of the motion and interaction of millions of cells over extended periods of time. Also, the simulation of Radiative Heat Transfer (RHT) effects by the Photon Monte Carlo (PMC) method is an extremely computationally demanding problem. The PMC method is example of the Monte Carlo simulation method—an approach extensively used in wide of application areas. Although the basic algorithmic framework of these Monte Carlo methods is simple, they can be extremely computationally intensive. Therefore, an efficient parallel realization of these simulations depends on a careful analysis of the nature these problems and the development of an appropriate software framework. The overarching goal of this dissertation is develop and understand what the appropriate parallel programming model should be to exploit these disparate architectures, both from the metric of efficiency, as well as from a software engineering perspective. In this dissertation we examine these issues through a performance study of PathSim2, a software framework for the simulation of large-scale biological systems, using two different parallel architectures’ distributed and shared memory. First, a message-passing implementation of a multiple germinal center simulation by PathSim2 is developed and analyzed for distributed memory architectures. Second, a germinal center simulation is implemented on shared memory architecture with two parallelization strategies based on Pthreads and OpenMP. Finally, we present work targeting a complete hybrid, parallel computing architecture. With this work we develop and analyze a software framework for generic Monte Carlo simulations implemented on multiple, distributed memory nodes consisting of a multi-core architecture with attached GPUs. This simulation framework is divided into two asynchronous parts: (a) a threaded, GPU-accelerated pseudo-random number generator (or producer), and (b) a multi-threaded Monte Carlo application (or consumer). The advantage of this approach is that this software framework can be directly used within any Monte Carlo application code, without requiring application-specific programming of the GPU. We examine this approach through a performance study of the simulation of RHT effects by the PMC method on a hybrid computing architecture. We present a theoretical analysis of our proposed approach, discuss methods to optimize performance based on this analysis, and compare this analysis to experimental results obtained from simulations run on two different hybrid, parallel computing architectures.

Parallel Discrete Event Simulation (PDES) is an active area of research for many years. Studies with PDES have focused primarily on either shared memory or distributed memory platforms. However, the emergence of low-cost multi-core and many-core processors suitable for use in Beowulf clusters provides an opportunity for PDES execution on a platform containing both shared memory and distributed memory parallelism. This thesis explores the migration of an existing PDES simulation kernel called WARPED to a Beowulf Cluster of many-core processors. More precisely, WARPED is an optimistically synchronized PDES simulation kernel that implements the Time Warp paradigm. It was originally designed for efficient executionon single-core Beowulf Clusters. The work of this thesis extends the WARPED kernel to contain parallelthreaded execution on each node as well as parallelism between the nodes of the cluster. The new versionof warped will be called threaded WARPED.In this thesis, warped is redesigned with thread safe data structure protected by various constructs. In particular atomic instructions are used to deploy lock-free data-structures and synchronization. With the addition of thread to WARPED the work also required adjustments and extensions to several of the subalgorithms of Time Warp. In particular, adjustments to the algorithm for computing Global Virtual Time (GVT), and termination detection were required. This thesis explains the modifications made to implement threaded WARPED and evaluates the performance capabilities of the two solutions for managing the shared data structures.

Parallel and concurrent software sometimes exhibit incorrect behavior because ofunintended interference between different threads of execution. Common classesof concurrency bugs include data races, deadlocks, and atomicity violations.These bugs are often non-deterministic and hard to find without sophisticatedtools. We present Active Testing, a methodology to effectively find concurrencybugs that scales to large distributed memory parallel systems.Active Testing combines the coverage and predictive power of program analysiswith the familiarity of testing. It works in two phases: in the predictiveanalysis phase, a program is executed and monitored for potential concurrencybugs and in the testing phase, Active Testing re-executes the program whilecontrolling the thread schedules in an attempt to reproduce the bug predicted inthe first phase. We have implemented Active Testing for multi-threaded Java programs in theCalFuzzer framework. We have also developed UPC-Thrille, an Active Testing frameworkfor Unified Parallel C (UPC) programs written in the Single Program MultipleData (SPMD) programming model combined with the Partitioned Global Address Space(PGAS) memory model. We explain in detail the design decisions and optimizationsthat were necessary to scale Active Testing to thousands of cores. We presentextensions to UPC-Thrille that support hybrid memory models as well. We evaluate the effectiveness of Active Testing by running our tools on severalJava and UPC benchmarks, showing that it can predict and confirm realconcurrency bugs with low overhead. We demonstrate the scalability of ActiveTesting by running benchmarks with UPC-Thrille on large clusters with thousandsof cores.

As parallel systems become ubiquitous, exploiting parallelism becomes crucial for improving application performance. However, the complexities of developing parallel software are major challenges. Shared memory parallel programming models, such as OpenMP and Thread Building Blocks (TBBs), offer a single view of the memory thereby making parallel programming easier. However, theysupport limited forms of parallelism. Distributed memory programming models,such as the Message Passing Interface (MPI), support more parallelism types; however, their low level interfaces require great deal of programming effort.This dissertation presents the SpiceC system that simplifies the task of parallel programming while supporting different forms of parallelism and parallel computing platforms. SpiceC provides easy to use directives to express different forms of parallelism, including DOALL, DOACROSS, and pipelining parallelism. SpiceC is based upon an intuitive computation model in which each thread performs its computation in isolation from other threads using its private space and communicates with other threads via the shared space. Since, all data transfers between shared and private spaces are explicit, SpiceC naturally supports both shared and distributed memory platforms with ease. SpiceC is designed to handle the complexities of real world applications.The effectiveness of SpiceC is demonstrated both in terms of delivered performance and the ease of parallelization for applications with the following characteristics.Applications that cannot be statically parallelized due to presence of dependences, often contain large amounts of input dependent and dynamic data level parallelism. SpiceC supports speculative parallelizationfor exploiting dynamic parallelism with minimal programming effort. Applications that operate on large data sets often make extensive use of pointer-based dynamic data structures. SpiceC provides support for partitioning dynamic data structures across threads and then distributing the computation among the threads in a partition sensitive fashion. Finally, due to large input sizes, many applications repeatedly performI/O operations that are interspersed with the computation. While traditionalapproach is to execute loops contain I/O operations serially, SpiceC introduces support for parallelizing computations in the presence of I/O operations. Finally, this dissertation demonstrates that SpiceC can handle the challengesposed by the memory architectures of modern parallel computing platforms.The memory architecture impacts the manner in which data transfers betweenprivate and shared spaces are implemented. SpiceC does not place thethe burden of data transfers on the programmer. Therefore portability of SpiceCto different platforms is achieved by simply modifying the handling of data transfers by the SpiceC compiler and runtime. First, it is shown how SpiceC can be targeted to shared memory architectures both with and without hardware support for cache coherence. Next it is shown how accelerators such as GPUs present in heterogeneous systems are exploited by SpiceC. Finally, the ability of SpiceC to exploit the scalability of a distributed-memory system, consisting of a cluster of multicore machines, is demonstrated.

Computer vision research enables machines to understand the world. Humans usually interpret and analyze the world through what they see - the objects they capture with their eyes. Similarly, machines can better understand the world by recognizing objects in images. Object recognition is therefore a major branch of computer vision. To achieve the highest accuracy, state-of-the-art object recognition systems must extract features from hundreds to millions of images, train models with enormous data samples, and deploy those models on query images. As a result, these systems are computationally-intensive. In order to make such complicated algorithms practical to apply in real life, we must accelerate them on modern massively-parallel platforms. However, parallel programming is complicated and challenging, and takes years to master. In order to help object recognition researchers employ parallel platforms more productively, we propose a parallel application library for object recognition. Researchers can simply call the library functions, and need not understand the technical details of parallelization and optimization. To pave the way for such a library, we perform pattern mining on 31 important object recognition systems, and conclude that 15 application patterns are necessary to cover the computations in these systems. In other words, if we support these 15 application patterns in our library, we can parallelize all 31 object recognition systems. In order to optimize any given application pattern in a systematic way, we propose using patterns and software architectures to explore the design space of algorithms, parallelization strategies, and platform parameters.In this dissertation, we exhaustively examine the design space for three application patterns, and achieve significant speedups on these patterns - 280x speedup on the eigensolver application pattern, 12-33x speedup on the breadth-first-search graph traversal application pattern, and 5-30x speedup on the contour histogram application pattern. To improve the portability and flexibility of the proposed library, we also initiate the OpenCL for OpenCV project. This project aims to provide a collection of autotuners that optimize the performance of application patterns on many different parallel platforms. We have developed two autotuners in this project. clSpMV is an autotuner for sparse matrix vector multiplication (SpMV) computation - it tunes the representation of a sparse matrix and the corresponding SpMV kernel, and is 40% faster than the vendor-optimized parallel implementation. clPaDi is an autotuner for the pair-wise distance computation application pattern - it allows users to customize their own distance functions, and finds the best blocking size for each function. clPaDi performs 320-650 giga floating point operations per second on modern GPU platforms. By employing these optimized functions in a state-of-the-art object recognition system, we have achieved 110-120x speedup compared to the original serial implementation. Now it takes only three seconds to identify objects in a query image - a much more practical and useful processing time. Our research makes it possible to deploy complicated object recognition algorithms in real applications.With these encouraging results, we are confident that the methodology we illustrate in this dissertation is applicable to optimizing all application patterns. If we expand the parallel application library to support all 15 application patterns, the library will be a key toolkit for both existing and future object recognition systems.

Abstract: Cloud computing has emerged as a popular mechanism for deploying services and running applications. A key feature of many cloud environments is the use of virtual machines (VMs) as the unit of resource allocation. Multiple virtual machines running the same application may be co-located on a single physical host, by either chance or design, in which case we can share memory between them, providing fast inter-process communication to applications. It is desirable to use inter-VM shared memory at the framework and service level, providing its advantages to applications transparently. We present two use cases for inter-VM shared memory. Elastic Phoenix, a MapReduce framework allowing for malleable jobs, demonstrates how inter-VM shared memory allows the easy addition of features to existing frameworks, making them more suitable for cloud computing. Nahanni Memcached, a caching server for web applications, demonstrates how existing services can use inter-VM shared memory to improve performance.

Many scientific problems found in the real world are so large and massively parallel that they cannot be solved efficiently on a single computer with limited memory capacity. The great computational cost of such a large problem often necessitates efficient use of computing resources by means of employing parallel programming models. Current trends in computer architecture, software applications, and networking suggest a future in which parallelism will be as important as portability for algorithms and software. In this future, an algorithm able to execute only on a single process will be computationally more expensive than a parallel algorithm capable of achieving the same/better performance on multiple processes. In recent years the standardization of programming languages has enhanced code portability to computers of various architectures. But, it is still the case that actual code implementation can differ in a number of details on different platforms, often to the extent that significant code modifications have to be made in order to effect code portability. This thesis presents the physical, computational, and pragmatic aspects of the development and application of explicitly-parallel, architecture-neutral, and platform-independent HPJava scientific software applications, JAVART (JAva Versatile Atmospheric Remote-sensing Tools), in the Object-Oriented canonical SPMD Programming Style, which are aimed at solving some common problems that can arise in atmospheric remote sensing applications beyond the basic RTM formulation. Software tools in the JAVART collection consist of over 54 class objects. The length of the source code exceeds 30,000 lines. JAVART is developed, with the aim of implementing modern programming paradigms, in the hope that they can enhance the adaptability of a typical RT solving technique to a problem beyond the basic RTM formulation. The intent is not only to help to develop a better understanding of the radiative process in the Earth-atmosphere system through developing realistic computer simulation but also to lay the foundation for others to do more work by means of providing a well-documented open-source code base that others can easily build on. This thesis is intended to be used as not just the user's guide which suggests a number of ways to run applications but also supplementary material which is helpful for understanding the underlying science.

GPUs have been gaining popularity as general purpose parallel processors that deliver a performance to cost ratio superior to that of CPUs. However, programming on GPUs has remained a specialised area, as it often requires significant knowledge about the GPU architecture and platform-specific parallelisation of the algorithms that are implemented. Furthermore, the dominant programming models on GPUs limit functional decomposition of programs, as they require programmers to write separate functions to run on GPUs. I present and quantitatively evaluate a GPU programming system that provides a high-level abstraction to facilitate the use of GPUs for general purpose array processing. The presented programming system liberates programmers of low-level details and enables functional decomposition of programs, whilst providing the facilities to sufficiently exploit the parallel processing capability of GPUs. Fundamentally, the presented programming system allows programmers to focus on what to program on GPUs instead of how to program GPUs. The approach is based on algorithmic skeletons mapped to higher-order functions, which are commonly available in functional programming languages. The presented programming system (1) encapsulates the low-level control of GPUs and the GPU-specific parallelisation of the higher-order functions in algorithmic skeletons, (2) employs an embedded domain specific language as the interface that treats the parallel operations as expressions with parallel semantics, allowing functional decomposition of programs, and (3) manages the compilation of the embedded domain specific language into algorithmic skeleton instances and the execution of the algorithmic skeleton instances online. Programmers only need to write the operations to be executed on GPUs as expressions in the embedded domain specific language, and the presented programming system takes care of the rest. Although the concrete implementation presented in the thesis involves an embedded domain specific language in Haskell, Accelerate, and a specific GPU platform, CUDA, the approach in this thesis can be applied to other similar configurations with appropriate adjustments.

Contemporary parallel microprocessors exploit Chip Multiprocessing along with Single Instruction, Multiple Data parallelism to deliver high performance on applications that expose substantial fine-grained data parallelism. Although data parallelism is widely available in many computations, implementing data parallel algorithms in low-level efficiency languages such as C++ is often a difficult task, since the programmer is burdened with mapping data parallelism from an application onto the hardware structures designed to execute it. Languages specifically designed for data parallelism, such as NESL, aim to improve programmer productivity by allowing the programmer to express computation as a composition of data parallel primitives, such as map, reduce and scan. However, efficiently compiling nested data parallel computations to contemporary parallel microprocessors is challenging.Additionally, the rise of productivity languages, such as Ruby and Python, has facilitated the construction of domain-specific embedded languages. These embedded languages employ familiar syntactic constructs, which eases the task of learning a new programming environment, while also retaining the full capabilities of the host language. This work capitalizes on the productivity of domain-specific embedded languages as well as the nested data parallel abstraction to create a programming environment that is both productive and efficient on contemporary parallel microprocessors. We describe Copperhead, a high-level data parallel language embedded in Python. The Copperhead programmer writes parallel computations via composition of familiar data parallel primitives supporting both flat and nested data parallel computation on arrays of data. Copperhead programs are expressed in a subset of the widely used Python programming language and interoperate with standard Python modules, including libraries for numeric computation, data visualization, and analysis.Compiling data parallel computations requires analyses and transformations to schedule data parallel operations onto a target platform. We discuss the language, compiler, and runtime features that enable Copperhead to efficiently do so. We define the restricted subset of Python that Copperhead supports and introduce the program analysis techniques and transformations necessary for compiling Copperhead code into efficient low-level implementations. We demonstrate that indiscriminate use of the flattening or vectorization transform, common to data parallel compilers, is inefficient on contemporary microprocessors, and we advocate a more direct mapping of nested data parallel operations onto the natural parallelism hierarchy provided by today's parallel platforms. We show how this direct mapping allows a data parallel compiler to capitalize on hierarchical on-chip memory structures, as well as perform data parallel primitive fusion in order to gain efficiency. We outline the runtime support that allows Copperhead programs to efficiently interoperate with standard Python modules. We demonstrate the effectiveness of our techniques with several examples targeting the CUDA platform for parallel programming on graphics processors. Copperhead code is concise, on average requiring 3.6 times fewer lines of code than CUDA, and the compiler generates efficient low-level implementations, yielding 45-100% of the performance of hand-crafted, well optimized CUDA code. Copperhead provides an efficient and productive way to program parallel microprocessors.

We are now seeing diminishing returns from classic single-core processor designs, yet the number of transistors available for a processor is still increasing. Processor architects are therefore experimenting with a variety of multicore processor designs. Heterogeneous multicore processors with Explicitly Managed Memory (EMM) hierarchies are one such experimental design which has the potential for high performance, but at the cost of great programmer effort. EMM processors have cores that are divorced from the normal memory hierarchy, thus the onus is on the programmer to manage locality and parallelism. This dissertation presents the Cellgen source-to-source compiler which moves some of this complexity back into the compiler. Cellgen offers a directive-based programming model with semantics similar to OpenMP for the Cell Broadband Engine, a general-purpose processor with EMM. The compiler implicitly handles locality and parallelism, schedules memory transfers for data parallel regions of code, and provides performance predictions which can be leveraged to make scheduling decisions. We compare this approach to using a software cache, to a different programming model which is task based with explicit data transfers, and to programming the Cell directly using the native SDK. We also present a case study which uses the Cellgen compiler in a comparison across multiple kinds of multicore architectures: heterogeneous, homogeneous and radically data-parallel graphics processors.

Often times, scientific software needs to be adapted for different execution environments, problem sets, and available resources to ensure its efficiency and reliability. Directly modifying source code to implement adaptation is time-consuming, error-prone, and difficult to manage for today's complex software. This thesis studies modular approaches to implementing program adaptation with existing scientific codes, whereby application-specific adaptation strategies can be implemented in separate code which is then transparently combined with a given program. By using the approaches developed in this thesis, scientific programmers can focus on the design and implementation of adaptation schemes, manage an adaptation code separately from the main program components, and compose an adaptive application whose original capabilities are enhanced in diverse aspects such as application performance and stability. The primary objective of the modular approaches in this study is to provide a language-independent development method of adapting existing scientific software, so that applications written in different languages can be supported when implementing adaptation schemes. In particular, the emphasis is on Fortran, which has been a mainstream language for programming scientific applications. Three research questions are formulated in this thesis, each of which aims to: design and implement high-level abstractions for expressing adaptation strategies, develop a dynamic tuning approach for parallel programs, and support flexible runtime adaptation schemes, respectively. The applicability of the proposed approaches is demonstrated through example applications to real-world scientific software.

We take a novel perspective on real-life decision making problems involving binary activity-selection decisions that compete for scarce resources. The current literature in operations research approaches these problems by forming an optimal portfolio of activities that meets the specified resource constraints. However, often practitioners in industry and government do not take the optimal-portfolio approach. Instead, they form a rank-ordered list of activities and select those that have the highest priority. The academic literature tends to discredit such ranking schemes because they ignore dependencies among the activities. Practitioners, on the other hand, sometimes discredit the optimal-portfolio approach because if the problem parameters change, the set of activities that was once optimal no longer remains optimal. Even worse, the new optimal set of activities may exclude some of the previously optimal activities, which they may have already selected. Our approach takes both viewpoints into account. We rank activities considering both the uncertainty in the problem parameters and the optimal portfolio that will be obtained once the uncertainty is revealed. We use stochastic integer programming as a modeling framework. We develop several mathematical formulations and discuss their relative merits, comparing them theoretically and computationally. We also develop cutting planes for these formulations to improve computation times. To be able to handle larger real-life problem instances, we develop parallel branch-and-price algorithms for a capital budgeting application. Specifically, we construct a column-based reformulation, develop two branching strategies and a tabu search-based primal heuristic, propose two parallelization schemes, and compare these schemes on parallel computing environments using commercial and open-source software. We give applications of prioritization in facility location and capital budgeting problems. In the latter application, we rank maintenance and capital-improvement projects at the South Texas Project Nuclear Operating Company, a two-unit nuclear power plant in Wadsworth, Texas. We compare our approach with several ad hoc ranking schemes similar to those used in practice.

Transactional Memory(TM) is an optimistic speculative synchronization scheme that provides atomic execution for a region of code marked as a transaction by the programmer. Programs with critical sections that are not heavily contended benefit from the optimistic nature of TM systems. However, for heavily contended critical sections, performance for TM systems can degrade due to conflicts leading to stalls and expensive rollbacks. In this thesis, we investigate methods to improve scalability of TM systems using early value communication (EVC) and understand its mechanisms and hardware complexity. We look into the nature of the shared data involved in conflicts for TM systems and find that most transactions have conflicts around a few shared addresses and shared-conflicting data is often updated in a predictable manner by different transactions. We propose using a memory-level value predictor (VP-TM) to capture this predictability for such data structures and increase overall concurrency by satisfying loads from conflicting transactions with predicted values, instead of stalling. We present one possible design and implementation of TM system with a value predictor. Our benchmark results show us that the value predictor can capture this predictable behavior for most benchmarks and can improve performance of TM programs by improving concurrency and minimizing stalls and rollbacks due to conflicts. To reduce the hardware complexity, we present another design that can provide performance from EVC without the extra hardware costs. Finally, we present a realistic design of the VP-TM system that shows the full impact of the extra hardware and messages and gives us a better idea of performance with VP-TM. Our goal is to increase the adoption of TM for parallel programming by extending the number of applications that can benefit from TM.

Manycore microprocessors are powerful computing engines that are architected to embrace the use of parallelism to extract computational throughput from the continued improvements in the semiconductor manufacturing process. Yet the performance of the software applications running on these microprocessors is highly sensitive to factors such as data layout, data placement, and synchronization. These factors are not usually part of an application domain experts daily concerns, as they look to utilize the powerful compute capabilities of manycore microprocessors for their applications, but failure to carefully address these concerns could mean an order of magnitude of loss in application execution latency and/or throughput. With the proliferation of manycore microprocessors from servers to laptops and portable devices, there is increasing demand for the productive development of computationally efficient business and consumer applications in a wide range of usage scenarios. The sensitivity of execution speed to software architecture and programming techniques can impede the adoption of the manycore microprocessors and slow the momentum of the semiconductor industry.This thesis discusses how we can empower application domain experts with pattern- oriented application frameworks, which can allow them to effectively utilize the capabilities of highly parallel manycore microprocessors and productively develop efficient parallel software applications. Our pattern-oriented application framework includes an application context for outlining application characteristics, a software architecture for describing the application concurrency exploited in the framework, a reference implementation as a sample design, and a set of extension points for flexible customization.We studied the process of accelerating applications in the fields of machine learning and computational finance, specifically looking at automatic speech recognition (ASR), financial market value-at-risk estimation (VaR), and financial potential future exposure (PFE). We present a pattern-oriented application framework for ASR, as well as efficient reference implementations of VaR and PFE. For the ASR framework, we demonstrate its construction and two separate deployments, one of which flexibly extends the ASR framework to enable lip-reading in high-noise recognition environments. The framework enabled a Matlab/Java programmer to effectively utilize a manycore microprocessor to achieve a 20x speedup in recognition throughput as compared to a sequential CPU implementation.Our pattern-oriented application framework provides an approach for crystallizing and transferring the often-tacit knowledge of effective parallel programming techniques while allowing for flexible adaptation to various application usage scenarios. We believe that the pattern-oriented application framework will be an essential tool for the effective utilization of manycore microprocessors for application domain experts.

The field of computer vision has become an important part of today's society, supporting crucial applications in the medical, manufacturing, military intelligence and surveillance domains. Many computer vision tasks can be divided into fundamental steps: image acquisition, pre-processing, feature extraction, detection or segmentation, and high-level processing. This work focuses on classification and object detection, specifically k-Nearest Neighbors, Support Vector Machine classification, and Viola & Jones object detection. Object detection and classification algorithms are computationally intensive, which makes it difficult to perform classification tasks in real-time. This thesis aims in overcoming the processing limitations of the above classification algorithms by offloading computation to the graphics processing unit (GPU) using NVIDIA's Compute Unified Device Architecture (CUDA). The primary focus of this work is the implementation of the Viola and Jones object detector in CUDA. A multi-GPU implementation provides a speedup ranging from 1x to 6.5x over optimized OpenCV code for image sizes of 300 x 300 pixels up to 2900 x 1600 pixels while having comparable detection results. The second part of this thesis is the implementation of a multi-GPU multi-class SVM classifier. The classifier had the same accuracy as an identical implementation using LIBSVM with a speedup ranging from 89x to 263x on the tested datasets. The final part of this thesis was the extension of a previous CUDA k-Nearest Neighbor implementation by exploiting additional levels of parallelism. These extensions provided a speedup of 1.24x and 2.35x over the previous CUDA implementation. As an end result of this work, a library of these three CUDA classifiers has been compiled for use by future researchers.

Functional parallel programming techniques for feed-forward artificial neural networks trained using backpropagation learning are analyzed. In particular, the Data Parallel Haskell extension to the Glasgow Haskell Compiler is considered as a tool for achieving data parallelism. We find much potential and elegance in this method, and determine that a sufficiently large workload is critical in achieving real gains. Several additional features are recommended to increase usability and improve results on small datasets.

In this thesis, we present a versatile parallel programming model composed of an individual general-purpose processor aided by several application-specific coprocessors. These computing units operate under a simplification of the master-worker model. The user-defined coprocessors may be either homogeneous or heterogeneous. We analyze system performance with regard to system size and task granularity, and we present experimental results to determine the optimal operating conditions. Finally, we consider the suitability of this approach for scientific simulations — specifically for use in agent-based models of biological systems.