Theory for systolizing global computational problems.

Wentai Liu, Ralph K. Cavin, Thomas Hughes

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


A theory is presented for rasterizing a class of two-dimensional problems including signal/image processing, computer vision, and linear algebra. The rasterization theory is steered by an isomorphic relationship between the multidimensional shuffle-exchange network (mDSE) and the multidimensional butterfly network (mDBN). Many important multidimensional signal-processing problems can be solved on a mDSE with a solution time approaching known theoretical lower bounds. The isomorphism between mDSE and mDBN is exploited by transforming and mDSE solution into its equivalent mDBN solution. A methodology for rastering the mDBN solution is developed. It turns out that not all mD algorithms can be rasterized. A sufficient condition for algorithm rasterization is given.

Original languageEnglish
Title of host publicationProc Int Conf on Systolic Arrays
PublisherPubl by IEEE
Number of pages11
ISBN (Print)0818688602
Publication statusPublished - 1988

Publication series

NameProc Int Conf on Systolic Arrays

All Science Journal Classification (ASJC) codes

  • General Engineering


Dive into the research topics of 'Theory for systolizing global computational problems.'. Together they form a unique fingerprint.

Cite this