Energy-efficient hardware accelerators specialized for AI tasks are now being deployed from low-power edge devices to large-scale high-performance computing systems and data centers. This paper presents the main outcomes of the Flagship 2 project of the ICSC Italian National Research Center for High Performance Computing, which focuses on the design techniques for heterogeneous hardware optimized for AI acceleration from the edge to the HPC. In particular, we describe the main challenges addressed and highlight some advances in architectures, technologies, and design methodologies tailored to accelerate deep learning, transformer-based, and generative AI models. We also summarize the most significant outcomes achieved through the close collaboration among the project partners, including the development of design techniques, tools, prototypes, IP cores, and models that collectively advance AI acceleration from the edge to the HPC contexts.

Domain-specific systems improve the performance of specific applications compared to general-purpose processing systems by deploying custom hardware accelerators. These hardware accelerators are generated using high-level synthesis (HLS) tools. The HLS tools enable a comprehensive design space exploration, optimizing the accelerators' compute performance. However, they often ignore the challenges of implementing the accelerators in a system-on-chip, particularly how they access memory. Our work introduces a buffering system design that improves accelerators' memory accesses by intelligently employing burst transactions to prefetch useful data from external memory to on-chip local buffers. Our design is dynamic, parametric, and transparent to the accelerators generated by HLS tools. We derive the buffering system parameters using appropriate compiler-based analysis passes and memory channel latency constraints. The proposed buffering system design results in, on average, 8.8× performance improvements while lowering memory channel utilization by 53.2% for a set of PolyBench kernels.

Recent pre-exascale and exascale supercomputers have driven the development of increasingly sophisticated AI models for diverse applications, including image recognition and classification, natural language processing, and generative AI. These applications require specialized hardware accelerators, to handle the heavy computational demands of AI algorithms in an energy-efficient manner. Today, AI accelerators are deployed across various systems, from low-power edge devices to large-scale servers, high-performance computing (HPC) infrastructures, and data centers. The primary objective of the ICSC Flagship 2 project, discussed in this paper, is to develop heterogeneous hardware platforms optimized to accelerate HPC and big data applications. Specifically, this paper provides an overview of the key challenges addressed and the achievements realized at the current intermediate stage of the ICSC Flagship 2 project focused on architectures, technologies, and design methodologies to design efficient hardware accelerators for AI workloads, such as deep learning (DL) and transformer models.

Functional verification of accelerator designs generated through High-Level Synthesis (HLS) requires users to write low-level testbenches and feed them to a Register-Transfer Level (RTL) simulator alongside the generated accelerator. Such a manual and error-prone process hinders early design space exploration due to the inherently slow RTL simulation phase, and it is unable to capture the interaction between the host application and the accelerated kernels. We propose two key improvements to the co-simulation process integrated within an HLS tool: a fast and accurate functional simulation methodology that calculates clock cycles during software execution of an annotated HLS intermediate representation, and a system-level co-simulation that couples RTL simulation with software execution of a host application through direct programming interfaces and inter-process communication. Both components augment the HLS verification process, enabling developers to extract kernels to be accelerated from a large application, quickly verify their expected performance after synthesis, and automatically validate their correctness by simulating a full host-accelerator system. Our augmented functional verification methodology is, on average, 7.0x faster than a state-of-the-art method and 36.2x faster than RTL simulation in terms of simulated cycles per second, with high accuracy and minimal memory overhead.

This article presents a methodology for the Synthesis of PARallel multi-Threaded Accelerators (SPARTA) from OpenMP annotated C/C++ specifications. SPARTA extends an open-source HLS tool, enabling the generation of accelerators that provide latency tolerance for irregular memory accesses through multithreading, support fine-grained memory-level parallelism through a hot-potato deflection-based network-on-chip (NoC), support synchronization constructs, and can instantiate memory-side caches. Our approach is based on a custom runtime OpenMP library, providing flexibility and extensibility. Experimental results show high scalability when synthesizing irregular graph kernels. The accelerators generated with our approach are, on average, 2.29 \(\times\) faster than state-of-the-art HLS methodologies.

The Software Defined Architectures (SODA) Synthesizer is an open-source compiler-based tool able to automatically generate domain-specialized systems targeting Application-Specific Integrated Circuits (ASICs) or Field Programmable Gate Arrays (FPGAs) starting from high-level programming. SODA is composed of a high-level frontend, SODA-OPT, which leverages the multilevel intermediate representation (MLIR) framework to interface with productive programming tools (e.g., machine learning frameworks), identify kernels suitable for acceleration, and perform high-level optimizations, and of a state-of-the-art high-level synthesis backend, Bambu from the PandA framework, to generate custom accelerators. One specific application of the SODA Synthesizer is the generation of accelerators to enable ultra-low latency inference and control on autonomous systems for scientific discovery (e.g., electron microscopes, sensors in particle accelerators, etc.). This talk will discuss ongoing work on the SODA synthesizer to enable no-human-in-the-loop generation and design space exploration of the chiplets for highly specialized artificial intelligence accelerators. Connecting these highly specialized chiplets to general-purpose cores or programmable accelerators will allow to quickly deploy autonomous systems for scientific discovery.

Modern big data workflows are characterized by computationally intensive kernels. The simulated results are often combined with knowledge extracted from AI models to ultimately support decision-making. These energy-hungry workflows are increasingly executed in data centers with energy-efficient hard-ware accelerators since FPG As are well-suited for this task due to their inherent parallelism. We present the H2020 project EVEREST, which has developed a system development kit (SDK) to simplify the creation of FPGA-accelerated kernels and manage the execution at runtime through a virtualization environment. This paper describes the main components of the EVEREST SDK and the benefits that can be achieved in our use cases.

Specialized hardware is often key to accelerate big data applications [2], [3]. However, while High-Level Synthesis (HLS) has advanced considerably in the past decades, offloading to FPGAs still requires significant manual effort from platform experts [4]. This is especially the case for industrial applications and when kernels may execute, interchangeably, on CPU or FPGA. To reduce this effort, we present Etna, an integrated MLIR-based development approach for applications with re-targetable kernels. As shown in Figure 1 (bottom), Etna takes as inputs a set of kernels for both CPU (C/C++) and FPGA execution (C/C++/MLIR for HLS), the FPGA description, and the MLIR representation of the application's dataflow graph (DFG). Etna supports Application Composition, System Generation, and integration with HLS tools for kernel synthesis. This is enabled by two novel MLIR dialects: dfg to describe the interactions among the kernels and olympus to describe the system-level architecture. dfg represents a generic graph model that can be extracted, e.g., from implicit dataflow languages [5]. In Application Composition, kernels marked as offloaded in the dfg dialect are lowered to olympus for hardware generation. The remaining kernels are lowered to LLVM-IR for code generation. Olympus takes the olympus representation of the offloaded portion of the DFG and performs System Generation to create an optimized system architecture and host drivers. For kernel HLS we use Bambu [1] for its unique support for data containers. The resulting HDL is instantiated within the system architecture. Finally, all CPU-side sources (application LLVM-IR, CPU kernel sources, FPGA kernel drivers) are linked to produce an executable.

Artificial Intelligence (AI) and Machine Learning (ML) methods offer significant opportunities to improve the quality of results in high-level synthesis (HLS). For instance, they can be used to model and predict metrics of the final design (e.g., area, considering aspects such as interconnect overhead for different device technologies), thereby facilitating exploration when searching for the best design trade-offs. Additionally, they can help identify hidden correlations across various phases of synthesis and the optimizations performed, enabling the identification of the most effective pipelines. Furthermore, these methods can greatly facilitate and enhance the design space exploration for the synthesis process in terms of both time and quality of results. This paper discusses the opportunities and challenges of augmenting HLS with AI/ML, using as an example the SODA Synthesizer, an open-source hardware generation toolchain that includes SODA-OPT, a hardware/software partitioning and pre-optimization tool developed with the MLIR framework, and PandA-Bambu, a state-of-the-art HLS tool. SODA interfaces with OpenROAD to provide a complete end-to-end toolchain.

The Software Defined Architectures (SODA) Synthesizer is an open-source compiler-based tool able to automatically generate domain-specialized systems targeting Application-Specific Integrated Circuits (ASICs) or Field Programmable Gate Arrays (FPGAs) starting from high-level programming. SODA is composed of a frontend, SODA-OPT, which leverages the multilevel intermediate representation (MLIR) framework to interface with productive programming tools (e.g., machine learning frameworks), identify kernels suitable for acceleration, and perform high-level optimizations, and of a state-of-the-art high-level synthesis backend, Bambu from the PandA framework, to generate custom accelerators. One specific application of the SODA Synthesizer is the generation of accelerators to enable ultra-low latency inference and control on autonomous systems for scientific discovery (e.g., electron microscopes, sensors in particle accelerators, etc.). This paper provides an overview of the flow in the context of the generation of accelerators for edge processing to be integrated in transmission electron microscopy (TEM) devices, focusing on use cases from precision material synthesis. We show the tool in action with an example of design space exploration for inference on reconfigurable devices with a conventional deep neural network model (LeNet). Finally, we discuss the research directions and opportunities enabled by SODA in the area of autonomous control for scientific experimental workflows.

Model-based development techniques in Matlab/Simulink simplify the design and implementation of software for aerospace applications, providing the required level of abstraction for scientists that work on complex navigation and control algorithms. As Field Programmable Gate Arrays (FPGAs) have become more and more relevant in space hardware platforms, developers could benefit from automated acceleration flows that do not require extensive manual rewriting of their code to port it on FPGA. We analyze existing methods that synthesize Simulink models, showing how a combination of automated C code generation and High-Level Synthesis can enable rapid prototyping, fast design space exploration, and a good trade-off between accelerator efficiency and design flexibility. We test the proposed acceleration flow on real-world guidance and navigation control systems for CubeSats.

Field Programmable Gate Arrays (FPGAs) are reconfigurable hardware components that can be programmed using a hardware specification language such as Verilog or VHDL.Writing code to program an FPGA requires a set of different skills than software programming, for example, related to the use of signals and registers instead of variables and the explicit description of parallelism. High-Level Synthesis (HLS) tools can help by automatically translating software specifications into hardware descriptions.

European efforts to boost competitiveness in the sector of space services promote the research and development of advanced software and hardware solutions. The EU-funded HERMES project contributes to the effort by qualifying radiation-hardened, high-performance programmable microprocessors, and by developing$a$software ecosystem that facilitates the deployment of complex applications on such platforms. The main objectives of the project include reaching a technology readiness level of 6 (i.e., validated and demonstrated in relevant environment) for the rad-hard NG-ULTRA FPGA with its ceramic hermetic package CGA 1752, developed within projects of the European Space Agency, French National Centre for Space Studies and the European Union. An equally important share of the project is dedicated to the development and validation of tools that support multicore software programming and FPGA acceleration, including Bambu for High-Level Synthesis and the XtratuM hypervisor with a level one boot loader for virtualization.

In modern SoC designs, digital components' development and verification processes often depend on the component's interactions with other digital and analog modules on the same die. While designers can rely on a wide range of tools and practices for validating fully-digital models, porting the same workflow to mixed models' development requires significant efforts from the designers. A common practice is to use Real Number Modeling techniques to generate HDL-based behavioral models of analog components to efficiently simulate mixed models using only event-based simulations rather than Analog Mixed Signals (AMS) simulations. However, some of these models' language features are not synthesizable with existing synthesis tools, requiring additional efforts from the designers to generate post-tapeout prototypes. This paper presents a methodology for transforming some non-synthesizable System Verilog language features related to timing controls into functionally-equivalent synthesizable Verilog constructs. The resulting synthesizable models replicate their respective RNMs' behavior while explicitly managing delay controls and event expressions. The RNMs are first transformed using the MLIR framework and then synthesized with open-source HLS tools to obtain FPGA-synthesizable Verilog models.

High-Level Synthesis (HLS) tools automatically translate code from a general-purpose programming language (typically C or C++) into a hardware description language (HDL) such as Verilog or VHDL, significantly reducing the hardware design productivity gap. HLS benefits from the same compiler optimizations that identify instruction, memory, and data parallelism for general-purpose processors. However, they also need to consider specific needs of low-level circuit design, such as the notion of time, synchronous and asynchronous logic, and wiring delays. Because of the mismatch between hardware abstractions and general-purpose programming languages, HLS tools often require the addition of pragma directives in the input code to guide hardware generation.

Machine learning (ML) and deep learning algorithms are well suited to process and analyze large amounts of data, as it has been repeatedly proven in applications such as image classification, natural language processing, or recommendation systems. Both ML training and inference are compute- and memory-intensive, leading to widespread adoption of heterogeneous systems containing specialized accelerators. While graphic processing units (GPUs) are the established platform of choice to accelerate training, they are often too power-hungry to run inference tasks, or cannot meet the strict latency requirements of scientific experiments. A variety of custom solutions implemented as field programmable gate arrays (FPGAs) or application-specific circuit (ASICs) have been proposed in their place, ranging from generic "neural processors" to accelerators that focus on a narrow set of models with great efficiency.

Novel "converged" applications combine phases of scientific simulation with data analysis and machine learning. Each computational phase can benefit from specialized accelerators. However, algorithms evolve so quickly that mapping them on existing accelerators is suboptimal or even impossible. This paper presents the SODA (Software Defined Accelerators) framework, a modular, multi-level, open-source, no-human-in-the-loop, hardware synthesizer that enables end-to-end generation of specialized accelerators. SODA is composed of SODA-Opt, a high-level frontend developed in MLIR that interfaces with domain-specific programming frameworks and allows performing system level design, and Bambu, a state-of-the-art high-level synthesis engine that can target different device technologies. The framework implements design space exploration as compiler optimization passes. We show how the modular, yet tight, integration of the high-level optimizer and lower-level HLS tools enables the generation of accelerators optimized for the computational patterns of converged applications. We then discuss some of the research opportunities that such a framework allows, including system-level design, profile driven optimization, and supporting new optimization metrics.

Presents a powerpoint on the topic of high level frameworks to custom silicon with SODA.

The SODA Synthesizer is an open-source, modular, end-to-end hardware compiler framework. The SODA frontend, developed in MLIR, performs system-level design, code partitioning, and high-level optimizations to prepare the specifications for the hardware synthesis. The backend is based on a state-of-the-art high-level synthesis tool and generates the final hardware design. The backend can interface with logic synthesis tools for field programmable gate arrays or with commercial and open-source logic synthesis tools for application-specific integrated circuits. We discuss the opportunities and challenges in integrating with commercial and open-source tools both at the frontend and backend, and highlight the role that an end-to-end compiler framework like SODA can play in an open-source hardware design ecosystem.

Edge systems are required to autonomously make real-time decisions based on large quantities of input data under strict power, performance, area, and other constraints. Meeting these constraints is only possible by specializing systems through hardware accelerators purposefully built for machine learning and data analysis algorithms. However, data science evolves at a quick pace, and manual design of custom accelerators has high non-recurrent engineering costs: general solutions are needed to automatically and rapidly transition from the formulation of a new algorithm to the deployment of a dedicated hardware implementation. Our solution is the SOftware Defined Architectures (SODA) Synthesizer, an end-to-end, multi-level, modular, extensible compiler toolchain providing a direct path from machine learning tools to hardware. The SODA Synthesizer frontend is based on the multilevel intermediate representation (MLIR) framework; it ingests pre-trained machine learning models, identifies kernels suited for acceleration, performs high-level optimizations, and prepares them for hardware synthesis. In the backend, SODA leverages state-of-the-art high-level synthesis techniques to generate highly efficient accelerators, targeting both field programmable devices (FPGAs) and application-specific circuits (ASICs). In this paper, we describe how the SODA Synthesizer can also assemble the generated accelerators (based on the finite state machine with datapath model) in a custom system driven by a distributed controller, building a coarse-grained dataflow architecture that does not require a host processor to orchestrate parallel execution of multiple accelerators. We show the effectiveness of our approach by automatically generating ASIC accelerators for layers of popular deep neural networks (DNNs). Our high-level optimizations result in up to 74x speedup on isolated accelerators for individual DNN layers, and our dynamically scheduled architecture yields an additional 3x performance improvement when combining accelerators to handle streaming inputs.

Graph analytics are an emerging class of irregular applications. Operating on very large datasets, they present unique behaviors, such as fine-grained, unpredictable memory accesses, and highly unbalanced task level parallelism, that make existing high-performance general-purpose processors or accelerators (e.g., GPUs) suboptimal. To address these issues, research and industry are developing a variety of custom accelerator designs for this application area, including solutions based on reconfigurable devices (Field Programmable Gate Arrays). These new approaches often employ High-Level Synthesis (HLS) to Speed up the development of the accelerators. In this paper, we propose a novel architecture template for the automatic generation of accelerators for graph analytics and irregular applications. The architecture template includes a dynamic task scheduling mechanism, a parallel array of accelerators that enables supporting task-level parallelism with context switching, and a related multi-channel memory interface that decouples communication from computation and provides support for fine-grained atomic memory operations. We discuss the integration of the architectural template in an HLS flow, presenting the necessary modifications to enable automatic generation of the custom architectures starting from OpenMP annotated code. We evaluate our approach first by synthesizing and exploring triangle counting, a common graph algorithm, and then by synthesizing custom designs for a set of graph database benchmark queries, representing series of graph pattern matching routines. We compare the synthesized accelerators with previous state-of-the-art methodologies for the synthesis of parallel architectures, showing that the proposed approach allows reducing resource usage by optimizing the number of accelerators replicas without any performance penalty.

