%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 }