Heuristic Loop-Based Scheduling and Allocation for DSP Synthesis with Heterogeneous Functional Units

Yun Nan Chang, Ching Y.I. Wang, Keshab K Parhi

Research output: Contribution to journalArticle

4 Citations (Scopus)

Abstract

This paper presents a new heuristic, concurrent, iterative loop-based scheduling and allocation algorithm for high-level synthesis of digital signal processing (DSP) architectures using heterogeneous functional units. In a heterogeneous architecture, functional units could be either bit-serial or digit-serial or bit-parallel. We assume that a library of functional units based on heterogeneous implementation style is available. Experiments show that this new heuristic synthesis approach generates optimal and near-optimal area solutions. Although optimum synthesis of such architectures were proposed recently using an integer linear programming (ILP) model, our method can produce similar solutions in one to two orders of magnitude less time, at the expense of sacrificing the cost optimality. We compare the solutions generated by the proposed algorithm with the optimal solutions generated by the ILP approach and other recent techniques. We have incorporated this new algorithm into the Minnesota ARchitecture Synthesis (MARS-II) system.

Original languageEnglish (US)
Pages (from-to)243-256
Number of pages14
JournalJournal of VLSI Signal Processing Systems for Signal, Image, and Video Technology
Volume19
Issue number3
StatePublished - Dec 1 1998

Fingerprint

Digital signal processing
Signal Processing
Scheduling
Heuristics
Synthesis
Linear programming
Unit
Integer Linear Programming
High-level Synthesis
Digit
Programming Model
Concurrent
Linear Model
Optimality
Optimal Solution
Architecture
Costs
Experiments
Experiment

Cite this

Heuristic Loop-Based Scheduling and Allocation for DSP Synthesis with Heterogeneous Functional Units. / Chang, Yun Nan; Wang, Ching Y.I.; Parhi, Keshab K.

In: Journal of VLSI Signal Processing Systems for Signal, Image, and Video Technology, Vol. 19, No. 3, 01.12.1998, p. 243-256.

Research output: Contribution to journalArticle

@article{5ce1c29549ab412388eca4897790d0b8,
title = "Heuristic Loop-Based Scheduling and Allocation for DSP Synthesis with Heterogeneous Functional Units",
abstract = "This paper presents a new heuristic, concurrent, iterative loop-based scheduling and allocation algorithm for high-level synthesis of digital signal processing (DSP) architectures using heterogeneous functional units. In a heterogeneous architecture, functional units could be either bit-serial or digit-serial or bit-parallel. We assume that a library of functional units based on heterogeneous implementation style is available. Experiments show that this new heuristic synthesis approach generates optimal and near-optimal area solutions. Although optimum synthesis of such architectures were proposed recently using an integer linear programming (ILP) model, our method can produce similar solutions in one to two orders of magnitude less time, at the expense of sacrificing the cost optimality. We compare the solutions generated by the proposed algorithm with the optimal solutions generated by the ILP approach and other recent techniques. We have incorporated this new algorithm into the Minnesota ARchitecture Synthesis (MARS-II) system.",
author = "Chang, {Yun Nan} and Wang, {Ching Y.I.} and Parhi, {Keshab K}",
year = "1998",
month = "12",
day = "1",
language = "English (US)",
volume = "19",
pages = "243--256",
journal = "Journal of Signal Processing Systems",
issn = "1939-8018",
publisher = "Springer New York",
number = "3",

}

TY - JOUR

T1 - Heuristic Loop-Based Scheduling and Allocation for DSP Synthesis with Heterogeneous Functional Units

AU - Chang, Yun Nan

AU - Wang, Ching Y.I.

AU - Parhi, Keshab K

PY - 1998/12/1

Y1 - 1998/12/1

N2 - This paper presents a new heuristic, concurrent, iterative loop-based scheduling and allocation algorithm for high-level synthesis of digital signal processing (DSP) architectures using heterogeneous functional units. In a heterogeneous architecture, functional units could be either bit-serial or digit-serial or bit-parallel. We assume that a library of functional units based on heterogeneous implementation style is available. Experiments show that this new heuristic synthesis approach generates optimal and near-optimal area solutions. Although optimum synthesis of such architectures were proposed recently using an integer linear programming (ILP) model, our method can produce similar solutions in one to two orders of magnitude less time, at the expense of sacrificing the cost optimality. We compare the solutions generated by the proposed algorithm with the optimal solutions generated by the ILP approach and other recent techniques. We have incorporated this new algorithm into the Minnesota ARchitecture Synthesis (MARS-II) system.

AB - This paper presents a new heuristic, concurrent, iterative loop-based scheduling and allocation algorithm for high-level synthesis of digital signal processing (DSP) architectures using heterogeneous functional units. In a heterogeneous architecture, functional units could be either bit-serial or digit-serial or bit-parallel. We assume that a library of functional units based on heterogeneous implementation style is available. Experiments show that this new heuristic synthesis approach generates optimal and near-optimal area solutions. Although optimum synthesis of such architectures were proposed recently using an integer linear programming (ILP) model, our method can produce similar solutions in one to two orders of magnitude less time, at the expense of sacrificing the cost optimality. We compare the solutions generated by the proposed algorithm with the optimal solutions generated by the ILP approach and other recent techniques. We have incorporated this new algorithm into the Minnesota ARchitecture Synthesis (MARS-II) system.

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

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

M3 - Article

VL - 19

SP - 243

EP - 256

JO - Journal of Signal Processing Systems

JF - Journal of Signal Processing Systems

SN - 1939-8018

IS - 3

ER -