Search

Graphic Processing Units (GPUs) have become popular in the last decade due to their high memory bandwidth and powerful computing capacity. Nevertheless, achieving high-performance on GPUs is not trivial. It generally requires significant programming expertise and understanding of details of low-level execution mechanisms in GPUs. This dissertation introduces approaches for optimizing regular and irregular applications. To optimize regular applications, it introduces a novel approach to GPU kernel optimization by identifying and alleviating bottleneck resources. This approach, however, is not effective in irregular applications because of data-dependent branches and memory accesses. Hence, tailored approaches are developed for two popular domains of irregular applications: graph algorithms and sparse matrix primitives. Performance modeling for GPUs is carried out by abstract kernel emulation along with latency/gap modeling of resources. Sensitivity analysis with respect to resource latency/gap parameters is used to predict the bottleneck resource for a given kernel's execution. The utility of the bottleneck analysis is demonstrated in two contexts: i) Enhancing the OpenTuner auto-tuner with the new bottleneck-driven optimization strategy. Effectiveness is demonstrated by experimental results on all kernels from the Rodinia suite and GPU tensor contraction kernels from the NWChem computational chemistry suite. ii) Manual code optimization. Two case studies illustrate the use of a bottleneck analysis to iteratively improve the performance of code from state-of-the-art DSL code generators. However, the above approach is ineffective for irregular applications such as graph algorithms and sparse linear systems. Graph algorithms are used in various applications, and high-level GPU graph processing frameworks are an attractive alternative for achieving both high productivity and high-performance. This dissertation develops an approach to graph processing on GPUs that seeks to overcome some of the performance limitations of existing frameworks. It uses multiple data representations and execution strategies for dense- versus sparse vertex frontiers, dependent on the fraction of active graph vertices. Experimental results demonstrate performance improvement over current state-of-the-art GPU graph processing frameworks for many benchmark programs and data sets. Sparse matrix primitves such as sparse matrix vector multiplication (SpMV), sparse matrix multi-vector multiplication (SpMM), and Sampled Dense-dense matrix multiplication (SDDMM), are key kernels for scientific computing as well as data science and machine learning. A large number of recent research studies have focused on various GPU implementations of the SpMV kernel. But SpMM and SDDMM kernels have received much less attention. This dissertation presents in-depth analyses to contrast SpMV and SpMM, and develops new sparse-matrix representations and computation approaches suited to achieving high data-movement efficiency and effective GPU parallelization of SpMM. It also introduces a novel tiling approach for high-performance implementations for SpMM and SDDMM with the standard sparse matrix representation -- Compressed Sparse Row (CSR). Experimental evaluation demonstrates performance improvement over existing implementations. In short, this dissertation contributes to enhancing compiler technology to achieve high-performance on GPUs by mainly considering data locality and concurrency.

Model-based design based on the Simulink modeling formalism and the associated toolchain has gained its popularity in the development of complex embedded control systems. However,the current research on software synthesis for Simulink models has a critical gap for providing a deterministic, semantics-preserving implementation on multicore architectures with partitioned fixed-priority scheduling. In this thesis, we propose to judiciously assign task offset, task priority, and task communication mechanism, to avoid simultaneous access to shared memory by tasks on different cores, to preserve the model semantics, and to optimize the control performance. We develop two approaches to solve the problem: (a) a mixed integer linear programming (MILP) formulation; and (b) a problem specific exact algorithm that may run several magnitudes faster than MILP.

Designing chip multiprocessors (CMPs) that scale to more than a handful of cores is an important goal for the upcoming technology generations. A challenge to scalability is the fact that these cores will inevitably share hardware resources, whether it be on-chip storage, memory bandwidth, the chip’s power budget, etc. Efficiently allocating those shared resources across cores is critical to optimize CMP executions. Techniques proposed in the literature often rely on global, centralized mechanisms that seek to maximize system throughput. Global optimization may hurt scalability: as more cores are integrated on a die, the search space grows exponentially, making it harder to achieve optimal or even acceptable operating points at run-time without incurring significant overheads. In this thesis, we present XChange, a framework for scalable resource allocation in large-scale CMPs. Inspired by market mechanisms, which are widely used in real life to allocate social resources at scale, we propose to address the resource allocation problem in large-scale CMPs as a purely dynamic, largely distributed market framework. Each shared resource is assigned a virtual price, which changes over time to reflect its supply-demand relationship. Cores in the CMP act as market players: they seek to maximize their own utilities by bidding for shared resources within their budgets. Because each core works largely independently, the resource allocation becomes a scalable, mostly distributed decision-making process. Cores in the system are able to dynamically monitor and learn their own resource-performance relationship and bid accordingly—no prior knowledge of the workload characteristics is assumed. We show our market-based resource allocation mechanism delivers superior system efficiency and fairness against existing proposals. This approach is purely empirical, however, and thus it does not provide any guarantees on the loss of efficiency and fairness. It is well known, for example, that market mechanisms in equilibrium can sometimes be highly inefficient—this is known as Tragedy of Commons. Therefore, we study the theoretic properties of our market-based approach, and establish a bound on the loss of efficiency and fairness in the market-based resource allocation, by introducing two new metrics, market utility range (MUR) and market budget range (MBR). Further, guided by such theoretic foundations, we propose ReBudget, a budget re-assignment technique that is able to systematically trade off efficiency and fairness in an adjustable manner. In the process of formulating our XChange framework, we propose novel mechanisms to support fine-grain resource management. Specifically, we propose SWAP, a scalable and fine-grain cache management technique that seamlessly combines set and way partitioning. By cooperatively managing cache ways and sets, SWAP (“Set and WAy Partitioning”) can successfully provide hundreds of fine-grained cache partitions for the manycore era. We implement SWAP as a user-space management thread on Cavium’s ThunderX, a real server-grade 48-core processor, and we show that SWAP significantly improves system throughput by twice as much speedup as what we can obtain by using only ThunderX’s way partitioning mechanism. This was a collaboration with Cavium engineers.

