In this paper, we describe an effort to preserve the semantics and relationships between Digital Objects content. As the system ingests the content, it has to understand and parse structures of files and packages that hold bundles of digital content. It also has to map the content to an ontology that captures domain knowledge, allowing for preservation of the relationships among incoming data while improving data access and retrieval at the later time.

Three dimensional reconstruction of a rigid object from monocular video sequences is addressed. Initially object pose is estimated in each image by locating similar (unknown) textures assuming flat depth maps for all input images. Shape-from-silhouette Szeliski (1993) is then applied to make a 3-D model (volume), which is used for a new round of pose estimation, this time by a model-based method giving better estimates. Before repeating this process by building a new volume, pose estimates are adjusted to reduce error by maximizing a quality measure for shape-from-silhouette volume reconstruction. The volume feedback is terminated when pose estimates do not change much as compared to those produced by previous iteration. The final output is a pose index (the last set of pose estimates) and a volume. Good performance of the system is shown by several experiments. No model is assumed for the object. Feature points are neither detected nor tracked: no problematic feature matching or correspondence. The high-level pose index generated for input images can be used for content-based retrieval. Our method can be also applied to 3-D object tracking in video.

In concatenative Text-to-Multimedia composition systems, accurate endpoint detection of the uttered audio words, used as input into such systems, is needed to ensure optimal audio concatenation. In this paper, we outline a method of endpoint detection that takes advantage of the fact that the text of the audio word is known before endpoint detection actually takes place. From the text, the associated phonemes for an uttered audio word can be determined and used to fine tune the endpoint detection for a specific given phoneme.

We provide scheduling techniques to enable cluster tools to produce different kinds of wafers at the same time. In this model, the multi-route model, wafers can visit different processing modules in their path. Some of these processing modules may have a limit on how long they allow the wafer to stay after the process is finished. If none of the modules have this timing constraint, we provide a greedy algorithm to schedule the multi-route cluster tool. However, if some modules have a timing constraint, the scheduling problem becomes more complicated, and an exhaustive search in a very large search space must be performed to find the optimal schedule. The exhaustive search may take as long as an hour to come up with the answer, and is not practical. We provide a simulated annealing technique to find a near-optimal schedule. To evaluate each state in the simulated annealing we need to solve a linear programming system. Instead of solving that LP system with conventional methods, we provide a much faster method. This method that uses shortest path algorithm and binary search improves the performance of the simulated annealing significantly. Our experiments showed that we can find a near-optimal solution in less than 2 minutes with this method.

Visual presentation of a talking person requires the generation of image frames showing the speaker in various views while pronouncing various phonemes. The existing approaches, mostly use either a complex 3D geometric model to reconstruct a desired image or a set of 2D images for each viewpoint, to select from. We propose a new system which utilizes facial feature detection and image-based transformation to create any talking frame using only one given image from the desired viewpoint and a set of reference images from one standard view. The proposed approach, together with optical flow-based view morphing and a customizable concatenative text-to-speech, makes a personalized visual speech generation system which can be used for moving/talking head applications where an optimal trade-of between computational complexity and image database requirements is necessary.

This paper discusses two scheduling techniques for dual-arm cluster tools that address both process module and transport-module residency constraints and throughput requirements. The first technique is an extension of our previous work (2000) that only addressed process-module residency constraints. For cases with long process times, this technique can take a long time to find the solution and is not practical. Hence, we use this algorithm mainly as a benchmark for comparison. The second technique that uses a linear programming method with several heuristics can find the optimal solution very efficiently. An analytical and experimental analysis of this technique shows the correctness, completeness and efficiency of this technique.

In a cluster tool where process modules have residency constraints, an optimal schedule may need to buffer the partially processed wafers. In previous approaches, one of the active resources (i.e. the transport module) was used as a temporary buffer. In this approach we try to use a resource that is usually available in cluster tools and is only used for tool maintenance reasons. This passive module that we refer to as buffer module, can hold the partially processed wafers, and free the transport module (TM). Our experiment shows that in 57% of the cases, because the TM can perform other actions while the wafer is buffered in the buffer module, a schedule with better throughput was found.

Discusses a scheduling technique, for cluster tools, that addresses postprocessing residency constraints and throughput requirements. The residency constraints impose a limit on the postprocessing time that a material unit spends in a processing module. The technique searches in the time and resource domains for a feasible schedule with a maximum throughput. It operates in two main phases; the initial one of which (and the lower complexity one) computes a simple periodic schedule. For a large number of problem instances, the simple periodic schedule feasibly solves the problem. If a feasible schedule cannot be found in the first phase, the scheduler enters phase two (the higher complexity one) to compute a feasible schedule. During this phase, the scheduler incrementally increases the period only if necessary, to keep the throughput at a maximum. Several heuristics are designed and added to reduce the complexity of the scheduling algorithm. The resulting schedules are deadlock free, since resources are scheduled according to the times that they are available. Analytical and experimental analyses demonstrate the correctness and efficiency of our proposed technique.

