Graph partition based mapping algorithm on multiprocessors for streaming applications
To take advantage of multiprocessor platform,it is a necessity to map tasks of the application properly onto different processors to exploit the concurrency in the application and thus meet the stringent timing requirements.Parallelism graph was proposed to quantify and model the concurrency among t...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Department of Journal on Communications
2016-06-01
|
| Series: | Tongxin xuebao |
| Subjects: | |
| Online Access: | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2016123/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841539606846111744 |
|---|---|
| author | Qi TANG Shang-feng WU Jun-wu SHI Ji-bo WEI |
| author_facet | Qi TANG Shang-feng WU Jun-wu SHI Ji-bo WEI |
| author_sort | Qi TANG |
| collection | DOAJ |
| description | To take advantage of multiprocessor platform,it is a necessity to map tasks of the application properly onto different processors to exploit the concurrency in the application and thus meet the stringent timing requirements.Parallelism graph was proposed to quantify and model the concurrency among tasks of the application.An algorithm was also proposed to construct the parallelism graph based on the self-timed schedule and transform the mapping problem to a graph partitioning problem.The graph partitioning problem as a pure 0-1 integer linear programming model was further formulated and the ILP solver to find the optimal result.A lot of randomly generated synchronous dataflow graphs and a set of practical applications were used to evaluate the performance of the proposed method.The experimental results demonstrate that the proposed method outperforms available algorithms. |
| format | Article |
| id | doaj-art-bcdb5293197049b89a4fe375a75881e4 |
| institution | Kabale University |
| issn | 1000-436X |
| language | zho |
| publishDate | 2016-06-01 |
| publisher | Editorial Department of Journal on Communications |
| record_format | Article |
| series | Tongxin xuebao |
| spelling | doaj-art-bcdb5293197049b89a4fe375a75881e42025-01-14T06:55:38ZzhoEditorial Department of Journal on CommunicationsTongxin xuebao1000-436X2016-06-013713714359701740Graph partition based mapping algorithm on multiprocessors for streaming applicationsQi TANGShang-feng WUJun-wu SHIJi-bo WEITo take advantage of multiprocessor platform,it is a necessity to map tasks of the application properly onto different processors to exploit the concurrency in the application and thus meet the stringent timing requirements.Parallelism graph was proposed to quantify and model the concurrency among tasks of the application.An algorithm was also proposed to construct the parallelism graph based on the self-timed schedule and transform the mapping problem to a graph partitioning problem.The graph partitioning problem as a pure 0-1 integer linear programming model was further formulated and the ILP solver to find the optimal result.A lot of randomly generated synchronous dataflow graphs and a set of practical applications were used to evaluate the performance of the proposed method.The experimental results demonstrate that the proposed method outperforms available algorithms.http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2016123/synchronous dataflow graphmappingmultiprocessorgraph partition |
| spellingShingle | Qi TANG Shang-feng WU Jun-wu SHI Ji-bo WEI Graph partition based mapping algorithm on multiprocessors for streaming applications Tongxin xuebao synchronous dataflow graph mapping multiprocessor graph partition |
| title | Graph partition based mapping algorithm on multiprocessors for streaming applications |
| title_full | Graph partition based mapping algorithm on multiprocessors for streaming applications |
| title_fullStr | Graph partition based mapping algorithm on multiprocessors for streaming applications |
| title_full_unstemmed | Graph partition based mapping algorithm on multiprocessors for streaming applications |
| title_short | Graph partition based mapping algorithm on multiprocessors for streaming applications |
| title_sort | graph partition based mapping algorithm on multiprocessors for streaming applications |
| topic | synchronous dataflow graph mapping multiprocessor graph partition |
| url | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2016123/ |
| work_keys_str_mv | AT qitang graphpartitionbasedmappingalgorithmonmultiprocessorsforstreamingapplications AT shangfengwu graphpartitionbasedmappingalgorithmonmultiprocessorsforstreamingapplications AT junwushi graphpartitionbasedmappingalgorithmonmultiprocessorsforstreamingapplications AT jibowei graphpartitionbasedmappingalgorithmonmultiprocessorsforstreamingapplications |