This paper presents the open-source high-level synthesis (HLS) research framework Bambu. Bambu provides a research environment to experiment with new ideas across HLS, high-level verification and debugging, FPGA/ASIC design, design flow space exploration, and parallel hardware accelerator design. The tool accepts as input standard C/C++ specifications and compiler intermediate representations (IRs) coming from the well-known Clang/LLVM and GCC compilers. The broad spectrum and flexibility of input formats allow the electronic design automation (EDA) research community to explore and integrate new transformations and optimizations. The easily extendable modular framework already includes many optimizations and HLS benchmarks used to evaluate the QoR of the tool against existing approaches [1]. The integration with synthesis and verification backends (commercial and open-source) allows researchers to quickly test any new finding and easily obtain performance and resource usage metrics for a given application. Different FPGA devices are supported from several different vendors: AMD/Xilinx, Intel/Altera, Lattice Semiconductor, and NanoXplore. Finally, integration with the OpenRoad open-source end-to-end silicon compiler perfectly fits with the recent push towards open-source EDA.

High-Performance Big Data Analytics (HPDA) applications are characterized by huge volumes of distributed and heterogeneous data that require efficient computation for knowledge extraction and decision making. Designers are moving towards a tight integration of computing systems combining HPC, Cloud, and IoT solutions with artificial intelligence (AI). Matching the application and data requirements with the characteristics of the underlying hardware is a key element to improve the predictions thanks to high performance and better use of resources. We present EVEREST, a novel H2020 project started on October 1, 2020, that aims at developing a holistic environment for the co-design of HPDA applications on heterogeneous, distributed, and secure platforms. EVEREST focuses on programmability issues through a data-driven design approach, the use of hardware-accelerated AI, and an efficient runtime monitoring with virtualization support. In the different stages, EVEREST combines state-of-the-art programming models, emerging communication standards, and novel domain-specific extensions. We describe the EVEREST approach and the use cases that drive our research.

The multiplication of large integers represents a significant computation effort in some cryptographic techniques. The use of dedicated hardware is an appealing solution to improve performances or efficiency. We propose a methodology to generate throughput oriented hardware accelerators for large integers multiplication leveraging High-Level Synthesis. The proposed micro-architectural template combines Karatsuba and Comba algorithms to control the extra-functional properties of the generated multiplier. The goal is to enable the end user to explore a wide range of possibilities, in terms of performance and resource utilization, without requiring them to know implementation and synthesis details. Experimental results show the large flexibility of the generated architectures and that the generated Pareto-set of multipliers can outperform some state-of-the-art RTL design.

The growing numbers of application areas for artificial intelligence (AI) methods have led to an explosion in availability of domain-specific accelerators, which struggle to support every new machine learning (ML) algorithm advancement, clearly highlighting the need for a tool to quickly and automatically transition from algorithm definition to hardware implementation and explore the design space along a variety of SWaP (size, weight and Power) metrics. The software defined architectures (SODA) synthesizer implements a modular compiler-based infrastructure for the end-to-end generation of machine learning accelerators, from high-level frameworks to hardware description language. Neuromorphic computing, mimicking how the brain operates, promises to perform artificial intelligence tasks at efficiencies orders-of-magnitude higher than the current conventional tensor-processing based accelerators, as demonstrated by a variety of specialized designs leveraging Spiking Neural Networks (SNNs). Nevertheless, the mapping of an artificial neural network (ANN) to solutions supporting SNNs is still a non-trivial and very device-specific task, and completely lacks the possibility to design hybrid systems that integrate conventional and spiking neural models. In this paper, we discuss the design of such an integrated generator, leveraging the SODA Synthesizer framework and its modular structure. In particular, we present a new MLIR dialect in the SODA frontend that allows expressing spiking neural network concepts (e.g., spiking sequences, transformation, and manipulation) and we discuss how to enable the mapping of spiking neurons to the related specialized hardware (which could be generated through middle-end and backend layers of the SODA Synthesizer). We then discuss the opportunities for further integration offered by the hardware compilation infrastructure, providing a path towards the generation of complex hybrid artificial intelligence systems.

Conventional High-Level Synthesis (HLS) tools exploit parallelism mostly at the Instruction Level (ILP). They statically schedule the input specifications and build centralized Finite State Machine (FSM) controllers. However, aggressive exploitation of ILP in many applications has diminishing returns and, usually, centralized approaches do not efficiently exploit coarser parallelism, because FSMs are inherently serial. In this paper we present an HLS framework able to synthesize applications that, beside ILP, also expose Task Level Parallelism (TLP). An application can expose TLP through annotations that identify the parallel functions (i.e., tasks). To generate accelerators that efficiently execute concurrent tasks, we need to solve several issues: devise a mechanism to support concurrent execution flows, exploit memory parallelism, and manage synchronization. To support concurrent execution flows, we introduce a novel adaptive controller. The adaptive controller is composed of a set of interacting control elements that independently manage the execution of a task. These control elements check dependencies and resource constraints at runtime, enabling as soon as possible execution. To support parallel access to shared memories and synchronization, we integrate with a novel Hierarchical Memory Interface (HMI). With respect to previous solutions, the proposed interface supports multi-ported memories and atomic memory operations, which commonly occur in parallel programming. Our framework can generate the hardware implementation of C functions by employing two different approaches, depending on its characteristics. If a function exposes TLP, then the framework generates hardware implementations based on the adaptive controller. Otherwise, the framework implements the function through the FSM approach, which is optimized for ILP exploitation. We evaluate our framework on a set of parallel applications and show substantial performance improvements (average speedup of 4.7) with limited area overheads (average area increase of 5.48 times).

Improving data locality of tensor data structures is a crucial optimization for maximizing the performance of machine learning and intensive linear algebra applications. While CPUs and GPUs improve data locality by means of automated caching mechanisms, FPGAs let the developer specify data structure allocation. Although this feature enables a high degree of customizability, the increasing complexity and memory footprint of modern applications prevent considering any manual approach to find an optimal allocation. For this reason, we propose a compiler optimization to automatically improve the tensor allocation of high-level software descriptions. The optimization is controlled by a flexible cost model that can be tuned by means of simple yet expressive callback functions. In this way, the user can tailor the optimization strategy with respect to the optimization goal. We tested our methodology integrating our optimization in the Bambu open-source HLS framework. In this setting, we achieved a 14% speedup on the digit recognition version proposed by the Rosetta benchmark. Moreover, we tested our optimization on the CHStone benchmark suite, achieving an average of 6% speedup. Finally, we applied our methodology on two industrial examples from the aerospace domain obtaining a 15% speedup. As a final step, we tested the versatility of our methodology inserting our optimization in the Clang software optimization flow achieving a 12% speedup on the Rosetta benchmark when running on CPU.

Data analytics applications increasingly are complex workflows composed of phases with very different program behaviors (e.g., graph algorithms and machine learning, algorithms operating on sparse and dense data structures, etc). To reach the levels of efficiency required to process these workflows in real time, upcoming architectures will need to leverage even more workload specialization. If, at one end, we may find even more heterogenous processors composed by a myriad of specialized processing elements, at the other end we may see novel reconfigurable architectures, composed of sets of functional units and memories interconnected with (re)configurable on-chip networks, able to adapt dynamically to adapt the workload characteristics. Field Programmable Gate Arrays are more and more used for accelerating various workloads and, in particular, inferencing in machine learning, providing higher efficiency than other solutions. However, their fine-grained nature still leads to issues for the design software and still makes dynamic reconfiguration impractical. Future, more coarse-grained architectures could offer the features to execute diverse workloads at high efficiency while providing better reconfiguration mechanisms for dynamic adaptability. Nevertheless, we argue that the challenges for reconfigurable computing remain in the software. In this position paper, we describe a possible toolchain for reconfigurable architectures targeted at data analytics.

High Level Synthesis is a set of methodologies aimed at generating hardware descriptions starting from specifications written in high-level languages. While these methodologies share different elements with traditional compilation flows, there are characteristics of the addressed problem which require ad hoc management. In particular, differently from most of the traditional compilation flows, the complexity and the execution time of the High Level Synthesis techniques are much less relevant than the quality of the produced results. For this reason, fixed-point analyses, as well as successive refinement optimizations, can be accepted, provided that they can improve the quality of the generated designs. This article presents a design flow engine for the description and the execution of complex and customized synthesis flows. It supports dynamic addition of passes and dependencies, cyclic dependencies, and selective pass invalidation. Experimental results show the benefits of such type of design flows with respect to static linear design flows when applied to High Level Synthesis.

High-Level Synthesis (HLS) for FPGAs is attracting popularity and is increasingly used to handle complex systems with multiple integrated components. To increase performance and efficiency, HLS flows now adopt several advanced optimization techniques. Aggressive optimizations and system level integration can cause the introduction of bugs that are only observable on-chip. Debugging support for circuits generated with HLS is receiving a considerable attention. Among the data that can be collected on chip for debugging, one of the most important is the state of the Finite State Machines (FSM) controlling the components of the circuit. However, this usually requires a large amount of memory to trace the behavior during the execution. This work proposes an approach that takes advantage of the HLS information and of the structure of the FSM to compress control flow traces and to integrate optimized components for on-chip debugging. The generated checkers analyze the FSM execution on-fly, automatically notifying when a bug is detected, localizing it and providing data about its cause. The traces are compressed using a software profiling technique, called Efficient Path Profiling (EPP), adapted for the debugging of hardware accelerators generated with HLS. With this technique, the size of the memory used to store control flow traces can be reduced up to 2 orders of magnitude, compared to state-of-the-art.

Data analytics applications, such as graph databases, exibit irregular behaviors that make their acceleration non-trivial. These applications expose a significant amount of Task Level Parallelism (TLP), but they present fine grained memory accesses.

Modern High-Level Synthesis (HLS) compilers aggressively optimize memory architectures. Bugs involving memory accesses are hard to detect, especially if they are inserted in the compilation process. We present an approach to isolate automatically memory bugs introduced by HLS tools, without user interaction, using only the original high-level specification. This is possible by tracing memory accesses in software (SW) and hardware (HW) executions on a given input dataset. The execution traces are compared performing a context-aware HW/SW address translation, leveraging alias-analysis, HLS memory allocation information and SW memory debugging practices. No restrictions are imposed on memory optimizations. We show results on the relevance of the problem, the coverage, the detected bugs. We also show that the approach can be adapted to different commercial and academic HLS tools.

Presents a collection of slides covering the following: scheduling; graph methods; data analysis; parallel processing; memory interface controller; and load balancing.

RDF databases naturally map to a graph representation and employ languages, such as SPARQL, that implements queries as graph pattern matching routines. Graph methods exhibit an irregular behavior: they present unpredictable, fine-grained data accesses, and are synchronization intensive. Graph data structures expose large amounts of dynamic parallelism, but are difficult to partition without generating load unbalance. In this paper, we present a novel architecture to improve the synthesis of graph methods. Our design addresses the issues of these algorithms with two components: a Dynamic Task Scheduler (DTS), which reduces load unbalance and maximize resource utilization, and a Hierarchical Memory Interface controller (HMI), which provides support for concurrent memory operations on multi-ported/multi-banked shared memories. We evaluate our approach by generating the accelerators for a set of SPARQL queries from the Lehigh University Benchmark (LUBM). We first analyze the load unbalance of these queries, showing that execution time among tasks can differ even of order of magnitudes. We then synthesize the queries and compare the performance of the resulting accelerators against the current state of the art. Experimental results show that our solution provides a speedup over the serial implementation close to the theoretical maximum and a speedup up to 3.45 over a baseline parallel implementation. We conclude our study by exploring the design space to achieve maximum memory channels utilization. The best design used at least three of the four memory channels for more than 90% of the execution time.

High-level synthesis (HLS) is increasingly popular for the design of high-performance and energy-efficient heterogeneous systems, shortening time-to-market and addressing today’s system complexity. HLS allows designers to work at a higher-level of abstraction by using a software program to specify the hardware functionality. Additionally, HLS is particularly interesting for designing field-programmable gate array circuits, where hardware implementations can be easily refined and replaced in the target device. Recent years have seen much activity in the HLS research community, with a plethora of HLS tool offerings, from both industry and academia. All these tools may have different input languages, perform different internal optimizations, and produce results of different quality, even for the very same input description. Hence, it is challenging to compare their performance and understand which is the best for the hardware to be implemented. We present a comprehensive analysis of recent HLS tools, as well as overview the areas of active interest in the HLS research community. We also present a first-published methodology to evaluate different HLS tools. We use our methodology to compare one commercial and three academic tools on a common set ofCbenchmarks, aiming at performing an in-depth evaluation in terms of performance and the use of resources.

The current generation of High Level Synthesis (HLS) tools usually generates hierarchical and modular designs, mimicking the structure of the call graph of the original high-level input specification. The standard approach is to progressively synthesize functions into modules by navigating the application call graph from the leaves up to the top function. In the synthesized architecture, function calls corresponds to the instantiation of the related module into the data path generated for the caller. Our work introduces a methodology that enables sharing of (sub)modules across modules boundaries.

Modular design is becoming increasingly important in High Level Synthesis (HLS) flows. Current HLS flows generate hierarchical and modular designs that mimic the structure and call graph of the input specification by translating functions into modules. Function calls are translated by instantiating the callee module in the data-path of its caller, allowing for resource sharing when the same function is called multiple times. However, if two different callers invoke the same function, current HLS flows cannot share the instance of the module between the two callers, even if they invoke the function in a mutually exclusive way. In this paper, we propose a methodology that enables sharing of (sub)modules across modules boundaries. Sharing is obtained through function proxies, which act as forwarders of function calls in the original specification to shared modules without reducing performance. Building on the concept of function proxies, we propose a methodology and the related components to perform HLS of function calls through function pointers, without requiring complete static knowledge of the alias set (point-to set). We show that module sharing through function proxies provides valuable area savings and no significant impacts on the execution delays, and that our synthesis approach for function pointers enables dynamic polymorphism.

In this paper we present a set of techniques that enable the synthesis of efficient custom accelerators for memory intensive, irregular applications. To address the challenges of irregular applications (large memory footprint, unpredictable fine-grained data accesses, and high synchronization intensity), and exploit their opportunities (thread level parallelism, memory level parallelism), we propose a novel accelerator design that employs an adaptive and Distributed Controller (DC) architecture, and a Memory Interface Controller (MIC) that supports concurrent and atomic memory operations on a multi-ported/multi-banked shared memory. Among the multitude of algorithms that may benefit from our solution, we focus on the acceleration of graph analytics applications and, in particular, on the synthesis of SPARQL queries on Resource Description Framework (RDF) databases. We achieve this objective by incorporating the synthesis techniques into Bambu, an Open Source high-level synthesis tools, and interfacing it with GEMS, the Graph database Engine for Multithreaded Systems. The GEMS' front-end generates optimized C implementations of the input queries, modeled as graph pattern matching algorithms, which are then automatically synthesized by Bambu. We validate our approach by synthesizing several SPARQL queries from the Lehigh University Benchmark (LUBM).

Code motion and speculations are usually exploited in the High Level Synthesis of control dominated applications to improve the performances of the synthesized designs. Selecting the transformations to be applied is not a trivial task: their effects can indeed indirectly spread across the whole design, potentially worsening the quality of the results. In this paper we propose a code transformation flow, based on a new extension of the System of Difference Constraints (SDC) scheduling algorithm, which introduces a large number of transformations, whose profitability is guaranteed by SDC formulation. Experimental results show that the proposed technique in average reduces the execution time of control dominated applications by 37% with respect to a commercial tool without increasing the area usage.

In this paper we present an approach for debugging hardware designs generated by High-Level Synthesis (HLS), relieving users from the burden of identifying the signals to trace and from the error-prone task of manually checking the traces. The necessary steps are performed after HLS, independently of it and without affecting the synthesized design. For this reason our methodology should be easily adaptable to any HLS tools. The proposed approach makes full use of HLS compile time informations. The executions of the simulated design and the original C program can be compared, checking if there are discrepancies between values of C variables and signals in the design. The detection is completely automated, that is, it does not need any input but the program itself and the user does not have to know anything about the overall compilation process. The design can be validated on a given set of test cases and the discrepancies are detected by the tool. Relationships between the original high-level source code and the generated HDL are kept by the compiler and shown to the user. The granularity of such discrepancy analysis is per-operation and it includes the temporary variables inserted by the compiler. As a consequence the design can be debugged as is, with no restrictions on optimizations available during HLS. We show how this methodology can be used to identify different kind of bugs: 1) introduced by the HLS tool used for the synthesis; 2) introduced using buggy libraries of hardware components for HLS; 3) undefined behavior bugs in the original high-level source code.

Data mining, bioinformatics, knowledge discovery, social network analysis, are emerging irregular applications that exploits data structures based on pointers or linked lists, such as graphs, unbalanced trees or unstructured grids. These applications are characterized by unpredictable memory accesses and generally are memory bandwidth bound, but also presents large amounts of inherent dynamic parallelism because they can potentially spawn concurrent activities for each one of the element they are exploring. Hybrid architectures, which integrate general purpose processors with reconfigurable devices, appears promising target platforms for accelerating irregular applications. These systems often connect to distributed and multi-ported memories, potentially enabling parallel memory operations. However, these memory architectures introduce several challenges, such as the necessity to manage concurrency and synchronization to avoid structural conflicts on shared memory locations and to guarantee consistency. In this paper we present an adaptive Memory Interface Controller (MIC) that addresses these issues. The MIC is a general and customizable solution that can target several different memory structures, and is suitable for High Level Synthesis frameworks. It implements a dynamic arbitration scheme, which avoids conflicts on memory resources at runtime, and supports atomic memory operations, commonly exploited for synchronization directives in parallel programming paradigms. The MIC simultaneously maps multiple accesses to different memory ports, allowing fine grained parallelism exploitation and ensuring correctness also in the presence of irregular and statically unpredictable memory access patterns. We evaluated the effectiveness of our approach on a typical irregular kernel, graph Breadth First Search (BFS), exploring different design alternatives.

