We present PolyMorphous, an MLIR-based polyhedral compiler that exposes a set of loop-based scheduling primitives, providing users with ample control over optimizations for input code. The primitives are expressed in a new Schedule dialect that is based on MLIR's Transform dialect. PolyMorphous' polyhedral engine collapses the primitives into a polyhedral schedule and checks for its legality. If necessary, and possible, the engine corrects an illegal schedule into a legal one. PolyMorphous is evaluated using the PolyBench suite. The evaluation validates PolyMorphous' approach in two ways. First, it shows that PolyMorphous enables users to explore the optimization space, and that it results in well-optimized code. Second, it shows that PolyMorphous' correction of illegal schedules enables users to optimize code with fewer primitives and improves their productivity by alleviating the need for manual correction. Specifically, the evaluation shows that PolyMorphous optimized code performs as well as code optimized by Pluto+ with its optimization flags tuned to achieve the best performance for each benchmark. Further, for several benchmarks, PolyMorphous optimized code performs better, confirming the value of providing users with control over optimizations. Averaged over all the benchmarks, PolyMorphous optimized code has a speedup of$1.24 \mathrm{x} / 1.25 \mathrm{x}$over that optimized by Pluto+ on Arm/X86 systems. PolyMorphous brings the approach of empowering users of polyhedral compilers with control over optimizations to a community-developed infrastructure, promoting the approach's adoptability. It does so while delivering performant code.

Sparse computations are common in practical HPC, AI and graph-based applications. Such computations often exhibit scattered and fragmented data accesses, which negatively impact data transfer efficiency to/from accelerators. We propose, implement and evaluate an algorithm for extracting or mining sparsity patterns that exist in sparse matrices. The algorithm extracts multiple pattern types in a matrix, including blocks, bands, triangles or regular compositions of each. It does so without a priori knowledge of the presence of these patterns in the matrix. The patterns may contain, under user control, zero elements, or imperfections, to facilitate the extraction of larger patterns. Additionally, we introduce the Compressed Sparse Pattern (CSP), a novel compressed representation for sparse matrices that is based on these patterns. The use of CSP combined with extensions to Address Generation Units (AGUs) of accelerators regularize data accesses and improve data transfer efficiency. Evaluation of the pattern mining algorithm and CSP using 26 real-world sparse matrices is conducted on an Ubuntu system with an 8 core Intel CPU (3.6 GHz i7-9700K) and 32 GB of memory. The evaluation shows that patterns of different sizes and shapes are common, representing ∼82% of the non-zero elements in these matrices. The patterns can be efficiently extracted in time, with an average of 4.6 seconds. The evaluation also shows that the mining of composite patterns contributes ∼8% to the number of non-zeros in patterns and that imperfections increase pattern sizes with a minimal impact of only ∼7% zero elements in patterns. Finally, using CSP leads to up to 90% reduction in data transfer overhead, compared to CSR and CSC, both common compressed sparse matrix representations. These results validate our approach of extracting and representing patterns to improve data transfer efficiency.

We propose, implement, and evaluate a novel approach for mapping dataflow graphs (DFGs) onto spatially configured Coarse-Grained Reconfigurable Arrays (CGRAs). The approach tackles mapping failure due to the congestion that arises when more than one routing path uses the same CGRA link. Heuristics are used to identify congestion patterns and “reserve” CGRA processing elements (PEs) around the congestion by preventing them from being used for DFG nodes in a mapping re-attempt. The reserved PEs effectively increases routing resources around the congestion, thereby increasing the likelihood of mapping success. This approach is referred to as reserve-on-demand mapping since PEs are reserved only when congestion exists and is driven by its patterns.

