The Experts below are selected from a list of 321 Experts worldwide ranked by ideXlab platform
Isabelle Puaut - One of the best experts on this subject based on the ideXlab platform.
-
Scalable Fixed-Point Free Instruction Cache Analysis
2011Co-Authors: Damien Hardy, Benjamin Lesage, Isabelle PuautAbstract:Estimating worst-case execution times (WCETs) for architectures with caches requires the worst-case number of cache misses to be upper bounded. Most existing static cache analysis methods use Fixed-Point Computation and do not scale well with large code sizes. To address this scalability issue, we propose in this paper a new fast and scalable instruction cache analysis technique. In contrast to existing work, neither fixed- point Computation nor heavyweight interprocedural analysis are required. Thus, code sizes too long to analyze with existing techniques are then analyzable with lower analysis time and memory consumption, and with only a slight degradation of the analysis precision. Experimental results show a reduction of the analysis execution time of a factor 5 in average (with a peak near 30 for the largest and most complex code) with only a degradation of the analysis precision of 0.5% in average. The proposed technique is intended to be used in situations where the need for fast analysis outweighs the need for very tight results: early software development phases, timing analysis of large pieces of software, or iterative WCET-oriented compiler optimizations.
-
RTSS - Scalable Fixed-Point Free Instruction Cache Analysis
2011 IEEE 32nd Real-Time Systems Symposium, 2011Co-Authors: Damien Hardy, Benjamin Lesage, Isabelle PuautAbstract:Estimating worst-case execution times (WCETs) for architectures with caches requires the worst-case number of cache misses to be upper bounded. Most existing static cache analysis methods use Fixed-Point Computation and do not scale well with large code sizes. To address this scalability issue, we propose in this paper a new fast and scalable instruction cache analysis technique. In contrast to existing work, neither fixed point Computation nor heavyweight interprocedural analysis are required. Thus, code sizes too long to analyze with existing techniques are then analyzable with lower analysis time and memory consumption, and with only a slight degradation of the analysis precision. Experimental results show a reduction of the analysis execution time of a factor 5 in average (with a peak near 30 for the largest and most complex code) with only a degradation of the analysis precision of 0.5% in average. The proposed technique is intended to be used in situations where the need for fast analysis outweighs the need for very tight results: early software development phases, timing analysis of large pieces of software, or iterative WCET-oriented compiler optimizations.
Shang-hua Teng - One of the best experts on this subject based on the ideXlab platform.
-
Quantum Separation of Local Search and Fixed Point Computation
Algorithmica, 2009Co-Authors: Xi Chen, Shang-hua TengAbstract:We give a lower bound of Ω(n (d−1)/2) on the quantum query complexity for finding a fixed point of a discrete Brouwer function over grid [n] d . Our lower bound is nearly tight, as Grover Search can be used to find a fixed point with O(n d/2) quantum queries. Our result establishes a nearly tight bound for the Computation of d-dimensional approximate Brouwer fixed points defined by Scarf and by Hirsch, Papadimitriou, and Vavasis. It can be extended to the quantum model for Sperner’s Lemma in any dimensions: The quantum query complexity of finding a panchromatic cell in a Sperner coloring of a triangulation of a d-dimensional simplex with n d cells is Ω(n (d−1)/2). For d=2, this result improves the bound of Ω(n 1/4) of Friedl, Ivanyos, Santha, and Verhoeven. More significantly, our result provides a quantum separation of local search and fixed point Computation over [n]d , for d≥4. Aaronson’s local search algorithm for grid [n]d , using Aldous Sampling and Grover Search, makes O(n d/3) quantum queries. Thus, the quantum query model over [n]d for d≥4 strictly separates these two fundamental search problems.
-
COCOON - Quantum Separation of Local Search and Fixed Point Computation
Lecture Notes in Computer Science, 2008Co-Authors: Xi Chen, Shang-hua TengAbstract:We give a lower bound of i¾?(n(di¾? 1)/2) on the quantum query complexity for finding a fixed point of a discrete Brouwer function over grid [n]d. Our lower bound is nearly tight, as Grover Search can be used to find a fixed point with O(nd/2) quantum queries. Our result establishes a nearly tight bound for the Computation of d-dimensional approximate Brouwer fixed points defined by Scarf and by Hirsch, Papadimitriou, and Vavasis. It can be extended to the quantum model for Sperner's Lemma in any dimensions: The quantum query complexity of finding a panchromatic cell in a Sperner coloring of a triangulation of a d-dimensional simplex with ndcells is i¾?(n(di¾? 1)/2). For d= 2, this result improves the bound of i¾?(n1/4) of Friedl, Ivanyos, Santha, and Verhoeven. More significantly, our result provides a quantum separation of local search and fixed point Computation over [n]d, for di¾? 4. Aaronson's local search algorithm for grid [n]d, using Aldous Sampling and Grover Search, makes O(nd/3) quantum queries. Thus, the quantum query model over [n]dfor di¾? 4 strictly separates these two fundamental search problems.
-
FOCS - Paths Beyond Local Search: A Tight Bound for Randomized Fixed-Point Computation
48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), 2007Co-Authors: Xi Ghen, Shang-hua TengAbstract:In 1983, Akhus proved that randomization can speedup local search. For example, it reduces the query complexity of local search over grid [1 : n]d from ominus(nd-1) to 0(d1/2nd/2). It remains open whether randomisation helps Fixed-Point Computation. Inspired by the recent advances on the complexity of equilibrium Computation, we solve this open problem by giving an asymptotically tight bound of (Omega(n))d-1 on the randomized query complexity for computing a fixed point of a discrete Brouwer function over grid [1 : n]d. Our result can be extended to the black-box query model for Sperner's I&mma in any dimension. It also yields a tight bound for the Computation of d-dimensional approximate Brouwer fixed points as defined by Scarf and by Hirsch, Papadimitriou, and Vavasis. Since the randomized query complexity of global optimization over [1 : n]d is ominus(nd), the randomized query model over [ 1 : n]d strictly separates these three important search problems: Global optimization is harder than Fixed-Point Computation, and Fixed-Point Computation is harder than local search. Our result indeed demonstrates that randomization does not help much in Fixed-Point Computation in the black-box query model. Our randomized lower bound matches the deterministic complexity of this problem, which is ominus(nd-1).
-
Settling the Complexity of Computing Two-Player Nash Equilibria
arXiv: Computer Science and Game Theory, 2007Co-Authors: Xi Chen, Xiaotie Deng, Shang-hua TengAbstract:We settle a long-standing open question in algorithmic game theory. We prove that Bimatrix, the problem of finding a Nash equilibrium in a two-player game, is complete for the complexity class PPAD Polynomial Parity Argument, Directed version) introduced by Papadimitriou in 1991. This is the first of a series of results concerning the complexity of Nash equilibria. In particular, we prove the following theorems: Bimatrix does not have a fully polynomial-time approximation scheme unless every problem in PPAD is solvable in polynomial time. The smoothed complexity of the classic Lemke-Howson algorithm and, in fact, of any algorithm for Bimatrix is not polynomial unless every problem in PPAD is solvable in randomized polynomial time. Our results demonstrate that, even in the simplest form of non-cooperative games, equilibrium Computation and approximation are polynomial-time equivalent to fixed point Computation. Our results also have two broad complexity implications in mathematical economics and operations research: Arrow-Debreu market equilibria are PPAD-hard to compute. The P-Matrix Linear Complementary Problem is Computationally harder than convex programming unless every problem in PPAD is solvable in polynomial time.
-
Paths Beyond Local Search: A Nearly Tight Bound for Randomized Fixed-Point Computation
arXiv: Computer Science and Game Theory, 2007Co-Authors: Xi Chen, Shang-hua TengAbstract:In 1983, Aldous proved that randomization can speedup local search. For example, it reduces the query complexity of local search over [1:n]^d from Theta (n^{d-1}) to O (d^{1/2}n^{d/2}). It remains open whether randomization helps Fixed-Point Computation. Inspired by this open problem and recent advances on equilibrium Computation, we have been fascinated by the following question: Is a Fixed-Point or an equilibrium fundamentally harder to find than a local optimum? In this paper, we give a nearly-tight bound of Omega(n)^{d-1} on the randomized query complexity for computing a fixed point of a discrete Brouwer function over [1:n]^d. Since the randomized query complexity of global optimization over [1:n]^d is Theta (n^{d}), the randomized query model over [1:n]^d strictly separates these three important search problems: Global optimization is harder than Fixed-Point Computation, and Fixed-Point Computation is harder than local search. Our result indeed demonstrates that randomization does not help much in Fixed-Point Computation in the query model; the deterministic complexity of this problem is Theta (n^{d-1}).
Bernhard Bauer - One of the best experts on this subject based on the ideXlab platform.
-
data flow based model analysis and its applications
Model Driven Engineering Languages and Systems, 2013Co-Authors: Christian Saad, Bernhard BauerAbstract:In this paper we present a data-flow based approach to static model analysis to address the problem of current methods being either limited in their expressiveness or employing formalisms which complicate seamless integration with standards and tools in the modeling domain. By applying data-flow analysis - a technique widely used for static program analysis - to models, we realize what can be considered a generic "programming language" for context-sensitive model analysis through declarative specifications. This is achieved by enriching meta models with data-flow attributes which are afterward instantiated for models. The resulting equation system is subjected to a Fixed-Point Computation that yields a static approximation of the model's dynamic behavior as specified by the analysis. The applicability of the approach is evaluated in the context of a running example, the examination of viable application domains and a statistical review of the algorithm's performance.
-
MoDELS - Data-Flow Based Model Analysis and Its Applications
Lecture Notes in Computer Science, 2013Co-Authors: Christian Saad, Bernhard BauerAbstract:In this paper we present a data-flow based approach to static model analysis to address the problem of current methods being either limited in their expressiveness or employing formalisms which complicate seamless integration with standards and tools in the modeling domain. By applying data-flow analysis - a technique widely used for static program analysis - to models, we realize what can be considered a generic "programming language" for context-sensitive model analysis through declarative specifications. This is achieved by enriching meta models with data-flow attributes which are afterward instantiated for models. The resulting equation system is subjected to a Fixed-Point Computation that yields a static approximation of the model's dynamic behavior as specified by the analysis. The applicability of the approach is evaluated in the context of a running example, the examination of viable application domains and a statistical review of the algorithm's performance.
Damien Hardy - One of the best experts on this subject based on the ideXlab platform.
-
Scalable Fixed-Point Free Instruction Cache Analysis
2011Co-Authors: Damien Hardy, Benjamin Lesage, Isabelle PuautAbstract:Estimating worst-case execution times (WCETs) for architectures with caches requires the worst-case number of cache misses to be upper bounded. Most existing static cache analysis methods use Fixed-Point Computation and do not scale well with large code sizes. To address this scalability issue, we propose in this paper a new fast and scalable instruction cache analysis technique. In contrast to existing work, neither fixed- point Computation nor heavyweight interprocedural analysis are required. Thus, code sizes too long to analyze with existing techniques are then analyzable with lower analysis time and memory consumption, and with only a slight degradation of the analysis precision. Experimental results show a reduction of the analysis execution time of a factor 5 in average (with a peak near 30 for the largest and most complex code) with only a degradation of the analysis precision of 0.5% in average. The proposed technique is intended to be used in situations where the need for fast analysis outweighs the need for very tight results: early software development phases, timing analysis of large pieces of software, or iterative WCET-oriented compiler optimizations.
-
RTSS - Scalable Fixed-Point Free Instruction Cache Analysis
2011 IEEE 32nd Real-Time Systems Symposium, 2011Co-Authors: Damien Hardy, Benjamin Lesage, Isabelle PuautAbstract:Estimating worst-case execution times (WCETs) for architectures with caches requires the worst-case number of cache misses to be upper bounded. Most existing static cache analysis methods use Fixed-Point Computation and do not scale well with large code sizes. To address this scalability issue, we propose in this paper a new fast and scalable instruction cache analysis technique. In contrast to existing work, neither fixed point Computation nor heavyweight interprocedural analysis are required. Thus, code sizes too long to analyze with existing techniques are then analyzable with lower analysis time and memory consumption, and with only a slight degradation of the analysis precision. Experimental results show a reduction of the analysis execution time of a factor 5 in average (with a peak near 30 for the largest and most complex code) with only a degradation of the analysis precision of 0.5% in average. The proposed technique is intended to be used in situations where the need for fast analysis outweighs the need for very tight results: early software development phases, timing analysis of large pieces of software, or iterative WCET-oriented compiler optimizations.
Thomas A. Henzinger - One of the best experts on this subject based on the ideXlab platform.
-
Strategy construction for parity games with imperfect information
Information and Computation, 2010Co-Authors: Dietmar Berwanger, Krishnendu Chatterjee, Laurent Doyen, Martin De Wulf, Thomas A. HenzingerAbstract:We consider two-player parity games with imperfect information in which strategies rely on observations that provide imperfect information about the history of a play. To solve such games, i.e., to determine the winning regions of players and corresponding winning strategies, one can use the subset construction to build an equivalent perfect-information game. Recently, an algorithm that avoids the inefficient subset construction has been proposed. The algorithm performs a Fixed-Point Computation in a lattice of antichains, thus maintaining a succinct representation of state sets. However, this representation does not allow to recover winning strategies. In this paper, we build on the antichain approach to develop an algorithm for constructing the winning strategies in parity games of imperfect information. One major obstacle in adapting the classical procedure is that the complementation of attractor sets would break the invariant of downward-closedness on which the antichain representation relies. We overcome this difficulty by decomposing problem instances recursively into games with a combination of reachability, safety, and simpler parity conditions. We also report on an experimental implementation of our algorithm; to our knowledge, this is the first implementation of a procedure for solving imperfect-information parity games on graphs.
-
strategy construction for parity games with imperfect information
International Conference on Concurrency Theory, 2008Co-Authors: Dietmar Berwanger, Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger, Sangram RajeAbstract:We consider imperfect-informationparity games in which strategies rely on observations that provide imperfect information about the history of a play. To solve such games, i.e.to determine the winning regions of players and corresponding winning strategies, one can use the subset construction to build an equivalent perfect-informationgame. Recently, an algorithm that avoids the inefficient subset construction has been proposed. The algorithm performs a Fixed-Point Computation in a lattice of antichains, thus maintaining a succinct representation of state sets. However, this representation does not allow to recover winning strategies. In this paper, we build on the antichain approach to develop an algorithm for constructing the winning strategies in parity games of imperfect information. We have implemented this algorithm as a prototype. To our knowledge, this is the first implementation of a procedure for solving imperfect-information parity games on graphs.
-
CONCUR - Strategy Construction for Parity Games with Imperfect Information
CONCUR 2008 - Concurrency Theory, 2008Co-Authors: Dietmar Berwanger, Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger, Sangram RajeAbstract:We consider imperfect-informationparity games in which strategies rely on observations that provide imperfect information about the history of a play. To solve such games, i.e.to determine the winning regions of players and corresponding winning strategies, one can use the subset construction to build an equivalent perfect-informationgame. Recently, an algorithm that avoids the inefficient subset construction has been proposed. The algorithm performs a Fixed-Point Computation in a lattice of antichains, thus maintaining a succinct representation of state sets. However, this representation does not allow to recover winning strategies. In this paper, we build on the antichain approach to develop an algorithm for constructing the winning strategies in parity games of imperfect information. We have implemented this algorithm as a prototype. To our knowledge, this is the first implementation of a procedure for solving imperfect-information parity games on graphs.