Runtime incremental parallel scheduling (RIPS) on distributed memory computers
IEEE Transactions on Parallel and Distributed SystemsPublished 1 June 1996
Wei Shu, Min‐You Wu
Citations30
SJR quartileQ1
SJR score2.10
SNIP2.28
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The paper presents methods for scheduling a single job on a dedicated parallel machine using the advanced parallel scheduling technique to produce a low overhead, high quality load balancing, as well as adapting to irregular applications.
Abstract
Runtime Incremental Parallel Scheduling (RIPS) is an alternative strategy to the commonly used dynamic scheduling. In this scheduling strategy, the system scheduling activity alternates with the underlying computation work. RIPS utilizes the advanced parallel scheduling technique to produce a low overhead, high quality load balancing, as well as adapting to irregular applications. The paper presents methods for scheduling a single job on a dedicated parallel machine.
Keywords
Computer ScienceEngineering
Artificial IntelligenceDepth-first iterative-deepening
1,549 Citations1985Richard E. Korf
A depth·first iterative·deepening algorithm is shown to be asymptotically optimal along all three dimmsions for exponential tree searches and is the only known algorithm that is capable of finding optimal solUtions to randomly generated instances of the Fif/un Puzzle within practical resource.
Journal of Parallel and Distributed ComputingDynamic load balancing for distributed memory multiprocessors
986 Citations1989George Cybenko
This paper completely analyze the hypercube network by explicitly computing the eigenstructure of its node adjacency matrix and shows that a diffusion approach to load balancing on a hypercube multiprocessor is inferior to another approach which is called the dimension exchange method.
IEEE Transactions on Software EngineeringAdaptive load sharing in homogeneous distributed systems
926 Citations1986Derek L. Eager, Edward D. Lazowska +1 more
It is shown that extremely simple adaptive load sharing policies, which collect very small amounts of system state information and which use this information in very simple ways, yield dramatic performance improvements.
IEEE Transactions on Parallel and Distributed SystemsA compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures
881 Citations1993G.C. Sih, Edward A. Lee
The authors present a compile-time scheduling heuristic called dynamic level scheduling, which accounts for interprocessor communication overhead when mapping precedence-constrained, communicating tasks onto heterogeneous processor architectures with limited or possibly irregular interconnection structures.
IEEE Transactions on Parallel and Distributed SystemsHypertool: a programming aid for message-passing systems
654 Citations1990M.-Y. Wu, Daniel D. Gajski
Programming assistance, automation concepts, and their application to a message-passing system program development tool called Hypertool, which performs scheduling and handles the communication primitive insertion automatically, thereby increasing productivity and eliminating synchronization errors.
IEEE Transactions on ComputersA Partitioning Strategy for Nonuniform Problems on Multiprocessors
576 Citations1987Berger, Bokhari
This work uses a binary decomposition of the domain to partition it into rectangles requiring equal computational effort, and studies the communication costs of mapping this partitioning onto different multiprocessors: a mesh- connected array, a tree machine, and a hypercube.
IEEE Transactions on Parallel and Distributed SystemsStrategies for dynamic load balancing on highly parallel computers
524 Citations1993M. Willebeek-LeMair, Anthony P. Reeves
Five DLB strategies are presented which illustrate the tradeoff between knowledge - the accuracy of each balancing decision, and overhead - the amount of added processing and communication incurred by the balancing process.
ComputerLoad distributing for locally distributed systems
500 Citations1992N.G. Shivaratri, P. Krueger +1 more
The problem of judiciously and transparently redistributing the load of the system among its nodes so that overall performance is maximized is discussed and conclusions about which algorithm might help in realizing the most benefits of load distributing are drawn.
IEEE Transactions on ComputersLoad Sharing in Distributed Systems
458 Citations1985Yung-Terng Wang, Robert Morris
A taxonomy of load sharing algorithms is proposed that draws a basic dichotomy between source- initiative and server-initiative approaches and a performance metric called the Q-factor (quality of load share) is defined which summarizes both overall efficiency and fairness of an algorithm.
Journal of Parallel and Distributed ComputingScheduling parallel program tasks onto arbitrary target machines
420 Citations1990Hesham El‐Rewini, T. Lewis
A new scheduling heuristic (MH) is introduced that schedules program modules represented as nodes in a precedence task graph with communication onto arbitrary machine topology taking contention into consideration.
IEEE Transactions on Software EngineeringThe Gradient Model Load Balancing Method
275 Citations1987Frank C. Lin, Robert Keller
A dynamic load balancing method is proposed for a class of large-diameter multiprocessor systems based on the "gradient model," which entails transferring backlogged tasks to nearby idle processors according to a pressure gradient indirectly established by requests from idle processors.
Journal of the ACMRandomized parallel algorithms for backtrack search and branch-and-bound computation
175 Citations1993Richard M. Karp, Yanjun Zhang
Universal randomized methods for parallelizing sequential backtrack search and branch-and-bound computation are presented and demonstrate the effectiveness of randomization in distributed parallel computation.
PYRROS
171 Citations2014Tao Yang, Apostolos Gerasoulis
A parallel programming tool for scheduling static task graphs and generating the appropriate target code for message passing MIMD architectures and preliminary experiments show performance comparable to the "best" hand-written programs.
International Journal of Parallel ProgrammingParallel depth first search. Part I. Implementation
168 Citations1987V. Nageshwara Rao, Vipin Kumar
A parallel formulation of depth-first search which retains the storage efficiency of sequential depth- first search and can be mapped on to anyMIMD architecture is presented and results show that hypercube and sharedmemory architectures are significantly better.
Conference on High Performance Computing (Supercomputing)Applications and performance analysis of a compile-time optimization approach for list scheduling algorithms on distributed memory multiprocessors
143 Citations1992Yeh‐Ching Chung, Sanjay Ranka
Parallel hierarchical N-body methods
141 Citations1992John K. Salmon
It is shown how the BH algorithm can be adapted to execute in parallel, and the performance of the parallel version of the algorithm is analyzed, finding that the overhead is due primarily to interprocessor synchronization delays and redundant computation.
A randomized parallel branch-and-bound procedure
83 Citations1988Richard M. Karp, Yanjun Zhang
A universal randomized method called Local Best-First Search for parallelizing sequential branch-and-bound algorithms that shows that, uniformly on all instances, the execution time of the method is unlikely to exceed a certain inherent lower bound by more than a constant factor.
Applications and performance analysis of a compile-time optimization approach for list scheduling algorithms on distributed memory multiprocessors
73 Citations2003Yeh‐Ching Chung, Sanjay Ranka
Simulation results show that, given a directed acyclic growth (DAG), the graph parallelism of the DAG can accurately predict the number of processors to be used such that a good scheduling length and a good resource utilization can be achieved simultaneously.
Computer Networks (1976)Simulations of three adaptive, decentralized controlled, job scheduling algorithms
70 Citations1984John A. Stankovic
Simulation results of three adaptive, decentralized controlled job scheduling algorithms which assume absolutely no a priori knowledge about jobs are presented, and it is observed that, if tuned correctly, the decentralized algorithms exhibit stable behavior and considerably improve performance at modest cost.
Computer Networks and ISDN SystemsSimulations of three adaptive, decentralized controlled, job scheduling algorithms
61 Citations1984John A. Stankovic
Chemical PhysicsMolecular dynamics simulation of superoxide interacting with superoxide dismutase
43 Citations1991Jian Shen, J. Andrew McCammon
The Caltech Institute Archives (California Institute of Technology)Fine Grain Concurrent Computations
40 Citations1987W.C. Athas
A new concurrent programming notation Cantor is used to demonstrate the cognitive process of writing programs using the object model, and hardware and software architectures for organizing fine grain message-passing computations is proposed, including support for fault tolerance and for garbage collection.
Relaxing SIMD control flow constraints using loop transformations
32 Citations1992Reinhard von Hanxleden, Ken Kennedy
It is argued that loop flattening, whether performed by the programmer or by the compiler, introduces negligible overhead and can significantly improve the performance of scientific codes for solving irregular problems.
OecologiaA low-cost hypercube load-balance algorithm
30 Citations1989K.M. Dragon, John L. Gustafson
A divide-and-conquer approach to dynamic load balancing for a 1024-processor hypercube that requires only O(1) additional storage and O((log/sub 2/P)/sup 2/) additional operations is developed.
Randomized load balancing for tree-structured computation
28 Citations2002Soumen Chakrabarti, Abhiram Ranade +1 more
This work shows that the time taken to explore a task tree is likely to be within a small constant factor of an inherent lower bound for the tree instance, and thus extends earlier work which assumed fixed cost tasks and used a bulk synchronous style.
A parallel approach for multiprocessor scheduling
19 Citations2002Iftikhar Ahmad, Yu‐Kwong Kwok
This research proposes a low complexity static scheduling and allocation algorithm for message-passing architectures by considering factors such as communication delays, link contention, message routing and network topology and to reduce the complexity, the scheduling algorithm is itself parallelized.
Performance Comparison of Algorithms for Static Scheduling of DAGs to Multiprocessors1
13 Citations1998Ishfaq Ahmad, Yu‐Kwong Kwok +1 more
This paper discusses the design philosophies and principles behind these algorithms and assess their merits and deficiencies, and examines several classes of such algorithms known as the arbitrary processor network (APN) scheduling algorithms.
The Computer JournalSelf-adjusting Mapping: A Heuristic Mapping Algorithm for Mapping Parallel Programs on to Transputer Networks
12 Citations1992Hong Shen
A fast heuristic algorithm to solve the problem of mapping parallel programs on to multiprocessor systems on transputer networks of grid structure by combining three modules under a self-adjusting scheme towards a successful mapping result.
Concurrency Practice and ExperienceSymmetrical hopping: A scalable scheduling algorithm for irregular problems
9 Citations1995Min‐You Wu
A new algorithm, Symmetrical Hopping, is presented, a dynamic, distributed, adaptive and scalable scheduling algorithm for dynamic scheduling of ultra-lightweight processes that achieves much better performance due to its adaptiveness.
Parallel Processing LettersPARALLEL INCREMENTAL SCHEDULING
7 Citations1995Min‐You Wu
This paper provides an overview of parallel incremental scheduling, a new approach for load balancing that accurately balances the load by using global load information.
International Journal of Parallel ProgrammingA distributed fair polling scheme applied to OR-parallel logic programming
7 Citations1991Zheng Lin
A task scheduling algorithm for parallel execution of logic programs on NUMA multiprocessors endorces a so-called fair polling policy that achieves reasonable speed-up on benchmarks, using a nonconstant time task migration protocol.
Scientific ProgrammingAdaptive Dynamic Process Scheduling on Distributed Memory Parallel Computers
7 Citations1994Wei Shu
The experimental results show that even though the ACWN algorithm incurs somewhat larger overhead than the randomized allocation, it achieves better performance in most cases due to its adaptiveness, and its feature of quickly spreading the work helps it outperform the gradient model in performance and scalability.
Runtime incremental parallel scheduling (RIPS) for large-scale parallel computers
6 Citations2002Wei Shu, Min‐You Wu
Runtime incremental parallel scheduling is an alternative strategy to the commonly used dynamic scheduling that utilizes advanced parallel scheduling techniques to produce a low-overhead, high-quality load balancing and adapts to applications of nonuniform structures.
Dynamic scheduling of medium-grained processes on distributed memory computers
5 Citations1994Wei Shu
The experimental results show that even though ACWN algorithm incurs larger overhead than randomized allocation, it achieves better performance in most cases due to its adaptiveness, and its feature of fast spreading the work helps it outperform the gradient model in performance and scalability.
NASA Technical Reports Server (NASA)The PARTY parallel runtime system
5 Citations1989Joel Saltz, Ravi Mirchandaney +3 more
An optimized static-workload partitioning is computed for such repetitive-computation pattern problems as the iterative ones employed in scientific computation.
IEEE Transactions on ComputersA systematic approach for mapping application tasks in hypercubes
3 Citations1993Alireza Kavianpour, Nader Bagherzadeh
A systematic approach for mapping application tasks to hypercubes based on a partitioning algorithm in which the final mapping is rendered as a task-node tuple assignment for an n-cube system is proposed.
IEEE Transactions on Parallel and Distributed SystemsDisjoint task allocation algorithms for MIN machines with minimal conflicts
1 Citations1995Chansu Yu, Chita R. Das
A renaming scheme for input and output ports of a MIN is proposed and it is called bit reversal (BR) matching pattern, which can be used with any kind of MIN and minimizes conflicts and partitions the system completely into independent subsystems.