Power and thermal limitations have forced the processor industry to pursue the path of designing multi-core processors. Currently, multi-core processors have become ubiquitous in mainstream computing. Recently, the embedded world, where energy efficiency is considered paramount, has also embraced the multi-core revolution. Hence, while designing software for future multi-core processors, one has to now consider energy efficiency as a highly critical factor compared to previous generations. To derive performance from parallel hardware, parallel programs are needed for these architectures. Within parallel programs, there is a need for synchronization between threads when these threads modify shared data. Unfortunately, synchronization is also one of the main factors affecting the energy efficiency and performance of a parallel program.To address this problem, there is a need to develop novel methods for improving the energy efficiency of multi-core synchronization. Specifically, this dissertation focuses on (1) exploring the feasibility of employing prominent energy saving techniques such as Dynamic Voltage and Frequency Scaling (DVFS) to synchronization primitives such as Spinlocks to save energy and (2) to analyze the energy efficiency of prominent scalable and fair multi-processor synchronization algorithms on modern multi-core processors. The experimental results have shown that employing the DVFS technique to Spinlocks could save a considerable amount of energy. The energy efficiency analysis of prominent scalable and fair locks, such as Backoff lock and Ticket lock respectively, show that non-scalable locks consume more energy than scalable counterparts. Nevertheless, new energy efficient versions of Backoff lock and Ticket lock are proposed and their energy efficiencies are evaluated.

Prediction of the performance of parallel applications is a concept useful in several domains of software operation. In the commercial world, it’s often useful to be able to anticipate how an application will perform on a customer’s machine with a minimal burden to the user. In the same spirit, it’s in the best interest of a user/consumer of computational software to most optimally operate it. In the super-computing/distributed computing world, being able to anticipate the performance of an application on a set of compute-nodes allows one to more optimally select the set of nodes to execute on. In terms of a large-scale shared computing environment where parallel computational jobs are assigned resources and scheduled for execution, being able to optimally do so can improve overall throughput by decreasing contention. In all cases, being able to anticipate the ideal degree of parallelism to invoke during execution (and have reasonable expectations for what can be acheived) will lead to more optimal use of all resources involved. For any of this to be possible, a good model (or models) are required which can not only capture an application’s performance on one machine but also predict its behavior on another.Here, we present a large family of performance models composed of discrete parts, all as combinatoric variations on Amdahl’s Law. We establish a protocol involving thorough benchmarking of the application on a known system. A protocol is established for the collection of meaningful machine architecture and performance information for the known and target machines. With the resulting high quality models and a single execution of the application on the target system we are able to closely predict its parallel behavior. We propose that computation applications that are in need of this kind of treatment are sufficiently sophisticated and, especially in the case of commercial applications, are most likely black boxes and therefore avoid any need to analyze our applications in any static manner and expressly rely on parallel runtimes of individual executions. The protocols and methods can be implemented by any skilled developer on conceivably any parallel platform without the need of specialized API’s, hardware diagnostic support, or any manner of reverse engineering of the applications of interest.

The multicore era has initiated a move to ubiquitous parallelization of software. In the process, cores have scaled out but the memory subsystem resources have not kept up. Memory subsystem contention within and between applications makes it challenging to extract performance scaling that matches the increase in the number of cores. This dissertation explores the diagnosis of memory subsystem contention, identifies associated performance and energy efficiency opportunities, and suggests techniques and optimizations to both precisely measure and reduce the contention. The dissertation begins by exploring contention within a single and between multiple, large-scale, distributed scientific applications and moves to exploring the impact of memory subsystem contention on graphics processing units, accelerators that are seeing increasing usage in both commercial data centers and scientific clusters. The findings of the studies demonstrate that memory subsystem contention is a serious impediment to achieving high performance and energy efficiency but also that relatively simple techniques that control job placement, resource sharing, tuning of parallelism, and algorithmic optimizations at the application level provide significant opportunities to improve performance and energy efficiency.The dissertation comprises four distinct works. (1) It begins by quantifying the performance and energy efficiency opportunities afforded by co-scheduling large-scale distributed scientific applications within a supercomputer. (2) From there, it studies the design of a prototype system for dynamically quantifying inter-application interference between co-located supercomputer jobs and uses those estimates to reform the accounting system to more fairly reflect end-user utility. (3) Next, it explores performance and energy scaling of analytic database workloads on graphics processors and finds that disabling whole compute units can reduce query execution time and reduce energy by throttling back the number of threads at any instant that contend for shared hardware resources. (4) The dissertation ends by describing the Horton table, a hash table that accelerates in-memory data-intensive computing by more efficiently using hardware cache and memory bandwidth.

On the software side, managed languages and their workloads are ubiquitous, executing on mobile, desktop, and server hardware. Managed languages boost the productivity of programmers by abstracting away the hardware using virtual machine technology. On the hardware side, modern hardware increasingly exploits parallelism to boost energy efficiency and performance with homogeneous cores, heterogenous cores, graphics processing units (GPUs), and vector instructions. Two major forms of parallelism are: task parallelism on different cores and vector instructions for data parallelism. With task parallelism, the hardware allows simultaneous execution of multiple instruction pipelines through multiple cores. With data parallelism, one core can perform the same instruction on multiple pieces of data. Furthermore, we expect hardware parallelism to continue to evolve and provide more heterogeneity. Existing programming language runtimes must continuously evolve so programmers and their workloads may efficiently utilize this evolving hardware for better performance and energy efficiency. However, efficiently exploiting hardware parallelism is at odds with programmer productivity, which seeks to abstract hardware details. My thesis is that managed language systems should and can abstract hardware parallelism with modest to no burden on developers to achieve high performance, energy efficiency, and portability on ever evolving parallel hardware. In particular, this thesis explores how the runtime can optimize and abstract heterogenous parallel hardware and how the compiler can exploit data parallelism with new high-level languages abstractions with a minimal burden on developers. We explore solutions from multiple levels of abstraction for different types of hardware parallelism. (1) For asymmetric multicore processors (AMP) which have been recently introduced, we design and implement an application scheduler in the Java virtual machine (JVM) that requires no changes to existing Java applications. The scheduler uses feedback from dynamic analyses that automatically identify critical threads and classifies application parallelism. Our scheduler automatically accelerates critical threads, honors thread priorities, considers core availability and thread sensitivity, and load balances scalable parallel threads on big and small cores to improve the average performance by 20% and energy efficiency by 9% on frequency-scaled AMP hardware for scalable, non-scalable, and sequential workloads over prior research and existing schedulers. (2) To exploit vector instructions, we design SIMD.js, a portable single instruction multiple data (SIMD) language extension for JavaScript (JS), and implement its compiler support that together add fine-grain data parallelism to JS. Our design principles seek portability, scalable performance across various SIMD hardware implementations, performance neutral without SIMD hardware, and compiler simplicity to ease vendor adoption on multiple browsers. We introduce type speculation, compiler optimizations, and code generation that convert high-level JS SIMD operations into minimal numbers of SIMD native instructions. Finally, to accomplish wide adoption of our portable SIMD language extension, we explore, analyze, and discuss the trade-offs of four different approaches that provide the functionality of SIMD.js when vector instructions are not supported by the hardware. SIMD.js delivers an average performance improvement of 3.3× on micro benchmarks and key graphic algorithms on various hardware platforms, browsers, and operating systems. These language extension and compiler technologies are in the final approval process to be included in the JavaScript standards. This thesis shows using virtual machine technologies protects programmers from the underlying details of hardware parallelism, achieves portability, and improves performance and energy efficiency.

