Browsing by Subject "Lagrangian relaxation"
Now showing 1 - 4 of 4
Results Per Page
Sort Options
Item Clustering-Based Simultaneous Task and Voltage Scheduling for NoC Systems(2011-08-08) Yang, YuNetwork-on-Chip (NoC) is emerging as a promising communication structure, which is scalable with respect to chip complexity. Meanwhile, latest chip designs are increasingly leveraging multiple voltage-frequency domains for energy-efficiency improvement. In this work, we propose a simultaneous task and voltage scheduling algorithm for energy minimization in NoC based designs. The energy-latency tradeoff is handled by Lagrangian relaxation. The core algorithm is a clustering based approach which not only assigns voltage levels and starting time to each task (or Processing Element) but also naturally finds voltage-frequency clusters. Compared to a recent previous work, which performs task scheduling and voltage assignment sequentially, our method leads to an average of 20 percent energy reduction.Item Cost minimization in multi−commodity multi−mode generalized networks with time windows(Texas A&M University, 2007-04-25) Chen, Ping-ShunThe purpose of this research is to develop a heuristic algorithm to minimize total costs in multi-commodity, multi-mode generalized networks with time windows problems. The proposed mathematical model incorporates features of the congestion of vehicle flows and time restriction of delivering commodities. The heuristic algorithm, HA, has two phases. Phase 1 provides lower and upper bounds based on Lagrangian relaxations with subgradient methods. Phase 2 applies two methods, early due date with overdue-date costs and total transportation costs, to search for an improved upper bound. Two application networks are used to test HA for small and medium-scale problems. A different number of commodities and various lengths of planning time periods are generated. Results show that HA can provide good feasible solutions within the reasonable range of optimal solutions. If optimal solutions are unknown, the average gap between lower and upper bounds is 0.0239. Minimal and maximal gaps are 0.0007 and 0.3330. If optimal solutions are known, the maximal gap between upper bounds and optimal solutions is less than 10% ranges of optimal solutions.Item Discrete gate sizing and threshold voltage assignment to optimize power under performance constraints(2013-08) Singh, Jagmohan; Pan, David Z.In today's world, it is becoming increasingly important to be able to design high performance integrated circuits (ICs) and have them run at as low power as possible. Gate sizing and threshold voltage (Vt) assignment optimizations are one of the major contributors to such trade-offs for power and performance of ICs. In fact, the ever increasing design sizes and more aggressive timing requirements make gate sizing and Vt assignment one of the most important CAD problems in physical synthesis. A promising gate sizing optimization algorithm has to satisfy requirements like being scalable to tackle very large design sizes, being able to optimally utilize a large (but finite) number of possible gate configurations available in standard cell library based on different gate sizes and/or threshold voltages (Vt) and/or gate lengths (Lg), and also, being able to handle non-convex cell delays in modern cell libraries. The work in this thesis makes use of the research-oriented infrastructure made available as part of the ISPD (International Symposium on Physical Design) 2012 Gate Sizing Contest that addresses the issues encountered in modern gate sizing problems. We present a two-phase optimization approach where Lagrangian Relaxation is used to formulate the optimization problem. In the first phase, the Lagrangian relaxed subproblem is iteratively solved using a greedy algorithm, while in the second phase, a cell downsizing and Vt upscaling heuristic is employed to further recover power from the timing-feasible and power-optimized sizing solution obtained at the end of first phase. We also propose a multi-core implementation of the first-phase optimizations, which constitute majority of the total runtime, to take advantage of multi-core processors available today. A speedup of the order of 4 to 9 times is seen on different benchmarks as compared to serial implementation when run on a 2 socket 6-core machine. Compared to the winner of ISPD 2012 contest, we further reduce leakage power by 17.21% and runtime by 87.92%, on average, while obtaining feasible sizing solutions on all the benchmark designs.Item Dynamic and Robust Capacitated Facility Location in Time Varying Demand Environments(2010-07-14) Torres Soto, JoaquinThis dissertation studies models for locating facilities in time varying demand environments. We describe the characteristics of the time varying demand that motivate the analysis of our location models in terms of total demand and the change in value and location of the demand of each customer. The first part of the dissertation is devoted to the dynamic location model, which determines the optimal time and location for establishing capacitated facilities when demand and cost parameters are time varying. This model minimizes the total cost over a discrete and finite time horizon for establishing, operating, and closing facilities, including the transportation costs for shipping demand from facilities to customers. The model is solved using Lagrangian relaxation and Benders? decomposition. Computational results from different time varying total demand structures demonstrate, empirically, the performance of these solution methods. The second part of the dissertation studies two location models where relocation of facilities is not allowed and the objective is to determine the optimal location of capacitated facilities that will have a good performance when demand and cost parameters are time varying. The first model minimizes the total cost for opening and operating facilities and the associated transportation costs when demand and cost parameters are time varying. The model is solved using Benders? decomposition. We show that in the presence of high relocation costs of facilities (opening and closing costs), this model can be solved as a special case by the dynamic location model. The second model minimizes the maximum regret or opportunity loss between a robust configuration of facilities and the optimal configuration for each time period. We implement local search and simulated annealing metaheuristics to efficiently obtain near optimal solutions for this model.