Abstract: This article provides an overview of a canonical representation for arithmetic expressions and how it can be used to obtain various factorizations of such expressions to optimize them. The applicability of the approach is demonstrated in a high-level synthesis flow.
Abstract: This paper presents a new unified design flow developed within the Perplexus IST European project [IST-034632]1 that aims to accelerate parallelizable data-intensive applications in the context of ubiquitous computing. This contribution relies on JubiTool: a set of integrated tools (JubiSplitter, JubiCompiler, UbiAssembler), allowing respectively to extract, compile and assemble parallelizable parts of applications described in Jubi language. Jubi is a modified Java agent based
language (JADE) dedicated to the Ubichip (the bio-inspired chip developed within the confines of the Perplexus project). By appending hardware directives to a software agent description,
the inherent flexibility of software is combined with the runtime performance of a hardware execution. In the case of typical Perplexus applications such as the Spiking Neural Network Simulator, this contribution takes profit of the intrinsic property of the Ubichip in terms of parallelism resulting in an expected speedup to be at least of one the order of magnitude.
Finally, this hybrid (SW/HW) flow could be easily modified and adapted to support other kind of distributed platforms.
Abstract: This paper describes an efficient graph-based method to optimize data-flow expressions for best hardware implementation. The method is based on factorization, common subexpression elimination (CSE) and decomposition of algebraic expressions performed on a canonical representation, Taylor Expansion Diagram. The method is generic, applicable to arbitrary algebraic expressions and does not require specific knowledge of the application domain. Experimental results show that the DFGs generated from such optimized expressions are better suited for high level synthesis, and the final, scheduled implementations are characterized, on average, by 15.5% lower latency and 7.6% better area than those obtained using traditional CSE and algebraic decomposition.
Abstract: An original technique to transform functional representation of the design into a structural representation in form of a data flow graph (DFG) is described. A canonical, word-level data structure, Taylor Expansion Diagram (TED), is used as a vehicle to effect this transformation. The problem is formulated as that of applying a sequence of decomposition cuts to a TED that transforms it into a DFG optimized for a particular objective. A systematic approach to arrive at such a decomposition is described. Experimental results show that such constructed DFG provides a better starting point for architectural synthesis than those extracted directly from HDL specifications.
Abstract: A systematic method and system for behavioral transformations for hardware synthesis and code optimization in software compilation based on Taylor Expansion Diagrams. The system can be integrated with any suitable architectural synthesis system. It can also be built into a compiler tool for general purpose processor or into a specific target compiler. For hardware synthesis, an arithmetic expression of the computation is extracted from the behavioral-level HDL design or directly from its matrix representation, and represented in canonical data structure, called Taylor Expansion Diagram. In architectural synthesis, factorization, common sub-expression extraction and decomposition of the resulting Taylor Expansion Diagram is performed, producing an optimized data flow graph, from which the structural HDL design is obtained using standard architectural synthesis. For software compilation and code optimization, common sub-expression extraction and factorization serve as pre-compilation optimization tasks performed according to the target architecture to generate a new code for the compiler.
Abstract: TDS is an experimental software system to perform high-level transformations of designs specified at algorithmic and behavioral levels. The system transforms the initial design specifications into a data flow graph (DFG) optimized for final hardware implementation. The optimizing transformations are based on a canonical representation, Taylor Expansion Diagram (TED), followed by structural transformations of the resulting DFG network. The system is intended for data-flow and computation-intensive designs used in computer graphics and digital signal processing applications.
Abstract: Unprecedented advances over the past few decades in semiconductor technology, combined with an impressive progress in telecommunications industry, have lead to an explosion of microelectronic designs in signal processing and multimedia applications. However, this advancement in microelectronics technology has significantly outperformed the progress in Electronic Design Automation (EDA) tools needed to sustain the productivity.In 1999 the Semiconductor Industry Association (SIA) warned that there is a widening gap between the technological capabilities provided by fabrication technology and design productivity achieved by chip designers. According to SIA, the solutions to reduce this "Design Productivity Gap", is to raise the level of abstraction of specifications and to increase the use of EDA tools to automatically generate the designs on physical level from ''high level" specifications.
In the same manner that made it necessary in the late 1980's to raise the level of abstraction of design specification from Boolean logic level to Register Transfer Level (RTL), the late 1990's have seen the level of abstraction increased from an RTL to a behavioral level. Whereas the adoption of RTL has lead to the creation of hardware description languages (HDL) and first uses of logic synthesis tools, the increase in the abstraction level to behavioral specifications resulted in the development of "high-level" synthesis (HLS) tools (or, more correctly, architectural synthesis tools) and design methodologies. Although progress has been made in HLS over the past two decades, current HLS tools are limited in their ability to transform the initial design specification into a final, optimized architecture. Specifically, those tools perform a direct translation of the initial specification without any attempt to optimize it, leaving any modification of the initial description to the designer. As a result, the same computation, described in different ways or by different algorithms, will result in often drastically different physical implementations, differing in power dissipation, area, delay, latency, or computational precision.
This thesis addresses this problem by employing a canonical representation, called "Taylor Expansion Diagram" (TED). TED is a graphical representation based on Taylor series decomposition of the data-flow computation. Optimizations and high-level transformations developed in this thesis are based on transformations and pattern recognition applied to the TED representation. The results of such transformations are the optimized data-flow graphs, which provide input to standard, HLS tools for final architectural synthesis. Such optimizations cannot be achieved by traditional architectural and "high-level" synthesis tools or compilers available today.
The work described in this thesis has been done in collaboration with the VLSI-CAD Laboratory at the University of Massachusetts, Amherst (USA). The algorithms developed in this work have been integrated with an experimental tool, "Taylor Decomposition System" (TDS), compatible with the architectural synthesis tool "GAUT".
References:
GAUT:http://web.univ-ubs.fr/lester/www-gaut/
TDS: http://tango.ecs.umass.edu/TED/Doc/html/index.html