Introduces a novel approach for rigid object pose estimation. The system rotates a reference frame of the object of interest until it reaches a view at which the rotated reference view and the unknown-pose view seem to be "similar". A number of pose similarity measures were tested for different types of objects undergoing various amounts of rotation from the reference pose. We demonstrate that the sum of the texture difference and the mask difference can be used as an effective pose similarity measure, which is capable of a unique determination of the correct pose. A number of optimization methods (e.g. genetic algorithms) were used as feedback from pose comparison to reference frame rotation. The results of comparing these methods in a number of experiments is reported in this paper as well.

Discrete media (DM) data throughput is vital to systems that need to support the heterogeneity and variety of data found in interactive hypermedia and digital library applications. Therefore, a multimedia server's ability in delivering a high DM data throughput without degrading its CM data throughput deserves more attention. In this paper, we address this issue by optimizing the use of disk bandwidth spent on CM service at run-time and redirecting the saved bandwidth to service DM requests. Based on a new cost model of disk access incurred in CM service, we formulate strategies to control the size of each disk read at run time. These strategies improve the efficiency of each disk access and improve the DM data throughput of a multimedia server, without jeopardizing the CM throughput. Through experimental evaluations, the improvements achieved are demonstrated. Furthermore, efficient control of the allocation of disk bandwidth between DM and CM services over a wide range is also demonstrated.

Algorithms for scheduling independent tasks on to the processors of a multiprocessor system must trade-off processor load balance, memory locality, and scheduling overhead. Most existing algorithms, however, do not adequately balance these conflicting factors. This paper introduces the self-adjusting dynamic scheduling (SADS) class of algorithms that use a unified cost model to explicitly account for these factors at runtime. A dedicated processor performs scheduling in phases by maintaining a tree of partial schedules and incrementally assigning tasks to the least-cost schedule. A scheduling phase terminates whenever any processor becomes idle, at which time partial schedules are distributed to the processors. An extension of the basic SADS algorithm, called DBSADS, controls the scheduling overhead by giving higher priority to partial schedules with more task-to-processor assignments. These algorithms are compared to two distributed scheduling algorithms within a database application on an Intel Paragon distributed memory multiprocessor system.

Puzzles have traditionally been used as popular benchmarks for evaluating different problem solving strategies. Many of the game benchmarks are suitable for evaluating static scheduling techniques. In such benchmarks, the scheduling phase and the execution phase (i.e. when the schedule is executed to play the game) are disjoint. The scheduling technique can be executed to compute a complete schedule prior to the execution of any moves to play the game. Due to recent interest in on-line problem solving techniques, there is a need for benchmarks which can evaluate the performance trade-offs of dynamic scheduling techniques. Many modern video and computer games can be suitable candidates for dynamic scheduling benchmarks, since they require on-line problem solving. These benchmarks and their system testbeds should be chosen and implemented such that they can accurately reveal important performance trade-offs of dynamic scheduling techniques. In this paper, we introduce a dynamic scheduling benchmark and its system testbed. This benchmark is based on an extended version of the Tetris computer game. The rules and semantics of the game were modified to lend themselves well to evaluation of discrete problem solving and optimization techniques. The system testbed is implemented in a distributed and asynchronous fashion, on a network of workstations, to reveal performance trade-offs between scheduling time, schedule quality, and problem constraints.

We study the problem of providing real-time service to hard and soft real-time messages in wavelength division multiplexing (WDM) optical networks. We propose and evaluate a set of scheduling algorithms which schedule message transmissions in single-hop WDM passive star networks based on specific time constraints. We compare the performances of our algorithms with that of the typical WDM scheduling algorithm which does not consider the time constraint of the transmitted messages by discrete-event simulations and an analytical model. We find that the improvement on real-time performance can be attributed to our scheduling algorithms where the time constraint of messages has been taken into consideration. This study suggests that when scheduling real-time messages in WDM networks, one has to consider not only the problem of resources allocation in the network but also the problem of sequencing messages based on their time constraints.

Scheduling real time tasks in a distributed memory multiprocessor is characterized as sequencing a set of tasks and assigning them to processors of the architecture. Real time systems research has extensively investigated the sequencing dimension of the scheduling problem by extending uniprocessor scheduling techniques to more complex architectures. We introduce a technique that uses an assignment oriented representation to dynamically schedule real time tasks on the processors of the system. The technique we propose, automatically controls and allocates the scheduling time, in order to minimize deadline violation of real time tasks, due to the scheduling overhead. We evaluate this technique in the context of scheduling real time transactions in a distributed database application which we implemented on an Intel Paragon distributed memory multiprocessor. In this implementation, we compared the performance of our algorithm with another dynamic algorithm that uses a sequence oriented representation. The results show interesting performance trade-offs among the candidate algorithms and validate our conjectures about scalability performance limitations of sequence oriented representations. The results also show the effect of the mechanisms that our technique uses to control and allocate scheduling time.

