Implicit Data-Parallelism in Kahn Process Networks: Bridging the MacQueen Gap

Robert Khasanov, Andrés Goens, Jeronimo Castrillon

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Modern embedded systems are rapidly increasing their complexity, both in terms of numbers of cores, as well as heterogeneity. To generate efficient code for these systems, it is common to leverage formal models of computation. Among these, the dataflow model of Kahn Process Networks (KPN) is widespread because it is expressive but guarantees a deterministic execution. However, the KPN model is ill-suited to expose data-level parallelism, since this has to be made explicit in the process network. This is aggravated by the fact that its most common execution model, Kahn-MacQueen, poses restrictive conditions on the scheduling of data-parallel processes, leading to an inefficient execution. In this paper we present a novel extension to the KPN model and a relaxed execution strategy that addresses this problem, while keeping the deterministic KPN semantics. It improves run-time adaptivity in malleable way and provides implicit parallelism. We evaluate our approach on two architectures, improving the performance of a benchmark by up to 25.6% on an Intel chip with hyper-threading, and by up to 78.0 % on a heterogeneous embedded ARM big.LITTLE architecture.
Original languageEnglish
Title of host publicationProceedings of the 9th Workshop and 7th Workshop on Parallel Programming and RunTime Management Techniques for Manycore Architectures and Design Tools and Architectures for Multicore Embedded Computing Platforms
Place of PublicationNew York, NY, USA
PublisherACM Association for Computing Machinery
Pages20–25
Number of pages6
ISBN (Print)9781450364447
DOIs
Publication statusPublished - 23 Jan 2018
Event9th Workshop on Parallel Programming and Run-Time Management Techniques for Many-core Architectures & 7th Workshop on Design Tools and Architectures For Multicore Embedded Computing Platforms - Manchester, United Kingdom
Duration: 23 Jan 201823 Jan 2018

Publication series

NamePARMA-DITAM '18
PublisherAssociation for Computing Machinery

Conference

Conference9th Workshop on Parallel Programming and Run-Time Management Techniques for Many-core Architectures & 7th Workshop on Design Tools and Architectures For Multicore Embedded Computing Platforms
Abbreviated titlePARMA-DITAM 2018
Country/TerritoryUnited Kingdom
CityManchester
Period23/01/1823/01/18

Keywords

  • MPSoC
  • Streaming applications
  • adaptivity
  • process networks
  • heterogeneous

Fingerprint

Dive into the research topics of 'Implicit Data-Parallelism in Kahn Process Networks: Bridging the MacQueen Gap'. Together they form a unique fingerprint.

Cite this