2855119
Optimal Scheduling of Aperiodic Jobs on Cluster
This paper presents an algorithm to schedule aperiodic jobs on a cluster system. A cluster consists of one dispatcher and multiple schedulers. The algorithm is optimal for the response time of each aperiodic job. Aperiodic jobs are partitioned into phases and assigned deadlines by the dispatcher. With the deadline, the aperiodic jobs can be scheduled uniformly under EDF (Earliest Deadline First) together with periodic jobs. With rigorous theoretical analysis and proof, we have that even if the dispatcher has no scheduling information, the algorithm can still dispatch the aperiodic jobs onto the proper scheduler to achieve optimal response time and also guarantee the deadline requirements of periodic jobs.
14096392
Mapping DAG-based applications to multiclusters with background workload
Before an application modelled as a directed acyclic graph (DAG) is executed on a heterogeneous system, a DAG mapping policy is often enacted. After mapping, the tasks (in the DAG-based application) to be executed at each computational resource are determined. The tasks are then sent to the corresponding resources, where they are orchestrated in the pre-designed pattern to complete the work. Most DAG mapping policies in the literature assume that each computational resource is a processing node of a single processor, i.e. the tasks mapped to a resource are to be run in sequence. Our studies demonstrate that if the resource is actually a cluster with multiple processing nodes, this assumption will cause a mis-perception in the tasks' execution time and execution order. This will disturb the pre-designed cooperation among tasks so that the expected performance cannot be achieved. In this paper, a DAG mapping algorithm is presented for multicluster architectures. Each constituent cluster in the multicluster is shared by background workload (from other users) and has its own independent local scheduler. The multicluster DAG mapping policy is based on theoretical analysis and its performance is evaluated through extensive experimental studies. The results show that compared with conventional DAG mapping policies, the new scheme that we present can significantly improve the scheduling performance of a DAG-based application in terms of the schedule length.
37859827
Optimal dispatching and scheduling for both periodic and aperiodic jobs in cluster
Presents dispatching and scheduling algorithms for both periodic and aperiodic jobs on a cluster of computers. A cluster system consists of one front-end node, called dispatcher and multiple back-end nodes, called schedulers. By rigorous theoretical analysis, these algorithms are optimal in the sense that each aperiodic job can achieve the shortest response time in the cluster while maintaining the schedulability of periodic jobs. The aperiodic jobs, which have no deadline requirement, are partitioned into phases and assigned deadlines by the dispatcher With the deadlines the aperiodic jobs can be scheduled uniformly under EDF together with periodic jobs. Based on extensive simulation studies, we have that the algorithms proposed in the paper can achieve great performance improvement. We also work out the workload zone in which the response time of aperiodic jobs in the cluster with N schedulers is the same as the ideal bound of response time in the corresponding M/M/N model.
14206406
Performance-Aware Workflow Management for Grid Computing
Grid middleware development has advanced rapidly over the past few years to support component-based programming models and service-oriented architectures. This is most evident with the forthcoming release of the Globus toolkit (GT4), which represents a convergence of concepts (and standards) from both the grid and web-services communities. Grid applications are increasingly modular, composed of workflow descriptions that feature both resource and application dynamism. Understanding the performance implications of scheduling grid workflows is critical in providing effective resource management and reliable service quality to users. This paper describes a series of extensions to an existing performance-aware grid management system (TITAN). These extensions provide additional support for workflow prediction and scheduling using a multi-domain performance management infrastructure.
16360889
Optimising static workload allocation in multiclusters
Summary form only given. Workload allocation and job dispatching are two fundamental components in static job scheduling for distributed systems. We address the static workload allocation techniques for two types of job stream in multicluster systems, namely, nonreal-time job streams and soft-real-time job streams, which request different qualities of service. Two workload allocation strategies (called ORT and OMR) are developed by establishing and numerically solving two optimisation equation sets. The ORT strategy achieves the optimised mean response time for the nonreal-time job stream; while the OMR strategy can gain the optimised mean miss rate for the soft-real-time job stream over multiple clusters (these strategies can also be applied in a single cluster system). The effectiveness of both strategies is demonstrated through theoretical analysis. The proposed workload allocation schemes are combined with two job dispatching strategies (weighted random and weighted round-robin) to generate new static job scheduling algorithms for multicluster environments. These algorithms are evaluated through extensive experimental studies and the results show that compared with static approaches without the optimisation techniques, the proposed workload allocation schemes can significantly improve the performance of static job scheduling in multiclusters, in terms of both the mean response time (for the nonreal-time jobs) and the mean miss rate (for soft-real-time jobs).
9439581
Light Weight Background Blurring for Video Conferencing Applications
Background blurring is an effective way to both preserving privacy and keeping communication effective during video conferencing. This paper proposes a light weight real-time algorithm to perform background blurring using a fast background modeling algorithm combined with a face detector/tracker. A soft decision is made at each pixel whether it belongs to the foreground or the background based on multiple vision features. The classification results are mapped to a per-pixel blurring radius image to blur the background. The algorithm produces satisfactory results under a wide range of conditions, and occupies less than 30% of the CPU cycles on a 3 GHz Pentium 4 machine without further optimization.
17606652
Solving the Chan-Vese Model by a Multiphase Level Set Algorithm Based on the Topological Derivative
In this work, we specifically solve the Chan-Vese active contour model by multiphase level set methods. We first develop a fast algorithm based on calculating the variational energy of the Chan-Vese model without the length term. We check whether the energy decreases or not when we move a point to another segmented region. Then we draw a connection between this algorithm and the topological derivative, a concept emerged from the shape optimization field. Furthermore, to include the length term of the Chan-Vese model, we apply a preprocessing step on the image by using nonlinear diffusion. We show numerical experiments to demonstrate the efficiency and the robustness of our algorithm.
5542322
Rendering with concentric mosaics
An image based system and process for rendering novel views of a real or synthesized 3D scene based on a series of concentric mosaics depicting the scene. In one embodiment, each concentric mosaic represents a collection of consecutive slit images of the surrounding 3D scene taken from a different viewpoint tangent to a circle on a plane within the scene. Novel views from viewpoints within circular regions of the aforementioned circle plane defined by the concentric mosaics are rendered using these concentric mosaics. Specifically, a slit image can be identified by a ray originating at its viewpoint on the circle plane and extending toward the longitudinal midline of the slit image. Each of the rays associated with the slit images needed to construct a novel view will either coincide with one of the rays associated with a previously captured slit image, or it will pass between two of the concentric circles on the circle plane. If it coincides, then the previously captured slit image associated with the coinciding ray can be used directly to construct part of the novel view. If the ray passes between two of the concentric circles of the plane, then the needed slit image is interpolated using the two previously captured slit images associated with the rays originating from the adjacent concentric circles that are parallel to the non-coinciding ray. If the objects in the 3D scene are close to the camera, depth correction is applied to reduce image distortion for pixels located above and below the circle plane. In another embodiment, a single camera is used to capture a sequence of images. Each image includes image data that has a ray direction associated therewith. To render an image at a novel viewpoint, multiple ray directions from the novel viewpoint are chosen. Image data is combined from the sequence of images by selecting image data that has a ray direction substantially aligning with the ray direction from the novel viewpoint.
2560002
Automating lecture capture and broadcast: technology and videography
Abstract.Our goal is to help automate the capture and broadcast of lectures to online audiences. Such systems have two interrelated design components. The technology component includes hardware and associated software. The aesthetic component comprises the rules and idioms that human videographers follow to make a video visually engaging; these rules guide hardware placement and software algorithms. We report the design of a complete system that captures and broadcasts lectures automatically and report on a user study and a detailed set of video-production rules obtained from professional videographers who critiqued the system, which has been deployed in our organization for 2 years. We describe how the system can be generalized to a variety of lecture room environments differing in room size and number of cameras. We also discuss gaps between what professional videographers do and what is technologically feasible today.
11874775
Microarchitecture Level Interconnect Modeling Considering Layout Optimization
— In this paper, we study microarchitecture-level interconnect modeling for power and performance. Considering structural interconnects, layer assignment, and concurrent repeater and Flip-Flop (FF) insertion, we develop cycle-accurate microarchitecture-level power and throughput simulation and obtain an accurate modeling of interconnects at the early design stage. Experiment show that the simulation reduces over-estimation by up to 2.24X compared to the conventional power estimation based on purely stochastic interconnects and fixed switching factor. Furthermore, we optimize throughput with consideration of FF insertion for interconnects and floorplanning optimization. We show that throughput is not always higher for an increased clock frequency, and there exists an optimal clock frequency to maximize throughput for a given microarchitecture and given floorplan. In addition, floorplan optimized for IPC (instructions per cycle)-critical interconnects has little on the total interconnect length but improves throughput by 23.49%. As FF insertion becomes necessary to achieve the clock frequency specified by ITRS, we conclude that the traditional design flow optimizing IPC and clock frequency separately is no longer valid, and coupled microarchitecture and layout optimization may improve both power efficiency and throughput.