A hardware analyzer for the Boolean satisfiability problem using a complete algorithm was developed for an Alter a DE2-70 Cyclone II FPGA board. In one clock cycle, all implications are computed, variables are assigned and all clauses are evaluated in parallel. Backtracking is done by means of a hardware stack occupying minimal memory resources. No memory is required to hold the potentially gigantic problem specification as a VHDL package is used by the HDL compiler to simplify the circuit (by propagating constants). Run-time comparisons were made using instances from the DIMACS suite with MiniSAT, one of the most efficient software solvers, revealing accelerations of up to 6.66, as well as with other state-of-the-art hardware SAT solvers where accelerations of 2 orders of magnitude were observed. Our approach demonstrates a high level of flexibility and scalability as the generated circuits have a very small FPGA footprint. The largest problem tested has 317 variables, 1264 clauses for a total of 3670 literals and occupies 20.47% of the FPGA used. Projections regarding circuit frequency and FPGA footprint for larger problems are also deduced to show the scalability of the approach.

Due to their great ability to parallelize at a very high integration level, Multi-Processors Systems-on-Chip (MPSoCs) are good candidates for systems and applications such as multimedia. Memory is becoming a key player for significant improvements in these applications (power, performance and area). The large amount of data manipulated by these applications requires high-capacity computing and memory. Lately, new programming models have been introduced. This leads to the need of new optimization and mapping techniques suitable for embedded systems and their programming models. This article presents novel approaches for combining memory optimization with mapping of data-driven applications while considering anti-dependence conflicts. Two different approaches are studied and integrated with existing mapping algorithms. The first approach (based on heuristic algorithms) keeps the graph transformation for memory optimization stage from the mapping stage and enables their combination in a design flow. The second approach (based on evolutionary algorithms) combines these two stages and integrates them in a unique stage. Some significant improvements are obtained for memory gain, communication load and physical links.

Three-dimensional (3D) integrated circuits (IC) are emerging as a viable solution to enhance the performance of Multi-processor System-On-Chip (MPSoC). The use of highspeed hardware and the increased density of 3D architectures present novel challenges concerning thermal dissipation and power management. Most approaches at power and thermal modeling use either static analytical models or slow low-level analog simulations. In this paper, we propose a novel thermal modeling methodology for evaluation of 3D MPSoCs. The integration of this methodology in a virtual platform enables effcient dynamic thermal evaluation of a chip. We present initial results for an architecture based on a 3D Network-On-Chip (NoC) interconnecting 2D processing elements (PE). Our methodology is based on the finite difference method: we perform an initial static characterization, after which high-speed dynamic simulation is possible.

Longer range, faster speed and stronger link are today's wireless mandatory characteristics. Tremendous efforts are being deployed to create new and improved wireless protocols. However, these new protocols are being tested in harsh and uncontrolled environments. Simulation tools help to capture the expected behavior, but the proposed designs might not work in real life situations due to lack of accurate simulation models. Testbed platforms are able to test designs in real life settings, but the flexibility of the design is reduced and design exploration becomes a complex task. This paper presents a hybrid platform composed of a simulation tool and a testbed environment, which makes it possible easily design and accurately test new wireless protocols.

Given the increasing heterogeneity and complexity of systems being developed, untimed modeling at a system level becomes more and more important for design space exploration and verification, due to its conciseness and speed. After showing inadequacies of SystemC, which is the predominant modeling environment in this area, we propose a paradigm shift from immediate notifications and coroutines in SystemC to Atomic Actions and true parallelism in an extension of Esys.NET. We exploit the introspection and attribute programming to extend the capabilities of the environment and to build the basis for heterogeneous cosimulation. This paper aims to show the main advantages of this paradigm shift, such as (1) the improvement of simulation time by exploiting the capabilities of multicore simulation hosts, (2) the reduction of modeling hazards related to parallelism and resource sharing, and (3) a more efficient design space exploration.

Simulation monitoring tools are needed in hardware/software codesign for performance debugging, model validation and hardware/software partitioning purposes. Existing tools are either hardware- or software-centric and lack integrated and seamless co-monitoring. This paper presents a system-level co-monitoring tool that can monitor the computation and communication activities of SystemC user modules, as well as bus, memory and processor usage, on a variety of hardware/software embedded configurations that may include an RTOS. We also describe how performance metrics are generated during or after simulation and made accessible to users or external applications. Finally, experimental results show that such co-monitoring does not disturb the simulation's internal timing and only moderately increases the simulation's wall clock run time (by 11-22% for hardware/software partitioned architectures)

Multiprocessor system-on-a-chip (MPSoC) architectures have received a lot of attention in the past years, but few advances in compilation techniques target these architectures. This is particularly true for the exploitation of data locality. Most of the compilation techniques for parallel architectures discussed in the literature are based on a single loop nest. This article presents new techniques that consist in applying loop fusion and tiling to several loop nests and to parallelize the resulting code across different processors. These two techniques reduce the number of memory accesses. However, they increase dependencies and thereby reduce the exploitable parallelism in the code. This article tries to address this contradiction. To optimize the memory space used by temporary arrays, smaller buffers are used as a replacement. Different strategies are studied to optimize the processing time spent accessing these buffers. The experiments show that these techniques yield a significant reduction in the number of data cache misses (30%) and in processing time (50%).

In today's embedded systems, memory hierarchy is rapidly becoming a major factor in terms of power, performance and area. This is especially true for embedded multimedia applications using temporary multi-dimensional arrays that are typically used to store intermediate results during multimedia processing. In this paper, the authors propose a new technique that optimizes the use of caches and registers. It consists in combining buffer and register allocation to reduce the size of the temporary arrays. The authors use the concept of live data to replace each array by a smaller buffer. The authors then replace references to this buffer by registers. The experiments are made on a Unix environment and on the StepNP simulator. The results show that the technique yields significant reduction of the number of data cache misses

New sophisticated EDA tools and methodologies will be needed to make products viable in the future marketplace by simplifying the various design stages. These tools will permit system design at a high abstraction level and enable automatic refinement through several abstraction levels to obtain a final prototype. They will have to be based on representations that are clean, complete, and easy to manipulate. In order to develop these new EDA tools, key features such as standardization, metadata programming, reflectivity, and introspection are needed. This work proposes a .Net Framework-based methodology, which possesses all these required key features. This methodology simplifies specification, synthesis, and validation of systems and enables the efficient creation/customization of EDA tools at low cost and development time. We show the effectiveness of this methodology by presenting its application for the design of a new EDA tool called ESys .Net (Embedded System design with .Net). We emphasize the specification and simulation aspects of this tool.

Sharing IP blocks in today's competitive market poses significant high security risks. Creators and owners of IP designs want assurances that their content will not be illegally redistributed by consumers, and consumers want assurances that the content they buy is legitimate. Recently, digital watermarking emerged as a candidate solution for copyright protection of IP blocks. In this paper, we propose a new approach for watermarking IP designs based on the embedding of the ownership proof as part of the IP design's finite state machine (FSM). The approach utilizes coinciding as well as unused transitions in the state transition graph of the design. Our approach increases the robustness of the watermark and allows a secure implementation, hence enabling the development of the first public-key IP watermarking scheme at the FSM level. We also define for our approach, and use experimental measures to prove its robustness.

Developing a functional prototype of a system-on-chip provides a unifying vehicle for model validation and system refinement. Keeping the prototype executable across several abstraction levels, clock domains and design tools is a key requirement to effective prototyping. This paper presents how model-level transactors address design heterogeneity by unifying event-based and cycle-based worlds from specification to implementation. Transactors are used to build a functional prototype of a software-radio component. An executable UML model is bridged to a hardware abstraction of a radio stream developed with Simulink to implement a realistic and working prototype. Model validation and performance measurements are realized through prototype execution and real-time monitoring.

Data dependency constraints constitute a lower bound P on the minimal clock period of single-phase clocked sequential circuits. In contrast to methods based on basic retiming, clocked sequential circuits with clock period P can always be obtained using software pipelining techniques. Such circuits can be derived by any method that can be framed in the following four-step process: Step 1, determine P; Step 2, compute a valid periodic schedule of the computational elements; Step 3, place registers back to the circuit; Step 4, assign the clock signals to control registers.Methods with polynomial run-time to implement this process are proposed in the literature. They implement these steps sequentially, starting with Step 1. These methods do not know how to optimally place registers which leads to an unnecessary number of registers. In this article, we address the problem of how to simultaneously implement Steps 2 and 3 in order to minimize the total number of registers. We conjecture that the problem is NP-hard in its general form. We formulate the problem for the first time in the literature, and devise a Mixed Integer Linear Program (MILP) to solve it. From this MILP, we derive a linear program to determine approximate solutions to the problem for large general circuits. We show that the proposed approach can handle nonzero clock skew. Experimental results confirm the effectiveness of the approach and show that significant reductions of the number of registers can be obtained although register sharing is not used. When the schedule is given, the proposed approach provides solutions to the problem of how to place the minimal number of registers in Step 3.

Nowadays, the use of system level description languages is mandatory for the efficient design of complex systems. These description languages are exemplified by SystemC and SystemVerilog. In this paper, we propose a new .NET framework based system level modeling and simulation environment called Esys.NET (embedded systems design with .NET). It allows (1) cooperation - by enabling Web-based design and multi-language features, (2) easy systems specification task - by enabling integration of software components running application and operating systems and by alleviating memory management, (3) link to automatic refinement tools - by enabling translation of specification models into a standard intermediate format and annotation of specification models, and (4) comparative performances with existing environments.

A recent practice in the development of programmable SoC is the integration of configurable processors, since they offer an interesting compromise between purely software and hardware solutions. This paper proposes an adjustment to the current codesign approach to integrate this opportunity at the partitioning level. Since configurable processors seem to be an interesting option for NPU designs, we integrated into a system level exploration platform the support of an Xtensa processor for more investigation. As case studies, this paper illustrates the methodology for two realistic network-processing applications, for which interesting performances are obtained.

The next generation of tools for embedded systems design will represent a common arena for several cooperating groups. These tools will permit system design at a high abstraction level and enable automatic refinement through several abstraction levels to obtain the final prototype. To facilitate this evolution, we propose a new .Net Framework based system level modeling and simulation environment. This environment allows (1) cooperation -- by enabling web-based design and multi-language features, (2) easy systems specification task -- by enabling the integration of software components and by alleviating memory management and (3) the linking to automatic refinement tools -- by enabling the translation of model specifications into a standard intermediate format and by permitting the annotation of model specifications.

There is a growing need for e2e lightpaths for high volume data transferring applications such as GridFTP and SAN. They wish to dynamically deploy lightpaths over multiple management domains. Research, sponsored by Canarie Incorporated, is underway to enable "customer-empowered networks" and to experiment them with the Canadian research network CA*Net4. New signaling and control approaches using Web services have been proposed. One difficulty is that each domain must retain the control of their optical network infrastructure and ensure proper allocation of optical resources. Hence, it is important that the signaling takes into account the management constraints imposed by the different domains. This paper presents a policy-based approach for user-controlled lightpath provisioning. The work builds on the research around the new signaling approaches for realizing customer-empowered networks. We present an architecture based on Web Services allowing users or Grid applications to establish e2e lightpaths over multiple autonomous systems. To tackle the problem of admission control and to address the resource allocation issue, we developed policy restricted signaling which allows customers to reserve lightpaths over multiple domains while ensuring that management rules of each domain are enforced. The signaling has been implemented and the experiment on a small network composed of Cisco equipment proves the viability of our approach.

Segmented channel routing is fundamental to the routing of row-based FPGAs. In this paper, we study segmented channel routability via satisfiability. Our method encodes the horizontal and vertical constraints of the routing problem as Boolean conditions. The routability constraint is satisfiable if and only if the net connections in the segmented channel are routable. Empirical results show that the method is time-efficient and applicable to large problem instances.

This work attempts to enhance the support of embedded software modeling with SystemC 2.0. We propose a top-down approach that first lets designers specify their application in SystemC at a high abstraction level through a set of connected modules, and simulate the whole system. Then, the application is partitioned in two parts: software and hardware modules. Each partition can be connected to our platform that includes a commercial RTOS executed by an ARM ISS scheduled by the SystemC simulator. One of our major contributions is that we can easily move a module from hardware to software (and vice versa) to allow architectural exploration. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

We address the problem of minimizing dynamic power consumption for single-phase synchronous digital designs, under timing constraints, using an unification of basic retiming and supply voltage scaling. We assume that the number of supply voltages and their values are known for each computation element. Our main objective is then to change the location of registers using basic retiming while maximizing the number of computation elements off critical paths that can operate under a low available supply voltage, and can lead to a maximum dynamic power saving. We address the problem at the system-level. We formulate the problem as a Mixed Integer Linear Program (MILP). The exact optimal solution for the problem is then guaranteed. We also devise an algorithm to compute bounds on the values assigned by basic retiming to each computational element. Besides helping to find the optimal solution to the problem, these bounds also allow to reduce the run-time for finding this solution. The proposed approach can produce converter-free designs and can also minimize short-circuit power consumption. Experimental results have shown that dynamic power consumption can be reduced by factors that range from 2.78% to 37.24% for single-phase designs with minimal clock period. For these experimental results, the run-time for solving the MILP is under 2min.

We address the problem of minimizing dynamic power consumption under performance constraints by scaling down the supply voltage of computational elements off critical paths. We assume that the number of possible supply voltages and their values are known for each computational element. We focus on solving this problem on cyclic and acyclic graphs corresponding to synchronous designs. We consider multiphase clocked sequential circuits derived using software pipelining techniques. In this paper, we present exact and heuristic methods to solve the problem. The proposed methods take the form of mathematical programming formulations and their associated solution algorithms. The exact methods are based on a mixed integer linear programming formulation of the problem. The heuristic methods are based on linear programming formulations derived from the exact problem formulation. Solution methods are analyzed experimentally in terms of their run time and effectiveness in finding designs with lower dynamic power using circuits from the ISCAS89 benchmark suite. Power reduction factors as high as 69.75% were obtained compared to designs using the highest supply voltages. One of the heuristic methods leads to solutions that are near optimal, typically within 5% from the optimal solution. Low dynamic-power designs with no or a small number of level converters, are also obtained.

Reduced-ordered binary decision diagrams (BDDs) are a data structure for representation and manipulation of Boolean functions. The variable ordering largely influences the size of the BDD, varying from linear to exponential. In this paper, the authors study the BDD minimization problem based on scatter search optimization. Scatter search offers a reasonable compromise between quality (BDD reduction) and time. On smaller benchmarks it delivers almost optimal BDD size with less time than the exact algorithm. For larger benchmarks it delivers smaller BDD sizes than genetic algorithm or simulated annealing at the expense of longer runtime.

SystemC is a new open source library in C++ for developing cycle-accurate or more abstract models of software algorithms, hardware architecture and system-level designs. SystemC is meant to be an interoperable, modeling platform allowing seamless tool integration. Our objective is to evaluate the feasibility of linking a third party software to SystemC without modifying the SystemC source. We chose the development of a GUI as such an application. This application illustrates a set of applications following the observer pattern defined recently in software engineering. This class of applications can be loosely coupled to a platform designed following specific rules of software reuse.

Dynamic power is the main source of power consumption in CMOS circuits. It depends on the square of the supply voltage. It may significantly be reduced by scaling down the supply voltage of some computational elements in the circuit, with the penalty of an increase of their execution delay. To reduce the dynamic power consumption, without degrading the performance determined assuming that the circuit operates at the highest available supply voltage, the supply voltage of computational elements off critical paths can be scaled down. Defined here as MinP/sub dyn/, the problem of minimizing the dynamic power consumption, under performance constraints, by scaling down the supply voltage of computational elements on non-critical paths is NP-hard in general. Solving MinP/sub dyn/ for multi-phase clocked sequential circuits may allow to reduce their power consumption and the required number of registers. Reducing the number of registers also allows to reduce the power consumption, the number of control signals, and the area of the circuit. In this paper, we focus on devising methods to efficiently solve MinP/sub dyn/ for designs modeled as cyclic or acyclic graphs. More precisely, once the circuit is optimized for timing constraints, then we look for schedules that allow the computational elements of the circuit to operate at the lowest possible supply voltage. We present an integer linear programming formulation for that problem, which we use to devise a polynomial time solvable method and an exact algorithm based on a branch-and-bound technique. Experimental results confirm the effectiveness of the method and power reduction factors as high as 53.84% were obtained. Also, they show that the exact algorithm produces optimal results in a small number of tries, which is due to the rules used to prune useless solutions.

