Substantial gains are realizable through basestation cooperation during assignment of transmission powers to users. While binary power assignment is optimal for sum capacity in a two-cell system, it does not hold true in general for multi-cell systems. In this paper, we study an optimal power allocation for sum capacity in a three-cell system. The proposed branching algorithm is of linear computational complexity, and provides a power assignment which achieves a sum capacity arbitrarily close to the theoretical value. This result provides the impetus for next generation wireless systems to enable basestations to perform joint power assignment across multiple cells.

This article describes a polynomial time algorithm for min-area retiming for edge-triggered circuits to handle both setup and hold constraints. Given a circuit G and a target clock period c , our algorithm either outputs a retimed version of G satisfying setup and hold constraints or reports that such a solution is not possible, in O (∣V∣ 3 log ∣ V ∣ log (∣ V ∣ C )) steps, where ∣ V ∣ corresponds to number of gates in the circuit and C is equal to the number of registers in the circuit. This is the first polynomial-time algorithm ever reported for min-area retiming with constraints on both long and short-paths. An alternative problem formulation that takes practical issues into consideration and lowers the problem complexity is also developed. Both the problem formulations have many parallels with the original formulation of long path only retiming by Leiserson and Saxe and all the speed improvements that have been obtained on that problem statement are also demonstrated in simulation for the approach presented here. Finally, a basis is provided for deriving efficient heuristics for addressing both long-path and short-path requirements by combining the techniques of retiming and min-delay padding.

This paper presents MINFLOTRANSIT, a new transistor sizing tool for fast sizing of combinational circuits with minimal cost. MINFLOTRANSIT is an iterative relaxation-based tool that has two alternating phases. For a circuit with |V| transistors and |E| wires, the first phase (D-phase) is based on minimum cost network flow, which in our application, has a worst case complexity of O(|V/spl par/E| log(log(|V|))). The second phase (W-phase) has a worst case complexity of O(|V/spl par/E|). In practice, during our simulations both the D-phase and W-phase show a near linear run-time dependence on the size of the circuit, comparable to TILOS. Simulation results show excellent run-time behavior for MINFLOTRANSIT on all the ISCAS85 benchmark circuits. For reasonable delay targets, MINFLOTRANSIT shows up to 16.5% area savings (in relatively large circuits) over a circuit sized using a TILOS-like algorithm. In our opinion, the primary contribution of this paper is to take advantage of the structure of the transistor sizing problem and devise an iterative relaxation based gradient descent approach (D-phase) that has excellent convergence properties.

Transitions on high capacitance busses in VLSI systems result in considerable power dissipation. Various coding schemes have been proposed in literature to encode the input signal in order to reduce the number of transitions. Reducing number of transitions comes in exchange for redundancy in data transferred over the busses. For a given amount of redundancy there exists a lower bound on the average number of transitions. In recent times noise and reliability problems have brought the peak/instantaneous power consumed in VLSI systems in to prominence. There has been limited study done on reducing the number of instantaneous transitions and hence the peak power consumed in busses. In this paper we model a bus with a limit on the maximum instantaneous transition activity as a constrained channel and derive an upper bound on the data-rate obtainable using the capacity of the underlying channel. We then demonstrate that some existing bus encoding schemes are near-optimal with respect to the derived bounds thus, perhaps, obviating the need to search for newer more complicated coding schemes. Also considered is a bus with a constraint on number of transitions in a fixed number of (k) bus transmissions. The capacity of such a bus is derived in the same manner as a bus with a constraint on maximum instantaneous transition activity. 1.

This paper presents MINFLOTRANSIT, a new transistor sizing tool for fast sizing of combinational circuits with minimal cost. MINFLOTRANSIT is an iterative relaxation based tool that has two alternating phases. For a circuit with |V| transistors and |E| wires, the first phase (D-phase)) is based on minimum cost network flow, which in our application, has a worst-case complexity of O(|V||E|log(log(|V|))). The second phase W-phase has a worst case complexity of O(|V||E|). In practice, during our simulations both the D-phase and W-phase show a near linear run-time dependence on the size of the circuit, comparable to TILOS. Simulation results show excellent run-time behavior for MINFLOTRANSIT on all the ISCAS85 benchmark circuits. For reasonable delay targets MINFLOTRANSIT shows up to 16.5% area savings over a circuit sized using a TILOS-like algorithm.

Transitions on high capacitance busses in VLSI systems result in considerable power dissipation. Various coding schemes have been proposed in literature to encode the input signal in order to reduce the number of transitions. Number of transitions can be reduced by introducing redundancy in data transferred over the busses. For a given amount of redundancy there exists a lower bound on the average number of transitions. In this paper we derive a new coding scheme which leads to extremely practical techniques for bus transmission that reduce bus transitions to within 3.96-8.42% of the lower bound depending on the redundancy employed. There is also a net reduction in power dissipation ranging from 8.53-21.88% over an uncoded bus transmission scheme. This savings in power dissipation is identical to that for bus-invert coding per word transmitted the higher efficiency brought about by codeword slimming, however, results in shorter codewords than bus-invert coding which in turn results in higher energy efficiency in word transmission. Applications suitable for this new technique include systems relying on bit-serial implementation and systems with bit-parallel implementations where the cost of extra parallel-to-serial and serial-to-parallel data-format converters is marginal compared to the power savings obtained.

This paper presents a novel programmable digital signal processor (PDSP) component called the multiply multiple accumulator (MMAC). The MMAC differs from a standard multiply accumulator (MAC) in that it has k addressable accumulators rather than 1 in the case of the MAC. It is demonstrated that this feature of the MMAC can provide for low power scheduling of FIR filter operations. Typically, the number of read accesses to associated memories can come down, asymptotically, by a factor of k. The switching activity of associated multipliers also comes down by a factor of k.

Dynamic power consumed in CMOS gates goes down quadratically with the supply voltage.By maintaining a high supply voltage for gates on the critical path and by using a low supply voltage for gates off the critical path it is possible to dramatically reduce power consumption in CMOS VLSI circuits without performance degradation.Interfacing gates operating under multiple supply voltages, however, requires the use of level converters, which makes the problem modeling difficult.In this paper we develop a formal model and develop an efficient heuristic for addressing the use of two supply voltages for low power CMOS VLSI circuits without performance degradation.Power consumption savings up to 25% over and above the best known existing heuristics are demonstrated for combinational circuits in the ISCAS85 benchmark suite.

This paper describes a polynomial time algorithm for min-area retiming for edge-triggered circuits to handle both setup and hold constraints. Given a circuit G and a target clock period c, our algorithm either outputs a retimed version of G satisfying setup and hold constraints or reports that such a solution is not possible, in O(|V/sup 3/|log|V|log(|V|C)) steps, where |V| corresponds to number of gates in the circuit and C is equal to the number of registers in the circuit. This is the first polynomial time algorithm ever reported for min-area retiming with constraints on both long and short-paths. An alternative problem formulation that takes practical issues in to consideration and lowers the problem complexity is also developed. Both the problem formulations have many parallels with the original formulation of long-path only retiming by Leiserson and Saxe and all the speed improvements that have been obtained on that technique are likely to be valid for improving the performance of the technique described in this paper.

The use of dual threshold voltages can significantly reduce the static power dissipated in CMOS VLSI circuits.With the supply voltage at 1V and threshold voltage as low as 0.2V the subthreshold leakage power of transistors starts dominating the dynamic power.Also, many times a large number of devices spend a long time in a standby mode where the leakage power is the only source of power consumption.We present a near-optimal approach to synthesize low static power CMOS VLSI circuits with two threshold voltages that reduces power consumption compared with a previous approach by upto 29.45%.Also, presented is a technique which finds static power optimal configurations for CMOS VLSI circuits when arbitrary number of threshold voltages are allowed.

Motivated by the need for designing efficient architectures for two-dimensional discrete wavelet transforms (DWTs), this paper presents a novel multi-dimensional (MD) folding transformation technique which can be used to synthesize control circuits for pipelined architectures for a specific class of multirate MD digital signal processing (DSP) algorithms. Although a multirate MD DSP algorithm contains decimeters and expanders which change the effective sample rate of a MD discrete time signal, MD folding time-multiplexes the algorithm to hardware in such a manner that the resulting synchronous architecture requires only a single clock signal for the clocking of the datapath. Feasibility constraints are derived for folding a 2-D data-flow graph (DFG) onto a given set of hardware functional units according to a specified schedule. Area/power efficient architectures are derived for 1-4 level 2-D discrete wavelet transforms (DWT) with 18.5-23.3% savings in storage area.

A wavelet domain robust denoising algorithm is presented, which efficiently removes both Gaussian as well as Gaussian mixed with impulse noise. Several wavelet domain operators are developed which help in the denoising process. The superiority of the new algorithm is firmly established by simulation over a variety of images.