The Experts below are selected from a list of 34995 Experts worldwide ranked by ideXlab platform

Saman Amarasinghe - One of the best experts on this subject based on the ideXlab platform.

  • cimple instruction and memory Level Parallelism a dsl for uncovering ilp and mlp
    International Conference on Parallel Architectures and Compilation Techniques, 2018
    Co-Authors: Vladimir Kiriansky, Martin Rinard, Saman Amarasinghe
    Abstract:

    Modern out-of-order processors have increased capacity to exploit instruction Level Parallelism (ILP) and memory Level Parallelism (MLP), e.g., by using wide superscalar pipelines and vector execution units, as well as deep buffers for inflight memory requests. These resources, however, often exhibit poor utilization rates on workloads with large working sets, e.g., in-memory databases, key-value stores, and graph analytics, as compilers and hardware struggle to expose ILP and MLP from the instruction stream automatically. In this paper, we introduce the IMLP (Instruction and Memory Level Parallelism) task programming model. IMLP tasks execute as coroutines that yield execution at annotated long-latency operations, e.g., memory accesses, divisions, or unpredictable branches. IMLP tasks are interleaved on a single thread, and integrate well with thread Parallelism and vectorization. Our DSL embedded in C++, Cimple, allows exploration of task scheduling and transformations, such as buffering, vectorization, pipelining, and prefetching. We demonstrate state-of-the-art performance on core algorithms used in in-memory databases that operate on arrays, hash tables, trees, and skip lists. Cimple applications reach 2.5× throughput gains over hardware multithreading on a multi-core, and 6.4× single thread speedup.

  • goSLP: Globally Optimized Superword Level Parallelism Framework
    Proceedings of the ACM on Programming Languages, 2018
    Co-Authors: Charith Mendis, Saman Amarasinghe
    Abstract:

    Modern microprocessors are equipped with single instruction multiple data (SIMD) or vector instruction sets which allow compilers to exploit superword Level Parallelism (SLP), a type of fine-grained Parallelism. Current SLP auto-vectorization techniques use heuristics to discover vectorization opportunities in high-Level language code. These heuristics are fragile, local and typically only present one vectorization strategy that is either accepted or rejected by a cost model. We present goSLP, a novel SLP auto-vectorization framework which solves the statement packing problem in a pairwise optimal manner. Using an integer linear programming (ILP) solver, goSLP searches the entire space of statement packing opportunities for a whole function at a time, while limiting total compilation time to a few minutes. Furthermore, goSLP optimally solves the vector permutation selection problem using dynamic programming. We implemented goSLP in the LLVM compiler infrastructure, achieving a geometric mean speedup of 7.58% on SPEC2017fp, 2.42% on SPEC2006fp and 4.07% on NAS benchmarks compared to LLVM's existing SLP auto-vectorizer.

  • Software orchestration of instruction Level Parallelism on tiled processor architectures
    2005
    Co-Authors: Anant Agarwal, Saman Amarasinghe, Walter Lee
    Abstract:

    Projection from silicon technology is that while transistor budget will continue to blossom according to Moore's law, latency from global wires will severely limit the ability to scale centralized structures at high frequencies. A tiled processor architecture (TPA) eliminates long wires from its design by distributing its resources over a pipelined interconnect. By exposing the spatial distribution of these resources to the compiler, a TPA allows the compiler to optimize for locality, thus minimizing the distance that data needs to travel to reach the consuming computation. This thesis examines the compiler problem of exploiting instruction Level Parallelism (ILP) on a TPA. It describes Rawcc, an ILP compiler for Raw, a fully distributed TPA. The thesis examines the implication of the resource distribution on the exploitation of ILP for each of the following resources: instructions, registers, control, data memory, and wires. It designs novel solutions for each one, and it describes the solutions within the integrated framework of a working compiler. Performance is evaluated on a cycle-accurate Raw simulator as well as on a 16-tile Raw chip. Results show that Rawcc can attain modest speedups for fine-grained applications, as well speedups that scale up to 64 tiles for applications with such Parallelism. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)

  • exploiting superword Level Parallelism with multimedia instruction sets
    Programming Language Design and Implementation, 2000
    Co-Authors: Samuel Larsen, Saman Amarasinghe
    Abstract:

    Increasing focus on multimedia applications has prompted the additionof multimedia extensions to most existing general purpose microprocessors. This added functionality comes primarily with the addition of short SIMD instructions. Unfortunately, access to these instructions is limited to in-line assembly and library calls. Generally, it has been assumed that vector compilers provide the most promising means of exploiting multimedia instructions. Although vectorization technology is well understood, it is inherently complex and fragile. In addition, it is incapable of locating SIMD-style Parallelism within a basic block. In this paper we introduce the concept of Superword Level Parallelism (SLP) ,a novel way of viewing Parallelism in multimedia and scientific applications. We believe SLPP is fundamentally different from the loop Level Parallelism exploited by traditional vector processing, and therefore demands a new method of extracting it. We have developed a simple and robust compiler for detecting SLPP that targets basic blocks rather than loop nests. As with techniques designed to extract ILP, ours is able to exploit Parallelism both across loop iterations and within basic blocks. The result is an algorithm that provides excellent performance in several application domains. In our experiments, dynamic instruction counts were reduced by 46%. Speedups ranged from 1.24 to 6.70.

  • space time scheduling of instruction Level Parallelism on a raw machine
    Architectural Support for Programming Languages and Operating Systems, 1998
    Co-Authors: Walter Lee, Rajeev Barua, Matthew I Frank, Devabhaktuni Srikrishna, Jonathan Babb, Vivek Sarkar, Saman Amarasinghe
    Abstract:

    Increasing demand for both greater Parallelism and faster clocks dictate that future generation architectures will need to decentralize their resources and eliminate primitives that require single cycle global communication. A Raw microprocessor distributes all of its resources, including instruction streams, register files, memory ports, and ALUs, over a pipelined two-dimensional mesh interconnect, and exposes them fully to the compiler. Because communication in Raw machines is distributed, compiling for instruction-Level Parallelism (ILP) requires both spatial instruction partitioning as well as traditional temporal instruction scheduling. In addition, the compiler must explicitly manage all communication through the interconnect, including the global synchronization required at branch points. This paper describes RAWCC, the compiler we have developed for compiling general-purpose sequential programs to the distributed Raw architecture. We present performance results that demonstrate that although Raw machines provide no mechanisms for global communication the Raw compiler can schedule to achieve speedups that scale with the number of available functional units.

