This thesis is a computational study of recently developed algorithms which aim to overcome degeneracy in the simplex method. We study the following algorithms: the non-negative least squares algorithm, the least-squares primal-dual algorithm, the least-squares network flow algorithm, and the combined-objective least-squares algorithm. All of the four algorithms use least-squares measures to solve their subproblems, so they do not exhibit degeneracy. But they have never been efficiently implemented and thus their performance has also not been proved. In this research we implement these algorithms in an efficient manner and improve their performance compared to their preliminary results. For the non-negative least-squares algorithm, we develop the basis update technique and data structure that fit our purpose. In addition, we also develop a measure to help find a good ordering of columns and rows so that we have a sparse and concise representation of QR-factors. The least-squares primal-dual algorithm uses the non-negative least-squares problem as its subproblem, which minimizes infeasibility while satisfying dual feasibility and complementary slackness. The least-squares network flow algorithm is the least-squares primal-dual algorithm applied to min-cost network flow instances. The least-squares network flow algorithm can efficiently solve much bigger instances than the least-squares primal-dual algorithm. The combined-objective least-squares algorithm is the primal version of the least-squares primal-dual algorithm. Each subproblem tries to minimize true objective and infeasibility simultaneously so that optimality and primal feasibility can be obtained together. It uses a big-M to minimize the infeasibility. We developed the techniques to improve the convergence rates of each algorithm: the relaxation of complementary slackness condition, special pricing strategy, and dynamic-M value. Our computational results show that the least-squares primal-dual algorithm and the combined-objective least-squares algorithm perform better than the CPLEX Primal solver, but are slower than the CPLEX Dual solver. The least-squares network flow algorithm performs as fast as the CPLEX Network solver.

The primary design goal of many embedded systems for multimedia applications is usually meeting the performance requirement at a minimum cost. In this thesis, we proposed two different ILP based approaches for hardware/software (HW/SW) partitioning and pipelined scheduling of embedded systems for multimedia applications. One ILP approach solves the HW/SW partitioning and pipelined scheduling problem simultaneously. Another ILP approach separates the HW/SW partitioning and pipelined scheduling problem into two phases. The first phase is focusing on the HW/SW partitioning and mapping problem. Second phase is used to solve the pipelined scheduling problem. The two ILP approaches not only partition and map each computation task of a particular multimedia application onto a component of the heterogeneous multiprocessor architecture, but also schedules and pipelines the execution of these computation tasks while considering communication time. For the first ILP model, the objective is to minimize the total component cost and the number of pipeline stages subject to the throughput constraint. In the second ILP approach, the objective of the first phase and second phase is to minimize the total component cost and the number of pipeline stages subject to the throughput constraint, respectively. Finally, experiments on three real multimedia applications (JPEG Encoder, MP3 Decoder, Wavelet Video Encoder) are used to demonstrate the effectiveness of the proposed approaches.

Thesis (M.S.)--Naval Postgraduate School, 2002. / Thesis advisor(s): Robert F. Dell, William J. Tarantino, Eva D. Regnier. Includes bibliographical references (p. 45-47). Also available online.

Thesis (Ph. D.)--University of Washington, 2002. / Vita. Includes bibliographical references (leaves 71-75).

As device geometries shrink, variability of process parameters becomes pronounced, resulting in a significant impact on the power and timing performance of integrated circuits. Deterministic optimization algorithms for power and area lack capabilities for handling uncertainty, and may lead to over-conservative solutions. As a result, there is an increasing need for statistical algorithms that can take into account the probabilistic nature of process parameters. Statistical optimization techniques however suffer from the limitation of high computational complexity. The objective of this work is to develop efficient algorithms for optimization of area and power under process variability while guaranteeing high yield. The first half of the dissertation focuses on two design-time techniques: (i) a gate sizing approach for area minimization under timing variability; (ii) an algorithm for total power minimization considering variability in timing and power. Design-time methods impose an overhead on each instance of the fabricated chip since they lack the ability to react to the actual conditions on the chip. In the second half of the dissertation we develop joint design-time and post-silicon co-optimization techniques which are superior to design-time only optimization methods. Specifically, we develop (i) a methodology for optimization of leakage power using design-time sizing and post silicon tuning using adaptive body bias; (ii) an optimization technique to minimize the total power of a buffer chain while considering the finite nature of adaptability afforded. The developed algorithms effectively improve the overconservatism of the corner-based deterministic algorithms and permit us to target a specified yield level accurately. As the magnitude of variability increases, it is expected that statistical algorithms will become increasingly important in future technology generations. / text

No description available.

In a standard tennis match each player has an unlimited opportunity to challenge an umpire’s call, but if three incorrect challenges are made in a set he is not allowed to challenge anymore in that set. If the set goes into a tie break the limit on incorrect challenges increases by one. These limited incorrect challenges are not carried over from one set to another. So this is kind of a limited resource available to the player and if he knows how to use this resource in a best possible way, there is a scope for increasing his overall chances of winning a match. With the motive of gaining insight on when to challenge a call, we have modeled a single game in a tennis match as a Markov decision process. We have also studied the impact of variables like player’s probability of winning a point, the player’s perception of the challengability of a call and proportion of challengable calls on the decision making process. / text

No description available.

No description available.

No description available.