The terms dual-core and quad-core have become ubiquitous for modern computer processors. Where processors previously had a single powerful processing core, they now have multiple lower power processing cores. While some applications can readily be adapted to this change in computer architecture, a large class of applications dealing with unstructured data poses significant challenges to achieving performance on these new architectures. In this thesis we propose new algorithms and methods for the problems of graph partitioning, fill reducing ordering, and graph clustering on multicore architectures. These problems are used for the discovery and introduction of structure into this data. This is important in the fields of scientific and parallel computing, data sciences, life sciences, and integrated circuit design. Our new methods for graph partitioning exploit current multicore architectures to greatly reduce both runtime and memory requirements. Our methods rely on a model of coarse grained parallelism while effectively maximizing data locality. We develop new methods for each phase of multilevel graph partitioning including a new aggregation method, an adaptive parallel formulation of initial partitioning, a high speed method for performing greedy refinement, and a new method for high quality refinement which is highly scalable. These new algorithms result in 3x lower runtimes than previous methods, while matching them in terms of quality using the greedy refinement method. Our new high quality and highly scalable refinement method improves the solution quality by 8%. We develop new methods for generating fill reducing orderings of sparse matrices. This includes a new method of vertex separator refinement which manages to achieve effective parallelization while still matching the quality of the best serial algorithms. We introduce a task scheduling method specifically for nested dissection and show that it results in significantly better performance over the task schedulers available in current threading libraries. Overall, our algorithms for nested dissection are 1.5x faster than existing parallel methods and reduce the fill-in by 3.7% and operation count by 14% of Cholesky factorization compared to the orderings produced by other parallel methods. This matches the quality of orderings generated by serial methods while achieving a 10.1x speedup on 16 cores. Finally, we develop new serial and parallel algorithms for the graph clustering problem. We take many of the strategies we used for parallelizing graph partitioning on multicore architectures, and adapt them to the modularity maximization problem. We develop new methods for vertex aggregation, initial clustering, and cluster refinement. Our serial algorithms are an order of magnitude faster than state of the art serial methods while producing clusterings of equal or greater quality. Our parallel algorithms are 4.5--27.2x faster than other parallel methods and achieve 8.9x speedup on 16 cores while exhibiting less than 1% degradation in solution quality compared to their counterparts. Our implementation of these algorithms can cluster a three billion edge graph in under 90 seconds on a single computer.

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.

Power consumption is becoming an increasingly important component of processor design. As technology shrinks both static and dynamic power become more relevant. This is particularly important for the cache hierarchy. The cache portion of a microprocessor contains a large percentage of the total number of transistors in the microprocessor. Therefore the cache consumes a large percentage of both static and dynamic power. When improving power consumption in the past, there has always been a large trade-off between energy savings and performance. Techniques that reduce power consumption typically have a negative impact on performance. Likewise, when performance is improved it is at the cost of higher energy consumption. Also many current implementations only reduce one kind of power in the cache, either static or dynamic. For a more robust approach that will remain relevant as technology continues to shrink, both aspects of power need to be addressed. This thesis implements a phase adaptive cache that will reduce both static and dynamic power while having very little impact on the performance. This cache stores the most recently used blocks in one partition that is quick and easy to access. The second partition is placed in drowsy mode to reduce leakage power consumption. In this work, this approach is implemented for all three levels of cache in a multicore architecture. The design is also tested with multithreaded simulations. The results are measured using an architecture simulator. Simulations of the modified cache structure are compared to those of a baseline unchanged cache hierarchy running on the same machine. These results are compared for both energy savings including static and dynamic power, along with the overall impact on performance. The results in this work show that this cache design produces both dynamic energy and leakage energy savings with a low performance impact.

When parallel applications do not fully utilize the cores that are available to them they are missing the opportunity to have better performance. Sometimes threads have to wait for other threads. I call the code segments that make other threads wait bottlenecks. Examples of these bottlenecks include contended critical sections, threads arriving late to barriers and the slowest stage of a pipelined program. Other times all threads are running but some of them, which I call lagging threads, are making less progress, setting the stage to become bottlenecks. My thesis proposes identifying the code segments that are more critical for performance and efficiently accelerating them using faster cores, by either migrating execution to large cores of an Asymmetric Chip Multi-Processor (ACMP) or executing locally on DVFS-accelerated cores. The key contribution of this dissertation is a Utility of Acceleration metric that combines a measure of the acceleration for each code segment with a measure of its criticality. This metric enables meaningful comparisons to decide which bottlenecks or lagging threads to accelerate with each of the available acceleration mechanisms. My evaluation shows significant performance improvement for single multithreaded applications and sets of multiple single- and multi-threaded applications, and also reduction in energy-delay product due to the efficient utilization of the available acceleration mechanisms.

This dissertation proves the feasibility of accurate runtime prediction of processor performance under frequency scaling. The performance predictors developed in this dissertation allow processors capable of dynamic voltage and frequency scaling (DVFS) to improve their performance or energy efficiency by dynamically adapting chip or core voltages and frequencies to workload characteristics. The dissertation considers three processor configurations: the uniprocessor capable of chip-level DVFS, the private cache chip multiprocessor capable of per-core DVFS, and the shared cache chip multiprocessor capable of per-core DVFS. Depending on processor configuration, the presented performance predictors help the processor realize 72–85% of average oracle performance or energy efficiency gains.

As manufacturers introduce new machines with more cores, more NUMA-like architectures, and more tightly integrated heterogeneous processors, the traditional abstraction of a monolithic OS running on a SMP system is encountering new challenges.  One proposed path forward is the multikernel operating system.  Previous efforts have shown promising results both in scalability and in support for heterogeneity.  However, one effort\'s source code is not freely available (FOS), and the other effort is not self-hosting and does not support a majority of existing applications (Barrelfish). In this thesis, we present Popcorn, a Linux-based multikernel operating system.  While Popcorn was a group effort, the boot layer code and the memory partitioning code are the author\'s work, and we present them in detail here.  To our knowledge, we are the first to support multiple instances of the Linux kernel on a 64-bit x86 machine and to support more than 4 kernels running simultaneously. We demonstrate that existing subsystems within Linux can be leveraged to meet the design goals of a multikernel OS.  Taking this approach, we developed a fast inter-kernel network driver and messaging layer.  We demonstrate that the network driver can share a 1 Gbit/s link without degraded performance and that in combination with guest kernels, it meets or exceeds the performance of SMP Linux with an event-based web server.  We evaluate the messaging layer with microbenchmarks and conclude that it performs well given the limitations of current x86-64 hardware.  Finally, we use the messaging layer to provide live process migration between cores.

One of the challenges of multicore design is providing data quickly to all the processor cores running on a system. This has led to the development of architectures based on Network on Chips (NoC) due to their flexibility and scalability. In the NoC architecture, data is distributed among cache banks connected to different routers, therefore data access time varies by location. If data is accessed by two or more cores at the same time, then placing that data in the vicinity of those cores significantly improves overall access time. Recent proposals of hybrid and reconfigurable interconnect architectures try to take advantage of data locality to a certain extent by grouping processors that work on the same data set. In this dissertation, we propose migrating processor cores instead of data lines to take advantage of data locality. This is done either at static time where cores are assigned to routers before the runtime of the process with the introduction of the Reconfigurable Architecture for Multicore Systems (RAMS). In the static architecture, previous knowledge of the process characteristics is essential in determining a good configuration. We extend the idea further with the introduction of a dynamic reconfiguration entitled Dynamically Reconfigurable Multicore Architecture (DyaReMA) where cores are reassigned on the fly based on the pattern of data requests. A good test platform is essential to verify the validity of proposed architectures. We developed a complete modular hardware model that can be used to synthesize and simulate a range of architectures. The architectures proposed in literature have a homogeneous distribution of caches to routers. We propose a heterogeneous configuration of cache blocks to routers and show that the performance is significantly improved. We take this idea one step further and introduce the reconfigurable cache architecture that reassigns cache blocks to neighboring routers based on data access patterns. Hardware implementation alone cannot extract the full potential of multiocre architectures. Efficient data migration and cache coherency protocols are needed that further improve cache access time. Since data access is determined at run time, data migration has become an important part of multicore design. However, traditional data migration is expensive both due to the high cost in keeping track of all data accesses and the actual migration of data lines across multiple routers. In this dissertation, we propose a stepwise data migration scheme that improves efficiency reducing hardware cost. Data sharing introduces the need for cache coherency protocols. We propose a hybrid cache coherency protocol that combines the advantages of both broadcast and directory protocol to implement an efficient and scalable coherency method. Two coherency protocols are proposed, the first takes advantage of the characteristics of the hybrid/bus architecture. The second is targeted for NoC architectures. The proposed architectures along with data migration and cache coherency can improve data access time for L2 cache misses and help to significantly reduce the runtime of different processes in the realm of multicore architecture.

With the increasing application of multiple processor cores (multicores) within embedded system applications, as well as the pervasive utilization of the field-programmable gate array (FPGA), the embedded system development community has been exploring the advantages of the dynamically reconfigurable nature of FPGAs. Given size and power limitations, a primary motivation for this interest is to enable dynamic customization of hardware to optimize system performance for the various algorithms that a system encounters. This work presents a hardware based platform for studying dynamic reconfiguration of FPGAs in the context of multicore embedded systems. It also presents a methodology for developing the hardware and software for these systems. An important aspect of this work was to maximize the utilization of open source hardware and software intellectual property (IP). An example of the basic implementation flow is also provided, along with some benchmarking results.

Since multicore systems offer greater performance via parallelism, future computing is progressing towards use of machines with large number of cores. However, due to the complex interaction among characteristics of multithreaded applications, operating system policies, and architectural characteristics of multicore systems, delivering high performance on multicore systems is a challenging task. This dissertation addresses the above challenge by developing runtime techniques to achieve high performance when running a single multithreaded application as well as high system utilization and fairness when running multiple multithreaded applications. The runtime techniques are based on a simple monitoring system that captures important application characteristics and relevant architectural factors with negligible overhead. To develop runtime techniques for achieving high performance when running a single multithreaded program on a multicore system, important performance limiting factors that impact the scalability of performance are identified. These factors include the threads configuration (i.e., the number of threads for a multithreaded program that provide the best speedup) and the thread scheduling and memory allocation polices employed. This dissertation presents two runtime techniques Thread Reinforcer, for dynamically determining appropriate threads configuration and Thread Tranquilizer, for dynamically selecting appropriate scheduling and memory allocation policies. By dynamically determining the appropriate threads configuration, scheduling policy, and memory allocation policy the performance of applications is maximized.Lock contention is an important performance limiting factor for multithreaded programs on a multicore system. The dissertation presents two techniques Thread Shuffling and FaithFul Scheduling to limit the performance impact due to locks. Thread Shuffling reduces high lock acquisition latencies, resulting from the NUMA nature of a multicore system, via inter-CPU thread migrations. FaithFul Scheduling reduces the durations for which threads hold locks by minimizing lock holder thread preemptions through adaptive time-quanta allocations. These techniques significantly enhance the performance of applications in the presence of high lock contention.Finally, this dissertation presents a coscheduling technique called ADAPT for achieving high system utilization and fairness when running multiple multithreaded applications on multicore systems. ADAPT uses supervised learning techniques for predicting the effects of interference between programs on their performance and adaptively schedules together programs that interfere with each other's performance minimally. It achieves high throughput, high system utilization, and fairness when running multiple multithreaded applications.

Conventional CMOS scaling has been the engine of the technology revolution in most application domains. This trend has changed as in each technology generation, transistor densities continue to increase while due to the limits on threshold voltage scaling, per-transistor energy consumption decreases much more slowly than in the past. The power scaling issues will restrict the adaptability of designs to operate in different power and performance regimes. Consequently, future systems must employ more efficient architectures for optimizing every thread in the program across different power and performance regimes, rather than architectures that utilize more transistors. One solution is composable or dynamic multicore architectures that can span a wide range of energy/performance operating points by enabling multiple simple cores to compose to form a larger and more powerful core. Explicit Data Graph Execution (EDGE) architectures represent a highly scalable class of composable processors that exploit predicated dataflow block execution and distributed microarchitectures. However, prior EDGE architectures suffer from several energy and performance bottlenecks including expensive intra-block operand communication due to fine-grain instruction distribution among cores, the compiler-generated fanout trees built for high-fanout operand delivery, poor next-block prediction accuracy, and low speculation rates due to predicates and expensive refills after pipeline flushes. To design an energy-efficient and flexible dynamic multicore, this dissertation employs a systematic methodology that detects inefficiencies and then designs and evaluates solutions that maximize power and performance efficiency across different power and performance regimes. Some innovations and optimization techniques include: (a) Deep Block Mapping extracts more coarse-grained parallelism and reduces cross-core operand network traffic by mapping each block of instructions into the instruction queue of one core instead of distributing blocks across all composed cores as done in previous EDGE designs, (b) Iterative Path Predictor (IPP) reduces branch and predication overheads by unifying multi-exit block target prediction and predicate path prediction while providing improved accuracy for each, (c) Register Bypassing reduces cross-core register communication delays by bypassing register values predicted to be critical directly from producing to consuming cores, (d) Block Reissue reduces pipeline flush penalties by reissuing instructions in previously executed instances of blocks while they are still in the instruction queue, and (e) Exposed Operand Broadcasts (EOBs) reduce wide-fanout instruction overheads by extending the ISA to employ architecturally exposed low-overhead broadcasts combined with dataflow for efficient operand delivery for both high- and low-fanout instructions. These components form the basis for a third-generation EDGE microarchitecture called T3. T3 improves energy efficiency by about 2x and performance by 47% compared to previous EDGE architectures. T3 also performs in a highly power efficient manner across a wide spectrum of energy and performance operating points (low-power to high-performance), extending the domain of power/performance trade-offs beyond what dynamic voltage and frequency scaling offers on state-of-the-art conventional processors. This high level of flexibility and power efficiency makes T3 an attractive candidate for future systems which need to operate on a wide range of workloads under varying power and performance constraints.

The importance of biological pattern discovery has grown greatly due to the enormous amount of biological sequence data that exists and that is being generated on a daily basis. Many techniques exist to perform this pattern or motif discovery, each having its own strengths and weaknesses. One such algorithm, TEIRESIAS, has been used in a variety of computational biology applications. It possesses attributes which make it in some ways superior to other approaches, by reducing the computational complexity required to exhaustively find patterns which are maximal in form.While this tool continues to be cited by various research papers, a robust, open-source version does not exist. Users must rely on an aging Web-based system to use the tool, which is no longer updated. The major contribution of this thesis is the implementation of this algorithm, as well as providing its availability for any interested users. It has been verified against the existing Web-based version, in order to demonstrate its correctness.Modern processor architectures have steadily moved toward more processing cores and parallelism, with no signs of slowing down. Thus, this implementation utilizes these architectures effectively, reducing the time-to-completion for results. Therefore, presented here is a robust and efficient implementation.The layout of this document guides the reader through the various steps necessary to understand and appreciate how this was achieved. First, biological background and motivation is given. The TEIRESIAS algorithm is then presented in detail, thoroughly familiarizing the reader with its operation. The fundamental data structures required to realize this implementation are then explained, and how each might be appropriately applied. The strategies used to parallelize the algorithm are then presented. Results of this parallelization are also detailed, with numerous experiments showing its efficiency. A case study is performed, demonstrating the use of the algorithm for real biological analysis. Finally, the value of the work is concluded, as well as future directions that it could take.

We investigate the parallelization of an algorithm on three very different architectures. These are: a 128-processor Cray XMT massively multithreaded machine, a 16-processor IBM x3755 shared memory machine and a 240-core NVIDIA FX 5800 graphics processor unit (GPU). The problem we use in our investigation is the well-known subset-sum problem. While this is known to be NP-complete, it is solvable in pseudo-polynomial time, i.e., time proportional to the number of input objects multiplied by the sum of their sizes. This product defines the size of the dynamic programming table used to solve the problem.The hypothesis that we wish to test is that the Cray, with its specialized hardware and large uniform shared memory, is suitable for very large problems, the IBM x3755 is suitable for intermediate sized problems and the NVIDIA FX 5800 can give superior performance only for problems that fit within its modest internal memory.We show that it is straightforward to parallelize this algorithm on the Cray XMT primarily because of the word-level locking that is available on this architecture. For the other two machines we present an alternating word algorithm that can implement an efficient solution. The timings of our respective codes were carefully measured over a comprehensive range of problem sizes. On the Cray XMT we observe very good scaling for large problems and see sustained performance as the problem size increases. However this machine has poor scaling for small problem sizes; it performs best for problem sizes of 1012 bits or more. The IBM x3755 performs very well on medium sized problems, but has poor scalability as the number of processors increases and is unable to sustain performance as the problem size increases. This machine tends to saturate for problem sizes of 1011 bits. The NVIDIA GPU performs well for problems whose tables t within its 4GB device memory. This corresponds to tables of size approximately 1010/.The experimental measurements support our hypothesis and show that each machine gives superior performance for distinct ranges of problem sizes and demonstrate the strengths and weaknesses of the three architectures.

