Exploiting coarse-grained task, data, and pipeline parallelism in stream programs
The DOI matches its Crossref record; 19 of the 19 references it cites were found in a registry or an index.
Abstract
As multicore architectures enter the mainstream, there is a pressing demand for high-level programming models that can effectively map to them. Stream programming offers an attractive way to expose coarse-grained parallelism, as streaming applications (image, video, DSP, etc.) are naturally represented by independent filters that communicate over explicit data channels.In this paper, we demonstrate an end-to-end stream compiler that attains robust multicore performance in the face of varying application characteristics. As benchmarks exhibit different amounts of task, data, and pipeline parallelism, we exploit all types of parallelism in a unified manner in order to achieve this generality. Our compiler, which maps from the StreamIt language to the 16-core Raw architecture, attains a 11.2x mean speedup over a single-core baseline, and a 1.84x speedup over our previous work.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
Introduction to the Theory of Computation
Sipser, M. (1996) · ACM SIGACT News · doi:10.1145/230514.571645 · Cited by 2,784
Static Scheduling of Synchronous Data Flow Programs for Digital Signal Processing
Lee, E. A., & Messerschmitt, D. G. (1987) · IEEE Transactions on Computers · doi:10.1109/tc.1987.5009446 · Cited by 1,318
Static scheduling algorithms for allocating directed task graphs to multiprocessors
Kwok, Y.-K., & Ahmad, I. (1999) · ACM Computing Surveys · doi:10.1145/344588.344618 · Cited by 1,314
Brook for GPUs: stream computing on graphics hardware
Buck, I., Foley, T., Horn, D., Sugerman, J., Fatahalian, K., Houston, M., & Hanrahan, P. (2004) · ACM Transactions on Graphics · doi:10.1145/1015706.1015800 · Cited by 1,155
StreamIt: A Language for Streaming Applications
Thies, W., Karczmarek, M., & Amarasinghe, S. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45937-5_14 · Cited by 1,104
Self-citationCg: a system for programming graphics hardware in a C-like language
Mark, W. R., Glanville, R. S., Akeley, K., & Kilgard, M. J. (2003) · ACM SIGGRAPH Conference (SIGGRAPH) · doi:10.1145/1201775.882362 · Cited by 565
Static rate-optimal scheduling of iterative data-flow programs via optimum unfolding
Parhi, K. K., & Messerschmitt, D. G. (1991) · IEEE Transactions on Computers · doi:10.1109/12.73588 · Cited by 364
Evaluation of the Raw Microprocessor
Taylor, M. B., Lee, W., Miller, J. E., Wentzlaff, D., Bratt, I., Greenwald, B., Hoffmann, H., Johnson, P., Kim, J. Z., Psota, J., et al. (2004) · ACM SIGARCH Computer Architecture News · doi:10.1145/1028176.1006733 · Cited by 353
Self-citationPower Efficient Processor Architecture and The Cell Processor
Hofstee, H. P. (2005) · 11th International Symposium on High-Performance Computer Architecture · doi:10.1109/hpca.2005.26 · Cited by 346
A stream compiler for communication-exposed architectures
Gordon, M. I., Thies, W., Karczmarek, M., Lin, J., Meli, A. S., Lamb, A. A., Leger, C., Wong, J., Hoffmann, H., Maze, D., et al. (2002) · Proceedings of the 10th international conference on Architectural support for programming languages and operating systems · doi:10.1145/605397.605428 · Cited by 337
Self-citationStephens, R. (1997) · Acta Informatica · doi:10.1007/s002360050095 · Cited by 322
Automatic Thread Extraction with Decoupled Software Pipelining
Ottoni, G., Rangan, R., Stoler, A., & August, D. I. (2006) · 38th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO'05) · doi:10.1109/micro.2005.13 · Cited by 273
Cg: a system for programming graphics hardware in a C-like language
Mark, W. R., Glanville, R. S., Akeley, K., & Kilgard, M. J. (2003) · ACM Transactions on Graphics · doi:10.1145/882262.882362 · Cited by 214
Data and Computation Transformations for Brook Streaming Applications on Multiprocessors
Liao, S.-W., Du, Z.-H., Wu, G., & Lueh, G.-Y. (2006) · Proceedings of the CGO/Proceedings of the ... CGO · doi:10.1109/cgo.2006.13 · Cited by 108
Cache aware optimization of stream programs
Sermulins, J., Thies, W., Rabbah, R., & Amarasinghe, S. P. (2005) · ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES) · doi:10.1145/1065910.1065927 · Cited by 76
Self-citationLinear analysis and optimization of stream programs
Lamb, A. A., Thies, W., & Amarasinghe, S. P. (2003) · ACM SIGPLAN Notices · doi:10.1145/780822.781134 · Cited by 39
Self-citationOptimizing stream programs using linear state space analysis
Agrawal, S., Thies, W., & Amarasinghe, S. P. (2005) · International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES) · doi:10.1145/1086297.1086315 · Cited by 32
Self-citationLinear analysis and optimization of stream programs
Lamb, A. A., Thies, W., & Amarasinghe, S. P. (2003) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/781131.781134 · Cited by 25
Self-citation
Cited by
Cooperative Caching for Chip Multiprocessors
Chang, J., & Sohi, G. S. (2006) · ACM SIGARCH Computer Architecture News · doi:10.1145/1150019.1136509 · Cited by 355
The tao of parallelism in algorithms
Pingali, K., Nguyen, D., Kulkarni, M., Burtscher, M., Hassaan, M. A., Kaleem, R., Lee, T.-H., Lenharth, A., Manevich, R., Méndez-Lojo, M., et al. (2011) · ACM SIGPLAN Notices · doi:10.1145/1993316.1993501 · Cited by 312
A catalog of stream processing optimizations
Hirzel, M., Soulé, R., Schneider, S., Gedik, B., & Grimm, R. (2014) · ACM Computing Surveys · doi:10.1145/2528412 · Cited by 299
A Practical Approach to Exploiting Coarse-Grained Pipeline Parallelism in C Programs
Thies, W., Chandrasekhar, V., & Amarasinghe, S. (2007) · 40th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO 2007) · doi:10.1109/micro.2007.38 · Cited by 274
Self-citationA monad for deterministic parallelism
Marlow, S., Newton, R., & Peyton Jones, S. (2011) · Proceedings of the 4th ACM symposium on Haskell · doi:10.1145/2034675.2034685 · Cited by 98
Metadata
- Authors
- Gordon, M. I., Thies, W., & Amarasinghe, S.
- Venue
- Proceedings of the 12th international conference on Architectural support for programming languages and operating systems
- Publisher
- ACM
- Published
- 2006-10-20
- Pages
- 151-162
- OpenAlex
- W2165100134
- Cited by
- 512
- References
- 19
- FWCI
- 30.98
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.