GEMM accelerators used for AI typically require special layouts of their input and output data. Pre- and post-conversion to such layouts from and to standard row-major or column-major layouts degrades performance. This is particularly the case when conversion overhead cannot be amortized over multiple GEMM executions, as in, for example, LU factorization, a key computation in HPC.We propose a novel on-the-fly data layout conversion approach for GEMM used for LU factorization on Huawei’s DaVinci AI Core. The approach alleviates the bulk of conversion through the use of DMA and Vector engines to convert data layout as data moves through the memory hierarchy, and as it is processed. The approach reduces conversion overhead, but requires more use of the DMA and Vector engines, compared to when data is already in the accelerator’s required data layout.We experimentally evaluate the approach on an Ascend 910 AI processor with 32 DaVinci cores used to accelerate GEMM. We show that the approach reduces layout conversion time by 74% and that the additional use of the DMA/Vector engines reduces compute efficiency by no more than 15%. The result is an improvement in GEMM’s end-to-end performance— over explicit pre-/post-conversion—by up to ∼2X, and on average by 1.6X. In the context of LU factorization, where GEMM is repeatedly used for shrinking matrix sizes, our approach improves GEMM performance by up to 1.6X and on average by 1.4X.

We propose, implement and evaluate a work stealing based scheduler, called HWS, for graph processing on heterogeneous CPU-FPGA systems that tightly couple the CPU and the FPGA to share system memory. HWS addresses unique concerns that arise with work stealing in the context of our target system. Our evaluation is conducted on the Intel Heterogeneous Architecture Research Platform (HARPv2), using three key processing kernels and seven real-world graphs. We show that HWS effectively balances workloads. Further, the use of HWS results in better graph processing performance compared to static scheduling and a representative of existing adaptive partitioning techniques, called HAP. Improvements vary by graph processing application, input graph and number of threads, and can be up to 100% over static scheduling, and up to 17% over HAP. We also compare to an oracle chunk self-scheduler, in which the best chunk size is known a priori for each number of threads and each input graph. HWS performs no worse than 1-3% in most cases. Finally, our graph processing throughput scales well with increasing threads. These results collectively demonstrate the effectiveness of work stealing for graph processing on our heterogeneous target platform.

We consider software-hardware acceleration of K-means clustering on the Intel Xeon+FPGA platform. We design a pipelined accelerator for K-means and combine it with CPU threads to assess performance benefits of (1) acceleration when data are only accessed from system memory and (2) cooperative CPU-FPGA acceleration. Our evaluation shows that the accelerator is up to 12.7×/2.4× faster than a single CPU thread for the assignment/update step of K-means. The cooperative use of threads and FPGA is roughly 1.9× faster than CPU threads alone or the FPGA by itself. Our approach delivers 4×–5× higher throughput compared to existing offload processing approaches.

We present a case study of the design of an FPGA accelerator for a tightly-coupled shared-memory processor-FPGA system: the Intel QuickAssist FPGA platform. We use K-means as an example computationally-intensive application and design a pipelined accelerator for calculating minimum distances between points and centroids. Our accelerator is unique in that it works in collaboration with CPU threads, accessing shared data in system memory. It achieves a speedup of 3.8X over a reference software implementation. Moreover, the combined use of CPU threads and the FPGA accelerator achieves a speedup of up to 2.9X over using only the CPU threads and of up to 1.9X over using only the accelerator, depending on the number of CPU threads. We analyze the impact of data sharing between the CPU threads and the FPGA and reason that while this sharing increases memory traffic, it has little impact on overall performance.

We consider automatic performance tuning of stencil computations on Graphics Processing Units. We present a strategy that uses machine learning to determine the best way to use memory followed by a heuristic that divides the remaining optimizations into groups and exhaustively explores one group at a time. We evaluate our strategy using 102 synthetically generated OpenCL stencil kernels on an Nvidia GTX Titan GPU. We assess our strategy both in terms of the number of configurations explored during auto-tuning and the quality of the best configuration obtained. We explore two alternative heuristics that use different groupings of the optimizations. We show that, relative to a random sampling of the space and an expert search, our strategy achieves a reduction in the number of configurations explored of up to 80% and 84% respectively while also finding better performing configurations.

Data races make parallel programs hard to understand. Precise race detection that stops an execution on first occurrence of a race addresses this problem, but it comes with significant overhead. In this work, we exploit the insight that precisely detecting only write-after-write (WAW) and read-after-write (RAW) races suffices to provide cleaner semantics for racy programs. We demonstrate that stopping an execution only when these races occur ensures that synchronization-free-regions appear to be executed in isolation and that their writes appear atomic. Additionally, the undetected racy executions can be given certain deterministic guarantees with efficient mechanisms.

We analyze the fundamental performance impact of enforcing a fixed order of synchronization operations to achieve weak deterministic execution. Our analysis is in three parts, performed on a real system using the SPLASH-2 and PARSEC benchmarks. First, we quantify the impact of various sources of non-determinism on execution of data-race-free programs. We find that thread synchronization is the prevalent source of non-determinism, sometimes affecting program output. Second, we divorce the implementation overhead of a system imposing a specific synchronization order from the impact of enforcing this order. We show that this fundamental cost of determinism is small (slowdown of 4% on average and 32% in the worst case) and we identify application characteristics responsible for this cost. Finally, we evaluate this cost under perturbed execution conditions. We find that demanding determinism when threads face such conditions can cause almost 2x slowdown.

Mesh-of-functional-units (mesh-of-FUs) overlays can deliver high-performance because they expose the massively parallel FPGA fabric and have the ability to be customized for different applications. However, a key challenge is how to quickly compile a number of custom mesh-of-FUs overlays to FPGA fabric such that they achieve high fMAXand scale to large mesh sizes. We propose a tile-based bottom-up CAD flow that utilizes the hierarchical physical design techniques of partitioning and floorplanning. Our flow partitions the overlay circuit into tiles, groups of adjacent overlay cells, and then compiles the tiles to a rectangular coarse-grain floorplan. Independent compilation of tiles is made possible by inserting complementary elastic buffers on inter-tile paths to ensure that these paths are not a bottleneck for fMAX. As a result, an overlay can be formed by only “stitching” a set of pre-compiled tiles.We show that compared to the flat flow, our bottom-up flow results in higher fMAXthat degrades little with increasing overlay size. Further, our flow can generate a library of pre-compiled tiles that can be reused - it can stitch a set of library tiles into a new overlay in only 35 minutes. It also allows a divide-and-conquer overlay compilation flow by compiling its tiles in parallel on multiple machines.

A major issue facing the widespread use of FPGAs as accelerators is their programmability wall: the difficulty of hardware design and the long synthesis times. Overlays-pre-synthesized FPGA circuits that are themselves reconfigurable - promise to tackle these challenges. We design and evaluate an overlay architecture, structured as a mesh of functional units, for pipelined execution of data-flow graphs (DFGs), a common abstraction for expressing parallelism in applications. We use data-driven execution based on elastic pipelines to balance pipeline latencies and achieve a high fMAX, scalability and maximum throughput. We prototype two overlays on a Stratix IV FPGA: a 355 MHz 24×16 integer overlay and a 312 MHz 18×16 floating-point overlay. We also design a tool that maps DFGs to overlays. We map 15 DFGs and show that the two overlays deliver throughputs of up to 35 GOPS and 22 GFLOPS, respectively. We also show that DFG mapping is fast, taking no more than 6 seconds for the largest DFG. Thus, our overlay architecture raises the level of abstraction of FPGA programming closer to that of software and avoids lengthy synthesis time, easing the use of these devices to accelerate applications.

We design, implement and evaluate a parallel radix sort that simultaneously utilizes the CPU and GPU devices on the AMD Fusion APU. The parallel sort, referred to as Fusion Sort, partitions the sort keys between the CPU and GPU devices and utilizes the integrated memory system of the APU to avoid data copying between the devices. We identify three design issues that impact overhead and performance: the granularity of sharing between the two devices, the scheme of data partitioning and the allocation of data in memory regions accessible by each device. We present three variants of Fusion Sort that share data at coarse and fine granularities and with fixed and variable data partitioning schemes. In each variant, data is allocated to minimize the overhead of non-preferred memory accesses of each device. Our evaluation shows that fine-grain sharing with variable data partitioning performs the best. Further, Fusion Sort outperforms CPU-only and GPU-only parallel radix sorts by up to 1.8X and 1.9X respectively. These results demonstrate the viability of the integrated memory system of the APU in the context of sorting.

We explore the design, implementation, and evaluation of a coarse-grain superscalar processor in the context of the microarchitecture of the Control Processor (CP) of the Multilevel Computing Architecture (MLCA), a novel architecture targeted for multimedia multicore systems. The MLCA augments a traditional multicore architecture (called the lower level) with a CP (called the top-level), which automatically extracts parallelism among coarse-grain units of computation (tasks), synchronizes these tasks and schedules them for execution on processors. It does so in a fashion similar to how instruction-level parallelism is extracted by superscalar processors, i.e., using register renaming, Out-of-Order Execution (OoOE) and scheduling. The coarse-grain nature of tasks imposes challenging constraints on the direct use of these techniques, but also offers opportunities for simpler designs. We analyze the impact of these constraints and opportunities and present novel microarchitectural mechanisms for coarse-grain superscalar execution, including register renaming, task queue, dynamic out-of-order scheduling and task-issue. We design an MLCA system around our CP microarchitecture and implement it on an FPGA. We evaluate the system using multimedia applications and show good scalability for eight processors, limited by the memory bandwidth of the FPGA platform. Furthermore, we show that the CP introduces little overhead in terms of resource usage. Finally, we show scalability beyond eight processors using cycle-accurate RTL-level simulation with an idealized memory subsystem. We demonstrate that the CP poses no performance bottlenecks and is scalable up to 32 processors.

We propose a heap analysis for extracting data access summaries based on symbolic access paths (SAPs) of methods in object-oriented languages. The analysis takes advantage of the insight that typical programs access dynamic data structures in regular manners. We combine this insight with a bottom-up approach that computes a local summary for each basic block, loop, and method in the program, which is then encapsulated into an abstract block in order to efficiently handle the higher levels of the analysis. We solve the problem of the dependence of local analysis results on the global heap aliasing by inferring the sets of aliases on which the correctness of the local results is predicated. Experimental evaluation for Java shows that for typical programs that use dynamic data structures, our analysis runs in a fast single pass and produces useful results.

We propose a novel synchronization mechanism called versioning. It dynamically establishes a deterministic order of memory accesses in parallel programs that have serial semantics, in a way that is transparent to the programmer. This order is created in a distributed manner and is enforced by monitoring memory accesses and stalling threads if necessary. Versioning gives rise to parallel programming models in which programmers need not explicitly synchronize threads and only need to specify shared data, which greatly simplifies parallel programming. However, versioning introduces overheads and thus demands architectural support. We describe versioning and the architectural support it needs. We also propose one parallel programming model that utilizes versioning and use it to parallelize 13 benchmark applications. We build an FPGA prototype of a multiprocessor system with versioning support and show that good parallel speedups are obtained. Our analysis shows minimal impact of versioning, both in terms of timing overheads and in terms of additional hardware.

Some of today's TM systems implement the two-phase-locking (2PL) algorithm which aborts transactions every time a conflict occurs. 2PL is a simple algorithm that provides fast transactional operations. However, it limits concurrency in benchmarks with high contention because it increases the rate of aborts. We propose the use of a more relaxed concurrency control algorithm to provide better concurrency. This algorithm is based on the conflict-serializability (CS) model. Unlike 2PL, it allows some transactions to commit successfully even when they make conflicting accesses. We implement this algorithm in a STM system and evaluate its performance on 16 cores using standard benchmarks. Our evaluation shows that the algorithm improves the performance of applications with long transactions and high abort rates. Throughput is improved by up to 2.99 times despite the overheads of testing for CS at runtime. These improvements come with little additional implementation complexity and require no changes to the transactional programming model. We also propose an adaptive approach that switches between 2PL and CS to mitigate the overhead in applications that have low abort rates.

