Systolic partitioning algorithms

Systolic arrays are derived for the so-called partition problem using the dynamic programming method. The recurrence formulation associated with this method involves some peculiar non-uniformities which cause existing synthesis methods to break down. It is shown that such difficulties can be overcom...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 1993-04, Vol.46 (1), p.13-18
Main Author: Megson, G.M.
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Computer science
control theory
systems
Computer systems and distributed systems. User interface
design of algorithms
Dynamic programming
Exact sciences and technology
Information processing
Mathematical models
parallel processing
Software
Studies
Systolic arrays
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Systolic arrays are derived for the so-called partition problem using the dynamic programming method. The recurrence formulation associated with this method involves some peculiar non-uniformities which cause existing synthesis methods to break down. It is shown that such difficulties can be overcome with the aid of domain extension and control signals so that a system of uniform recurrence equations can be produced. Any NP problem that can be transformed or reduced to partition automatically acquires a systolic implementation, albeit after a polynomial time transformation of the data. In addition, the range of recurrences for which existing regular array synthesis techniques can be applied has been improved.
ISSN:0020-0190
1872-6119
DOI:10.1016/0020-0190(93)90189-G