Trading Off Cache Capacity for Low-Voltage Operation

Two proposed techniques let microprocessors operate at low voltages despite high memory-cell failure rates. They identify and disable defective portions of the cache at two granularities: individual words or pairs of bits. Both techniques use the entire cache during high-voltage operation while sacrificing cache capacity during low-voltage operation to reduce the minimum voltage below 500 mV.     

A split least-squares characteristic mixed finite element method for Sobolev equations with convection term

In this paper, a split least-squares characteristic mixed finite element method for a kind of Sobolev equation with convection term is proposed, in which the characteristic method is based on the approximation of the material derivative term, that is, the time derivative term plus the convection term. The resulting least-squares procedure can be split into two independent symmetric positive definite sub-schemes and does not need to solve a coupled system of equations. Theory analysis shows that the method yields the approximate solutions with optimal accuracy in L²(Ω) norm for the primal unknown and in H(div;Ω) norm for the unknown flux, respectively. Numerical examples in one dimension, which are consistent with the theoretical results, are provided to demonstrate the characteristic behavior of this approach.     

<Emphasis Type="Italic">N</Emphasis>-person credibilistic strategic game

This paper enlarges the scope of fuzzy-payoff game to n-person form from the previous two-person form. Based on credibility theory, three credibilistic approaches are introduced to model the behaviors of players in different decision situations. Accordingly, three new definitions of Nash equilibrium are proposed for n-person credibilistic strategic game. Moreover, existence theorems are proved for further research into credibilistic equilibrium strategies. Finally, two numerical examples are given to illustrate the significance of credibilistic equilibria in practical strategic games.     

Toward effective service composition for real-time SOA-based systems

Many application domains are increasingly leveraging service-oriented architecture (SOA) techniques to facilitate rapid system deployment. Many of these applications are time-critical and, hence, real-time assurance is an essential step in the service composition process. However, there are gaps in existing service composition techniques for real-time systems. First, admission control is an essential technique to assure the time bound for service execution, but most of the service composition techniques for real-time systems do not take admission control into account. A service may be selected for a workflow during the composition phase, but then during the grounding phase, the concrete service may not be able to admit the workload. Thus, the entire composition process may have to be repeated. Second, communication time is an important factor in real-time SOA, but most of the existing works do not consider how to obtain the communication latencies between services during the composition phase. It is clear that maintaining a full table of communication latencies for all pairs of services is infeasible. Obtaining communication latencies between candidate services during the composition phase can also be costly, since many candidate services may not be used for grounding. Thus, some mechanism is needed for estimating the communication latency for composite services. In this paper, we propose a three-phase composition approach to address the above issues. In this approach, we first use a highly efficient but moderately accurate algorithm to eliminate most of the candidate compositions based on estimated communication latencies and assured service response latency. Then, a more accurate timing prediction is performed on a small number of selected compositions in the second phase based on confirmed admission and actual communication latency. In the third phase, specific concrete services are selected for grounding, and admissions are actually performed. The approach is scalable and can effectively achieve service composition for satisfying real-time requirements. Experimental studies show that the three-phase approach does improve the effectiveness and time for service composition in SOA real-time systems. In order to support the new composition approach, it is necessary to effectively specify the needed information. In this paper, we also present the specification model for timing-related information and the extension of OWL-S to support this specification model.     

Data reductions, fixed parameter tractability, and random weighted d-CNF satisfiability

Data reduction is a key technique in the study of fixed parameter algorithms. In the AI literature, pruning techniques based on simple and efficient-to-implement reduction rules also play a crucial role in the success of many industrial-strength solvers. Understanding the effectiveness and the applicability of data reduction as a technique for designing heuristics for intractable problems has been one of the main motivations in studying the phase transition of randomly-generated instances of NP-complete problems.In this paper, we take the initiative to study the power of data reductions in the context of random instances of a generic intractable parameterized problem, the weighted d-CNF satisfiability problem. We propose a non-trivial random model for the problem and study the probabilistic behavior of the random instances from the model. We design an algorithm based on data reduction and other algorithmic techniques and prove that the algorithm solves the random instances with high probability and in fixed-parameter polynomial time O(dknm) where n is the number of variables, m is the number of clauses, and k is the fixed parameter. We establish the exact threshold of the phase transition of the solution probability and show that in some region of the problem space, unsatisfiable random instances of the problem have parametric resolution proof of fixed-parameter polynomial size. Also discussed is a more general random model and the generalization of the results to the model.     

Multi-sensor calibration through iterative registration and fusion

In this paper, a new multi-sensor calibration approach, called iterative registration and fusion (IRF), is presented. The key idea of this approach is to use surfaces reconstructed from multiple point clouds to enhance the registration accuracy and robustness. It calibrates the relative position and orientation of the spatial coordinate systems among multiple sensors by iteratively registering the discrete 3D sensor data against an evolving reconstructed B-spline surface, which results from the Kalman filter-based multi-sensor data fusion. Upon each registration, the sensor data gets closer to the surface. Upon fusing the newly registered sensor data with the surface, the updated surface represents the sensor data more accurately. We prove that such an iterative registration and fusion process is guaranteed to converge. We further demonstrate in experiments that the IRF can result in more accurate and more stable calibration than many classical point cloud registration methods.     

Deadline division-based heuristic for cost optimization in workflow scheduling

Cost optimization for workflow applications described by Directed Acyclic Graph (DAG) with deadline constraints is a fundamental and intractable problem on Grids. In this paper, an effective and efficient heuristic called DET (Deadline Early Tree) is proposed. An early feasible schedule for a workflow application is defined as an Early Tree. According to the Early Tree, all tasks are grouped and the Critical Path is given. For critical activities, the optimal cost solution under the deadline constraint can be obtained by a dynamic programming strategy, and the whole deadline is segmented into time windows according to the slack time float. For non-critical activities, an iterative procedure is proposed to maximize time windows while maintaining the precedence constraints among activities. In terms of the time window allocations, a local optimization method is developed to minimize execution costs. The two local cost optimization methods can lead to a global near-optimal solution. Experimental results show that DET outperforms two other recent leveling algorithms. Moreover, the deadline division strategy adopted by DET can be applied to all feasible deadlines.     

Performance-First Control for Discrete-Time LQG Problems

Performance-first control for discrete-time LQG is considered in this paper to minimize the probability that the performance index exceeds a preselected threshold via constructing a closed-loop feedback control law. This problem can be converted into a mean-variance control problem which can be solved by developing a nested form of the variance and using polynomial optimization as a solution scheme.     

Maximum entropy membership functions for discrete fuzzy variables

Due to the deficiency of information, the membership function of a fuzzy variable cannot be obtained explicitly. It is a challenging work to find an appropriate membership function when certain partial information about a fuzzy variable is given, such as expected value or moments. This paper solves such problems for discrete fuzzy variables via maximum entropy principle and proves some maximum entropy theorems with certain constraints. A genetic algorithm is designed to solve the general maximum entropy model for discrete fuzzy variables, which is illustrated by some numerical experiments.