Quantifying intrinsic parallelism via eigen-decomposition of dataflow graphs for algorithm/architecture co-exploration

He Yuan Lin, Gwo-Giun Lee

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)

Abstract

Algorithmic complexity analysis and dataflow models play significant roles in the concurrent optimization of both algorithms and architectures, which is now a new design paradigm referred to as Algorithm/Architecture Co-exploration. One of the essential complexity metrics is the parallelism revealing the number of operations that can be concurrently executed. Inspired by the principle component analysis (PCA) capable of transforming random variables into uncorrelated ones and hence dependency analysis, this paper presents a systematic methodology for identifying independent operations in algorithms and hence quantifying the intrinsic degree of parallelism based on the dataflow modeling and subsequent eigen-decomposition of the dataflow graphs. Our quantified degree of parallelism is platform-independent and is capable of providing insight into architectural characteristics in early design stages. Starting from different dataflows derived from signal flow graphs in basic signal processing algorithms, the case study on DCT shows that our proposed method is capable of quantitatively characterizing the algorithmic parallelisms making possible the potentially facilitation of the design space exploration in early system design stages especially for parallel processing platforms.

Original languageEnglish
Title of host publication2010 IEEE Workshop on Signal Processing Systems, SiPS 2010 - Proceedings
Pages317-322
Number of pages6
DOIs
Publication statusPublished - 2010 Dec 27
Event2010 IEEE Workshop on Signal Processing Systems, SiPS 2010 - San Francisco, CA, United States
Duration: 2010 Oct 62010 Oct 8

Publication series

NameIEEE Workshop on Signal Processing Systems, SiPS: Design and Implementation
ISSN (Print)1520-6130

Other

Other2010 IEEE Workshop on Signal Processing Systems, SiPS 2010
Country/TerritoryUnited States
CitySan Francisco, CA
Period10-10-0610-10-08

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering
  • Signal Processing
  • Applied Mathematics
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Quantifying intrinsic parallelism via eigen-decomposition of dataflow graphs for algorithm/architecture co-exploration'. Together they form a unique fingerprint.

Cite this