Gianfranco Bilardi

SODA Conference 2019 Conference Paper

The I/O complexity of Toom-Cook integer multiplication

• Gianfranco Bilardi
• Lorenzo De Stefani

Nearly matching upper and lower bounds are derived for the I/O complexity of the Toom-Cook- k (or Toom- k ) algorithm computing the products of two integers, each represented with n digits in a given base s, in a two-level storage hierarchy with M words of fast memory, with different digits stored in different memory words. An IO Ak ( n, M ) = Ω ([ n/M ) log k (2 k –1) M ) lower bound on the I/O complexity is established, by a technique that combines an analysis of the size of the dominators of suitable sub-CDAGs of the Toom-Cook- k CDAG (Computational Directed Acyclic Graph) and the analysis of a function, which we call “ Partial Grigoriev's flow ”, which captures the amount of information to be transferred between specific subsets of input and output variables, by any algorithm that solves the integer multiplication problem. The lower bound applies even if the recomputation of partial results is allowed. A careful implementation of the Toom-Cook-fc algorithm, assuming that M = Ω ( k 3 log s k ), is also developed and analyzed, leading to an I/O complexity upper bound that is within a factor O ( k 2 ) of the corresponding lower bound, hence asymptotically optimal for fixed k. Both the lower and the upper bounds are actually derived in the more general case where the value of k is allowed to vary with the level of recursion, although the quantitative expressions become more involved. Extensions of the lower bound for a parallel model with P processors are also discussed.

TCS Journal 2013 Journal Article

Optimal eviction policies for stochastic address traces

• Gianfranco Bilardi
• Francesco Versaci

The eviction problem for memory hierarchies is studied for the Hidden Markov Reference Model (HMRM) of the memory trace, showing how miss minimization can be naturally formulated in the optimal control setting. In addition to the traditional version assuming a buffer of fixed capacity, a relaxed version is also considered, in which buffer occupancy can vary and its average is constrained. Resorting to multiobjective optimization, viewing occupancy as a cost rather than as a constraint, the optimal eviction policy is obtained by composing solutions for the individual addressable items. This approach is then specialized to the Least Recently Used Stack Model (LRUSM), a type of HMRM often considered for traces, which includes V − 1 parameters, where V is the size of the virtual space. A gain optimal policy for any target average occupancy is obtained which (i) is computable in time O ( V ) from the model parameters, (ii) is optimal also for the fixed capacity case, and (iii) is characterized in terms of priorities, with the name of Least Profit Rate (LPR) policy. An O ( log C ) upper bound (being C the buffer capacity) is derived for the ratio between the expected miss rate of LPR and that of OPT, the optimal off-line policy; the upper bound is tightened to O ( 1 ), under reasonable constraints on the LRUSM parameters. Using the stack-distance framework, an algorithm is developed to compute the number of misses incurred by LPR on a given input trace, simultaneously for all buffer capacities, in time O ( log V ) per access. Finally, some results are provided for miss minimization over a finite horizon and over an infinite horizon under bias optimality, a criterion more stringent than gain optimality.

TCS Journal 2008 Journal Article

Area-time tradeoffs for universal VLSI circuits

• Sandeep N. Bhatt
• Gianfranco Bilardi
• Geppino Pucci

An area-universal VLSI circuit can be programmed to emulate every circuit of a given area, but at the cost of lower area-time performance. In particular, if a circuit with area-time bounds ( A, T ) is emulated by a universal circuit with bounds ( A u, T u ), we say that the universal circuit has blowup A u / A and slowdown T u / T. A central question in VLSI theory is to investigate the inherent costs and tradeoffs of universal circuit designs. Prior to this work, universal designs were known for area- A circuits with O ( 1 ) blowup and O ( log A ) slowdown. Universal designs for the family of area- A circuits containing O ( A 1 + ϵ log A ) vertices, with O ( A ϵ ) blowup and O ( log log A ) slowdown had also been developed. However, the existence of universal circuits with O ( 1 ) slowdown and relatively small blowup was an open question. In this paper, we settle this question by designing an area-universal circuit U A ϵ with O ( 1 / ϵ ) slowdown and O ( A ϵ ) blowup, for any value of the parameter ϵ, with 4 log log A / log A ≤ ϵ ≤ 1. By varying ϵ, we obtain universal circuits which operate at different points in the spectrum of the slowdown-blowup tradeoff. In particular, when ϵ is chosen to be a constant, our universal circuit yields O ( 1 ) slowdown.

TCS Journal 1995 Journal Article

Language learning without overgeneralization

• Shyam Kapur
• Gianfranco Bilardi

Language learnability is investigated in the Gold paradigm of inductive inference from positive data. Angluin gave a characterization of learnable families in this framework. Here, learnability of families of recursive languages is studied when the learner obeys certain natural constraints. Exactly learnable families are characterized for prudent learners with the following types of constraints: 1. (0) conservative, 2. (1) conservative and consistent, 3. (2) conservative and responsive, and 4. (3) conservative, consistent and responsive. The class of learnable families is shown to strictly increase going from (3) to (2) and from (2) to (1), while it stays the same going from (1) to (0). It is also shown that, when exactness is not required, prudence, consistency and responsiveness, even together, do not restrict the power of conservative learners.

FOCS Conference 1990 Conference Paper

Deterministic On-Line Routing on Area-Universal Networks (Extended Abstract)

• Paul Bay
• Gianfranco Bilardi

Two deterministic routing networks, the pruned butterfly and the sorting fat-tree, are presented. Both networks are area universal, i. e. they can simulate with polylogarithmic slowdown, any other routing network fitting in similar area. Previous area-universal networks were either for the offline problem, where the message set to be routed is known in advance and substantial precomputation is permitted, or involved randomization, yielding results that hold only with high probability. The present networks are the first that are simultaneously deterministic and online, and they use two substantially different routing techniques. The performance of the routing algorithms depends on the difficulty of the problem instance, which is measured by a quantity lambda, known as the load factor. The pruned butterfly algorithm runs in time O( lambda log/sup 2/N), where N is the number of possible sources and destinations for messages and lambda is assumed to be polynomial in N. The sorting fat-free algorithm runs in O( lambda log N + log/sup 2/N) time for a restricted class of message sets, including partial permutations. Other results include a new type of sorting circuit, an area universal circuit, and an area-time lower bound for routers. >

STOC Conference 1987 Conference Paper

Size-Time Complexity of Boolean Networks for Prefix Computations

• Gianfranco Bilardi
• Franco P. Preparata

STOC Conference 1984 Conference Paper

A Minimum Area VLSI Network for O(log n) Time Sorting

• Gianfranco Bilardi
• Franco P. Preparata