Scheduling nonlinear divisible loads in a single level tree network

Suresh, S.; Kim, H.; Run, Cui; Robertazzi, T.
September 2012
Journal of Supercomputing;Sep2012, Vol. 61 Issue 3, p1068
Academic Journal
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.


Related Articles

  • Abstract Communication Model for Distribution Systems. Glässer, Uwe; Gurevich, Yuri; Veanes, Margus // IEEE Transactions on Software Engineering;Jul2004, Vol. 30 Issue 7, p458 

    In some distributed and mobile communication models, a message disappears in one place and miraculously appears in another. In reality, of course, there are no miracles. A message goes from one network to another; it can be lost or corrupted in the process. Here, we present a realistic but...

  • Machine Vision Meets the PC. Vollset, Thor // Quality;May2010 Supplement, p12 

    The article discusses several personal computer (PC)-based vision sensor solutions. It discusses some of the most important factors which affect the position of PC-based solutions in the technology industry including GigE cameras, effect of multi-core processing, and machine vision servers....

  • High diagnosability of a sequential diagnosis algorithm in hypercubes under the PMC model. Kuo, Chin-Lin; Yang, Ming-Jeng; Chang, Yao-Ming; Yeh, Yao-Ming // Journal of Supercomputing;Sep2012, Vol. 61 Issue 3, p1116 

    We consider the problem of sequential fault diagnosis in a hypercube multiprocessor system under the PMC model. The diagnosability is defined as the ability to provide a correct and complete diagnosis. In this paper, we propose a novel and simple sequential diagnosis method called the Major...

  • Reducing communication costs in collective I/O in multi-core cluster systems with non-exclusive scheduling. Cha, Kwangho; Maeng, Seungryoul // Journal of Supercomputing;Sep2012, Vol. 61 Issue 3, p966 

    As the number of nodes in high performance computing (HPC) systems increases, collective I/O becomes an important issue and I/O aggregators are the key factors in improving the performance of collective I/O. When an HPC system uses non-exclusive scheduling, a different number of CPU cores per...

  • MIPS UNVEILS PLANS FOR 64-BIT MULTIPROCESSOR "PRODIGY".  // Electro Manufacturing;May2011, Vol. 24 Issue 5, p1 

    The article reports on the plan of Sunnyvale, California-based processor architectures and cores provider MIPS Technologies Inc. to offer its first Prodigy information processing core. The core, which is scheduled to be officially launched in 2011, combines a 64-bit processor architecture with...

  • Exploiting hierarchical parallelisms for molecular dynamics simulation on multicore clusters. Liu Peng; Kunaseth, Manaschai; Dursun, Hikmet; Nomura, Ken-ichi; Weiqiang Wang; Kalia, Rajiv K.; Nakano, Aiichiro; Vashishta, Priya // Journal of Supercomputing;Jul2011, Vol. 57 Issue 1, p20 

    We have developed a scalable hierarchical parallelization scheme for molecular dynamics (MD) simulation on multicore clusters. The scheme explores multilevel parallelism combining: (1) Internode parallelism using spatial decomposition via message passing; (2) intercore parallelism using cellular...

  • Parallel evidence propagation on multicore processors. Yinglong Xia; Prasanna, Viktor K. // Journal of Supercomputing;Aug2011, Vol. 57 Issue 2, p189 

    We propose a parallel evidence propagation method on general-purpose multicore processors. Evidence propagation is a major step in exact inference, a key problem in exploring probabilistic graphical models. We explore the parallelism in evidence propagation at various levels. First, given an...

  • Using hybrid MPI and OpenMP programming to optimize communications in parallel loop self-scheduling schemes for multicore PC clusters. Wu, Chao-Chin; Lai, Lien-Fu; Yang, Chao-Tung; Chiu, Po-Hsun // Journal of Supercomputing;Apr2012, Vol. 60 Issue 1, p31 

    Recently, a series of parallel loop self-scheduling schemes have been proposed, especially for heterogeneous cluster systems. However, they employed the MPI programming model to construct the applications without considering whether the computing node is multicore architecture or not. As a...

  • Performance analysis and optimization of MPI collective operations on multi-core clusters. Tu, Bibo; Fan, Jianping; Zhan, Jianfeng; Zhao, Xiaofang // Journal of Supercomputing;Apr2012, Vol. 60 Issue 1, p141 

    Memory hierarchy on multi-core clusters has twofold characteristics: vertical memory hierarchy and horizontal memory hierarchy. This paper proposes new parallel computation model to unitedly abstract memory hierarchy on multi-core clusters in vertical and horizontal levels. Experimental results...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics