Rapid evaluation of custom instruction selection approaches with FPGA estimation

Siew Kei Lam, Thambipillai Srikanthan, Christopher T. Clarke

Research output: Contribution to journalArticle

Abstract

The main aim of this article is to demonstrate that a fast and accurate FPGA estimation engine is indispensable in design flows for custom instruction (template) selection. The need for a FPGA estimation engine stems from the difficulty in predicting the FPGA performance measures of selected custom instructions. We will present a FPGA estimation technique that partitions the high-level representation of custom instructions into clusters based on the structural organization of the target FPGA, while taking into account general logic synthesis principles adopted by FPGA tools. In this work, we have evaluated a widely used graph covering algorithm with various heuristics for custom instruction selection. In addition, we present an algorithm called Refined Largest Fit First (RLFF) that relies on a graph covering heuristic to select nonoverlapping superset templates, which typically incorporate frequently used basic templates. The initial solution is further refined by considering overlapping templates that were ignored previously to see if their introduction could lead to higher performance. While RLFF provides the most efficient cover compared to the ILP method and other graph covering heuristics, FPGA estimation results reveals that RLFF leads to the worst performance in certain applications. It is therefore a worthy proposition to equip design flows with accurate FPGA estimation in order to rapidly determine the most profitable custom instruction approach for a given application.

LanguageEnglish
Article number75
Pages1 - 29
Number of pages29
JournalACM Transactions on Embedded Computing Systems
Volume13
Issue number4
DOIs
StatusPublished - Nov 2014

Fingerprint

Field programmable gate arrays (FPGA)
Engines
Inductive logic programming (ILP)

Keywords

  • Approximation algorithms
  • Customizable processors
  • FPGA
  • ISA extension

Cite this

Rapid evaluation of custom instruction selection approaches with FPGA estimation. / Lam, Siew Kei; Srikanthan, Thambipillai; Clarke, Christopher T.

In: ACM Transactions on Embedded Computing Systems, Vol. 13, No. 4, 75, 11.2014, p. 1 - 29.

Research output: Contribution to journalArticle

Lam, Siew Kei ; Srikanthan, Thambipillai ; Clarke, Christopher T./ Rapid evaluation of custom instruction selection approaches with FPGA estimation. In: ACM Transactions on Embedded Computing Systems. 2014 ; Vol. 13, No. 4. pp. 1 - 29
@article{8b49d0c7ce3346419842ca32c9dcbaaf,
title = "Rapid evaluation of custom instruction selection approaches with FPGA estimation",
abstract = "The main aim of this article is to demonstrate that a fast and accurate FPGA estimation engine is indispensable in design flows for custom instruction (template) selection. The need for a FPGA estimation engine stems from the difficulty in predicting the FPGA performance measures of selected custom instructions. We will present a FPGA estimation technique that partitions the high-level representation of custom instructions into clusters based on the structural organization of the target FPGA, while taking into account general logic synthesis principles adopted by FPGA tools. In this work, we have evaluated a widely used graph covering algorithm with various heuristics for custom instruction selection. In addition, we present an algorithm called Refined Largest Fit First (RLFF) that relies on a graph covering heuristic to select nonoverlapping superset templates, which typically incorporate frequently used basic templates. The initial solution is further refined by considering overlapping templates that were ignored previously to see if their introduction could lead to higher performance. While RLFF provides the most efficient cover compared to the ILP method and other graph covering heuristics, FPGA estimation results reveals that RLFF leads to the worst performance in certain applications. It is therefore a worthy proposition to equip design flows with accurate FPGA estimation in order to rapidly determine the most profitable custom instruction approach for a given application.",
keywords = "Approximation algorithms, Customizable processors, FPGA, ISA extension",
author = "Lam, {Siew Kei} and Thambipillai Srikanthan and Clarke, {Christopher T.}",
year = "2014",
month = "11",
doi = "10.1145/2560014",
language = "English",
volume = "13",
pages = "1 -- 29",
journal = "ACM Transactions on Embedded Computing Systems",
issn = "1539-9087",
publisher = "Association for Computing Machinery",
number = "4",

}

TY - JOUR

T1 - Rapid evaluation of custom instruction selection approaches with FPGA estimation

AU - Lam,Siew Kei

AU - Srikanthan,Thambipillai

AU - Clarke,Christopher T.

PY - 2014/11

Y1 - 2014/11

N2 - The main aim of this article is to demonstrate that a fast and accurate FPGA estimation engine is indispensable in design flows for custom instruction (template) selection. The need for a FPGA estimation engine stems from the difficulty in predicting the FPGA performance measures of selected custom instructions. We will present a FPGA estimation technique that partitions the high-level representation of custom instructions into clusters based on the structural organization of the target FPGA, while taking into account general logic synthesis principles adopted by FPGA tools. In this work, we have evaluated a widely used graph covering algorithm with various heuristics for custom instruction selection. In addition, we present an algorithm called Refined Largest Fit First (RLFF) that relies on a graph covering heuristic to select nonoverlapping superset templates, which typically incorporate frequently used basic templates. The initial solution is further refined by considering overlapping templates that were ignored previously to see if their introduction could lead to higher performance. While RLFF provides the most efficient cover compared to the ILP method and other graph covering heuristics, FPGA estimation results reveals that RLFF leads to the worst performance in certain applications. It is therefore a worthy proposition to equip design flows with accurate FPGA estimation in order to rapidly determine the most profitable custom instruction approach for a given application.

AB - The main aim of this article is to demonstrate that a fast and accurate FPGA estimation engine is indispensable in design flows for custom instruction (template) selection. The need for a FPGA estimation engine stems from the difficulty in predicting the FPGA performance measures of selected custom instructions. We will present a FPGA estimation technique that partitions the high-level representation of custom instructions into clusters based on the structural organization of the target FPGA, while taking into account general logic synthesis principles adopted by FPGA tools. In this work, we have evaluated a widely used graph covering algorithm with various heuristics for custom instruction selection. In addition, we present an algorithm called Refined Largest Fit First (RLFF) that relies on a graph covering heuristic to select nonoverlapping superset templates, which typically incorporate frequently used basic templates. The initial solution is further refined by considering overlapping templates that were ignored previously to see if their introduction could lead to higher performance. While RLFF provides the most efficient cover compared to the ILP method and other graph covering heuristics, FPGA estimation results reveals that RLFF leads to the worst performance in certain applications. It is therefore a worthy proposition to equip design flows with accurate FPGA estimation in order to rapidly determine the most profitable custom instruction approach for a given application.

KW - Approximation algorithms

KW - Customizable processors

KW - FPGA

KW - ISA extension

UR - http://www.scopus.com/inward/record.url?scp=84930354010&partnerID=8YFLogxK

UR - http://dx.doi.org/10.1145/2560014

U2 - 10.1145/2560014

DO - 10.1145/2560014

M3 - Article

VL - 13

SP - 1

EP - 29

JO - ACM Transactions on Embedded Computing Systems

T2 - ACM Transactions on Embedded Computing Systems

JF - ACM Transactions on Embedded Computing Systems

SN - 1539-9087

IS - 4

M1 - 75

ER -