Scheduling nonlinear divisible loads in a single level tree network
In this paper, we study the scheduling problem for polynomial time complexity computational loads in a single level tree network with a collective communication model. The problem of minimizing the processing time is investigated when the computational loads require polynomial order of processing ti...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2013
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/99293 http://hdl.handle.net/10220/17260 |
| _version_ | 1811697772843237376 |
|---|---|
| author | Suresh, Sundaram Run, Cui Kim, H. J. Robertazzi, T. G. |
| author2 | School of Computer Engineering |
| author_facet | School of Computer Engineering Suresh, Sundaram Run, Cui Kim, H. J. Robertazzi, T. G. |
| author_sort | Suresh, Sundaram |
| collection | NTU |
| description | In this paper, we study the scheduling problem for polynomial time complexity computational loads in a single level tree network with a collective communication model. The problem of minimizing the processing time is investigated when the computational loads require polynomial order of processing time which is proportional to the size of load fraction. In the divisible load theory framework, the presence of polynomial time complexity computational loads leads to solving higher-order algebraic equations to find the optimal load fractions assigned to the processors in the network. The problem of finding optimal load fraction is a computationally intensive task. Using a mild assumption on the ratio of communication time to computation time, we present a closed-form solution for near optimal load fractions and processing time for the entire load fractions. Finally, we also present a closed-form solution for scheduling polynomial loads with start-up delay in communication and computation. The numerical speedup results obtained using closed-form solution clearly show that super-linear speedup is possible for the polynomial computational loads. |
| first_indexed | 2024-10-01T08:00:35Z |
| format | Journal Article |
| id | ntu-10356/99293 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T08:00:35Z |
| publishDate | 2013 |
| record_format | dspace |
| spelling | ntu-10356/992932020-05-28T07:18:57Z Scheduling nonlinear divisible loads in a single level tree network Suresh, Sundaram Run, Cui Kim, H. J. Robertazzi, T. G. School of Computer Engineering DRNTU::Engineering::Computer science and engineering In this paper, we study the scheduling problem for polynomial time complexity computational loads in a single level tree network with a collective communication model. The problem of minimizing the processing time is investigated when the computational loads require polynomial order of processing time which is proportional to the size of load fraction. In the divisible load theory framework, the presence of polynomial time complexity computational loads leads to solving higher-order algebraic equations to find the optimal load fractions assigned to the processors in the network. The problem of finding optimal load fraction is a computationally intensive task. Using a mild assumption on the ratio of communication time to computation time, we present a closed-form solution for near optimal load fractions and processing time for the entire load fractions. Finally, we also present a closed-form solution for scheduling polynomial loads with start-up delay in communication and computation. The numerical speedup results obtained using closed-form solution clearly show that super-linear speedup is possible for the polynomial computational loads. 2013-11-05T05:29:42Z 2019-12-06T20:05:28Z 2013-11-05T05:29:42Z 2019-12-06T20:05:28Z 2011 2011 Journal Article Suresh, S., Kim, H. J., Run, C., & Robertazzi, T. G. (2012). Scheduling nonlinear divisible loads in a single level tree network. The Journal of Supercomputing, 61(3), 1068-1088. https://hdl.handle.net/10356/99293 http://hdl.handle.net/10220/17260 10.1007/s11227-011-0677-2 en The journal of supercomputing |
| spellingShingle | DRNTU::Engineering::Computer science and engineering Suresh, Sundaram Run, Cui Kim, H. J. Robertazzi, T. G. Scheduling nonlinear divisible loads in a single level tree network |
| title | Scheduling nonlinear divisible loads in a single level tree network |
| title_full | Scheduling nonlinear divisible loads in a single level tree network |
| title_fullStr | Scheduling nonlinear divisible loads in a single level tree network |
| title_full_unstemmed | Scheduling nonlinear divisible loads in a single level tree network |
| title_short | Scheduling nonlinear divisible loads in a single level tree network |
| title_sort | scheduling nonlinear divisible loads in a single level tree network |
| topic | DRNTU::Engineering::Computer science and engineering |
| url | https://hdl.handle.net/10356/99293 http://hdl.handle.net/10220/17260 |
| work_keys_str_mv | AT sureshsundaram schedulingnonlineardivisibleloadsinasingleleveltreenetwork AT runcui schedulingnonlineardivisibleloadsinasingleleveltreenetwork AT kimhj schedulingnonlineardivisibleloadsinasingleleveltreenetwork AT robertazzitg schedulingnonlineardivisibleloadsinasingleleveltreenetwork |