Optimal Scheduling for UET/UET-UCT Generalizedn-Dimensional Grid Task Graphs |
| |
| Affiliation: | 1. College of Optical Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China;2. College of Optical and Electronic Technology, China Jiliang University, 310018 Hangzhou, China;3. College of Horticulture & Forestry Sciences, Huazhong Agricultural University, Key Laboratory of Horticultural Plant Biology, Ministry of Education, 430070 Wuhan, China;1. National Research University of Electronic Technology – MIET, Bld. 1, Shokin Square, Zelenograd, Moscow 124498, Russia;2. Faculty of Physics, M.V. Lomonosov, Moscow State University, Leninskie Gory, Moscow 119991, Russia;3. National Research Centre “Kurchatov Institute”, Kurchatov sq., 1, Moscow 123182, Russia;4. I.M. Sechenov First Moscow State Medical University, st. Trubetskaya, 8, bld. 2, Moscow 119991, Russia;1. Department of physics, University of the Free State-Qwaqwa Campus, Private Bag X13, Phuthaditjhaba 9866, South Africa;2. Natural Resources and Environment, Council for Scientific and Industrial Research, P.O. Box 395, Pretoria 0001, South Africa;3. Chemistry Department, University of the Western Cape, Private Bag X17, Bellville, Cape Town, South Africa;1. Department of Chemistry, University of Pittsburgh, Pittsburgh, PA 15260, USA;2. Department of Chemistry, University at Albany, SUNY, 1400 Washington Avenue, Albany, NY 12222, USA;3. Molecular Biophysics and Structural Biology Program, University of Pittsburgh, Pittsburgh, PA 15260, USA |
| |
| Abstract: | Then-dimensional grid is one of the most representative patterns of data flow in parallel computation. Many scientific algorithms, which require nearest neighbor communication in a lattice space, are modeled by a task graph with the properties of a simple or enhanced grid. The two most frequently used scheduling models for grids are the unit execution time-zero communication delay (UET) and the unit execution time–unit communication time (UET-UCT). In this paper we introduce an enhanced model of then-dimensional grid by adding extra diagonal edges and allowing unequal boundaries for each dimension. For this generalized grid topology we establish the optimal makespan for both cases of UET/UET-UCT grids. Then we give a closed formula that calculates the minimum number of processors required to achieve the optimal makespan. Finally, we propose a low-complexity optimal time and processor scheduling strategy for both cases. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