Parallel computing on clusters of workstations is receiving much attention from the research community. Unfortunately, many aspects of parallel computing over this parallel computing engine is not very well understood. Some of these issues include the workstation architectures, the network protocols, the communication-to-computation ratio, the load balancing strategies, and the data partitioning schemes. The aim of this paper is to assess the strengths and limitations of a cluster of workstations by capturing the effects of the above issues. This has been achieved by evaluating the performance of this computing environment in the execution of a parallel ray tracing application through analytical modeling and extensive experimentation.

Efficiently scheduling parallel tasks on to the processors of a shared-memory multiprocessor is critical to achieving high performance. Given perfect information at compile-time, a static scheduling strategy can produce an assignment of tasks to processors that ideally balances the load among the processors while minimizing the run-time scheduling overhead and the average memory referencing delay. Since perfect information is seldom available, however, dynamic scheduling strategies distribute the task assignment function to the processors by having idle processors allocate work to themselves from a shared queue. While this approach can improve the load balancing compared to static scheduling, the time required to access the shared work queue adds directly to the overall execution time. To overlap the time required to dynamically schedule tasks with the execution of the tasks, we examine a class of self-adjusting dynamic scheduling (SADS) algorithms that centralizes the assignment of tasks to processors. These algorithms dedicate a single processor of the multiprocessor to perform a novel on-line branch-and-bound technique that dynamically computes partial schedules based on the loads of the other processors and the memory locality (affinity) of the tasks and the processors. Our simulation results show that this centralized scheduling outperforms self-scheduling algorithms even when using only a small number of processors.

We introduce a new set of dynamic scheduling algorithms for scheduling and guaranteeing the deadline compliance of a set of aperiodic real-time tasks on a uniprocessor architecture. The task model selected is that of non-preemptable tasks with arbitrary start times and deadlines. The proposed algorithms address a fundamental trade-off in dynamic scheduling between the cost of scheduling and the quality of the resulting schedules. The algorithms control the time allocated to scheduling explicitly, in order to obtain good-quality schedules in reasonable times. We show that taking into account the scheduling time is crucial for honoring the deadlines of scheduled real-time tasks. We provide an experimental evaluation of our algorithms via performance comparisons with existing landmark algorithms that were originally designed to address some similar issues. The results of our experiments show that our algorithms outperform the existing techniques in several parameter configurations.

There are many application domains such as flexible manufacturing systems (FMS) in which the world changes during the problem solving process or about which the problem solver does not have complete information a priori. A problem solver in such environments is required to take advantage of up-to-date information that becomes available, on line, and to use this information in order to avoid producing solutions that are obsolete by the time they are to be executed. In this paper, we propose an algorithm which performs problem solving on line in order to obtain new information about the availability of resources in its local surroundings. The algorithm performs partial planning followed by partial execution, in order to take immediate advantage of resources which become available and remain available for a short period of time. As part of this paper, we introduce a model of dynamicity included in a graph representation of a task. The decision on the time points at which the resource availability information is probed and updated is automatically made according to the parameters of the model of dynamicity in the environment. We provide theoretical and empirical analyses of the proposed algorithm for a routing problem in the proposed dynamic model. A set of candidate algorithms were chosen for the performance-comparison experiments each of which is suitable for a particular condition (i.e. some produce good results in a static environment and some produce better results in a highly dynamic environment). Results of our performance-comparison experiments show that the proposed algorithm performs as well as the best of the candidate algorithms under a wide range of experiment parameters. The results also show that the proposed algorithm is capable of automatically adapting to the degree of dynamicity in the environment.

In many dynamic application domains, the environment changes during problem solving. A problem solver, in these applications, does not have complete information about the task and resources, a priori. The problem solver is required to use up-to-date information that becomes available on line. It must use this information to avoid producing solutions that are obsolete by the time they are to be executed. The problem solver has to be opportunistic, in order to take immediate advantage of resources that become available and remain available for a short period of time. How opportunistic the algorithm should be depends on the degree of dynamicity in the environment. In this paper, we propose an algorithm which performs problem solving on line in order to obtain new information about the availability of resources in the system. The proposed algorithm adjusts itself automatically to adapt to the degree of dynamicity in the environment. We introduce a model of dynamicity in a graph representation of a task. We provide theoretical and empirical analyses of our algorithm for a routing problem in the proposed dynamic model. Our theoretical analyses demonstrate the correctness and completeness properties of our algorithm. Results of our performance-comparison experiments show that the proposed algorithm performs as well as the best of the candidate algorithms under a wide range of experiment parameters. The results also show that the proposed algorithm is capable of automatically adapting to the degree of dynamicity in the environment.

