Abstract
Traditionally, common processor augmentation solutions have involved the addition of coprocessors or the datapath integration of custom instructions within extensible processors as Instruction Set Extensions (ISE). Rarely is the hybrid option of using both techniques explored. Much research already exists concerning the identification and selection of custom hardware blocks from hardware/software partitioning techniques, but the question of how to best use this hardware within a user system where both coprocessors and datapath augmentations are possible remains. This paper looks to extend existing ISE algorithms which provide custom hardware as dataflow graphs (DFG) and place them appropriately within a hybrid System-on-Chip (SoC) using standard combinatorial optimization techniques. A combinatorial model is presented to address this placement issue and is applied to two well known kernel programs. We further show that such standard techniques can execute within a reasonable time frame alleviating the need for heuristics.
I. INTRODUCTION
Much work exists concerning the identification of possible custom instructions for hardware implementations from a given software program [1], [2]. Many commercial tools can effectively convert identified software segments to hardware such as Altera’s C2H compiler [3]. An important question that is rarely addressed is how these custom hardware blocks can be integrated into the entire system. Due to the closed nature of existing IP cores it is not overly common that a user is able to modify a datapath directly, but with more open source projects becoming readily available this is indeed becoming a potential design space exploration (DSE) avenue. A few vendors offer products that allow the addition of custom hardware directly to the datapath, more precisely the ALU or in parallel to the existing ALU. Note that these procedures and implementations are often proprietary and not available to the end-user. All of these products place the internal and external selection and placement problem on the user. Here we will consider two possible solutions to the processor augmentation problem yielding a hybrid SoC (Fig. 1); integration directly into or parallel with the datapath, more succinctly the ALU itself or the addition of standardized coprocessors. The ultimate goal of such selections is a maximized speedup due to the optimal hybrid placement of hardware blocks within the processor itself and as coprocessors. Fig. 1. Hybrid SoC with internal custom instruction extensions and external coprocessors. The selection and placement problem itself can be modeled as a binary linear program (BLP). Using traditional combinatorial optimization techniques, the problem can be solved efficiently and quickly if appropriately constrained. Most importantly, using such BLP solution techniques as Branch-and- Bound with a single objective problem, the solution can be guaranteed to offer the best speedup for a given target chip. For these techniques to be justified, System-on-Chip targets are considered. As SoCs are typically targeted with ASIC and FPGA design flows, hardware will not be minimized but constrained to the size of the user selected chip or finite group of candidate chips. Looking at a set of finite targets ensures that all available resources are used effectively in achieving the best speedup. Systems will not be created that only use a fraction of the target chip as this is not feasible from an economic standpoint for FPGA targets. In this case, another target will be tried. By removing the hardware minimization consideration, a simplified mathematical model arises that when solved can guarantee the maximum speedup within the selected candidate target chips. The area constraint becomes an upper bound.


Download full report
http://googleurl?sa=t&source=web&cd=1&ve...873058.pdf%3Farnumber%3D5873058&ei=tGZbTtUSxMitB8GwidcK&usg=AFQjCNGSCzN9xtRCq2pv8lVBcMpP5-6gkg