32575594
Synthèse architecturale d'applications temps réel pour technologies submicroniques
La synthese d'architectures est un procede automatise qui facilite l'adequation algorithme architecture par l'exploration de l'espace des solutions architecturales. A partir d'une description comportementale de l'algorithme a integrer, les outils de synthese d'architectures permettent ainsi l'implantation materielle sous contraintes et fournissent rapidement des estimations de surfaces et de performances. Les outils actuels ne prennent cependant pas en compte de maniere efficace le cout des interconnexions internes aux circuits, cout qui devient predominant avec l'evolution conjointe des technologies et de la complexite des applications. Nous proposons une methode qui, a partir d'une analyse des interconnexions des le niveau comportemental et d'une modelisation de leurs parametres de couts, assure le controle des interconnexions tout au long du processus de synthese d'architectures et autorise ainsi une adequation algorithme architecture efficace a un haut niveau d'abstraction.
5563691
Synchronization processor synthesis for latency insensitive systems
In this paper we present our contribution in terms of synchronization processor for a SoC design methodology based on the theory of the latency insensitive systems (LIS) of Carloni et al. (2001). Our contribution consists in IP encapsulation into a new wrapper model whose speed and area are optimized and synthetizability guaranteed. The main benefit of our approach is to preserve the local IP performance when encapsulating them and reduce SoC silicon area.
15462003
How to transform an architectural synthesis tool for low power VLSI designs
High level synthesis (HLS) for low power VLSI design is a complex optimization problem due to the area/time/power interdependence. As few low power design tools are available, a new approach providing a modular low power synthesis method is proposed. Although based for the moment on a generic architectural synthesis tool Gaut, the use of different "commercial" tools is possible. The Gaut-w HLS tool is constituted of low power modules: high level power dissipation estimation, assignment, module selection (operators and supply voltage), optimization criteria and operators library. As illustration, power saving factors on DWT algorithms are presented.
3221643
Power Consumption Estimation of a C Program for Data-Intensive Applications
A method for estimating the power consumption of an algorithm is presented. The estimation can be performed both from the C program and from the assembly code. It relies on a power model for the targeted processor. Without compilation, several targets can be compared at the C-level in order to rapidly explore the design space. The estimation can be refined afterwards at the assembly level to allow further code optimizations. The power model of the Texas Instrument TMS320C6201 is presentedas a case study. Estimations are performed on real-life digital signal processing applications with average errors of 4.2 % at the C-level, and 1.8 % at the assembly level.
15834659
Architectural Synthesis with Interconnection Cost Control
Architectural synthesis tools map algorithms to architectures under various constraints and quickly provide estimations of area and performance. However, these tools do not take the interconnection cost into account whereas it becomes predominant with the technology decrease and the application complexity increase. A way to control costly interconnections during the architectural process is presented in this paper.
16853689
A complete methodology for memory optimization in DSP applications
In the digital and signal processing (DSP) applications, the main issue in system performance is strongly related to the memory subsystem characteristics and data positions. In such applications, exhaustive data analysis is often highly complex and time consuming whereas the actual bottlenecks are essentially due to the few largest data objects (arrays). Therefore, to ensure a good trade-off between analysis time and efficiency, we focus the optimization on these objects also called 'structures'. Our approach relies on a new graph formalism called 'data control flow graph' which analyzes an algorithm (written in C), and brings out data structure dependencies while retaining execution order constraints. Manipulating this graph allows to determine an optimized memory mapping according to a fixed memory hierarchy and thus to reduce bus activity, resulting in improved both execution time and energy consumption. This method is also planned to be extended to memory optimization by sizing both the memory hierarchy and the architecture.
10369661
Identifying Clusters from Positive Data
The present work studies clustering from an abstract point of view and investigates its properties in the framework of inductive inference. Any class $S$ considered is given by a hypothesis space, i.e., numbering, $A_0,A_1,\ldots$ of nonempty recursively enumerable (r.e.) subsets of ${\mathbb{N}}$ or ${\mathbb{Q}^k}$. A clustering task is a finite and nonempty set of r. e. indices of pairwise disjoint such sets. The class $S$ is said to be clusterable if there is an algorithm which, for every clustering task $I$, converges in the limit on any text for $\bigcup_{i \in I} A_i$ to a finite set $J$ of indices of pairwise disjoint clusters such that $\bigcup_{j \in J} A_j = \bigcup_{i \in I} A_i$. A class is called semiclusterable if there is such an algorithm which finds a $J$ with the last condition relaxed to $\bigcup_{j \in J} A_j \supseteq \bigcup_{i \in I} A_i$. 
 