Computing applications demand good performance from networking systems. This includes high-bandwidth communication using protocols with sophisticated features such as ordering, reliability, and congestion control. Much of this protocol processing occurs in software, both on desktop systems and servers. Multi-processing is a requirement on today's computer architectures because their design does not allow for increased processor frequencies. At the same time, network bandwidths continue to increase. In order to meet application demand for throughput, protocol processing must be parallel to leverage the full capabilities of multi-processor or multi-core systems. Existing parallelization strategies have performance difficulties that limit their scalability and their application to single, high-speed data streams. This dissertation introduces a new approach to parallelizing network protocol processing without the need for locks or for global state. Rather than maintain global states, each processor maintains its own copy of protocol state. Therefore, updates are local and don't require fine-grained locks or explicit synchronization. State management work is replicated, but logically independent work is parallelized. Along with the approach, this dissertation describes Dominoes, a new framework for implementing replicated processing systems. Dominoes organizes the state information into Domains and the communication into Channels. These two abstractions provide a powerful, but flexible model for testing the replication approach. This dissertation uses Dominoes to build a replicated network protocol system. The performance of common protocols, such as TCP/IP, is increased by multiprocessing single connections. On commodity hardware, throughput increases between 15-300% depending on the type of communication. Most gains are possible when communicating with unmodified peer implementations, such as Linux. In addition to quantitative results, protocol behavior is studied as it relates to the replication approach.

At present there is a strong interest in the research community to develop large scale implementations of neuromorphic algorithms. These systems consume significant amounts of power, area, and are very expensive to build. This thesis examines the design space of multicore processors for accelerating neuromorphic algorithms. A new multicore chip will enable more efficient design of large scale neuromorphic computing systems. The algorithms examined in this thesis are the HMAX and Izhikevich models. HMAX was developed recently at MIT to model the visual system of the human brain. The Izhikevich model was presented by Izhikevich as a biologically accurate spiking neuron model. This thesis also examines the parallelization of the HMAX model for studying multicore architectures. The results show the best single core architectures for HMAX and Izhikevich are almost same, though HMAX needs more cache. The multicore study shows that the off chip memory bus width and physical memory latency could improve the performance of the multicore system.

Elliptic curve cryptography (ECC) is becoming the algorithm of choice for digital signature generation and authentication in embedded context. However, performance of ECC and the underlying modular arithmetic on embedded processors remains a concern. At the same time, more complex system-on-chip platforms with multiple heterogeneous cores are commonly available in mobile phones and other embedded devices. In this work we investigate the design space for ECC on TI's OMAP 3530 platform, with a focus of utilizing the on-chip DSP core to improve the performance and efficiency of ECC point multiplication on the target platform. We examine multiple aspects of ECC and heterogeneous design such as algorithm-level choices for elliptic curve operations and the effect of interprocessor communication overhead on the design partitioning. We observe how the limitations of the platform constrict the design space of ECC. However, by closely studying the platform and efficiently partitioning the design between the general purpose ARM core and the DSP, we demonstrate a significant speed-up of the resulting ECC implementation. Our system focused approach allows us to accurately measure the performance and power profiles of the resulting implementation. We conclude that heterogeneous multiprocessor design can significantly improve the performance and power consumption of ECC operations, but that the integration cost and the overhead of interprocessor communication cannot be ignored in any actual system.

Dense linear algebra(DLA) is one of the most seven important kernels in high performance computing. The introduction of new machines from vendors provides us opportunities to optimize DLA libraries for the new machines and thus exploit their power. Unfortunately the optimization phase is not straightforward. The optimum code of a certain Basic Linear Algebra Subprogram (BLAS) kernel, which is the core of DLA algorithms, in two different machines with different semiconductor process can be different even if they share the same features in terms of instruction set architecture, memory hierarchy and clock speed. It has become a tradition to optimize BLAS for new machines. Vendors maintain highly optimized BLAS libraries targeting their CPUs. Unfortunately the existing BLAS for GPUs is not highly optimized for DLA algorithms. In my research, I have provided new algorithms for several important BLAS kernels for different generation of GPUs and introduced a pointer redirecting approach to make BLAS run faster in generic problem size. I have also presented an auto-tuning approach to parameterize the developed BLAS algorithms and select the best set of parameters for a given card. The hardware trends have also brought up the need for updates on existing legacy DLA software packages, such as the sequential LAPACK. To take advantage of the new computational environment, successors of LAPACK must incorporate algorithms of three main characteristics: high parallelism, reduced communication, and heterogeneity-awareness. On multicore architectures, Parallel Linear Algebra Software for Multicore Architectures (PLASMA) has been developed to meet the challenges in multicore. On the other extreme, Matrix Algebra on GPU and Multicore Architectures (MAGMA) library demonstrated a hybridization approach that indeed streamlined the development of high performance DLA for multicores with GPU accelerators. The performance of these two libraries depend upon right choice of parameters for a given problem size and given number of cores and/or GPUs. In this work, the issue of automatically tuning these two libraries is presented. A prune based empirical auto-tuning method has been proposed for tuning PLASMA. Part of the tuning method for PLASMA was considered to tune hybrid MAGMA library.

