We provide scheduling algorithms that attempt to maximize the profits of a broadcast-based electronic delivery service for digital products purchased, for example, at e-commerce sites on the World Wide Web. Examples of such products include multimedia objects such as CDs and DVDs. Other examples include software and, with increasing popularity, electronic books as well. We consider two separate alternatives, depending in part on the sophistication of the set-top box receiving the product at the customer end. The first, more restrictive option, assumes that the atomic unit of transmission of the product is the entire object, which must be transmitted in order from start to finish. We provide a solution based in part on a transportation problem formulation for this so-called noncyclic scheduling problem. The second alternative, which is less restrictive, assumes that the product may be transmitted cyclically in smaller segments, starting from an arbitrary point in the object. Three heuristics are provided for this difficult cyclic scheduling problem. Both scenarios assume that the broadcasts of the same digital product to multiple customers can be "batched." We examine the effectiveness of these algorithms via simulation experiments under varying parametric assumptions. Each of the three cyclic scheduling algorithms perform better than the noncyclic algorithm. Moreover, one of the cyclic scheduling algorithms emerges as the clear winner.

Detecting and resolving performance problems in distributed systems often requires measurements of end-to-end ("finger tip to eyeball") response times. Existing approaches embed transaction definitions in instrumentation codes. As a result, service providers (e.g., ISPs) cannot tailor transaction definitions to the usage patterns of their customers. We propose a new approach-ETE (end-to-end)-in which transaction definitions are externalized so that they can be customized. This is accomplished by having instrumentation generate events (not transactions) and employing a separate component-the transaction generator-that uses external definitions of transactions to construct response time measurements from event streams. ETE provides measurements of both end-to-end response times and their components. The latter reflect delays for services within distributed systems (e.g., name resolution service). We have used ETE to measure response times for Web transactions, terminal emulators, and Lotus Notes.

Consider a system of independent tasks to be scheduled without preemption on a parallel computer. For each task the number of processors required, the execution time, and a weight are known. The problem is to find a schedule with minimum weighted average response time. We present an algorithm called SMART (which stands for scheduling to minimize average response time) for this problem that produces solutions that are within a factor of 8.53 of optimal. To our knowledge this is the first polynomial-time algorithm for the minimum weighted average response time problem that achieves a constant bound. In addition, for the unweighted case (that is, where all the weights are unity) we describe a variant of SMART that produces solutions that are within a factor of 8 of optimal, improving upon the best known bound of 32 for this special case.

We introduce a new framework for classifying large images (in the EOS; Earth Observing System) that is more accurate and less computationally expensive than the classical pixel-by-pixel approach. This approach, called progressive classification, is well suited for analyzing large images, such as multispectral satellite scenes, compressed with wavelet-based or block-transform-based transformations. These transformations produce a multiresolution pyramid representation of the data. A progressive classifier analyses the image at the coarsest resolution level, and it decides whether each coefficient corresponds to a homogeneous block of pixels in the original image or to a heterogeneous block. In the first case it labels the block, in the second case it recursively analyzes the region of the image at the immediately finer resolution level. Computational efficiency, compared to the classical approach, results from examining a much smaller number of coefficients than the number of pixels in the original image. Thus, progressive classification is a prime candidate as a content-based search operator for remotely-sensed data.

There has been a good deal of progress made recently toward the efficient parallelization of individual phases of single queries in multiprocessor database systems. In this paper we devise and experimentally evaluate a number of scheduling algorithms designed to handle multiple parallel queries. (Scheduling in this context implies the determination of both processor allotments and temporal processor assignments to individual queries and query phases.) One of these algorithms performs the best in our experiments. This algorithm is hierarchical in nature: In the first phase, a good quality precedence based schedule is created for each individual query and each possible number of processors. This component employs dynamic programming. In the second phase, the results of the first phase are used to create an overall schedule of the full set of queries. This component is based on previously published work on nonprecedence-based malleable scheduling. Even though the problem we are considering is NP-hard in the strong sense, the multiple query schedules generated by our hierarchical algorithm are seen experimentally to achieve high quality results.>

There has been a good deal of progress made recently towards the efficient parallelization of individual phases of single queries in multiprocessor database systems. In this paper we devise and evaluate a number of scheduling algorithms designed to handle multiple parallel queries. One of these algorithms emerges as a clear winner. This algorithm is hierarchical in nature: In the first phase, a good quality precedence-based schedule is created for each individual query and each possible number of processors. This component employs dynamic programming. In the second phase, the results of the first phase are used to create an overall schedule of the full set of queries. This component is based on previously published work on nonprecedence-based malleable scheduling. Even though the problem we are considering is NP-hard in the strong sense, the multiple query schedules generated by our hierarchical algorithm are seen experimentally to achieve results which are close to optimal.

