Loop-list scheduling for heterogeneous functional units

Y. N. Chang, Ch Y. Wang, Keshab K Parhi

Research output: Contribution to journalArticle

12 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 a library of heterogeneous implementation style based functional units 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)2-7
Number of pages6
JournalProceedings of the IEEE Great Lakes Symposium on VLSI
StatePublished - Jan 1 1996

Fingerprint

Scheduling
Linear programming
Digital signal processing
Costs
Experiments
High level synthesis

Cite this

Loop-list scheduling for heterogeneous functional units. / Chang, Y. N.; Wang, Ch Y.; Parhi, Keshab K.

In: Proceedings of the IEEE Great Lakes Symposium on VLSI, 01.01.1996, p. 2-7.

Research output: Contribution to journalArticle

@article{507b7a42b88b4602839c07a47f463c5c,
title = "Loop-list scheduling for 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 a library of heterogeneous implementation style based functional units 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, {Y. N.} and Wang, {Ch Y.} and Parhi, {Keshab K}",
year = "1996",
month = "1",
day = "1",
language = "English (US)",
pages = "2--7",
journal = "Proceedings of the IEEE Great Lakes Symposium on VLSI",
issn = "1066-1395",
publisher = "IEEE Computer Society",

}

TY - JOUR

T1 - Loop-list scheduling for heterogeneous functional units

AU - Chang, Y. N.

AU - Wang, Ch Y.

AU - Parhi, Keshab K

PY - 1996/1/1

Y1 - 1996/1/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 a library of heterogeneous implementation style based functional units 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 a library of heterogeneous implementation style based functional units 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=0029694860&partnerID=8YFLogxK

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

M3 - Article

SP - 2

EP - 7

JO - Proceedings of the IEEE Great Lakes Symposium on VLSI

JF - Proceedings of the IEEE Great Lakes Symposium on VLSI

SN - 1066-1395

ER -