Software Pipelined Execution of Stream Programs on GPUs
Authors:
- Abhishek UdupaAUAbhishek Udupa
- R. GovindarajanRGR. Govindarajan
- Matthew J. ThazhuthaveetilMTMatthew J. Thazhuthaveetil
- 1 March 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 200-209
Abstract
The StreamIt programming model has been proposed to exploit parallelism in streaming applications on general purpose multi-core architectures. This model allows programmers to specify the structure of a program as a set of filters that act upon data, and a set of communication channels between them. The StreamIt graphs describe task, data and pipeline parallelism which can be exploited on modern graphics processing units (GPUs), as they support abundant parallelism in hardware. In this paper, we describe the challenges in mapping StreamIt to GPUs and propose an efficient technique to software pipeline the execution of stream programs on GPUs. We formulate this problem - both scheduling and assignment of filters to processors - as an efficient integer linear program (ILP), which is then solved using ILP solvers. We also describe a novel buffer layout technique for GPUs which facilitates exploiting the high memory bandwidth available in GPUs. The proposed scheduling utilizes both the scalar units in GPU, to exploit data parallelism, and multiprocessors, to exploit task and pipeline parallelism. Further it takes into consideration the synchronization and bandwidth limitations of GPUs, and yields speedups between 1.87X and 36.83X over a single threaded CPU.Keywords
This publication has 15 references indexed in Scilit:
- A lightweight streaming layer for multicore executionACM SIGARCH Computer Architecture News, 2008
- Optimization principles and application performance evaluation of a multithreaded GPU using CUDA2008
- Buffer merging—a powerful technique for reducing memory requirements of synchronous dataflow specificationsACM Transactions on Design Automation of Electronic Systems, 2004
- Phased scheduling of stream programs2003
- A novel framework for multi-rate scheduling in DSP applications2002
- Minimizing memory requirements in rate-optimal schedules2002
- A stream compiler for communication-exposed architectures2002
- Looped schedules for dataflow descriptions of multirate signal processing algorithmsFormal Methods in System Design, 1994
- Well-behaved dataflow programs for DSP computation1992
- Static Scheduling of Synchronous Data Flow Programs for Digital Signal ProcessingIEEE Transactions on Computers, 1987