A parallelizable (or malleable) task is one which can be run on an arbitrary number of processors, with a task execution time that depends on the number of processors allotted to it. Consider a system of M independent parallelizable tasks which are to be scheduled without preemption on a parallel computer consisting of P identical processors. For each task, the execution time is a known function of the number of processors allotted to it. The goal is to find (1) for each task i, an allotment of processors β, and (2) overall, a non-preemptive schedule assigning the tasks to the processors which minimizes the average response time of the tasks. Equivalently, we can minimize the flow time which is the sum of the completion times of each of the tasks.

Parallel processing is an attractive option for relational database systems. As in any parallel environment however, load balancing is a critical issue which affects overall performance. Load balancing for one common database operation in particular, the join of two relations, can be severely hampered for conventional parallel algorithms, due to a natural phenomenon known as data skew. In a pair of recent papers (J. Wolf et al., 1993; 1993), we described two new join algorithms designed to address the data skew problem. We propose significant improvements to both algorithms, increasing their effectiveness while simultaneously decreasing their execution times. The paper then focuses on the comparative performance of the improved algorithms and their more conventional counterparts. The new algorithms outperform their more conventional counterparts in the presence of just about any skew at all, dramatically so in cases of high skew.>

Presents a parallel hash join algorithm that is based on the concept of hierarchical hashing, to address the problem of data skew. The proposed algorithm splits the usual hash phase into a hash phase and an explicit transfer phase, and adds an extra scheduling phase between these two. During the scheduling phase, a heuristic optimization algorithm, using the output of the hash phase, attempts to balance the load across the multiple processors in the subsequent join phase. The algorithm naturally identifies the hash partitions with the largest skew values and splits them as necessary, assigning each of them to an optimal number of processors. Assuming for concreteness a Zipf-like distribution of the values in the join column, a join phase which is CPU-bound, and a shared nothing environment, the algorithm is shown to achieve good join phase load balancing, and to be robust relative to the degree of data skew and the total number of processors. The overall speedup due to this algorithm is compared to some existing parallel hash join methods. The proposed method does considerably better in high skew situations.>

Nonblocking algorithms for concurrent data structures guarantee that a data structure is always accessible. This is in contrast to blocking algorithms in which a slow or halted process can render part or all of the data structure inaccessible to other processes.

In this paper we formulate the following natural multiprocessor scheduling problem: Consider a parallel system with P processors. Suppose that there are Ntasks to be scheduled on this system, and that the execution time of each task j ε {1,…,N} is a nonincreasing function tj(βj) of the number of processors βj ε {1,…,P} allotted to it. The goal is to find, for each task j, an allotment of processors βj, and, overall, a schedule assigning the tasks to the processors which minimizes the makespan, or latest task completion time. The so-called shelf strategy is commonly used for orthogonal rectangle packing, a related and classic optimization problem. The prime difference between the orthogonal rectangle problem and our own is that in our case the rectangles are, in some sense, malleable: The height of each rectangle is a nonincreasing function of its width. In this paper, we solve our multiprocessor scheduling problem exactly in the context of a shelf-based paradigm. The algorithm we give uses techniques from resource allocation theory and employs a variety of other combinatorial optimization techniques.

A model for studying the optimal allocation of cache memory among two or more competing processes is developed and used to show that, for the examples studied, the least recently used (LRU) replacement strategy produces cache allocations that are very close to optimal. It is also shown that when program behavior changes, LRU replacement moves quickly toward the steady-state allocation if it is far from optimal, but converges slowly as the allocation approaches the steady-state allocation. An efficient combinatorial algorithm for determining the optimal steady-state allocation, which, in theory, could be used to reduce the length of the transient, is described. The algorithm generalizes to multilevel cache memories. For multiprogrammed systems, a cache-replacement policy better than LRU replacement is given. The policy increases the memory available to the running process until the allocation reaches a threshold time beyond which the replacement policy does not increase the cache memory allocated to the running process.>

A parallel hash join algorithm based on the concept of hierarchical hashing is proposed to address the problem data skew. The proposed algorithm adds an extra scheduling phase to the usual hash and join phases. During the scheduling phase, a heuristic optimization algorithm, using the output of the hash phase, attempts to balance the load across the multiple processors in the subsequent join phase. The algorithm naturally identifies the hash partitions with the largest skew elements, splits them up, and assigns each of them to an optimal number of processors. Assuming a Zipf-like distribution of the elements in the join column, the algorithm is shown to achieve good load balancing for the join phase in a CPU-bound environment, and it is shown to be fairly robust relative to the degree of data skew and the total number of processors. The overall speedup due to this algorithm is compared with conventional parallel hash join methods and the considerable advantage of the proposed method is demonstrated even when the additional scheduling phase is taken into account.>

An efficient, exact algorithm is developed for optimizing the performance of nested block joins. The method uses both dynamic programming and branch-and-bound. In the process of deriving the algorithm, the class of resource allocation problems for which the greedy algorithm applies has been extended. Experiments with this algorithm on extremely large problems show that it is superior to all other known algorithms by a wide margin.>