20167907
Hardware interface design for real time embedded systems
In this paper, we address the problem of hardware interface design in a Codesign approach for real time Digital Signal Processing (DSP) applications. We focus on the allocation problem of necessary storage components needed for data communication between hardware-software components. First, we present a modeling style for I/O data exchanged between both components and we describe our generic model of the hardware interface. Second, we describe a formal technique to the necessary storage components allocation. Our design strategy starts from the hardware I/O transfer sequences computed by a high level synthesis tool, like GAUT (E. Martin et al., 1993). It incorporates some interface specification (I/O transfer order, timing constraints) obtained by any cosynthesis tool (such as that developed by P. H. Chon et al., 1995). The proposed allocation procedure assigns for each I/O data a time interval at which its transfer could occur. The results presented are based on FFT algorithms implemented on ASICs.
34309839
Design of a flexible 2-D discrete wavelet transform IP core for JPEG2000 image coding in embedded imaging systems
The increasingly demanding requirements of multimedia applications have led to the definition of complex image and video coding standards such as JPEG2000 and MPEG4. Implementation of image or video encoders or decoders on mobile device requires high integration densities together with ability for "real-time" (on-the-fly) data processing. Today, the electronic system design community is mainly concerned with defining efficient System-on-a-Chip (SoC) design methodologies in order to benefit from the high integration capabilities of current application-specific integrated circuit and field-programmable gate array technologies on the one hand, and manage the increasing algorithmic complexity of applications on the other hand. Intellectual property (IP) reuse is considered as the key to speed up the system design and verification flow and make it more reliable.In this context, we have introduced a novel methodology for VLSI implementation of computation-intensive algorithms targeting digital signal processing applications. Our methodology combines IP reuse and high-level synthesis (HLS) and introduces the notion of "Behavioral IP". This approach aims at leveraging IP re-usability through functional and architectural flexibility based on: (1) modeling a component's behavior at a high abstraction level and (2) benefiting from HLS tools for architectural exploration and hardware generation.In this paper, we illustrate our methodology in the case of a 2-D discrete wavelet transform IP core for JPEG2000 image compression. We describe the successive views of the component throughout the design flow, from the application level down to the architectural level. We also provide synthesis results showing the variety of dedicated architectures that can be generated depending on user-defined functional-level, system-level and architectural-level requirements. We compare the performance and re-usability of the set of obtained architectures versus hand-crafted RTL specifications.
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.
11449422
Functional level power analysis: an efficient approach for modeling the power consumption of complex processors
A high-level consumption estimation methodology and its associated tool, SoftExplorer, are presented. The estimation methodology uses a functional modeling of the processor combined with a parametric model to allow the designer to estimate the power consumption when the embedded software is executed on the target. SoftExplorer uses as input the assembly code generated by the compiler; its efficiency is compared to SimplePower's approach. Results for different processors (TI C62, C67, C55, and ARM7) and for several DSP applications provide an average error less than 5%.
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.
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.
43024012
Absolute Versus Probabilistic Classification in a Logical Setting
Given a set $\mathcal{W}$of logical structures, or possible worlds, a set $\mathcal{D}$of logical formulas, or possible data, and a logical formula ϕ, we consider the classification problem of determining in the limit and almost always correctly whether a possible world $\mathcal{M}$satisfies ϕ, from a complete enumeration of the possible data that are true in $\mathcal{M}$. One interpretation of almost always correctly is that the classification might be wrong on a set of possible worlds of measure 0, w.r.t. some natural probability distribution over the set of possible worlds. Another interpretation is that the classifier is only required to classify a set $\mathcal{W}'$of possible worlds of measure 1, without having to produce any claim in the limit on the truth of ϕ in the members of the complement of $\mathcal{W}'$in $\mathcal{W}$. We compare these notions with absolute classification of $\mathcal{W}$w.r.t. a formula that is almost always equivalent to ϕ in $\mathcal{W}$, hence investigate whether the set of possible worlds on which the classification is correct is definable. Finally, in the spirit of the kind of computations considered in Logic programming, we address the issue of computing almost correctly in the limit witnesses to leading existentially quantified variables in existential formulas.
13158446
On Ordinal VC-Dimension and Some Notions of Complexity
We generalize the classical notion of VC-dimension to ordinal VC-dimension, in the context of logical learning paradigms. Logical learning paradigms encompass the numerical learning paradigms commonly studied in Inductive inference. A logical learning paradigm is defined as a set W of structures over some vocabulary, and a set D of first-order formulas that represent data. The sets of models of φ in W, where φ varies over D, generate a natural topology W over W. We show that if D is closed under boolean operators, then the notion of ordinal VC-dimension offers a perfect characterization for the problem of predicting the truth of the members of D in a member of W, with an ordinal bound on the number of mistakes. This shows that the notion of VC-dimension has a natural interpretation in Inductive Inference, when cast into a logical setting. We also study the relationships between predictive complexity, selective complexity—a variation on predictive complexity—and mind change complexity. The assumptions that D is closed under boolean operators and that W is compact often play a crucial role to establish connections between these concepts.
980414
A General Theory of Deduction, Induction, and Learning
Deduction, induction, learning, are various aspects of a more general scientific activity: the discovery of truth. We propose to embed them in a common, logical framework. First, we define a generalized notion of "logical consequence." Alternating compact and "weakly compact" consequences, we stratify the set of generalized logical consequences of a given theory in a hierarchy. Classical first-order logic is a particular case of this framework; the fact that it is all about deduction is due to the compactness theorem, and this is reflected by the collapsing of the corresponding hierarchy to the first level. Classical learning paradigms in the inductive inference literature provide other particular cases. Finite learning corresponds exactly to the first level (or level ?1) of the hierarchy, whereas learning in the limit corresponds to another level (namely ?2). More generally, strong and natural connections exist between our hierarchy of generalized logical consequences, the Borel hierarchy, and the hierarchy which measures the complexity of a formula in terms of alternations of quantifiers. It is hoped that this framework provides the foundation of a unified logic of deduction and induction, and highlights the inductive nature of learning. An essential motivation for our work is to apply the theory presented here to the design of "Inductive Prolog", a system with both deductive and inductive capabilities, based on a natural extension of the resolution principle.
39139980
On Sufficient Conditions for Learnability of Logic Programs from Positive Data
Shinohara, Arimura, and Krishna Rao have shown learnability in the limit of minimal models of classes of logic programs from positive only data. In most cases, these results involve logic programs in which the "size" of the head yields a bound on the size of the body literals. However, when local variables are present, such a bound on body literal size cannot directly be ensured. The above authors achieve such a restriction using technical notions like mode and linear inequalities. The present paper develops a conceptually clean framework where the behavior of local variables is controlled by nonlocal ones. It is shown that for certain classes of logic programs, learnablity from positive data is equivalent to limiting identification of bounds for the number of clauses and the number of local variables. This reduces the learning problem finding two integers. This cleaner framework generalizes all the known results and establishes learnability of new classes.