Abstract There has been a recent increase of interest in heterogeneous computing systems, due partly to the fact that a single parallel architecture may not be adequate for exploiting all of a program's available parallelism. In some cases, heterogeneous systems have been shown to produce higher performance for lower cost than a single large machine. However, there has been only limited work on developing techniques and frameworks for partitioning and scheduling applications across the components of a heterogeneous system. In this paper we propose a general model for describing and evaluating heterogeneous systems that considers the degree of uniformity in the processing elements and the communication channels as a measure of the heterogeneity in the system. We also propose a class of dynamic scheduling algorithms for a heterogeneous computing system interconnected with an arbitrary communication network. These algorithms execute a novel optimization technique to dynamically compute schedules based on the potentially non‐uniform computation and communication costs on the processors of a heterogeneous system. A unique aspect of these algorithms is that they easily adapt to different task granularities, to dynamically varying processor and system loads, and to systems with varying degrees of heterogeneity. Our simulations are designed to facilitate the evaluation of different scheduling algorithms under varying degrees of heterogeneity. The results show improved performance for our algorithms compared to the performance resulting from existing scheduling techniques.

Techniques for scheduling parallel tasks on to the processors of a multiprocessor architecture must tradeoff three interrelated factors: 1) scheduling and synchronization costs, 2) load balancing, and 3) memory locality. Current scheduling techniques typically consider only one or two of these three factors at a time. We propose a novel Self- Adjusting Scheduling (SAS) algorithm that addresses all three factors simultaneously. This algorithm dedicates a single processor to execute an on-line branch-and-bound algorithm to search for partial schedules concurrent with the execution of tasks previously assigned to the remaining processors. This overlapped scheduling and execution, along with self-adjustment of duration of partial scheduling periods reduces scheduling and synchronization costs significantly. To satisfy the load-balancing and locality management, SAS introduces a unified cost model that accounts for both of these factors simultaneously. We compare the simulated performance of SAS with the Affinity Scheduling algorithm (AFS). The results of our experiments demonstrate that the potential loss of performance caused by dedicating a processor to scheduling is outweighed by the higher performance produced by SAS's dynamically adjusted schedules, even in systems with a small number of processors. SAS is a general on-line optimization technique that can be applied to a variety of dynamic scheduling problems.

Real-time search algorithms need to address the deadlines imposed by applications like process control and robot navigation. Possible deadline violations should be predicted ahead of time to allow remedial actions to prevent the undesirable consequences of missing deadlines. The algorithms should also demonstrate progressively optimizing behavior. That is, they should improve the quality of the solutions as time constraints are relaxed. To successfully address these issues, a real-time search algorithm must address the central problem of choosing the proper values for its parameters, which control the time allocated to planning. The authors propose a new approach to determine the parameter values of a real-time search algorithm, in order to enable the algorithm to meet deadlines, exhibit progressively optimizing behavior, and to predict deadline violation prior to the deadline. They provide a theoretical and experimental characterization of the proposed algorithm.

An approach to learning query-transformation rules based on analyzing the existing data in the database is proposed. A framework and a closure algorithm for learning rules from a given data distribution are described. The correctness, completeness, and complexity of the proposed algorithm are characterized and a detailed example is provided to illustrate the framework.>

The authors provide a method for the specification of real-time artificial intelligence (AI) problem solvers. Using this method, a formal specification of a real-time problem is presented. In addition, a method for analyzing real-time AI problem solvers is examined using a case study of two real-time problem solvers, namely DYNORAII and RTA* for the real-time path planning problem. New results on worst-case and average-case complexity of the problem, and of the algorithms that solve it, and an experimental evaluation of DYNORAII and RTA* for deadline compliance and response-time minimization are provided.>

A classification of different dynamic worlds is presented. A detailed model of a dynamic world where changes occur in edge costs around a zero mean is provided. A formal analysis of the model suggests that the static rank ordering of solution paths is preserved in the model. Two real-time search algorithms, DYNORAII and RTA*, for the real-time path planning problem are analyzed. Results on the path planning problem using the proposed dynamic model of graphs are given. The ability of DYNORAII and RTA* to minimize response times in dynamic environments has been evaluated experimentally. It is found that DYNORAII outperforms RTA* in minimizing response times.>

Most real-time planning algorithms address either the issue of response-time constraints or the issue of dynamic environments. A new real-time planning algorithm, DYNORA, is proposed to address both of these issues simultaneously. DYNORA is structured as a sequence of partial planning and execution cycles to avoid obsolescence of planning solutions at the time of execution. DYNORA uses a stopping criterion to balance planning cost and execution cost to achieve near optimal response times. DYNORA was used for the routing problem to optimize total cost. It shows better average-case time complexity than traditional real-time algorithms.>