Parallel Custom Instruction Identification for Extensible Processors
| Autor: | Emmanuel Casseau, Chenglong Xiao, Shanshan Wang, Wanjun Liu |
|---|---|
| Přispěvatelé: | Liaoning Technical University [Huludao], Energy Efficient Computing ArchItectures with Embedded Reconfigurable Resources (CAIRN), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-ARCHITECTURE (IRISA-D3), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), ARCHITECTURE (IRISA-D3), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria) |
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: |
[INFO.INFO-AR]Computer Science [cs]/Hardware Architecture [cs.AR]
Theoretical computer science Computer science Parallel algorithms Subgraph isomorphism problem Parallel algorithm 02 engineering and technology Parallel computing 01 natural sciences Maximum common subgraph isomorphism problem Software Local optimum Application domain Computer cluster 0103 physical sciences 0202 electrical engineering electronic engineering information engineering Extensible processors 010302 applied physics Mathematics::Combinatorics business.industry Ant colony optimization algorithms Custom instruction Subgraph enumeration algorithm 020202 computer hardware & architecture Hardware and Architecture business Subgraph selection algorithm |
| Zdroj: | Journal of Systems Architecture Journal of Systems Architecture, 2017, 76, pp.149-159. ⟨10.1016/j.sysarc.2016.11.011⟩ Journal of Systems Architecture, Elsevier, 2017, 76, pp.149-159. ⟨10.1016/j.sysarc.2016.11.011⟩ |
| ISSN: | 1383-7621 |
| DOI: | 10.1016/j.sysarc.2016.11.011⟩ |
| Popis: | International audience; With the ability of customization for an application domain, extensible processors have been used more and more in embedded systems in recent years. Extensible processors customize an application domain by executing parts of application code in hardware instead of software. Determining parts of application code as custom instruction generally requires subgraph enumeration and subgraph selection. Both subgraph enumeration problem and subgraph selection problem are computationally difficult problems. Most of previous works focus on sequential algorithms for these two problems. In this paper, we present a parallel implementation of a latest subgraph enumeration algorithm based on a computer cluster. A standard ant colony optimization algorithm (ACO), a modified version of ACO with local optimum search and a parallel ACO algorithm are also proposed to solve the subgraph selection problem in this work. Experimental results show that the parallel algorithms outperform the sequential algorithms in terms of runtime or (and) quality of results. In addition, we have formally proved the upper bound on the number of feasible solutions in subgraph selection problem with or without the overlapping constraint. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect