In this paper, a wide-input-range buck converter with a dual time-based PWM and PFM control is presented. The time-based PWM control features novel line feedforward and adaptive gain techniques to speed up line transient response and keep the loop gain crossover frequency almost constant over the input voltage range. The same line-feedforward circuitry is also exploited to perform seamless transitions from PFM to PWM mode and boost efficiency at medium and light loads. A 1.4-A prototype converter with 5-to-32-V input and 3.3-V output voltage, fabricated in a 180-nm BCD process, shows a 3x reduction in the line transient response and a control loop bandwidth with limited dependence on the input voltage. PFM-to-PWM transitions are achieved with no output voltage variation thanks to the phase-shift preset. The PFM quiescent current including bias network, controller and drivers in no-load operation is 14$\mu$A. The die area is 3.74 mm2, while the controller occupies 0.31 mm2.

Time-based techniques are proven to reduce the area of the compensation networks of DC-DC converters when compared to their voltage mode counterparts. To maximize the converter efficiency both at heavy and light load, the converter controller also needs to seamlessly switch from a PWM to a PFM control. While buck converters are inherently stable during start-up, boost converters might enter a latched-up state and thus require a dedicated start-up controller, which often makes use of bulky components increasing the overall area. To overcome this issue, we present a start-up mechanism for time-based boost converters. The proposed solution makes use of the time-based feedback loop and seamless PFM/PWM transition circuit to implement the start-up functionality without requiring any extra circuitry or off-chip components.

Controlling the differential expression of many thousands different genes at any given time is a fundamental task of metazoan organisms and this complex orchestration is controlled by the so-called regulatory genome encoding complex regulatory networks: several Transcription Factors bind to precise DNA regions, so to perform in a cooperative manner a specific regulation task for nearby genes. The in silico prediction of these binding sites is still an open problem, notwithstanding continuous progress and activity in the last two decades. In this paper, we describe a new efficient combinatorial approach to the problem of detecting sets of cooperating binding sites in promoter sequences, given in input a database of Transcription Factor Binding Sites encoded as Position Weight Matrices. We present CMStalker, a software tool for composite motif discovery which embodies a new approach that combines a constraint satisfaction formulation with a parameter relaxation technique to explore efficiently the space of possible solutions. Extensive experiments with 12 data sets and 11 state-of-the-art tools are reported, showing an average value of the correlation coefficient of 0.54 (against a value 0.41 of the closest competitor). This improvements in output quality due to CMStalker is statistically significant.

Providing strong QoS guarantees for wireless multi-hop networks is very challenging, due to many factors such as use of a shared communication medium, variability in wireless link quality, and so on. However, wireless mesh technology gives the opportunity to alleviate some of these problems, due to lack of mobility in the wireless infrastructure, and presence of natural centralization points in the network. The main contribution of this paper is the definition of a simple framework that exploits these features to provide provable, strong QoS guarantees to network clients. In particular, admitted clients are guaranteed a certain minimum bandwidth and maximum delay on their connections. The framework is based on STDMA scheduling at the MAC layer, which is periodically executed at the network manager to adapt to changes in traffic demand. While scheduling computation is centralized, admission control is performed locally at the wireless backbone nodes, thus reducing signaling. We propose two bandwidth distribution and related admission control policies, which are at opposite ends of the network utilization/spatial fairness trade-off. Through extensive simulations, we show that the proposed framework achieves its design goals of providing strong QoS guarantees to VoIP clients while not sacrificing throughput in a realistic mesh network scenario, also in presence of highly unbalanced load at the backbone nodes. To the best of our knowledge, this is the first proposal with similar features for wireless mesh networks.

We study a version of the beta-assignment problem (Chang and Lee, 1988) on asynchronous rings: consider a set of items and a set of m colors, where each item is associated to one color. Consider also n computational agents connected by an asynchronous ring. Each agent holds a subset of the items, where initially different agents might hold items associated to the same color. We analyze the problem of distributively assigning colors to agents in such a way that (a) each color is assigned to one agent and (b) the number of different colors assigned to each agent is minimum. Since any color assignment requires that the items be distributed according to it (e.g. all items of the same color are to be held by only one agent), we define the cost of a color assignment as the amount of items that need to be moved, given an initial allocation. We first show that any distributed algorithm for this problem on the ring requires a communication complexity of Omega(n middot m) and then we exhibit a polynomial time distributed algorithm with message complexity matching the bound, that determines a color assignment with cost at most (2 + epsi) times the optimal cost, for any 0 < epsi < 1

Topology control, wherein nodes adjust their transmission ranges to conserve energy and reduce interference, is an important feature in wireless ad hoc networks. Contrary to most of the literature on topology control which focuses on reducing energy consumption, in this paper we tackle the topology control problem with the goal of limiting interference as much as possible, while keeping the communication graph connected with high probability. Our approach is based on the principle of maintaining the number of physical neighbors of every node equal to or slightly below a specific value k. As we will discuss in this paper, having a nontrivially bounded physical node degree allows a network topology with bounded interference to be generated. The proposed approach enforces symmetry on the resulting communication graph, thereby easing the operation of higher layer protocols. To evaluate the performance of our approach, we estimate the value of k that guarantees connectivity of the communication graph with high probability both theoretically and through simulation. We then define k-Neigh, a fully distributed, asynchronous, and localized protocol that uses distance estimation. k-Neigh guarantees logarithmically bounded physical degree at every node, is the most efficient known protocol (requiring 2n messages in total, where n is the number of nodes in the network), and relies on simpler assumptions than existing protocols. Furthermore, we verify through simulation that the network topologies produced by k-Neigh show good performance in terms of node energy consumption and expected interference.

In this paper we study the following problem: we are given a certain region R to monitor and a requirement on the degree of coverage (DoC) of R to meet by a network of deployed sensors. The latter will be dropped by a moving vehicle, which can release sensors at arbitrary points within R. The node spatial distribution when sensors are dropped at a certain points is modeled by a certain probability density function F. The network designer is allowed to choose an arbitrary set of drop points, and to release an arbitrary number of sensors at each point. Given this setting, we consider the problem of determining the optimal deployment strategy, i.e., the drop strategy such that the DoC requirement is fulfilled and the total number of deployed nodes n is minimum. We study this problem both analytically and through simulation, under the assumption that F is the two-dimensional Normal distribution of parameter s (sigma) centered at the drop point. We show that, for given value of s (sigma) and DoC requirement, optimal deployment strategies can be easly identified. The sensor dropping problem studied in this paper is relvant whenever manual node deployment is impossible or overly expensive, and partially controlled deployment (the network designer can choose the drop points, but the final node deployment is random) is the only feasible choice.

Topology Control (TC) is a well-studied technique used in wireless ad hoc networks to find energy-efficient and/or low-interference subgraphs of the maxpower communication graph. However, existing work has the following limitations: (1) the energy model adopted is quite unrealistic - only transmit power is often considered and homogeneous decay of the radio signal with distance is assumed; (2) the interference measure does not account for multi-hop communications. In this paper, we show the dramatic effect of the underlying energy and interference model on TC. In particular, we demonstrate that by using more realistic energy models and considering the effects of multi-hop interference, radically different conclusions about TC can be drawn; namely that (1) energy efficient TC is essentially meaningless, since every link turns out to be "efficient", and that (2) topologies identified as "interference-optimal" in the current literature can be extremely bad from the viewpoint of multi-hop interference. Given these observations, we propose a new measure of link interference, extend it to deal with multi-hop interference, and design a corresponding optimal communication subgraph, called ATASP. We prove that, in the worst case, ATASP coincides with the maxpower communication graph, showing that in some unfortunate situations also performing multi-hop interference-based TC is pointless. However, the simulation results with random node deployments presented in this paper show that, on the average, ATASP is a sparse subgraph of the maxpower communication graph, and multi-hop interference-based TC is indeed possible. Since computing ATASP requires global knowledge, we experiment through simulation with known localized algorithms for energy-efficient TC and show that they perform well (on the average) with respect to multi-hop interference.

We propose an approach to topology control based on the principle of maintaining the number of neighbors of every node equal to or slightly below a specific value k. The approach enforces symmetry on the resulting communication graph, thereby easing the operation of higher layer protocols. To evaluate the performance of our approach, we estimate the value of k that guarantees connectivity of the communication graph with high probability. We then define k-Neigh, a fully distributed, asynchronous, and localized protocol that follows the above approach and uses distance estimation. We prove that k-Neigh terminates at every node after a total of 2n messages have been exchanged (with n nodes in the network) and within strictly bounded time. Finally, we present simulations results which show that our approach is about 20% more energy-efficient than a widely-studied existing protocol.

We prove a number of negative results about practical (i.e., work efficient and numerically accurate) algorithms for computing the main matrix factorizations. In particular, we prove that the popular Householder and Givens methods for computing the QR decomposition are P-complete, and hence presumably inherently sequential, under both real and floating point number models. We also prove that Gaussian elimination (GE) with a weak form of pivoting, which aims only at making the resulting algorithm nondegenerate, is likely to be inherently sequential as well. Finally, we prove that GE with partial pivoting is P-complete over GF(2) or when restricted to symmetric positive definite matrices, for which it is known that even standard GE (no pivoting) does not fail. Altogether, the results of this paper give further formal support to the widespread belief that there is a tradeoff between parallelism and accuracy in numerical algorithms.

ll;eprove allulllberof negaLive resultsahout practicaf (i.e., numerically accurate) algorithms for certain matrix factorization.In particular.we prow that the popular (;iwns' method for computing the QR decomposition is inherentl} sequential over the realistic model of floating point arithmetic.We also prove a number of additional results concerning Gaussian Elimination for computing the LIT decon]positiou..iltogether, the results of this paper sllpport the widespread belief that there is a tradeotlbetween palallclism and accuracy in numerical algorithms. 1 Introduction Matrix factorization algorithms form the hackhone of stateof-the-ar[ numerical libraries and packages, such as L.\-PACK and hfATL.%f3[9.1~].indeed, factoring ii matrix is almost always the first.step of mall: scient,ifir collll~ut.ations,ancl usually the one which places the heaviest demand in terms of computing resolwces.Among the rompl]t.ationsthat involve matrix factoriza( ions of sonle sort ~ve I.ccall linear system solution, eigenva]ue and least scll]ares alJproximirtion, and rank revealing 11.ansforlllikti{jlls. in Iicfv of this, some authors have invest j~.+t.e[]the parallel conlldcxity of the most popular matrix f&torizat.ion>.]M]IIVI) tlw (} ')L[" and QR(II) clecompositions (see .Appell~lix .1 for {ldinit,ions and simple properties)..4list of positive known resIIlt.sfol- Io\vs.q LL" clecolnposit,ion is in arithmetic ,1"('.}vlw]lef.erit exists, i.e., pro}"ided that tlw leaditl~Iwil]ripal minors "This Ivork haS lb y Esprit P!',)J@ WIT? (;l~Pl'-(""Oht,and by illurst 4077 and G1l'Zf{[ncls tn,,>art,l,,e,, ra<-ll [Ilsortllatlccl.IJl],,!rrs]t{i di Ptsn, ('~,rsu ltal[a 10, JGI05 pl~a, Italy, ~l)d I?,lc.cNFL \;ia S Nlaria .tli,.ZG12G }>lsO, ]ttl)y 13ma11lemlcin]&l UIIII>I II 'D,pamm,c.nrod, SCIK113: c lcC1lOb~l?,%\,a!1Z;3 ??, (l!>),,,.I'sI(;3 <{1 'IcmnO.\"Ia(.'avoIIr&,1511) 11.iiessailclr]a, [i+' an,{ lNt('-('Nrt \'la s Llal'la.l(i,5612(; Plsa, Italy 1~,111 all IIlal)z llllfl'lllllnl 1! , 'D1part.imento ,:11 Sclrllz.(lell'I 11ror111a7,1c,11,.(Jilivsl.11:1,11 Bologna, Alum A1ltKI 'Zallll)Olll i. .11)1?7 ttolcJ~lla It;ily 1<111311 )Ijargara

Consider the problem of determining the pivot sequence used by the Gaussian Elimination algorithm with Partial Pivoting (GEPP). Let N stand for the order of the input matrix and let e be any positive constant. Assuming P ≠ NC, we prove that if GEPP were decidable in parallel time M1/2–e then all the problems in P would be characterized by polynomial speedup. This strengthens the P-completeness result that holds of GEPP. We conjecture that our result is valid even with the exponent 1 replaced for 1/2, and provide supporting arguments based on our result. This latter improvement would demonstrate the optimality of the naive parallel algorithm for GEPP (modulo P ≠ NC).

The authors discuss the development and implementation of an object-oriented experimental environment for global routing heuristics in VLSI layout design. This experimental environment has been implemented in both common lisp (with object-oriented extensions) and Smalltalk, providing a user-friendly graphical interface for problem input, output, interaction and modification of the heuristics. Several heuristics have been implemented, some of which use only local information, while others use global information concerning the instance of the problem. All heuristics seem to have good average case performance, and from the results it is concluded that, also on average, multi-turn routings do not provide a significant improvement over one-turn routings.>