Mahmut Kandemir - One of the best experts on this subject based on the ideXlab platform.

  • co optimizing memory Level Parallelism and cache Level Parallelism
    Programming Language Design and Implementation, 2019
    Co-Authors: Xulong Tang, Mahmut Kandemir, Mustafa Karakoy, Meenakshi Arunachalam
    Abstract:

    Minimizing cache misses has been the traditional goal in optimizing cache performance using compiler based techniques. However, continuously increasing dataset sizes combined with large numbers of cache banks and memory banks connected using on-chip networks in emerging manycores/accelerators makes cache hit–miss latency optimization as important as cache miss rate minimization. In this paper, we propose compiler support that optimizes both the latencies of last-Level cache (LLC) hits and the latencies of LLC misses. Our approach tries to achieve this goal by improving the Parallelism exhibited by LLC hits and LLC misses. More specifically, it tries to maximize both cache-Level Parallelism (CLP) and memory-Level Parallelism (MLP). This paper presents different incarnations of our approach, and evaluates them using a set of 12 multithreaded applications. Our results indicate that (i) optimizing MLP first and CLP later brings, on average, 11.31% performance improvement over an approach that already minimizes the number of LLC misses, and (ii) optimizing CLP first and MLP later brings 9.43% performance improvement. In comparison, balancing MLP and CLP brings 17.32% performance improvement on average.

  • Improving bank-Level Parallelism for irregular applications
    2016 49th Annual IEEE ACM International Symposium on Microarchitecture (MICRO), 2016
    Co-Authors: Xulong Tang, Praveen Yedlapalli, Mahmut Kandemir, Jagadish Kotra
    Abstract:

    Observing that large multithreaded applications with irregular data access patterns exhibit very low memory bank-Level Parallelism (BLP) during their execution, we propose a novel loop iteration scheduling strategy built upon the inspector-executor paradigm. A unique characteristic of this strategy is that it considers both bank-Level Parallelism (from an inter-core perspective) and bank reuse (from an intra-core perspective) in a unified framework. Its primary goal is to improve bank-Level Parallelism, and bank reuse is taken into account only if doing so does not hurt bank-Level Parallelism. Our experiments with this strategy using eight application programs on both a simulator and a real multicore system show an average BLP improvement of 46.8% and an average execution time reduction of 18.3%.

  • Compiler Support for Optimizing Memory Bank-Level Parallelism
    2014 47th Annual IEEE ACM International Symposium on Microarchitecture, 2014
    Co-Authors: Wei Ding, Diana Guttman, Mahmut Kandemir
    Abstract:

    Many prior compiler-based optimization schemes focused exclusively on cache data locality. However, cache locality is only one part of the overall performance of applications running on emerging multicores or many cores. For example, memory stalls could constitute a very large fraction of execution time even in cache-optimized codes, and one of the main reasons for this is lack of memory-Level Parallelism. Motivated by this, we propose a compiler-based Bank-Level Parallelism (BLP) optimization scheme that uses loop tile scheduling. More specifically, we first use Cache Miss Equations to predict where the last-Level cache miss will happen in each tile, and then identify the set of memory banks that will be accessed in each tile. Using this information, two tile scheduling algorithms are proposed to maximize BLP, each targeting a different scenario. We further discuss how our compiler-based scheme can be enhanced to consider memory controller-Level Parallelism and row-buffer locality. Our experimental evaluation using 11 multithreaded applications shows that the proposed BLP optimization can improve average BLP by 17.1% on average, resulting in a 9.2% reduction in average memory access latency. Furthermore, considering memory controller-Level Parallelism and row-buffer locality (in addition to BLP) takes our average improvement in memory access latency to 22.2%.

  • a compiler framework for extracting superword Level Parallelism
    Programming Language Design and Implementation, 2012
    Co-Authors: Jun Liu, Wei Ding, Yuanrui Zhang, Ohyoung Jang, Mahmut Kandemir
    Abstract:

    SIMD (single-instruction multiple-data) instruction set extensions are quite common today in both high performance and embedded microprocessors, and enable the exploitation of a specific type of data Parallelism called SLP (Superword Level Parallelism). While prior research shows that significant performance savings are possible when SLP is exploited, placing SIMD instructions in an application code manually can be very difficult and error prone. In this paper, we propose a novel automated compiler framework for improving superword Level Parallelism exploitation. The key part of our framework consists of two stages: superword statement generation and data layout optimization. The first stage is our main contribution and has two phases, statement grouping and statement scheduling, of which the primary goals are to increase SIMD Parallelism and, more importantly, capture more superword reuses among the superword statements through global data access and reuse pattern analysis. Further, as a complementary optimization, our data layout optimization organizes data in memory space such that the price of memory operations for SLP is minimized. The results from our compiler implementation and tests on two systems indicate performance improvements as high as 15.2% over a state-of-the-art SLP optimization algorithm.

Ce Guo - One of the best experts on this subject based on the ideXlab platform.

  • towards efficient deep neural network training by fpga based batch Level Parallelism
    Journal of Semiconductors, 2020
    Co-Authors: Cheng Luo, Mankit Sit, Hongxiang Fan, Shuanglong Liu, Wayne Luk, Ce Guo
    Abstract:

    Training deep neural networks (DNNs) requires a significant amount of time and resources to obtain acceptable results, which severely limits its deployment in resource-limited platforms. This paper proposes DarkFPGA, a novel customizable framework to efficiently accelerate the entire DNN training on a single FPGA platform. First, we explore batch-Level Parallelism to enable efficient FPGA-based DNN training. Second, we devise a novel hardware architecture optimised by a batch-oriented data pattern and tiling techniques to effectively exploit Parallelism. Moreover, an analytical model is developed to determine the optimal design parameters for the DarkFPGA accelerator with respect to a specific network specification and FPGA resource constraints. Our results show that the accelerator is able to perform about 10 times faster than CPU training and about a third of the energy consumption than GPU training using 8-bit integers for training VGG-like networks on the CIFAR dataset for the Maxeler MAX5 platform.

  • towards efficient deep neural network training by fpga based batch Level Parallelism
    Field-Programmable Custom Computing Machines, 2019
    Co-Authors: Cheng Luo, Mankit Sit, Hongxiang Fan, Shuanglong Liu, Wayne Luk, Ce Guo
    Abstract:

    Training Deep Neural Networks (DNNs) requires a significant amount of time and resources to obtain acceptable results, which severely limits its deployment in resource-limited platforms. This paper proposes DarkFPGA, a novel customizable framework to efficiently accelerate the entire DNN training on a single FPGA platform. First, we explore batch-Level Parallelism to enable efficient training on FPGAs. Second, we devise a novel hardware architecture optimised by a batch-oriented data pattern and tiling techniques to effectively exploit Parallelism. Moreover, an analytical model is developed to determine the optimal design parameters for the DarkFPGA accelerator with respect to a specific network specification and FPGA resource constraints. Our results show that the accelerator is able to perform about 11 times faster than CPU training and about a third of the energy consumption than GPU training using 8-bit integers for training VGG-like networks on the CIFAR dataset for the Maxeler MAX5 platform.