Applications with irregular accesses to shared state are one of the most challenging computational patterns in parallel computing. Accesses can involve both read or write operations, with writes having the additional complexity of requiring some form of synchronization. Irregular accesses perform poorly in local cached-based memory systems and across networks in global distributed memory settings, because they have poor spatial and temporal locality. Irregular accesses arises in transaction processing, in various system level programs, in computing histograms, performing sparse matrix operations, updating meshes inparticle-mesh methods, and building adaptive unstructured meshes. Writing codes with asynchronous parallel updates on clusters and multicore processors presents different sets of challenges. On clusters, the goal is to minimize the number of messages and the volume of messages between nodes. While on multicore machines, the goal is to minimize off-chip accesses since there is significant performance difference between on chip and off chip memory access.In this dissertation, we explore various analyses, optimizations, and tools for shared accesses on both multicore and distributed memory cluster architectures. On cluster architectures, we consider both irregular reads and writes, demonstrate how Partitioned Global Address Space languages support programming irregular problems, and develop optimizations to minimizecommunication traffic, both in volume and number of distinct events. On multicore processors, we consider the lower level code generation and tuning problem, independent of any particular source language. We explore performance tradeoffs between various shared update implementations, such as locking, replication of state to avoid collisions, and hybrid versions.We develop an adaptive implementation that adjusts the shared update strategy based on densities that yields significant speedups. In addition, we develop a performance debugging tool to find scalability problems in large scientific applications early in the development cycle. Throughout the thesis we perform experiments demonstrating the value of our optimizations and tools in both architectural settings, use a set of benchmarks and applications that includehistogram making, sparse matrix computations, and two scientific simulations involving particle-mesh methods. Our results show substantial speeds of up to 4.8X for multicore platforms and 120X for clusters. The results are a comprehensive set of techniques for improving the performance of irregular applications using advanced languages, compilers, analyses, optimizations and tools.

The widening spectrum of network applications incurs increasing stress on physical resources for both the network infrastructure and the web servers. Meanwhile, the emergence of faster Ethernet has shifted the bottleneck of network performance to the processing capability of the web servers. This trend has driven the prevalence of Chip Multiprocessors (CMP, a.k.a. multicore). However, even running on the state of the art multicore web servers, the network performance still falls short of expectations. In this study, we optimize multicore scheduling in both the OS kernel and userspace for three legacy network applications, i.e. Deep Packet Inspection (DPI), multimedia transcoding and SPECweb2005. In the OS kernel, we propose an interrupt affinity based scheduler to prevent starvation by separating interrupt handlers from userspace application. In the userspace, we first parallelize the network application and then propose an affinity based scheduler that affinitizes all the packets in the same connection to the same core. However, this scheduler is oblivious of load balancing, which can offset the cache benefits. We therefore propose several hash based schedulers to strike a balance between connection locality and load balancing. While the baseline Highest Random Weight (HRW) hash balances workload at the connection level, our Adjusted HRW (AHRW) achieves packet level load balancing by comparison of runqueue length of each core. In addition, we enable cache awareness of AHRW by means of a communication matrix in Cache-Aware AHRW (CA-HRW), and propose a hierarchical version, H-CAHRW, for different core/cache topologies. To incorporate QoS concerns, we also develop a Proportional Share HRW scheduler, PS-HRW, by allocating cores to each connection based on connection buffer size. We implement and verify all of our schedulers using real application measurements. With the resurgent interest in system virtualization, we present a performance characterization of a virtualized multicore server under consolidated network workloads and show that L2 cache misses are the major bottleneck. We therefore optimize the virtual CPU migration policy to take advantage of the cache topology. Then, we port all our schedulers developed in the native system to a virtualized multicore server, and observe minimum performance degradation.

The exponential improvement in single processor performance has recently come to an end, mainly because clock frequency has reached its limit due to power constraints. Thus, processor manufacturers are choosing to enhance computing capabilities by placing multiple cores into a single chip, which can improve performance given parallel software. This paradigm shift to chip multiprocessors (also called multicore) requires scalable parallel applications that execute tasks on each core, otherwise the additional cores are worthless. Making an application scalable requires more than simply parallelizing the application code itself. Modern applications are written in managed languages, which require automatic memory management, type and memory abstractions, dynamic analysis and just-in-time (JIT) compilation. These managed runtime systems monitor and interact frequently with the executing application. Hence, the managed runtime itself must be scalable, and the instrumentation that monitors the application should not perturb its scalability. While multicore hardware forces a redesign of managed runtimes for scalability, it also provides opportunities when applications do not fully utilize all of the cores. Using available cores for concurrent helper threads that enhance the software, with debugging, security, and software support will make the runtime itself more capable and more scalable. This dissertation presents two novel techniques that improve the scalability of managed runtimes by utilizing unused cores. The first technique is a concurrent dynamic analysis framework that provides a low-overhead buffering mechanism called Cache-friendly Asymmetric Buffering (CAB) that quickly offloads data from the application to helper threads that perform specific dynamic analyses. Our framework minimizes application instrumentation overhead, prevents microarchitectural side-effects, and supports a variety of dynamic analysis clients, ranging from call graph and path profiling to cache simulation. The use of this framework ensures that helper threads perturb the performance of application as little as possible. Our second technique is concurrent trace-based just-in-time compilation, which exploits available cores for the JavaScript runtime. The JavaScript language limits applications to a single-thread, so extra cores are worthless unless they are used by the runtime components. We redesigned a production trace-based JIT compiler to run concurrently with the interpreter, and our technique is the first to improve both responsiveness and throughput in a trace-based JIT compiler. This thesis presents the design and implementation of both techniques and shows that they improve scalability and core utilization when running applications in managed runtimes. Industry is already adopting our approaches, which demonstrates the urgency of the scalable runtime problem and the utility of these techniques.

