Automated design of domain-specific custom instructions = Geautomatiseerd ontwerp van domeinspecifieke gespecialiseerde instructies

Universiteit Gent Faculteit Ingenieurswetenschappen en Architectuur Vakgroep Elektronica en Informatiesystemen Automated Design of Domain-Specific Custom Instructions Geautomatiseerd ontwerp van domeinspecifieke gespecialiseerde instructies Cecilia González-Álvarez Promotoren: Prof. Dr. Ir. Lieven Eeckhout Prof. Dr. Daniel Jiménez-González Prof. Dr. Carlos Álvarez Proefschrift tot het behalen van de graad van Doctor in de Ingenieurswetenschappen: Computerwetenschappen Academiejaar 2015-2016 Departament d’Arquitectura de Computadors Automated Design of Domain-Specific Custom Instructions Diseño automatizado de instrucciones especializadas para un dominio específico Cecilia González-Álvarez Directores: Prof. Dr. Lieven Eeckhout Prof. Dr. Daniel Jiménez-González Prof. Dr. Carlos Álvarez Tesis presentada para obtener el título de Doctora por la Universitat Politècnica de Catalunya Programa de Doctorado: Arquitectura de Computadores Año académico 2015-2016 Acknowledgements I would like to express my sincere gratitude to my advisors: Daniel Jiménez-González and Carlos Álvarez at UPC, and Lieven Eeckhout at UGent. They have guided me with expertise and understanding, and without their support this thesis would have never been possible. I would also like to thank people I met at each step of my PhD journey. First, I thank my supervisor at BSC, Xavier Martorell for his guidance and support, and my colleagues at BSC and UPC for all the great moments shared. Also, a very special thanks goes to Hironori Kasahara, professor at Waseda University, for all the encouragement during the year and a half that I spent in Japan. At last, I also would like to thank my colleagues at UGent, with special thanks to Jennifer Sartor for her help and support. Of course, I would like to thank my family and friends for all the best moments shared that lighted up the darkest times. Special thanks go to my parents and Klaas for their loving encouragement. Finally, this research would not have been possible without the financial assistance of the Severo Ochoa program (SEV-2011-00067), the Spanish Ministry of Science and Technology (TIN2012-34557), the Generalitat de Catalunya (MPEXPAR, 2009-SGR-980), HiPEAC3 Network of Excellence (FP7/ICT 287759), the European Research Council under the European Community’s Seventh Framework Programme (FP7/2007-2013) / ERC Grant agreement no. 259295, the Xilinx University Program, and the Japanese Ministry of Education. I express my gratitude to those agencies. Ghent, 24/09/2015 Cecilia González Álvarez Summary In the last years, hardware specialization has received renewed attention as chips approach a utilization wall. Specialized accelerators can take advantage of underutilized transistors implementing custom hardware that complements the main processor. However, specialization adds complexity to the design process and limits reutilization. Application-Specific Instruction Processors (ASIPs) balance performance and reusability, extending a general-purpose processor with custom instructions (CIs) specific for an application, implemented in Specialized Functional Units (SFUs). Still, time- to-market is a major issue with application-specific designs because, if CIs are not frequently executed, the acceleration benefits will not compensate for the overall design cost. Domain-specific acceleration increases the applicability of ASIPs, as it targets several applications that run on the same hardware. Also, reconfigurable SFUs and the automation of the CIs design can solve the aforementioned problems. In this dissertation, we explore different automated approaches to the design of CIs that extend a baseline processor for domain-specific acceleration to improve both performance and energy efficiency. First, we develop automated techniques to identify code sequences within a domain to create CI candidates. Due to the disparity among coding styles of different programs, it is difficult to find patterns that are represented by a unique CI across applications. Therefore, we propose an analysis at the basic block level that identifies equivalent CIs within and across different programs. We use the Taylor Expansion Diagram (TED) canonical representation to find not only structurally equivalent CIs, but also functionally similar ones, as opposed to the commonly applied directed acyclic graph (DAG) isomorphism detection. We combine both methods into a new Hybrid DAG/TED technique to identify more patterns across applications that map to the same CI. Then, we select a subset of the CI candidates that fits in the available SFU area. Because of the complexity of the problem, we propose four scoring heuristics to reduce the design space and smooth the potential performance speedup across applications. We include these me- iv Summary thods in the FuSInG framework, and we estimate performance with hardware models on a set of media benchmarks. Results show that, when limiting core area devoted to specialization, the SFU customization with the largest speedups includes a mix of application and domain-specific custom instructions. If we target larger CIs to obtain higher speedups, reusability across applications becomes critical; without enough equivalences, CIs cannot be generalized for a domain. We aim to share partially common operations among CIs to accelerate more code, especially across basic blocks, and to reduce the hardware area needed for specialization. Hence, we create a new canonical representation across basic blocks, the Merging Diagram, to facilitate similarity detection and improve code coverage. We also introduce clustering-based partial matching to identify partially-similar domainspecific CIs, which generally leads to better performance than applicationspecific ones. Yet, at small areas, merging two CIs induces a high additional overhead that might penalize energy-efficiency. Thus, we also detect fragments of CIs and we join them with the existing merged clusters resulting in minimal extra overhead. Also, using speedup as the deciding factor for CI selection may not be optimal for devices with limited power budgets. For that reason, we propose a linear programming-based selection that balances performance and energy consumption. We implement these techniques in the MInGLE framework and evaluate them with media benchmarks. The selected CIs significantly improve the energy-delay product and performance, demonstrating that we can accelerate a domain covering more code while reducing the needed area for the CI implementation. Resumen La especialización de hardware ha recibido renovado interés debido al utilization wall, ya que transistores infrautilizados pueden implementar hardware a medida que complemente el procesador principal. Sin embargo, el proceso de diseño se complica y se limita la reutilización. Procesadores de instrucciones para aplicaciones específicas (ASIPs) equilibran rendimiento y reuso, extendiendo un procesador con instruciones especializadas (custom instructions – CIs) para una aplicación, implementadas en unidades funcionales especializadas (SFUs). No obstante, los plazos de comercialización suponen un obstáculo en diseños específicos ya que, si las CIs no se ejecutan con frecuencia, los beneficios de la aceleración no compensan los costes de diseño. La aceleración de un dominio específico incrementa la aplicabilidad de los ASIPs,acelerando diferentes aplicaciones en el mismo hardware, mientras que una SFU reconfigurable y un diseño automatizado pueden resolver los problemas mencionados. En esta tesis, exploramos diferentes alternativas al diseño de CIs que extienden un procesador para acelerar un dominio, mejorando el rendimiento y la eficiencia energética. Proponemos primero técnicas automatizadas para identificar código acelerable en un dominio. Sin embargo, la identificación se ve dificultada por la diversidad de estilos entre diferentes programas. Por tanto, proponemos identificar en el bloque básico CIs equivalentes utilizando la representación canónica Taylor Expansion Diagram (TED). Con TEDs encontramos no sólo código estructuralmente equivalente, sino también con similitud funcional, en contraposición a la detección isomórfica de grafos acíclicos dirigidos (DAG). Combinamos ambos métodos en una nueva técnica híbrida DAG/TED, que identifica en varias aplicaciones más secuencias representadas por la misma CI. Tras esto, seleccionamos un subconjunto de CIs que puede ser contenido en el área de la SFU. Por la complejidad del problema, proponemos cuatro heurísticas de selección para reducir el espacio de búsqueda y homogeneizar el rendimiento de las aplicaciones. Incluimos estas técnicas en la infraestructura FuSInG y estimamos el rendimiento para un conjunto de benchmarks multimedia. Los resultados muestran que, al xii Table of Contents 3. Functionally Similar Domain-Specific Instructions 33 3.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.2. Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.3. FuSInG Automatic Framework . . . . . . . . . . . . . . . . 35 3.4. Identification of CI Candidates with DFG Exploration . . . . 37 3.5. Instruction Clustering to Discover Equivalences . . . . . . . 38 3.5.1. Clustering with DAG Isomorphism . . . . . . . . . 38 3.5.2. Clustering with TED isomorphism . . . . . . . . . . 40 3.5.3. Hybrid TED-DAG clustering . . . . . . . . . . . . . 41 3.6. Heuristic Selection . . . . . . . . . . . . . . . . . . . . . . . 42 3.6.1. Application-Specific Scoring . . . . . . . . . . . . . 42 3.6.2. Domain-Specific Scoring . . . . . . . . . . . . . . . 43 3.6.2.1. Scoring 1: Normalized Application-Specific 43 3.6.2.2. Scoring 2: Scaled by Sharing . . . . . . . 43 3.6.2.3. Scoring 3: Geometric Mean of Sharing . . 44 3.6.2.4. Scoring 4: Random-Scaled Sharing . . . . 44 3.7. Estimating Performance and Area . . . . . . . . . . . . . . 45 3.8. Experimental Setup . . . . . . . . . . . . . . . . . . . . . . 46 3.9. Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.9.1. DAG vs TED vs Hybrid . . . . . . . . . . . . . . . . 49 3.9.2. Domain-Specific Scoring . . . . . . . . . . . . . . . 53 3.9.3. Application-Specific vs Domain-Specific Configurations . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.9.4. Custom Instruction Analysis . . . . . . . . . . . . . 59 3.9.5. Cross-Validation . . . . . . . . . . . . . . . . . . . . 61 3.10. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4. Partially Similar Domain-Specific Instructions 65 4.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.2. Context and Motivation . . . . . . . . . . . . . . . . . . . . 66 4.3. MInGLE Framework . . . . . . . . . . . . . . . . . . . . . . 68 4.4. Candidates Extraction: From Application Code to Hardware Acceleration . . . . . . . . . . . . . . . . . . . . . . . 68 4.5. Canonicalization of Custom Instructions using Merging Diagrams ............................. 70 4.5.1. Merging Diagram Construction . . . . . . . . . . . 71 4.5.2. Global diagram of variants . . . . . . . . . . . . . . 74 4.6. Generation of Merged Custom Instructions . . . . . . . . . . 74 4.6.1. Distance Calculation . . . . . . . . . . . . . . . . . 74 Table of Contents xiii 4.6.2. Clustering Custom Instruction Variants . . . . . . . 74 4.6.3. Merging Estimation and Modeling . . . . . . . . . . 76 4.7. Custom Instruction Selection for an Area Constrained Configuration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4.8. Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4.9. Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4.9.1. Experimental Setup . . . . . . . . . . . . . . . . . . 79 4.9.2. Results and Discussion . . . . . . . . . . . . . . . . 81 4.10. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 5. Fragments of Domain-Specific Instructions 87 5.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 87 5.2. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.3. MInGLE+ Automatic Framework . . . . . . . . . . . . . . . 90 5.4. Generation of Custom Instruction Fragments . . . . . . . . 92 5.5. Distance and Matching Calculation . . . . . . . . . . . . . . 94 5.6. Custom Instruction Selection with Fragments . . . . . . . . 95 5.7. Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 5.7.1. Experimental Setup . . . . . . . . . . . . . . . . . . 96 5.7.2. Results . . . . . . . . . . . . . . . . . . . . . . . . . 97 5.7.2.1. Speedup and EDP Improvement . . . . . 97 5.7.2.2. Threshold Analysis . . . . . . . . . . . . 101 5.7.2.3. Sharing Characterization . . . . . . . . . 103 5.8. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 6. Conclusion 107 6.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 6.2. Future work . . . . . . . . . . . . . . . . . . . . . . . . . . 110 List of Figures 1.1. Automated process for CI generation and key contributions . 6 2.1. Generic target architecture with SFU . . . . . . . . . . . . . 16 2.2. Implementation of a merged CI that executes on a DSFU . . 19 2.3. DSFU with a configuration manager to reprogram CIs . . . 20 2.4. Intel Atom processor pipeline with a tightly-coupled DSFU . 21 2.5. Chronogram of instructions on a pipeline with a tightlycoupled DSFU . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.6. Example of a reduced and ordered BDD construction . . . . 27 2.7. Example of a canonical TED construction . . . . . . . . . . 29 3.1. Schematic overview of the CI selection and evaluation framework FuSInG .......................... 36 3.2. Examples of the usage of TEDs for instruction clustering . . 39 3.3. Results of benchmark speedup versus CI area for DAG, TED and Hybrid methods with domain-specific CIs (part 1/2) . . 50 3.4. Results of benchmark speedup versus CI area for DAG, TED and Hybrid methods with domain-specific CIs (part 2/2) . . 51 3.5. Results of benchmark speedup versus SFU area for scoring techniques with domain-specific CIs (part 1/2) . . . . . . . . 54 3.6. Results of benchmark speedup versus SFU area for scoring techniques with domain-specific CIs (part 2/2) . . . . . . . . 55 3.7. Results of benchmark speedup versus SFU area using only application-specific, application and domain-specific, or only domain-specific CIs (part 1/2) . . . . . . . . . . . . . . . . . 57 3.8. Results of benchmark speedup versus SFU area using only application-specific, application and domain-specific, or only domain-specific CIs (part 2/2) . . . . . . . . . . . . . . . . . 58 3.9. Results of benchmark speedup versus SFU area for crossvalidation per application using domain-specific CIs (part 1/2) ............................... 62 xvi List of Figures 3.10. Results of benchmark speedup versus SFU area for crossvalidation per application using domain-specific CIs (part 2/2) ............................... 63 4.1. MInGLE framework for the implementation and generation of partially-merged CIs . . . . . . . . . . . . . . . . . . . . 69 4.2. Example of Merging Diagram construction . . . . . . . . . . 72 4.3. Hierarchical clustering of CIs . . . . . . . . . . . . . . . . . 75 4.4. Average speedup versus percentage of area occupancy of the DSFU for exact and partial matching methods . . . . . . 82 4.5. Average EDP improvement versus percentage of area occupancy of the DSFU for exact and partial matching methods . 82 4.6. Speedup for each benchmark at a limited implementation area 83 4.7. EDP improvement for each benchmark at a limited implementation area . . . . . . . . . . . . . . . . . . . . . . . . . 84 5.1. Example of partial merging without and with CI fragments . 89 5.2. MInGLE+ automated framework for the generation of CIs with fragments . . . . . . . . . . . . . . . . . . . . . . . . . 91 5.3. Average speedups against increasing area percentages for exact and partial matching and matching with fragments . . 98 5.4. Average EDP improvements against increasing area percentages for exact and partial matching and matching with fragments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 5.5. EDP improvement for each benchmark with CIs selected across basic blocks with fragments, partial matching and exact matching . . . . . . . . . . . . . . . . . . . . . . . . . 100 5.6. Percentage of area versus average EDP improvement for the matching with fragments for different thresholds . . . . . . 101 5.7. Characterization of shared FPGA hardware for different area utilizations with partial matching . . . . . . . . . . . . . . . 104 5.8. Characterization of shared FPGA hardware for different area utilizations with fragments . . . . . . . . . . . . . . . . . . 104 List of Tables 2.1. Extensions to the base ISA to operate the DSFU . . . . . . . 23 3.1. Description of the evaluated application benchmarks and their input files......................... 47 3.2. Number of code sequences and CIs found in each application with DAG, TED and Hybrid methods, and the percentage of dynamic instructions covered by them . . . . . . . . 48 3.3. Classification of CIs in a full-system configuration of 5%, 10% and 15% of the SPARC area . . . . . . . . . . . . . . . 60 4.1. Percentages of area occupancy and EDP improvement for different CI implementations . . . . . . . . . . . . . . . . . 67 4.2. List of the evaluated applications and benchmarks suites . . 80 5.1. For each application, number of CIs and CI variants considered, the percentage of dynamic instructions covered by them, and the number of candidates found . . . . . . . . . . 96 5.2. Number of candidates in the selection step and time to solve the selection problem for different thresholds using matching with fragments . . . . . . . . . . . . . . . . . . . . . 102 List of Acronyms ARM Advanced RISC Machines ASIP Application-Specific Instruction Processor ASIC Application-Specific Integrated Circuit BDD Binary Decision Diagram CFG Control Flow Graph CI Custom Instruction CMOS Complementary Metal-Oxide-Semiconductor DAG Directed Acyclic Graph DFG Data Flow Graph DMA Direct Memory Access DSFU Domain-Specific Functional Unit EDP Energy-Delay Product FPGA Field Programmable Gate Array GPU Graphics Processing Unit HLS High Level Synthesis INF If-then-else Normal Form IR Intermediate Representation ISA Instruction Set Architecture xx Acronyms ISEF Instruction Set Extension Fabric ITE If Then Else (operator) MILP Mixed Integer Linear Programming MISO Multiple Input Single Output MIMO Multiple Input Multiple Output RISC Reduced Instruction Set Computing ROBDD Reduced Ordered Binary Decision Diagram SFU Specialized Functional Unit SMT Simultaneous Multithreading SRAM Static Random-Access Memory SSA Static Single Assignment TED Taylor Expansion Diagram VLIW Very Long Instruction Word 6 Introduction Identification of CI candidates Selection of CI candidates SFU 1A Functionally Equivalent CIs 2A Domain-specific Heuristic-based 1B Partially Similar CIs 2B Domain-specific Constraint-based 1C Fragments of CIs Automatic Custom Instruction Generation Contributions Frameworks Configuration Application within basic blocks + across basic blocks + reuse & area efficiency optimize performance + optimize energy FuSInG MInGLE MInGLE+ Figure 1.1: The automated process for CI generation and the key contributions of this dissertation. trade-offs have to be carefully weighed to achieve full efficiency in every sense of the word. 1.4. Key Contributions In this dissertation, we explore different approaches for CI generation, focusing on domain-specific acceleration. Figure 1.1 shows, on the top, a high-level schema of the CI generation process; an application is analyzed to identify CI candidates, and a subset of the best candidates is selected to configure the SFU. The figure also shows, on the bottom, our key contributions; we expand and improve the identification in contributions 1-A, B and C, and we provide alternatives to the candidate selection problem in contributions 2-A and B. The contributions are implemented within these frameworks: FuSInG (Functionally Similar Instructions Generator), which implements 1-A and 2-A; MInGLE (Merged Instructions Generator for Large Efficiency), which implements 1-B and 2-B, and MInGLE+, expanded with 1-C. Introduction 7 Contribution 1-A: Identification of functionally equivalent custom instructions Limiting ASIPs to application-specific acceleration makes them feasible for only big-volume markets with high returns. Therefore, creating CIs that target a whole domain is an economically viable solution. However, the disparity among coding styles of different programs makes it difficult to identify code patterns that can be represented by a unique CI across applications. We therefore propose an analysis at the basic block level, complementary to CI candidate identification, that identifies equivalent CIs within the same program and across different programs. We use the Taylor Expansion Diagram (TED) canonical representation to identify common sections of code that can be accelerated by specialized hardware. As TEDs are canonical, we can find not only structurally equivalent pieces of code, but also functionally similar ones. Functional equivalence reveals if CIs perform the same mathematical function, which cannot be guessed with a DFG- based representation. We compare them to a straightforward technique of directed acyclic graph (DAG) isomorphism detection, which essentially reveals whether graphs are similar in shape. We also introduce a new Hybrid DAG/TED technique that combines the best of the traditional graph isomorphism with TEDs. With any of the three techniques, we can identify CI candidates that are specific for either an application or a domain. We find that, with the canonical representation, we can identify more sequences across applications that are mapped to the same CI, thus achieving higher speedups for smaller chip area than the traditionally used DAGs. Contribution 1-B: Identification of partially similar custom instructions Hardware reusability across applications is a critical factor to achieve high and balanced speedups with CIs, yet if there are not enough equivalences, CIs cannot be generalized for a domain. This issue arises more frequently when we target larger code sections to obtain higher performance. Consequently, we introduce a new canonical representation of CIs across basic blocks, the Merging Diagram, to facilitate similarity detection and improve the code coverage of our CIs. It builds upon the previous Hybrid DAG/TEG representation to provide a more compact representation with predication, spanning CIs across basic blocks. We also propose clusteringbased partial matching of code sequences to identify not only those CIs that are functionally equivalent, but also those with partial similarities. Clustered CIs are merged and we quantify their potential improvement of cove- 8 Introduction ring more code while reducing the needed area for the CI implementation. These techniques expand the opportunity for CIs with a limited area budget inside simple processors to accelerate numerous applications from a domain, improving the system’s energy efficiency. Contribution 1-C: Identification of custom instruction fragments We have observed that partially-similar domain-specific CIs outperform application-specific ones when the area for implementation is over a given threshold. However, at small areas, we have to rely on application-specific CIs, since the potential gains of merging two CIs do not compensate for the involved overhead. To solve this, we extend CI merging with an analysis step that detects parts of CIs that can use the existing merged clusters with minimal extra overhead. We call CI fragments to those parts of CIs, since they do not include the full original CI as in the partially similar CIs, but only sections of it. With CI fragments we can improve reutilization of hardware at the most limited areas, because we partially reuse an already merged CI cluster, with minimum additional overhead. Contribution 2-A: Domain-specific heuristic-based selection At the last step of any CI generation process, the final selection tries to choose a subset of CIs that fits within the available area. The objective of getting an optimal CI group is an NP-complete problem, and thus there exists no known fast solution for it. Also, the CI design space of a whole application domain is big enough to make the task computationally challenging. Typically, approximate algorithms or heuristics are used to solve the selection fast. The main drawback of existing methods is that they target speedup for individual applications. Therefore, their suitability for a whole domain is rather limited, since the gains must be balanced to be fair across applications. To bridge this gap, we propose four scoring heuristics to quickly and effectively cull the huge CI design space. These heuristics rank potential CIs under the premise that we aim to smoothen the obtained gains across applications. We evaluate them and give insight about their suitability for domain-specific acceleration. Introduction 9 Contribution 2-B: Domain-specific energy-efficient selection Having proved that the CI selection is appropriate for a domain of applications, we go a step further by introducing energy efficiency into the equation. Speedup is an excellent metric to select a set of CIs that accelerate the applications, hence it has been extensively used in the literature. However, for devices with limited power budgets, focusing only on performance can be detrimental for the design, since we may be introducing power-hungry CIs as well. This last contribution proposes a constraint-based selection mechanism that, with a novel objective function, balances speedup and energy consumption to fulfill the goal of a energy-efficient design with good performance. We then solve the problem of choosing an energy-efficient set of CIs to fit in limited area while accelerating a domain harmoniously. 1.5. Key Results We summarize here the key results obtained with the frameworks that implement the contributions: FuSInG,MInGLE and MInGLE+. FuSInG We combine the techniques for functional equivalence identification and the scoring heuristics in our automated framework FuSInG, which also estimates performance and area of new acceleration designs. With the framework, we explore the trade-offs between application-specific and domain-specific hardware specialization. Results expose the following insights: TED and Hybrid DAG/TED representations identify more hardware acceleration opportunities across applications that are mapped to the same CI, which results in higher speedups for lower area than the traditionally used DAGs. While using only application-specific CIs results in the highest possible speedups at unbounded core areas, it is ineffective at small areas. Instead, including domain-specific CIs in the configuration produces the highest possible speedup at small, more realistic core areas, which underlines the importance of identifying CIs that can be shared across applications. 10 Introduction New applications inside a domain can also benefit from CIs already designed for that domain. This suggests that processors with domainspecific functional units can extend their lifetime, making specialization more generally applicable. MInGLE Partial matching of Merging Diagrams expands the acceleration opportunities for domain-specific CIs with a limited area budget, improving the system’s energy efficiency. We implement these techniques in our automated framework MInGLE, and we evaluate them with applications from the media domain. We obtain the following key results: CIs that cover code beyond the basic block level expand the acceleration opportunities, achieving a maximum average speedup of 1.98× and an energy-delay product (EDP) improvement of 3.35×, a significant gain over CIs within a single basic block (speedup of 1.48×and EDP improvement of 1.67×). Partial matching and merging of CIs is crucial for achieving larger speedup and EDP improvement for a limited hardware area. For instance, for 1.8% of the area, the EDP improvement of partial matching reaches 3.04×, higher than a exact matching CI configuration (2.53×). MInGLE+ We extend the analysis in MInGLE+ to detect fragments of CIs that can use the existing merged clusters with minimal area overhead. These are the outcomes of this extension: CI fragments increase the share-out of the circuit components on an SFU at better rate than partial matching, which results in more implementation area available. This means that we achieve a particular energy efficiency at greatly reduced hardware area. CI fragments are key to get high performance and energy efficiency at the smallest areas. For example, for 1% of the area, CIs with fragments achieve, on average, a speedup of 2×and an EDP improvement of 3.6×, significantly higher than results for partially matched CIs (speedup of 1.6×and EDP improvement of 3.6×) Introduction 11 1.6. Publications The above contributions and results are gathered in several international journals and conference proceedings. Contributions 1-A and 2-A, with focus on the identification and selection of functionally equivalent CIs for an application domain, were published in: C. González-Álvarez, J. B. Sartor, C. Álvarez, D. Jiménez-González, and L. Eeckhout. “Accelerating an application domain with specialized functional units”. ACM Transactions on Architecture and Code Optimization (TACO), Vol 10, No 4, January 2014. Contributions 1-B and 2-B, that go a step further identifying and selecting domain-specific partially-similar energy-efficient CIs, were published in: C. González-Álvarez, J. B. Sartor, C. Álvarez, D. Jiménez-González, and L. Eeckhout. “Automatic Design of Domain-Specific Instructions for Low-Power Processors”. Proceedings of the 26th IEEE International Conference on Application-specific Systems, Architectures and Processors (ASAP), 2015. Best student paper award. Contribution 1-C, that extends previous contributions to allow maximum efficiency at small hardware areas, will be published in: C. González-Álvarez, J. B. Sartor, C. Álvarez, D. Jiménez-González, and L. Eeckhout. “MInGLE: An Efficient Framework for Domain Acceleration using Low-Power Specialized Functional Units”. ACM Transactions on Architecture and Code Optimization (TACO), 2015. Under review. 1.6.1. Other research activities In addition to the publications above, we list here other research activities that are not included in this dissertation. These include studies of automatic parallelization for heterogeneous multicores, as well as automatically generated accelerators integration in multicore systems, using the OSCAR source-to-source compiler and runtime. We refer to the original articles for more information: C. González-Álvarez, Y. Kanehagi, K. Takemoto, Y. Kishimoto, K. Muto, H. Mikami, A. Hayashi, K. Kimura, H. Kasahara. “Automatic 12 Introduction parallelization with OSCAR API Analyzer: a cross-platform performance evaluation”. IPSJ SIG Notes, Dec 2012. Information Processing Society of Japan (IPSJ). C. González-Álvarez, H. Ishikawa, A. Hayashi, D. Jiménez-González, C. Álvarez, K. Kimura and H. Kasahara. “Automatic design exploration framework for multicores with reconfigurable accelerators”. 7th HiPEAC Workshop on Reconfigurable Computing (WRC 2013). K. Kimura, C. González-Álvarez, A. Hayashi, H. Mikami, M. Shimaoka, J. Shirako, H. Kasahara, “OSCAR API v2.1: Extensions for an advanced accelerator control scheme to a low-power multicore API”, 17th Workshop on Compilers for Parallel Computing (CPC2013), Lyon, France, Jul. 2013. 1.7. Overview This dissertation is organized as follows. In Chapter 2, we present the necessary background information on hardware acceleration. We give an overview of relevant design techniques and accelerator architectures found in the literature, narrowing the research focus to processors with specialized functional units that execute CIs. We provide the design details of an extended processor that we use in our experiments, and we close the chapter with additional background information on code representations. We present two key contributions in Chapter 3. First, we introduce the techniques to identify equivalent CIs that can be clustered together. Then, we explain a set of heuristics developed for domain-specific selection. Lastly, we evaluate the presented methodologies for a concrete application domain and present insights on the trade-offof application-specific and domain-specific acceleration. In Chapter 4, we introduce two more key contributions. We firstly describe the methodology behind the identification of partially-similar CIs, and secondly, the selection mechanism to choose the most efficient configuration of CIs. We introduce in Chapter 5 our last contribution. We explain the concept of fragments of CIs, presenting the techniques to extract and implement them, and we demonstrate their effectiveness comparing the results against previously proposed methods. Finally, we present the conclusions of this dissertation in Chapter 6 and we discuss possible future research directions. 2 Background 2.1. Introduction Hardware acceleration, in its many forms, has emerged as a solution to the demands of high performance and low power in the embedded market. A cost-effective approach is to extend a baseline processor with specialized hardware and its ISA with new custom instructions. The hardware is augmented as functional units, tightly-coupled to the processor’s datapath, or coprocessors, intra or outer-core, working as a slave of the main processor. Datapath specialization can be approached from different perspectives, depending on the focus of the problem. First, from the top-down point of view of creating hardware starting from a set of target applications, we can consider automated design CIs, also known as instruction set extensions. Generally, methods explore the target applications’ critical code and translate them to hardware under some constraints. We review those exploration techniques in Section 2.2. From another angle, a bottom-up process involves creating the configurable accelerator design based on architectural expertise. The focus is on creating specialized hardware, possibly configurable, in a less automated way, and then map applications on the hardware to accelerate them. Those architectural proposals are surveyed in Section 2.3, with a specific focus on tightly-coupled accelerators. Independently from the perspective, hardware acceleration is a complex process that involves more than exploration and architectural design. Once 14 Background the design is ready, the actual circuit implementation is a step necessary to prove the suitability of the accelerator. In the latest years, high level synthesis (HLS) programs, such as Vivado HLS [9], have contributed to speed up the implementation step. Different compilation phases are also involved, such as instruction selection once the hardware is created. We do not cover that step in this dissertation, assuming that we can annotate code to substitute lines of code by the accelerating CI. However, Section 2.4 includes background information on compilers’ intermediate representations (IRs) and other coding models that are relevant for the upcoming chapters. 2.2. Custom Instruction Design There are many techniques for CI design from the ISA extension perspective that target different objectives and architectures. We provide here a comprehensive survey of evolution of the field through the most important works found in the literature. The first work on the topic [10] proposes to partition the main problem of instruction generation into regularity extraction and template matching, which we have previously introduced as generation of CIs, and the substitution of generic code by CIs. They do not provide any implementation of their ideas neither in hardware nor in simulation, but estimate quantitatively the gains depending on the instruction types. In the first description [11] of CI operations types MISO (Multiple Input Single Output) and MIMO (Multiple Input Multiple Output), the authors discuss architectural constraints, such as register ports, in their identification of new instructions within the VLIW compiler Trimaran. Later work [12,13] formally establish the analysis using Data Flow Graphs (DFG), and the importance of preserving graph convexity. The research focus shifts to the design process problem and clearly separates identification and selection phases. Reducing the algorithmic complexity of the design methods is a priority to make the program tractable. Some works rely on heuristics [14] to predict a CI’s gain as a function of the instruction’s frequency of execution and latency, and on dynamic programming to optimize area usage. Pipelining techniques [15] allow CIs with more inputs and outputs than ports in the register file. A later work by the same authors [16] couple the identification and selection phases, which results in relaxing the constraints and opens up the possibility of approximate techniques and genetic algorithms that are computationally less expensive. Their CIs have any number of outputs, and are evaluated with a software latency model using the hardware measurements of CMOS operators. Others [17] assume that the core processor must be a RISC, which also relaxes constraints. This implies a limited number Chapter 2 15 of inputs and outputs, which prunes the results, in order to minimize the number of registers used. A different work for the application-specific embedded market [18] assumes additional storage inside an ARM-based ASIP that allows DMA for some vectors. They select CIs with a merit function based on a latency estimation of memory accesses as a model of SRAM. In their experiments with decoder, filter and encryption applications the CIs are simulated in Simplescalar. Breaking with the application-specific CI design trends, the generation of domain-specific CIs [19] involves a pattern-matching approach on the data-flow graph using heuristics. They define guide functions for a greedy search that prune the exploration space, using the criticality of the datapath, latency and area as metrics. Most notably, they combine instruction candidates to generalize the accelerators for a simulated VLIW architecture within Trimaran. Also integrated in Trimaran, ASIP extensions for multimedia and cryptography applications based on identification of maximal convex subgraphs within a basic block [20], could be adapted for domainspecific acceleration, since they group graphs that can be implemented with the same hardware and estimate their gain to choose the most promising one. The concept of maximal convex subgraph, or the maximum code coverage that we can get in a basic block without violating any constraint, is further studied [21]. They propose a fast CI identification algorithm [21] based on binary search, that we adapt in our domain-specific framework described in Chapter 3. Other approaches to solve the CI design problem include applying integer linear programming [22,23] or constraint programming [24] at only the CI identification, or at any of the CI design steps. Alternatively, other authors [25] apply a predefined set of rules, in a specific order, to obtain a DAG representation of code functionality instead of focusing on the structure of CI subgraphs, which is related to the techniques we see in this dissertation. 2.3. Datapath Accelerators A common accelerator classification [26] categorizes architectures according to their size and proximity to the CPU. On one hand, looselycoupled systems, or coprocessors, accelerate coarse-grained tasks with low interaction with the rest of the program, and imply a manual approach to hardware/software partitioning. An example of such a loosely-coupled system is GARP [27], in which a MIPS processor invokes special instructions that run on a custom coprocessor, outside the main core. On the other hand, tightly-coupled systems, or specialized functional units (SFUs), 22 Background example for the DSFU integration. The Atom processor is in-order and lowpower, with one or two cores, each one running up to two threads. For simplicity, we do not consider its simultaneous multithreading (SMT) features at the moment. Although Atom processors implement the x86 instruction set, some versions support the x86-64 instruction set as well, which we take as the baseline ISA here. Microarchitecture details Figure 2.4 shows a diagram of an Atom processor extended with an embedded DSFU. The pipeline stages are also depicted at the top of the Figure. Concretely, the pipeline has sixteen stages: three for instruction fetch, three for decoding, three for issue, three for data access, one for execution and three for exception handling and write-back. We modify the instruction decode stage of the baseline processor to support CIs. The lookup table for the translation of instructions (XLAT) is extended with the additional instructions needed for the DSFU. The DSFU’s 16 128-bit input registers are directly connected for reading from both the integer (64-bit) and SIMD/XMM (128-bit) register files. A load from memory to an integer register (cache read) takes 1 or 3 cycles, while a load to a XMM register takes 4 cycles. Depending on the situation, we will read from one or another register file to minimize latency. The 32 64-bit output registers are only connected to the integer register file, since a store always takes 1 cycle, while a XMM store is set in 5 cycles. DSFU’s input and output registers operate at the same clock frequency as the main processor. However, the reconfigurable part of the DSFU where the CIs execute may operate at a different frequency than the main processor, depending on the reconfigurable hardware technology. Thus, there is a DSFU clock that is isochronous to the core clock; in other words, DSFU’s period is a multiple of the core’s period (for instance, there is a 1:4 ratio for an Atom core operating at 1.6 GHz and an FPGA set at 400 MHz). To keep the clocks synchronized, at the beginning of a DSFU execution, the decoding stage sends a reset signal to the DSFU clock before executing the requested CI. The configuration manager, responsible for reprogramming the DSFU CIs, is directly connected to main memory to load the configuration data. ISA extensions We extend the x86-64 based ISA with the instructions in Table 2.1, whose encodings are compatible with those of the Atom processor. The Chapter 2 23 Instruction Operands Latency Description RF2DSFU_i dsfu_in, r 1Moves 64-bit of data from an integer register to a DSFU input register. RF2DSFU_x dsfu_in, x 1Moves 128-bit of data from an XMM register to a DSFU input register. DSFU2RF r, dsfu_out 1 Moves 64-bit of data from a DSFU output register to an integer register. DSFU_exec config, i/r/x 4×CResets DSFU internal clock and starts execution of the CI determined by config. The second operand may be used to transfer data to a determined input register. DSFU_configm, i F(i)Reads inumber of bytes from mmemory location and reconfigures the CI implementation space of the DSFU with that configuration. Table 2.1: Extensions to the base ISA to operate the DSFU. Conventions: i = immediate data, r = integer register, x = 128 bit xmm register, dsfu_in = DSFU’s input register, dsfu_out = DSFU’s output register, C = number of DSFU internal cycles. Operands are determined in Intel syntax (destination, source). first two instructions, RF2DSFU_i and RF2DSFU_x, move data from the register files to the DSFU input registers. When we need a memory access of at least 128-bit data whose address was recently calculated, it is better to use an XMM register (4 cycles versus 3×2cycles to load). In all other cases we prefer to use the integer registers. The third instruction sends the data from the output registers to the integer register file, ready for write back. A single instruction DSFU_exec is added to execute CIs. The config signal that chooses the CI configuration is passed as the first operand, allowing up to 256 different configurations. The second operand is data needed in the 24 Background 0123456789 clk core decoder inst core RF2DSFU DSFUexec DSFU2RF inst core inst core FU exec exec regs move RF>Input Output>RF DSFU exec ready reset clk DSFU Figure 2.5: Chronogram of a sequence of instructions executing on a pipeline with an integrated DSFU. DSFU execution, saving in the best case one cycle of a transfer instruction. When we try to execute a non-configured CI, an exception is triggered and the equivalent code in the non-extended ISA will be executed. The latency is determined for a DSFU that runs 4×slower than the Atom core. Therefore, the latency of the DSFU_exec instruction is the number of internal cycles C that the CI takes in the DSFU, scaled to the core clock. Finally, the DSFU_configinstruction loads from the specified memory address a whole new configuration of the specified size. The latency of this instruction depends on the number of bytes to read and the memory bandwidth. Chronogram Figure 2.5 shows an example of the execution of a CI, displayed as a chronogram with different pipeline stages and signals involved. We have two clocks: the core clock in the first row, and the DSFU clock in the last one. Cycles in the upper part are counted as part of the core clock. After the core clock signal, we show the instructions decoded (decode), execution in normal functional units (FU), data moves between register files and DSFU registers (regs move), execution on the DSFU (DSFU), and the ready and reset signals. For simplicity, we assume that the instruction decode stage takes 1 cycle, though in Atom it would take 3 cycles. Also, the gap between decoding and execution would be wider in a real setting. In cycle 1, the decoder processes a data transfer instruction that results in a register move in cycle 2. In cycle 2, the instruction that starts the DSFU execution is decoded, setting the reset signal until the end of the cycle, which triggers a reset of the DSFU clock. In cycle 3, the execution of the CI on the DSFU starts, while the decoder processes the instruction that reads the DSFU output, and then stalls. At the end of the DSFU execution the ready signal is set, triggering the moves from the output registers to the Chapter 2 25 register file and resuming the stalled pipeline. 2.4. Intermediate Code Representations In this section, we examine the most relevant intermediate representations (IR) for this dissertation. These code representations are created for transforming an application’s high-level code to an abstract description, in which significant features are highlighted. First, we discuss in Section 2.4.1 those models that represent the code’s structure and flow, and we then review the canonical representation alternatives in Section 2.4.2. 2.4.1. Structural Representations A data flow graph (DFG) is a well-known and widely-used representation that exposes the data dependences of operations within a basic block. It is built as a directed acyclic graph (DAG) G(V ,E), with Vthe nodes that represent the operations, and Ethe edges that stand for the data dependencies between nodes. Most of the CI design algorithms in Section 2.2 start from this representation to solve the candidate identification problem. The main advantage of this representation is that we can expose structural constraints naturally as the DAG imposes a strict topological order to the operations. In CI design, not all the operations of a basic block are included to be accelerated; the most common case is to avoid memory and branch operations. The resulting subgraph G′after suppressing those invalid nodes may contain a structural hazard that make instruction scheduling infeasible. Therefore, CI design algorithms have to ensure that G′is convex; that is, there does not exist any path in Gfrom a node u∈G′to another node v∈G′which involves a node w<G′. Although DFGs have proved their validity for application-specific CI design, we question the use of DAG-formed basic blocks for domain-specific CI generation in Chapter 3. 2.4.1.1. IR and SelectionDAG in LLVM LLVM [44] is our compiler of choice at several phases of the frameworks we develop. Thus, we describe briefly here two representations within LLVM that are relevant for our tools, LLVM-IR and the SelectionDAG. LLVM-IR, produced after the first compiler’s frontend passes is the common code representation used for analysis and optimizations in LLVM. It is based on Static Single Assignment (SSA) and it is microarchitecture independent, though still representing type safety and low-level operations. The 26 Background IR is distinctly used in three forms: as in-memory C++ classes, as on-disk bitcode, and as assembly-like human-readable language. The assembly is a strongly typed RISC instruction set which abstracts away details of the target, for instance, using unlimited virtual registers. Basic block limits are clearly marked, as well as control flow through SSA’s φ(Phi) functions. If auto-vectorization is activated in the frontend, the IR is also able to represent vector operations. This last form is the most common used one, and we work with it at several points of our frameworks: for profiling in FuSInG (Chapter 3), and for both profiling and HLS in MInGLE (Chapters 4 and 5). The SelectionDAG is a code abstraction found in several backend phases of LLVM. It passes through different transformations, starting from an IR- close form to a more final microarchitecture specific representation. This representation facilitates the compiler’s instruction selection phase that uses pattern matching techniques, as well as low-level target-independent optimizations. The SelectionDAG is a directed acyclic graph whose nodes are operation codes – the operation performed and the operands involved. It has two different kinds of edges: those to represent data flow dependencies, and those to represent control flow ones. We isolate and work on the DFG of the SelectionDAG of individual basic blocks just before the instruction selection phase in LLVM’s backend. We use it for the DFG Explorer step that extracts the CI candidates in the FuSInG framework of Chapter 3. 2.4.2. Canonical Diagrams A canonical representation presents a unique description for a given mathematical object, such as a graph, as a mathematical expression. With a canonical form we can test, for instance, if two graphs are equal. This is different to the graph isomorphism commonly applied to DFGs where we check the structural equivalence of two graphs. In the case of canonical representations, we aim to test the semantic equality of the mathematical expressions that the graphs represent, or in other words, if they are functionally equivalent. Although there is vast work in graph-based canonical representations, here we focus on the relevant ones for this dissertation: Binary Decision Diagrams (BDDs), that represent binary functions, in Section 2.4.2.1, and Taylor Expansion Diagrams (TEDs), that can express work-level functions, in Section 2.4.2.2. 2.4.2.1. Binary Decision Diagrams A binary decision diagram (BDD) [45] represents a binary function as a rooted graph, based on a recursive Shannon decomposition, which com- Chapter 2 27 x1 x2x2 x3x3x3x3 0 1 0 1 0 1 0 1 x1 x2x2 x3x3x3x3 1 0 x1 x2x2 x3x3x3 1 0 x1 x2x2 x3 1 0 x1 x2 x3 1 0 Recursive Shannon expansion Collapse leaf nodes Remove redundant tests Isomorphic subgraphs Remove redundant ROBDD 1. 2. 3. 4. Figure 2.6: Example of a reduced and ordered BDD construction for Boolean functions f1= (x1∧x3)∨(x2∧x3)and f2= (x1∨x2)∧x3, with variable order [x1,x2,x3]. bined with a set of reduction rules, makes the BDD minimal and canonical for a given ordering of variables. BDDs have been applied in formal verification problems, such as correctness check of circuit implementations. BDDs represent Boolean functions that determine Boolean values from logical calculations on Boolean inputs. The representation is a rooted DAG with several decision and terminal nodes, all connected by decision edges. The initial node stands for the top Boolean formula. Non-terminal, decision, or internal nodes are labeled as a Boolean variable wand have one out-edge 0(then) and one out-edge 1(else), Each non-terminal node represents the Boolean function corresponding to its 1edge if wevaluates to 1, or to its 0 edge if wevaluates to 0, building up the top formula down to the terminals. Terminal nodes are labeled as 0 or 1, representing the Boolean functions 0 and 1. Figure 2.6 shows and example of BDD construction, explained in detail later. The rightmost graph is the final BDD of the Boolean function f1= (x1∧x3)∨(x2∧x3). Each node represents one of the Boolean variables hx1,x2,x3i, and in this graphical representation, edges labeled with 0 are dashed and with 1 are solid. The if-then-else normal form (INF) represents a Boolean function using the if-then-else (ITE) operator. For inputs {x,y,z}, ITE computes if x then y else z, which is equivalent to: ITE(x,y,z) = (x∧y)∨(¯ x∧z),(2.1) with variable xevaluating to 1 or to 0. Multivariate boolean functions can be expressed by recursive decomposition as a Shannon expansion using the ITE operator: f(x0,...,xn) = ITE(xn,f1(x0,...,xn−1),f0(x0,...,xn−1).(2.2) Thus, the BDD is built performing the ITE logical function at each node, operating in time proportional to the size of the resulting function graph. 28 Background A BDD composed of INF expressions, with all equal ITE nodes shared, and with variables appearing in the same order and at most once in any path from root to leaf, is called reduced ordered binary decision diagram (ROBDD). Such BDDs are canonical since each derivation of a particular Boolean function leads to the same representation. The variables in the ROBDD must have a specific order definition used to build the diagram recursively. Therefore, in ordered BDDs different variables appear in the same order from root to leaf in each expression path. For an ordered list of variables L= [v1,...,vn]without duplicates, a BDD Bhas an ordering [v1,...,vn]if all the variable labels of Boccur in [v1,...,vn], and if vjfollows vion a path in B, then j > i. The orderings of two BDDs B and B′are compatible if there are no variables hv,wisuch that vis before w in the ordering for B, and wis before vin the ordering for B′. The example of Figure 2.6 follows the variable ordering [x1,x2,x3]to apply the required recursive Shannon expansion in step 1. To reach a full reduced BDD, reduction operations are applied to simplify the diagram to its maximum. First, duplicated terminals are removed; if there is more than one 0terminal nodes, all edges pointing to them are redirected to just one of the 0node. The same applies to 1terminal nodes. Then, redundant tests are also removed; if the two outgoing edges of a node vpoint to the same node w,vis removed and its incoming edges are redirected w. And finally, duplicated non-terminals are removed as well; if two different nodes vand ware the roots of identical sub-BDDs, eliminate v and redirect its incoming edges to w. In the example of Figure 2.6, duplicated terminals are removed and collapsed in step 2. Then, a redundant test with variable x3is also removed in step 3, while step 4detects and collapses all the identical x3sub-BDDs. Finally, the reduced and ordered BDD is obtained removing in the last step redundant tests once again. The reduced and ordered BDD is a canonical form of a logic function. This means that two functions with compatible variable orderings are equivalent if the ROBDD for each function are isomorphic. For instance, the ROBDD of Figure 2.6 represents not only Boolean function f1= (x1∧x3)∨(x2∧x3), but also the function f2= (x1∨x2)∧x3. This property makes it useful in functional equivalence checking of Boolean functions, and we make use of this feature in the MInGLE framework (Chapters 4 and 5). 2.4.2.2. Taylor Expansion Diagrams A Taylor Expansion Diagram (TED) [46] is a canonical, graph-based representation like BDDs, but whose decomposition is non-binary. Such a representation raises the level of abstraction to allow word-level algebraic Chapter 2 29 x 0 2 First variable expansion -y^2 -1 Reduction x 2 y -2 Normalization x y ONE Second variable expansion x 0 2 y 0 -20 v f(0) f'(0) f''(0)/2 Node decomposition representation TED 3.2.1. Figure 2.7: Example of a TED construction for the polynomials f1= (x+y)(x−y) and f2=x2−y2, with variable order [x,y]. symbols with lower memory requirements than binary-based representations. TEDs are based on the Taylor series expansion which, for a multivariate algebraic expression f(x,y,...), is represented as follows: f(x,y,...) = f(0,y,z,...)+xf ′(0,y,z,...)+ 1 2x2f′′(0,y,z,...)+..., (2.3) where the origin is set in x= 0 and with f′(x= 0) and f′′(x= 0) as the successive derivatives of f(x= 0). The individual terms of the expression are then decomposed with respect to the remaining variables on which they depend (y,..., etc.), This decomposition, applied recursively at each algebraic function derived, is stored in a directed acyclic graph, the Taylor Expansion Diagram. A TED is composed of a root ρ, a set of nodes V, a set of edges E, and terminals T. The root represents the multivariate polynomial φthat the TED expresses. Each node v∈Vhas an index that identifies an input variable and it is related to a specific decomposing order. For a node v, the function it represents is determined by the Taylor series expansion of all variables with indexes lower than index(v). An edge eis directed E is directed from vto the derivative of the function with respect to the variable index(v). Graphically, there are three different types of edges: dashed for the constant Taylor expansion, plain lined for the expansion on the first derivative, and double-lined for the expansion on the second derivative. The function computed at the terminals is an integer constant. On the leftmost diagram of Figure 2.7 we can find a key of that representation. In step 1and 2of the same figure, we show the Taylor expansions of polynomial f1= (x+y)(x−y) with respect to variables xand y. The order in which the variables are expanded affects the size and shape of the final canonical representation. Following certain rules to find an initial variable ordering [47] can help to obtain TEDs optimized in size: 30 Background 1. Variables that never appear in the same monomial on a single-output TED can be treated as outputs of a temporary multiple output TED. 2. Variables that appear in most terms of the monomial with the same exponent should be placed at the top of the TED. 3. Variables that appear in most terms of the monomial and have several exponents should be placed right after any variable identified in rule 1. 4. In the case of TEDs with multiple outputs: we place in rule 2 the node at the bottom instead of the top, and we put in rule 3 the node before instead of after. A TED is reduced if it contains no redundant nodes and has no distinct nodes vand v′, such that the subgraphs rooted at vand v′are isomorphic. A node in a TED is redundant if all of its non-0 edges are connected to terminal 0. We can reduce redundant nodes by removing them and merging isomorphic subgraphs. Figure 2.7 shows, in step 3, the reduction of a TED with redundant nodes and edges removed. The normalization of a TED consist of propagating the weights at the terminal edges, or the common factor of all kedges from node vto the terminal node, and storing them as edge weights in the upper edges, enabling the extraction of common subTEDs. By applying this to all terminal nodes, only the terminal node 1, also represented as ONE, remains in the graph. Last step of Figure 2.7 shows a reduced and normalized TED. For any multivariate polynomial phi with integer coefficients, there is a unique ordered, reduced and normalized TED denoting phi, that is, an ordered, reduced and normalized TED is minimal and canonical. TEDs can also represent operators for Boolean logic: not :x′= (1 −x) and :x∧y=x·y or :x∨y=x+y−x·y xor :x⊕y=x+y−2·x·y with xand yBoolean variables represented by binary variables. The resulting functions are 0,1integer functions. TEDs are limited to represent only those functions that have a finite Taylor expansion, therefore functions with an infinite Taylor series such as ax(ais a constant) are excluded from the representation. Also, TEDs cannot Chapter 2 31 represent relational operators (such as comparators, A≥B) in symbolic form, since relations are characterized by discontinuities over their domain and are not differentiable. For the same reason, modular arithmetic is also restricted. TEDs have been commonly used for circuit verification. We use the representation for another purpose in this dissertation: to find common parts of the code that cannot be found with pattern matching techniques using DAGs. For instance, the example TED from Figure 2.7 represents two different polynomials that perform the same functionality: f1= (x+y)(x−y) and f2=x2−y2. These ideas are further developed in Chapters 3 to 5. 38 Chapter 3 criteria above in non-exponential asymptotic time complexity (bounded by the number of invalid instructions, as they define the amount of recursive calls). In order to cut down on the number of candidates, we define a few rules to limit subDFG candidates. Groups of instructions are selected to preserve the consistency of scheduling, which means that all the inputs of the set are ready at issue time. In our exploration, we allow unlimited inputs and outputs to the CI, because more complex CIs will potentially achieve a higher speedup. We also limit the exploration space by only considering executed parts of the code, using a previously-gathered execution profile of the application (label 1.2 in Figure 3.1). At the end of Step 1, we have a list of candidates that are then passed to the next step which clusters the potential code sequences to help select CIs. 3.5. Instruction Clustering to Discover Equivalences In Step 2 of Figure 3.1, we analyze the code sequences found in Step 1 in order to group them to propose CIs that apply to several sequences of code. This clustering step can be performed on code sequences identified from the same application (targeting application-specific CIs), and/or sequences from different applications (targeting domain-specific CIs). Clustering serves several functions: to enhance reusability, to minimize implementation area in hardware, and to reduce the search space in the selection step. In the following sections, we describe three methodologies for the clustering: DAG,TED and Hybrid. 3.5.1. Clustering with DAG Isomorphism The first technique clusters the code sequences using directed acyclic graphs (DAGs). For each pair of subDFGs obtained in Step 1, we perform a one-to-one isomorphism detection (label 2.1 in Figure 3.1). Those graphs that are isomorphically exact are clustered under the same label, to be potentially transformed into a single CI candidate. Previous works [19,48] approached the problem by starting from small graphs, building them up to arrive at relatively large-sized accelerators — a bottom-up approach. In our work, we employ a top-down approach and start from maximal subgraphs extracted from a basic block, ideally covering as large code sequences as possible, and exploit as much instruction-level parallelism as possible. Relatively larger CIs are more likely to yield better overall performance, but the identification of big patterns of functionally identical computation is Functionally Similar Domain-Specific Instructions 39                  !"# "   #"  " #  "    $%&               "     "                                                                             '!"# (    !"# (  !"#                       !!                                )#' '*+!        ! ! !                                 !  !  "#  $%& $%& Figure 3.2: Three examples of the usage of TEDs for instruction clustering. From top to bottom: DAGs, Algebraic expressions, TED construction process and final normalized TEDs. 40 Chapter 3 a complex problem. Consider the three examples of subDFGs in Figure 3.2, identified in different benchmarks and their equivalent algebraic expressions. Example 1 shows two portions of code of the aacenc application from different basic blocks in their DAG representations. They differ in the number and types of instructions they contain. Simple DAG pattern matching would not cluster these two DAGs, although their algebraic functions are equivalent. In Example 2, we extend the problem to a domain of applications. We show DAGs of basic blocks from different benchmarks (mpeg2dec,aacenc,mpeg2enc and face_detect) that perform the same computation, but with different operators. The DAGs of two of them (mpeg2dec, mpeg2enc) are isomorphically the same, therefore they could be clustered with DAG pattern matching. However, DAG pattern matching is not able to cluster all four of them. In Example 3 we show two DAGs of face_de- tect and tmndec with multiple outputs. In this case, although we can have a partial match with DAGs for outputs 2 and 3, the full match for identical computation cannot be found. Summarizing, in the three motivational examples, pattern matching using DAGs is missing opportunities to find commonalities among code sequences. 3.5.2. Clustering with TED isomorphism Because of the limitations of using DAG pattern matching, we introduce a second clustering technique based on a canonical representation of portions of the application’s code. We gather insights from works on TEDs (see Chapter 2, Section 2.4.2.2), adapting them here to find common parts of the code that cannot be found with a simple pattern matching technique using DAGs. We match code from applications using TEDs at compile time (at an intermediate code level), and thus the shape of a TED does not influence the final implementation of a CI at the circuit-level. Although TEDs were described in Chapter 2 in great detail, we briefly introduce here the basics of the representation to understand how the TED technique works for cases such as the one depicted in the examples of Figure 3.2. Starting with a multivariate algebraic expression, we apply recursively the Taylor series expansion and we store this decomposition, into a directed acyclic graph, the Taylor Expansion Diagram (label 2.2 in Figure 3.1). Each node of the graph represents an input variable, and three different types of edges can be linked to a node: constant Taylor expansion, the expansion on the first derivative, and the expansion on the second derivative. Following a set of rules, we obtain a normalized and canonical representation of the TED from the starting algebraic expression. We start with the computations expressed as subDFGs or DAGs from Functionally Similar Domain-Specific Instructions 41 Step 1 in Figure 3.2. Then, in order to build a TED, we execute the following steps: 1. Convert the subDFG into an algebraic expression. Note that boolean logic can be expressed as an algebraic expression as well: for example, the logical ‘or’ operation can be represented as x∨y=x+y−xy. 2. Establish the order in which the variables are expanded, as it affects the size and shape final canonical representation. 3. Recursively calculate the values of the Taylor expansion for the constant, first and second derivative for every term in the algebraic expression, following the order from point 2. 4. Apply reduction and normalization rules to ensure that the TED is canonical. We explain the TED construction with three examples in Figure 3.2. In Example 1, the first step converts the DAGs into the algebraic expressions A and B written under the graphs. Note the expansion of the ‘or’ operation into its counterpart algebraic expression. In the second step, we decide the ordering of the variables, which is important to arrive at a canonical representation. In this case, the order is x,y. In the third step we construct the TED, which will be unique for both A and B, as their Taylor series expansions yield the same values. Step (i) in the TED construction builds a partial TED performing the Taylor series expansion first on variable x. Then, step (ii) expands on variable y. The resulting TED, after applying normalization and reduction, leads to the reduced version in the bottom of the example. For Example 2, the four algebraic expressions are expanded in the same way, as shown in steps (i) to (v). In Example 3, with multiple output DAGs, we will have an algebraic expression for each one of the outputs. Each expression is transformed into the corresponding TED, with as many steps as input variables. At the end, the generated TEDs, separately, are reduced and normalized, but also merged into a single normalized TED. Finally, as TEDs are also directed acyclic graphs, we perform a one-to- one isomorphism detection with the normalized TED — like the ones at the bottom of Figure 3.2 – as we do with the DAG representation (label 2.3 in Figure 3.1). 3.5.3. Hybrid TED-DAG clustering The final clustering technique is a hybrid TED-DAG technique. Not all computations in their directed acyclic graphs can be converted to a polynomial expression, and only polynomials with a finite Taylor expansion can be 42 Chapter 3 modeled as TEDs. This excludes modular arithmetic, relational operations, and exponentiation of constants as a base, whereas a DAG can represent all types of computations as they are expressed structurally in the DFG. Due to these restrictions, we propose a hybrid technique that uses the TED representation when it can be created, and otherwise uses the DAG representation of subDFGs to cluster computation (label 2.4 in Figure 3.1). Using this hybrid approach, we should be able to cluster more code sequences to target the same hardware, identifying the most efficient CIs for our set of applications. 3.6. Heuristic Selection After clustering code sequences, we have many CI candidates. In order to select the most promising ones for our applications, we introduce four novel scoring heuristics in Step 3 of Figure 3.1. Our scoring techniques use dynamic execution data from the applications in order to prioritize CIs, either focusing on application-specific or domain-specific CIs, that maximize speedup. They score based on the number of regular instructions covered by each CI, the frequency of execution of the basic blocks that contain the subDFG that maps to that CI, and (for domain-specific) the number of applications that can use each CI. 3.6.1. Application-Specific Scoring We first focus on a scoring heuristic that prioritizes CIs targeted at just one application (label 3.1 in Figure 3.1). Our heuristic ranks CIs based on the potential speedup they can offer, using the following terms: Kis a CI for which ncode sequences are found in an application, i.e., ncode sequences can be accelerated using CI K.ninstiis the number of regular instructions and freqiis the frequency of execution of the code sequence amenable to the CI. The latter is gathered through profiling (label 1.2 in Figure 3.1). Our application-specific scoring heuristic for CI Kis then defined as: scoringK= n X i=1 ninsti×freqi,(3.1) and essentially weights all code sequences with their instruction counts and execution frequencies to have a measure of the speedup of the application as a whole. Functionally Similar Domain-Specific Instructions 43 3.6.2. Domain-Specific Scoring To identify CIs that are most efficient across a domain of applications, we must use different heuristics that take into account the reusability of the hardware (label 3.2 in Figure 3.1). We still take into account a CI’s execution frequency, however with a slight change. Because we are considering different applications, we must normalize the execution frequencies to the application’s total dynamic instruction count. For any given application, the normalization is done by scaling the frequency of execution to the percentage of the application’s total number of instructions executed. We first define the following variables: Kis a CI with ncode sequences found across all applications (1 ≤n). ninst is the number of regular instructions of a given code sequence amenable to the given CI. nfreq is the normalized frequency of execution of the given code sequence. napp is the number of applications that can use the CI. Each of these napp applications can use the CI at mdifferent points in the code (1 ≤m≤n), and thus (n=Pnapp i=1 mi). We now detail four new scoring heuristics that each prioritize CIs differently, and we compare them later in the experimental results section. 3.6.2.1. Scoring 1: Normalized Application-Specific scoringK= n X i=1 ninsti×nfreqi(3.2) Equation 3.2 shows the first scoring, which is similar to the applicationspecific scoring, though it uses normalized frequency values. It maximizes the ranking of frequently used CIs targeting high numbers of instructions. A CI’s sharing across applications is not taking into account with this scoring heuristic. 3.6.2.2. Scoring 2: Scaled by Sharing scoringK= ( n X i=1 ninsti×nfreqi)×napp (3.3) 44 Chapter 3 Our second scoring technique, in Equation 3.3, does take into consideration a CI’s ability to be reused or shared across applications. The napp factor prioritizes CIs that have a high sharing factor, when the scoring has to discriminate among CIs with similar numbers of normalized dynamic instructions. Application-specific CIs that are very frequently used are still highly ranked, since nf reqi≫napp. 3.6.2.3. Scoring 3: Geometric Mean of Sharing scoringK=napp v u tnapp Y i=1 ( mi X j=1 ninstj×nfreqj)(3.4) Equation 3.4 shows our third scoring heuristic that calculates the geometric mean of the miapplication-specific scores, where ian index that iterates over the applications involved. Since application-specific scores for a given CI can vary by several orders of magnitude, we propose this scoring to smooth out the spikes in the scores due to a single application (when napp > 1). CIs that benefit many applications but get a high score from only one application, are penalized. This heuristic thus introduces fairness for CIs targeting several applications. However, CIs used by one application are not penalized. 3.6.2.4. Scoring 4: Random-Scaled Sharing scoringK= napp−1 X i=0 ( mi X j=1 ninstj×nfreqj)×napp napp −i(3.5) In the final scoring heuristic, in Equation 3.5, we introduce a randomness factor controlled by the number of applications that the CI targets. The application-specific scoring is weighted by napp napp−i. The assignment of iis random, but napp still influences the final result, thus the higher the sharing factor, the higher the score. Note that the value of iassigned to a particular application is non-deterministic, so the applications are weighted differently for each code sequence. The reason for introducing some controlled randomness is to distribute scores in a more flexible way, since there are other factors that we do not consider in our current heuristics, such as the area that a CI occupies. Functionally Similar Domain-Specific Instructions 45 3.7. Estimating Performance and Area Finally, in Step 4 from Figure 3.1, we evaluate the effectiveness of the CIs identified by the previous three steps. Informed by the ranking of CIs produced by the scoring heuristics in Step 3, we feed top CIs into a hardware description language conversion tool that creates a preliminary hardware implementation (label 4.1 in Figure 3.1). This implementation verifies that the identified sequences of code can be implemented as hardware structures, and double-checks the scoring techniques. The hardware implementation, using information from the application profile, is fed into a model that estimates the achievable speedup and area occupied by each CI (label 4.2 in Figure 3.1). Area estimates are obtained through hardware synthesis as we will explain in Section 3.8. We estimate the speedup each CI can achieve for each identified sequence of code as follows. Consider a CI that would be invoked at ndifferent locations in the code of a particular application, that covers ninst normal instructions, and is executed nfreq times at a particular location. Further, assume that hardware synthesis estimates the CI to take hw_cycles to execute. Consider also a cost of Cin cycles to move input data from the register file to the SFU before the CI starts and a Cout cost to move outputs back to the register file at the end of the accelerated execution. Both costs depend on the number of input and output parameters of a particular CI and the available register ports in the baseline processor. We first estimate the execution time in cycles of all uses of the CI (on the SFU) as: Tw/ ci = n X i=1 nfreqi×(hw_cycles +Cini+Couti),(3.6) or the number of times the CI is invoked multiplied by its execution time in cycles. Then, we estimate the number of cycles that the same sequences of code would take on the non-customized processor (without using the CI): Tw/o ci = n X i=1 ninsti×nfreqi×CPI,(3.7) with CPI as the cycles per instruction of the application on the target processor. We define Tas the total application execution time in cycles on the target processor (without using the CI). We then can find the difference between the number of cycles our candidate sequences take on the noncustomized processor versus using CIs, and subtract this from Tto approximate the accelerated performance. Formally, the estimated total application 46 Chapter 3 time when using CIs is: T−(Tw/o ci −Tw/ ci).(3.8) We then divide Tby that estimated time to calculate the SFU’s achievable speedup. This is a conservative estimate since we do not take into account the potential instruction-level parallelism between regular and CI execution, which would result in higher speedups. With this evaluation step, we are able to compare the potential performance improvements that a set of CIs, whether including just applicationspecific CIs, domain-specific, or both, can provide to an application or set of applications. 3.8. Experimental Setup We describe the implementation details of our specialized functional unit design exploration framework FuSInG, including the software and hardware tools used, and our benchmarks. We use the LLVM compiler infrastructure [44] as the front-end to our CI design exploration framework FuSInG. We modify the LLVM code generation module to find maximum valid subDFGs for DFG exploration (Step 1 in FuSInG). Using the NetworkX library [49], we perform graph isomorphism detection, and construct the TED representations using the symbolic algebra and calculus part of Sage [50]. We obtain an execution profile for each of our applications using the LLVM binary interpreter. The profile indicates the frequency of execution for each basic block, and is used in Steps 2 to 4 of FuSInG. We assume that the target architecture has spare core area tightly-cou- pled to the processor core to implement the configurable SFU, as shown in Figure 2.1 (Chapter 2). We consider a single-core single-thread OpenSPARC T1 as the baseline architecture, which has been adapted previously for research on embedded applications [51]. The register file that both the ALU and the SFU access consists of 32 64-bit registers with three read, two write and one transport ports. The instruction encoding allows moving two input operands to the SFU with no additional cost. Any extra inputs are sent in groups of three, with a cost of one cycle per transfer, before the CI execution starts. When the instruction ends, outputs are packed together in groups of two and moved back to the register file, with a cost of one cycle per transfer. To evaluate the selected CIs, we first translate their functionality to C code. For a given application, CIs that are functionally equivalent are translated to one common piece of code. Across applications, for a given set of Functionally Similar Domain-Specific Instructions 47 Benchmark Description Input aacenc AAC audio compression encoder 33.9MB WAV cjpeg JPEG image format compressor 1.2MB PPM (Mediabench) djpeg JPEG image format decoder 12.8kB JPEG (Mediabench) face Face detection on bitmap files 734.5kB bitmap tmndec H263 video format decoder (TMN) 114 kB H263 (Mediabench) tmnenc H263 video format encoder (TMN) 5.5MB YUV (Mediabench) mpeg2dec MPEG2 video format decoder 34.9kB (Mediabench) mpeg2enc MPEG2 video format encoder 506.9kB (Mediabench) optflow Optical flow for motion estimation 884 kB images Table 3.1: Description of the evaluated application benchmarks and their input files. sections of code identified as functionally equivalent, we provide an implementation of the CI execution path for each application involved. Later, we choose the best among them for the performance model. We use the Vivado HLS suite to perform C to HDL conversion on those C code segments. For feasibility reasons, our automated toolchain uses the default optimizations of Vivado HLS [9]. Any further improvements to the hardware implementation with specifically-set optimizations would result in better overall speedups. The Xilinx ISE tool performs the synthesis of the design, using the Virtex 5 FPGA as a target, which estimates the new hardware’s area (per CI) as a number of look-up tables (LUTs) and slices. We report area estimates relative to the OpenSPARC T1 core area, which is also mapped onto a Xilinx Virtex 5 FPGA for apples-to-apples comparison. We also use the Xilinx ISE reports to estimate the number of cycles per CI, which we use to estimate performance speedup through acceleration as previously explained. Table 3.1 shows the list of benchmarks that we use for our experiments, with their descriptions and input files. All the applications belong to the media domain. The optical flow kernel and the face detection benchmark are part of the OpenCV library [52]. The AAC (audio compression) encoder is based on a program provided by Renesas Technology and Hitachi Ltd. The rest of the applications and their input files belong to the Mediabench II benchmark suite [53]. 54 Chapter 3 0 20 40 60 80 100 Percentage of Area 1.00 1.05 1.10 1.15 1.20 1.25 1.30 Speedup Domain-specific only: aacenc Norm. app-specific Scaled by sharing Geom. mean Random-scaled 0 20 40 60 80 100 Percentage of Area 1.00 1.05 1.10 1.15 1.20 1.25 1.30 Speedup Domain-specific only: cjpeg Norm. app-specific Scaled by sharing Geom. mean Random-scaled (a) (b) 0 20 40 60 80 100 Percentage of Area 1.00 1.05 1.10 1.15 1.20 1.25 1.30 Speedup Domain-specific only: djpeg Norm. app-specific Scaled by sharing Geom. mean Random-scaled 0 20 40 60 80 100 Percentage of Area 1.00 1.05 1.10 1.15 1.20 1.25 1.30 Speedup Domain-specific only: face Norm. app-specific Scaled by sharing Geom. mean Random-scaled (c) (d) 0 20 40 60 80 100 Percentage of Area 1.00 1.05 1.10 1.15 1.20 1.25 1.30 Speedup Domain-specific only: mpeg2dec Norm. app-specific Scaled by sharing Geom. mean Random-scaled 0 20 40 60 80 100 Percentage of Area 1.00 1.05 1.10 1.15 1.20 1.25 1.30 Speedup Domain-specific only: mpeg2enc Norm. app-specific Scaled by sharing Geom. mean Random-scaled (e) (f) Figure 3.5: Results of benchmark speedup versus SFU area for scoring techniques, with domain-specific CIs created with the Hybrid technique (part 1/2). Functionally Similar Domain-Specific Instructions 55 0 20 40 60 80 100 Percentage of Area 1.00 1.05 1.10 1.15 1.20 1.25 1.30 Speedup Domain-specific only: optflow Norm. app-specific Scaled by sharing Geom. mean Random-scaled 0 20 40 60 80 100 Percentage of Area 1.00 1.05 1.10 1.15 1.20 1.25 1.30 Speedup Domain-specific only: tmndec Norm. app-specific Scaled by sharing Geom. mean Random-scaled (g) (h) 0 20 40 60 80 100 Percentage of Area 1.00 1.05 1.10 1.15 1.20 1.25 1.30 Speedup Domain-specific only: tmnenc Norm. app-specific Scaled by sharing Geom. mean Random-scaled 0 20 40 60 80 100 Percentage of Area 1.00 1.05 1.10 1.15 1.20 1.25 1.30 Speedup Domain-specific only: Average Norm. app-specific Scaled by sharing Geom. mean Random-scaled (i) (j) 0510 15 20 Percentage of Area 1.00 1.05 1.10 1.15 1.20 1.25 1.30 Speedup Domain-specific only: Average Norm. app-specific Scaled by sharing Geom. mean Random-scaled (k) Figure 3.6: Results of benchmark speedup versus SFU area for scoring techniques, with domain-specific CIs created with the Hybrid technique (part 2/2). Graph (j) shows the average for 100% of the SPARC core area, and (k) zooms the average in for 20% of the area. 56 Chapter 3 particular, a CI that causes a 6% speedup improvement is selected with that scoring three positions earlier than with scaled-by-sharing. However, for cjpeg (b), the scaled-by-sharing heuristic is the one that raises to high speedup values at lower areas. We find here a counter-example: scaled-by- sharing selects a CI that contributes 5% to the speedup improvement five positions earlier than random-scaled. A closer look at the groups of code sequences that are clustered into those CIs tell us that in both cases the coverage across applications is maximized. However, random-scaled prioritizes less aggressively, and CIs with a medium number of applications but good overall performance will still rank high. Therefore, we use that scoring as our default in the other experiments reported in the chapter. 3.9.3. Application-Specific vs Domain-Specific Configurations Up until now, we have analyzed the potential of only domain-specific CIs. But our framework allows us to compare the performance of potential application-specific CIs as well. In this section, we compare the speedups that can be achieved using a part of the core area dedicated to only application-specific, only domain-specific, or a mixture of both kinds of CIs. Our goal here is to understand how to best configure an SFU to optimize full-system performance across applications subject to area constraints. Or in other words, for a given core area, are we better offchoosing applicationspecific only, domain-specific only, or both application- and domain-specific CIs for the SFU? Figures 3.7 and 3.8 present the speedup for each benchmark across a range of areas, including only application-specific, only domain-specific, and both kinds of CIs. We analyze performance when the SFU takes zero to 100% of the core area. Figure 3.8 (j) and (k) show the averages across all benchmarks, using up to 100% of the core’s area, and zooming in on small, more realistic areas from zero to 20%. For all of these graphs, we use the Hybrid clustering technique, and we use the application-specific scoring for application-specific CIs, and the random-scaled sharing scoring for domainspecific. Our results reveal that, if given unlimited area, using only applicationspecific CIs can achieve the maximum speedup (34% on average) for our benchmarks. However, a potentially surprising result is that using both application- and domain-specific CIs together approaches the performance of using only application-specific CIs (29%), and obtains higher speedups at lower areas as compared to only application-specific. While using only domain-specific CIs limits maximal speedup to around 13%, we see that this technique is more effective than application-specific at obtaining speedups Functionally Similar Domain-Specific Instructions 57 0 20 40 60 80 100 Percentage of Area 1.0 1.1 1.2 1.3 1.4 1.5 1.6 Speedup Full system configuration: aacenc Only App-specific App-Domain specific Only Domain specific 0 20 40 60 80 100 Percentage of Area 1.0 1.1 1.2 1.3 1.4 1.5 1.6 Speedup Full system configuration: cjpeg Only App-specific App-Domain specific Only Domain specific (a) (b) 0 20 40 60 80 100 Percentage of Area 1.0 1.1 1.2 1.3 1.4 1.5 1.6 Speedup Full system configuration: djpeg Only App-specific App-Domain specific Only Domain specific 0 20 40 60 80 100 Percentage of Area 1.0 1.1 1.2 1.3 1.4 1.5 1.6 Speedup Full system configuration: face Only App-specific App-Domain specific Only Domain specific (c) (d) 0 20 40 60 80 100 Percentage of Area 1.0 1.1 1.2 1.3 1.4 1.5 1.6 Speedup Full system configuration: mpeg2dec Only App-specific App-Domain specific Only Domain specific 0 20 40 60 80 100 Percentage of Area 1.0 1.1 1.2 1.3 1.4 1.5 1.6 Speedup Full system configuration: mpeg2enc Only App-specific App-Domain specific Only Domain specific (e) (f) Figure 3.7: Results of benchmark speedup versus SFU area using only application-specific, application and domain-specific, or only domain-specific CIs (part 1/2). Results gathered using the Hybrid technique. 58 Chapter 3 0 20 40 60 80 100 Percentage of Area 1.0 1.1 1.2 1.3 1.4 1.5 1.6 Speedup Full system configuration: optflow Only App-specific App-Domain specific Only Domain specific 0 20 40 60 80 100 Percentage of Area 1.0 1.1 1.2 1.3 1.4 1.5 1.6 Speedup Full system configuration: tmndec Only App-specific App-Domain specific Only Domain specific (g) (h) 0 20 40 60 80 100 Percentage of Area 1.0 1.1 1.2 1.3 1.4 1.5 1.6 Speedup Full system configuration: tmnenc Only App-specific App-Domain specific Only Domain specific 0 20 40 60 80 100 Percentage of Area 1.0 1.1 1.2 1.3 1.4 1.5 1.6 Speedup Full system configuration: Average Only App-specific App-Domain specific Only Domain specific (i) (j) 0510 15 20 Percentage of Area 1.0 1.1 1.2 1.3 1.4 1.5 1.6 Speedup Full system configuration: Average Only App-specific App-Domain specific Only Domain specific (k) Figure 3.8: Results of benchmark speedup versus SFU area using only application-specific, application and domain-specific, or only domain-specific CIs (part 2/2). Results gathered using the Hybrid technique. Graph (j) shows the average for 100% of the SPARC core area, and (k) zooms the average in for 20% of the area. Functionally Similar Domain-Specific Instructions 59 at very small areas. Given 20% area, application-specific achieves 8% speedup, while domain-specific achieves 10% and both together achieve 23%. Furthermore, for several benchmarks, namely aacenc (a),face (d),mpeg2dec (e), and optflow (g), using only domain-specific CIs performs close to the best of the other two techniques. The key insight here is that, while using only application-specific CIs results in the highest possible speedups at large or unbounded core areas, considering domain-specific CIs next to application-specific CIs yields the highest possible speedup at realistic, smaller core areas. The reason is that the domain-specific CIs benefit several applications, which is more areaefficient compared to application-specific CIs which benefit a single application only, and therefore have limited contribution to overall system performance. A corollary of this finding is that, in order for hardware acceleration to deliver substantial speedups, some notion of application-specific hardware acceleration is needed (even at small areas). This requires knowing the target domain and its applications at SFU configuration time so that some application-specific CIs can be included. Alternatively, one could devote a fraction of the SFU die area to domain-specific and application-specific CIs that are known to perform well given the applications known at design time. 3.9.4. Custom Instruction Analysis In order to reveal further insight about how to build future specialized computing units, and which CIs offer the most benefit inside an application domain, we present an analysis of the CIs identified as the most effective at a few particular core areas. We compare the details of the SFU for designs with application-specific, domain-specific, and a mixture of both kinds of CIs. We show CI statistics for core area percentages 5,10 and 15% in Table 3.3, taking the best configurations as shown in Figures 3.7 and 3.8. Table 3.3 shows three configurations: using only application-specific CIs (only AS), using only domain-specific CIs (only DS), and using both (AS/DS, with the specific AS and DS portions in parentheses). We define three sizes of CIs, depending on the number of instruction primitives that each CI implements. A small-sized CI has 1 to 5 instructions, a medium-sized one has 6 to 15, and a large-sized one has more than 15. We also present the average number of inputs and outputs for each size-class; however, these do not affect the size-class (i.e., small CIs could have many inputs or outputs). Finally, we show the number of applications that each configuration can cover in the second-to-last column, and the speedup it achieves. We can draw a few interesting conclusions from the best-performing CI configuration statistics. First, using both application and domain-specific 60 Chapter 3 %area Configsmall-sized medium-sized large-sized #app Speedup # CI in out # CI in out # CI in out 5% only AS 2 2.5 2 0 − − 2 38 2.54 1.07× AS/DS 6(0/6) 5.3 2.2 2(0/2) 10 5 6(6/0) 26.5 8.29 1.22× only DS 7 4.8 2 1 9 5 0 − − 9 1.07× 10% only AS 4 2.7 1.5 0 − − 2 38 2.56 1.07× AS/DS 8(0/8) 5.4 2.3 4(2/2) 11.25 5.25 6(6/0) 26.5 8.29 1.24× only DS 11 4.6 1.8 3 11.33 5.33 0 − − 9 1.10× 15% only AS 15 4.9 2.3 1 9 5 3 31.6 7 9 1.13× AS/DS 9(0/9) 4.7 1.8 4(2/2) 11.25 5.25 6(6/0) 26.5 8.29 1.24× only DS 13 4.8 2 4 12 6.5 0 − − 9 1.10× Table 3.3: Classification of CIs in a full-system configuration of 5%,10% and 15% of the SPARC area. (AS =application-specific, DS = domain-specific. Small =1-5 regular instructions; Medium =6-15 instructions; Large =>15 instructions.) Functionally Similar Domain-Specific Instructions 61 CIs already achieves speedup of 22% using only 5% of the SPARC core’s area. At the same area, using only application-specific CIs targets only 4 applications and can get only a speedup of 7%, which raises to 13% when using 15% of the core (while covering all 9 applications). Interestingly, applicationspecific CI configurations usually include small and large-sized CIs, but few medium-sized ones; in comparison, domain-specific CI configurations include no large-sized CIs, instead prioritizing CIs with fewer than 15 base ISA instructions. Using both kinds of CIs (AS/DS), we find more domainspecific small-sized CIs, but more application-specific ones of the large size. We also see that, though the average input and output sizes are independent of the number of regular instructions per CI, in general, the numbers of inputs and outputs grow as we go from small to medium to large-sized CIs. Interestingly, the mixed application and domain configurations include CIs from each size-class, and achieve the highest speedup. This suggests that the best-performing machine should include both application and domainspecific CIs. 3.9.5. Cross-Validation In all previous experiments, we generated candidate domain-specific CIs from code sequences using the entire set of benchmarks. In this final section, we evaluate a realistic setting where the machine is configured with a set of CIs for a particular application domain, but then an as-yet-unseen application runs upon it and tries to take advantage of the flexibility of the domain-specific CIs (generally known as cross-validation). In Step 3 of our methodology, shown in Figure 3.1, we cluster code sequences from N−1 of our benchmarks, prioritizing using our random-scaled scoring heuristic, and then in Step 4, we evaluate the effectiveness of those CIs on a different, the Nth, application. Figures 3.9 and 3.10 show our cross-validation results for each benchmark from (a) to (i), and the average across benchmarks (j). When given the total core area, all but two benchmarks can reach the maximal speedup (obtained using domain-specific CIs identified over all benchmarks, as in Section 3.9.3, when given unlimited area). Benchmarks optflow (g) and tmnenc (h) cannot achieve their maximum speedup using our cross-validation approach; optflow achieves its speedup when using only one CI; in addition, as shown in Figure 3.8 (g),optflow does achieve its maximum speedup when we include domain-specific CIs identified from all benchmarks, whereas in Figure 3.8 (h),tmnenc can only benefit from application-specific CIs (achieving very limited speedup overall). The other seven benchmarks can take advantage of CIs deemed useful for the domain, and especially aacenc in 62 Chapter 3 0 20 40 60 80 100 Percentage of Area 1.00 1.05 1.10 1.15 1.20 1.25 1.30 Speedup Cross validation: aacenc Upper bound Cross-validated result 0 20 40 60 80 100 Percentage of Area 1.00 1.05 1.10 1.15 1.20 1.25 1.30 Speedup Cross validation: cjpeg Upper bound Cross-validated result (a) (b) 0 20 40 60 80 100 Percentage of Area 1.00 1.05 1.10 1.15 1.20 1.25 1.30 Speedup Cross validation: djpeg Upper bound Cross-validated result 0 20 40 60 80 100 Percentage of Area 1.00 1.05 1.10 1.15 1.20 1.25 1.30 Speedup Cross validation: face Upper bound Cross-validated result (c) (d) 0 20 40 60 80 100 Percentage of Area 1.00 1.05 1.10 1.15 1.20 1.25 1.30 Speedup Cross validation: mpeg2dec Upper bound Cross-validated result 0 20 40 60 80 100 Percentage of Area 1.00 1.05 1.10 1.15 1.20 1.25 1.30 Speedup Cross validation: mpeg2enc Upper bound Cross-validated result (e) (f) Figure 3.9: Results of benchmark speedup versus SFU area for cross-validation per application using domain-specific CIs (part 1/2). Results gathered using the random-scaled sharing scoring and the Hybrid technique. Functionally Similar Domain-Specific Instructions 63 0 20 40 60 80 100 Percentage of Area 1.00 1.05 1.10 1.15 1.20 1.25 1.30 Speedup Cross validation: optflow Upper bound Cross-validated result 0 20 40 60 80 100 Percentage of Area 1.00 1.05 1.10 1.15 1.20 1.25 1.30 Speedup Cross validation: tmndec Upper bound Cross-validated result (g) (h) 0 20 40 60 80 100 Percentage of Area 1.00 1.05 1.10 1.15 1.20 1.25 1.30 Speedup Cross validation: tmnenc Upper bound Cross-validated result 0 20 40 60 80 100 Percentage of Area 1.00 1.05 1.10 1.15 1.20 1.25 1.30 Speedup Cross validation: Average Upper bound Cross-validated result (i) (j) Figure 3.10: Second part of results of benchmark speedup versus SFU area for cross-validation per application using domain-specific CIs (part 2/2). Results gathered using the Hybrid technique. Graph (j) shows the average for 100% of the SPARC core area. Figure 3.9 (a),djpeg (c),face (d),mpeg2dec (e) and tmndec in Figure 3.10 (h) achieve high speedups at very low core area percentages. On average, at only 20% of the core area shown in Figure 3.10 (j), our applications achieve over 7% speedup, which is a significant percentage of the maximum of 10%. 70 Chapter 4 are sliced and placed before and after the loop body computation. In step Simulation (1.4), we simulate the applications with the identified high-level CIs to measure cycles and energy consumption in the baseline processor. In step High Level Synthesis (1.3), we implement CIs in hardware, obtaining their area occupancy, execution cycles and energy, and their Intermediate Representation used in subsequent steps. We apply different unrolling and vectorization factors in the HLS transformation. Therefore, besides the implicit instruction-level parallelism of the CIs, we also have potential datalevel parallelism from the HLS optimizations. From now on, we talk about aCI as the high-level representation of a loop body or inline function that can be accelerated in hardware, and we talk about CI variants or only variants to specify distinct implementations of a CI (for example, with different unrolling factors). Thus, depending on the optimizations applied, we can obtain several variants of the same CI. The Candidates Extraction step produces application-specific CI variants with their implementation details. 4.5. Canonicalization of Custom Instructions using Merging Diagrams Identifying similarities between CI variants in a non-unified representation is difficult due to the amount of unnecessary information a modern compiler IR includes. Also, a representation such as a DFG, which expresses structural relations between operators, does not expose functional similarities, since different coding styles among applications may hide them. Therefore, in step Canonicalization of Figure 4.1, we transform the codes of the CI variants expressed initially in a compiler IR, into an abstract, canonical representation: the Merging Diagram (MD). The MD represents arithmetic and logic operations (within the basic block), and predicate information (at the loop level), both with unrestricted number of inputs and outputs. Its representation is partially based on Binary Decision Diagrams (BDDs) and Taylor Expansion Diagrams (TEDs), surveyed in Sections 2.4.2.1 and 2.4.2.2, respectively. We have successfully used TEDs for CI similarity detection within a basic block in Chapter 3, but extending CIs beyond the basic block level needs a new representation that includes predication. Also, the codes we process include operations that cannot be expressed as polynomial functions, which are the base of the TED representation. The following definitions explain the details of our new representation, which include both modified versions of TEDs and BDDs. Definition 1. An Augmented TED (AugTED), is a directed acyclic graph based on linearized and reduced TEDs. It is composed of a labeled set of Partially Similar Domain-Specific Instructions 71 nodes V, a weighted set of edges E, and the terminal node 1. In normal TEDs, Vrepresents variable names and Eare additions/subtractions or multiplications. AugTEDs expand TED nodes to represent any kind of computation, using variable renaming. Here, labels in Vcan be integer, float or special. Integer and float labels represent variable types, and special labels a function that cannot be represented by a Taylor expansion. Definition 2. A Linking BDD (LinBDD) is a directed acyclic graph based on reduced and ordered BDDs. It consists of a labeled set of nodes V′, a set of edges E′and terminal nodes 0and 1. LinBDDs nodes have BDDs’ 0-1 decision edges, and additionally a third edge Link that references an outside diagram, namely an AugTED. A LinBDD is constructed with the Shannon expansion of boolean functions created with the if-then-else (ITE) operator: ITE(I,T,E)=I·T+¯ I·E. Definition 3. A Merging Diagram is a data structure that provides a canonical representation of a predicated code region. It consists of a set Aof AugTEDs that represent computations and a set Lof LinBDDs that represent control flow execution. Link edges from the nodes in each member of L references a member in A. Figure 4.2 (d) shows an example of an MD for a given code sequence. The left part of the MD is a LinBDD and its nodes are linked to AugTEDs on the right by Link edges. There is a special label (SA(slt)) that stands for a relational operator that cannot be expressed by Taylor expansions. Details on the construction of the MD, with explanation of the example of Figure 4.2, follow. 4.5.1. Merging Diagram Construction To build all the canonical MDs of a group of CI variants, we follow the steps of Algorithm 1. We start processing in lines 3−7the set of IRs of all the CI variants’ code regions. Figure 4.2 (a) shows an extract of an IR example with arithmetic, relational and conditional selection instructions. For each one of the IRs, we extract the polynomial representation of the computations (PolyAugTED) and the branch predication (PolyLinBDD) of the code, as illustrated in Figure 4.2 (b). With those base polynomials, we establish a precise renaming of variables that unifies their name space in lines 8−22, which facilitates fast similarity identification in Section 4.6.1. We decompose each polynomial into its monomials, and we rename each variable based on the type of monomial where it is found. We find primarily adding and multiplying types of monomials, but also cover floating-point 72 Chapter 4 IR Merging Diagram (MD) ... %sub = sub nsw i32 %q11, %q21 %shl = shl i32 %sub, %c %cmp = icmp slt i32 %shl, 0 %sub1 = sub nsw i32 0, %shl %cond = select i1 %cmp, i32 %sub1, i32 %shl ... PM1 PM2 PM3 0 1 0 1 SA(slt) PM3 M1 M2 M3 1 %cmp %sub1 %shl icmp slt %q11 %q21 2^(%c) -1 -1 Add edge Mul edge Link edge Variable renaming PM1 PM2 PM3 SA(slt) M1 M2 M3 vn vn' PolyAugTED %shl = (%q11 - %q21) * 2^%c %cmp = icmp slt (%shl, 0) // special %sub1 = 0 - %shl PolyLinBDD %cond = %cmp * %sub1 + %cmp * %shl AllPolynomials operator (a) (b) (c) (d) Figure 4.2: Example of Merging Diagram construction. For the IR on the top left (a), polynomials are extracted (b), variables renamed (c), and an MD is created (d). and predicated types. For instance, in Figure 4.2 (c), variables are renamed as A(adding) and M(multiplying) preceded by P(predicated) or S(special). Then, in lines 23 −25 we define a strict variable ordering to perform the expansions, common to all variables implicated. As we have multiple polynomials that expand with the same group of variables, we first set variables in ascending order based on the number of times they occur. This ensures that we will have a minimum number of expansions, resulting in a more compacted MD. For the same reason, in the case of a tie in the number of instances between multiplying and adding variables, we prioritize the former ones. Finally, in lines 27 −31, for each rewritten polynomial, we create an MD structure with a condensed matrix Diagram that contains all the nodes and edges from the AugTEDs and LinBDD; it is thus of size s×s, with sthe precomputed size of all the variables involved. Link edges are though kept apart in a two dimensional array. Following the variable ordering, we build the MD expanding each term recursively as it is done regularly with TEDs and BDDs. We show in Figure 4.2 (d) the resulting representation, which is still canonical for the assumed variable order, as it is the case for regular TEDs and BDDs. Partially Similar Domain-Specific Instructions 73 Algorithm 1: Merging Diagram construction input : Array of CIs’ IR codes AllIRs output: Merging Diagrams AllMDs 1Array AllPolynomials,RewrittenPolynomials ←− ∅ 22D array RenamedMap ←− ∅ 3for IR ∈AllIRs do 4PolyAugT ED ←ComputationPolynomials(IR) 5PolyLinBDD ←PredicationPolynomials(IR) 6add (PolyAugT ED ∪PolyLinBDD) to AllPolynomials 7end 8for p∈AllPolynomials do 9M←GetMonomials(p) 10 for m∈Mdo 11 MonomialType ←GetMonomialT ype(m) 12 V arNames ←GetV ariablesNames(m) 13 for vn ∈V arNames do 14 if vn <RenamedMap then 15 vn′←renameV ar(vn,MonomialType) 16 add < vn,vn′>to RenamedMap 17 end 18 end 19 end 20 p′←replaceV ars(p,RenamedMap) 21 add p′to RewrittenPolynomials 22 end 23 V arsOccurrences ← countOccurrencesV ars(RewrittenPolynomials) 24 OrderedV ars ←ascendingOrderV ars(V arsOccurrences) 25 s←size of OrderedV ars + 1 26 Array AllMDs ←− ∅ 27 for p′∈RewrittenPolynomials do 28 MD ←< Diagram:s×sarray, Link: 2D array> 29 MD.Link ←linkT oAugT EDV ars(p′,RenamedMap) 30 diagramExpansions(p′,MD.Diagram,OrderedV ars)add MD to AllMDs 31 end 32 return AllMDs 74 Chapter 4 4.5.2. Global diagram of variants In order to cut down computation costs in later steps it is required to have a diagram that represents the entire design space of CI variants. To do so, we combine all the AugTED and LinBDD polynomials to obtain a global MD unified representation. For each variant, we locally rename its polynomial variables, saving the naming convention and number of instances in a global structure. Then, based on that locally collected information, we produce a global variable ordering that is fixed for the design space. Finally, MDs are produced individually for each variant with the global ordering. 4.6. Generation of Merged Custom Instructions 4.6.1. Distance Calculation In step Distance Calculation of Merged CIs Generation (step 3.1 in Figure 4.1), we need to establish a concrete metric that measures similarities among CIs to guide the subsequent clustering step of the MInGLE framework. We therefore develop a new way to measure how different two CI variants are in terms of their functionality, using the MD. We perform a distance calculation for pairs of MDs of variants that do not implement the same loop body, CIXand CIY. We use the previously built global diagrams to speed up this calculation. If we would not have the global, uniformed variable space that we obtained in Section 4.5.2, we would have to build a pair of diagrams for each pair of CIs being compared, which would be computationally very expensive. Thus, based on the prebuilt global diagrams, we obtain the number of AugTED-operations and LinBDD-branches that in CIXdo not match with those in CIY, namely nMX, and vice versa, nMY. An MD node vxmatches another MD node vy if their labels and out edges also match. The matching information is kept for the merging step explained below in Section 4.6.3. We also count the number of total AugTED and LinBDD nodes that each MD variant has – TotXand TotY. Then, we compute the distance δas: δ(CIX,CIY)=average nMX TotX ,nMY TotY!.(4.1) One-to-one distances are saved in a condensed distance matrix. 4.6.2. Clustering Custom Instruction Variants For domain-specific acceleration, merging CIs reduces energy consumption because we need less implementation area; to put it another way, it im- Partially Similar Domain-Specific Instructions 75 exact matching partial matching more similarity less CI00_v1, CI00_v2, CI01_v1, CI01_v2, CI02_v1 CI00_v1, CI00_v2, CI01_v1 level 0 level 1 level 2 level 3 Figure 4.3: Hierarchical clustering of CIs. Exact matching instructions are found at the bottom, while nodes closer to the root group are increasingly less similar CIs. CIXX_vy: CI with identifier XX and implementation variant y. proves performance since we can allocate more CIs in the constrained area. We have to merge circuits of CIs that have more in common to maximize area reduction, as well as minimize the implementation overhead due to circuit multiplexing. However, with the huge set of CI variants that we obtain when we work with multiple applications, it is prohibitive to try all the possible combinations of CIs that could be grouped together. Therefore, in step CI variants Clustering, we group CIs based on a hierarchical clustering that organizes groups by more to less functional similarity, cutting down the search space to avoid those groups that are not similar enough to be worth implementing together. Distances between variants help to quickly decide which ones are better to merge together to reduce energy consumption. Using the distance matrix computed in the previous step, we create clusters of CI variants. We perform hierarchical, agglomerative clustering of CI variants, obtaining a dendrogram, a tree-like structure, as shown in Figure 4.3, where tree leaves represent exact matches and internal nodes denote partial matches. Starting from the baseline CI variants, we form exact-matching clusters based on the distance matrix (leaves – level 0 in the figure). Then, distances between the newly formed clusters use the complete method to determine the agglomerative distance, that is, the maximal distance between any two vari- 76 Chapter 4 ants in the cluster (levels 1 to 3, to the root). From leaves to root, we find different versions of merged variants, ordered from more to less similar. Some obtained clusters may include variants that target the same CI. In Figure 4.3, level 0 includes two variants of the same CI: CI00_v1 and CI00_- v2; a variant of CI01, and {CI01_v2, CI02_v1}, that is the exact matching of two different implementations of two different CIs. Level 1 has the cluster {CI00_v2, CI01_v1}, which has the maximum similarity for partial matching. Variant CI00_v1 from level 0 is clustered at level 2 with {CI00_v2, CI01_v1} from level 1. However, as a merged variant cannot implement a concrete CI more than once, we produce different versions that do not duplicate the loop body (CI00 or CI01) within the clusters where this problem occurs. Thus, at level 2 we generate two solutions: {CI00_v1, CI01_v1} and {CI00_- v2, CI01_v1}. Since the latter already exists at level 1, we will eventually discard it, although its information is still used to generate the cluster at level 3. Note that this can induce an explosion in the number of solution clusters for a given level. In case of many cluster versions, we select a reduced group chosen heuristically based on an approximation of expected EDP improvement. 4.6.3. Merging Estimation and Modeling With the clustering formation, we obtain a bigger set of CI variants, some of which are merged to save area. In step Merging Estimation, we estimate the new hardware area occupancy, performance and energy gains of merged variants in order to run the selection step with accurate information. Based on the information from the distance calculation (Section 4.6.1) of non-common matches between each pair of variants, we obtain the area consumption of operators that are shared (shared) and of those that are not (non_shared). For sharing logic, we need to introduce multiplexers that will induce an extra area cost, overhead. Therefore, we calculate the area aiof a merged CI variant ias: ai=overheadi+sharedi+ N X j=1 non_sharedij.(4.2) Then, in step Performance and Energy Model, we model first the performance of an accelerated application. We start obtaining the cycles c_l_SW that a hot loop iteration takes to execute in the baseline processor, excluding memory operations, from simulation. We also obtain the number of iterations N_it of that loop for a given execution of the benchmark. From hardware synthesis, we get the number of cycles c_HW that a CI variant Partially Similar Domain-Specific Instructions 77 takes. We calculate the cycles c_Tto transfer data to the DSFU local memory as a function of the input data size. With the previous data we obtain the cycles we save executing a CI variant as: c_saved =(c_l_SW −(c_HW +c_T)) ×N_it.(4.3) We calculate the new number of application cycles as: App_cycles =c_total_SW −c_saved,(4.4) with c_total_SW as the application cycles without CIs. Finally, the modeled energy consumption of an application that uses CIs is calculated as: Eapp =Ebaseline +ECI,(4.5) with Ebaseline the baseline processor’s energy model and ECI the CI energy consumption. The latter is modeled as the sum of its dynamic and static components: ECI =Pdynamic ×TCI +Pstatic ×Ttotal,(4.6) where Pdynamic and Pstatic are, respectively, the dynamic and static power of the hardware components that implement the CI variant, TCI is the time that the CI is active, and Ttotal is the execution time of the application calculated from App_cycles. 4.7. Custom Instruction Selection for an Area Constrained Configuration Implementation area is an expensive commodity in our low-power target that largely influences the energy consumption of the final design. However, performance gains also play an important role, because a faster running application would generally consume less energy. Therefore, in the last step of the framework (CI Selection), we address the performance and energy trade-offwhen choosing the best fitting set of CI variants for a given hardware area. We model this optimization as a Knapsack problem, in which we try to fit a subset Sof a collection of objects C– each object oiwith an intrinsic value viand weight wi– within limited mass Mso that the sum of the values of the final subset is maximized and the sum of the weights does not exceed M. In our case, we try to fit the nCI variants, merged and not merged, within a limited hardware area A. Each ci 78 Chapter 4 candidate has a value vithat we describe later, and a hardware occupancy, hwi. We have an additional requirement in our problem: as each CI can be selected only once, though it can be implemented by different variants – with distinct unrolling factors, or merged with other instructions – once we select one CI variant, all other variants of the same CI are invalidated for the following selection steps. We model our problem with Mixed Integer Linear Programming (MILP). We define the following constraints: n X i=0 ci×hwi≤A, (4.7) n X i=0 lbi≤1,(4.8) with lbia loop body that can be implemented by (n) CI variants. Therefore, for a given loop body, only one of its CI variants will be selected. As our main goal is to accelerate execution and save energy, our objective function tries to maximize the EDP improvement. However, the total EDP value changes depending on the area occupancy, and thus, it cannot be deterministically precomputed before the selection starts. Though, for each potential CI we can calculate an approximated value of the EDP difference with respect to the baseline processor without the CI. Also, the static energy component of the EDP is subject to the known value of the maximum area A, which is an approximation for the value that we want to maximize. Therefore, we define the objective function as: n X i=1 ci×σ_EDPi→max.(4.9) The metric σ_EDPiof a concrete CI variant is the value viin the original Knapsack problem and we calculate it as: σ_EDPi= B X j kσ_EDPijk × (1 + σ_Ai×Ai),(4.10) where Bis the number of applications that the current variant targets; kσ_EDPijkis the original application j’s EDP minus the EDP with the variant, normalized to the observed maximum for that application; σ_Ai is applicable only to merged variants, since it is the percentage of area we save by merging and Aiis the percentage of the total area that the variant Partially Similar Domain-Specific Instructions 79 takes. We find that this metric selects more medium-sized variants that help to save area occupancy, and have lower overhead and lower static power than larger variants. From experimentation, we confirm that this objective gives stable results and maximizes EDP fairly among all applications. 4.8. Complexity While the overall complexity of the framework varies in each step, our methodology reduces the search space to keep the exploration tractable and fast. We establish bounds based on the number of total CI variants. Selection is the most critical step and could be exponential in the worst-case. Therefore, we try to always keep a reduced number of CI variants candidates, while maintaining energy and performance efficiency. For each input application from the set of Bbenchmarks we have a number of CIs C, and each CI is implemented as a variant numVariants times. The total number of variants CV processed to build MDs by Algorithm 1 is determined as: CV = B X i=1 Ci X j=1 numVariantsj.(4.11) The complexity Kdis of calculating distances between pairs of MDs (Section 4.6.1) is: Kdis =O(CV ×(CV −C−1)).(4.12) However, the key design decision here is to have a global MD, which obviates the need for a new MD to be computed to compare each pair of variants, speeding up the calculation. Finally, by performing the hierarchical clustering step explained in Section 4.6.2, and using a heuristic to limit the number of cluster versions per level, the final number of generated solutions that the selection of Section 4.7 processes is within the bounds of O(CV). We thus retain the most promising CI candidates, in terms of area, performance and energy efficiency, while making sure the selection step’s complexity does not explode exponentially. 4.9. Evaluation 4.9.1. Experimental Setup We now describe the setup and experimental evaluation of our automated exploration framework MInGLE. 5 Fragments of Domain-Specific Instructions 5.1. Introduction In the last two chapters, we explored the design of CIs that augment a general-purpose processor to accelerate an application domain. We found that domain-specific CIs deliver higher speedup than application-specific ones at realistic implementation areas. In order to expand the accelerating opportunities and to minimize specialized area, we identified partiallymatching CIs across basic blocks, and integrated energy-efficiency in our methods. However, when the available area to implement the CIs is very small, domain-specialized CIs gains are limited. We are interested on exploiting these low areas, since the implementation space for DSFUs has to be treated as an expensive commodity; it is not only reusability that drives domain-specific specialization, but also the optimal use of the available area. With a shrunk circuit we can either decide to add more functionalities, or to benefit from a low-power design. Therefore, in this chapter, we extend previous techniques to expand CIs’ usage and gains with minimal extra overhead. A new analysis step that detects fragments of CIs from which previously unseen acceleration opportunities are detected. The technique is critical to improve reutilization of hardware at the most limited areas, because we partially reuse an already 88 Chapter 5 merged CI cluster, with minimum additional overhead. We integrate the new CI fragment analysis within the automated framework MInGLE+, to strengthen the design of CIs across applications from a domain. Our techniques still tractably generate a non-exponential search space with merging and fragments generation. The framework selects CIs among exact-matched, partially-matched and matching with fragments that fit into a particular hardware area, maximizing energy efficiency and speedup across the applications. We compare the effectiveness of all matching configurations across and within basic blocks, and we evaluate different design parameters of the framework and we study the area usage for the exposed techniques. The rest of this chapter is organized as follows: Section 5.2 explains the motivation behind the main contribution of this chapter. Section 5.3 introduces the framework in which the CIs are created. Section 5.4 presents a new matching technique with CI fragments, Section 5.5 explains the new distance calculation, and Section 5.6 includes the new selection strategy. For the evaluation, Section 5.7 presents results with several applications of the media domain, and Section 5.8 closes this chapter with the summary. 5.2. Motivation Consider the clustering dendrogram of Figure 5.1 that organizes a hierarchy of CI similarities. Baseline CIs are located at level 0, while merged CIs start from level 1 and go upwards from more to less similarity degree. At each new level, two CIs from lower levels are merged. In the merging process, the distance (dist) between CIs is evaluated to determine which is the next merging pair of CIs. Each one of the merged CIs has an overhead from multiplexer switches represented as MUX, and a figurative saved cycles and new area placed in adjacent boxes. Each one of the Nbaseline CIs is composed of one or several fragments, that we define as computation blocks that can be separated from the CI without incurring structural problems. Although those computation blocks can overlap, in this example, the internal CI operations covered by each fragment are fixed for illustrative purposes. Also, to simplify the example, we consider that each CI has only one variant. For instance, the only variant of CI_1, at level 0, is composed of fragments F1_A and F1_B. The partial merging explained in Chapter 4 merges whole CIs, based on increasing distance. With that method, we obtain first a new merged CI_2+3 at level 1and then CI_1+2+3 at level 2. With each new merged CI, we obtain a speedup based on the combined saved cycles, and a new area that includes non-common operations, merged common computations, and the switching Fragments of Domain-Specific Instructions 89 more similarity less . . . + CI_1 CI_2 CI_3 CI_N CI_2+3 F1_A F2_A F3_A FN_A CI_1+2+3 CI_2+3+F1_B saved cycles{2,3,1_B} merged area{2,3,1_B,MUX} saved cycles{2,3} merged area{2,3,MUX} saved cycles{1,2,3} merged area{1,2,3,MUX} Merged CI with fragments level 2 level 1 level 0 dist = 0.125 dist = 0.325 Merged CIs without fragments Figure 5.1: Motivational example of partial merging without and with CI fragments. 90 Chapter 5 logic overhead (MUX). However, consider CI_1+2+3 and its fragments at level 2, product of merging CI_1 with CI_2+3. Fragment F1_B from CI_1 is completely merged with CI_2+3, avoiding a significant area increase. In contrast, fragment F1_A, also from CI_1, is fully incorporated at a substantial area increase. Consequently, we can argue that if we merge only one of the fragments, we could obtain savings in cycles at a low area cost. This is the case that CI_- 2+3+F1_B on the right of the figure illustrates (Merged CI with fragments). If we merge only fragment F1_B from CI_1 with CI_2+3, the area increase from additional switching logic (extra) will be negligible, while performance will improve due to the additional saved cycles of computation block that F1_B accelerates. 5.3. MInGLE+ Automatic Framework We adopt the same baseline processor as in Chapter 4: an in-order Intel Atom modified accordingly to Figure 2.4. CIs execute on a DSFU that reads and writes data from the processor’s register files. Data transfers are therefore completely decoupled from CIs’ execution, that is multi-cycle, with variable latency, and not parallel with the processor’s functional units. We follow the same naming conventions as in Chapter 4, thus a CI is the high-level representation of a loop body or inline function that can be accelerated in hardware, and CI variants or only variants are distinct implementations of a CI. Figure 5.2 shows the high-level representation of MInGLE+ automated framework, composed of five steps. The framework follows a similar flow as described in Section 4.3. However, a new component is added after the Merged CIs Generation, which is the main contribution of this chapter. New Step 4,CI Fragments Generation, implements a new method to obtain larger improvements in performance and energy efficiency with small hardware areas available, which we explain in the following section. To adapt the CIs to the fragment recognition step, we also modified the Distance calculation, step 3.1, that obtains the pairwise distances to measure similarities between CIs (Section 5.5), and the objective function of the relabeled Step 5, CI Selection (Section 5.6), to fit the best CI configuration that includes fragments in a limited area to save energy and improve performance across the domain. Fragments of Domain-Specific Instructions 91 Figure 5.2: MInGLE+ automated framework for the implementation and generation of partially-merged CIs with fragments. 92 Chapter 5 5.4. Generation of Custom Instruction Fragments We call CI fragments a variation of partially matched CIs that will not include the full original CI, but parts (fragments) of it. This kind of matching is aimed to improve reutilization of hardware at the most limited areas. With CI fragments we can partially reuse an already merged CI cluster for CIs that were initially not included in that cluster, with minimum additional overhead. We obtain CI fragments in the CI Fragments Generation step of the MInGLE+ framework. There are some conditions to specify how suitable CI fragments are found: The size of a CI fragment is at most the same as the CI that matches, which is generally much bigger. Therefore, for a given merged CI, we can have several fragments from different applications matching. Operations included in a fragment do not depend on excluded ones, to avoid a convexity violation [61], or circular dependency between operations that could result in wrong scheduling. CI fragments should not add logic to perform computations, but they can add some additional overhead for switching circuits. They also may have extra cycles to transfer data and the total number of saved cycles are probably less than if the full CI was included. All this additional overhead and reduced gains are carefully weighed to determine if a CI fragment is worth including. We can create CI fragments from the basis of CIs from any level of the dendrogram, either with exact or with partial similarities. Starting the fragment search from a basis CI variant, merged or not merged, that implements a set of CIs C, we will only consider adding fragments from variants not included in C. Under those conditions, note that fragments of a given CI differ depending on the matching target, therefore their area coverage and saved cycles vary across solutions. Algorithm 2 lists the pseudo-code that detects fruitful fragments to augment the initial set of solutions generated after the hierarchical clustering. We evaluate against each solution the possible matches of any CI variant, represented as an MD, that is not yet part of the solution. We start with the clustering solutions MS, that are the base to the new solution set plus fragments (MSF). For each MD evaluated, we obtain the fragment matches Fragments of Domain-Specific Instructions 93 Algorithm 2: Fragment Matching input : Merged Diagrams MDs, merged clustering solutions MS, threshold output: Solutions MSF 1Array MSF ←− MS 2for Sol ∈MS do 3Candidates ←− ∅ 4for md ∈MDs do 5if CI(md)<Sol then 6FM ←− ∅ 7for WholeFrag ∈md do 8FM ← FM ∪GetMatchesOneWay(WholeFrag,Sol) 9end 10 if matches(FM)> threshold then 11 EDPImprov ←GetEDPImprovement(FM) 12 Candidates ←Candidates ∪< FM, EDPImprov > 13 end 14 end 15 end 16 BestCandidates ←FilterCIV ariant(Candidates) 17 NewSols ←CreateSolutions(BestCandidates) 18 MSF ←MSF ∪NewSols 19 end 20 return MSF (FM) evaluating separately the sequence of solutions that lead to each output (lines 6−9). Then, we can easily limit the fragmented matches to the boundaries of a certain output to control the convexity of the selected operations. With the function GetMatchesOneWay we perform a matching as explained in Section 5.5. In this case, we are only interested in knowing the coverage of each valid, whole fragment (WholeFrag) within sol. In lines 10 −13, we evaluate if the percentage of matches of the fragments found reach a user-defined threshold. If they do, an estimation of the expected EDP improvement is calculated, and the fragments of that CI variant are considered to be included. As several variants of the same CI could be in the set of candidates, we filter them based on the best estimated EDP im- 94 Chapter 5 provement in line 16. Finally, in the next line, we create a new solution structure with updated information over the area and the CI fragments that it includes, applying again the Performance and Energy Model step. 5.5. Distance and Matching Calculation We modify the Distance Calculation step of Merged CIs Generation (3.1 in Figure 5.2), to measure the similarities among CIs and to use the calculation also for finding CI fragments. For each pair of MDs of variants that do not implement the same CI, CIX and CIY, we compare them using the previously built global diagrams 4.5.2 to still compute distances fast. Thus, based on the pre-built global diagrams, we obtain the number of AugTED-operations and LinBDD-branches in CIX that do not match with those in CIY, namely nMX, and vice versa, nMY. However, looking at how fragments could match, we identify now three different types of matches with MDs: perfect, hidden and with overhead. An MD subdiagram Swith nodes < v1,...,vn>and edges < e1,...,en>has a perfect match with another MD subdiagram S′with nodes < v′ 1,...,v′ n> and edges < e′ 1,...,e′ n>if their labels and edges types match exactly. Afterwards, we identify a hidden match if the types of the outgoing edges of nodes vzand v′ zmatch and are connected to subdiagrams with a perfect match. Finally, a match with overhead identifies only nodes that represent the same operations, but that do not share the same computational structure and would need a multiplexer to be shared. MoXand MoYare then the number of nodes of CIXand CIY, respectively, with the same operations but with that extra overhead. As those matches with overhead incur in area costs, we count them also for the dissimilarity metric. We also count the number of total AugTED and LinBDD nodes that each MD variant has: TotXand TotY. Then, we compute the distance δas: δ(CIX,CIY)=average MoX 2+nMX TotX , MoY 2+nMY) TotY.(5.1) We use the same methodology for the function GetMatchesOneWay of Algorithm 2. In this case, we define a base MD Sol, and the potential MD fragment fand we obtain the matching information as described above. However, the distance value δ′will be in this case: δ′(Sol,f )= Mof 2+nMf Totf ,(5.2) Fragments of Domain-Specific Instructions 95 with Mofmatches of fwith overhead, nMfthe non-matching subdiagram nodes, and Totfthe total nodes of f. Apart from the distance, the matching information is also passed along to the CI fragments generation. 5.6. Custom Instruction Selection with Fragments In the last CI Selection step of MInGLE+, we choose again the best fitting CI configuration for a given hardware area. As explained in 4.7, we model this step as a Knapsack problem, trying to fitnCI variants, merged and not merged, with fragments included and not included, within a limited hardware area A. Each cicandidate still has a value vi, and a hardware occupancy hwi. Using MILP to solve the problem, the area constraint is: n X i=0 ci×hwi≤A. (5.3) The additional requirement of each CI being selected only once still holds, but expanding it with fragments. Now we not only have different variant implementations for each CI due to distinct unrolling factors or to merging, but we also include CIs with partially added fragments. Thus, we have to follow the same rule of invalidating a CI for further selection once a variant or only a fragment of that CI are selected. We do so by defining the constraint: m X i=0 vfi≤1,(5.4) with vfithe high-level CI that can be implemented by (m) CI variants and variants with fragments. The objective function, related to the overall energy-efficiency is: n X i=1 ci×σ_EDPi→max.(5.5) The metric σ_EDPiis computed as: σ_EDPi= B X j kσ_EDPijk,(5.6) where Bis the number of applications that the currently considered variant targets, and kσ_EDPijkis the original application j’s EDP minus the EDP 102 Chapter 5 TCandidates Time to solve EDP improvement num. % inc. secs. % inc. 90 363 – 24.4 – 2.64× 80 390 +7.4 26.5 +8.6 2.94× 70 456 +16.9 27.4 +3.4 2.94× 60 581 +27.4 33.7 +22.9 3.19× 50 633 +8.9 35.9 +6.5 3.64× 40 923 +45.8 52.4 +45.9 3.67× 30 1056 +14.4 59.3 +13.2 3.67× 20 2117 +100.4 125.5 +111.6 3.67× 10 2263 +6.9 135.3 +7.8 3.67× Table 5.2: Number of candidates in the selection step and time to solve the selection problem for different thresholds (T) using matching with fragments, for 1% of the area. 5.6 presents a comparison of solutions with different threshold values, with area percentage on the x-axis up to 2% and the average EDP improvement across the domain on the y-axis. The legend shows the thresholds that go from 90% to 10% of matching. A higher threshold corresponds to a higher similarity. The CI candidates with a given threshold include all those CIs from higher thresholds. For instance, a threshold of 70% also includes the CIs of thresholds 80% and 90%. We observe that up to 0.8% of the area, 10% threshold obtains the highest EDP improvement. However, from that area onwards, thresholds up to 50% yield the same EDP improvement and, from 1.3% of the area, thresholds 60% and 70% join the efficiency ceiling. The EDP improvement with a threshold of 90% at 2% of the area equals the one achieved with partial matching (no fragments). At larger areas, we have room to choose bigger variants that provide the full CI acceleration instead of fragments that do not give the maximum efficiency. Also, fragments with 90% similarity matching are more difficult to find than those with lower thresholds and therefore scarcer. The threshold level has an immediate effect on the number of CI candi- Fragments of Domain-Specific Instructions 103 dates in the selection pool and the runtime of the selection process, which is shown in Table 5.2. Data in the table refer to the selection step for 1% of the area. For each threshold percentage (T), we list first the number of candidates considered for selection with the percentage increase with respect to the previous row. We list also the time in seconds to solve the selection problem with the pool of candidates and, again, percentage increases. In the last column we list the EDP improvement achieved. Note that, for different areas, the number of CI candidates varies because some CIs are pre-filtered by area occupancy; if their area is greater than the maximum area targeted, they will not be considered. Also note that, as the number of candidates of a given threshold includes those of higher ones, the amount of candidates increases as the threshold value decreases. The time to solve increases linearly with the number of candidates; the largest difference in both the amount of CIs considered and seconds to solve happens relaxing the threshold from 30% to 20%, showing that smaller fragments are more frequent than larger ones. However, the EDP at those low thresholds is not better than thresholds of 40 −50% because larger fragments achieve better EDP, and the threshold is related to the size of the fragment. Thus, the increase in the problem complexity of the lowest thresholds weighed against the problem size and time to solve of a threshold of the 50% has no advantage because similar CIs are chosen. 5.7.2.3. Sharing Characterization In this last analysis, we evaluate how area is shared among CIs to understand the high gains that the matching with fragments provides. Figures 5.7 and 5.8 show two graphs that display the increasing percentage of the Virtex 7 occupancy (up to 5%) of different CI configurations on the x-axis versus the normalized percentage of LUTs on the y-axis, broken down by non-shared operators, shared operators and multiplexer overhead for circuit sharing. The CI configurations target all the applications in Table 5.1. The graph on Figure 5.7 shows the characterization for partial matching, whereas the graph on Figure 5.8 shows that of matching with fragments. First, we observe that, for partial matching, the CI configuration with the smallest area (0.2%) does not share any of the CIs included. At that small area, the cost for merging CI variants is too high to compete against lighter application-specific CIs. In contrast, matching with fragments devotes 80% of the LUTs on the smallest configuration to shared resources. We find the maximum percentage of shared circuits at smallest areas, which explains why the configurations with CI fragments are more efficient than those without. The percentage of overhead due to multiplexers is more no- 104 Chapter 5 0.20 0.40 0.60 0.80 0.99 1.20 1.38 1.60 1.79 1.98 2.19 2.32 2.59 2.76 3.00 3.11 3.48 3.54 3.78 3.98 4.19 4.33 4.51 4.86 5.00 Percentage of area 0.0 20.0 40.0 60.0 80.0 100.0 Percentage of LUTs Non-shared Shared Overhead Figure 5.7: Characterization of shared FPGA hardware for different area utilizations with partial matching. 0.20 0.40 0.59 0.79 0.98 1.20 1.38 1.58 1.78 2.00 2.18 2.39 2.58 2.78 3.03 3.22 3.46 3.58 3.82 3.96 4.20 4.36 4.63 4.79 4.94 Percentage of area 0.0 20.0 40.0 60.0 80.0 100.0 Percentage of LUTs Non-shared Shared Overhead Figure 5.8: Characterization of shared FPGA hardware for different area utilizations with fragments. Fragments of Domain-Specific Instructions 105 ticeable at lower areas also, correlated with the amount of shared resources. Although at larger area utilizations the sharing levels decrease, they are steadily higher than those for partial matching, where the sharing percentages are around the 30% on average. 5.8. Summary This chapter presents MInGLE+, an automated framework that extracts CIs from a domain of applications that are executed on a DSFU. We aim to select CIs that improve performance and energy efficiency for all the target applications, without substantially compromising any of them. Hence, we propose techniques to perform partial matching of CIs based on their similarity. Our techniques here build on top of the work of the previous chapter, now focusing on getting high benefits for DSFU with very limited areas. Therefore, we introduce an analysis step that detects fragments of CIs that can use the existing merged clusters with minimal extra overhead. Our experimental results with eleven media benchmarks show that the new matching technique with fragments achieves a speedup of 2.1×and an EDP improvement of 3.8×, on average, across basic blocks, while within a basic block we obtain a speedup of 1.5×and EDP improvement of 1.7×. Compared to partially matched CIs, CIs with fragments are key for achieving larger performance (2×versus 1.6×) and EDP improvements (3.6×versus 2.4×) for a limited hardware area (1%). This means that we achieve a particular energy efficiency with a greatly reduced hardware area. The work presented in this chapter, complemented with the analysis and techniques from Chapters 3 and 4, shows the applicability of introducing configurable accelerators with limited area inside embedded processors. We demonstrate the viability of accelerating many applications from a domain, improving the system’s performance and energy efficiency. 6 Conclusion 6.1. Overview Hardware specialization has gained attention over the past few years in an effort to improve performance and energy-efficiency at the end of Dennard scaling. However, an application-specific processor delivers high performance for that specific application only, and is costly to manufacture. In contrast, domain-specific acceleration may deliver better overall system performance when different applications run on the custom device, and may be more economically viable by targeting a larger market. In addition, the design of custom instructions (CIs) enables a fast way of creating specialized hardware from the extension of a general-purpose processor. CIs run on specialized functional units, which are an area-efficient alternative of hardware specialization, extending a processor with minimal impact on the existing design. The memory hierarchy is maintained, and although the amount of data that can be processed at once is limited, hardware extensions are more efficiently managed, and energy consumption can be better controlled to not be increased over the original baseline. Although domain-specific CIs stand as a plausible option for acceleration design, the differences among coding styles across applications complicate the task of finding patterns that can be executed by a single CI. Therefore, we propose using a canonical representation, the Taylor Expansion Diagram (TED), to identify CIs that are functionally similar. Com- 108 Conclusion pared to the commonly used Directed Acyclic Graph (DAG) representation, TEDs are more effective at identifying those functional equivalences along sequences of code within and across applications. We also propose a Hybrid representation, which uses TEDs when it is possible by the nature of the computation, and otherwise uses DAG. Additionally, we propose four scoring heuristics to quickly compare and rank CIs in the selection phase, which is known to be an NP-complete problem. These heuristics rank potential configurations of groups of CIs to smooth the gains obtained across applications, making them suitable for domain-specific acceleration. We combine the functional equivalence identification and the scoring heuristics in our framework FuSInG, which allows a design space exploration of new acceleration designs through performance and area estimation. With the framework, we evaluate the proposed methodologies using a set of application benchmarks from the media domain. We first explore the effectiveness of a canonical representation for the design of domainspecific CIs. While TED’s canonical representation does not lead to better results than DAG with code sequences within the same application, it is key to achieve higher speedups when generating domain-specific CIs. As individual applications are coded following the same style, the benefit of a canonical representation is unnoticeable, as opposed to CIs across applications with different code styles. In the domain-specific case, we find that Hybrid and TED techniques perform very similarly. Hybrid is, though, the most effective technique, achieving higher speedups at smaller areas and increasing the speedup faster than only TED or DAG. The main advantage of the Hybrid technique is that it tries to identify identical CIs using TED first, and when it cannot find any more, it complements the identification using DAG. Furthermore, we evaluate the behavior of the heuristic selection techniques. We observe that, from all four, the random-scaled sharing technique performs best on average, since it maximizes the overall performance across applications. Also, we explore the trade-offs of different SFU configurations to optimize full-system performance across applications subject to area constraints. We compare configurations with application-specific only, domain-specific only, or both application- and domain-specific CIs. We find that, while application-specific CIs result in the highest possible performance at large or unbounded core areas, considering domain-specific CIs next to application-specific CIs yields to the highest possible speedup at realistic, smaller core areas. In addition, we cross-validate the results looking at the performance of non-analyzed applications that run upon a machine configured with a set of CIs for a particular application domain. We demonstrate that the identified CIs are effective for previously unseen Conclusion 109 applications within the same domain, making specialization more generally applicable. These findings underline the need of domain-specific instructions for practical and flexible hardware specialization. In order to achieve high and balanced speedups with domain-specific CIs, reusability across applications is a critical factor. However, targeting code sections beyond the basic block level to achieve higher speedups results in not enough exact equivalences to generalize the accelerating hardware. Therefore, to improve the code coverage, we propose a new canonical representation of code sequences across basic blocks, the Merging Diagram. This representation is partly based on TED-DAG Hybrid, and its structure facilitates the identification of partial similarities. We also introduce a clusteringbased partial matching of CIs, that we merge, calculating their potential performance and energy improvement. Also, having confirmed the suitability of the CI selection in an application domain, we introduce energy efficiency as a new parameter to take into account, since in the context of devices with limited power-budgets, focusing only on performance could introduce power-hungry CIs. We propose then a constraint-based selection mechanism that, with a novel objective function, balances speedup and energy efficiency across an application domain. These techniques expand the opportunity for CIs with a limited area budget inside embedded processors to accelerate several applications from a domain, improving the system’s energy efficiency. We evaluate our claims with MInGLE, an automated framework that converts code sequences at the loop body level into CIs, considering several implementations for each of them. CIs are further transformed into Merging Diagrams, and clustered to find partially-matching sequences to minimize specialized area. Experimental results with a set of media benchmarks show that looking across basic blocks achieves a speedup of 1.98×and an EDP improvement of 3.35×, a significant gain over looking within a single basic block (speedup of 1.48×and EDP improvement of 1.67×). Improvements in both performance and EDP across basic blocks are due to be able to cover 41% more dynamic instructions on average, which expands the acceleration opportunities. Furthermore, across basic blocks, partial matching achieves larger speedups and EDP improvements as compared to exact matching, given the same area. For example, for a limited hardware area (1.8%), partial matching achieve larger performance than exact matching (1.88×versus 1.73×) and EDP improvements (3.04×versus 2.53×). Alternatively, for a given EDP improvement, partial matching saves area, which is important as the area available to implement the CIs in a low-power processor is very limited. 110 Conclusion Previous results show that partially-similar domain-specific CIs outperform application-specific ones when the area for implementation is over a given threshold. However, at small areas, application-specific CIs are still in dominance, since the overhead added when two CIs are merged override the potential gains. Consequently, we extend the CI merging of MInGLE with an analysis step that detects fragments of CIs that can use the existing merged clusters with minimal extra overhead. With CI fragments we can improve reutilization of hardware at the most limited areas, because we partially reuse an already merged CI cluster. Experimental results show that the new matching technique with fragments achieves a speedup of 2.1×and an EDP improvement of 3.8×, on average, across basic blocks, while within a basic block we obtain a speedup of 1.5×and EDP improvement of 1.7×. Comparing matching techniques across basic blocks, matching with fragments outperforms previously proposed techniques from the beginning, at very limited areas. With only 1% of the area, we have a speedup of 2× and EDP improvement of 3.65×, clearly higher than the same values for partial matching, 1.63×and 2.35×, respectively. Matching with fragments uses area more effectively; a speedup of 1.96×is achieved with fragments at 0.75% of the area, in contrast with the 2.5% needed with partial matching. As there is virtually more area available from the low overhead costs of including a new fragment, better performing CIs can be selected. The results presented in this dissertation show the applicability of introducing configurable accelerators with limited area inside low-power processors to accelerate many applications from a domain, improving the system’s performance and energy efficiency. 6.2. Future work The techniques for domain-specific acceleration proposed in this dissertation could be extended and adapted to new environments. In order to improve performance, we could broaden the coverage of CIs beyond the loop body level. For example, the analysis phase might try to identify a coarser type of CIs than body loops, possibly at the function level. However, finding similarities across larger sequences of code might pose a problem, once again due to the disparities of coding strategies across applications. That said, a new canonical representation at the algorithmic level, conscious of data structures, and acting as a functional intermediate representation, could help with the similarity identification. With a beyondloop-level type of CI, memory transfers should be included, which might imply architectural changes to allow more direct memory connections. To improve the similarity matching, we could also consider approximate com- Conclusion 111 puting approaches, such as relaxing type constraints to be able to generalize more CIs across applications. To extend the applicability of the techniques presented in this dissertation, instead of an off-line analysis and generation of CIs, we could do both the identification of CIs and configuration of SFUs in runtime. Runtime configuration would need architectural support to raise an exception and stop the program, flushing and updating the SFU. Identification at runtime is a more interesting and difficult problem. We could approach it, for instance, by establishing an initial baseline of CIs that could evolve and change depending on real workload dynamics. Additionally, we could extrapolate the domain-specific design methods to other, not yet explored, architectures. For instance, the design and implementation of non-tightly-coupled accelerator types would be of interest, because off-core accelerators would allow better performance gains. This direction would be related to the expansion of CIs beyond the loop body, since full functions would be offloaded on accelerators to minimize communication with the main processor. However, without changing the granularity of the CIs, we could start extending the current work for out-of-order processors, which in the latest years are growing as the default choice in embedded devices. Also, we could evaluate our techniques in other highperformance environments, like multiprocessors. Using an Intel Atom prototype with 2-way SMT, we can have up to 4 simultaneous threads with a dual-core machine. We could study the architectural possibilities on such a platform, and the possible impact of introducing CIs in the system. For example, in a scenario of two applications running concurrently in the same chip, we could design exact duplicates of the DSFUs as it is done in Atom for rest of the FUs. Alternatively, we could design different kinds of DSFUs in each processor, and a scheduler would choose in which one of them a process that uses CIs would run. 118 Bibliography [48] M. Arnold and H. Corporaal, “Designing domain-specific processors,” in Proceedings of the 9th International Symposium on Hardware/Software Codesign, pp. 61–66, ACM, 2001. [49] A. A. Hagberg, D. A. Schult, and P. J. Swart, “Exploring network structure, dynamics, and function using NetworkX,” in Proceedings of the 7th Python in Science Conference (SciPy2008), pp. 11–15, Aug. 2008. [50] W. Stein et al.,Sage Mathematics Software (Version 5.8). The Sage Development Team, 2013. http://www.sagemath.org. [51] SRISC, “Simply risc s1 core,” 2012. [52] G. Bradski, “The OpenCV Library,” Dr. Dobb’s Journal of Software Tools, 2000. [53] J. E. Fritts, F. W. Steiling, J. A. Tucek, and W. Wolf, “MediaBench II video: expediting the next generation of video systems research,” Microprocessor and Microsystems, vol. 33, pp. 301–318, June 2009. [54] I. Kuon and J. Rose, “Measuring the gap between FPGAs and ASICs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 26, pp. 203–215, Feb 2007. [55] M. R. Guthaus, J. S. Ringenberg, D. Ernst, T. M. Austin, T. Mudge, and R. B. Brown, “MiBench: A free, commercially representative embedded benchmark suite,” in Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop, WWC ’01, pp. 3–14, IEEE Computer Society, 2001. [56] T. E. Carlson, W. Heirman, S. Eyerman, I. Hur, and L. Eeckhout, “An evaluation of high-level mechanistic core models,” ACM Transactions on Architecture and Code Optimization (TACO), 2014. [57] S. Li, J. H. Ahn, R. D. Strong, J. B. Brockman, D. M. Tullsen, and N. P. Jouppi, “McPAT: An integrated power, area, and timing modeling framework for multicore and manycore architectures,” in Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture, MICRO 42, pp. 469–480, ACM, 2009. [58] D. Müllner, “fastcluster: Fast hierarchical, agglomerative clustering routines for R and Python,” Journal of Statistical Software, vol. 53, no. 9, pp. 1–18, 2013. Bibliography 119 [59] IBM, “ILOG CPLEX Optimizer.” http://www-01.ibm.com/ software/commerce/optimization/cplex-optimizer/index. html, 2015. [60] D. Kroshko, “OpenOpt: Free scientific-engineering software for mathematical modeling and optimization,” 2007–2015. [61] K. Karuri and R. Leupers, “A primer on ISA customization,” in Application Analysis Tools for ASIP Design, pp. 93–109, Springer New York, 2011.