Cheng Luo - One of the best experts on this subject based on the ideXlab platform.

  • towards efficient deep neural network training by fpga based batch Level Parallelism
    Journal of Semiconductors, 2020
    Co-Authors: Cheng Luo, Mankit Sit, Hongxiang Fan, Shuanglong Liu, Wayne Luk, Ce Guo
    Abstract:

    Training deep neural networks (DNNs) requires a significant amount of time and resources to obtain acceptable results, which severely limits its deployment in resource-limited platforms. This paper proposes DarkFPGA, a novel customizable framework to efficiently accelerate the entire DNN training on a single FPGA platform. First, we explore batch-Level Parallelism to enable efficient FPGA-based DNN training. Second, we devise a novel hardware architecture optimised by a batch-oriented data pattern and tiling techniques to effectively exploit Parallelism. Moreover, an analytical model is developed to determine the optimal design parameters for the DarkFPGA accelerator with respect to a specific network specification and FPGA resource constraints. Our results show that the accelerator is able to perform about 10 times faster than CPU training and about a third of the energy consumption than GPU training using 8-bit integers for training VGG-like networks on the CIFAR dataset for the Maxeler MAX5 platform.

  • towards efficient deep neural network training by fpga based batch Level Parallelism
    Field-Programmable Custom Computing Machines, 2019
    Co-Authors: Cheng Luo, Mankit Sit, Hongxiang Fan, Shuanglong Liu, Wayne Luk, Ce Guo
    Abstract:

    Training Deep Neural Networks (DNNs) requires a significant amount of time and resources to obtain acceptable results, which severely limits its deployment in resource-limited platforms. This paper proposes DarkFPGA, a novel customizable framework to efficiently accelerate the entire DNN training on a single FPGA platform. First, we explore batch-Level Parallelism to enable efficient training on FPGAs. Second, we devise a novel hardware architecture optimised by a batch-oriented data pattern and tiling techniques to effectively exploit Parallelism. Moreover, an analytical model is developed to determine the optimal design parameters for the DarkFPGA accelerator with respect to a specific network specification and FPGA resource constraints. Our results show that the accelerator is able to perform about 11 times faster than CPU training and about a third of the energy consumption than GPU training using 8-bit integers for training VGG-like networks on the CIFAR dataset for the Maxeler MAX5 platform.

D Verkest - One of the best experts on this subject based on the ideXlab platform.

  • software simultaneous multi threading a technique to exploit task Level Parallelism to improve instruction and data Level Parallelism
    Lecture Notes in Computer Science, 2006
    Co-Authors: Daniele Paolo Scarpazza, Praveen Raghavan, Francky Catthoor, David Novo, D Verkest
    Abstract:

    The search for energy efficiency in the design of embedded systems is leading toward CPUs with higher instruction-Level and data-Level Parallelism. Unfortunately, individual applications do not have sufficient Parallelism to keep all these CPU resources busy. Since embedded systems often consist of multiple tasks, task-Level Parallelism can be used for the purpose. Simultaneous multi-threading (SMT) proved a valuable technique to do so in high-performance systems, but it cannot be afforded in system with tight energy budgets. Moreover, it does not exploit data-Level parallel hardware, and does not exploit the available information on threads. We propose software-SMT (SW-SMT), a technique to exploit task-Level Parallelism to improve the utilization of both instruction-Level and data-Level parallel hardware, thereby improving performance. The technique performs simultaneous compilation of multiple threads at design-time, and it includes a run-time selection of the most efficient mixes. We have applied the technique to two major blocks of a SDR (software-defined radio) application, achieving energy gains up to 46% on different ILP and DLP architectures. We show that the potentials of SW-SMT increase with SIMD datapath size and VLIW issue width.

  • performance analysis for identification of sub task Level Parallelism in java
    Software and Compilers for Embedded Systems, 2003
    Co-Authors: Richard Stahl, Robert Pasko, Luc Rijnders, D Verkest, Serge Vernalde, Rudy Leuwereins, Francky Catthoor
    Abstract:

    In the era of future embedded systems the designer is confronted with multiple processors both for performance and energy reasons. Exploiting (sub-)task-Level Parallelism is crucial when targeting those multi-processor systems, because ILP on itself is not sufficient.

  • exploiting loop Level Parallelism on coarse grained reconfigurable architectures using modulo scheduling
    Design Automation and Test in Europe, 2003
    Co-Authors: Bingfeng Mei, D Verkest, Serge Vernalde, H De Man, R Lauwereins
    Abstract:

    Coarse-grained reconfigurable architectures have become increasingly important in recent years. Automatic design or compilation tools are essential to their success. In this paper, we present a modulo scheduling algorithm to exploit loop-Level Parallelism for coarse-grained reconfigurable architectures. This algorithm is a key part of our dynamically reconfigurable embedded systems compiler (DRESC). It is capable of solving placement, scheduling and routing of operations simultaneously in a modulo-constrained 3D space and uses an abstract architecture representation to model a wide class of coarse-grained architectures. The experimental results show high performance and efficient resource utilization on tested kernels.