Presents a conference poster that addresses high-level synthesis of memory bound and irregular parallel applications.

Classical techniques for register allocation and binding require the definition of the program execution order, since a partial ordering relation between operations must be induced to perform liveness analysis through data-flow equations. In High Level Synthesis (HLS) flows this is commonly obtained through the scheduling task. However for some HLS approaches, such a relation can be difficult to be computed, or not statically computable at all, and adopting conventional register binding techniques, even when feasible, cannot guarantee maximum performances. To overcome these issues we introduce a novel scheduling-independent liveness analysis methodology, suitable for dynamic scheduling architectures. Such liveness analysis is exploited in register binding using standard graph coloring techniques, and unlike other approaches it avoids the insertion of structural dependencies, introduced to prevent run-time resource conflicts in dynamic scheduling environments. The absence of additional dependencies avoids performance degradation and makes parallelism exploitation independent from the register binding task, while on average not impacting on area, as shown through the experimental results.

This paper presents bambu, a modular framework for research on high-level synthesis currently under development at Politecnico di Milano. It can accept most of C constructs without requiring any three-state for their implementations by exploiting a novel and efficient memory architecture. It also allows the integration of floating-point units and thus it can deal with a wide range of data types. Finally, it allows to easily customize the synthesis flow (e.g., transformation passes, constraints, options, synthesis scripts) through an XML file and it automatically generates test-benches and validates the results against the corresponding software execution, supporting both ASIC and FPGA technologies.

High Level Synthesis (HLS) provides a way to significantly enhance the productivity of embedded system designers, by enabling the automatic or semiautomatic generation of hardware accelerators starting from high level descriptions with (usually software) programming languages. Typical HLS approaches build a centralized Finite State Machine (FSM) to control the generated datapath, performing the operations according to a pre-determined, static schedule. However, FSM-based approaches are only able to extract parallelism within a single execution flow. In the presence of coarse grained parallelism, in the form of concurrent function calls or parallel control structures, they either serialize all the operations, or build excessively complex controllers, aiming at executing as many operation as possible in a single control step (i.e., they try to extract as much instruction level parallelism as possible). The resulting controllers occupy an excessive amount of area or lead to very low operating frequencies. In this paper we propose a methodology for the HLS of accelerators supporting parallel execution and dynamic scheduling. The approach exploits an adaptive distributed controller, composed of a set of communicating elements associated with each operation. This controller design enables supporting multiple concurrent execution flows, thus increasing parallelism exploitation beyond instruction level parallelism. The approach also supports variable latency operations, such as memory accesses and speculative operations. We apply our methodology on a set of typical HLS benchmarks, and demonstrate valuable speed ups with limited area overheads with respect to conventional FSM-based flows.

Modern hardware cores necessarily have to deal with many sources of unknown or uncertain information. Components with variable latency and unpredictable behavior are becoming predominant in hardware designs. Conventional hardware cores underperform when dealing with unknown or uncertain information. Common High-Level Synthesis (HLS) approaches, which require to specify the complete behavior at design-time, present significant restrictions in supporting this kind of conditions. The literature proposes several dynamic scheduling techniques to improve the cores performance by handling inherent uncertainty of applications. However, they do not address other sources of unknown information. In this paper, we propose the dynamic Activating Conditions (AC)-scheduling: a methodology for the design automation of hardware cores which can dynamically adapt the instructions scheduling according to behaviors unknown at design-time. Neither assumptions about components latency nor worst case approach are required. Experimental results show significant performance increase, with limited area overhead, with respect to state-of-the-art approaches.

Modern embedded systems include hundreds of cores. Because of the difficulty in providing a fast, coherent memory architecture, these systems usually rely on noncoherent, non-uniform memory architectures with private memories for each core. However, programming these systems poses significant challenges. The developer must extract large amounts of parallelism, while orchestrating communication among cores to optimize application performance. These issues become even more significant with irregular applications, which present data sets difficult to partition, unpredictable memory accesses, unbalanced control flow and fine grained communication. Hand-optimizing every single aspect is hard and time-consuming, and it often does not lead to the expected performance. There is a growing gap between such complex and highly-parallel architectures and the high level languages used to describe the specification, which were designed for simpler systems and do not consider these new issues. In this paper we introduce YAPPA (Yet Another Parallel Programming Approach), a compilation framework for the automatic parallelization of irregular applications on modern MPSoCs based on LLVM. We start by considering an efficient parallel programming approach for irregular applications on distributed memory systems. We then propose a set of transformations that can reduce the development and optimization effort. The results of our initial prototype confirm the correctness of the proposed approach.

Since time constraints are a very critical aspect of an embedded system, performance evaluation can not be postponed to the end of the design flow, but it has to be introduced since its early stages. Estimation techniques based on mathematical models are usually preferred during this phase since they provide quite accurate estimation of the application performance in a fast way. However, the estimation error has to be considered during design space exploration to evaluate if a solution can be accepted (e.g., by discarding solutions whose estimated time is too close to constraint). Evaluate if the possible error can be significant analyzing a punctual estimation is not a trivial task. In this paper we propose a methodology, based on statistical analysis, that provides a prediction interval on the estimation and a confidence level on meeting a time constraint. This information can drive design space exploration reducing the number of solutions to be validated. The results show how the produced intervals effectively capture the estimation error introduced by a linear model.

Current EDA tools are often based on standard-cell libraries for the design of modern complex systems-on-chip. In general, there are opposite trends to compact and extend the standard cell libraries, and to move towards custom libraries, highly optimized for specific goals (e.g., area, timing or power consumption) or designs. We thus propose a design methodology for library sizing that combines decimation strategies and generation of cell variants. The proposed methodology is based on Simulated Annealing, also integrating heuristic principles to efficiently guide the exploration process. The approach has been validated on a set of common benchmarks for logic synthesis, demonstrating interesting results, specially when starting from a relative small initial library.

Efficient mapping and scheduling of partitioned applications are crucial to improve the performance on today's reconfigurable multiprocessor systems-on-chip (MPSoCs) platforms. Most of existing heuristics adopt the directed acyclic (task) Graph as representation, that unfortunately, is not able to represent typical embedded applications (e.g., real-time and loop-partitioned). In this paper we propose a novel approach, based on Ant Colony Optimization, that explores different alternative designs to determine an efficient hardware-software partitioning, to decide the task allocation and to establish the execution order of the tasks, dealing with different design constraints imposed by a reconfigurable heterogeneous MPSoC. Moreover, it can be applied to any parallel C application, represented through Hierarchical Task Graphs. We show that our methodology, addressing a realistic target architecture, outperforms existing approaches on a representative set of embedded applications.

Face Recognition techniques are solutions used to quickly screen a huge number of persons without being intrusive in open environments or to substitute id cards in companies or research institutes. There are several reasons that require to systems implementing these techniques to be reliable. This paper presents the design of a reliable face recognition system implemented on Field Programmable Gate Array (FPGA). The proposed implementation uses the concepts of multiprocessor architecture, parallel software and dynamic reconfiguration to satisfy the requirement of a reliable system. The target multiprocessor architecture is extended to support the dynamic reconfiguration of the processing unit to provide reliability to processors fault. The experimental results show that, due to the multiprocessor architecture, the parallel face recognition algorithm can achieve a speed up of 63% with respect to the sequential version. Results regarding the overhead in maintaining a reliable architecture are also shown.

In this paper, we apply multi-objective evolutionary computation to the synthesis of real-time, embedded, heterogeneous, multiprocessor systems (briefly, Multiprocessor Systems-on-Chip or MP-SoCs). Our approach simultaneously explores the architecture, the mapping and the scheduling of the system, by using multi-objective evolution. In particular, we considered three approaches: a multi-objective genetic algorithm, multi-objective Simulated Annealing, and multi-objective Tabu Search. The algorithms search for optimal architectures, in terms of processing elements (processors and hardware accelerators) and communication infrastructure, and for the best mappings and schedules of multi-rate real-time applications given objectives such as: system area, hard and soft dead-lines violations, dimensions of memory buffers. We formalize the problem, describe our flow and compare the three algorithms, dis- cussing which one performs better with respect to different classes of applications.

To exploit the power of modern heterogeneous multiprocessor embedded platforms on partitioned applications, the designer usually needs to efficiently map and schedule all the tasks and the communications of the application, respecting the constraints imposed by the target architecture. Since the problem is heavily constrained, common methods used to explore such design space usually fail, obtaining low-quality solutions. In this paper, we propose an ant colony optimization (ACO) heuristic that, given a model of the target architecture and the application, efficiently executes both scheduling and mapping to optimize the application performance. We compare our approach with several other heuristics, including simulated annealing, tabu search, and genetic algorithms, on the performance to reach the optimum value and on the potential to explore the design space. We show that our approach obtains better results than other heuristics by at least 16% on average, despite an overhead in execution time. Finally, we validate the approach by scheduling and mapping a JPEG encoder on a realistic target architecture.

Multiprocessors on a chip are the reality of these days. Semiconductor industry has recognized this approach as the most efficient in order to exploit chip resources, but the success of this paradigm heavily relies on the efficiency and widespread diffusion of parallel software. Among the many techniques to express the parallelism of applications, this paper focuses on pipelining, a technique well suited to data-intensive multimedia applications. We introduce a prototyping platform (FPGA-based) and a methodology for these applications. Our platform consists of a mix of standard and custom heterogeneous cores. We discuss several case studies, analyzing the interaction of the architecture and applications and we show that multimedia and telecommunication applications with unbalanced pipeline stages can be easily deployed. Our framework eases the development cycle and enables the developers to focus directly on the problems posed by the programming model in the direction of the implementation of a production system.

odern Field Programmable Gate Arrays (FPGA) can be programmed with multiple soft-core processors. These solutions can be used for MultiProcessor Systems-on-Chip (MPSoCs) prototyping or even for final implementation. Nevertheless, efficient synchronization is required to guarantee performance in multiprocessing environments with the simple cores that do not support atomic instructions and are normally used in the standard FPGA toolchains. In this paper, we introduce two hardware synchronization modules for Xilinx MicroBlaze systems, with local polling or queuing mechanisms for locks and barriers, and present a comparison of these solutions to alternative designs.

In this paper, we compare four algorithms for the mapping of pipelined applications on a heterogeneous multiprocessor platform implemented using Field Programmable Gate Arrays (FPGAs) with customizable processors. Initially, we describe the framework and the model of pipelined application we adopted. Then, we focus on the problem of mapping a set of pipelined applications onto a heterogeneous multiprocessor platform and consider four search algorithms: Tabu Search, Simulated Annealing, Genetic Algorithms, and the Bayesian Optimization Algorithm. We compare the performance of these four algorithms on a set of synthetic problems and on two real-world applications (the JPEG image encoding and the ADPCM sound encoding). Our results show that on our framework the Bayesian Optimization Algorithm outperforms all the other three methods for the mapping of pipelined applications.

This paper presents a multiprocessor architecture prototype on a field programmable gate arrays (FPGA) with support for hardware and software multithreading. Thanks to partial dynamic reconfiguration, this system can, at run time, spawn both software and hardware threads, sharing not only the general purpose soft-cores present in the architecture but also area on the FPGA. While on a standard single processor architecture the partial dynamic reconfiguration requires the processor to stop working to instantiate the hardware threads, the proposed solution hides most of the reconfiguration latency through the parallel execution of software threads. We validate our framework on a JPEG 2000 encoder, showing how threads are spawned, executed and joined independently of their hardware or software nature. We also show results confirming that, by using the proposed approach, we are able to hide the reconfiguration time.

The speed-up estimation of parallelized code is crucial to efficiently compare different parallelization techniques or task graph transformations. Unfortunately, most of the time, during the parallelization of a specification, the information that can be extracted by profiling the corresponding sequential code (e.g. the most executed paths) are not properly taken into account. In particular, correlating sequential path profiling with the corresponding parallelized code can help in the identification of code hot spots, opening new possibilities for automatic parallelization. For this reason, starting from a well-known profiling technique, the Efficient Path Profiling, we propose a methodology that estimates the speed-up of a parallelized specification, just using the corresponding hierarchical task graph representation and the information coming from the dynamic profiling of the initial sequential specification. Experimental results show that the proposed solution outperforms existing approaches.

This paper presents a multiprocessor system on FPGA that adopts Direct Memory Access (DMA) mechanisms to move data between the external memory and the local memory of each processor. The system integrates all standard DMA primitives via a fast Application Programming Interface (API) and relies on interrupts having also the possibility to manage a command list. This interface allows to program the embedded multiprocessor architecture on FPGA with simple DMAs using the same DMA techniques adopted on high performance multiprocessors with complex DMA controllers. Several experiments demonstrate the performance of our solution, allowing 57% improvement on the execution time of a selected set of benchmarks. We furthermore show how some DMA programming techniques (double and multi-buffering) can be effectively used within our platform, thus easing the design and development of the hardware and the software in a reconfigurable DMA-based environment.

The high-level synthesis process involves three interdependent and NP-complete optimization problems: (i) the operation scheduling, (ii) the resource allocation, and (iii) the controller synthesis. Evolutionary algorithms have been effectively applied to high level synthesis in presence conflicting design objectives for finding good tradeoffs in the design space. However, so far the design space exploration has been performed using single-objective evolutionary algorithms with an ad hoc fitness function to achieve the desired tradeoff between the objectives. Recently we proposed a framework based on multi-objective genetic algorithms to perform a fully automated design space exploration. In this paper we focus on the choice of the solution representations that can be used to perform the design space exploration with multi-objective genetic algorithms. In particular we consider two specific representations and compare them on a set of benchmark problems. Our results suggest that they have different biases on the search space that make them more effective in different problems and design subspaces. Accordingly, we present a preliminary investigation on a new representation that exploits the advantages of both of them.

This paper presents the implementation of a dual-priority scheduling algorithm for real-time embedded systems on a shared memory multiprocessor on FPGA. The dual-priority microkernel is supported by a multiprocessor interrupt controller to trigger periodic and aperiodic thread activation and manage context switching. We show how the dual-priority algorithm performs on a real system prototype compared to the theoretical performance simulations with a typical standard workload of automotive applications, underlining where the differences are.

Dynamic reconfiguration allows to selectively substitute blocks of logic at run-time in order to improve the area efficiency of a FPGA design. This paper presents the design of a JPEG Encoder which exploits this feature. We propose a mixed HW/SW architecture, where most compute-intensive components of the application are mapped to application-specific HW cores. These cores dynamically alternate on the FPGA. Our purpose is to describe a real-world application of reconfigurable computing, illustrating how this approach allows for saving area with negligible performance overhead. We built a fully-working prototype, which demonstrates that the reconfigurable JPEG encoder achieves 29.6% area saving, 1.5% performance loss, and negligible power overhead with respect to a solution which uses statically mapped HW cores.

The high-level synthesis process allows the automatic design and implementation of digital circuits starting from a behavioral description. Evolutionary algorithms are very widely adopted to approach this problem or just part of it. Nevertheless, some concerns regarding execution times exist. In evolutionary high-level synthesis, design solutions have to be evaluated to extract information about some figures of merit (such as performance, area, etc.) and to allow the genetic algorithm to evolve and converge to Pareto-optimal solutions. Since the execution time of such evaluations increases with the complexity of the specification, the overall methodology could lead to unacceptable execution time. This paper presents a model to exploit fitness inheritance in a multi-objective optimization algorithm (i.e. NSGA-II) by substituting the expensive real evaluations with estimations based on closeness in an hypothetical design space. The estimations are based on the measure of the distance between individuals and a weighted average of the fitnesses of the closest ones. The results shows that the Pareto-optimal set obtained by applying the proposed model well approximates the set obtained without fitness inheritance. Moreover, the overall execution time is reduced up to the 25% in average.

This paper presents a framework to design a shared memory multiprocessor on a programmable platform. We propose a complete flow, composed by a programming model and a template architecture. Our framework permits to write a parallel application by using a shared memory model. It deals with the consistency of shared data, with no need of hardware coherence protocol, but uses a software model to properlyallsynchronize the local copies with the shared memory image. This idea can be applied both to a scratchpad-based architecture or a cache-based one. The architecture is synthesizable with standard IPs, such as the softcores and interconnect elements, which may be found in any commercial FPGA toolset.

Recent research results have seen the application of parallelizing techniques to high-level synthesis. In particular, the effect of speculative code transformations on mixed control-data flow designs has demonstrated effective results on schedule lengths. In this paper we first analyze the use of the control and data dependence graph as an intermediate representation that provides the possibility of extracting the maximum parallelism. Then we analyze the scheduling problem by formulating an approach based on Integer Linear Programming (ILP) to minimize the number of control steps given the amount of resources. We improve the already proposed ILP scheduling approaches by introducing a new conditional resource sharing constraint which is then extended to the case of speculative computation. The ILP formulation has been solved by using a Branch and Cut framework which provides better results than standard branch and bound techniques.

This paper aims at introducing a methodology that allows an easy implementation of IP-Cores focusing only on their functionalities rather than their interfaces and their integration in a given architecture. The proposed approach implements all the communication infrastructure needed by a component, described in VHDL, to be finally inserted into a real architecture that can be implemented on FPGAs, reducing the time to market of the final implementation of the system. To validate the entire methodology, we have performed a comparison based on the CoreConnect communication infrastructure, between our results with the classical Xilinx design flow using EDK and ISE.

It is common nowadays to employ FPGAS, not only as a means of rapidly prototyping and testing dedicated solutions, but also as a platform on which to implement actual production systems. Although modern FPGAS allow the designer to modify dynamically even only portions of the chip, to this date there is a lack of satisfying design methodologies that using only non-proprietary widely available tools make it possible to optimally implement a high-level specification into a partially dynamically reconfigurable system. The aim of this work is to propose a methodology for solving this problem. The main features of the Caronte methodology are: 1. full exploitation of partial dynamic reconfiguration; 2. the reconfiguration is internal; 3. a real-time Unix-like operating system helps the management of complex systems with multiple tasks, and simplifies reconfiguration through an optimized device driver.

Embedded systems are composed of both dedicated elements (hardware components) and programmable units (software components), which have to interact with each other for accomplishing a specific task. One of the aims of hardware-software codesign is the choice of a partitioning between elements that will be implemented in hardware and elements that will be implemented in software is one of the important step in design. In this paper, we present an application of the learning classifier system XCS to the analysis of data derived from hardware-software codesign applications. The goal of the analysis is the discovering or explicitation of existing interelationships among system components, which can be used to support the human design of embedded systems. The proposed approach is validated on a specific task involving a digital sound spatializer.

In this paper, we present the results of a set of experiments we conducted in order to evaluate the viability of behavioral synthesis, relying on the tools available at the moment in the EDA market. To accomplish this we modelled a complex PCI bus interface in SystemC using a behavioral style of description. Then we tried to synthesize it by means of the Synopsis CoCentric SystemC compiler tool. The problems arisen during synthesis, in particular those concerned with the cycle-accurate timing behavior of the synthesized circuit, were addressed. After analyzing them, possible solutions were proposed, where possible. Finally, a summary of the pros and cons of the behavioral synthesis in SystemC is presented.

Verification of the functionality of VHDL specifications is one of the primary and most time consuming tasks of design. However, it must necessarily be an incomplete task because it is impossible to completely exercise the specification by exhaustively applying all input patterns. We present a two-step strategy based on symbolic analysis of the VHDL specification, using a behavioral error model. First, we generate a reduced number of functional test vectors for each process of the specification by using a new analysis metric which we call bit coverage. The error model based on this metric allows the identification of possible design errors represented by redundancies in the VHDL code. Then, through the definition of a controllability measure, we verify if these functional test vectors can be applied to the process inputs when it is interconnected to other processes. If this is not the case, the analysis of the nonapplicable inputs provides identification of possible design errors due to erroneous interconnections. The bit-coverage provides complete statement, condition and branch coverage; and we experimentally show that it allows the identification of possible design errors. Identification and removal of design errors improves the global testability of a design.

Summary form only given. The combined effects of devices increased complexity and reduced design cycle time creates a testing problem: an increasing larger portion of the design time is devoted to testing and verification. Today EDA tools, moving towards higher levels of abstraction, promise greater designer productivity, resulting in increased design complexity and size. In order to reduce the testing and verification time, different high-level approaches have been proposed in literature. Most of these approaches are based on the definition of an error or fault model, applicable at a higher level of abstraction of the description of the system to be implemented. In this paper we concentrate our attention on the evaluation of error models, used in test generation and in functional verification. Evaluation of error models is also an important aspect when fault injection methodologies are used to evaluate the dependability of complex system.

This paper addresses the problem of test vectors generation starting from an high level description of the system under test, specified in SystemC. The verification method considered is based upon the simulation of input sequences. The system model adopted is the classical Finite State Machine model. Then, according to different strategies, a set of sequences can be obtained, where a sequence is an ordered set of transitions. For each of these sequences, a set of constraints is extracted. Test sequences can be obtained by generating and solving the constraints, by using a constraint solver (GProlog). A solution of the constraint solver yields the values, of the input signals for which a sequence of transitions in the FSM is executed. If the constraints cannot be solved, it implies that the corresponding sequence cannot be executed by any test. The presented algorithm is not based on a specific fault model, but aims at reaching the highest possible path coverage.

Presents an analysis of the behavioral descriptions of embedded systems to generate behavioral test patterns that are used to perform the exploration of design alternatives based on testability. In this way, during the hardware/software partitioning of the embedded system, testability aspects can be considered. This paper presents an innovative error model for algorithmic (behavioral) descriptions, which allows for the generation of behavioral test patterns. They are converted into gate-level test sequences by using more-or-less accurate procedures based on scheduling information or both scheduling and allocation information. The paper shows, experimentally, that such converted gate-level test sequences provide a very high stuck-at fault coverage when applied to different gate-level implementations of the given behavioral specification. For this reason, our behavioral test patterns can be used to explore testability alternatives, by simply performing fault simulation at the gate level with the same set of patterns, without regenerating them for each circuit. Furthermore, whenever gate-level ATPGs are applied on the synthesized gate-level circuits, they obtain lower fault coverage with respect to our behavioral test patterns, in particular when considering circuits with hard-to-detect faults.

Functional testing of HDL specifications is one of the most promising approaches for the verification of the functionalities of a design before synthesis. The contribution of this work is the development of a test generation algorithm targeting a new coverage metric (called bit-coverage) that provides full statement coverage, branch coverage, condition coverage and partial path coverage for behaviorally sequential models. The behavioral test sequences can be also the only way to evaluate testability of VHDL model for which a gate-level representation is not available (e.g third-party cores), since the behavioral error model is characterized also by a high correlation with the RT and gate-level stuck-at fault model. Moreover the preciseness of the proposed coverage metric makes the identified test sequences more effective in identifying design errors, than other test patterns developed by following standard coverage metrics.

A high-level synthesis strategy is proposed for design of semiconcurrently self-checking devices. Attention is mainly focused on data path design. After identifying the reference architecture against which cost and performance are evaluated, a simultaneous scheduling-and-allocation strategy is presented for linear-code data flow graphs, allowing resource sharing between nominal and checking data paths. The proposed strategy is actually independent from a specific scheduling-and-allocation algorithm since it is essentially concerned with the introduction of the fault tolerance issue at high-abstraction level in any design environment. Conventional duplication with comparison, even if considered in a high-level synthesis strategy, leads to high circuit complexity increase. The proposed approach provides that the required checking periodicity is satisfied while minimizing additional functional units by means of maximum reuse of the resources available for the nominal computation as long as error detection ability is preserved. The strategy is then extended to deal with branches and loops in the data path. Risk of error aliasing due to resource sharing is analyzed.

The paper presents a new approach to solve the unate covering problem based on exploitation of information provided by Lagrangean relaxation. In particular, main advantages of the proposed heuristic algorithm are the effective choice of elements to be included in the solution, cost-related reductions of the problem, and a good lower bound on the optimum. The results support the effectiveness of this approach: on a wide set of benchmark problems, the algorithm nearly always hits the optimum and in most cases proves it to be such. On the problems whose optimum is actually unknown, the best known result is strongly improved.

The classical solving approach for two-level logic minimisation reduces the problem to a special case of unate covering and attacks the latter with a (possibly limited) branch-and-bound algorithm. We adopt this approach, but we propose a constructive heuristic algorithm that combines the use of Binary Decision Diagrams (BDDs) with the Lagrangian relaxation. This technique permits us to achieve an effective choice of the elements to include in the solution, as well as cost-related reductions of the problem and a good lower bound on the optimum. The results support the effectiveness of this approach: on a wide set of benchmark problems, the algorithm nearly always hits the optimum, and in most cases proves it to be so. On the problems whose optimum is actually unknown, the best known result is strongly improved.

This paper describes a functional level rest pattern generator, which combines two techniques: genetic algorithms (GAs) and binary decision diagrams (BDDs). The combined execution of such two techniques achieves better results for functional testing, than the single application of each separated technique. The entire set of functional errors is examined in a shorter time and a more compact test set is produced. The reason of this interesting result has been analyzed in the paper. It mainly depends on the fact that hard to detect errors for GA-based testing techniques are easy to detect than errors for BDD-based techniques and vice versa. The two testing approaches are thus complementary and can effectively cooperate.

The aim of this paper is to show the effectiveness of a high-level approach to testability analysis and test pattern generation, when analyzing different classes of architectures implementing the same specification. A unique test set is derived on the behavioral specification, based on a functional error model, which shows a high correlation with the single stuck-at-gate-level fault model. Such a test set is then tailored to the particular gate-level implementation by transforming it into a specific test sequence, based on the scheduling adopted by the high-level synthesis. Experimental results show that the application of such test sequences allows one to accurately evaluate the testability of the architecture in terms of gate-level fault coverage, in a fraction of the time required by a gate-level test pattern generator.

