Article

Free access

Optimal latency-throughput tradeoffs for data parallel pipelines

Authors:

Jaspar Subhlok,

Gary VondranAuthors Info & Claims

SPAA '96: Proceedings of the eighth annual ACM symposium on Parallel Algorithms and Architectures

Pages 62 - 71

https://doi.org/10.1145/237502.237508

Published: 24 June 1996 Publication History

PDF eReader

References

[1]

BOKHARI, S. Assignment Problems zn Parallel and Distributed Computing. Kluwer Academic Publishers, 1987.]]

Digital Library

Google Scholar

[2]

CHAKRABARTI, S., DEMMEL, J., AND YELICK, K. Modeling the benefits of mixed data and task parallelism. In Seventh Annual A CM Symposium on Parallel Algomthms and Architectures (Santa Barbara, CA, July 1995).]]

Digital Library

Google Scholar

[3]

CHANDY, M., FOSTER, I., KENNEDY, #., KOELBEL, C., AND TSENG, C. Integrated support for task and data parallelism. International dournal of Supercomputer Applicat,ons 8, 2 (1994), 80-98.]]

Google Scholar

[4]

CHAPMAN, B., MEHROTRA, P., VAN ROSENDALE, J., AND ZIMA, H. A software architecture for multidisciplinary applications: Integrating task and data parallelism. Tech. Rep. 94-18, ICASE, NASA Langley Research Center, Hampton, VA, Mar. 1994.]]

Digital Library

Google Scholar

[5]

#HOUDHARY, A., NARAHARI, B., NICOL, D., AND SIMttA, R. Optimal processor assignment for a class of pipelined computations. IEEE Transactions on Parallel and Distributed Systems 5, 4 (April 94), 439-445.]]

Digital Library

Google Scholar

[6]

CROWL, L., CROVELLA, M., LEBLANC, T., AND SCOTT, M. The advantages of multiple parallelizations in combinatorial search. Journal of Parallel and Dzstmbuted Computing 21 (1994), 110-123.]]

Digital Library

Google Scholar

[7]

DINDA, P., GROSS, T., O'HALLARON, D., SEGALL, E., STICHNOTH, J., SUBHLOK, J., WEBB, J., AND YANG, B. The CMU task parallel program suite. Tech. Rep. CMU-CS-94-131, School of Computer Science, Carnegie Mellon University, Mar. 1994.]]

Google Scholar

[8]

FOSTER, I., AVALANI, B., CHOUDHARY, A., AND XU, M. A compilation system that integrates High Performance Fortran and Fortran M. In Proceeding of 1994 Scalable High Performance Comput,ng Conference (Knoxville, TN, October 1994), pp. 293-300.]]

Google Scholar

[9]

Gaoss, T., O'HALLARON, D., AND SUBHLOK, J. Task parallelism in a High Performance Fortran framework. IEEE Parallel # Distributed Technology, 3 (1994), 16- 26.]]

Digital Library

Google Scholar

[10]

HICH PERFORMANCE FORTRAN FORUM. High Performance Fortran Language Specification, Version 1.0, May 1993.]]

Google Scholar

[11]

RAMASWAMY, S., SAPATNEKAR, S., AND BANERJEE, P. A convex programming approach for exploiting data and functional parallelism. In Proceedings of the 1994 International Conference on Parallel Processing (St Charles, IL, August 1994), vol. 2, pp. 116-125.]]

Digital Library

Google Scholar

[12]

SARKAR, V. Partitioning and Scheduling Parallel Programs for Multiprocessors. The MIT Press, Cambridge, MA, 1989.]]

Digital Library

Google Scholar

[13]

SUBHLOK, J., O'HALLARON, D., GROSS, T., DINDA, P., AND WEBB, J. Communication and memory requirements as the basis for mapping task and data parallel programs. In Supcrcomputing '94 (Washington, DC, November 1994), pp. 330-339.]]

Crossref

Google Scholar

[14]

SUBHLOK, J., STICHNOTH, J., O'HALLARON, D., AND GRoss, T. Exploiting task and data parallelism on multicomputer. In ACM SIGPLAN Sympos,um on Pmnciples and Practice of Parallel Programming (San Diego, CA, May 1993), pp. 13-22.]]

Digital Library

Google Scholar

[15]

SUBHLOK, J., AND VONDRAN, G. Optimal mapping of sequences of data parallel tasks. In Proceedzngs of the Fifth A CM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Santa Barbara, CA, July 1995), pp. 134-143.]]

Digital Library

Google Scholar

[16]

VONDRAN, G. Optimization of latency, throughput and processors for pipelines of data parallel tasks. Master's thesis, Dept. of Electrical and Computer Engineering, Carnegie Mellon University, May 1995.]]

Google Scholar

[17]

WEB#, J. Latency and bandwidth consideration in parallel robotics image processing. In Supercomputzng '93 (Port}#nd, OR, Nov. 1993), pp. 230-239.]]

Digital Library

Google Scholar

[18]

YANG, B., WEBB, J., STICHNOTH, J., O'HALLARON, D., AND GROSS, T. Do&merge: Integrating parallel loops and reductions. In Sixth Annual Workshop on Languages and Compilers for Parallel Computing (Portland, Oregon, Aug 1993).]]

Digital Library

Google Scholar

[19]

YANG, T. Scheduling and Code Generat,on }or Parallel Architectures. PhD thesis, Rutgers University, May 1993.]]

Digital Library

Google Scholar

Cited By

View all

Shin YPark JCho SSung HDubach CBruening DHardekopf B(2023)PIMFlow: Compiler and Runtime Support for CNN Models on Processing-in-Memory DRAMProceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3579990.3580009(249-262)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3579990.3580009
Gutierrez JBohm Agostini NKaeli DBourcier JJiang ZBezemer CCortellessa V(2021)Performance Evaluation and Improvement of Real-Time Computer Vision Applications for Edge Computing DevicesCompanion of the ACM/SPEC International Conference on Performance Engineering10.1145/3447545.3451202(139-144)Online publication date: 19-Apr-2021
https://dl.acm.org/doi/10.1145/3447545.3451202
Timcheck SBuhler J(2021)Reducing queuing impact in streaming applications with irregular dataflowParallel Computing10.1016/j.parco.2021.102863(102863)Online publication date: Nov-2021
https://doi.org/10.1016/j.parco.2021.102863
Show More Cited By

Index Terms

Optimal latency-throughput tradeoffs for data parallel pipelines

Recommendations

Understanding Parallelization Tradeoffs for Linear Pipelines
PMAM'18: Proceedings of the 9th International Workshop on Programming Models and Applications for Multicores and Manycores

Pipelining techniques execute some loops with cross-iteration dependences in parallel, by partitioning the loop body into a sequence of stages such that the data dependences are not violated. Obtaining good performance for all kinds of loops is ...
Throughput maximization in multiprocessor speed-scaling

In the classical energy minimization problem, introduced in 24, we are given a set of n jobs each one characterized by its release date, its deadline, its processing volume and we aim to find a feasible schedule of the jobs on a single speed-scalable ...
Throughput Maximization in Multiprocessor Speed-Scaling
Algorithms and Computation
Abstract
In the classical energy minimization problem, introduced in [Yao et al., FOCS’95], we are given a set of jobs each one characterized by its release date, its deadline, its processing volume and we aim to find a feasible schedule of the jobs on a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SPAA '96: Proceedings of the eighth annual ACM symposium on Parallel Algorithms and Architectures

June 1996

337 pages

ISBN:0897918096

DOI:10.1145/237502

Chairman:
Guy E. Blelloch
CMU

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 June 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

8SPAA96

Sponsor:

8SPAA96: 8th Annual ACM Symposium on Parallel

June 24 - 26, 1996

Padua, Italy

Acceptance Rates

SPAA '96 Paper Acceptance Rate 39 of 106 submissions, 37%;

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

76
Total Citations
View Citations
798
Total Downloads

Downloads (Last 12 months)85
Downloads (Last 6 weeks)15

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Shin YPark JCho SSung HDubach CBruening DHardekopf B(2023)PIMFlow: Compiler and Runtime Support for CNN Models on Processing-in-Memory DRAMProceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3579990.3580009(249-262)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3579990.3580009
Gutierrez JBohm Agostini NKaeli DBourcier JJiang ZBezemer CCortellessa V(2021)Performance Evaluation and Improvement of Real-Time Computer Vision Applications for Edge Computing DevicesCompanion of the ACM/SPEC International Conference on Performance Engineering10.1145/3447545.3451202(139-144)Online publication date: 19-Apr-2021
https://dl.acm.org/doi/10.1145/3447545.3451202
Timcheck SBuhler J(2021)Reducing queuing impact in streaming applications with irregular dataflowParallel Computing10.1016/j.parco.2021.102863(102863)Online publication date: Nov-2021
https://doi.org/10.1016/j.parco.2021.102863
Timcheck SBuhler J(2020)Reducing Queuing Impact in Irregular Data Streaming Applications2020 IEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3)10.1109/IA351965.2020.00009(22-30)Online publication date: Nov-2020
https://doi.org/10.1109/IA351965.2020.00009
Wu SLiu ZIbrahim SGu LJin HChen F(2018)Dual-Paradigm Stream ProcessingProceedings of the 47th International Conference on Parallel Processing10.1145/3225058.3225120(1-10)Online publication date: 13-Aug-2018
https://dl.acm.org/doi/10.1145/3225058.3225120
Mastoras AGross T(2018)Understanding Parallelization Tradeoffs for Linear PipelinesProceedings of the 9th International Workshop on Programming Models and Applications for Multicores and Manycores10.1145/3178442.3178443(1-10)Online publication date: 24-Feb-2018
https://dl.acm.org/doi/10.1145/3178442.3178443
Mastoras AGross T(2018)Unifying Fixed Code Mapping, Communication, Synchronization and Scheduling Algorithms for Efficient and Scalable Loop PipeliningIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2018.281720729:9(2136-2149)Online publication date: 1-Sep-2018
https://doi.org/10.1109/TPDS.2018.2817207
Rottenstreich OKeslassy IRevah YKadosh A(2017)Minimizing Delay in Network Function Virtualization with Shared PipelinesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2016.255667028:1(156-169)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1109/TPDS.2016.2556670
Kaci ANguyen HNakib ASiarry P(2016)Hybrid Heuristics for Mapping Task Problem on Large Scale Heterogeneous Platforms2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)10.1109/IPDPSW.2016.163(809-816)Online publication date: May-2016
https://doi.org/10.1109/IPDPSW.2016.163
Benoit ACoqblin MNicod JRehn-Sonigo V(2016)Optimizing memory allocation for multistage scheduling including setup timesJournal of Scheduling10.1007/s10951-015-0437-x19:6(641-658)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1007/s10951-015-0437-x
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Understanding Parallelization Tradeoffs for Linear Pipelines

Throughput maximization in multiprocessor speed-scaling

Throughput Maximization in Multiprocessor Speed-Scaling