| Presentation | 2009-01-29 On Upper and Lower Bounds of Optimal Execution Time of Task Graph by Considering Communication Delays Takashi OTSUKA, Masato NAKAHARA, Qi-Wei GE, Mitsuru NAKATA, Yuu MORIYAMA, Hirotoshi TONOU, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | This paper deals with upper and lower bounds of optimal execution time of task graphs that are supposed to be executed in a model of multiprocessor system, in which communication times are taken into account. We firstly define a path-dependent minimum subnet whose execution time is the shortest when executed by a single processor. Based on this definition, we then define a critical subnet of task graphs, which is the minimum subnet with the maximum execution time. Analyzing the properties of the minimum subnet and the critical subnet, we finally give the upper and lower bounds of optimal execution time of task graphs. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | multiprocessor scheduling / communication time / minimum subnet / critical subnet / upper bound / lower bound |
| Paper # | CST2008-41 |
| Date of Issue |
| Conference Information | |
| Committee | CST |
|---|---|
| Conference Date | 2009/1/22(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Concurrent System Technology (CST) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | On Upper and Lower Bounds of Optimal Execution Time of Task Graph by Considering Communication Delays |
| Sub Title (in English) | |
| Keyword(1) | multiprocessor scheduling |
| Keyword(2) | communication time |
| Keyword(3) | minimum subnet |
| Keyword(4) | critical subnet |
| Keyword(5) | upper bound |
| Keyword(6) | lower bound |
| 1st Author's Name | Takashi OTSUKA |
| 1st Author's Affiliation | Yamaguchi University() |
| 2nd Author's Name | Masato NAKAHARA |
| 2nd Author's Affiliation | Yamaguchi University |
| 3rd Author's Name | Qi-Wei GE |
| 3rd Author's Affiliation | Yamaguchi University |
| 4th Author's Name | Mitsuru NAKATA |
| 4th Author's Affiliation | Yamaguchi University |
| 5th Author's Name | Yuu MORIYAMA |
| 5th Author's Affiliation | Fujitsu TEN Limited |
| 6th Author's Name | Hirotoshi TONOU |
| 6th Author's Affiliation | Fujitsu TEN Limited |
| Date | 2009-01-29 |
| Paper # | CST2008-41 |
| Volume (vol) | vol.108 |
| Number (no) | 415 |
| Page | pp.pp.- |
| #Pages | 4 |
| Date of Issue | |