The relationship between natural topological properties and clusterability is investigated. Topological properties can provide sufficient or necessary conditions for clusterability, but they cannot characterize it. On the one hand, many interesting conditions make use of both the topological structure of the class and a well-chosen numbering. On the other hand, the clusterability of a class does not depend on which numbering of the class is used as a hypothesis space for the\break clusterer. 
 
These ideas are demonstrated in the context of naturally geometrically defined classes. Besides the text for the clustering task, clustering of many of these classes requires the following additional information: the class of convex hulls of finitely many points in a rational vector space can be clustered with the number of clusters as additional information. Interestingly, the class of polygons (together with their interiors) is clusterable if the number of clusters and the overall number of vertices of these clusters is given to the clusterer as additional information. Intriguingly, this additional information is not sufficient for classes including figures with holes. 
 
While some classes are unclusterable due to their topological structure, others are only computationally intractable. An oracle might permit clustering all computationally intractable clustering tasks but fail on some classes which are topologically difficult. It is shown that an oracle $E$ permits clustering all computationally difficult classes iff $E \geq_T K \wedge E' \geq_T K"$. Furthermore, no 1-generic oracle below $K$ and no 2-generic oracle permits clustering any class which is not clusterable without an oracle.
31898263
Limiting Resolution: From Foundations to Implementation
We present a generalization of SLD-resolution, Limiting Resolution (LR) which embeds concepts from the field of inductive inference into logic programming. This paper describes the development of LR from theoretical underpinnings through to demonstrating a practical implementation. LR is designed to represent and solve problems which are not purely deductive more easily than current logic programming formalisms. It is based on the notion of identification in the limit, where successful computations produce a non-halting converging sequence of outputs as opposed to computations which produce a single output and halt. The queries of LR are of the form \(\exists \overline{x} ( \psi(\overline{x}) \land \forall \overline{y} \neg \chi(\overline{x},\overline{y}))\), with some restrictions on the occurrence of negation in ψ and χ. The programs are divided into background knowledge and a potentially infinite stream of data which drives the construction of the converging sequence of outputs. In some problems true negation can be applied to data in this stream. We describe the logical foundations of LR, where the notions of induction, deduction and identification in the limit are unified in a common framework. The programs, queries, and proof procedure of LR are precisely defined, and a completeness result is stated. Furthermore we present a Prolog-style system, RichProlog, which implements LR, and provide an extended example of RichProlog’s execution. This example shows that it is possible to solve genuine problems in polynomial time and also illustrates RichProlog’s utility, conciseness, and declarative nature.
7592429
On the Convergence of Incremental Knowledge Base Construction
Ripple Down Rules is a practical methodology to build knowledge-based systems, which has proved successful in a wide range of commercial applications. However, little work has been done on its theoretical foundations. In this paper, we formalise the key features of the method. We present the process of building a correct knowledge base as a discovery scenario involving a user, an expert, and a system. The user provides data for classification. The expert helps the system to build its knowledge base incrementally, using the output of the latter in response to the last datum provided by the user. In case the system’s output is not satisfactory, the expert guides the system to improve its future performance while not affecting its ability to properly classify past data. We examine under which conditions the sequence of knowledge bases constructed by the system eventually converges to a knowledge base that faithfully represents the target classification function. Our results are in accordance with the observed behaviour of real-life systems.
36905391
A note on the use of probabilities by mechanical learners
We raise the following problem: in a probabilistic context, is it always fruitful for a machine to compute probabilities? The question is made precise in a paradigm of the limit-identification kind, where a learner must discover almost surely whether an infinite sequence of heads and tails belongs to an effective subset S of the Cantor space. In this context, a successful strategy for an ineffective learner is to compute, at each stage, the conditional probability that he is faced with an element of S, given the data received so far. We show that an effective learner should not proceed this way in all circumstances. Indeed, even if he gets an optimal description of a set S, and even if some machine can always compute the conditional probability for S given any data, an effective learner optimizes his inductive competence only if he does not compute the relevant probabilities. We conclude that the advice “compute probabilities whenever you can” should sometimes be received with caution in the context of machine learning.
5821670
Learning in Logic with RichProlog
Deduction and induction are unified on the basis of a generalized notion of logical consequence, having classical first-order logic as a particular case. RichProlog is a natural extension of Prolog rooted in this generalized logic, in the same way as Prolog is rooted in classical logic. Prolog can answer ?1 queries as a side effect of a deductive inference. RichProlog can answer ?1 queries, ?1 queries (as a side effect of an inductive inference), and ?2 queries (as a side effect of an inductive inference followed by a deductive inference). RichProlog can be used to learn: a learning problem is expressed as a usual logic program, supplemented with data, and solved by asking a ?2 query. The output is correct in the limit, i.e., when sufficient data have been provided.