Reducing queuing impact in streaming applications with irregular dataflow.
Saved in:
| Title: | Reducing queuing impact in streaming applications with irregular dataflow. |
|---|---|
| Authors: | Timcheck, Stephen1 (AUTHOR) stimcheck@wustl.edu, Buhler, Jeremy1 (AUTHOR) |
| Source: | Parallel Computing. Mar2022, Vol. 109, pN.PAG-N.PAG. 1p. |
| Subjects: | Queuing theory, Analytical solutions |
| Abstract: | Throughput-oriented streaming applications on massive data sets are a prime candidate for parallelization on wide-SIMD platforms, especially when inputs are independent of one another. Many such applications are represented as a pipeline of compute nodes connected by directed edges. Here, we study applications with irregular dataflow, i.e., those where the number of outputs produced per input to a node is data-dependent and unknown a priori. We consider how to implement such applications on wide-SIMD architectures, such as GPUs, where different nodes of the pipeline execute cooperatively on a single processor. To promote greater SIMD parallelism, irregular application pipelines can utilize queues to gather and compact multiple data items between nodes. However, the decision to introduce a queue between two nodes must trade off benefits to occupancy against costs associated with managing the queue and scheduling the nodes at its endpoints. Moreover, once queues are introduced to an application, their relative sizes impact the frequency with which the application switches between nodes, incurring scheduling and context-switching overhead. This work examines two optimization problems associated with queues. First, given a pipeline with queues between each two nodes and a fixed total budget for queue space, we consider how to choose the relative sizes of inter-node queues to minimize the frequency of switching between nodes. Second, we consider which pairs of successive nodes in a pipeline should have queues between them to maximize overall application throughput. We give an empirically useful approximation to the first problem that allows for an analytical solution and formulate a performance model for the second that directs implementation toward higher-performing strategies. We implemented our analyses and resulting optimizations in applications built using Mercator, a framework we designed to support irregular streaming applications on NVIDIA GPUs. We demonstrate that these optimizations yield meaningful performance improvements for several benchmark Mercator applications. • The Mercator framework supports irregular dataflow computations on SIMD platforms. • Queues in Mercator improve SIMD parallelism but incur runtime overhead. • We show how to select queue sizes given a fixed space budget to maximize throughput. • We decide whether to insert queues by modeling their impact on throughput. • We validated our optimizations on irregular dataflow applications using Mercator. [ABSTRACT FROM AUTHOR] |
| Copyright of Parallel Computing is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 154245105 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Reducing queuing impact in streaming applications with irregular dataflow. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Timcheck%2C+Stephen%22">Timcheck, Stephen</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> stimcheck@wustl.edu</i><br /><searchLink fieldCode="AR" term="%22Buhler%2C+Jeremy%22">Buhler, Jeremy</searchLink><relatesTo>1</relatesTo> (AUTHOR) – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Parallel+Computing%22">Parallel Computing</searchLink>. Mar2022, Vol. 109, pN.PAG-N.PAG. 1p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Queuing+theory%22">Queuing theory</searchLink><br /><searchLink fieldCode="DE" term="%22Analytical+solutions%22">Analytical solutions</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Throughput-oriented streaming applications on massive data sets are a prime candidate for parallelization on wide-SIMD platforms, especially when inputs are independent of one another. Many such applications are represented as a pipeline of compute nodes connected by directed edges. Here, we study applications with irregular dataflow, i.e., those where the number of outputs produced per input to a node is data-dependent and unknown a priori. We consider how to implement such applications on wide-SIMD architectures, such as GPUs, where different nodes of the pipeline execute cooperatively on a single processor. To promote greater SIMD parallelism, irregular application pipelines can utilize queues to gather and compact multiple data items between nodes. However, the decision to introduce a queue between two nodes must trade off benefits to occupancy against costs associated with managing the queue and scheduling the nodes at its endpoints. Moreover, once queues are introduced to an application, their relative sizes impact the frequency with which the application switches between nodes, incurring scheduling and context-switching overhead. This work examines two optimization problems associated with queues. First, given a pipeline with queues between each two nodes and a fixed total budget for queue space, we consider how to choose the relative sizes of inter-node queues to minimize the frequency of switching between nodes. Second, we consider which pairs of successive nodes in a pipeline should have queues between them to maximize overall application throughput. We give an empirically useful approximation to the first problem that allows for an analytical solution and formulate a performance model for the second that directs implementation toward higher-performing strategies. We implemented our analyses and resulting optimizations in applications built using Mercator, a framework we designed to support irregular streaming applications on NVIDIA GPUs. We demonstrate that these optimizations yield meaningful performance improvements for several benchmark Mercator applications. • The Mercator framework supports irregular dataflow computations on SIMD platforms. • Queues in Mercator improve SIMD parallelism but incur runtime overhead. • We show how to select queue sizes given a fixed space budget to maximize throughput. • We decide whether to insert queues by modeling their impact on throughput. • We validated our optimizations on irregular dataflow applications using Mercator. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Parallel Computing is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=154245105 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1016/j.parco.2021.102863 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 1 StartPage: N.PAG Subjects: – SubjectFull: Queuing theory Type: general – SubjectFull: Analytical solutions Type: general Titles: – TitleFull: Reducing queuing impact in streaming applications with irregular dataflow. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Timcheck, Stephen – PersonEntity: Name: NameFull: Buhler, Jeremy IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 03 Text: Mar2022 Type: published Y: 2022 Identifiers: – Type: issn-print Value: 01678191 Numbering: – Type: volume Value: 109 Titles: – TitleFull: Parallel Computing Type: main |
| ResultId | 1 |
