Hardware Index to Set Partition Converter
Loading...
Authors
Butler, Jon T.
Sasao, Tsutomu
Subjects
Advisors
Date of Issue
2013
Date
2013
Publisher
Springer-Verlag
Language
en_US
Abstract
We demonstrate, for the first time, high-speed circuits that generate partitions on a set S of n objects. We offer two versions. 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 needed in the hardware implemen- tation of the optimum distribution of tasks to processors. Our circuits are combinational. For large n, they can have large delay. However, one can easily pipeline them to produce one set partition per clock period. We show 1) analytical and 2) experimental time/complexity results that quantify the efficiency of our designs. Our results show that a hardware partition generator running on a 100 MHz FPGA produces partitions at a rate that is approximately 10 times the rate of a software implemen- tation on a processor running at 2.26 GHz.
Type
Preprint
Description
Series/Report No
Department
Organization
Naval Postgraduate School
Identifiers
NPS Report Number
Sponsors
Funder
Format
13 p.
Citation
Butler, Jon T., and Tsutomu Sasao. "Hardware Index to Set Partition Converter." 2013. Preprint.
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.