We explore the feasibility of accelerating soft processors by dynamically translating hot segments of code into FPGA circuits. We propose an approach that tackles two key challenges: the prohibitive compile time of standard synthesis tools and the limited run-time reconfigurability of commodity FPGAs. We use traces, or hot straight-line segments of code, as the units of code to translate into FPGA circuits, combined with a pre-synthesized overlay that is tuned for traces. The overlay, referred to as the Virtual Dynamically Reconfigurable (VDR) overlay consists of an array of functional units that are interconnected by a set of programmable switches. The overlay can be rapidly configured by the soft processor at run-time. Our approach avoids traditional synthesis and reduces code-to-circuit translation to the significantly faster mapping of instructions to VDR units. Preliminary evaluation shows that the overlay speeds up the execution of the benchmark by up to 9X over a Nios II processor. The overlay incurs a 6.4X penalty in resources compared to Nios II.

Graphics Processing Units (GPUs) have become a competitive accelerator for applications outside the graphics domain, mainly driven by the improvements in GPU programmability. Although the Compute Unified Device Architecture (CUDA) is a simple C-like interface for programming NVIDIA GPUs, porting applications to CUDA remains a challenge to average programmers. In particular, CUDA places on the programmer the burden of packaging GPU code in separate functions, of explicitly managing data transfer between the host and GPU memories, and of manually optimizing the utilization of the GPU memory. Practical experience shows that the programmer needs to make significant code changes, often tedious and error-prone, before getting an optimized program. We have designed hiCUDA}, a high-level directive-based language for CUDA programming. It allows programmers to perform these tedious tasks in a simpler manner and directly to the sequential code, thus speeding up the porting process. In this paper, we describe the hiCUDA} directives as well as the design and implementation of a prototype compiler that translates a hiCUDA} program to a CUDA program. Our compiler is able to support real-world applications that span multiple procedures and use dynamically allocated arrays. Experiments using nine CUDA benchmarks show that the simplicity hiCUDA} provides comes at no expense to performance.

Today's transactional memory systems implement the two-phase-locking (2PL) algorithm which aborts transactions every time a conflict happens. 2PL is a simple algorithm that provides fast transactional operations. However, it limits concurrency in applications with high contention by increasing the rate of aborts. More relaxed algorithms that can commit conflicting transactions have recently been shown to provide better concurrency both in software and hardware. However, existing approaches for implementing such algorithms increase latencies of transactional operations, require complex hardware support and alter standard cache coherence protocols. In this paper, we discuss how a relaxed concurrency control algorithm can be efficiently implemented in hardware. More specifically, we use a technique which approximates conflict-serializability and implement it in hardware on top a base hardware transactional memory system that provides support for isolation and conflict detection. Our novel hardware scheme is based on recording conflicts as they occur, instead of aborting transactions. Transactions serialize at commit time according to these conflicts by sending broadcast messages. Our evaluation of this hardware scheme using a simulator and standard benchmarks shows that it captures the benefits of conflict-serializability. Applications with long transactions and high contention benefit the most, abort rates are reduced up to 7.2 times and the performance is improved up to 66%. We argue that this improvement comes with little additional hardware complexity and requires no changes to the transactional programming model.

We propose and evaluate a novel approach for automatic parallelization. The approach uses traces as units of parallel work. We discuss the benefits and challenges of the use of traces and propose an execution model for automatic parallelization based on traces. We implement a system that demonstrates the benefits and addresses the challenges of using traces for data-parallel applications in an offline feedback directed system. Finally, we evaluate our system by using it to automatically parallelize three sequential programs that exhibit data-level parallelism from the Java Grande benchmark suite. The resulting performance compares favorably to the performance achieved by hand parallelized versions of these programs. Thus, we demonstrate the viability of trace-based parallelization.

Dynamic voltage scaling (DVS) is an effective method for reducing processor power consumption. We present a compiler-based technique for DVS-based power optimizations of multimedia applications in the context of the Multi-Level Computing Architecture (MLCA) a novel architecture for parallel systems-on-a-chip. Our technique combines dependence analysis of long-running loops with profiling information in order to identify the slack available in the execution of parallel tasks. DVS is then applied to slow down processors executing noncritical-path tasks, reducing power with little or no impact on execution time. We evaluate our technique using realistic multimedia applications and a simulator of the MLCA. The results demonstrate that up to 10% savings in processor power consumption can be achieved with no more than 1.5% increase in execution time. Although our technique is developed in the context of MLCA, we believe that it is applicable in the broader context of task-level parallelism in multimedia applications.

Abstract This paper describes the design, implementation, and experimental evaluation of a modular and extensible Java™ Virtual Machine (JVM) infrastructure, called Jupiter. The infrastructure is intended to serve as a vehicle for our research on scalable JVM architectures for a cluster of PC workstations, with support for shared memory in software. Jupiter is constructed, using a building block architecture, out of many modules with small, simple interfaces. This flexible structure, similar to UNIX® shells that build complex command pipelines out of discrete programs, allows the rapid prototyping of our research ideas by confining changes in JVM design to a small number of modules. In spite of this flexibility, Jupiter delivers good performance. Experimental evaluation of the current implementation of Jupiter using the SPECjvm98 and the EPCC Java Grande single‐threaded and multithreaded benchmarks reflects competitive performance. Jupiter is on average about 2.5 times faster than Kaffe and about 2 times slower than the Sun Microsystems JDK (interpreter versions only). By providing a flexible JVM infrastructure that delivers competitive performance, we believe we have developed a framework that supports further research into JVM scalability. Copyright © 2003 John Wiley & Sons, Ltd.

Wavefront parallelism, in which parallelism is limited to hyperplanes in an iteration space, can arise when compilers apply tiling to loop nests to enhance locality. Previous approaches for scheduling wavefront parallelism focused on maximizing parallelism; balancing workloads, and reducing synchronization. In this paper, we show that on large-scale shared-memory multiprocessors, locality is a crucial factor. We make the distinction between intratile and intertile locality and show that as the number of processors grows, intertile locality becomes more important. We consider and experimentally evaluate existing strategies for scheduling wavefront parallelism. We show that dynamic self-scheduling can be efficiently used on a small number of processors, but performs poorly at large scale because it does not enhance intertile locality. By contrast, static scheduling strategies enhance intertile locality for small tiles, maintaining parallelism and resulting in better performance at large scale. Results from a Convex SPP1000 multiprocessor demonstrate the importance of taking intertile locality into account. Static scheduling outperforms dynamic self-scheduling by a factor of up to 2.3 on 30 processors.

Small-scale multiprocessors are becoming increasingly economical and common, whereas larger multiprocessors continue to have higher per-node costs. The NUMAchine multiprocessor project seeks to make large-scale multiprocessors more economical while maintaining high performance by exploring architectural and hardware features for low-cost, modular multiprocessors. To demonstrate our approach, we have implemented a prototype system that is scalable to 128 processors. An efficient directory-based cache coherence protocol exploits our hierarchical ring-based interconnect and supports sequential consistency. This paper documents the design choices and the resulting performance of the system using both simulation results and measurements on the prototype hardware.

This paper describes an algorithm for deriving data and computation partitions on scalable shared memory multiprocessors. The algorithm establishes affinity relationships between where computations are performed and where data is located based on array accesses in the program. The algorithm then uses these affinity relationships to determine both static and dynamic partitions for arrays and parallel loops. Experimental results from a prototype implementation of the algorithm demonstrate that it is computationally efficient and that it improves the parallel performance of standard benchmarks. The results also show the necessity of taking shared memory effects (memory contention, cache locality, false-sharing and synchronization) into account-partitions derived to minimize only interprocessor communications do not necessarily result in the best performance.

Loop fusion improves data locality and reduces synchronization in data-parallel applications. However, loop fusion is not always legal. Even when legal, fusion may introduce loop-carried dependences which prevent parallelism. In addition, performance losses result from cache conflicts in fused loops. In this paper, we present new techniques to: (1) allow fusion of loop nests in the presence of fusion-preventing dependences, (2) maintain parallelism and allow the parallel execution of fused loops with minimal synchronization, and (3) eliminate cache conflicts in fused loops. We describe algorithms for implementing these techniques in compilers. The techniques are evaluated on a 56-processor KSR2 multiprocessor and on a 18-processor Convex SPP-1000 multiprocessor. The results demonstrate performance improvements for both kernels and complete applications. The results also indicate that careful evaluation of the profitability of fusion is necessary as more processors are used.