As Systems-on-Chip size increase, the communication costs become critical and Networks-on-Chip (NoC) bring innovative solutions. Efficient stream-based protocols over NoC have been widely studied to address dataflow communications. They are usually controlled by a set of static parameters. However, new applications, such as high-resolution video decoders, present more data-dependent behaviors forcing communication protocols to support higher dynamicity. For this purpose, we present in this paper dynamic stream links for stream-based end-to-end NoC communications by introducing two link protocols, both independent of the transfer size, allowing to improve the hardware/software control flexibility. The proposed protocols have been modeled in a MPSoC virtual platform and the hardware cost evaluated. Based on simulations, we provide guidelines to exploit these protocols according to application needs.

Explicitly managed memory many-cores (EMM) have been a part of the industrial landscape for the last decade. The IBM CELL processor, general-purpose graphics processing units (GP-GPU) and the STHORM embedded many-core of STMicroelectronics are representative examples. This class of architecture is expected to scale well and to deliver good performance per watt and per mm2of silicon. As such, it is appealing for application problems with regular data access patterns. However, this moves significant complexity to the programmer who must master parallelization and data movement. High level programming tools are therefore essential in order to allow the effective programming of EMM many-cores to a wide class of programmers. This paper presents a novel approach designed for simplifying the programming of EMM many-core architectures. It initially addresses the image processing application domain and has been targeted to the STHORM platform. It takes a high-level description of the computation kernel algorithm and generates an OpenCL kernel optimized for the target architecture, while managing the parallelization and data movements across the hierarchy in a transparent fashion. The goal is to provide both high productivity and high performance without requiring parallel computing expertise from the programmer, nor the need for application code specialization for the target architecture.

Efficient, scalable and productive parallel programming is a major challenge for exploiting the future multi-processor SoC platforms. This article presents the MultiFlex programming environment which has been developed to address this challenge. It is targeted for use on Platform 2012 , a scalable multi-processor fabric. The MultiFlex environment supports high-level simulation, iterative platform mapping, and includes tools for programming model aware debug, trace, visualization and analysis. This article focuses on the two classes of programming abstractions supported in MultiFlex. The first is a set of Parallel Programming Patterns (PPP) which offer a rich set of programming abstractions for implementing efficient data- and task-level parallel applications. The second is a Reactive Task Management (RTM) abstraction, which offers a lightweight C-based API to support dynamic dispatching of small grain tasks on tightly coupled parallel processing resources. The use of the MultiFlex native programming model is illustrated through the capture and mapping of two representative video applications. The first is a high-quality rescaling (HQR) application on a multi-processor platform. We present the details of the optimization process which was required for mapping the HQR application, for which the reference code requires 350 GIPS (giga instructions per second), onto a 16 processor cluster. Our results show that the parallel implementation using the PPP model offers almost linear acceleration with respect to the number of processing elements. The second application is a high-definition VC-1 decoder. For this application, we illustrate two different parallel programming model variants, one using PPPs, the other based on RTM. These two versions are mapped onto two variants of a homogeneous version of the Platform 2012 multi-core fabric.

SUMMARY Many‐core platforms, providing large numbers of parallel execution resources, emerge as a response to the increasing computation needs of embedded applications. A major challenge raised by this trend is the efficient mapping of applications on parallel resources. This is a nontrivial problem because of the number of parameters to be considered for characterizing both the applications and the underlying platform architectures. Recently, several authors have proposed to use multi‐objective evolutionary algorithm to solve this problem within the context of mapping applications on network‐on‐chips. However, these proposals have several limitations: (1) only few metaheuristics are explored (mainly Nondominated Sorting Genetic Algorithm II and Strength Pareto Evolutionary Algorithm 2), (2) only few objective functions are provided, and (3) they only deal with a small number of the application and architecture constraints. In this paper, we propose a new framework that avoids all of the problems cited previously. Our framework is implemented on top of the jMetal framework, which offers an extensible environment. Our framework allows designers to (1) explore several new metaheuristics, (2) easily add a new objective function (or to use an existing one), and (3) take into account any number of architecture and application constraints. The paper also presents experiments illustrating how our framework is applied to the problem of mapping streaming applications on an NoC‐based many‐core platform. Our results show that several new metaheuristics outperform the classical multi‐objective metaheuristics such as Nondominated Sorting Genetic Algorithm II and Strength Pareto Evolutionary Algorithm 2. Moreover, a parallel multi‐objective evolutionary algorithm is implemented in our framework in order to increase the explored space of solutions by simultaneously running several metaheuristics. Copyright © 2011 John Wiley & Sons, Ltd.

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.

In this paper, we describe challenges and solutions for programming multi-processor systems-on-a-chip, based on our experience in programming Platform2012, a large-scale multicore fabric under development by STMicroelectronics and CEA, using the MultiFlex multi-core programming environment.

State-of-the-art System-on-Chip (SoC) consists of hundreds of processing elements, while trends in design of the next generation of SoC point to integration of thousand of processing elements, requiring high performance interconnect for high throughput communications. Optical on-chip interconnects are currently considered as one of the most promising paradigms for the design of such next generation Multi-Processors System on Chip (MPSoC). They enable significantly increased bandwidth, increased immunity to electromagnetic noise, decreased latency, and decreased power. Therefore, defining new architectures taking advantage of optical interconnects represents today a key issue for MPSoC designers. Moreover, new design methodologies, considering the design constraints specific to these architectures are mandatory. In this paper, we present a contention-free new architecture based on optical network on chip, called Optical Ring Network-on-Chip (ORNoC). We also show that our network scales well with both large 2D and 3D architectures. For the efficient design, we propose automatic wavelength-/waveguide assignment and demonstrate that the proposed architecture is capable of connecting 1296 nodes with only 102 waveguides and 64 wavelengths per waveguide.

Optical on-chip interconnects and 3D die stacking are currently considered to be two promising paradigms for the design of next generation Multi-Processors System on Chip architectures (MPSoC). New architectures based on these paradigms are currently emerging and new system-level approaches are required for their efficient design and prototype. The paper investigates a system-level flow for evaluating design feasibility, interconnect architecture performance and application execution efficiency as early as possible in the MPSoC design cycle.

Multi Processor SoC (MPSoC) are being designed today. MPSoC design can help achieve aggressive performance and low power targets but it creates new design challenges: How to design the interconnect fabric and memory sub-system to allow the massive data movement required in a multi processor SoC environment? How to develop, debug and verify HW and SW functionality in a MPSoC design? Is MPSoC design an inflection point that will require new design methods including ESL methodologies?

Multiprocessor systems-on-a-chip (MPSoCs 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 several level of memory hierarchy. Usually tiling is applied to one loop nest; in this paper we apply simultaneously loop fusion with two-level tiling to several loop nests in the context of a MPSoC architecture. The two level-tiling allows the simultaneous optimization of caches and registers. To optimize the memory space used by temporary arrays, buffers and registers are used as a replacement. The experiments show that these techniques yield a significant reduction in the number of data cache misses and in processing time.

Multiprocessor system-on-a-chip architectures have received a lot of attention in the past years, but few advances in compilation techniques are targeting these architectures. This is particularly true for the exploitation of data locality. Most of the compilation techniques discussed in the literature for parallel architectures are based on single loop nest. However, most multimedia and image processing applications are composed of several loop nests. In this paper, new techniques based on program transformations are proposed to optimize these types of applications. In a monoprocessor architecture, the loop fusion technique is well known. In this paper, the loop fusion is generalized and adapted to a MPSoC architecture. Another technique called "computation propagation " is proposed. It completely removes the temporary arrays and significantly reduces the memory accesses, the memory space and the processing time. Experimental results show that this new technique yields a significant reduction in the number of data cache misses (35%), in processing time (30%) and in channel transactions (85%).

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%).

This paper summarizes the characteristics of distributed object models used in large-scale distributed software systems. We examine the common subset of requirements for distributed software systems and systems-on-a-chip (SoC), namely: openness, heterogeneity and multiple forms of transparency. We describe the application of these concepts to the emerging class of complex, parallel SoC's, including multiple heterogeneous embedded processors interacting with hardware co-processors and I/O devices. An implementation of this approach is embodied in STMicroelectronics' DSOC (distributed system object component) programming model. The use of this programming model for an architecture exploration of STs Nomadik mobile multimedia platform is described

This paper introduces an application mapping methodology and case study for multiprocessor on-chip architectures. Starting from the description of an application in standard sequential code (e.g. in C), first the application is profiled, parallelized when possible, and then its components are moved to hardware implementation when necessary to satisfy performance and power constraints. The key contribution of this work is a methodology for high-level hardware/software partitioning that allows the designer to use the same code for both hardware and software models for simulation, providing nevertheless preliminary estimations for timing and power consumption. The methodology has been applied to the co-exploration of an industrial case study: an MPEG4 VGA realtime encoder

The MultiFlex system is an application-to-platform mapping tool that integrates heterogeneous parallel components-H/W or S/W- into a homogeneous platform programming environment. This leads to higher quality designs through encapsulation and abstraction. Two high-level parallel programming models are supported by the following MultiFlex platform mapping tools: a distributed system object component (DSOC) object-oriented message passing model and a symmetrical multiprocessing (SMP) model using shared memory. We demonstrate the combined use of the MultiFlex multiprocessor mapping tools, supported by high-speed hardware-assisted messaging, context-switching, and dynamic scheduling using the StepNP demonstrator multiprocessor system-on-chip platform, for two representative applications: 1) an Internet traffic management application running at 2.5 Gb/s and 2) an MPEG4 video encoder (VGA resolution, at 30 frames/s). For these applications, a combination of the DSOC and SMP programming models were used in interoperable fashion. After optimization and mapping, processor utilization rates of 85%-91% were demonstrated for the traffic manager. For the MPEG4 decoder, the average processor utilization was 88%

This panel will bring six speakers relating their success stories about design starting at the system-level. The format is an educational Panel aimed at informing DAC attendees of the challenges (difficulties and pitfalls) and opportunities (sizable benefits and lessons learned from these experiences).

Today's electronic products are composed of an increasingly diverse set of ICs, ranging from dedicated ASICs, domain-specific ASSPs, platform FPGAs, to general-purpose FPGA's. With increasing integration, a mix of different fabrics on a single SoC becomes possible, combining ASIC-style standard cells, embedded FPGAs, mask-programmable sea-of-gates, and programmable processors. The panelists will present their vision of the fabric which will dominate SoCs in 90 nm technologies and beyond, based on industrial trends and case studies. They will also outline the key CAD tool challenges for the chosen fabric.

In this paper, we explore the requirements of emerging complex SoC's and describe StepNP, an experimental flexible, multi-processor SoC platform targeted towards communications and networking applications. We present the results of mapping an internet protocol (IPv4) packet forwarding application, running at 2.5 Gb/s and 10 Gb/s. We demonstrate how the use of high-speed hardware-assisted messaging and dynamic task allocation in the StepNP platform allows us to achieve very high processor utilization rates (up to 97%) in spite of the presence of high network-on-chip and memory access latencies. The inter-processor communication overhead is kept very low, representing only 9% of instructions.

This paper reviews the challenges in the design of emerging complex systems-on-a-chip (SoC) at STMicroelectronics, from the perspective of our customers' requirements. We then present an approach to effectively integrate heterogenous parallel components - H/W or S/W - into a homogeneous programming environment. This approach, supported by ST's MultiFlex multi-processing SoC environment, allows for the combination of a range of heterogeneous processing elements, supported by high-level programming models. Two programming models are supported: a distributed system object component (DSOC) message passing model, and a symmetrical multi-processing (SMP) model using shared memory. To illustrate the concepts discussed in this paper, we have applied the MultiFlex technology to the mapping of a high-level MPEG4 video encoder (VGA resolution at 30 frames per second) onto a mixed multi-processor and hardware platform.

In this paper, we analyze the emerging trends in the design of complex Systems-on-a-Chip for nanometer-scale semiconductor technologies and their impact on design automation requirements, from the perspective of a broad range SoC supplier.We present our vision of some of the key changes that will emerge in the next five years. This vision is characterized by two major paradigm changes. The first is that SoC design will become divided into four mostly non-overlapping distinct abstraction levels. Very different competences and design automation tools will be needed at each level.The second paradigm change is the emergence of domain-specific S/W programmable SoC platforms consisting of large, heterogeneous sets of embedded processors. These will be complemented by embedded reconfigurable hardware and networks-on-chip. A key enabler for the effective us of these flexible SoC platforms, is a high-level parallel programming model supporting automatic specification-to-platform mapping.

Summary form only given. As VLSI technology advances, it forces changes in the business organization of the industry. Traditional vertically integrated semiconductor manufacturers are concentrating less on manufacturing as foundries such as TSMC, UMC, and Chartered grow. These foundries supply capacity not only to fables houses but also to even large semiconductor manufacturers. As a result, these semiconductor houses are spending more time creating novel platforms for important applications. This puts them in competition with the systems houses that traditionally were their customers.

With the projected explosion of low-cost bandwidth availability, the intensive processing tasks and service hosting will move close to consumers on the "intelligent edge" of the network, where a significant portion of the future storage, processing and network management will take place. We address the rationale for this change, the characteristics of the network processor architecture required to address it, and the software development tools needed in order to improve time-to-market without sacrificing embedded software performance.

This paper outlines a case study at SGS-Thomson Microelectronicson the development of a firmware development environment in co-operationwith Thomson Consumer Electronics Components. Theenviornment is for an embedded processor used for audiodecompression algorithms including: MPEG2, Dolby AC-3 Surround,and Dolby Pro-logic. The enabling component of the firmwareenvironment is a retargetable compiler which maps high-levelalgorithms onto the embedded processor. Although compilation is thecritical technology, this experience has shown that it is insufficient andthat other supporting design tools are also important. For this project,that environment includes an instruction-set simulator, a source-leveldebugger, a custom linker, and a compiler validation strategy. Themethodologies are outlined in this paper with an emphasis on thelessons learned in this hardware-software team development.

The increasing use of embedded software, often implemented on a core processor in a single-chip system, is a clear trend in the telecommunications, multimedia, and consumer electronics industries. A companion paper (Paulin et al., 1997) presents a survey of application and architecture trends for embedded systems in these growth markets. However, the lack of suitable design technology remains a significant obstacle in the development of such systems. One of the key requirements is more efficient software compilation technology. Especially in the case of fixed-point digital signal processor (DSP) cores, it is often cited that commercially available compilers are unable to take full advantage of the architectural features of the processor. Moreover, due to the shorter lifetimes and the architectural specialization of many processor cores, processor designers are often compelled to neglect the issue of compiler support. This situation has resulted in an increased research activity in the area of design tool support for embedded processors. This paper discusses design technology issues for embedded systems using processor cores, with a focus on software compilation tools. Architectural characteristics of contemporary processor cores are reviewed and tool requirements are formulated. This is followed by a comprehensive survey of both existing and new software compilation techniques that are considered important in the context of embedded processors.

We present an extensive survey of trends in embedded processor use with an emphasis on emerging applications in wireless communication, multimedia, and general telecommunications. We demonstrate the importance of application-specific instruction-set processors (ASIPs) in high-volume, low cost applications. We also examine some of the underlying trends of the applications in which embedded processors are used. This is followed by a description of embedded software development tool requirements. High-performance software compilation emerges as a key requirement. Finally, specific industrial case studies of products in MPEG, videophone, and low-cost digital signal processor (DSP) applications are used to illustrate the architecture design tradeoffs, and highlight specific tool requirements. A companion paper (Goosens et al., 1997) presents a comprehensive survey of embedded software development tools, focusing mostly on retargetable software compilation.

