mdh.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Automatic Inference of Task Parallelism in Task-graph-based Actor Models
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0002-4872-1208
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0001-5297-6548
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0002-0401-1036
2018 (English)In: IEEE Access, E-ISSN 2169-3536, Vol. 6, p. 78965-78991Article in journal (Refereed) Published
Abstract [en]

Automatic inference of task level parallelism is fundamental for ensuring many kinds of safety and liveness properties of parallel applications. For example, two tasks running in parallel may be involved in data races when they have conflicting memory accesses, or one is affecting the termination of another by updating shared variables. In this article, we have considered a task-graph-based actor model, used in signal processing applications (e.g., baseband processing in wireless communication, LTE uplink processing) that are deployed on many-core platforms, in which actors, task-graphs and tasks are the active entities running in parallel. Actors invoke task graphs, which in turn invoke tasks, and they communicate through message passing, thus creating different kinds of dependencies and parallelism in the application. We introduce a novel May Happen in Parallel (MHP) analysis for complex parallel applications based on our computational model. The MHP analysis consists of (i) data-flow analysis applicable to parallel control-flow structures inferring MHP facts representing pairs of tasks running in parallel, (ii) identification of all direct and indirect communication by generating a context-free grammar and enumerating valid strings representing parallelism and dependencies among active entities, and (iii) inferring MHP facts when multiple task-graphs communicate. Our analysis is applicable to other computational models (e.g. Cilk or X10) too. We have fully implemented our analysis and evaluated it on signal processing applications consisting of a maximum of 36.57 million lines of code representing 232 different tasks. The analysis approximately 7 minutes to identify all communication information and 10.5 minutes to identify 12052 executable parallel task-pairs (to analyse for concurrency bugs) proving that our analysis is scalable for industrial-sized code-bases.

Place, publisher, year, edition, pages
2018. Vol. 6, p. 78965-78991
Keywords [en]
May happen in parallel, data flow analysis, actor model, parallel task graph, graph reachability, UML profile
National Category
Engineering and Technology Computer Systems
Identifiers
URN: urn:nbn:se:mdh:diva-41748DOI: 10.1109/ACCESS.2018.2885705ISI: 000454857600001Scopus ID: 2-s2.0-85058163957ISBN: 2169-3536 OAI: oai:DiVA.org:mdh-41748DiVA, id: diva2:1282627
Projects
Static Program Analysis for Complex Embedded systemsMOMENTUM: analysis of models towards compilation to predictable embedded real-time and safety-critical applicationsAvailable from: 2018-12-18 Created: 2019-01-25 Last updated: 2019-01-17Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Masud, Abu NaserLisper, BjörnCiccozzi, Federico

Search in DiVA

By author/editor
Masud, Abu NaserLisper, BjörnCiccozzi, Federico
By organisation
Embedded Systems
In the same journal
IEEE Access
Engineering and TechnologyComputer Systems

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 4 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf