The Instruction-Set Extension Problem: A Survey
---
paper_title: From ASIC to ASIP: the next design discontinuity

paper_content:

A variety of factors is making it increasingly difficult and expensive to design and manufacture traditional Application Specific Integrated Circuits (ASICs). This has started a significant move towards the use of programmable solutions of various forms - increasingly referred to as programmable platforms. For the platform manufacturer, programmability provides higher volume to amortize design and manufacturing costs, as the same platform can be used over multiple related applications, as well as over generations of an application. For the application implementer, programmability provides a lower risk and shorter time-to-market implementation path. The flexibility provided by programmability comes with a performance and power overhead. This can be significantly mitigated by using application specific platforms, also referred to as Application Specific Instruction Set Processors (ASIPs). This paper details the reasons for this significant change in application implementation philosophy, provides illustrative contemporary evidence of this change, examines the space of application specific platforms, outlines fundamental problems in their development, and finally presents a methodology to deal with this changing design style.
---
paper_title: Reconfigurable computing: a survey of systems and software

paper_content:

Due to its potential to greatly accelerate a wide variety of applications, reconfigurable computing has become a subject of a great deal of research. Its key feature is the ability to perform computations in hardware to increase performance, while retaining much of the flexibility of a software solution. In this survey, we explore the hardware aspects of reconfigurable computing machines, from single chip architectures to multi-chip systems, including internal structures and external coupling. We also focus on the software that targets these machines, such as compilation tools that map high-level algorithms directly to the reconfigurable substrate. Finally, we consider the issues involved in run-time reconfigurable systems, which reuse the configurable hardware during program execution.
---
paper_title: Automatic selection of application-specific instruction-set extensions

paper_content:

In this paper, we present a general and an efficient algorithm for automatic selection of new application-specific instructions under hardware resources constraints. The instruction selection is formulated as an ILP problem and efficient solvers can be used for finding the optimal solution. An important feature of our algorithm is that it is not restricted to basic-block level nor does it impose any limitation on the number of the newly added instructions or on the number of the inputs/outputs of these instructions. The presented results show that a significant overall application speedup is achieved even for large kernels (for ADPCM decoder the speedup ranges from x1.2 to x3.7) and that our algorithm compares well with other state-of-art algorithms for automatic instruction set extensions.
---
paper_title: HW/SW partitioning and code generation of embedded control applications on a reconfigurable architecture platform

paper_content:

This paper studies the use of a reconfigurable architecture platform for embedded control applications aimed at improving real time performance. The hw/sw codesign methodology from POLIS is used. It starts from high-level specifications, optimizes an intermediate model of computation (Extended Finite State Machines) and derives both hardware and software, based on performance constraints. We study a particular architecture platform, which consists of a general purpose processor core, augmented with a reconfigurable function unit and data-path to improve run time performance. A new mapping flow and algorithms to partition hardware and software are proposed to generate implementations that best utilize this architecture. Encouraging preliminary results are shown for automotive electronic control examples.
---
paper_title: A hardware/software partitioning algorithm for pipelined instruction set processor

paper_content:

This paper proposes a new method to design an optimal instruction set for pipelined ASIP development using a formal HW/SW codesign methodology. The codesign task addressed in this paper is to find a set of HW implemented operations to achieve the highest performance of a pipelined ASIP under a given gate count and power consumption constraint. The method enables to estimate the performance and pipeline hazards of the designed ASIP very accurately. The experimental results show that the proposed method is effective and quite efficient.
---
paper_title: Hardware/Software Partitioning in embedded system design

paper_content:

One of the most crucial steps in the hardware/software co-design of embedded systems is hardware/software partitioning. Most existing partitioning approaches try to capture too many details of partitioning problems and target architectures. In this paper, a simplified model for the hardware/software partitioning problem is introduced, and different versions of the partitioning problem are defined formally. Based on the simplified model, and ILP (integer linear programming) based approach and a genetic algorithm are presented. Experiments show that our genetic algorithm can solve the partitioning problem with thousands of nodes, yielding solutions close to optimal.
---
paper_title: A linear complexity algorithm for the automatic generation of convex multiple input multiple output instructions

paper_content:

The instruction-set extensions problem has been one of the major topics in recent years and it consists of the addition of a set of new complex instructions to a given instruction-set. This problem in its general formulation requires an exhaustive search of the design space to identify the candidate instructions. This search turns into an exponential complexity of the solution. In this paper we propose an efficient linear complexity algorithm for the automatic generation of convex multiple input multiple output instructions, whose convexity is theoretically guaranteed. The proposed approach is not restricted to basic-block level and does not impose limitations either on the number of input and/or output, or on the number of new instructions generated. Our results show a significant overall application speedup (up to ×2.9 for ADPCM decoder) considering the linear complexity of the proposed solution and which therefore compares well with other state-of-art algorithms for automatic instruction-set extensions.
---
paper_title: An efficient framework for dynamic reconfiguration of instruction-set customization

paper_content:

We present an efficient framework for dynamic reconfiguration of application-specific instruction-set customization. A key component of this framework is an iterative algorithm for temporal and spatial partitioning of the loop kernels. Our algorithm maximizes performance gain of an application while taking into consideration the dynamic reconfiguration cost. It selects the appropriate custom instruction-sets for the loops and maps them into appropriate configurations. We model the temporal partitioning problem as a k-way graph partitioning problem. A dynamic programming based solution is used for the spatial partitioning. Comprehensive experimental results indicate that our iterative algorithm is highly scalable while producing optimal or near-optimal (99% of the optimal) performance gain.
---
paper_title: MediaBench: a tool for evaluating and synthesizing multimedia and communications systems

paper_content:

Significant advances have been made in compilation technology for capitalizing on instruction-level parallelism (ILP). The vast majority of ILP compilation research has been conducted in the context of general-purpose computing, and more specifically the SPEC benchmark suite. At the same time, a number of microprocessor architectures have emerged which have VLIW and SIMD structures that are well matched to the needs of the ILP compilers. Most of these processors are targeted at embedded applications such as multimedia and communications, rather than general-purpose systems. Conventional wisdom, and a history of hand optimization of inner-loops, suggests that ILP compilation techniques are well suited to these applications. Unfortunately, there currently exists a gap between the compiler community and embedded applications developers. This paper presents MediaBench, a benchmark suite that has been designed to fill this gap. This suite has been constructed through a three-step process: intuition and market driven initial selection, experimental measurement to establish uniqueness, and integration with system synthesis algorithms to establish usefulness.
---
paper_title: An integer linear programming approach for identifying instruction-set extensions

paper_content:

This paper presents an Integer Linear Programming (ILP) approach to the instruction-set extension identification problem. An algorithm that iteratively generates and solves a set of ILP problems in order to generate a set of templates is proposed. A selection algorithm that ranks the generated templates based on isomorphism testing and potential evaluation is described. A Trimaran based framework is used to evaluate the quality of the instructions generated by the technique. Speed-up results of up to 7.5 are observed.
---
paper_title: Synthesis of Application Specific Instructions for Embedded DSP Software

paper_content:

Application specific instructions play an important role in reducing the required code size and increasing performance in embedded DSP systems. This paper describes a new approach to generate application specific instructions for DSP applications. The proposed approach is based on a modified subset-sum problem and supports multicycle complex instructions, as well as single-cycle instructions, while the previous state-of-the-art approaches generate only the single-cycle instructions or just select instructions from the fixed super-set of possible instructions. In addition, the proposed approach can also be applied to the case that instructions are predefined. Experimental results on real applications show that Various given constraints can be met by the generated set of application specific instructions without attaching special hardware accelerators.
---
paper_title: Synthesis of application specific instructions for embedded DSP software

paper_content:

Application specific instructions play an important role in reducing the required code size and increasing performance. This paper describes a new approach to generate application specific instructions for DSP applications. The proposed approach is based on a modified subset-sum problem, and can support multi-cycle complex instructions as well as single cycle instructions, while the previous state-of-the-art approaches can generate only the single-cycle instructions or can just select instructions from the fixed super-set of possible instructions. In addition, the proposed approach can also be applicable to the case that instructions are predefined. The experimental results on real applications show that the proposed approach is effective in making the instructions meet the given constraints without attaching special hardware accelerators.
---
paper_title: Instruction-set matching and selection for DSP and ASIP code generation

paper_content:

The increasing use of digital signal processors (DSPs) and application specific instruction-set processors (ASIPs) has put a strain on the perceived mature state of compiler technology. The presence of custom hardware for application-specific needs has introduced instruction types which are unfamiliar to the capabilities of traditional compilers. Thus, these traditional techniques can lead to inefficient and sparsely compacted machine microcode. In this paper, we introduce a novel instruction-set matching and selection methodology, based upon a rich representation useful for DSP and mixed control-oriented applications. This representation shows explicit behaviour that references architecture resource classes. This allows a wide range of instructions types to be captured in a pattern set. The pattern set has been organized in a manner such that matching is extremely efficient and retargeting to architectures with new instruction sets is well defined. The matching and selection algorithms have been implemented in a retargetable code generation system called CodeSyn. >
---
paper_title: Synthesis of Accelerator Data Paths for High-Throughput Signal Processing Applications

paper_content:

A disc brake having a friction lining pad for braking engagement with a rotatable disc. Moving of the friction lining pad is obtained by rotation of a cam engaging a force directing member fastened to the lining pad for transmitting an actuating force to the friction lining pad in a direction for bringing the lining pad into engagement with the disc. Adjustment for wear of the friction lining pad is obtained through the rotation of the cam in the other direction in an amount to maintain engagement with the force directing member in the disengaged condition of the brake to equalize the stroke required to actuate the brake.
---
paper_title: Automatic Application-Specific Instruction-Set Extensions Under Microarchitectural Constraints

paper_content:

This paper presents a methodology for automatically designing Instruction-Set Extensions in embedded processors. Many commercially available CPUs now offer the possibility of extending their instruction set for a specific application. Their tool chains typically support manual experimentations, but algorithms that can define the set of customised functional units most beneficial for a given applications are missing. Only a few algorithms exist but are severely limited in the type and size of operation clusters they can choose and hence reduce significantly the effectiveness of specialisation. A more general algorithm is presented here which selects maximal-speedup convex subgraphs of the application data-flow graph under fundamental microarchitectural constraints, and which improves significantly on the state of the art.
---
paper_title: Instruction set definition and instruction selection for ASIPs

paper_content:

Application Specific Instruction set Processors (ASIPs) are field or mask programmable processors of which the architecture and instruction set are optimised to a specific application domain. ASIPs offer a high degree of flexibility and are therefore increasingly being used in competitive markets like telecommunications. However, adequate CAD techniques for the design and programming of ASIPs are missing hitherto. An interactive approach for the definition of optimised microinstruction sets of ASIPs is presented. A second issue is a method for instruction selection when generating code for a predefined ASIP. A combined instruction set and data-path model is generated, onto which the application is mapped. >
---
paper_title: A hardware/software codesign partitioner for ASIP design

paper_content:

This paper introduces a new codesign partitioning method used in automating the design of ASIP (Application Specific Integrated Processor). The codesign partitioning problem is formalized as a combinatorial optimization problem that partitions the operations into hardware and software such that a certain performance goal is met using minimum hardware resources. A branch-and-bound algorithm is used to solve the presented formalization. The proposed method is found to be effective in producing a quality design in reasonable time with a minimum of design interaction.
---
paper_title: Instruction generation for hybrid reconfigurable systems

paper_content:

Future computing systems need to balance flexibility, specialization, and performance in order to meet market demands and the computing power required by new applications. Instruction generation is a vital component for determining these trade-offs. In this work, we present theory and an algorithm for instruction generation. The algorithm profiles a dataflow graph and iteratively contracts edges to create the templates. We discuss how to target the algorithm toward the novel problem of instruction generation for hybrid reconfigurable systems. In particular, we target the Strategically Programmable System, which embeds complex computational units such as ALUs, IP blocks, and so on into a configurable fabric. We argue that an essential compilation step for these systems is instruction generation, as it is needed to specify the functionality of the embedded computational units. In addition, instruction generation can be used to create soft reconfigurable macros---tightly sequenced prespecified operations placed in the reconfigurable fabric.
---
paper_title: Hardware/software instruction set configurability for system-on-chip processors

paper_content:

New application-focused system-on-chip platforms motivate new application-specific processors. Configurable and extensible processor architectures offer the efficiency of tuned logic solutions with the flexibility of standard high-level programming methodology. Automated extension of processor function units and the associated software environment - compilers, debuggers, simulators and real-time operating systems - satisfies these needs. At the same time, designing at the level of software and instruction set architecture significantly shortens the design cycle and reduces verification effort and risk. This paper describes the key dimensions of extensibility within the processor architecture, the instruction set extension description language and the means of automatically extending the software environment from that description. It also describes two groups of benchmarks, EEMBC's Consumer and Telecommunications suites, that show 20 to 40 times acceleration of a broad set of algorithms through application-specific instruction set extension, relative to high performance RISC processors.
---
paper_title: Lx: a technology platform for customizable VLIW embedded processing

paper_content:

Lx is a scalable and customizable VLIW processor technology platform designed by Hewlett-Packard and STMicroelectronics that allows variations in instruction issue width, the number and capabilities of structures and the processor instruction set. For Lx we developed the architecture and software from the beginning to support both scalability (variable numbers of identical processing resources) and customizability (special purpose resources). In this paper we consider the following issues. When is customization or scaling beneficial? How can one determine the right degree of customization or scaling for a particular application domain? What architectural compromises were made in the Lx project to contain the complexity inherent in a customizable and scalable processor family? The experiments described in the paper show that specialization for an application domain is effective, yielding large gains in price/performance ratio. We also show how scaling machine resources scales performance, although not uniformly across all applications. Finally we show that customization on an application-by-application basis is today still very dangerous and much remains to be done for it to become a viable solution.
---
paper_title: Garp: a MIPS processor with a reconfigurable coprocessor

paper_content:

Typical reconfigurable machines exhibit shortcomings that make them less than ideal for general-purpose computing. The Garp Architecture combines reconfigurable hardware with a standard MIPS processor on the same die to retain the better features of both. Novel aspects of the architecture are presented, as well as a prototype software environment and preliminary performance results. Compared to an UltraSPARC, a Garp of similar technology could achieve speedups ranging from a factor of 2 to as high as a factor of 24 for some useful applications.
---
paper_title: Automatic Design of Computer Instruction Sets

paper_content:

This dissertation presents the thesis that good and usable instruction sets can be automatically derived for a specified data path and benchmark set. This is achieved by a multistep process: generating execution traces for the benchmark programs, sampling these traces to form a large set of small code segments, optimally recompiling these segments using exhaustive search, and finding the cover of the new instructions generated that optimizes the performance metric. The complete process is illustrated by generating an instruction set for a processor optimized for executing compiled Prolog programs. The generated instruction set is compared with the hand-designed VLSI-BAM instruction set. The automatically designed instruction set is smaller and has only a few percent less performance on the benchmark programs. This result is an improvement for a metric which includes both instruction set size and performance. Thus automatically derived instruction sets can be as good as or better than manually derived ones.
---
paper_title: Accelerator Data-Path Synthesis for High-Throughput Signal Processing Applications

paper_content:

From the Publisher: ::: Accelerator Data-Path Synthesis for High-Throughput Signal Processing Applications is the first book to show how to use high-level synthesis techniques to cope with the stringent timing requirements of complex high-throughput real-time signal and data processing. The book describes the state-of-the-art in architectural synthesis for complex high-throughput real-time processing. Unlike many other, the Synthesis approach used in this book targets an architecture style or an application domain. This approach is thus heavily application-driven and this is illustrated in the book by several realistic demonstration examples used throughout. Accelerator Data-Path Synthesis for High-Throughput Signal Processing Applications focuses on domains where application-specific high-speed solutions are attractive such as significant parts of audio, telecom, instrumentation, speech, robotics, medical and automotive processing, image and video processing, TV, multi-media radar, sonar, etc. Moreover, it addresses mainly the steps above the traditional scheduling and allocation tasks which focus on scalar operations and data. Accelerator Data-Path Synthesis for High-Throughput Signal Processing Applications is of interest to researchers, senior design engineers and CAD managers both in academia and industry. It provides an excellent overview of what capabilities to expect from future practical design tools and includes an extensive bibliography.
---
paper_title: Designing domain-specific processors

paper_content:

We present a semi-automated method for the detection and exploitation of application domain specific instruction set extensions for embedded (VLIW) processors. It consists of three steps: the first step detects frequently occurring operation patterns, in the second step, the patterns are grouped and implemented in a number of Special Function Units (SFUs) and the third step incorporates the custom operations into the code generation process. Experiments show that the SFUs generated and exploited with our methodology can result in architectures that perform up to 30% better than architectures of the same cost without SFUs.
---
paper_title: An integer linear programming approach for identifying instruction-set extensions

paper_content:

This paper presents an Integer Linear Programming (ILP) approach to the instruction-set extension identification problem. An algorithm that iteratively generates and solves a set of ILP problems in order to generate a set of templates is proposed. A selection algorithm that ranks the generated templates based on isomorphism testing and potential evaluation is described. A Trimaran based framework is used to evaluate the quality of the instructions generated by the technique. Speed-up results of up to 7.5 are observed.
---
paper_title: A Retargetable Framework for Automated Discovery of Custom Instructions

paper_content:

The problem of efficiently mapping a software application onto an extensible processor has received considerable attention. However, except for specialized kinds of computation accelerators, end-to-end studies of the problems are hard to find in the literature. We propose a classification of previous work on the mapping problem; we then frame previous results into this classification, and propose a new framework for solving this problem. By dividing the problem into several parts-some of them solved exactly, some of them relying on greedy algorithms-we provide a generic scheme that can be adapted to different kinds of hardware accelerators. We implemented our approach on top of a GCC-based compiler toolchain for extensible processors. Benchmarks taken from MiBench show a speedups up to 6.74 x using the SimpleScalar/ARM cycle-exact simulator.
---
paper_title: Fast instruction set customization

paper_content:

This work proposes an approach to tune embedded processor datapaths toward a specific application, so as to maximize the application performance. We customize the computation capabilities of a base processor, by extending its instruction set to include custom operations which are implemented as new specialized functional units. We describe an automatic methodology to select the custom instructions from the given application code, in a way that there is no need of compensation code or other modifications in the application, simplifying the code generation. By using the ArchC architecture description language, fast compilation and simulation of the resulting customized processor code are achieved, considerably reducing the turnaround time required to evaluate the best set of custom operations. Experimental results show that our framework provides large performance improvements (up to 3.6 times), when compared to the base general-purpose processor, while significantly speeding up the design process.
---
paper_title: Processor acceleration through automated instruction set customization

paper_content:

Application-specific extensions to the computational capabilities of a processor provide an efficient mechanism to meet the growing performance and power demands of embedded applications. Hardware, in the form of new function units (or co-processors), and the corresponding instructions, are added to a baseline processor to meet the critical computational demands of a target application. The central challenge with this approach is the large degree of human effort required to identify and create the custom hardware units, as well as porting the application to the extended processor. In this paper, we present the design of a system to automate the instruction set customization process. A dataflow graph design space exploration engine efficiently identifies profitable computation subgraphs from which to create custom hardware, without artificially constraining their size or shape. The system also contains a compiler subgraph matching framework that identifies opportunities to exploit and generalize the hardware to support more computation graphs. We demonstrate the effectiveness of this system across a range of application domains and study the applicability of the custom hardware across the domain.
---
paper_title: Custom-instruction synthesis for extensible-processor platforms

paper_content:

Efficiency and flexibility are critical, but often conflicting, design goals in embedded system design. The recent emergence of extensible processors promises a favorable tradeoff between efficiency and flexibility, while keeping design turnaround times short. Current extensible processor design flows automate several tedious tasks, but typically require designers to manually select the parts of the program that are to be implemented as custom instructions. In this work, we describe an automatic methodology to select custom instructions to augment an extensible processor, in order to maximize its efficiency for a given application program. We demonstrate that the number of custom instruction candidates grows rapidly with program size, leading to a large design space, and that the quality (speedup) of custom instructions varies significantly across this space, motivating the need for the proposed flow. Our methodology features cost functions to guide the custom instruction selection process, as well as static and dynamic pruning techniques to eliminate inferior parts of the design space from consideration. Furthermore, we employ a two-stage process, wherein a limited number of promising instruction candidates are first short-listed using efficient selection criteria, and then evaluated in more detail through cycle-accurate instruction set simulation and synthesis of the corresponding hardware, to identify the custom instruction combinations that result in the highest program speedup or maximize speedup under a given area constraint. We have evaluated the proposed techniques using a state-of-the-art extensible processor platform, in the context of a commercial design flow. Experiments with several benchmark programs indicate that custom processors synthesized using automatic custom instruction selection can result in large improvements in performance (up to 5.4/spl times/, an average of 3.4/spl times/), energy (up to 4.5/spl times/, an average of 3.2/spl times/), and energy-delay products (up to 24.2/spl times/, an average of 12.6/spl times/), while speeding up the design process significantly.
---
paper_title: Automated custom instruction generation for domain-specific processor acceleration

paper_content:

Application-specific extensions to the computational capabilities of a processor provide an efficient mechanism to meet the growing performance and power demands of embedded applications. Hardware, in the form of new function units (or coprocessors), and the corresponding instructions are added to a baseline processor to meet the critical computational demands of a target application. In this paper, the design of a system to automate the instruction set customization process is presented. A dataflow graph design space exploration engine efficiently identifies computation subgraphs to create custom hardware and a compiler subgraph matching framework seamlessly exploits this hardware. We demonstrate the effectiveness of this system across a range of application domains and study the applicability of the custom hardware across an entire application domain. Generalization techniques are presented which enable the application-specific hardware to be more effectively used across a domain.
---
paper_title: Automatic Application-Specific Instruction-Set Extensions Under Microarchitectural Constraints

paper_content:

This paper presents a methodology for automatically designing Instruction-Set Extensions in embedded processors. Many commercially available CPUs now offer the possibility of extending their instruction set for a specific application. Their tool chains typically support manual experimentations, but algorithms that can define the set of customised functional units most beneficial for a given applications are missing. Only a few algorithms exist but are severely limited in the type and size of operation clusters they can choose and hence reduce significantly the effectiveness of specialisation. A more general algorithm is presented here which selects maximal-speedup convex subgraphs of the application data-flow graph under fundamental microarchitectural constraints, and which improves significantly on the state of the art.
---
paper_title: Automatic instruction set extension and utilization for embedded processors

paper_content:

There is a growing demand for application-specific embedded processors in system-on-a-chip designs. Current tools and design methodologies often require designers to manually specialize the processor based on an application. Moreover, the use of the new complex instructions added to the processor is often left to designers' ingenuity. We present a solution that automatically groups dataflow operations in the application software as potential new complex instructions. The set of possible instructions is then automatically used for code generation combined with high-level arithmetic optimizations using symbolic algebra. Symbolic arithmetic manipulations provide a novel and effective method for instruction selection that is necessary due to the complexity of the automatically identified instructions. We have used our methodology to automatically add new instructions to Tensilica processors for a set of examples. Our results show that our tools improve designers productivity and efficiently specialize an embedded processor for the given application such that the execution time is greatly improved.
---
paper_title: Application-specific instruction generation for configurable processor architectures

paper_content:

Designing an application-specific embedded system in nanometer technologies has become more difficult than ever due to the rapid increase in design complexity and manufacturing cost. Efficiency and flexibility must be carefully balanced to meet different application requirements. The recently emerged configurable and extensible processor architectures offer a favorable tradeoff between efficiency and flexibility, and a promising way to minimize certain important metrics (e.g., execution time, code size, etc.) of the embedded processors. This paper addresses the problem of generating the application-specific instructions to improve the execution speed for configurable processors. A set of algorithms, including pattern generation, pattern selection, and application mapping, are proposed to efficiently utilize the instruction set extensibility of the target configurable processor. Applications of our approach to several real-life benchmarks on the Altera Nios processor show encouraging performance speedup (2.75X on average and up to 3.73X in some cases).
---
paper_title: An efficient framework for dynamic reconfiguration of instruction-set customization

paper_content:

We present an efficient framework for dynamic reconfiguration of application-specific instruction-set customization. A key component of this framework is an iterative algorithm for temporal and spatial partitioning of the loop kernels. Our algorithm maximizes performance gain of an application while taking into consideration the dynamic reconfiguration cost. It selects the appropriate custom instruction-sets for the loops and maps them into appropriate configurations. We model the temporal partitioning problem as a k-way graph partitioning problem. A dynamic programming based solution is used for the spatial partitioning. Comprehensive experimental results indicate that our iterative algorithm is highly scalable while producing optimal or near-optimal (99% of the optimal) performance gain.
---
paper_title: Graph isomorphism and identification matrices: parallel algorithms

paper_content:

In this paper, we explore some properties of identification matrices and exhibit some uses of identification matrices in studying the graph isomorphism problem, a famous open problem. We show that, given two graphs in the form of a certain identification matrix, isomorphism can be tested efficiently in parallel if at least one matrix satisfies the circular 1s property, and more efficiently in parallel if at least one matrix satisfies the consecutive 1s property. Graphs which have identification matrices satisfying the consecutive 1s property include, among others, proper interval graphs and doubly convex bipartite graphs. The result presented here substantially broadens the class of graphs for which there are known efficient parallel isomorphism testing algorithms.
---
paper_title: Rapid configuration and instruction selection for an ASIP: a case study

paper_content:

We present a methodology that maximizes the performance of Tensilica based Application Specific Instruction-set Processor (ASIP) through instruction selection when an area constraint is given. Our approach rapidly selects from a set of pre-fabricated coprocessors/functional units from our library of pre-designed specific instructions (to evaluate our technology we use the Tensilica platform). As a result, we significantly increase application performance while area constraints are satisfied. Our methodology uses a combination of simulation, estimation and a pre-characterised library of instructions, to select the appropriate co-processors and instructions. We report that by selecting the appropriate coprocessors/functional units and specific TIE instructions, the total execution time of complex applications (we study a voice encoder/decoder), an application's performance can be reduced by up to 85% compared to the base implementation. Our estimator used in the system takes typically less than a second to estimate, with an average error rate of 4% (as compared to full simulation, which takes 45 minutes). The total selection process using our methodology takes 3-4 hours, while a full design space exploration using simulation would take several days.
---
paper_title: Partitioning by regularity extraction

paper_content:

The authors present a general methodology for extracting regularity at any level of hierarchy, and explore the problem of digital system partitioning by extraction of regularity. They consider system-level partitioning to demonstrate that regularity can lead to reduced design costs. The digital system is modeled with cyclic directed graphs. A prototype system based on these ideas has been built. Some examples are discussed. >
---
paper_title: Synthesis of Application Specific Instructions for Embedded DSP Software

paper_content:

Application specific instructions play an important role in reducing the required code size and increasing performance in embedded DSP systems. This paper describes a new approach to generate application specific instructions for DSP applications. The proposed approach is based on a modified subset-sum problem and supports multicycle complex instructions, as well as single-cycle instructions, while the previous state-of-the-art approaches generate only the single-cycle instructions or just select instructions from the fixed super-set of possible instructions. In addition, the proposed approach can also be applied to the case that instructions are predefined. Experimental results on real applications show that Various given constraints can be met by the generated set of application specific instructions without attaching special hardware accelerators.
---
paper_title: Instruction-set matching and selection for DSP and ASIP code generation

paper_content:

The increasing use of digital signal processors (DSPs) and application specific instruction-set processors (ASIPs) has put a strain on the perceived mature state of compiler technology. The presence of custom hardware for application-specific needs has introduced instruction types which are unfamiliar to the capabilities of traditional compilers. Thus, these traditional techniques can lead to inefficient and sparsely compacted machine microcode. In this paper, we introduce a novel instruction-set matching and selection methodology, based upon a rich representation useful for DSP and mixed control-oriented applications. This representation shows explicit behaviour that references architecture resource classes. This allows a wide range of instructions types to be captured in a pattern set. The pattern set has been organized in a manner such that matching is extremely efficient and retargeting to architectures with new instruction sets is well defined. The matching and selection algorithms have been implemented in a retargetable code generation system called CodeSyn. >
---
paper_title: Processor reconfiguration through instruction-set metamorphosis

paper_content:

The processor reconfiguration through instruction-set metamorphosis (PRISM) general-purpose architecture, which speeds up computationally intensive tasks by augmenting the core processor's functionality with new operations, is described. The PRISM approach adapts the configuration and fundamental operations of a core processing system to the computationally intensive portions of a targeted application. PRISM-1, an initial prototype system, is described, and experimental results that demonstrate the benefits of the PRISM concept are presented. >
---
paper_title: Processor acceleration through automated instruction set customization

paper_content:

Application-specific extensions to the computational capabilities of a processor provide an efficient mechanism to meet the growing performance and power demands of embedded applications. Hardware, in the form of new function units (or co-processors), and the corresponding instructions, are added to a baseline processor to meet the critical computational demands of a target application. The central challenge with this approach is the large degree of human effort required to identify and create the custom hardware units, as well as porting the application to the extended processor. In this paper, we present the design of a system to automate the instruction set customization process. A dataflow graph design space exploration engine efficiently identifies profitable computation subgraphs from which to create custom hardware, without artificially constraining their size or shape. The system also contains a compiler subgraph matching framework that identifies opportunities to exploit and generalize the hardware to support more computation graphs. We demonstrate the effectiveness of this system across a range of application domains and study the applicability of the custom hardware across the domain.
---
paper_title: Exact and approximate algorithms for the extension of embedded processor instruction sets

paper_content:

In embedded computing, cost, power, and performance constraints call for the design of specialized processors, rather than for the use of the existing off-the-shelf solutions. While the design of these application-specific CPUs could be tackled from scratch, a cheaper and more effective option is that of extending the existing processors and toolchains. Extensibility is indeed a feature now offered in real designs, e.g., by processors such as Tensilica Xtensa [T. R. Halfhill, Microprocess Rep., 2003], ARC ARCtangent [T. R. Halfhill, Microprocess Rep., 2000], STMicroelectronics ST200 [P. Faraboschi, G. Brown, J. A. Fisher, G. Desoli, and F. Homewood, Proc. 27th Annu. Int. Symp. Computer Architecture, 2000, p. 203], and MIPS CorExtend [T. R. Halfhill, Microprocess Rep., 2003]. While all these processors provide development environments with simulation capabilities for evaluating efficiently hand-crafted solutions, the tools to identify automatically the best processor configuration for a given application are less common. In particular, solutions to choose specialized instruction-set extensions (ISEs) have been investigated in the past years but are still seldom part of commercial toolchains. This paper provides a formal methodology and a set of algorithms that help address the problem. It proposes exact algorithms to derive optimal ISEs; exact identification of a single ISE is applicable to basic blocks of up to 1500 assembler-like instructions. This paper also introduces approximate methods that can process basic blocks of larger size. Results show that the described algorithms find solutions close to those that a designer would obtain by a detailed study of the application code. Both heuristic and exact algorithms find ISEs able to speed up unextended processors up to 5.0x. State-of-the-art comparisons show that the presented algorithms outperform existing ones by up to 2.6x
---
paper_title: Automatic Application-Specific Instruction-Set Extensions Under Microarchitectural Constraints

paper_content:

This paper presents a methodology for automatically designing Instruction-Set Extensions in embedded processors. Many commercially available CPUs now offer the possibility of extending their instruction set for a specific application. Their tool chains typically support manual experimentations, but algorithms that can define the set of customised functional units most beneficial for a given applications are missing. Only a few algorithms exist but are severely limited in the type and size of operation clusters they can choose and hence reduce significantly the effectiveness of specialisation. A more general algorithm is presented here which selects maximal-speedup convex subgraphs of the application data-flow graph under fundamental microarchitectural constraints, and which improves significantly on the state of the art.
---
paper_title: Instruction generation for hybrid reconfigurable systems

paper_content:

Future computing systems need to balance flexibility, specialization, and performance in order to meet market demands and the computing power required by new applications. Instruction generation is a vital component for determining these trade-offs. In this work, we present theory and an algorithm for instruction generation. The algorithm profiles a dataflow graph and iteratively contracts edges to create the templates. We discuss how to target the algorithm toward the novel problem of instruction generation for hybrid reconfigurable systems. In particular, we target the Strategically Programmable System, which embeds complex computational units such as ALUs, IP blocks, and so on into a configurable fabric. We argue that an essential compilation step for these systems is instruction generation, as it is needed to specify the functionality of the embedded computational units. In addition, instruction generation can be used to create soft reconfigurable macros---tightly sequenced prespecified operations placed in the reconfigurable fabric.
---
paper_title: Designing domain-specific processors

paper_content:

We present a semi-automated method for the detection and exploitation of application domain specific instruction set extensions for embedded (VLIW) processors. It consists of three steps: the first step detects frequently occurring operation patterns, in the second step, the patterns are grouped and implemented in a number of Special Function Units (SFUs) and the third step incorporates the custom operations into the code generation process. Experiments show that the SFUs generated and exploited with our methodology can result in architectures that perform up to 30% better than architectures of the same cost without SFUs.
---
paper_title: New Ideas for Solving Covering Problems

paper_content:

Covering problems occur at several steps during logic synthesis including two-level minimization and DAG covering. This paper presents a better lower bound computation algorithm and two new pruning techniques that significantly improve the efficiency of covering problem solvers. We show that these techniques reduce by up to three orders of magnitude the time required to solve covering problems exactly.
---
paper_title: Automatic Application-Specific Instruction-Set Extensions Under Microarchitectural Constraints

paper_content:

This paper presents a methodology for automatically designing Instruction-Set Extensions in embedded processors. Many commercially available CPUs now offer the possibility of extending their instruction set for a specific application. Their tool chains typically support manual experimentations, but algorithms that can define the set of customised functional units most beneficial for a given applications are missing. Only a few algorithms exist but are severely limited in the type and size of operation clusters they can choose and hence reduce significantly the effectiveness of specialisation. A more general algorithm is presented here which selects maximal-speedup convex subgraphs of the application data-flow graph under fundamental microarchitectural constraints, and which improves significantly on the state of the art.
---
paper_title: On solving covering problems

paper_content:

The set covering problem and the minimum cost assignment problem (respectively known as unate and binate covering problem) arise throughout the logic synthesis flow. This paper investigates the complexity and approximation ratio of two lower bound computation algorithms from both a theoretical and practical point of view. It also presents a new pruning technique that takes advantage of the partitioning.
---
paper_title: Designing domain-specific processors

paper_content:

We present a semi-automated method for the detection and exploitation of application domain specific instruction set extensions for embedded (VLIW) processors. It consists of three steps: the first step detects frequently occurring operation patterns, in the second step, the patterns are grouped and implemented in a number of Special Function Units (SFUs) and the third step incorporates the custom operations into the code generation process. Experiments show that the SFUs generated and exploited with our methodology can result in architectures that perform up to 30% better than architectures of the same cost without SFUs.
---
paper_title: Automatic selection of application-specific instruction-set extensions

paper_content:

In this paper, we present a general and an efficient algorithm for automatic selection of new application-specific instructions under hardware resources constraints. The instruction selection is formulated as an ILP problem and efficient solvers can be used for finding the optimal solution. An important feature of our algorithm is that it is not restricted to basic-block level nor does it impose any limitation on the number of the newly added instructions or on the number of the inputs/outputs of these instructions. The presented results show that a significant overall application speedup is achieved even for large kernels (for ADPCM decoder the speedup ranges from x1.2 to x3.7) and that our algorithm compares well with other state-of-art algorithms for automatic instruction set extensions.
---
paper_title: Disjoint Pattern Enumeration for Custom Instructions Identification

paper_content:

Extensible processors allow addition of application-specific custom instructions to the core instruction set architecture. These custom instructions are selected through an analysis of the program's dataflow graphs. The characteristics of certain applications and the modern compiler optimization techniques (e.g., loop unrolling, region formation, etc.) have lead to substantially larger dataflow graphs. Hence, it is computationally expensive to automatically select the optimal set of custom instructions. Heuristic techniques are often employed to quickly search the design space. In order to leverage full potential of custom instructions, our previous work proposed an efficient algorithm for exact enumeration of all possible candidate instructions (or patterns) given the dataflow graphs. But the algorithm was restricted to connected computation patterns. In this paper, we describe an efficient algorithm to generate all feasible disjoint patterns starting with the set of feasible connected patterns. Compared to the state-of-the-art technique, our algorithm achieves orders of magnitude speedup while generating the identical set of candidate disjoint patterns.
---
paper_title: Processor acceleration through automated instruction set customization

paper_content:

Application-specific extensions to the computational capabilities of a processor provide an efficient mechanism to meet the growing performance and power demands of embedded applications. Hardware, in the form of new function units (or co-processors), and the corresponding instructions, are added to a baseline processor to meet the critical computational demands of a target application. The central challenge with this approach is the large degree of human effort required to identify and create the custom hardware units, as well as porting the application to the extended processor. In this paper, we present the design of a system to automate the instruction set customization process. A dataflow graph design space exploration engine efficiently identifies profitable computation subgraphs from which to create custom hardware, without artificially constraining their size or shape. The system also contains a compiler subgraph matching framework that identifies opportunities to exploit and generalize the hardware to support more computation graphs. We demonstrate the effectiveness of this system across a range of application domains and study the applicability of the custom hardware across the domain.
---
paper_title: Scalable custom instructions identification for instruction-set extensible processors

paper_content:

Extensible processors allow addition of application-specific custom instructions to the core instruction set architecture. However, it is computationally expensive to automatically select the optimal set of custom instructions. Therefore, heuristic techniques are often employed to quickly search the design space. In this paper, we present an efficient algorithm for exact enumeration of all possible candidate instructions given the dataflow graph (DFG) corresponding to a code fragment. Even though this is similar to the "subgraph enumeration" problem (which is exponential), we find that most subgraphs are not feasible candidates for various reasons. In fact, the number of candidates is quite small compared to the size of the DFG. Compared to previous approaches, our technique achieves orders of magnitude speedup in enumerating these candidate custom instructions for very large DFGs.
---
paper_title: Exact and approximate algorithms for the extension of embedded processor instruction sets

paper_content:

In embedded computing, cost, power, and performance constraints call for the design of specialized processors, rather than for the use of the existing off-the-shelf solutions. While the design of these application-specific CPUs could be tackled from scratch, a cheaper and more effective option is that of extending the existing processors and toolchains. Extensibility is indeed a feature now offered in real designs, e.g., by processors such as Tensilica Xtensa [T. R. Halfhill, Microprocess Rep., 2003], ARC ARCtangent [T. R. Halfhill, Microprocess Rep., 2000], STMicroelectronics ST200 [P. Faraboschi, G. Brown, J. A. Fisher, G. Desoli, and F. Homewood, Proc. 27th Annu. Int. Symp. Computer Architecture, 2000, p. 203], and MIPS CorExtend [T. R. Halfhill, Microprocess Rep., 2003]. While all these processors provide development environments with simulation capabilities for evaluating efficiently hand-crafted solutions, the tools to identify automatically the best processor configuration for a given application are less common. In particular, solutions to choose specialized instruction-set extensions (ISEs) have been investigated in the past years but are still seldom part of commercial toolchains. This paper provides a formal methodology and a set of algorithms that help address the problem. It proposes exact algorithms to derive optimal ISEs; exact identification of a single ISE is applicable to basic blocks of up to 1500 assembler-like instructions. This paper also introduces approximate methods that can process basic blocks of larger size. Results show that the described algorithms find solutions close to those that a designer would obtain by a detailed study of the application code. Both heuristic and exact algorithms find ISEs able to speed up unextended processors up to 5.0x. State-of-the-art comparisons show that the presented algorithms outperform existing ones by up to 2.6x
---
paper_title: HW/SW partitioning and code generation of embedded control applications on a reconfigurable architecture platform

paper_content:

This paper studies the use of a reconfigurable architecture platform for embedded control applications aimed at improving real time performance. The hw/sw codesign methodology from POLIS is used. It starts from high-level specifications, optimizes an intermediate model of computation (Extended Finite State Machines) and derives both hardware and software, based on performance constraints. We study a particular architecture platform, which consists of a general purpose processor core, augmented with a reconfigurable function unit and data-path to improve run time performance. A new mapping flow and algorithms to partition hardware and software are proposed to generate implementations that best utilize this architecture. Encouraging preliminary results are shown for automotive electronic control examples.
---
paper_title: Automatic Application-Specific Instruction-Set Extensions Under Microarchitectural Constraints

paper_content:

This paper presents a methodology for automatically designing Instruction-Set Extensions in embedded processors. Many commercially available CPUs now offer the possibility of extending their instruction set for a specific application. Their tool chains typically support manual experimentations, but algorithms that can define the set of customised functional units most beneficial for a given applications are missing. Only a few algorithms exist but are severely limited in the type and size of operation clusters they can choose and hence reduce significantly the effectiveness of specialisation. A more general algorithm is presented here which selects maximal-speedup convex subgraphs of the application data-flow graph under fundamental microarchitectural constraints, and which improves significantly on the state of the art.
---
paper_title: Application-specific instruction generation for configurable processor architectures

paper_content:

Designing an application-specific embedded system in nanometer technologies has become more difficult than ever due to the rapid increase in design complexity and manufacturing cost. Efficiency and flexibility must be carefully balanced to meet different application requirements. The recently emerged configurable and extensible processor architectures offer a favorable tradeoff between efficiency and flexibility, and a promising way to minimize certain important metrics (e.g., execution time, code size, etc.) of the embedded processors. This paper addresses the problem of generating the application-specific instructions to improve the execution speed for configurable processors. A set of algorithms, including pattern generation, pattern selection, and application mapping, are proposed to efficiently utilize the instruction set extensibility of the target configurable processor. Applications of our approach to several real-life benchmarks on the Altera Nios processor show encouraging performance speedup (2.75X on average and up to 3.73X in some cases).
---
paper_title: Automatic topology-based identification of instruction-set extensions for embedded processors

paper_content:

The need for high performance in ASIC embedded processors, coupled with aggressive energy and area goals, is pushing researchers and designers toward processor specialisation for a given application-domain. In this paper, specialisation is addressed through introduction of Ad-hoc Functional Units special arithmetic/logic units added to a traditional architecture to perform domain-specific complex operations.
---
paper_title: Designing domain-specific processors

paper_content:

We present a semi-automated method for the detection and exploitation of application domain specific instruction set extensions for embedded (VLIW) processors. It consists of three steps: the first step detects frequently occurring operation patterns, in the second step, the patterns are grouped and implemented in a number of Special Function Units (SFUs) and the third step incorporates the custom operations into the code generation process. Experiments show that the SFUs generated and exploited with our methodology can result in architectures that perform up to 30% better than architectures of the same cost without SFUs.
---
paper_title: Disjoint Pattern Enumeration for Custom Instructions Identification

paper_content:

Extensible processors allow addition of application-specific custom instructions to the core instruction set architecture. These custom instructions are selected through an analysis of the program's dataflow graphs. The characteristics of certain applications and the modern compiler optimization techniques (e.g., loop unrolling, region formation, etc.) have lead to substantially larger dataflow graphs. Hence, it is computationally expensive to automatically select the optimal set of custom instructions. Heuristic techniques are often employed to quickly search the design space. In order to leverage full potential of custom instructions, our previous work proposed an efficient algorithm for exact enumeration of all possible candidate instructions (or patterns) given the dataflow graphs. But the algorithm was restricted to connected computation patterns. In this paper, we describe an efficient algorithm to generate all feasible disjoint patterns starting with the set of feasible connected patterns. Compared to the state-of-the-art technique, our algorithm achieves orders of magnitude speedup while generating the identical set of candidate disjoint patterns.
---
paper_title: A Fast Custom Instructions Identification Algorithm based on Basic Convex Pattern Model for Supporting ASIP Automated Design

paper_content:

To improve the computation efficiency of the application specific instruction-set processor (ASIP), a strategy of hardware/software collaborative design is usually utilized. In this process, the auto-customization of specific instruction set has always been a key part to support the automated design of ASIP. The key issue of this problem is how to effectively reduce the huge exponential exploration space in the instruction identification process. To address this issue, we first formulate it as a feasible sub-graph enumeration problem under multiple constraints, and then propose a fast instruction identification algorithm based on a new model called basic convex pattern (BCP). The kernel technique in this algorithm is the transformation from the graph exploration to the formula-based computations. The experimental results have indicated that the proposed algorithm has a distinct reduction in the execution time.
---
paper_title: Automatic Application-Specific Instruction-Set Extensions Under Microarchitectural Constraints

paper_content:

This paper presents a methodology for automatically designing Instruction-Set Extensions in embedded processors. Many commercially available CPUs now offer the possibility of extending their instruction set for a specific application. Their tool chains typically support manual experimentations, but algorithms that can define the set of customised functional units most beneficial for a given applications are missing. Only a few algorithms exist but are severely limited in the type and size of operation clusters they can choose and hence reduce significantly the effectiveness of specialisation. A more general algorithm is presented here which selects maximal-speedup convex subgraphs of the application data-flow graph under fundamental microarchitectural constraints, and which improves significantly on the state of the art.
---
paper_title: Disjoint Pattern Enumeration for Custom Instructions Identification

paper_content:

Extensible processors allow addition of application-specific custom instructions to the core instruction set architecture. These custom instructions are selected through an analysis of the program's dataflow graphs. The characteristics of certain applications and the modern compiler optimization techniques (e.g., loop unrolling, region formation, etc.) have lead to substantially larger dataflow graphs. Hence, it is computationally expensive to automatically select the optimal set of custom instructions. Heuristic techniques are often employed to quickly search the design space. In order to leverage full potential of custom instructions, our previous work proposed an efficient algorithm for exact enumeration of all possible candidate instructions (or patterns) given the dataflow graphs. But the algorithm was restricted to connected computation patterns. In this paper, we describe an efficient algorithm to generate all feasible disjoint patterns starting with the set of feasible connected patterns. Compared to the state-of-the-art technique, our algorithm achieves orders of magnitude speedup while generating the identical set of candidate disjoint patterns.
---
paper_title: A Linear Complexity Algorithm for the Generation of Multiple Input Single Output Instructions of Variable Size ⋆

paper_content:

The Instruction-Set extension problem has been one of the major topics in the last years and it is the addition of a set of new complex instructions to a given Instruction-Set. This problem in its general formulation requires an exhaustive search of the design space to identify the candidate instructions. This search turns into an exponential complexity of the solution. In this paper we propose an algorithm for the generation of Multiple Input Single Output instructions of variable size which can be directly selected or combined for Instruction-Set extension. Additionally, the algorithm is suitable for inclusion in a design flow for automatic generation of MIMO instructions. The proposed algorithm is not restricted to basic-block level and has linear complexity with the number of processed elements.
---
paper_title: An algorithm for mapping loops onto coarse-grained reconfigurable architectures

paper_content:

With the increasing demand for flexible yet highly efficient architecture platforms for media applications, there is a growing interest in the Coarse-grained Reconfigurable Architectures (CRAs). While many CRAs have demonstrated impressive performance improvement, the lack of compilation technology for such architectures causes a bottleneck in the current design process. In this paper, we present a novel mapping algorithm designed to support Reconfigurable ALU Array (RAA) architectures, that represent a significant class of CRAs. More specifically we present a core mapping algorithm that addresses the problem of placing and routing the operations of a loop body onto the ALU array, to be executed in a loop pipelined fashion. Experimental results using our mapping algorithm on a typical RAA show that our algorithm not only has very fast compilation time but can also generate quality mappings exhibiting high memory bandwidth utilization and low global interconnection requirements. Comparison with manual mapping also indicates that our algorithm can generate near-optimal mappings for several loops.
---
paper_title: Automatic instruction set extension and utilization for embedded processors

paper_content:

There is a growing demand for application-specific embedded processors in system-on-a-chip designs. Current tools and design methodologies often require designers to manually specialize the processor based on an application. Moreover, the use of the new complex instructions added to the processor is often left to designers' ingenuity. We present a solution that automatically groups dataflow operations in the application software as potential new complex instructions. The set of possible instructions is then automatically used for code generation combined with high-level arithmetic optimizations using symbolic algebra. Symbolic arithmetic manipulations provide a novel and effective method for instruction selection that is necessary due to the complexity of the automatically identified instructions. We have used our methodology to automatically add new instructions to Tensilica processors for a set of examples. Our results show that our tools improve designers productivity and efficiently specialize an embedded processor for the given application such that the execution time is greatly improved.
---
paper_title: Application-specific instruction generation for configurable processor architectures

paper_content:

Designing an application-specific embedded system in nanometer technologies has become more difficult than ever due to the rapid increase in design complexity and manufacturing cost. Efficiency and flexibility must be carefully balanced to meet different application requirements. The recently emerged configurable and extensible processor architectures offer a favorable tradeoff between efficiency and flexibility, and a promising way to minimize certain important metrics (e.g., execution time, code size, etc.) of the embedded processors. This paper addresses the problem of generating the application-specific instructions to improve the execution speed for configurable processors. A set of algorithms, including pattern generation, pattern selection, and application mapping, are proposed to efficiently utilize the instruction set extensibility of the target configurable processor. Applications of our approach to several real-life benchmarks on the Altera Nios processor show encouraging performance speedup (2.75X on average and up to 3.73X in some cases).
---
paper_title: Automatic topology-based identification of instruction-set extensions for embedded processors

paper_content:

The need for high performance in ASIC embedded processors, coupled with aggressive energy and area goals, is pushing researchers and designers toward processor specialisation for a given application-domain. In this paper, specialisation is addressed through introduction of Ad-hoc Functional Units special arithmetic/logic units added to a traditional architecture to perform domain-specific complex operations.
---
paper_title: An integer linear programming approach for identifying instruction-set extensions

paper_content:

This paper presents an Integer Linear Programming (ILP) approach to the instruction-set extension identification problem. An algorithm that iteratively generates and solves a set of ILP problems in order to generate a set of templates is proposed. A selection algorithm that ranks the generated templates based on isomorphism testing and potential evaluation is described. A Trimaran based framework is used to evaluate the quality of the instructions generated by the technique. Speed-up results of up to 7.5 are observed.
---
paper_title: Synthesis of Application Specific Instructions for Embedded DSP Software

paper_content:

Application specific instructions play an important role in reducing the required code size and increasing performance in embedded DSP systems. This paper describes a new approach to generate application specific instructions for DSP applications. The proposed approach is based on a modified subset-sum problem and supports multicycle complex instructions, as well as single-cycle instructions, while the previous state-of-the-art approaches generate only the single-cycle instructions or just select instructions from the fixed super-set of possible instructions. In addition, the proposed approach can also be applied to the case that instructions are predefined. Experimental results on real applications show that Various given constraints can be met by the generated set of application specific instructions without attaching special hardware accelerators.
---
paper_title: Automatic selection of application-specific instruction-set extensions

paper_content:

In this paper, we present a general and an efficient algorithm for automatic selection of new application-specific instructions under hardware resources constraints. The instruction selection is formulated as an ILP problem and efficient solvers can be used for finding the optimal solution. An important feature of our algorithm is that it is not restricted to basic-block level nor does it impose any limitation on the number of the newly added instructions or on the number of the inputs/outputs of these instructions. The presented results show that a significant overall application speedup is achieved even for large kernels (for ADPCM decoder the speedup ranges from x1.2 to x3.7) and that our algorithm compares well with other state-of-art algorithms for automatic instruction set extensions.
---
paper_title: Introduction of local memory elements in instruction set extensions

paper_content:

Automatic generation of Instruction Set Extensions (ISEs), to be executed on a custom processing unit or a coprocessor is an important step towards processor customization. A typical goal of a manual designer is to combine a large number of atomic instructions into an ISE satisfying microarchitectural constraints. However, memory operations pose a challenge for previous ISE approaches by limiting the size of the resulting instruction. In this paper, we introduce memory elements into custom units which result in ISEs closer to those sought after by the designers. We consider two kinds of memory elements for mapping to the specialized hardware: small hardware tables and architecturally-visible state registers. We devised a genetic algorithm to specifically exploit opportunities of introducing memory elements during ISE generation. Finally, we demonstrate the effectiveness of our approach by a detailed study of the variation in performance, area and energy in the presence of the generated ISEs, on a number of MediaBench, EEMBC and cryptographic applications. With the introduction of memory, the average speedup varied from 2.7X to 5X depending on the architectural configuration with a nominal area overhead. Moreover, we obtained an average energy reduction of 26% with respect to a 32-KB cache.
---
paper_title: Disjoint Pattern Enumeration for Custom Instructions Identification

paper_content:

Extensible processors allow addition of application-specific custom instructions to the core instruction set architecture. These custom instructions are selected through an analysis of the program's dataflow graphs. The characteristics of certain applications and the modern compiler optimization techniques (e.g., loop unrolling, region formation, etc.) have lead to substantially larger dataflow graphs. Hence, it is computationally expensive to automatically select the optimal set of custom instructions. Heuristic techniques are often employed to quickly search the design space. In order to leverage full potential of custom instructions, our previous work proposed an efficient algorithm for exact enumeration of all possible candidate instructions (or patterns) given the dataflow graphs. But the algorithm was restricted to connected computation patterns. In this paper, we describe an efficient algorithm to generate all feasible disjoint patterns starting with the set of feasible connected patterns. Compared to the state-of-the-art technique, our algorithm achieves orders of magnitude speedup while generating the identical set of candidate disjoint patterns.
---
paper_title: Exploiting pipelining to relax register-file port constraints of instruction-set extensions

paper_content:

Customisable embedded processors are becoming available on the market, thus making it possible for designers to speed up execution of applications by using Application-specific Functional Units (AFUs), implementing Instruction-Set Extensions (ISEs). While these processors have become available, the state of the art on automatic ISE identification is improving; many algorithms are being proposed for choosing, given the application's source code, the best ISEs under various constraints. Read and write ports between the AFUs and the processor register file are an expensive asset, fixed in the microarchitecture---some processors indeed only allow two read and one write ports---and, on the other hand, a large availability of inputs and outputs to and from the AFUs exposes high speedup. This paper proposes a solution to the limitation of actual register file ports by serialising register file access and therefore addressing multi-cycle read and write. It does so in an innovative way for two reasons: (1) it exploits and brings forward the progress in ISE identification under constraint [1, 16, 4, 19] and (2) it combines register file access serialisation with pipelining in order to obtain the best global solution. This paper proposes an algorithm for scheduling graphs---corresponding to ISEs---under input/output constraint; experiments show that by using the proposed method applications can be sped-up tangibly: speedup for low I/O constraints is 32% better on average, and 65% better at best, than that obtained by state of the art techniques.
---
paper_title: Scalable custom instructions identification for instruction-set extensible processors

paper_content:

Extensible processors allow addition of application-specific custom instructions to the core instruction set architecture. However, it is computationally expensive to automatically select the optimal set of custom instructions. Therefore, heuristic techniques are often employed to quickly search the design space. In this paper, we present an efficient algorithm for exact enumeration of all possible candidate instructions given the dataflow graph (DFG) corresponding to a code fragment. Even though this is similar to the "subgraph enumeration" problem (which is exponential), we find that most subgraphs are not feasible candidates for various reasons. In fact, the number of candidates is quite small compared to the size of the DFG. Compared to previous approaches, our technique achieves orders of magnitude speedup in enumerating these candidate custom instructions for very large DFGs.
---
paper_title: HW/SW partitioning and code generation of embedded control applications on a reconfigurable architecture platform

paper_content:

This paper studies the use of a reconfigurable architecture platform for embedded control applications aimed at improving real time performance. The hw/sw codesign methodology from POLIS is used. It starts from high-level specifications, optimizes an intermediate model of computation (Extended Finite State Machines) and derives both hardware and software, based on performance constraints. We study a particular architecture platform, which consists of a general purpose processor core, augmented with a reconfigurable function unit and data-path to improve run time performance. A new mapping flow and algorithms to partition hardware and software are proposed to generate implementations that best utilize this architecture. Encouraging preliminary results are shown for automotive electronic control examples.
---
paper_title: Automatic Application-Specific Instruction-Set Extensions Under Microarchitectural Constraints

paper_content:

This paper presents a methodology for automatically designing Instruction-Set Extensions in embedded processors. Many commercially available CPUs now offer the possibility of extending their instruction set for a specific application. Their tool chains typically support manual experimentations, but algorithms that can define the set of customised functional units most beneficial for a given applications are missing. Only a few algorithms exist but are severely limited in the type and size of operation clusters they can choose and hence reduce significantly the effectiveness of specialisation. A more general algorithm is presented here which selects maximal-speedup convex subgraphs of the application data-flow graph under fundamental microarchitectural constraints, and which improves significantly on the state of the art.
---
paper_title: Fast custom instruction identification by convex subgraph enumeration

paper_content:

Automatic generation of custom instruction processors from high-level application descriptions enables fast design space exploration, while offering very favorable performance and silicon area combinations. This work introduces a novel method for adapting the instruction set to match an application captured in a high-level language. A simplified model is used to find the optimal instructions via enumeration of maximal convex subgraphs of application data flow graphs (DFGs). Our experiments involving a set of multimedia and cryptography benchmarks show that an order of magnitude performance improvement can be achieved using only a limited amount of hardware resources. In most cases, our algorithm takes less than a second to execute.
---
paper_title: Rethinking custom ISE identification: a new processor-agnostic method

paper_content:

The last decade has witnessed the emergence of the Application Specific Instruction-set Processor (ASIP) as a viable platform for embedded systems. Extensible ASIPs allow the user to augment a base processor with Instruction Set Extensions (ISEs) that execute on Application Specific Functional Units (AFUs)-dedicated hardware that executes the ISEs. Due to the limited number of read and write ports in the register file of the base processor, the size and complexity of AFUs are generally limited. Recent work has focused on overcoming these constraints by serialising access to the register file. Apart from these complications, the primary challenge in the identification and selection of the best AFU is the modelling of AFU performance in the context of different base processors: once the base processor changes, the ISE identification and AFU selection process must be re-done from scratch. Exhaustive ISE/AFU enumeration methods are not scalable and generally fail for larger applications. To address this concern, a new approach to ISE/AFU identification is proposed. In particular, we show that the speedup model of ISEs/AFUs is independent of the specific details of the base processor, under fairly reasonable assumptions. The approach presented here significantly prunes the list of best ISE/AFU candidates compared to previous approaches. Experimentally, we observe the new approach produces optimal results on larger applications where prior approaches either fail or produce inferior results.
---
paper_title: Application Specific Datapath Extension with Distributed I/O Functional Units

paper_content:

Performance of an application can be improved through augmenting the processor with application specific functional units (AFUs). Usually a cluster of operations identified from the application forms the behavior of an AFU. Several researchers studied the impact of input and output (I/O) constraints for a legal operation cluster on the overall achievable speedup. The general observation is that the speedup potential grows with the relaxation of I/O constraints. Going further, in this paper, the authors investigate the speedup potential of AFUs in the absence of I/O constraints. Design challenge in the absence of I/O constraints is addressed in a very practical manner, through the identification of maximal convex subgraphs. Usually the available register ports are few but the number of inputs/outputs of the identified patterns are likely to be large. The authors solve the register port limitation by the design of distributed I/O functional units, in which the operands are communicated in multiple cycles. The experimental results show that selection of maximal clusters achieves average 50% higher speedup than selecting I/O constrained operation clusters. Also, our identification algorithm runs 2 to 3 orders faster than an exhaustive identification approach
---
paper_title: An Effective Heuristic Algorithm for the Traveling-Salesman Problem

paper_content:

This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric traveling-salesman problem. The procedure is based on a general approach to heuristics that is believed to have wide applicability in combinatorial optimization problems. The procedure produces optimum solutions for all problems tested, "classical" problems appearing in the literature, as well as randomly generated test problems, up to 110 cities. Run times grow approximately as n2; in absolute terms, a typical 100-city problem requires less than 25 seconds for one case GE635, and about three minutes to obtain the optimum with above 95 per cent confidence.
---
paper_title: New Ideas for Solving Covering Problems

paper_content:

Covering problems occur at several steps during logic synthesis including two-level minimization and DAG covering. This paper presents a better lower bound computation algorithm and two new pruning techniques that significantly improve the efficiency of covering problem solvers. We show that these techniques reduce by up to three orders of magnitude the time required to solve covering problems exactly.
---
paper_title: A new viewpoint on code generation for directed acyclic graphs

paper_content:

We present a new viewpoint on code generation for directed acyclic graphs (DAGs). Our formulation is based on binate covering , the problem of satisfying, with minimum cost, a set of disjunctive clauses, and can take into account commutativity of operators and of the machine model. An important contribution of this work is a set of necessary and sufficient conditions for a valid schedule to be derived, based on the notion of worms and worm-partitions . This set of conditions can be compactly expressed with clauses that relate scheduling to code selection. For the case of one-register machines, we can derive clauses that lead to generation of optimal code for the DAG. Recent advances in exact binate covering algorithms allows us to use this strategy to generate optimal code for large basic blocks. The optimal code generated by our algorithm results in significant reductions in overall code size.
---
paper_title: Automatic detection of recurring operation patterns

paper_content:

An important problem in the area of processor design for embedded systems is determining the proper instruction set architecture. Trade-offs have to be made between programmability and reusability of dedicated hardware for special functionality on the one hand, and a high performance dedicated instruction set on the other hand. This paper addresses the question of how to find specialized ISA extensions for a set of applications. We describe the application of a new pattern matching technique to the problem of the identification of recurring patterns of operations. By implementing frequently occurring operation patterns in hardware, and using this hardware as special function units, a fine-grained hardware/software partitioning can be found. The fine granularity, and the fact that patterns are taken from a number of different target applications rather than a single one, increase the opportunities for reuse of the special-purpose hardware. We illustrate our technique with experiments on a number of benchmarks from the DSP domain.
---
paper_title: An integer linear programming approach for identifying instruction-set extensions

paper_content:

This paper presents an Integer Linear Programming (ILP) approach to the instruction-set extension identification problem. An algorithm that iteratively generates and solves a set of ILP problems in order to generate a set of templates is proposed. A selection algorithm that ranks the generated templates based on isomorphism testing and potential evaluation is described. A Trimaran based framework is used to evaluate the quality of the instructions generated by the technique. Speed-up results of up to 7.5 are observed.
---
paper_title: Synthesis of Application Specific Instructions for Embedded DSP Software

paper_content:

Application specific instructions play an important role in reducing the required code size and increasing performance in embedded DSP systems. This paper describes a new approach to generate application specific instructions for DSP applications. The proposed approach is based on a modified subset-sum problem and supports multicycle complex instructions, as well as single-cycle instructions, while the previous state-of-the-art approaches generate only the single-cycle instructions or just select instructions from the fixed super-set of possible instructions. In addition, the proposed approach can also be applied to the case that instructions are predefined. Experimental results on real applications show that Various given constraints can be met by the generated set of application specific instructions without attaching special hardware accelerators.
---
paper_title: Automatic selection of application-specific instruction-set extensions

paper_content:

In this paper, we present a general and an efficient algorithm for automatic selection of new application-specific instructions under hardware resources constraints. The instruction selection is formulated as an ILP problem and efficient solvers can be used for finding the optimal solution. An important feature of our algorithm is that it is not restricted to basic-block level nor does it impose any limitation on the number of the newly added instructions or on the number of the inputs/outputs of these instructions. The presented results show that a significant overall application speedup is achieved even for large kernels (for ADPCM decoder the speedup ranges from x1.2 to x3.7) and that our algorithm compares well with other state-of-art algorithms for automatic instruction set extensions.
---
paper_title: A new HW/SW partitioning algorithm for synthesizing the highest performance pipelined ASIPs with multiple identical FUs

paper_content:

This paper introduces a new HW/SW partitioning algorithm for automatic synthesis of a pipelined CPU architecture with multiple identical functional units (MIFUs) of each type in designing ASIPs (Application Specific Integrated Processors). The partitioning problem is formalized as a combinatorial optimization problem that partitions the operations into hardware and software so that the performance of the designed ASIP is maximized under given gate count and power consumption constraints, regarding the optimal selection of needed FUs of each type. A branch-and-bound algorithm with proposed lower bound function is used to solve the formalized problem. The experimental results show that the proposed algorithm is found to be effective and efficient.
---
paper_title: Code generation using tree matching and dynamic programming

paper_content:

Compiler-component generators, such as lexical analyzer generators and parser generators, have long been used to facilitate the construction of compilers. A tree-manipulation language called twig has been developed to help construct efficient code generators. Twig transforms a tree-translation scheme into a code generator that combines a fast top-down tree-pattern matching algorithm with dynamic programming. Twig has been used to specify and construct code generators for several experimental compilers targeted for different machines.
---
paper_title: Determining the optimum extended instruction-set architecture for application specific reconfigurable VLIW CPUs

paper_content:

Considers reconfigurable computing for application-specific systems, with particular reference to mixed-technology chips. A VLIW "core" is augmented by means of reconfigurable functional units (RFUs) and register files implemented via FPGA on to the same chip. The application is analyzed to extract segments of computation that could be usefully collapsed into complex instructions decoded and executed by the RFUs. In this paper, we focus on the problem of selecting the optimum extension to the native instruction set by means of the "best" segments of the computation that will become complex instructions. In particular, a genetic algorithm approach is introduced to analyze the population of candidates; modifications to the classic genetic operators are introduced to take into account the peculiarity of our problem. Applying the proposed methodology to some significant applications has validated the overall approach.
---
paper_title: Automatic instruction generation for application specific co-processor

paper_content:

By extending the baseline processor with application specific instructions, an application specific co-processor can meet the computational demands of the application. Working with the traditional co-processor interface, it doesn't require the extensible processor core and has least impact on the existing hardware and software. This paper proposes a framework for design space exploration and automatic co-processor instructions generation, in which application profiling, instruction identification and evaluation proceed seamlessly and iteratively. The optimal instruction set of the co-processor under given constraints is automatically generated from the source code of the application. To demonstrate the effectiveness of the method we generate the instruction set of a SPARC V8 co-processor for a VoIP application. The experiment gives promising results with the speedup of factor 2.3
---
paper_title: Datapath merging and interconnection sharing for reconfigurable architectures

paper_content:

Recent work in reconfigurable computing research has shown that a substantial performance speedup can be achieved through architectures that map the most relevant application inner-loops to a reconfigurable datapath. Any solution to this problem must be able to synthesize a datapath for each loop and to merge them together into a single reconfigurable datapath. The main contribution of this paper is a novel graph-based technique for the datapath merge problem. This approach is based on the solution of a maximum clique problem that merges datapaths one at a time. A set of experiments, using the MediaBench benchmark, shows that the proposed technique produces 24% fewer datapath interconnections than a previous solution to this problem.
---
paper_title: Rapid design of area-efficient custom instructions for reconfigurable embedded processing

paper_content:

RISPs (Reconfigurable Instruction Set Processors) are increasingly becoming popular as they can be customized to meet design constraints. However, existing instruction set customization methodologies do not lend well for mapping custom instructions on to commercial FPGA architectures. In this paper, we propose a design exploration framework that provides for rapid identification of a reduced set of profitable custom instructions and their area costs on commercial architectures without the need for time consuming hardware synthesis process. A novel clustering strategy is used to estimate the utilization of the LUT (Look-Up Table) based FPGAs for the chosen custom instructions. Our investigations show that the area costs computations using the proposed hardware estimation technique on 20 custom instructions are shown to be within 8% of those obtained using hardware synthesis. A systematic approach has been adopted to select the most profitable custom instruction candidates. Our investigations show that this leads to notable reduction in the number of custom instructions with only marginal degradation in performance. Simulations based on domain-specific application sets from the MiBench and MediaBench benchmark suites show that on average, more than 25% area utilization efficiency (performance/area) can be achieved with the proposed technique.
---
paper_title: Instruction set extension generation with considering physical constraints

paper_content:

In this paper, we propose new algorithms for both ISE exploration and selection with considering important physical constraints such as pipestage timing and instruction set architecture (ISA) format, silicon area and register file. To handle these considerations, an ISE exploration algorithm is proposed. It not only explores ISE candidates but also their implementation option to minimize the execution time meanwhile using less silicon area. In ISE selection, many researches only take silicon area into account, but it is not comprehensive. In this paper, we formulate ISE selection as a multiconstrained 0-1 knapsack problem so that it can consider multiple constraints. Results with MiBench indicate that under same number of ISE, our approach achieves 69.43%, 1.26% and 33.8% (max., min. and avg., respectively) of further reduction in silicon area and also has maximally 1.6% performance improvement compared with the previous one.
---
paper_title: Satisfying real-time constraints with custom instructions

paper_content:

Instruction-set extensible processors allow an existing processor core to be extended with application-specific custom instructions. In this paper, we explore a novel application of instruction-set extensions to meet timing constraints in real-time embedded systems. In order to satisfy real-time constraints, the worst-case execution time (WCET) of a task should be reduced as opposed to its average-case execution time. Unfortunately, existing custom instruction selection techniques based on average-case profile information may not reduce a task's WCET. We first develop an Integer Linear Programming (ILP) formulation to choose optimal instruction-set extensions for reducing the WCET. However, ILP solutions for this problem are often too expensive to compute. Therefore, we also propose an efficient and scalable heuristic that obtains quite close to the optimal results. Experiment results indicate that suitable choice of custom instructions can reduce the WCET of our benchmark programs by as much as 42% (23.5% on an average).
---
paper_title: Removing communications in clustered microarchitectures through instruction replication

paper_content:

The need to communicate values between clusters can result in a significant performance loss for clustered microarchitectures. In this work, we describe an optimization technique that removes communications by selectively replicating an appropriate set of instructions. Instruction replication is done carefully because it might degrade performance due to the increased contention it can place on processor resources. The proposed scheme is built on top of a previously proposed state-of-the-art modulo-scheduling algorithm. Though this algorithm has been proved to be very effective at reducing communications, results show that the number of communications can be further decreased by around one-third through replication, which results in a significant speedup. IPC is increased by 25p on average for a four-cluster microarchitecture and by as much as 70p for selected programs. We also show that replicating appropriate sets of instructions is more effective than doubling the intercluster connection network bandwidth.
---
paper_title: Processor acceleration through automated instruction set customization

paper_content:

Application-specific extensions to the computational capabilities of a processor provide an efficient mechanism to meet the growing performance and power demands of embedded applications. Hardware, in the form of new function units (or co-processors), and the corresponding instructions, are added to a baseline processor to meet the critical computational demands of a target application. The central challenge with this approach is the large degree of human effort required to identify and create the custom hardware units, as well as porting the application to the extended processor. In this paper, we present the design of a system to automate the instruction set customization process. A dataflow graph design space exploration engine efficiently identifies profitable computation subgraphs from which to create custom hardware, without artificially constraining their size or shape. The system also contains a compiler subgraph matching framework that identifies opportunities to exploit and generalize the hardware to support more computation graphs. We demonstrate the effectiveness of this system across a range of application domains and study the applicability of the custom hardware across the domain.
---
paper_title: Optimizing instruction-set extensible processors under data bandwidth constraints

paper_content:

The authors present a methodology for generating optimized architectures for data bandwidth constrained extensible processors. The authors describe a scalable integer linear programming (ILP) formulation, that extracts the most profitable set of instruction-set extensions given the available data bandwidth and transfer latency. Unlike previous approaches, the authors differentiate between number of inputs and outputs for instruction-set extensions and the number of register file ports. This differentiation makes the approach applicable to architectures that include architecturally visible state registers and dedicated data transfer channels. The authors support a comprehensive design space exploration to characterize the area/performance trade-offs for various applications. The authors evaluate our approach using actual ASIC implementations to demonstrate that our automatically customized processors meet timing within the target silicon area. For an embedded processor with only two register read ports and one register write port, the authors obtain up to 4.3times speed-up with extensions incurring only a 35% area overhead
---
paper_title: Solving covering problems using LPR-based lower bounds

paper_content:

Unate and binate covering problems are a special class ofgeneral integer linear programming problems with which several problemsin logic synthesis, such as two-level logic minimization and technologymapping, are formulated. Previous branch-and-bound methodsfor exactly solving these problems use lower-bounding techniques basedon finding maximal independent sets. In this paper we examine lower-boundingtechniques based on linear programming relaxation (LPR) forthe binate covering problem. We show that a combination of traditionalreductions (essentiality and dominance) and incremental computation ofLPR-based lower bounds can exactly solve difficult covering problemsorders of magnitude faster than traditional methods.
---
paper_title: Synthesis of Accelerator Data Paths for High-Throughput Signal Processing Applications

paper_content:

A disc brake having a friction lining pad for braking engagement with a rotatable disc. Moving of the friction lining pad is obtained by rotation of a cam engaging a force directing member fastened to the lining pad for transmitting an actuating force to the friction lining pad in a direction for bringing the lining pad into engagement with the disc. Adjustment for wear of the friction lining pad is obtained through the rotation of the cam in the other direction in an amount to maintain engagement with the force directing member in the disengaged condition of the brake to equalize the stroke required to actuate the brake.
---
paper_title: Exact and approximate algorithms for the extension of embedded processor instruction sets

paper_content:

In embedded computing, cost, power, and performance constraints call for the design of specialized processors, rather than for the use of the existing off-the-shelf solutions. While the design of these application-specific CPUs could be tackled from scratch, a cheaper and more effective option is that of extending the existing processors and toolchains. Extensibility is indeed a feature now offered in real designs, e.g., by processors such as Tensilica Xtensa [T. R. Halfhill, Microprocess Rep., 2003], ARC ARCtangent [T. R. Halfhill, Microprocess Rep., 2000], STMicroelectronics ST200 [P. Faraboschi, G. Brown, J. A. Fisher, G. Desoli, and F. Homewood, Proc. 27th Annu. Int. Symp. Computer Architecture, 2000, p. 203], and MIPS CorExtend [T. R. Halfhill, Microprocess Rep., 2003]. While all these processors provide development environments with simulation capabilities for evaluating efficiently hand-crafted solutions, the tools to identify automatically the best processor configuration for a given application are less common. In particular, solutions to choose specialized instruction-set extensions (ISEs) have been investigated in the past years but are still seldom part of commercial toolchains. This paper provides a formal methodology and a set of algorithms that help address the problem. It proposes exact algorithms to derive optimal ISEs; exact identification of a single ISE is applicable to basic blocks of up to 1500 assembler-like instructions. This paper also introduces approximate methods that can process basic blocks of larger size. Results show that the described algorithms find solutions close to those that a designer would obtain by a detailed study of the application code. Both heuristic and exact algorithms find ISEs able to speed up unextended processors up to 5.0x. State-of-the-art comparisons show that the presented algorithms outperform existing ones by up to 2.6x
---
paper_title: HW/SW partitioning and code generation of embedded control applications on a reconfigurable architecture platform

paper_content:

This paper studies the use of a reconfigurable architecture platform for embedded control applications aimed at improving real time performance. The hw/sw codesign methodology from POLIS is used. It starts from high-level specifications, optimizes an intermediate model of computation (Extended Finite State Machines) and derives both hardware and software, based on performance constraints. We study a particular architecture platform, which consists of a general purpose processor core, augmented with a reconfigurable function unit and data-path to improve run time performance. A new mapping flow and algorithms to partition hardware and software are proposed to generate implementations that best utilize this architecture. Encouraging preliminary results are shown for automotive electronic control examples.
---
paper_title: A Method for Minimizing the Number of Internal States in Incompletely Specified Sequential Networks

paper_content:

A method is illustrated for minimizing the number of internal states in incompletely specified sequential networks. The minimization algorithm applies to any type of incompletely specified flow table. It is shown that only some compatibility classes (prime compatibility classes) need be considered as members of a solution. The selection of prime classes may be obtained as the solution of an integer linear program or by tabular techniques that are an extension of those used in the selection of prime implicants.
---
paper_title: Automatic Identification of Application-Specific Functional Units with Architecturally Visible Storage

paper_content:

Instruction Set Extensions (ISEs) can be used effectively to accelerate the performance of embedded processors. The critical, and difficult task of ISE selection is often performed manually by designers. A few automatic methods for ISE generation have shown good capabilities, but are still lim ited in the handling of memory accesses, and so they fail to directly address the memory wall problem. We present here the first ISE identification technique that can auto matically identify state-holding Application-specific Func tional Units (AFUs) comprehensively, thus being able to eliminate a large portion of memory traffic from cache and main memory. Our cycle-accurate results obtained by the SimpleScalar simulator show that the identified AFUs with architecturally visible storage gain significantly more than previous techniques, and achieve an average speedup of 2.8×over pure software execution. Moreover, the number of required memory-access instructions is reduced by two thirds on average, suggesting corresponding benefits on en ergy consumption.
---
paper_title: Automatic Application-Specific Instruction-Set Extensions Under Microarchitectural Constraints

paper_content:

This paper presents a methodology for automatically designing Instruction-Set Extensions in embedded processors. Many commercially available CPUs now offer the possibility of extending their instruction set for a specific application. Their tool chains typically support manual experimentations, but algorithms that can define the set of customised functional units most beneficial for a given applications are missing. Only a few algorithms exist but are severely limited in the type and size of operation clusters they can choose and hence reduce significantly the effectiveness of specialisation. A more general algorithm is presented here which selects maximal-speedup convex subgraphs of the application data-flow graph under fundamental microarchitectural constraints, and which improves significantly on the state of the art.
---
paper_title: Area-efficient instruction set synthesis for reconfigurable system-on-chip designs

paper_content:

Silicon compilers are often used in conjunction with Field Programmable Gate Arrays (FPGAs) to deliver flexibility, fast prototyping, and accelerated time-to-market. Many of these compilers produce hardware that is larger than necessary, as they do not allow instructions to share hardware resources. This study presents an efficient heuristic which transforms a set of custom instructions into a single hardware datapath on which they can execute. Our approach is based on the classic problems of finding the longest common subsequence and substring of two (or more) sequences. This heuristic produces circuits which are as much as 85.33% smaller than those synthesized by integer linear programming (ILP) approaches which do not explore resource sharing. On average, we obtained 55.41% area reduction for pipelined datapaths, and 66.92% area reduction for VLIW datapaths. Our solution is simple and effective, and can easily be integrated into an existing silicon compiler.
---
paper_title: Rapid generation of custom instructions using predefined dataflow structures

paper_content:

Abstract Custom instruction generation is fast becoming popular as it provides an alternative means to realize application specific processors. In this paper, we propose an efficient methodology for rapid instruction set customization on RISPs (Reconfigurable Instruction Set Processors) using predefined sets of dataflow structures that are based on templates and reusable structures. A novel template selection strategy was employed to reduce the number of templates required for matching by up to 50%, while providing comparable performance with known approaches. It has been shown that custom instructions could be realized through instantiation of a reduced set of pre-designed reusable structures. Experimental results show that a small number of reusable structures can sufficiently cater to custom instruction generation to notably reduce the time required to realize them on configurable hardware. Moreover, based on our evaluations using MiBench benchmark suites, the reusable structures constitute to only 2% of all the custom instruction instances. The custom instructions generated with reusable structures were implemented in FPGA and it is evident that up to 14% area savings with comparable performance can be achieved when compared with conventional implementation approaches.
---
paper_title: Instruction selection using binate covering for code size optimization

paper_content:

We address the problem of instruction selection in code generation for embedded DSP microprocessors. Such processors have highly irregular data-paths, and conventional code generation methods typically result in inefficient code. Instruction selection can be formulated as directed acyclic graph (DAG) covering. Conventional methods for instruction selection use heuristics that break up the DAG into a forest of trees and then cover them independently. This breakup can result in suboptimal solutions for the original DAG. Alternatively, the DAG covering problem can be formulated as a binate covering problem, and solved exactly or heuristically using branch-and-bound methods. We show that optimal instruction selection on a DAG in the case of accumulator-based architectures requires a partial scheduling of nodes in the DAG, and we augment the binate covering formulation to minimize spills and reloads. We show how the irregular data transfer costs of typical DSP data-paths can be modeled in the binate covering formulation.
---
paper_title: A design flow for configurable embedded processors based on optimized instruction set extension synthesis

paper_content:

Design tools for application specific instruction set processors (ASIPs) are an important discipline in systems-level design for wireless communications and other embedded application areas. Some ASIPs are still designed completely from scratch to meet extreme efficiency demands. However, there is also a trend, towards use of partially predefined, configurable RISC-like embedded processor cores that can be quickly tuned to given applications by means of instruction set extension (ISE) techniques. While the problem of optimized ISE synthesis has been studied, well from a theoretical perspective, there are still few approaches to an overall HW/SW design flow for configurable cores that take all real-life constraints into account In this paper, we therefore present a novel procedure for automated ISE synthesis that accommodates both user-specified and processor-specific constraints in a flexible wary and that produces value optimized ISE solutions in-short time. Driven by an advanced application C code analysis/profiling frontend, the ISE synthesis core algorithm is embedded into a complete, design flow, where the backend is formed by a state-of-the-art industrial tool for processor configuration, ISE IIW synthesis, and SW tool retargeting. The proposed, design flow, including ISE synthesis, is demonstrated, via several benchmarks for the MIPS CorExtend configurable RISC processor platform.
---
paper_title: Instruction generation for hybrid reconfigurable systems

paper_content:

Future computing systems need to balance flexibility, specialization, and performance in order to meet market demands and the computing power required by new applications. Instruction generation is a vital component for determining these trade-offs. In this work, we present theory and an algorithm for instruction generation. The algorithm profiles a dataflow graph and iteratively contracts edges to create the templates. We discuss how to target the algorithm toward the novel problem of instruction generation for hybrid reconfigurable systems. In particular, we target the Strategically Programmable System, which embeds complex computational units such as ALUs, IP blocks, and so on into a configurable fabric. We argue that an essential compilation step for these systems is instruction generation, as it is needed to specify the functionality of the embedded computational units. In addition, instruction generation can be used to create soft reconfigurable macros---tightly sequenced prespecified operations placed in the reconfigurable fabric.
---
paper_title: Automatic instruction set extension and utilization for embedded processors

paper_content:

There is a growing demand for application-specific embedded processors in system-on-a-chip designs. Current tools and design methodologies often require designers to manually specialize the processor based on an application. Moreover, the use of the new complex instructions added to the processor is often left to designers' ingenuity. We present a solution that automatically groups dataflow operations in the application software as potential new complex instructions. The set of possible instructions is then automatically used for code generation combined with high-level arithmetic optimizations using symbolic algebra. Symbolic arithmetic manipulations provide a novel and effective method for instruction selection that is necessary due to the complexity of the automatically identified instructions. We have used our methodology to automatically add new instructions to Tensilica processors for a set of examples. Our results show that our tools improve designers productivity and efficiently specialize an embedded processor for the given application such that the execution time is greatly improved.
---
paper_title: INSIDE: INstruction Selection/Identification & Design Exploration for Extensible Processors

paper_content:

This paper presents the INSIDE system that rapidly searches the design space for extensible processors, given area and performance constraints of an embedded application, while minimizing the design turn-around-time. Our system consists of a) a methodology to determine which code segments are most suited for implementation as a set of extensible instructions, b) a heuristic algorithm to select pre-configured extensible processors as well as extensible instructions (library), and c) an estimation tool which rapidly estimates the performance of an application on a generated extensible processor. By selecting the right combination of a processor core plus extensible instructions, we achieve a performance increase on average of 2.03x (up to 7x) compared to the base processor core at a minimum hardware overhead of 25% on average.
---
paper_title: On solving covering problems

paper_content:

The set covering problem and the minimum cost assignment problem (respectively known as unate and binate covering problem) arise throughout the logic synthesis flow. This paper investigates the complexity and approximation ratio of two lower bound computation algorithms from both a theoretical and practical point of view. It also presents a new pruning technique that takes advantage of the partitioning.
---
paper_title: A specification invariant technique for regularity improvement between flow-graph clusters

paper_content:

In system-level synthesis for DSP applications, algorithmic transformations on the initially specified flow-graph are crucial to arrive at a good specification as input for either high-level hardware synthesis, or for code generation. For both target styles, sharing of clusters (partitions) of the flow-graph on the same resource is essential to optimize within the combined search space of area, time, and power. To decrease sharing overhead, it is important for clusters that share the same resource to match each other as good as possible, which is the aim of regularity improvement. In this paper, we present a new technique that improves the regularity between two or more flow-graph clusters by means of algebraic transformations, operating at the word-level. The technique consists of a steepest descent optimization step, preceded by a normalization step. Both steps use optimizing algebraic transformations that feature a limited look-ahead. Regularity improvement is modeled as an area minimization problem. The technique is invariant to structural changes in the specification of the clusters, as long as their functionality is not affected. Our main target domain consists of lowly-multiplexed realizations of real-time DSP applications. The power of our approach is substantiated on several real-life applications from the video and image processing domain. The regularity improvement technique is able to generate optimal (or close to optimal) results, independent of cluster duplications or (behavior-preserving) cluster structure modifications, with only a few composite transformations. Large savings are possible compared to non optimized flow-graph clusters with an acceptable but relatively large run time complexity.
---
paper_title: An integer programming approach to instruction implementation method selection problem

paper_content:

A new algorithm for instruction implementation method selection problem (IMSP) in application specific integrated processors (ASIP) design automation is proposed. This problem is to be solved in the instruction set architecture and CPU core architecture designs. First, the IMSP is formalized as an integer programming problem, which is to maximize the performance of the CPU under the constraints of chip area and power consumption. Then, a branch-and-bound algorithm to solve IMSP is described. According to the experimental results, the proposed algorithm is quite effective and efficient in solving the IMSP. This algorithm will automate the complex parts of the ASIP chip design. >
---
paper_title: Instruction generation and regularity extraction for reconfigurable processors

paper_content:

The increasing demand for complex and specialized embedded hardware must be met by processors which are optimized for performance, yet are also extremely flexible. In our work, we explore the tradeoff between flexibility and performance in the domain of reconfigurable processor design. Specifically, we seek to identify regularly occurring, computation-heavy patterns in an application or set of applications. These patterns become candidates for hard-logic implementation, potentially embedded in the flexible reconfigurable fabric as special optimized instructions. In this work we present an extension to previous work in instruction generation: an algorithm that identifies parallel templates. We discuss the advantages of parallel templates, and prove the correctness of our algorithm. We introduce an All-Pairs Common Slack Graph (APCSG) as an effective tool for parallel template generation. Finally, we demonstrate the effectiveness of our algorithm on several applicationse dataflow graphs, reducing latency on average by 51.98%, without unreasonably increasing chip area.
---
paper_title: A hardware/software partitioning algorithm for designing pipelined ASIPs with least gate counts

paper_content:

This paper introduces a new HW/SW partitioning algorithm used in automating the instruction set processor design for pipelined ASIP (application specific integrated processor). The partitioning problem is formalized as a combinatorial optimization problem that partitions the operations into hardware and software so that the HW cost (gate count) of the designed pipelined ASIP is minimized under given execution cycle and power consumption constraints. A branch-and-bound algorithm with proposed lower bound functions is used to solve the presented formalization in the PEAS-I system. The experimental results show that the proposed method is found to be effective and efficient.
---
paper_title: Managing dynamic reconfiguration overhead in systems-on-a-chip design using reconfigurable datapaths and optimized interconnection networks

paper_content:

This research examines the role of dynamically reconfigurable logic in systems-on-a-chip (SoC) design. Specifically we study the overhead of storing and downloading the configuration code bits for different parts of an application in a dynamically reconfigurable coprocessor environment. For SoC designs the different configuration bit-streams will likely need to be stored on chip, thus it becomes crucial to reduce the storage overhead. In addition, reducing the reconfiguration time overhead is crucial in realizing performance benefits. This study provides insight into the granularity of the reconfigurable logic that is appropriate for the SoC context. Our initial study is in the domain of multimedia and communication systems. We first present profiling results for these using the MESCAL compiler infrastructure. These results are used to derive an architecture template that consists of dynamically reconfigurable datapaths using coarse grain logic blocks and a reconfigurable interconnection network. We justify this template based on the constraints of SoC design. We then describe a design flow where we start from an application, derive the kernel loops via profiling and then map the application using the dynamically reconfigurable datapath and the simplest interconnection network. As part of this flow we have developed a mapping algorithm that minimizes the size of the interconnection network and thus the overhead of reconfiguration, which is key for systems-on-a-chip. We provide some initial results that validate our approach.
---
paper_title: Energy-efficient instruction set synthesis for application-specific processors

paper_content:

Several techniques have been proposed to enhance the energy-efficiency of ASIPs (Application-Specific Instruction set Processors). While those techniques can reduce the energy consumption with a minimal change in the instruction set (IS), they fail to exploit the opportunity of designing the entire IS from the energy-efficiency perspective. In this paper, we present an energy-efficient IS synthesis technique that can comprehensively reduce the energy-delay product (EDP) of ASIPs through optimal instruction encoding, considering both the instruction bitwidth and the dynamic instruction count. Experimental results with a typical embedded RISC processor show that our technique can generate application-specific IS's that are up to 40% more energy-efficient over the native IS for several application benchmarks.
---
paper_title: Application-specific instruction generation for configurable processor architectures

paper_content:

Designing an application-specific embedded system in nanometer technologies has become more difficult than ever due to the rapid increase in design complexity and manufacturing cost. Efficiency and flexibility must be carefully balanced to meet different application requirements. The recently emerged configurable and extensible processor architectures offer a favorable tradeoff between efficiency and flexibility, and a promising way to minimize certain important metrics (e.g., execution time, code size, etc.) of the embedded processors. This paper addresses the problem of generating the application-specific instructions to improve the execution speed for configurable processors. A set of algorithms, including pattern generation, pattern selection, and application mapping, are proposed to efficiently utilize the instruction set extensibility of the target configurable processor. Applications of our approach to several real-life benchmarks on the Altera Nios processor show encouraging performance speedup (2.75X on average and up to 3.73X in some cases).
---
paper_title: A graph covering algorithm for a coarse grain reconfigurable system

paper_content:

The availability of high-level design entry tooling is crucial for the viability of any reconfigurable SoC architecture. This paper presents a graph covering algorithm. The graph covering is done in two steps: template generation and template selection. The objective of template generation step is to extract functional equivalent structures, i.e. templates, from a control data flow graph. By inspecting the graph, the algorithm generates all the possible templates and the corresponding matches. Using unique serial numbers and circle numbers, the algorithm can find all distinct templates with multiple outputs. The template selection algorithm shows how this information can be used in compilers for reconfigurable systems. The objective of the template selection algorithm is to find an efficient cover for an application graph with a minimal number of distinct templates and minimal number of matches.
---
paper_title: A linear complexity algorithm for the automatic generation of convex multiple input multiple output instructions

paper_content:

The instruction-set extensions problem has been one of the major topics in recent years and it consists of the addition of a set of new complex instructions to a given instruction-set. This problem in its general formulation requires an exhaustive search of the design space to identify the candidate instructions. This search turns into an exponential complexity of the solution. In this paper we propose an efficient linear complexity algorithm for the automatic generation of convex multiple input multiple output instructions, whose convexity is theoretically guaranteed. The proposed approach is not restricted to basic-block level and does not impose limitations either on the number of input and/or output, or on the number of new instructions generated. Our results show a significant overall application speedup (up to ×2.9 for ADPCM decoder) considering the linear complexity of the proposed solution and which therefore compares well with other state-of-art algorithms for automatic instruction-set extensions.
---
paper_title: Effective bounding techniques for solving unate and binate covering problems

paper_content:

Covering problems arise in many areas of electronic design automation such as logic minimization and technology mapping. An exact solution can critically impact both size and performance of the devices being designed. This paper introduces eclipse, a branch-and-bound solver that can solve many covering problems orders of magnitude faster than existing solvers. When used in place of the default covering engine of a well-known logic minimizer, eclipse makes it possible to find, in less than six minutes, true minima for three benchmark problems that have eluded exact solutions for more than a decade.
---
paper_title: Automatic application-specific instruction-set extensions under microarchitectural constraints

paper_content:

Many commercial processors now offer the possibility of extending their instruction set for a specific application - that is, to introduce customized functional units. There is a need to develop algorithms that decide automatically, from high-level application code, which operations are to be carried out in the customized extensions. A few algorithms exist but are severely limited in the type of operation clusters they can choose and hence reduce significantly the effectiveness of specialization. In this paper, we introduce a more general algorithm which selects maximal-speedup convex subgraphs of the application dataflow graph under fundamental microarchitectural constraints, and which improves significantly on the state of the art.
---
paper_title: Synthesis of custom processors based on extensible platforms

paper_content:

Efficiency and flexibility are critical, but often conflicting, design goals in embedded system design. The recent emergence of extensible processors promises a favorable tradeoff between efficiency and flexibility, while keeping design turnaround times short. Current extensible processor design flows automate several tedious tasks, but typically require designers to manually select the parts of the program that are to be implemented as custom instructions.In this work, we describe an automatic methodology to select custom instructions to augment an extensible processor, in order to maximize its efficiency for a given application program. We demonstrate that the number of custom instruction candidates grows rapidly with program size, leading to a large design space, and that the quality (speedup) of custom instructions varies significantly across this space, motivating the need for the proposed flow. Our methodology features cost functions to guide the custom instruction selection process, as well as static and dynamic pruning techniques to eliminate inferior parts of the design space from consideration. Further, we employ a two-stage process, wherein a limited number of promising instruction candidates are first selected, and then evaluated in more detail through cycle-accurate instruction set simulation and synthesis of the corresponding hardware, to identify the custom instruction combinations that result in the highest program speedup or maximize speedup under a given area constraint.We have evaluated the proposed techniques using a state-of-the-art extensible processor platform, in the context of a commercial design flow. Experiments with several benchmark programs indicate that custom processors synthesized using automatic custom instruction selection can result in large improvements in performance (upto 5.4X, average of 3.4X), energy (upto 4.5X, average of 3.2X), and energy-delay product (upto 24.2X, average of 12.6X), while speeding up the design process significantly.
---
paper_title: Accelerator Data-Path Synthesis for High-Throughput Signal Processing Applications

paper_content:

From the Publisher: ::: Accelerator Data-Path Synthesis for High-Throughput Signal Processing Applications is the first book to show how to use high-level synthesis techniques to cope with the stringent timing requirements of complex high-throughput real-time signal and data processing. The book describes the state-of-the-art in architectural synthesis for complex high-throughput real-time processing. Unlike many other, the Synthesis approach used in this book targets an architecture style or an application domain. This approach is thus heavily application-driven and this is illustrated in the book by several realistic demonstration examples used throughout. Accelerator Data-Path Synthesis for High-Throughput Signal Processing Applications focuses on domains where application-specific high-speed solutions are attractive such as significant parts of audio, telecom, instrumentation, speech, robotics, medical and automotive processing, image and video processing, TV, multi-media radar, sonar, etc. Moreover, it addresses mainly the steps above the traditional scheduling and allocation tasks which focus on scalar operations and data. Accelerator Data-Path Synthesis for High-Throughput Signal Processing Applications is of interest to researchers, senior design engineers and CAD managers both in academia and industry. It provides an excellent overview of what capabilities to expect from future practical design tools and includes an extensive bibliography.
---
paper_title: Efficient instruction encoding for automatic instruction set design of configurable ASIPs

paper_content:

Application-specific instructions can significantly improve the performance, energy, and code size of configurable processors. A common approach used in the design of such instructions is to convert application-specific operation patterns into new complex instructions. However, processors with a fixed instruction bitwidth cannot accommodate all the potentially interesting operation patterns, due to the limited code space afforded by the fixed instruction bitwidth. We present a novel instruction set synthesis technique that employs an efficient instruction encoding method to achieve maximal performance improvement. We build a library of complex instructions with various encoding alternatives and select the best set of complex instructions while satisfying the instruction bitwidth constraint. We formulate the problem using integer linear programming and also present an effective heuristic algorithm. Experimental results using our technique generate instruction sets that show improvements of up to 38% over the native instruction set for several realistic benchmark applications running on a typical embedded RISC processor.
---
paper_title: A Scalable Application-Specific Processor Synthesis Methodology

paper_content:

Custom processors based on application-specific or domain-specific instruction sets are gaining popularity, and are often used to implement critical architectural blocks in complex system-on-chips. While several advances have been made in custom processor architectures, tools, and design methodologies, designers are still required to manually perform some critical tasks, such as selection of the custom instructions best suited to the given application and design constraints. We present a scalable methodology for the synthesis of a custom processor from an embedded software program. A key feature of the proposed methodology is its scalability, which is achieved by exploiting the structured, hierarchical nature of large software programs. We motivate the need for such a methodology, and describe the algorithms used for the critical steps, including hardware resource budgeting, local optimizations, and global exploration. Our methodology utilizes the concept of "soft" instruction templates, which can be adapted by adding operations to them or deleting operations from them at any time during the design space exploration process, allowing for global design decisions to be interleaved with fine-grained optimizations. We have integrated our methodology in an open source compiler, and verified it using a commercial extensible processor. Experiments with several benchmarks indicate that our methodology can effectively tackle large programs. It resulted in the synthesis of high-quality custom processors that demonstrated an average speedup of 2.61X and a maximum speedup of 6.32X. The CPU times required for custom processor synthesis were quite small, indicating that the proposed techniques can be applied to embedded software programs of significant complexity.
---
paper_title: Reconfigurable computing: a survey of systems and software

paper_content:

Due to its potential to greatly accelerate a wide variety of applications, reconfigurable computing has become a subject of a great deal of research. Its key feature is the ability to perform computations in hardware to increase performance, while retaining much of the flexibility of a software solution. In this survey, we explore the hardware aspects of reconfigurable computing machines, from single chip architectures to multi-chip systems, including internal structures and external coupling. We also focus on the software that targets these machines, such as compilation tools that map high-level algorithms directly to the reconfigurable substrate. Finally, we consider the issues involved in run-time reconfigurable systems, which reuse the configurable hardware during program execution.
---
paper_title: Reconfigurable computing: a survey of systems and software

paper_content:

Due to its potential to greatly accelerate a wide variety of applications, reconfigurable computing has become a subject of a great deal of research. Its key feature is the ability to perform computations in hardware to increase performance, while retaining much of the flexibility of a software solution. In this survey, we explore the hardware aspects of reconfigurable computing machines, from single chip architectures to multi-chip systems, including internal structures and external coupling. We also focus on the software that targets these machines, such as compilation tools that map high-level algorithms directly to the reconfigurable substrate. Finally, we consider the issues involved in run-time reconfigurable systems, which reuse the configurable hardware during program execution.
---
paper_title: CHIMAERA: a high-performance architecture with a tightly-coupled reconfigurable functional unit

paper_content:

Reconfigurable hardware has the potential for significant performance improvements by providing support for application-specific operations. We report our experience with Chimaera, a prototype system that integrates a small and fast reconfigurable functional unit (RFU) into the pipeline of an aggressive, dynamically-scheduled superscalar processor. Chimaera is capable of performing 9-input/1-output operations on integer data. We discuss the Chimaera C compiler that automatically maps computations for execution in the RFU. Chimaera is capable of: (1) collapsing a set of instructions into RFU operations, (2) converting control-flow into RFU operations, and (3) supporting a more powerful fine-grain data-parallel model than that supported by current multimedia extension instruction sets (for integer operations). Using a set of multimedia and communication applications we show that even with simple optimizations, the Chimaera C compiler is able to map 22% of all instructions to the RFU on the average. A variety of computations are mapped into RFU operations ranging from as simple as add/sub-shift pairs to operations of more than 10 instructions including several branches. Timing experiments demonstrate that for a 4-way out-of-order superscalar processor Chimaera results in average performance improvements of 21%, assuming a very aggressive core processor design (most pessimistic RFU latency model) and communication overheads from and to the RFU.
---
paper_title: Processor reconfiguration through instruction-set metamorphosis

paper_content:

The processor reconfiguration through instruction-set metamorphosis (PRISM) general-purpose architecture, which speeds up computationally intensive tasks by augmenting the core processor's functionality with new operations, is described. The PRISM approach adapts the configuration and fundamental operations of a core processing system to the computationally intensive portions of a targeted application. PRISM-1, an initial prototype system, is described, and experimental results that demonstrate the benefits of the PRISM concept are presented. >
---
paper_title: The Chimaera reconfigurable functional unit

paper_content:

By strictly separating reconfigurable logic from their host processor, current custom computing systems suffer from a significant communication bottleneck. In this paper we describe Chimaera, a system that overcomes this bottleneck by integrating reconfigurable logic into the host processor itself with direct access to the host processor's register file, the system enables the creation of multi-operand instruction and a speculative execution model key to high performance, general-purpose reconfigurable computing. It also supports multi-output functions, and utilizes partial run-time reconfiguration to reduce reconfiguration time. Combined, this system can provide speedups of a factor of two or more for general-purpose computing, and speedups of 160 or more are possible for hand-mapped applications.
---
paper_title: OneChip: an FPGA processor with reconfigurable logic

paper_content:

This paper describes a processor architecture called OneChip, which combines a fixed-logic processor core with reconfigurable logic resources. Using the programmable components of this the performance of speed-critical can be improved by customizing OneChip's execution units, or flexibility can be added to the glue logic interfaces of embedded controller applications. OneChip eliminates the shortcomings of other custom compute machines by tightly integrating its reconfigurable resources into a MIPS-like processor. Speedups of close to 50 over strict software implementations on a MIPS R4400 are achievable for computing the DCT.
---
paper_title: A RISC architecture extended by an efficient tightly coupled reconfigurable unit

paper_content:

In this paper, the architecture of an embedded processor extended with a tightly-coupled coarse-grain reconfigurable functional unit (RFU) is proposed. The efficient integration of the RFU with the control unit and the datapath of the processor eliminate the communication overhead between them. To speed up execution, the RFU exploits instruction level parallelism (ILP) and spatial computation. Also, the proposed integration of the RFU efficiently exploits the pipeline structure of the processor, leading to further performance improvements. Furthermore, a development framework for the introduced architecture is presented. The framework is fully automated, hiding all reconfigurable hardware related issues from the user. The hardware model of the architecture was synthesized in a 0.13 µm process and all information regarding area and delay were estimated and presented. A set of benchmarks is used to evaluate the architecture and the development framework. Experimental results prove performance improvements i...
---
paper_title: Fine- and Coarse-Grain Reconfigurable Computing

paper_content:

Fine- and Coarse-Grain Reconfigurable Computing gives the basic concepts and building blocks for the design of Fine- (or FPGA) and Coarse-Grain Reconfigurable Architectures. Recently-developed integrated architecture design and software-supported design flow of FPGA and coarse-grain reconfigurable architecture are also described. The book is accompanied by an interactive CD which include case studies and lab projects for the design of FPGA and Coarse-grain architectures based on the European funded projects AMDREL and MOLEN, respectively. Part I consists of two extensive surveys of FPGA and Coarse-Grain Reconfigurable Architectures: The FPGA technology is defined, which includes architecture, logic block structure, interconnect, and configuration methods and existing fine-grain reconfigurable architectures emerged from both academia and industry. Additionally, the implementation techniques and CAD tools developed to facilitate the implementation of a system in reconfigurable hardware by the industry and academia are provided. In addition the features, the advantages and limitations of the coarse-grain reconfigurable systems, the specific issues that should be addressed during the design phase, as well as representative existing coarse-grain reconfigurable systems are explained. In Part II, case studies, innovative research results about reconfigurable architectures and design frameworks from three projects AMDREL, MOLEN and ADRES&DRESC, and, a new classification according to microcoded architectural criteria are described. Fine- and Coarse-Grain Reconfigurable Computing is an essential reference for researchers and professionals and can be used as a textbook by undergraduate, graduate students and professors.
---
paper_title: The design of dynamically reconfigurable datapath coprocessors

paper_content:

Increasing nonrecurring engineering and mask costs are making it harder to turn to hardwired application specific integrated circuit (ASIC) solutions for high-performance applications. The volume required to amortize these high costs has been increasing, making it increasingly expensive to afford ASIC solutions for medium-volume products. This has led to designers seeking programmable solutions of varying sorts using these so-called programmable platforms. These programmable platforms span a large range from bit-level programmable field programmable gate arrays to word-level programmable application-specific, and in some cases even general-purpose processors. The programmability comes with a power and performance overhead. Attempts to reduce this overhead typically involve making some core hardwired ASIC like logic blocks accessible to the programmable elements. This paper presents one such hybrid solution in this space---a relatively simple processor with a dynamically reconfigurable datapath acting as an accelerating coprocessor. This datapath consists of hardwired function units and reconfigurable interconnect. We present a methodology for the design of these solutions and illustrate it with two complete case studies: an MPEG2 coder, and a GSM coder, to show how significant speedups can be obtained using relatively little hardware. This work is part of the MESCAL project, which is geared towards developing design environments for the development of application-specific platforms.
---
paper_title: Reconfigurable processing: the solution to low-power programmable DSP

paper_content:

One of the most compelling issues in the design of wireless communication components is to keep power dissipation between bounds. While low-power solutions are readily achieved in an application-specific approach, doing so in a programmable environment is a substantially harder problem. This paper presents an approach to low-power programmable DSP that is based on the dynamic reconfiguration of hardware modules. This technique has shown to yield at least an order of magnitude of power reduction compared to traditional instruction-based engines for problems in the area of wireless communication.
---
paper_title: The NAPA adaptive processing architecture

paper_content:

The National Adaptive Processing Architecture (NAPA) is a major effort to integrate the resources needed to develop teraops class computing systems based on the principles of adaptive computing. The primary goals for this effort include: (1) the development of an example NAPA component which achieves an order of magnitude cost/performance improvement compared to traditional FPGA based systems, (2) the creation of a rich but effective application development environment for NAPA systems based on the ideas of compile time functional partitioning and (3) significantly improve the base infrastructure for effective research in reconfigurable computing. This paper emphasizes the technical aspects of the architecture to achieve the first goal while illustrating key architectural concepts motivated by the second and third goals.
---
paper_title: RaPiD - Reconfigurable Pipelined Datapath

paper_content:

Configurable computing has captured the imagination of many architects who want the performance of application-specific hardware combined with the reprogrammability of general-purpose computers. Unfortunately, onfigurable computing has had rather limited success largely because the FPGAs on which they are built are more suited to implementing »ndom logic than computing tasks. This paper presents RaPiD, a new coarse-grained FPGA architecture that is optimized for highly repetitive, computation-intensive tasks. Very deep application-specific computation pipelines can be configured in RaPiD. These pipelines make much more efficient use of silicon than traditional FPGAs and also yield much higher performance for a wide range of applications.
---
paper_title: PRISM-II compiler and architecture

paper_content:

This paper discusses the architecture and compiler for a general-purpose metamorphic computing platform called PRISM-II. PRISM-II improves the performance of many computationally-intensive tasks by augmenting the functionality of the core processor with new instructions that match the characteristics of targeted applications. In essence, PRISM (processor reconfiguration through instruction set metamorphosis) is a general purpose hardware platform that behaves like an application-specific platform. Two methods for hardware synthesis, one using VHDL Designer and the other using X-BLOX, are presented and synthesis results are compared. >
---
paper_title: Processor reconfiguration through instruction-set metamorphosis

paper_content:

The processor reconfiguration through instruction-set metamorphosis (PRISM) general-purpose architecture, which speeds up computationally intensive tasks by augmenting the core processor's functionality with new operations, is described. The PRISM approach adapts the configuration and fundamental operations of a core processing system to the computationally intensive portions of a targeted application. PRISM-1, an initial prototype system, is described, and experimental results that demonstrate the benefits of the PRISM concept are presented. >
---
paper_title: Spyder: A SURE (SUperscalar and REconfigurable) processor

paper_content:

A processor with three concurrent and data-shared execution units is described in detail in this paper. The functionality, resources, and data sizes of the execution units, implemented with Xilinx FPGA chips, are user-configurable in order to best fit the application being run. A Harvard-type architecture allows a very large instruction word (128 bits) and, therefore, a real parallel utilization and control of resources. We also present the results of the implementation of two applications, the game of Life and the Abingdon Cross benchmark.
---
paper_title: ADRES: an architecture with tightly coupled VLIW processor and coarse-grained reconfigurable Matrix

paper_content:

The coarse-grained reconfigurable architectures have advantages over the traditional FPGAs in terms of delay, area and configuration time. To execute entire applications, most of them combine an instruction set processor(ISP) and a reconfigurable matrix. However, not much attention is paid to the integration of these two parts, which results in high communication overhead and programming difficulty. To address this problem, we propose a novel architecture with tightly coupled very long instruction word (VLIW) processor and coarse-grained reconfigurable matrix. The advantages include simplified programming model, shared resource costs, and reduced communication overhead. To exploit this architecture, our previously developed compiler framework is adapted to the new architecture. The results show that the new architecture has good performance and is very compiler-friendly.
---
paper_title: The MOLEN polymorphic processor

paper_content:

In this paper, we present a polymorphic processor paradigm incorporating both general-purpose and custom computing processing. The proposal incorporates an arbitrary number of programmable units, exposes the hardware to the programmers/designers, and allows them to modify and extend the processor functionality at will. To achieve the previously stated attributes, we present a new programming paradigm, a new instruction set architecture, a microcode-based microarchitecture, and a compiler methodology. The programming paradigm, in contrast with the conventional programming paradigms, allows general-purpose conventional code and hardware descriptions to coexist in a program: In our proposal, for a given instruction set architecture, a onetime instruction set extension of eight instructions, is sufficient to implement the reconfigurable functionality of the processor. We propose a microarchitecture based on reconfigurable hardware emulation to allow high-speed reconfiguration and execution. To prove the viability of the proposal, we experimented with the MPEG-2 encoder and decoder and a Xilinx Virtex II Pro FPGA. We have implemented three operations, SAD, DCT, and IDCT. The overall attainable application speedup for the MPEG-2 encoder and decoder is between 2.64-3.18 and between 1.56-1.94, respectively, representing between 93 percent and 98 percent of the theoretically obtainable speedups.
---
paper_title: Garp: a MIPS processor with a reconfigurable coprocessor

paper_content:

Typical reconfigurable machines exhibit shortcomings that make them less than ideal for general-purpose computing. The Garp Architecture combines reconfigurable hardware with a standard MIPS processor on the same die to retain the better features of both. Novel aspects of the architecture are presented, as well as a prototype software environment and preliminary performance results. Compared to an UltraSPARC, a Garp of similar technology could achieve speedups ranging from a factor of 2 to as high as a factor of 24 for some useful applications.
---
paper_title: Reconfigurable computing: a survey of systems and software

paper_content:

Due to its potential to greatly accelerate a wide variety of applications, reconfigurable computing has become a subject of a great deal of research. Its key feature is the ability to perform computations in hardware to increase performance, while retaining much of the flexibility of a software solution. In this survey, we explore the hardware aspects of reconfigurable computing machines, from single chip architectures to multi-chip systems, including internal structures and external coupling. We also focus on the software that targets these machines, such as compilation tools that map high-level algorithms directly to the reconfigurable substrate. Finally, we consider the issues involved in run-time reconfigurable systems, which reuse the configurable hardware during program execution.
---
paper_title: PipeRench: a co/processor for streaming multimedia acceleration

paper_content:

Future computing workloads will emphasize an architecture's ability to perform relatively simple calculations on massive quantities of mixed-width data. This paper describes a novel reconfigurable fabric architecture, PipeRench, optimized to accelerate these types of computations. PipeRench enables fast, robust compilers, supports forward compatibility, and virtualizes configurations, thus removing the fixed size constraint present in other fabrics. For the first time we explore how the bit-width of processing elements affects performance and show how the PipeRench architecture has been optimized to balance the needs of the compiler against the realities of silicon. Finally, we demonstrate extreme performance speedup on certain computing kernels (up to 190x versus a modern RISC processor), and analyze how this acceleration translates to application speedup.
---
paper_title: SONIC-a plug-in architecture for video processing

paper_content:

This paper presents the SONIC reconfigurable computing architecture and the first implementation, SONIC-I. SONIC is designed to support a software plug-in methodology to accelerate video image processing applications. SONIC differs from other architectures through the use of Plug-In Processing Elements (PIPEs) and the Application Programmer's Interface (API). Each PIPE contains a reconfigurable processor, a scalable router that also formats video data, and a frame-buffer memory. The SONIC architecture integrates multiple PIPEs together using a specialised bus structure which enables flexible and optimal pipelined processing. SONIC-I communicates with the host PC through the PCI bus and has 8 PIPEs. We have developed an easy to use API which allows SONIC-I to he used by multiple applications simultaneously. Preliminary results show that a 19 tap separable 2-D FIR filter implemented on a single PIPE achieves processing rates of more than 15 frames per second operating on 512/spl times/512 video transferred over the PCI bus. We estimate that using all 8 PIPEs, we could obtain real-time processing rates for complex operations such as image warping.
---
paper_title: Video Image Processing with the Sonic Architecture

paper_content:

Current industrial video-processing systems use a mixture of high-performance workstations and application-specific integrated circuits. However, video image processing in the professional broadcast environment requires more computational power and data throughput than most of today's general-purpose computers can provide. In addition, using ASICs for video image processing is both inflexible and expensive. Configurable computing offers an appropriate alternative for broadcast video image editing and manipulation by combining the flexibility, programmability, and economy of general-purpose processors with the performance of dedicated ASICs. Sonic is a configurable computing system that performs real-time video image processing. The authors describe how it implements algorithms for two-dimensional linear transforms, fractal image generation, filters, and other video effects. Sonic's flexible and scalable architecture contains configurable processing elements that accelerate software applications and support the use of plug-in software.
---
paper_title: Building and using a highly parallel programmable logic array

paper_content:

A two-slot addition called Splash, which enables a Sun workstation to outperform a Cray-2 on certain applications, is discussed. Following an overview of the Splash design and programming, hardware development is described. The development of the logic description generator is examined in detail. Splash's runtime environment is described, and an example application, that of sequence comparison, is given. >
---
paper_title: Fine- and Coarse-Grain Reconfigurable Computing

paper_content:

Fine- and Coarse-Grain Reconfigurable Computing gives the basic concepts and building blocks for the design of Fine- (or FPGA) and Coarse-Grain Reconfigurable Architectures. Recently-developed integrated architecture design and software-supported design flow of FPGA and coarse-grain reconfigurable architecture are also described. The book is accompanied by an interactive CD which include case studies and lab projects for the design of FPGA and Coarse-grain architectures based on the European funded projects AMDREL and MOLEN, respectively. Part I consists of two extensive surveys of FPGA and Coarse-Grain Reconfigurable Architectures: The FPGA technology is defined, which includes architecture, logic block structure, interconnect, and configuration methods and existing fine-grain reconfigurable architectures emerged from both academia and industry. Additionally, the implementation techniques and CAD tools developed to facilitate the implementation of a system in reconfigurable hardware by the industry and academia are provided. In addition the features, the advantages and limitations of the coarse-grain reconfigurable systems, the specific issues that should be addressed during the design phase, as well as representative existing coarse-grain reconfigurable systems are explained. In Part II, case studies, innovative research results about reconfigurable architectures and design frameworks from three projects AMDREL, MOLEN and ADRES&DRESC, and, a new classification according to microcoded architectural criteria are described. Fine- and Coarse-Grain Reconfigurable Computing is an essential reference for researchers and professionals and can be used as a textbook by undergraduate, graduate students and professors.
---
paper_title: Reconfigurable computing: architectures and design methods

paper_content:

Reconfigurable computing is becoming increasingly attractive for many applications. This survey covers two aspects of reconfigurable computing: architectures and design methods. The paper includes recent advances in reconfigurable architectures, such as the Alters Stratix II and Xilinx Virtex 4 FPGA devices. The authors identify major trends in general-purpose and special-purpose design methods. It is shown that reconfigurable computing designs are capable of achieving up to 500 times speedup and 70% energy savings over microprocessor implementations for specific applications.
---
paper_title: Reconfigurable computing: a survey of systems and software

paper_content:

Due to its potential to greatly accelerate a wide variety of applications, reconfigurable computing has become a subject of a great deal of research. Its key feature is the ability to perform computations in hardware to increase performance, while retaining much of the flexibility of a software solution. In this survey, we explore the hardware aspects of reconfigurable computing machines, from single chip architectures to multi-chip systems, including internal structures and external coupling. We also focus on the software that targets these machines, such as compilation tools that map high-level algorithms directly to the reconfigurable substrate. Finally, we consider the issues involved in run-time reconfigurable systems, which reuse the configurable hardware during program execution.
---
paper_title: Coarse grain reconfigurable architecture (embedded tutorial)

paper_content:

The paper gives a brief survey over a decade of R&D on coarse grain reconfigurable hardware and related compilation techniques and points out its significance to the emerging discipline of reconfigurable computing.
---
paper_title: A decade of reconfigurable computing: a visionary retrospective

paper_content:

The paper surveys a decade of R&D on coarse grain reconfigurable hardware and related CAD, points out why this emerging discipline is heading toward a dichotomy of computing science, and advocates the introduction of a new soft machine paradigm to replace CAD by compilation.
---
paper_title: Reconfigurable instruction set processors: a survey

paper_content:

Reconfigurable instruction-set processors have the capability to adapt their instruction sets to the application being executed through a reconfiguration in their hardware. Through this adaptation, they are expected to achieve a great improvement in performance compared to fixed instruction-set processors. In this paper, we discuss the different hardware aspects that have to be considered during the design of such a reconfigurable processor. The topics discussed include the coupling of the processor and the reconfigurable logic, the configuration, instruction coding and scheduling, granularity, the hardware cache and reconfigurability. A classification of current reconfigurable processors is carried out according to the discussed topics.
---
paper_title: Hardware/Software Partitioning in embedded system design

paper_content:

One of the most crucial steps in the hardware/software co-design of embedded systems is hardware/software partitioning. Most existing partitioning approaches try to capture too many details of partitioning problems and target architectures. In this paper, a simplified model for the hardware/software partitioning problem is introduced, and different versions of the partitioning problem are defined formally. Based on the simplified model, and ILP (integer linear programming) based approach and a genetic algorithm are presented. Experiments show that our genetic algorithm can solve the partitioning problem with thousands of nodes, yielding solutions close to optimal.
---

<format>
Title: The Instruction-Set Extension Problem: A Survey

Section 1: INTRODUCTION
Description 1: Provide an overview of the introduction to the instruction-set extension problem, explaining the background, context, and motivations for the study.

Section 2: INSTRUCTION-SET EXTENSIONS
Description 2: Discuss the customization of instruction-sets, the advantages it presents, and the major considerations in generating and selecting custom instructions.

Section 3: DIFFERENT TYPES OF CUSTOMIZATIONS
Description 3: Elaborate on various approaches in customization, incorporating types such as complete or partial customization and granularity (fine-grain or coarse-grain).

Section 4: Motivational Example
Description 4: Present a motivational example to illustrate the concept of instruction-set extension and different methods of customization through data-flow subgraphs.

Section 5: Types of Customizations
Description 5: Explore specific types of customizations, categorized by approaches like complete vs. partial and fine-grain vs. coarse-grain, and the degree of automation required.

Section 6: THE CUSTOMIZATION PROCESS
Description 6: Break down the customization process into phases, including instruction generation and instruction selection, and examine the methodologies involved.

Section 7: Custom Templates vs. Predefined Templates
Description 7: Compare custom-built templates versus predefined templates, and discuss their roles and applications in generating custom instructions.

Section 8: The Cost Function
Description 8: Detail the use of cost functions in guiding the search and identification of custom instructions based on specific metrics and constraints.

Section 9: Instruction Generation
Description 9: Analyze the process of generating custom instructions, the complexity involved, and different strategies to manage this complexity.

Section 10: Connected Instructions vs. Disconnected Instructions
Description 10: Discuss the identification and advantages of connected and disconnected custom instructions in the context of parallelism and execution efficiency.

Section 11: Convexity and Schedulable Instructions
Description 11: Explain the importance of convexity and schedulability of instructions for ensuring proper execution and functional operation in hardware.

Section 12: Single-Output Instructions vs. Multiple-Output Instructions
Description 12: Differentiate between single-output and multiple-output custom instructions, and discuss their respective processes of identification.

Section 13: Instruction Selection
Description 13: Provide an overview of optimal and nonoptimal approaches to the selection of custom instructions for hardware implementation.

Section 14: CUSTOM INSTRUCTION INTEGRATION
Description 14: Review various methods of integrating custom instructions into processor architectures, including functional units, coprocessors, attached processing units, and embedded cores.

Section 15: CONCLUSIONS
Description 15: Summarize the article, highlighting key issues in instruction-set customization, future trends, and open issues for further research.
</format>