The advent of parallel executing address calculation units (ACUs) in digital signal processor (DSP) and application specific instruction-set processor (ASIP) architectures has made a strong impact on an application's ability to efficiently access memories. Unfortunately, successful compiler techniques which map high-level language data constructs to the addressing units of the architecture have lagged far behind. Since access to data is often the most demanding task in DSP, this mapping can be the most crucial function of the compiler. This paper introduces a new retargetable approach and prototype tool for the analysis of array references and traversals for efficient use of ACUs. The ArrSyn utility is designed to be used either as an enhancement to an existing dedicated compiler or as an aid for architecture exploration.

This paper presents a distributed hardware/software cosimulation environment for heterogeneous systems prototyping applied to an industrial application. The environment provides following features: distributed Hw/Sw cosimulation, automatic Hw/Sw interface generation, Hw elements can be described at different levels of abstraction and generic/specific Sw debuggers can be used. Starting from a brief description of the interface of the interconnected modules the tool automatically produces the link between Hw and Sw parts. In addition, the environment is very easy to use, even for complex systems that may include several Sw (C) modules and several Hw (VHDL) modules running in parallel. Applied to a large industrial multi-processor system, this method appeared reliable and efficient, providing important benefits in hardware-software codesign: better design environment and reduced time to validate.

We present a new form of partitioning of PLA-based FSMs that combines the advantages of traditional vertical PLA partitioning (i.e. via inputs and/or outputs) and counter embedding which consists of replacing the FSM state memories by a counter. Like the former, horizontal partitioning allows the reduction of the number of input and/or output columns in the PLAs resulting from the partition. Furthermore, the technique also reduces the total number of product terms, as in counter embedding techniques. This reduction is due to a decomposition of state transitions into two classes that are realized by two sets of logic. In this case however, a second PLA-based FSM is used in place of the counter. This results in area reductions of 30% to 60% (with respect to regular two-level logic minimization) for the benchmark examples presented.

New algorithms for high-level synthesis are presented. The first performs scheduling under hardware resource constraints and improves on commonly used list scheduling techniques by making use of a global priority function. A new design-space exploration technique, which combines this algorithm with an existing one based on time constraints, is also presented.

Novel fast decomposition algorithms that rely on precise linear models for gate delays are presented. Within the limits of the models, the algorithm performs locally optimal m-way balanced and unbalanced decompositions of logic gates to achieve a maximal timing gain. The decompositions take the output load into account and are characterized by a near-minimal area increase. The models were applied successfully to industrial standard cell and gate array libraries and the algorithms were integrated into a commercial technology mapping software package. Experimental results show that the speed improvement obtained by the m-way algorithms is nearly twice that resulting from optimal two-way decomposition.>

A general scheduling methodology is presented that can be integrated into specialized or general-purpose high-level synthesis systems. An initial version of the force-directed scheduling algorithm at the heart of this methodology was originally presented by the authors in 1987. The latest implementation of the logarithm introduced here reduces the number of functional units, storage units, and buses required by balancing the concurrency of operations assigned to them. The algorithm supports a comprehensive set of constraint types and scheduling modes. These include multicycle and chained operations; mutually exclusive operations; scheduling under fixed global timing constraints with minimization of functional unit costs, minimization of register costs, and minimization of global interconnect requirements; scheduling with local time constraints (on operation pairs); scheduling under fixed hardware resource constraints; functional pipelining; and structural pipeline (use of pipeline functional units). Examples from current literature, one of which was chosen as a benchmark for the 1988 High-Level Synthesis Workshop, are used to illustrate the effectiveness of the approach.>

The HAL system performs data path synthesis using a new scheduling algorithm that is part of an interdependent scheduling and allocation scheme. This scheme uses an estimate of the hardware allocation to guide and optimize the scheduling subtask. The allocation information includes the number, type, speed and cost of hardware modules as well as the associated multiplexer and interconnect costs.

A novel approach to automatic data path synthesis is presented. This approach features innovations in the synthesis process as well as in the system implementation.