ILP-based cost-optimal DSP synthesis with module selection and data format conversion

Kazuhito Ito, Lori E. Lucke, Keshab K Parhi

Research output: Contribution to journalArticle

36 Citations (Scopus)

Abstract

In high-level synthesis, a data flow graph (DFG) description of an algorithm is mapped onto a register transfer level description of an architecture. Each node of the DFG is scheduled to a specific time and allocated to a processor. In this paper, we present new integer linear programming (ILP) models which generate a blocked schedule for a DFG with automatic retiming, pipelining, and unfolding while performing module selection and data format conversion. A blocked schedule is a schedule which overlaps multiple iterations of the DFG to guarantee a processor optimal schedule. During module selection an appropriate processor is chosen from a library of processors to construct a cost optimal architecture. Furthermore, we also include the cost and latency of data format conversions between processors of different implementation styles. We also present a new formulation for minimizing the unfolding factor of the blocked schedule. The approach presented in this paper is the only systematic approach proposed so far to include implicit unfolding and to perform synthesis using nonuniform processor styles and data format converters.

Original languageEnglish (US)
Pages (from-to)582-594
Number of pages13
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume6
Issue number4
DOIs
StatePublished - Dec 1 1998

Fingerprint

Data flow graphs
Linear programming
Costs

Keywords

  • Data format conversion
  • High-level synthesis
  • Integer linear programming
  • Module selection
  • Time-constrained scheduling

Cite this

ILP-based cost-optimal DSP synthesis with module selection and data format conversion. / Ito, Kazuhito; Lucke, Lori E.; Parhi, Keshab K.

In: IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 6, No. 4, 01.12.1998, p. 582-594.

Research output: Contribution to journalArticle

@article{9df3aba379ab47459fcdb6db0db2c406,
title = "ILP-based cost-optimal DSP synthesis with module selection and data format conversion",
abstract = "In high-level synthesis, a data flow graph (DFG) description of an algorithm is mapped onto a register transfer level description of an architecture. Each node of the DFG is scheduled to a specific time and allocated to a processor. In this paper, we present new integer linear programming (ILP) models which generate a blocked schedule for a DFG with automatic retiming, pipelining, and unfolding while performing module selection and data format conversion. A blocked schedule is a schedule which overlaps multiple iterations of the DFG to guarantee a processor optimal schedule. During module selection an appropriate processor is chosen from a library of processors to construct a cost optimal architecture. Furthermore, we also include the cost and latency of data format conversions between processors of different implementation styles. We also present a new formulation for minimizing the unfolding factor of the blocked schedule. The approach presented in this paper is the only systematic approach proposed so far to include implicit unfolding and to perform synthesis using nonuniform processor styles and data format converters.",
keywords = "Data format conversion, High-level synthesis, Integer linear programming, Module selection, Time-constrained scheduling",
author = "Kazuhito Ito and Lucke, {Lori E.} and Parhi, {Keshab K}",
year = "1998",
month = "12",
day = "1",
doi = "10.1109/92.736132",
language = "English (US)",
volume = "6",
pages = "582--594",
journal = "IEEE Transactions on Very Large Scale Integration (VLSI) Systems",
issn = "1063-8210",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "4",

}

TY - JOUR

T1 - ILP-based cost-optimal DSP synthesis with module selection and data format conversion

AU - Ito, Kazuhito

AU - Lucke, Lori E.

AU - Parhi, Keshab K

PY - 1998/12/1

Y1 - 1998/12/1

N2 - In high-level synthesis, a data flow graph (DFG) description of an algorithm is mapped onto a register transfer level description of an architecture. Each node of the DFG is scheduled to a specific time and allocated to a processor. In this paper, we present new integer linear programming (ILP) models which generate a blocked schedule for a DFG with automatic retiming, pipelining, and unfolding while performing module selection and data format conversion. A blocked schedule is a schedule which overlaps multiple iterations of the DFG to guarantee a processor optimal schedule. During module selection an appropriate processor is chosen from a library of processors to construct a cost optimal architecture. Furthermore, we also include the cost and latency of data format conversions between processors of different implementation styles. We also present a new formulation for minimizing the unfolding factor of the blocked schedule. The approach presented in this paper is the only systematic approach proposed so far to include implicit unfolding and to perform synthesis using nonuniform processor styles and data format converters.

AB - In high-level synthesis, a data flow graph (DFG) description of an algorithm is mapped onto a register transfer level description of an architecture. Each node of the DFG is scheduled to a specific time and allocated to a processor. In this paper, we present new integer linear programming (ILP) models which generate a blocked schedule for a DFG with automatic retiming, pipelining, and unfolding while performing module selection and data format conversion. A blocked schedule is a schedule which overlaps multiple iterations of the DFG to guarantee a processor optimal schedule. During module selection an appropriate processor is chosen from a library of processors to construct a cost optimal architecture. Furthermore, we also include the cost and latency of data format conversions between processors of different implementation styles. We also present a new formulation for minimizing the unfolding factor of the blocked schedule. The approach presented in this paper is the only systematic approach proposed so far to include implicit unfolding and to perform synthesis using nonuniform processor styles and data format converters.

KW - Data format conversion

KW - High-level synthesis

KW - Integer linear programming

KW - Module selection

KW - Time-constrained scheduling

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

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

U2 - 10.1109/92.736132

DO - 10.1109/92.736132

M3 - Article

VL - 6

SP - 582

EP - 594

JO - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

JF - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

SN - 1063-8210

IS - 4

ER -