PAL, POULOMI. Scheduling to Consolidate Idle Periods for Energy Efficiency in Multicore Systems. (Under the direction of Dr. Gregory T. Byrd.) Power-efficiency and energy savings are the major drivers in the CPU design space. Design at all levels needs to be energy-aware in order to be considered seriously. With the emergence of mobile devices as a large market, energy efficiency has become of prime importance, as the emphasis now lies on making the battery last longer. Most modern cellphones are required to do much more than making and receiving calls. With 4G approaching quickly, the cellphone is required to be almost as good as any general purpose computer with respect to application complexities. This gives rise to the need for adaptive systems that can handle applications with high performance, and conserve energy as well. The research presented here provides a scheduling scheme which aims to consolidate CPU idle times, and to introduce some amount of inertia and determinism in the system, so as to provide the opportunity to switch CPUs into low-power modes for conservation of energy. The baseline used here is the Linux kernel-2.6.28, which implements distributed control for load balancing for different CPUs. Changes are made to this kernel, and CPU activity is used as the metric for comparison. It is found that the CPUs that are numbered higher get much longer idle periods, which can be used for switching to energy-efficiency mode, while still maintaining comparable performance.

The human cortex is the seat of learning and cognition. Biological scale implementations of cortical models have the potential to provide significantly more power problem solving capabilities than traditional computing algorithms. The large scale implementation and design of these models has attracted significant attention recently. High performance implementations of the models are needed to enable such large scale designs. This thesis examines the acceleration of the spiking neural network class of cortical models on several modern multicore processors. These include the Izhikevich, Wilson, Morris-Lecar, and Hodgkin-Huxley models. The architectures examined are the STI Cell, Sun UltraSPARC T2+, and Intel Xeon E5345. Results indicate that these modern multicore processors can provide significant speed-ups and thus are useful in developing large scale cortical models. The models are then implemented on a 50 TeraFLOPS 336 node PlayStation 3 cluster. Results indicate that the models scale well on this cluster and can emulate 108 neurons and 1010 synapses. These numbers are comparable to the large scale cortical model implementation studies performed by IBM using the Blue Gene/L supercomputer. This study indicates that a cluster of PlayStation 3s can provide an economical, yet powerful, platform for simulating large scale biological models.

The use of asymmetric multi-core processors with on-chip computational accelerators is becoming common in a variety of environments ranging from scientific computing to enterprise applications. The focus of current research has been on making efficient use of individual systems, and porting applications to asymmetric processors. The use of these asymmetric processors, like the Cell processor, in a cluster setting is the inspiration for the Cell Connector framework presented in this thesis. Cell Connector adopts a streaming approach for providing data to compute nodes with high computing potential but limited memory resources. Instead of dividing very large data sets once among computation resources, Cell Connector slices, distributes, and collects work units off of a master data held by a single large memory machine. Using this methodology, Cell Connector is able to maximize the use of limited resources and produces results that are up to 63.3\% better compared to standard non-streaming approaches.

High Performance Computing is enabling rapid innovations spanning several key areas ranging from science, technology and manufacturing disciplines to entertainment and financial markets. One computing paradigm contributing significantly to the outreach of such capabilitiesis Cluster Computing. Cluster computing involves the use ofmultiple Commodity PCs interconnected by a network to provide the required computational resource in a cost-effective manner. Recently, commodity clusters are rapidly transforming into capability class machines with several of them featuring in the Top 10 list of supercomputers. The two primary drivers for this trend being: a) Adventof Multicore technology and b) Performance and Scalability of InfiniBand, an open standard based interconnection network. These two factors are ushering in an era of ultra-scale InfiniBand Multicore clusters comprising of tens of thousands of compute cores.Utilizing Message Passing Interface (MPI) is the most popular method of programming parallel appplications. In this model, communication occurs via explicit exchange of data messages. MPI provides for plethora of communication primitives out of which Collective primtives are especially significant. These are extensively used in a variety of scientific and engineering applications (such as to compute fast fourier transforms and multiply large matrices, etc.). It is imperative that these collectives be designed efficiently to ensure good performance and scalability. MPI collectives pose several challenges and requirements in terms of guaranteeing data reliability, enabling efficient scalable means of data transfers and providing for process skew tolerance mechanisms. Moreover, the characteristics of underlying network and multicore systems directly impact the behavior of the collective operations and need to be taken into consideration for optimizing performance and resource usage.In this dissertation, we take on these challenges to design a Scalable and High Performance Collective Communication subsystem for MPI over InfiniBand Multicore clusters. The central theme used in our approach is to have an in-depth understanding of the capabilities of underlying network/system architecture and leverage these to provideoptimal design alternatives. Specifically, the dissertation describes novel communication protocols and algorithms utilizing a) InfiniBand's hardware Multicast, RDMA capabilities and b) System's shared memory to meet the stated requirements and challenges. Also, the collectiveoptimizations discussed in the dissertation take into account the different transport methods of InfiniBand and the architectural attributes of Multicore systems. The designs proposed in the dissertation have been incorporated into the open source MVAPICH software used by more than 680 organizations worldwide. It is used in several cluster installations, and currently used by the world's thirdfastest supercomputer.

The growing complexity of applications has increased the need for higher processing power. In the embedded domain, the convergence of audio, video, and networking on a handheld device has prompted the need for low cost, low power,and high performance implementations of these applications in the form of custom hardware. In a more mainstream domain like gaming consoles, the move towards more realism in physics simulations and graphics has forced the industry towards multicore systems. Many of the applications in these domains are streaming in nature. The key challenge is to get efficient implementations of custom hardware from these applications and map these applications efficiently onto multicore architectures. This dissertation presents a unified methodology, referred to as Streamroller, that can be applied for the problem of scheduling stream programs to multicore architectures and to the problem of automatic synthesis of custom hardware for stream applications. Firstly, a method called stream-graph modulo scheduling is presented, which maps stream programs effectively onto a multicore architecture. Many aspects of a real system, like limited memory and explicit DMAs are modeled in the scheduler. The scheduler is evaluated for a set of stream programs on IBM's Cell processor. Secondly, an automated high-level synthesis system for creating custom hardware for stream applications is presented. The template for the custom hardware is a pipeline of accelerators. The synthesis involves designing loop accelerators for individual kernels, instantiating buffers to store data passed between kernels, and linking these building blocks to form a pipeline. A unique aspect of this system is the use of multifunction accelerators, which improves cost by efficiently sharing hardware between multiple kernels. Finally, a method to improve the integer linear program formulations used in the schedulers that exploits symmetry in the solution space is presented. Symmetry-breaking constraints are added to the formulation, and the performance of the solver is evaluated.