This paper presents a binary decision diagram (BDD)-based algorithm for the optimization of the driven machine, M/sub 2/, of a finite-state machine (FSM) network with cascade connection, M/sub 1//spl rarr/M/sub 2/. The technique we propose relies on redundant faults identification and removal. A fault, f, located into machine M/sub 2/, is redundant with respect to the overall network if the driving machine M/sub 1/ is not able to generate any test sequence for such a fault. When the state transition graph (STG) specifications of the network components are available, the standard way for checking the redundancy condition for the considered fault requires one to first construct the product machine M/sub 2//spl times/M/sub 2//sup F/, where M/sub 2//sup F/ is the faulty FSM, then to connect it to the driving machine, and finally to perform reachability analysis on the composed machine M/sub 1//spl rarr/M/sub 2//spl times/M/sub 2//sup F/. Clearly, the size of such machine limits the applicability of the approach above to systems whose components have a few tens of states at most, even when symbolic traversal algorithms are used. Since we are interested in dealing with networks of larger FSM's (i.e., machines whose STGs can not be represented explicitly), we propose to use the product automaton P'=A/sub 1//spl times/A/sub f/, where A/sub 1/' is the finite automaton (FA) accepting all the output sequences of M/sub 1/, and A/sub f/ is the FA accepting all the test sequences for fault f, instead of machine M/sub 1//spl rarr/M/sub 2//spl times/M/sub 2//sup F/. This simplifies sensibly the task of the reachability analysis program, since A/sub f/ has considerably less states and less edges than the product machine M/sub 2//spl times/M/sub 2//sup F/ and, thus, the size of the BDD representation of its transition relation is much more easily manageable. In addition, differently from other approaches, automaton A/sub 1/' is not required to be deterministic and state minimal. This allows us to avoid the application of determinization and state minimization procedures whose complexity is exponential. We present experimental results For examples (i.e., network of interacting controllers) on which existing optimization methods are not applicable, due to the size of the component FSM's. We also provide a comparison to the data produced by state-of-the-art FSM network optimizers on small benchmarks in order to show the effectiveness of our approach.

Verification of the functional correctness of VHDL specifications is one of the primary and most time consuming tasks of design. However, it must necessarily be an incomplete task since it is impossible to completely exercise the specification by exhaustively applying all input patterns. The paper aims at presenting a two-step strategy based on symbolic analysis of the VHDL specification, using a behavioral fault model. First, we generate a reduced number of functional test vectors for each process of the specification which allows complete code statement coverage and bit coverage, allowing the identification of possible redundancies in the VHDL process. Then, through the definition of a controllability measure, we verify if these functional test vectors can be applied to the process inputs when interconnected to other processes. If this is not the case, the analysis of the nonapplicable inputs provides identification of possible code redundancies and design errors. Experimental results show that bit coverage provides complete statement coverage and a more detailed identification of possible design errors.

This paper presents a methodology for power estimation of designs described at the behavioral-level as the interconnection of functional modules. The input/output behavior of each module is implicitly stored using BDDs, and the power consumed by the network is estimated using a novel and accurate entropy-based approach. As a demonstration example, we have used the proposed power estimation technique to evaluate and compare the effects of some architectural transformations applied to a reference design specification on the power dissipation of the corresponding implementations.

Testability analysis of VHDL sequential models is the main topic of this paper. We investigate the possibility to obtain information about the testability of a sequential VHDL description before its actual synthesis. The analysis is based on an implicit fault model that injects faults into a BDD based description extracted from the VHDL representation. Such an injection is related to the original VHDL representation thus allowing the identification of potential testability problems before RTL and logic synthesis. Fault injection is performed efficiently by exploiting the concept of fault clustering, that is the possibility of grouping faults and analyzing them concurrently. The proposed methodology is applied to benchmarks for efficiency evaluation and to a real VHDL description.

This paper presents a nouel methodology for synthesizing PTL circuifg, whose disfincfiue feafures are the use of a symbolic algorifhm for the covem.ng of fhe initial network in ferms of PTL cells, and the eqloifation of layout-level ama and delay models dun.ng fhe selection of fhe be~t couem.ngsolufion.The results produced by the synthesis procedure on the full guite of fhe kcas'85 combinational circuifs are very encouraging.

A methodology for modifying VHDL descriptions is the core of this paper. Modifications are performed on general RTL descriptions composed of a mix of control and computation, that is, the typical type of description used for designing at the RT level. Such VHDL descriptions are automatically partitioned into a reference model composed of a controller driving a data-path. We call this transformation "VHDL restructuring". A set of restructuring steps is presented aiming at partitioning any VHDL description while guaranteeing the semantic equivalence of the restructured description with the original one. The main motivation to restructuring is the identification and separation of the two parts (FSM+data-path) which can thus be analyzed by using "ad hoc" synthesis, testability and design for testability algorithms. Promising results show that restructuring can sensibly impact on synthesis and testability.

This paper proposes a behavioral-level test pattern generation algorithm for behavioral VHDL descriptions. The proposed approach is based on the comparison between the implicit description of the fault-free behavior and the faulty behavior, obtained through a new behavioral fault model. The paper will experimentally show that the test patterns generated at the behavioral level provide a very high stuck-at fault coverage when applied to different gate-level implementations of the given VHDL behavioral specification. Gate-level ATPGs applied on these same circuits obtain lower fault coverage, in particular when considering circuits with hard to detect faults.

The industrial interest in the application of formal methods in the design of complex ASICs is noteworthy to improve the efficiency of the design process (reduced time-to-market) and to increase the quality of the final products (increased competitive profile). In this paper we focus our attention on design capture and functional verification, two critical phases in the current design methodologies. A modular toolset built around a model checker is described. A telecom co-processor is presented, and general properties derived. A user-oriented taxonomy of properties is introduced to support the design practice. Guidelines for the application of this technique are inferred from the example and generalized.

By considering test costs at the behavioral level, test problems can be pointed out during the first phases of the design flow. Thus, in case either some testability problems are identified or the size (and hence the cost) of the test set results to be too high, the designer or the high level synthesis tool can modify the circuit to reduce such testability problems. The main problem is the correspondence between the behavioral and RT or gate level fault models. To overcome such limitation, the paper presents a design flow based on the behavioral fault model modification ("evolution") depending on the actual RTL implementation.

The test problem increasingly affects the system design process and related costs and time to market. Requirements from VLSI/WSI manufacturers are for fast and reliable testability tools, with the possibility of their introduction in early phases of design. The paper presents a global toolset architecture for testability analysis and test pattern generation. Three abstraction levels are considered in this design flow, from the behavioral specifications, through RTL descriptions, down to gate level. In all these phases, VHDL is chosen as the referring description language. The paper then presents an application scenario, detailing the results achieved by the proposed methodology.

This paper presents a novel optimization algorithm for FSM networks that relies on sequential test generation and redundancy removal. The implementation of the proposed approach, which is based on the exploitation of input don't care sequences through regular language intersection, is fully symbolic. Experimental results, obtained on a large set of standard benchmarks, improve over the ones of state-of-the-art methods.

This paper presents a new testing strategy for networks of interacting FSMs. The approach allows us to generate test patterns for faults in the network by separately handling the network's components. The proposed algorithms are fully symbolic; therefore, they allow the manipulation of large designs. Experimental results, though preliminary, are promising.

Test pattern storage is an important problem affecting all Design for Testability (DfT) techniques based on scan-path. Test compaction is the key idea to reduce this problem, but in case of partial-scan test compaction would concern the concatenation and overlapping of test sequences instead of test vectors. Unfortunately, standard sequential TPGs do not show sufficient capabilities in test sequences compaction. Thus, the paper presents an innovative compaction strategy for test sequences based on implicit techniques. Preliminary results show that the use of the presented technique can sensibly reduce the amount of test patterns which mast be stored and applied.

In order to cope with tomorrow's challenges in the microelectronic market, the reliability of the first phases of the design process must be improved. The possibility of applying techniques for testability analysis at these abstract design levels can considerably help in achieving this goal, reducing at the same time system design costs. In this paper we introduce a novel approach for the application of functional testability at system design level and demonstrate the possibility of its application in an industrial environment. Testability conditions referring to both regular and irregular topologies have been defined, formalized and inserted into the knowledge base of the expert system, ALADIN. This tool operates as a testability analyzer able to identify critical areas for testability in designs whose functional modules and local interconnections are known and described in standard VHDL. The architecture of the tool has been defined in order to satisfy the users' requirements including the integrability into a standard CAD design flow through standard I/O interfaces. Then its application to both a regular and an irregular topology are presented in order to show on real examples which testability conditions apply, and how the tool operates in order to reach the testability assessment. From these industrial case studies, figures of merit are derived from which it is possible to evaluate the importance of the application of such a methodology to system level design.>