1720429
Energy-Aware Modeling and Scheduling for Dynamic Voltage Scaling with Statistical Real-Time Guarantee
Dynamic voltage scaling (DVS) is a promising technique for battery-powered systems to conserve energy consumption. Most existing DVS algorithms assume information about task periodicity or a priori knowledge about the task set to be scheduled. This paper presents an analytical model of general tasks for DVS assuming job timing information is known only after a task release. It models the voltage scaling process as a transfer function-based filtering system, which facilitates the design of two efficient scaling algorithms. The first is a time-invariant scaling policy and it is proved to be a generalization of several popular DVS algorithms for periodic, sporadic, and aperiodic tasks. A more energy efficient policy is a time-variant scaling algorithm for aperiodic tasks. It is optimal in the sense that it is online without assumed information about future task releases. The algorithm turns out to be a water-filling process with a linear time complexity. It can be applied to scheduling based on worst-case execution times as well as online slack distribution when jobs complete earlier. We further establish two relationships between computation capacity and deadline misses to provide a statistical real-time guarantee with reduced capacity
17355538
Distributed shared arrays: A distributed virtual machine with mobility support for reconfiguration
Distributed Shared Arrays (DSA) is a distributed virtual machine that supports Java-compliant multithreaded programming with mobility support for system reconfiguration in distributed environments. The DSA programming model allows programmers to explicitly control data distribution so as to take advantage of the deep memory hierarchy, while relieving them from error-prone orchestration of communication and synchronization at run-time. The DSA system is developed as an integral component of mobility support middleware for Grid computing so that DSA-based virtual machines can be reconfigured to adapt to the varying resource supplies or demand over the course of a computation. The DSA runtime system also features a directory-based cache coherence protocol in support of replication of user-defined sharing granularity and a communication proxy mechanism for reducing network contention. System reconfiguration is achieved by a DSA service migration mechanism, which moves the DSA service and residing computational agents between physical servers for load balancing and fault resilience. We demonstrate the programmability of the model in a number of parallel applications and evaluate its performance by application benchmark programs, in particular, the impact of the coherence granularity and service migration overhead.
14061717
Efficient Termination Detection for Loosely Synchronous Applications in Multicomputers
We propose a simple algorithm which is based on edge-coloring of system graphs for termination detection of loosely synchronous computations. The proposed algorithm is fully symmetric in that all processors run syntactically identical code and can detect global termination at the same time. Under the 1-port communication model, the algorithm is optimal in terms of termination delay, the difference between the time when a global termination occurs and the time it is detected, in a number of structures-chain, ring of even number of nodes, k-ary n-cube and k-ary n-mesh of low degree, where k is even; and near-optimal for other cases. The optimality analysis is based on results from a related problem, periodic gossiping in edge-colored graphs. This algorithm has been applied to some practical cases in which the overhead due to its execution is found to be insignificant.
7467010
Optimal Parameters for Load Balancing with the Diffusion Method in Mesh Networks
The diffusion method is a simple distributed load balancing method for distributed memory multiprocessors. It operates in a relaxation fashion for point-to-point networks. Its convergence to the balanced state relies on the value of a parameter—the diffusion parameter. An optimal diffusion parameter would lead to the fastest convergence of the method. Previous results on optimal parameters have existed for the k-ary n-cube and the torus. In this paper, we derive optimal diffusion parameters for mesh networks.
29283235
Request redirection and data layout for network traffic balancing in cluster-based video-on-demand s
Cluster architecture is a cost-effective approach to building up scalable servers. For I/O-intensive videoon-demand (VoD) applications, network bandwidth is usually the primary bottleneck. In this paper, we propose a request redirection strategy to balance the network traffic in cluster-based VoD servers. The redirection strategy utilizes the servers' internal backbone bandwidth to equalize their external network traffic. Performance of redirection is related with data layouts based on replication. We implemented two replication methods and two placement methods for videos with different popularities. Furthermore, we evaluated redirection strategy with different data layouts. The simulation results verify the effectiveness of the redirection strategy and proposed data layout methods.
6459835
Hash-based proximity clustering for load balancing in heterogeneous DHT networks
DHT networks based on consistent hashing functions have an inherent load uneven distribution problem. The objective of DHT load balancing is to balance the workload of the network nodes in proportion to their capacity so as to eliminate traffic bottleneck. It is challenging because of the dynamism nature of DHT networks and time-varying load characteristics. In this paper, we present a hash-based proximity clustering approach for load balancing in heterogeneity DHTs. In the approach, DHT nodes are classified as regular nodes and supernodes according to their computing and networking capacities. Regular nodes are grouped and associated with supernodes via consistent hashing of their physical proximity information on the Internet. The supernodes form a self-organized and churn resilient auxiliary network for load balancing. The hierarchical structure facilitates the design and implementation of a locality-aware randomized load balancing algorithm. The algorithm introduces a factor of randomness in the load balancing processes in a range of neighborhood so as to deal with both the proximity and dynamism. Simulation results show the superiority of the approach, in comparison with a number of other DHT load balancing algorithms. The approach performs no worse than existing proximity-aware algorithms and exhibits strong resilience to the effect of churn. It also greatly reduces the overhead of resilient randomized load balancing algorithms due to the use of proximity information.
3207638
A topology preserving deformable model using level sets
Active contour and surface models, also known as deformable models, constitute a class of powerful segmentation techniques. Geometric deformable models implemented via level-set methods have advantages over parametric ones due to their intrinsic behavior, parameterization independence, and ease of implementation. However, a long claimed advantage of geometric deformable models, the ability to automatically handle topology changes, turns out to be a liability in applications where the objects to be segmented have a known topology that must be preserved. In this paper, we present a geometric deformable model that preserves topology using the simple point concept from digital topology. This algorithm maintains the other advantages of standard geometric deformable models including sub-pixel accuracy and production of nonintersecting curves (or surfaces). Several experiments on simulated and real data are provided to demonstrate the performance of the proposed algorithm.
15546541
Reconstruction of the Central Layer of the Human Cerebral Cortex from MR Images
Reconstruction of the human cerebral cortex from MR images is a fundamental step in human brain mapping and in applications such as surgical path planning. In a previous paper, we described a method for obtaining a surface representation of the central layer of the human cerebral cortex using fuzzy segmentation and a deformable surface model. This method, however, suffers from several problems. In this paper, we significantly improve upon the previous method by using a fuzzy segmentation algorithm robust to intensity inhomogeneities, and using a deformable surface model specifically designed for capturing convoluted sulci or gyri. We demonstrate the improvement over the previous method both qualitatively and quantitatively, and show the result of its application to six subjects. We also experimentally validate the convergence of the deformable surface initialization algorithm.
49779
Nearly Completely Positive Graphs
Abstract. A non-cp graph G is called nearly vertex (edge) cp if any subgraph of G obtained by deleted a vertex (an edge) of G is completely positive. This paper presents necessary and sufficient conditions for any doubly nonnegative matrix realization A of a nearly cp graph to be completely positive.
6175091
Snakes, shapes, and gradient vector flow
Snakes, or active contours, are used extensively in computer vision and image processing applications, particularly to locate object boundaries. Problems associated with initialization and poor convergence to boundary concavities, however, have limited their utility. This paper presents a new external force for active contours, largely solving both problems. This external force, which we call gradient vector flow (GVF), is computed as a diffusion of the gradient vectors of a gray-level or binary edge map derived from the image. It differs fundamentally from traditional snake external forces in that it cannot be written as the negative gradient of a potential function, and the corresponding snake is formulated directly from a force balance condition rather than a variational formulation. Using several two-dimensional (2-D) examples and one three-dimensional (3-D) example, we show that GVF has a large capture range and is able to move snakes into boundary concavities.
3055871
A Topology Preserving Level Set Method for Geometric Deformable Models
Active contour and surface models, also known as deformable models, are powerful image segmentation techniques. Geometric deformable models implemented using level set methods have advantages over parametric models due to their intrinsic behavior, parameterization independence, and ease of implementation. However, a long claimed advantage of geometric deformable models-the ability to automatically handle topology changes-turns out to be a liability in applications where the object to be segmented has a known topology that must be preserved. We present a new class of geometric deformable models designed using a novel topology-preserving level set method, which achieves topology preservation by applying the simple point concept from digital topology. These new models maintain the other advantages of standard geometric deformable models including subpixel accuracy and production of nonintersecting curves or surfaces. Moreover, since the topology-preserving constraint is enforced efficiently through local computations, the resulting algorithm incurs only nominal computational overhead over standard geometric deformable models. Several experiments on simulated and real data are provided to demonstrate the performance of this new deformable model algorithm.