We present a method to optimize clocked circuits by relocating and changing the time of activation of registers to maximize the throughput. Our method is based on a modulo scheduling algorithm for software pipelining, instead of retiming. It optimizes the circuit without the constraint on the clock phases that retiming has, which permits to always achieve the optimal clock period. The two methods have the same overall time complexity, but we avoid the computation of all pair-shortest paths, which is a heavy burden regarding both space and time. From the optimal schedule found, registers are placed in the circuit without looking at where the original registers were. The resulting circuit is a multi-phase clocked circuit, where all the clocks have the same period and the phases are automatically determined by the algorithm. Edge-triggered flip-flops are used where the combinational delays exactly match that period, whereas level-sensitive latches are used elsewhere, improving the area occupied by the circuit. Experiments on existing and newly developed benchmarks show a substantial performance improvement compared to previously published work.

The number comparison is a difficult and fundamental operation for residue number systems (RNS). Previous algorithms use either some redundant modulus or big modulo operations. In this paper, based on the New Chinese Remainder Theorem II, we present a new comparison algorithm using smaller modulo operations and no redundant modulus.

This paper proposes three new residue-to-binary converters using 2n- bit or n-bit adders for the three moduli residue number system of the form (2/sup n/-1, 2/sup n/, 2/sup n/+1). The 2n-bit adder based converter is faster and requires about half of the hardware required by previous methods. For n-bit adder based implementations, one new converter is twice as fast as the previous method using similar amount of hardware; while another new converter achieves improvement in both speed and area.

In this paper, we present a method to optimize clocked circuits by relocating and changing the time of activation of registers to maximize throughput. Our method is based on software pipelining instead of retiming. The two methods have the same overall complexity, but unlike previously published retiming methods, the time consuming step of searching an adequate clock period is avoided, since the optimal clock period is always a solution. The resulting circuit is a multi-phase clocked circuit, where all the clocks have the same period. Edge-triggered flip-flops are used where the combinational delays exactly match that period, whereas level-sensitive latches are used elsewhere improving the area occupied by the circuit. Experiments on existing and newly developed benchmarks show substantial performance improvement compared to previously published work.

A new approach to fault analysis is presented. The authors consider multiple stuck-at-0/1 faults at the gate level. First, a fault collapsing phase is applied to the network, so that equivalent faults are eliminated. During the analysis the authors consider frontier faults where there is at least a normal path from each faulty line to a primary output. It is shown that the set of frontier faults is equivalent to the set of multiple faults. Given an input vector, the authors evaluate the fault-free circuit and then propagate fault effects. Assuming that fault-free response is observed, a fault-dropping procedure is then applied to eliminate faulty conditions on lines, that are either absent or may be hidden by other faulty conditions. This method is applied to some benchmark circuits and achieves a high degree of efficiency.>

A scheme for fault-tolerant triangular cellular interconnection networks is proposed. A fault model is defined which unifies the concept of usable and unusable faulty components. An algorithm for testing these networks with a minimal number of tests (8) is presented. This result is extended to other cellular networks. A constant number of tests independent of the network size (at most 8) is added, in order to locate the faulty cell in the triangular cellular interconnection networks. Then, by considering networks of n+2 instead of n inputs/outputs, any single faulty cell can be tolerated. Neither the complexity of the cell nor that of the links is increased. The programming of the fault tolerant network is of the same complexity as that of the fault-free network and the relative silicon area overhead decreases with n and is proportional to 4/n.>

It has been shown in the literature that C-testable iterative arrays have very simple test structures, independent of the length of the arrays. We show in this work that all C-testable arrays are also pI-testable, which is a property yielding, in many cases, rather simple built-in-testing structures, both for the test generator and for the response verifier.

Currently proposed and used schemes for built-in testing (B-I-T) use as test generators either binary counters (exhaustive testing), linear feedback shift registers (semiexhaustive testing), or ROM's containing the test vectors (prestored testing). The disadvantages of these methods have been discussed in [4], and a store-and-generate B-I-T arrangement was proposed as a compromise between the exhaustive and the prestored form of test generation. Unfortunately, no systematic method was given for producing tests.