State-feedback optimal control and cost evaluation problems for constrained difference inclusions are considered. Sufficient conditions, in the form of Lyapunov-like inequalities, are provided to derive an upper bound on the cost associated with the solution to a constrained difference inclusion with respect to a given cost functional. Under additional sufficient conditions, we determine the cost exactly without computing solutions. The proposed approach is extended to study an optimal control problem for discrete-time systems with constraints. In this setting, sufficient conditions for closed-loop optimality are given in terms of a constrained steady-state-like Hamilton-Jacobi-Bellman equation. Applications and examples of the proposed results are presented.

Cost evaluation problems for hybrid inclusions are studied. Sufficient conditions, in the form of Lyapunov-like inequalities, are provided to derive an upper bound on the cost associated with the solution to a hybrid inclusion with respect to a hybrid cost functional. Under additional sufficient conditions, we determine the cost exactly without computing solutions. Constructive results are proposed to solve cost evaluation problems in some relevant applications. Numerical examples are presented.

This paper deals with robust minimum-time control of a class of asymptotically null-controllable with bounded input planar systems. A hybrid controller is proposed to robustly achieve global finite time stability of a set of points wherein the plant state is zero. The resulting controller provides time optimal response from initial conditions in a certain subset of the state space, and finite time convergence elsewhere. Finally, the effectiveness of the proposed methods is demonstrated in a numerical example.

We formulate an optimal control problem for hybrid systems with inputs and propose conditions for the design of state-feedback laws solving the optimal control problem. The optimal control problem has the flavor of an infinite horizon problem, but it also allows solutions to have a bounded domain of definition, which is possible in hybrid systems with deadlocks. Design conditions for optimal feedback laws are obtained by relating a quite general hybrid cost functional to a Lyapunov like function. These conditions guarantee closed-loop optimality and are given by constrained steady-state-like Hamilton-Jacobi-Bellman-type equations. Applications and examples of the proposed results are presented.

Gauss-Seidel is an iterative computation used for solving sets of simulataneous linear equations, $Au=f$. When these unknowns are associated with nodes in an irregular mesh, then the Gauss-Seidel computation structure is related to the mesh structure. We use this structure to subdivide the computation at runtime using a technique called {\em sparse tiling}. The rescheduled computation exhibits better data locality and therefore improved performance. This paper gives a complete proof that a serial schedule based on sparse tiling generates results equivalent to those that a standard Gauss-Seidel computation produces.

Pre-2018 CSE ID: CS2001-0690

Predicated Execution can be used to alleviate the costs associated with frequently mispredicted branches. This is accomplished by trading the cost of a mispredicted branch for execution of both paths following the conditional branch. In this paper we concentrate on using predicated execution to aggressively reduce a program's branch misprediction rate. We examine an aggressive region formation algorithm focused on removing hard-to-predict branches. This region formation algorithm allows the inclusion of unbiased, but predictable, branches within a region. This was essential in order to predicate the hard-to-predict branches for the programs we examined. The branches left in the predicated region will now need to be predicted during fetch with greater frequency. Using a traditional branch prediction architecture, these region-based branches can end up having a similar miss rate to the hard-to-predict branches that were removed. We propose the Predicate Update Branch Predictor architecture to aid the prediction of these region-based branches. Region-based branches are heavily correlated with the outcome of the predicate with which they are guarded. A branch predicated on false should always predict that the branch should not be taken. Our predicate update predictor updates the global history with the result of the predicate defining instruction. This allows the region branches guarded by those predicates to benefit from this correlation history when making their prediction. For codes predicated with our hard-to-predict region formation algorithm, our results show that a Predicate Update Branch Predictor reduces the mispredict rate from an average of 7% to 5% for the benchmarks we studied.

Pre-2018 CSE ID: CS2001-0677

This paper investigates the problem of allocating a large number of independent, equal sized tasks on a distributed grid-like platform. We develop an efficient, autonomous, scalable, dynamic and generally applicable protocol for this purpose. The A-FAST protocol embodies the idea of pressure guiding the flow in fluid networks. It uses the number of unprocessed tasks buffered at each node in place of "pressure" to decide whether to move tasks to neighboring nodes. Simulations show that the A-FAST protocol performs well over a wide set of random networks, averaging more than 99% of the optimal performance. Such a protocol has the potential to aid the efficient deployment of large, data intensive applications on heterogeneous peer-to-peer computing platforms.

Pre-2018 CSE ID: CS2003-0744

Regional stability analysis of linear systems with multi-rate samplers and actuator saturation is studied. A hybrid controller is used to perform a fusion of measurements sampled at different times. In between sampling events, the controller behaves as a copy of the plant. When a new measurement is available, the controller state undergoes a jump. The resulting system is analyzed in a hybrid system framework. Sufficient conditions in the form of matrix inequalities are given to determine estimates of the basin of attraction of the closed-loop system. Finally, the effectiveness of the proposed methodology is shown in an example.

Many computationally-intensive programs, such as those for differential equations, spatial interpolation, and dynamic programming, spend a large portion of their execution time in multiply-nested loops which have a regular stencil of data dependences. Tiling is a well-known optimization that improves performance on such loops, particularly for computers with a multi-levelled hierarchy of parallelism and memory. Most previous work on tiling restricts the tile shape to be rectangular. Our previous work and its extension by Desprez, Dongarra, Rastello and Robert Showed that for doubly nested loops, using parallelograms can improve parallel execution time by decreasing the idle time, the time that a processor spends waiting for data or synchronization. In this technical report, we extend that work to more deeply nested loops, as well as to more complex loop bounds. We introduce a model which allows us to demonstrate the equivalence in complexity of linear programming and determining the execution time of a tiling in the model. We then identify a sub-class of these loops that constitute rectilinear iteration spaces for which we derive a closed form formula for their execution time. This formula can be used by a compiler to predict the execution tome of a loop nest. We then derive the tile shape that minimizes this formula. Using the duality property of linear programming, we also study how the longest path of dependent tiles within a rectilinear iteration space depends on the slope of only four of the facets defining the iteration space, independent of its dimensionality.

Pre-2018 CSE ID: CSE1999-0616