{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:44:38Z","timestamp":1740123878133,"version":"3.37.3"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,12,5]],"date-time":"2022-12-05T00:00:00Z","timestamp":1670198400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,12,5]],"date-time":"2022-12-05T00:00:00Z","timestamp":1670198400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1763503","CNS-1763503"],"award-info":[{"award-number":["CNS-1763503","CNS-1763503"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Parallel Prog"],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Streaming dataflow applications are an attractive target to parallelize on wide-SIMD processors such as GPUs. These applications can be expressed as a pipeline of compute nodes connected by edges, which feed outputs from one node to the next. Streaming applications often exhibit irregular dataflow, where the amount of output produced for one input is unknown <jats:italic>a priori<\/jats:italic>. Inserting finite queues between pipeline nodes can ameliorate the impact of irregularity and improve SIMD lane occupancy. The sizing of these queues is driven by both performance and safety considerations- relative queue sizes should be chosen to reduce runtime overhead and maximize throughput, but each node\u2019s output queue must be large enough to accommodate the maximum number of outputs produced by one SIMD vector of inputs to the node. When safety and performance considerations conflict, the application may incur excessive memory usage and runtime overhead. In this work, we identify properties of applications that lead to such undesirable behaviors, with examples from applications implemented in our MERCATOR framework for irregular streaming on GPUs. To address these issues, we propose extensions to support <jats:italic>interruptible nodes<\/jats:italic> that can be suspended mid-execution if their output queues fill. We illustrate the impacts of adding interruptible nodes to the MERCATOR framework on representative irregular streaming applications from the domains of branching search and bioinformatics.<\/jats:p>","DOI":"10.1007\/s10766-022-00745-2","type":"journal-article","created":{"date-parts":[[2022,12,5]],"date-time":"2022-12-05T16:04:55Z","timestamp":1670256295000},"page":"43-60","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Interruptible Nodes: Reducing Queueing Costs in Irregular Streaming Dataflow Applications on Wide-SIMD Architectures"],"prefix":"10.1007","volume":"51","author":[{"given":"Stephen","family":"Timcheck","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeremy","family":"Buhler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,12,5]]},"reference":[{"issue":"3","key":"745_CR1","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"SF Altschul","year":"1990","unstructured":"Altschul, S.F., Gish, W., Miller, W., Myers, E.W., Lipman, D.J.: Basic local alignment search tool. J. Molecul. Biol. 215(3), 403\u2013410 (1990)","journal-title":"J. Molecul. Biol."},{"key":"745_CR2","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1016\/j.nima.2008.06.047","volume":"595","author":"E Tyson","year":"2008","unstructured":"Tyson, E., Buckley, J., Franklin, M., Chamberlain, R.: Acceleration of atmospheric Cherenkov telescope signal processing to real-time speed with the auto-pipe design system. Nucl. Instrum. Methods Phys. Res. Sect. A Accel. Spectrometers Detect. Assoc. Equip. 595, 474\u2013479 (2008)","journal-title":"Nucl. Instrum. Methods Phys. Res. Sect. A Accel. Spectrometers Detect. Assoc. Equip."},{"key":"745_CR3","doi-asserted-by":"crossref","unstructured":"Cabrera, A.M., Faber, C.J., Cepeda, K., Derber, R., Epstein, C., Zheng, J., Cytron, R.K., Chamberlain, R.D.: DIBS: a data integration benchmark suite. In: Companion of the 2018 ACM\/SPEC International Conference on Performance Engineering. ICPE \u201918, pp. 25\u201328. Association for Computing Machinery, New York, NY, USA (2018)","DOI":"10.1145\/3185768.3186307"},{"key":"745_CR4","unstructured":"Roesch, M.: Snort - lightweight intrusion detection for networks. In: Proceedings of the 13th USENIX Conference on System Administration. LISA \u201999, pp. 229\u2013238. USENIX Association, USA (1999)"},{"issue":"9","key":"745_CR5","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1287\/mnsc.13.9.723","volume":"13","author":"PJ Kolesar","year":"1967","unstructured":"Kolesar, P.J.: A branch and bound algorithm for the knapsack problem. Manag. Sci. 13(9), 723\u2013735 (1967)","journal-title":"Manag. Sci."},{"key":"745_CR6","unstructured":"Viola, P., Jones, M.: Robust real-time object detection. In: International Journal of Computer Vision (2001)"},{"key":"745_CR7","doi-asserted-by":"crossref","unstructured":"Cole, S.V., Buhler, J.: MERCATOR: A GPGPU framework for irregular streaming applications. In: 2017 International Conference on High Performance Computing Simulation (HPCS), pp. 727\u2013736 (2017)","DOI":"10.1109\/HPCS.2017.111"},{"key":"745_CR8","doi-asserted-by":"publisher","first-page":"102863","DOI":"10.1016\/j.parco.2021.102863","volume":"109","author":"S Timcheck","year":"2022","unstructured":"Timcheck, S., Buhler, J.: Reducing queuing impact in streaming applications with irregular dataflow. Parallel Comput. 109, 102863 (2022)","journal-title":"Parallel Comput."},{"key":"745_CR9","doi-asserted-by":"crossref","unstructured":"Plano, T., Buhler, J.: Scheduling irregular dataflow pipelines on SIMD architectures. In: Proceedings of the 2020 Sixth Workshop on Programming Models for SIMD\/Vector Processing. WPMVP\u201920, pp. 1\u20139. Association for Computing Machinery, New York, NY, USA (2020)","DOI":"10.1145\/3380479.3380480"},{"key":"745_CR10","doi-asserted-by":"crossref","unstructured":"Kim, H., Patel, P., Wang, S., Rajkumar, R.R.: A server-based approach for predictable GPU access control. In: 2017 IEEE 23rd International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pp. 1\u201310. IEEE (2017)","DOI":"10.1109\/RTCSA.2017.8046309"},{"key":"745_CR11","unstructured":"Kato, S., Lakshmanan, K., Rajkumar, R., Ishikawa, Y., et al: TimeGraph: GPU scheduling for real-time multi-tasking environments. In: 2011 USENIX Annual Technical Conference (USENIX ATC 11) (2011)"},{"issue":"1","key":"745_CR12","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1145\/2786763.2694346","volume":"43","author":"JJK Park","year":"2015","unstructured":"Park, J.J.K., Park, Y., Mahlke, S.: Chimera: collaborative preemption for multitasking on a shared GPU. ACM SIGARCH Comput. Arch. News 43(1), 593\u2013606 (2015)","journal-title":"ACM SIGARCH Comput. Arch. News"},{"issue":"4","key":"745_CR13","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1145\/3093336.3037742","volume":"52","author":"B Wu","year":"2017","unstructured":"Wu, B., Liu, X., Zhou, X., Jiang, C.: FLEP: enabling flexible and efficient preemption on GPUs. ACM SIGPLAN Not. 52(4), 483\u2013496 (2017)","journal-title":"ACM SIGPLAN Not."},{"key":"745_CR14","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1109\/PROC.1987.13876","volume":"75","author":"E Lee","year":"1987","unstructured":"Lee, E., Messerschmitt, D.: Synchronous data flow. Proc. IEEE 75, 1235\u20131245 (1987)","journal-title":"Proc. IEEE"},{"key":"745_CR15","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/3-540-45937-5_14","volume-title":"International Conference on Compiler Construction","author":"W Thies","year":"2002","unstructured":"Thies, W., Karczmarek, M., Amarasinghe, S.: StreamIt: a language for streaming applications. In: Horspool, R.N. (ed.) International Conference on Compiler Construction, pp. 179\u2013196. Springer, Berlin (2002)"},{"key":"745_CR16","unstructured":"Prokopec, A., Liu, F.: Theory and practice of coroutines with snapshots. In: 32nd European Conference on Object-Oriented Programming (ECOOP 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)"}],"container-title":["International Journal of Parallel Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-022-00745-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10766-022-00745-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-022-00745-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T19:40:07Z","timestamp":1674848407000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10766-022-00745-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,5]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["745"],"URL":"https:\/\/doi.org\/10.1007\/s10766-022-00745-2","relation":{},"ISSN":["0885-7458","1573-7640"],"issn-type":[{"type":"print","value":"0885-7458"},{"type":"electronic","value":"1573-7640"}],"subject":[],"published":{"date-parts":[[2022,12,5]]},"assertion":[{"value":"9 September 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 November 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 December 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}