We refine the model underlying our prior work on scheduling cycle-stealing opportunities in NOWs [5, 16], obtaining a model wherein the scheduling guidelines of [16] produce optimal schedules for every such opportunit...
ISBN:
(纸本)9781581131857
We refine the model underlying our prior work on scheduling cycle-stealing opportunities in NOWs [5, 16], obtaining a model wherein the scheduling guidelines of [16] produce optimal schedules for every such opportunity. Although computing optimal schedules usually requires the use of general (often inefficient) function-optimizing methods, we show how to compute optimal schedules efficiently for the broad class of opportunities whose durations come from a concave probability distribution. Even when no such efficient computation of an optimal schedule is available, our refined model always suggests a natural notion of approximately optimal schedule, which may be efficiently computable. We illustrate such efficient approximability via the important class of cycle-stealing opportunities whose durations come from a heavy-tailed distribution. Such opportunities do not admit any optimal schedule—nor even a natural notion of approximately optimal schedule—within the model of [5, 16]. Within our refined model, though, we derive computationally simple schedules for heavy-tailed opportunities, which can be “tuned” to have expected work-output that is arbitrarily close to optimal.
In recent years, the task of allocating jobs to servers has been studied with the “balls and bins” abstraction. Results in this area exploit the large decrease in maximum load that can be achieved by allowing each j...
ISBN:
(纸本)9781581131857
In recent years, the task of allocating jobs to servers has been studied with the “balls and bins” abstraction. Results in this area exploit the large decrease in maximum load that can be achieved by allowing each job (ball) a little freedom in choosing its destination server (bin).In this paper we examine an infinite and parallel allocation process (see [ABS98]) which is related to the “balls and bins” abstraction. The simple process can be used to model many problems arising in applications like load balancing, data accesses for parallel data servers, hashing, and PRAM ***, the parallel allocation process behaves in a highly non-uniform manner which makes its analysis challenging. Even the typically simple question of for which arrival rates the process is stable, is highly non-trivial. In order to cope with this non-uniform behavior we introduce a new sequential process and show (via simulations) that the sequential process models the behavior of the parallel one very accurately. We develop a system of ordinary differential equations in order to describe the behavior of our sequential process and present a thorough analysis of the performance this process. For example, we show that the queue length distribution decreases double-exponentially. Finally, we present simulation results indicating that the solutions to the differential equations very well predict the queue length distribution of our sequential process and the largest injection rate for which it is ***, we can conclude that in all the performance characteristics we have measured experimentally, the parallel and the sequential process are closely related. This indicates that the obtained solution of the differential equations and the results presented above are applicable to the parallel process, too.
The problem of obtaining efficient solutions for parallel evaluation of linear algebraic circuits (LAC) is considered. The parallelism is obtained through matrix multiplications. A CREW PRAM algorithm is used, in whic...
详细信息
The problem of obtaining efficient solutions for parallel evaluation of linear algebraic circuits (LAC) is considered. The parallelism is obtained through matrix multiplications. A CREW PRAM algorithm is used, in which, during execution, propagates computed values into future matrix products, and uses a special scheduling of the matrix multiplications to reduce constant factors of the execution times.
The black box procedures for testing whether a parallel data structure behaved correctly are considered. The first systematic study of algorithms and hardness results for such testing procedures is presented, focusing...
详细信息
The black box procedures for testing whether a parallel data structure behaved correctly are considered. The first systematic study of algorithms and hardness results for such testing procedures is presented, focusing on queues, priority queues, stacks, and counters. The importance of selecting test data, such that distinct values are inserted into the data structures is shown.
An efficient implementation of simple randomized merging (SRM) algorithm was developed based upon novel data structures. The SRM's lookahead forecasting technique and forecast and flush technique were used for par...
详细信息
An efficient implementation of simple randomized merging (SRM) algorithm was developed based upon novel data structures. The SRM's lookahead forecasting technique and forecast and flush technique were used for parallel prefetching and buffer management, respectively. The techniques resulted in significant improvement in the way SRM carries out the parallel, independent disk accesses necessary to efficiently read blocks of input runs during external merging.
暂无评论