Automatic Extraction of Pipeline Parallelism for Embedded
Software Using Linear Programming
D. Cordes, A. Heinig, P. Marwedel, and A. Mallik. Parallel and Distributed Systems (ICPADS), 2011 IEEE 17th
International Conference on, page 699--706. (December 2011)
Abstract
The complexity and performance requirements of embedded software
are continuously increasing, making Multiprocessor
System-on-Chip (MPSoC) architectures more and more important in
the domain of embedded and cyber-physical systems. Using
multiple cores in a single system reduces problems concerning
energy consumption, heat dissipation, and increases performance.
Nevertheless, these benefits do not come for free. Porting
existing, mostly sequential, applications to MPSoCs requires
extracting efficient parallelism to utilize all available cores.
Many embedded applications, like network services and multimedia
tasks for voice-, image- and video processing, are operating on
data streams and thus have a streaming-based structure. Despite
the abundance of parallelism in streaming applications, it is a
non-trivial task to split and efficiently map sequential
applications to MPSoCs. Therefore, we present an algorithm which
automatically extracts pipeline parallelism from sequential
ANSI-C applications. The presented tool employs an integer
linear programming (ILP) based approach enriched with an
adequate cost model to automatically control the granularity of
the parallelization. By applying our tool to real-life
applications, it can be shown that our approach is able to speed
up applications by a factor of up to 3.9x on a four-core MPSoC
architecture, compared to a sequential execution.
%0 Conference Paper
%1 Cordes2011-qd
%A Cordes, D
%A Heinig, A
%A Marwedel, P
%A Mallik, A
%B Parallel and Distributed Systems (ICPADS), 2011 IEEE 17th
International Conference on
%D 2011
%K Automatic_Parallelization Cyber-Physical_Systems Embedded_Software Equations ILP_based_approach Indexes MPSoC MPSoC_architectures Mathematical_model Parallelization Pipeline_Parallelism Pipeline_processing Pipelines Polyhedral_model Program_Dependence_Graph Streaming_media To_Read cyber-physical_systems data_streams embedded_software_complexity embedded_software_performance_requirements embedded_systems energy_consumption heat_dissipation image_processing integer_linear_programming linear_programming multimedia_tasks multiple_cores multiprocessor_system-on-chip_architectures network_services pipeline_parallelism_automatic_extraction pipeline_processing sequential_ANSI-C_applications streaming-based_structure streaming_applications system-on-chip video_processing voice_processing
%P 699--706
%T Automatic Extraction of Pipeline Parallelism for Embedded
Software Using Linear Programming
%X The complexity and performance requirements of embedded software
are continuously increasing, making Multiprocessor
System-on-Chip (MPSoC) architectures more and more important in
the domain of embedded and cyber-physical systems. Using
multiple cores in a single system reduces problems concerning
energy consumption, heat dissipation, and increases performance.
Nevertheless, these benefits do not come for free. Porting
existing, mostly sequential, applications to MPSoCs requires
extracting efficient parallelism to utilize all available cores.
Many embedded applications, like network services and multimedia
tasks for voice-, image- and video processing, are operating on
data streams and thus have a streaming-based structure. Despite
the abundance of parallelism in streaming applications, it is a
non-trivial task to split and efficiently map sequential
applications to MPSoCs. Therefore, we present an algorithm which
automatically extracts pipeline parallelism from sequential
ANSI-C applications. The presented tool employs an integer
linear programming (ILP) based approach enriched with an
adequate cost model to automatically control the granularity of
the parallelization. By applying our tool to real-life
applications, it can be shown that our approach is able to speed
up applications by a factor of up to 3.9x on a four-core MPSoC
architecture, compared to a sequential execution.
@inproceedings{Cordes2011-qd,
abstract = {The complexity and performance requirements of embedded software
are continuously increasing, making Multiprocessor
System-on-Chip (MPSoC) architectures more and more important in
the domain of embedded and cyber-physical systems. Using
multiple cores in a single system reduces problems concerning
energy consumption, heat dissipation, and increases performance.
Nevertheless, these benefits do not come for free. Porting
existing, mostly sequential, applications to MPSoCs requires
extracting efficient parallelism to utilize all available cores.
Many embedded applications, like network services and multimedia
tasks for voice-, image- and video processing, are operating on
data streams and thus have a streaming-based structure. Despite
the abundance of parallelism in streaming applications, it is a
non-trivial task to split and efficiently map sequential
applications to MPSoCs. Therefore, we present an algorithm which
automatically extracts pipeline parallelism from sequential
ANSI-C applications. The presented tool employs an integer
linear programming (ILP) based approach enriched with an
adequate cost model to automatically control the granularity of
the parallelization. By applying our tool to real-life
applications, it can be shown that our approach is able to speed
up applications by a factor of up to 3.9x on a four-core MPSoC
architecture, compared to a sequential execution.},
added-at = {2015-04-11T18:41:09.000+0200},
author = {Cordes, D and Heinig, A and Marwedel, P and Mallik, A},
biburl = {https://www.bibsonomy.org/bibtex/2578bd38f01af6a63ac0ff9b399b4f6df/christophv},
booktitle = {Parallel and Distributed Systems ({ICPADS)}, 2011 {IEEE} 17th
International Conference on},
interhash = {f663d69770c538929ca139e5afe8e36a},
intrahash = {578bd38f01af6a63ac0ff9b399b4f6df},
keywords = {Automatic_Parallelization Cyber-Physical_Systems Embedded_Software Equations ILP_based_approach Indexes MPSoC MPSoC_architectures Mathematical_model Parallelization Pipeline_Parallelism Pipeline_processing Pipelines Polyhedral_model Program_Dependence_Graph Streaming_media To_Read cyber-physical_systems data_streams embedded_software_complexity embedded_software_performance_requirements embedded_systems energy_consumption heat_dissipation image_processing integer_linear_programming linear_programming multimedia_tasks multiple_cores multiprocessor_system-on-chip_architectures network_services pipeline_parallelism_automatic_extraction pipeline_processing sequential_ANSI-C_applications streaming-based_structure streaming_applications system-on-chip video_processing voice_processing},
month = dec,
pages = {699--706},
timestamp = {2015-04-11T18:41:09.000+0200},
title = {Automatic Extraction of Pipeline Parallelism for Embedded
Software Using Linear Programming},
year = 2011
}