Publication:
High-Speed Hardware Partition Generation

Loading...
Thumbnail Image
Authors
Butler, Jon T.
Sasao, Tsutomu
Subjects
Design
Algorithms
Performance
Reconfigurable computer
set partition
integer partition
index to partition generator
combinatorial objects
partition tree
partition diagram
Advisors
Date of Issue
2014-12
Date
Publisher
Language
Abstract
We demonstrate circuits that generate set and integer partitions on a set S of n objects at a rate of one per clock. Partitions are ways to group elements of a set together and have been extensively studied by researchers in algorithm design and theory. We offer two versions of a hardware set partition generator. In the first, partitions are produced in lexicographical order in response to successive clock pulses. In the second, an index input determines the set partition produced. Such circuits are useful in the hardware implementation of the optimum distribution of tasks to processors.We show circuits for integer partitions as well. Our circuits are combinational. For large n, they can have a large delay. However, one can easily pipeline them to produce one partition per clock period. We show (1) analytical and (2) experimental time/complexity results that quantify the efficiency of our designs. For example, our results show that a hardware set partition generator running on a 100MHz FPGA produces partitions at a rate that is approximately 10 times the rate of a software implementation on a processor running at 2.26GHz.
Type
Article
Description
The article of record as published may be located at http://dx.doi.org/ 10.1145/2629472
Series/Report No
Department
Electrical and Computer Engineering
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
ACM Transactions on Reconfigurable Technology and Systems, Vol. 7, No. 4, Article 28, Publication date: December 2014. DOI: http://dx.doi.org/10.1145/2629472
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Collections