Software applications use dynamic memory (allocated and deallocated in the system's heap) to handle dynamism in their working conditions. Embedded systems tend to include complex memory organizations but most techniques for dynamic memory management do not deal with the placement of data objects in physical memory modules. Additionally, the performance of hardware-controlled cache memories may be severely hindered when used with linked data structures. We therefore present a methodology to map dynamic data on the multilevel memory subsystem of embedded systems, taking advantage of any available memories (e.g., on-chip SRAMs) and avoiding interference with the cache memories. The resulting data placement uses an exclusive memory model and is compatible with existing techniques for managing static data. Our methodology helps the designer achieve reductions in energy consumption and execution time that can be obtained by an expert in an automated way while keeping control over the process through multiple configuration knobs.

Multispeculative Functional Units (MSFUs) are arithmetic functional units that operate using several predictors for the carry signal. The carry prediction helps to shorten the critical path of the functional unit. The average performance of these units is determined by the hit rate of the prediction. In spite of utilizing more than one predictor, none or only one additional cycle is enough for producing the correct result in the majority of the cases. In this paper we present multispeculation as a way of increasing the performance of tree structures with a negligible area penalty. By judiciously introducing these structures into computation trees, it will only be necessary to predict in certain selected nodes, thus minimizing the number of operations that can potentially mispredict. Hence, the average latency will be diminished and thus performance will be increased. Our experiments show that it is possible to improve on average 24% and 38% execution time, when considering logarithmic and linear modules, respectively.

Addition is the key arithmetic operation in most digital circuits and processors. Therefore, their performance and other parameters, such as area and power consumption, are highly dependent on the adders' features. In this paper, we present multispeculation as a way of increasing adders' performance with a low area penalty. In our proposed design, dividing an adder into several fragments and predicting the carry-in of each fragment enables computing every addition in two very short cycles at the most, with 99% or higher probability. Furthermore, based on multispeculation principles, we propose a new strategy for implementing addition chains and hiding most of the penalty cycles due to mispredictions, while keeping at the same time the resource sharing capabilities that are sought in high-level synthesis. Our results show that it is possible to build linear and logarithmic adders more than$4.7\times$and$1.7\times$faster than the nonspeculative case, respectively. Moreover, this is achieved with a low area penalty (38% for linear adders) or even an area reduction (${-}8\%$for logarithmic adders). Finally, applying multispeculation principles to signal processing benchmarks that use addition chains will result in 25% execution time reduction, with an additional 3% decrease in datapath area with respect to implementations with logarithmic fast adders.

Heterogenous datapaths maximize the utilization of functional units (FUs) by customizing their widths individually through fragmentation of wide operands. In comparison, slices in large functional units in a homogenous datapath could be spending many cycles not performing actual useful work. Various fragmentation techniques demonstrated benefits in minimizing the total functional unit area. Upon a closer look at fragmentation techniques, we observe that the area savings achieved by heterogenous datapaths can be traded-off for power optimization. Our specific approach is to introduce choices for functional units with power/area trade-offs for different fragmentation and allocation choices, for reducing power consumption while satisfying the area constraint imposed on the heterogenous datapath. As low power FUs in literature produce an area penalty, a methodology must be developed in order to introduce them in the HLS flow while complying with the area constraint. We propose an allocation and module selection algorithms that pursue a trade-off between area and power consumption for fragmented datapaths under a total area constraint. Results show that it is possible to reduce power by 37% on average (49% in the best case). Moreover latency and cycle time will be equal or nearly the same as in the baseline case, which will lead to an energy reduction, too.

Speculative functional units (SFUs) are arithmetic functional units that operate using a predictor for the carry signal. The carry prediction helps to shorten the critical path of the functional unit. The average case performance of these units is determined by the hit rate of the prediction. In case of mispredictions, the SFUs need to be coordinated by the datapath control mechanism to perform corrections and to maintain the datapath in the correct state. Devising a control mechanism for correcting mispredictions without adversely impacting overall performance is the most important challenge. In this paper, we present techniques for designing a datapath controller for seamless deployment of SFUs in high level synthesis. We have developed two techniques based on two main control paradigms: centralized and distributed control. The centralized approach stops the execution of the entire datapath for each misprediction and resumes execution once the correct value of the carry is known. The distributed approach decouples the functional unit suffering from the misprediction from the rest of the datapath. Hence, it allows the remainder of the functional units to carry on execution and be at different scheduling states at different times. We tested datapaths utilizing both linear structures and logarithmic structures for speculative arithmetic functional units. Our results show that it is possible to reduce execution time by as much as 38% (33% on average) for linear structures and by as much as 37.2% (25% on average) for logarithmic structures.

Speculative Functional Units (SFUs) enable a new execution paradigm for High Level Synthesis (HLS). SFUs are arithmetic functional units that operate using a predictor for the carry signal, which reduces the critical path delay. The performance of these units is determined by the success in the prediction of the carry value, i.e. the hit rate of the prediction. Hence SFUs reduce critical path at a low cost, but they cannot be used in HLS with the current techniques. In order to use them, it is necessary to include hardware support to recover from mispredictions of the carry signals. In this paper, we present techniques for designing a datapath controller for seamless deployment of SFUs in HLS. We have developed two techniques for this goal. The first approach stops the execution of the entire datapath for each misprediction and resumes execution once the correct value of the carry is known. The second approach decouples the functional unit suffering from the misprediction from the rest of the datapath. Hence, it allows the rest of the SFUs to carry on execution and be at different scheduling states at different times. Experiments show that it is possible to reduce execution time by as much as 38% and by 33% on average.

The information about the run-time behavior of software applications is crucial for enabling system level optimizations for embedded systems. This embedded Software Metadata information is especially important today, because several complex multi-threaded applications are mapped on the memory of a single embedded system. Each thread is triggered at run-time by different input events that can not be predicted at design-time. New methods and tools are needed to automatically profile and analyze the dynamic data access behavior of simultaneously executing threads in order to enable memory data transfer optimizations. In this paper, we propose such a method and tool which extract the necessary Software Metadata information to enable these data transfer optimizations at the system level. We assess the effectiveness of our approach with the results for five real-life software applications using seven real-life run-time input traces.

A complete power-aware high-level synthesis algorithm is presented. It performs the schedule, resource allocation and binding of behavioral specifications. It overcomes the limitations of low-power algorithms and based on a bit-level timing model and a study of the target technology, tries to chain in the same cycle as many operations as possible. It also fragments the functional units, not the operations, for diminishing the required hardware. We also keep a minimum performance by estimating the cycle time while we are chaining operations. This way we obtain a reduction for both the static power and the dynamic one. We achieve an additional dynamic power reduction by studying the Hamming distance and applying partial or total commutative property. Experimental results on real circuits show great improvements in both power and energy consumption and performance over conventional low power algorithms.

This paper justifies the use of estimation and prediction of carries to increase the performance of functional units built with the replication of full adders while keeping a low area penalization. Adders and multipliers are the most representative modules in this group of functional units. The use of these design techniques allows the implementation of modules with performance improvements ranging from 20% to 50% with only an area overheads around 5%. These functional units are suitable for asynchronous circuits but they could also be introduced in synchronous circuits with speculative techniques. The basic idea consists in estimating the carry out from some parts of the functional units, allowing every part to operate independently and in parallel. These modules are connected to build bigger ones. Results from simulations show that for some applications it is possible to make predictions even more accurate that the bit-based estimation. Predictions have also the advantage they can be introduced in the multipliers design, whether estimators cannot. These predictions are similar to the ones used in the branch prediction in a processor.

Conventional high-level synthesis algorithms usually employ multi-cycle operators to reduce the cycle length in order to improve the circuit performance. These operators need several cycles to execute one operation, but the entire functional unit is not used in any cycle. Additionally, the execution of operations over wider multi-cycle operators is unfeasible if their results must be available in a smaller number of cycles than the functional unit delay. This obliges to add new functional resources to the datapath even if multi-cycle operators are idle when the execution of the operation begins. In this paper a new design technique to overcome the restricted reusability of multi-cycle operators is presented. It reduces the area of these functional units allowing their internal reuse when executing one operation. It also expands the possibilities of common hardware sharing as it allows the partial use of multicycle operators to calculate narrower operations faster than the functional unit delay. This technique is applied as an optimization phase at the end of the high-level synthesis process, and can optimize the circuits synthesized by any high-level synthesis tool

Multi-Processor System-On-Chip (MPSoC) can provide the performance levels required by high-end embedded applications. However, they do so at the price of an increasing power density, which may lead to thermal runaway if coupled with low-cost packaging and cooling. Hence, mechanisms to efficiently evaluate the effectiveness of advanced thermal-aware operating-system (OS) strategies (e.g. task migration) onto the available MPSoC hardware are needed. In this paper, we propose a new MPSoC OS emulation framework that enables the study of thermal management strategies at the architectural- and OS-levels with the help of a standard FPGA. This framework includes the hardware and software components needed to accurately model complex MPSoCs architectures, and to test the effects of run-time thermal management strategies at the OS/middleware level with real-life inputs. Our results show that migration overhead is negligible w.r.t. temperature timings, enabling the development of thermal-aware migration strategies. Moreover, the effectiveness of the monitoring and feedback mechanism provides an emulation performance only ten times slower than real time.

Conventional high-level synthesis (HLS) algorithms are very conservative when dealing with read-after-write (RAW) dependences, the execution of one operation is allowed once all its predecessors have been calculated. However, in the execution of arithmetic operations, some bits are required later than others, and some bits are produced earlier than others. This paper proposes a presynthesis optimization algorithm that relaxes RAW dependences, taking advantage of this feature for a more efficient HLS of data flow graphs formed by additions, multiplications, and logic operations. The presented preprocessor analyzes the critical path at bit granularity and splits the arithmetic operations into subword fragments. These fragments become the input to any regular HLS tool to speed up circuit execution times through scheduling in different cycles of the fragments obtained from the same original operation. This way, the execution of one operation may begin before the calculus of its predecessors has been completed. This becomes feasible when the execution of the predecessor has begun in the selected cycle or in a previous one, and even if it will finish in a posterior cycle. The experimental results that were carried out show that implementations obtained from the optimized specification are, on the average, 70% faster, with only slight variations in the data path area.

New tendencies envisage multiprocessor systems-on-chips (MPSoCs) as a promising solution for the consumer electronics market. MPSoCs are complex to design, as they must execute multiple applications (games, video) while meeting additional design constraints (energy consumption, time-to-market). Moreover, the rise of temperature in the die for MPSoCs can seriously affect their final performance and reliability. In this article, we present a new hardware-software emulation framework that allows designers a complete exploration of the thermal behavior of final MPSoC designs early in the design flow. The proposed framework uses FPGA emulation as the key element to model hardware components of the considered MPSoC platform at multimegahertz speeds. It automatically extracts detailed system statistics that are used as input to our software thermal library running in a host computer. This library calculates at runtime the temperature of on-chip components, based on the collected statistics from the emulated system and final floorplan of the MPSoC. This enables fast testing of various thermal management techniques. Our results show speedups of three orders of magnitude compared to cycle-accurate MPSoC simulators.

With the growing complexity in consumer embedded products and the improvements in process technology, Multi-Processor System-On-Chip (MPSoC) architectures have become widespread. These new systems are complex to design as they must execute multiple complex applications (e.g. video processing, 3D games), while meeting additional design constraints (e.g. energy consumption or time-to-market). Moreover, the rise of temperature in the die for MPSoC components can seriously affect their final performance and reliability. Therefore, mechanisms to efficiently evaluate complete HW/SW MPSoC designs in terms of energy consumption, temperature, performance and other key metrics are needed. In this paper, we present a new HW/SW FPGA-based emulation framework that allows designers to rapidly extract a number of critical statistics from processing cores, memories and interconnection systems being emulated on a FPGA. This information is then used to interact in real-time with a SW thermal model running on a host computer via an Ethernet port. The results show speed-ups of three orders of magnitude compared to cycle-accurate MPSoC simulators, which enable a very fast exploration of a large range of MPSoC design alternatives at the cycle-accurate level. Finally, our HW/SW framework allows designers to test run-time thermal management strategies with real-life inputs without any loss in the performance of the emulated system.

New applications in embedded systems are becoming increasingly dynamic. In addition to increased dynamism, they have massive data storage needs. Therefore, they rely heavily on dynamic, run-time memory allocation. The design and configuration of a dynamic memory allocation subsystem requires a big design effort, without always achieving the desired results. In this paper, we propose a fully automated exploration of dynamic memory allocation configurations. These configurations are fine tuned to the specific needs of applications with the use of a number of parameters. We assess the effectiveness of the proposed approach in two representative real-life case studies of the multimedia and wireless network domains and show up to 76% decrease in memory accesses and 66% decrease in memory footprint within the Pareto-optimal trade-off space

Conventional high-level synthesis uses the worst case delay to relate all inputs to all outputs of an operation. This is a very conservative approximation of reality, especially in arithmetic operations (where some bits are required later than others and some bits are produced earlier than others). This paper proposes a pre-synthesis optimization algorithm that takes advantage of this feature for more efficient high-level synthesis of data-flow graphs formed by additions and multiplications. The presented pre-processor analyzes the critical path at bit-granularity and splits the arithmetic operations into sub-words fragments. In particular, some of the specification multiplications are broken up into several smaller multiplications, additions, and other operations of three new types specially defined to reduce the clock cycle duration. These fragments become the input to any regular high-level synthesis tool to speed up circuit execution times. The experimental results carried out show that implementations obtained from the optimized specification are on average 70% faster and in most cases substantial area reductions are also achieved

There is a clear trend of future embedded systems in moving toward wireless, multimedia, multi-functional and ubiquitous applications. This emerges new challenges in the existing solutions on performance, power, flexibility and costs, calling for innovations in both architecture and design methodology. In this paper, we propose a design flow consisting of three stages to handle dynamic data, allowing the designer to create highly customized dynamic memory managers, make them bank-aware and create a design-time schedule of the different tasks of the application. We evaluated the proposed flow using the visual texture coding (VTC) application, mapping it on a dual processor embedded platform achieving 5.5% reduction in memory footprint and 10% gains in execution time.

With the growing complexity in consumer embedded products and the improvements in process technology, multiprocessor system-on-chip (MPSoC) architectures have become widespread. These new systems are very complex to design as they must execute multiple complex real-time applications (e.g. video processing, or videogames), while meeting several additional design constraints (e.g. energy consumption or time-to-market). Therefore, mechanisms to efficiently explore the different possible HW-SW design interactions in complete MPSoC systems are in great need. In this paper, we present a new FPGA-based emulation framework that allows designers to rapidly explore a large range of MPSoC design alternatives at the cycle-accurate level. Our results show that the proposed framework is able to extract a number of critical statistics from processing cores, memory and interconnection systems, with a speed-up of three orders of magnitude compared to cycle-accurate MPSoC simulators

Conventional scheduling algorithms try to balance the number of operations of every different type executed per cycle. However, in most cases, a uniform distribution is not reachable, and thus, some hardware (HW) waste appears. This situation becomes worse when heterogeneous specifications (those formed by operations with different data formats and widths) are synthesized. Our proposal is an innovative bit-level algorithm able to minimize this HW waste. In order to obtain uniform distributions of the computational cost of operations among cycles, it successively transforms specification operations into sets of smaller ones, which are then scheduled independently. As a consequence, some specification operations may be executed during a set of nonconsecutive cycles, and over several functional units. In combination with allocation algorithms able to guarantee the bit-level reuse of HW resources, our approach produces circuits with substantially smaller area than conventional implementations. Due to the fragmentation of operations, in the proposed implementations, the type, number, and width of HW resources are, in general, independent of the type, number, and width of both specification operations and variables. Additionally, the clock-cycle length is also reduced in most circuits.

New portable consumer embedded devices must execute multimedia and wireless network applications that demand extensive memory footprint. Moreover, they must heavily rely on Dynamic Memory (DM) due to the unpredictability of the input data (e.g., 3D streams features) and system behavior (e.g., number of applications running concurrently defined by the user). Within this context, consistent design methodologies that can tackle efficiently the complex DM behavior of these multimedia and network applications are in great need. In this article, we present a new methodology that allows to design custom DM management mechanisms with a reduced memory footprint for such kind of dynamic applications. First, our methodology describes the large design space of DM management decisions for multimedia and wireless network applications. Then, we propose a suitable way to traverse the aforementioned design space and construct custom DM managers that minimize the DM used by these highly dynamic applications. As a result, our methodology achieves improvements of memory footprint by 60% on average in real case studies over the current state-of-the-art DM managers used for these types of dynamic applications.

Conventional scheduling algorithms usually adjust the clock cycle duration to the execution time of the longest operations. This results in large slack times wasted in those cycles with faster operations. To reduce the wasted times multi-cycle and chaining techniques have been employed. The scheduling algorithm presented in this paper goes one step further. It breaks up some of the specification operations and schedule several data-dependent operation fragments in the same cycle. In consequence, some of the specification operations are executed during several cycles (non-necessarily consecutive ones), and in every execution cycle some result bits are calculated. Thus the execution of one operation may start even if its predecessors have not finished yet. In the experimental results carried out, the proposed algorithm improves circuit performance above 70% on average, with slight increments in the datapath area.

Current systems-on-chip (SoC) execute applications that demand extensive parallel processing. Networks-on-chip (NoC) provide a structured way of realizing interconnections on silicon, and obviate the limitations of bus-based solutions. NoC can have regular or ad hoc topologies, and functional validation is essential to assess their correctness and performance. In this paper, we present a flexible emulation environment implemented on an FPGA that is suitable to explore, evaluate and compare a wide range of NoC solutions with a very limited effort. Our experimental results show a speed-up of four orders of magnitude with respect to cycle-accurate HDL simulation, while retaining cycle accuracy. With our emulation framework, designers can explore and optimize a various range of solutions, as well as characterize quickly performance figures.

Early scheduling algorithms usually adjusted the clock cycle duration to the execution time of the slowest operation. This resulted in large slack times wasted in those cycles executing faster operations. To reduce the wasted times multi-cycle and chaining techniques have been employed. While these techniques have produced successful designs, their effectiveness are often limited due to the area increment that may derive from chaining, and the extra latencies that may derive from multicycling. In this paper we present an optimization method that solves the time-constrained scheduling problem by transforming behavioural specifications into new ones whose subsequent synthesis substantially improves circuit performance. Our proposal breaks up some of the specification operations, allowing their execution during several possibly unconsecutive cycles, and also the calculation of several data-dependent operation fragments in the same cycle. To do so, it takes into account the circuit latency and the execution time of every specification operation. The experimental results carried out show that circuits obtained from the optimized specification are on average 60% faster than those synthesized from the original specification, with only slight increments in the circuit area.

Conventional scheduling algorithms usually produce schedules whose cycle lengths are influenced by the operations latency. Operations are assigned to one or several consecutive cycles (multicycle operators) and one operation cannot begin until all its predecessors have finished, except for operations chaining. This technique allows the execution in the same cycle of several data-dependent operations, being some bits of the chained operations calculated in parallel. Chaining one operation to its predecessor requires the completion of both in the selected cycle. This paper presents a less restrictive technique based on the softening of the read-after-write dependencies among operations, which allows beginning the execution of one operation before the calculus of its predecessors has been completed. This becomes feasible when the execution of the predecessor has begun in the selected cycle or in a previous one, and even if it finishes in a posterior cycle. This design technique is applied before synthesis to transform behavioural specifications into new ones whose subsequent synthesis substantially improves circuit performance.

An ever increasing number of dynamic interactive applications are implemented on portable consumer electronics. Designers depend largely on operating systems to map these applications on the architecture. However, today's embedded operating systems abstract away the precise architectural details of the platform. As a consequence, they cannot exploit the energy efficiency of scratchpad memories. We present in this paper a novel integrated hardware/software solution to support scratchpad memories at a high abstraction level. We exploit hardware support to alleviate the transfer cost from/to the scratchpad memory and at the same time provide a high-level programming interface for run-time scratchpad management. We demonstrate the effectiveness of our approach with a case-study.

New portable consumer embedded devices must execute multimedia and wireless network applications that demand extensive memory footprint. Moreover, they must heavily rely on dynamic memory (DM) due to the unpredictability of the input data (e.g. 3D streams features) and system behaviour (e.g. number of applications running concurrently defined by the user). Within this context, consistent design methodologies that can tackle efficiently the complex DM behaviour of these multimedia and network applications are in great need. In this paper, we present a new methodology that allows to design custom DM management mechanisms with a reduced memory footprint for such kind of dynamic applications. The experimental results in real case studies show that our methodology improves memory footprint 60% on average over current state-of-the-art DM managers.

Conventional synthesis algorithms schedule multiple precision specifications by balancing the number of operations of every different type and width executed per cycle. However, totally balanced schedules are not always possible and therefore some hardware waste appears. In this paper a heuristic scheduling algorithm to minimize this hardware waste is presented. It successively transforms specification operations into sets of smaller ones until the most uniform distribution of the computational effort of operations among cycles is reached. In the schedules proposed some operations are executed during a set of non-consecutive cycles.

Portable consumer devices are increasing their capabilities more and more and can now implement new multimedia algorithms that were reserved only for powerful workstations a few years ago. Unfortunately, the original design characteristics of such algorithms do not often allow them to be ported directly to current embedded devices. These algorithms share complex and intensive dynamic memory use and actual embedded systems cannot provide efficient general-purpose memory management as it is needed. As a result, dynamic memory optimizations are a requirement when porting these applications. Within these optimizations, the refinement of the dynamically (de)allocated abstract data type implementations in the complex multimedia applications involved is one of the most important and difficult parts for an efficient mapping of the algorithms on low-power and high-speed embedded consumer devices. We describe a high-level approach for modeling and refining complex data types using abstract derived classes in C++. This approach enables the multimedia developer to compose, evaluate and refine complex data types in a conceptually straightforward way, without a time-consuming programming effort

Embedded systems are evolving from traditional, stand-alone devices to devices that participate in Internet activity. The days of simple, manifest embedded software [e.g. a simple finite-impulse response (FIR) algorithm on a digital signal processor (DSP] are over. Complex, nonmanifest code, executed on a variety of embedded platforms in a distributed manner, characterizes next generation embedded software. One dominant niche, which we concentrate on, is embedded, multimedia software. The need is present to map large scale, dynamic, multimedia software onto an embedded system in a systematic and highly optimized manner. The objective of this paper is to introduce high-level, systematically applicable, data structure transformations and to show in detail the practical feasibility of our optimizations on three real-life multimedia case studies. We derive Pareto tradeoff points in terms of accesses versus memory footprint and obtain significant gains in execution time and power consumption with respect to the initial implementation choices. Our approach is a first step to systematically applying high-level data structure transformations in the context of memory-efficient and low-power multimedia systems.

This paper presents a heuristic method to perform the high-level synthesis of multiple-precision specifications. The scheduling is based on the balance of the number of bits calculated per cycle, and the allocation on the bit-level reuse of the hardware resources. The implementations obtained are multiple-precision datapaths independent of the number and widths of the specification operations. As a result impressive area savings are achieved in comparison with conventional algorithms implementations.

This paper presents an heuristic method to solve the combined resource selection and binding problems for the high-level synthesis of multiple-precision specifications. Traditionally, the number of functional (and storage) units in a datapath is determined by the maximum number of operations scheduled in the same cycle, with their respective widths depending on the number of bits of the wider operations. When these wider operations are not scheduled in such "busy" cycle, this way of acting could produce a considerable waste of area. To overcome this problem, we propose the selection of the set of resources taking into account the only truly relevant aspect: the maximum number of bits calculated and stored simultaneously in a cycle. The implementation obtained is a multiple-precision datapath, where the number and widths of the resources are independent of the specification operations and data objects.

The property called mutual exclusiveness, responsible for the degree of conditional reuse achievable after a high-level synthesis (HLS) process, is intrinsic to the systems behavior. However, sometimes it is only partially reflected in the actual description written by a designer. Our algorithm performs a transformation of the input description that exploits the maximum conditional reuse of the behavior, independently of description style, allowing the HLS tools to obtain circuits with less area.

One of the goals of a high level synthesis process is to minimize the circuit implementation cost. Since the minimization problem associated with those transformations is NP complete, in this work we present an evolutionary algorithm that optimize circuit specifications by means of a special type of genetic operator. We have named this operator algebraic mutation, carried out with the help of algebraic equations. This work can be classified within the algebraic optimization of equational specifications of circuits by using genetic techniques. We have applied this technique to a simple circuit equational specification and to a much more complex algebraic equation. In the first case our algorithm simplifies the equation until the optimum specification is found and in the second a solution improving the former is always obtained, and when we increase the population size, the optimum solution is also found.

This paper presents an efficient method to solve an important aspect of the high-level verification problem: the formal verification of RT-level implementations (datapath + controller), obtained from algorithmic-level specifications by high-level synthesis tools. The method consists in replicating external, and potentially incorrect, design processes within a mathematical framework, giving as a result the proof of correctness or the set of design decisions that led to errors. As the computational complexity is a major problem informal verification, the formal framework is based in an ad hoc formal theory. The moderate complexity achieved, has been confirmed by a detailed experimental study, which shows that our method can verify complex designs overloading the highlevel design-cycle only minimally.

This paper proposes an allocation algorithm able to perform the combined resource selection and operation binding of multiple-precision specifications that maximizes the bit-level reuse of hardware resources. Additionally, it presents an analytic method to estimate the amount of area that our approach could save in comparison with traditional allocation algorithms. In order to minimize the cost of the implementations obtained, the proposed algorithm produces circuits only influenced by the maximum number of bits calculated per cycle. This approach contrasts with the cost of implementations designed by traditional algorithms, which also depends on the number and widths of the operations executed in every cycle.

The computations of a system whose behavior varies depending on the value of some conditions may present a property called mutual exclusiveness. This property, responsible for the degree of conditional reuse achievable after a high-level synthesis (HLS) process, is intrinsic to the behavior. But sometimes it is only partially reflected in the actual description written by a designer, leading to worse implementations. Our algorithm explores in an efficient manner the real mutual exclusiveness of the behavior, independently of the description style. It performs a transformation of the input description that allows the HLS tools to obtain better circuits in terms of the area saving due to conditional reuse.

This paper presents a heuristic scheduling algorithm for heterogeneous specifications, those formed by operations of different types and widths. The algorithm extracts the common operative kernel of the operations, and binds afterwards operations to cycles with the aim of distributing uniformly the number of bits calculated per cycle. In consequence, operations may be fragmented and executed during a set of non-necessarily consecutive cycles, and over a set of several linked simple hardware resources. The proposed algorithm, in combination with allocation algorithms able to guarantee bit-level reuse of hardware resources, obtains considerably smaller datapaths than the ones proposed by conventional synthesis algorithms. In the datapaths produced the type, number, and width of the hardware resources are independent of the type, number, and width of the specification operations and variables.

This paper presents a formal synthesis system which delegates the design space exploration to non-formal, and potentially incorrect, high level synthesis tools. With a quadratic complexity, our system obtains either a truly correct-by-construction design, since the formal design process constitutes itself the verification process, or demonstrates that the solution found by the conventional tool was incorrect.