High-Speed Hardware Partition Generation
Butler, Jon T.
MetadataShow full item record
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.
The article of record as published may be located at http://dx.doi.org/ 10.1145/2629472
RightsThis 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.
Showing items related by title, author, creator and subject.
Hardware Index to Set Partition Converter Butler, Jon T.; Sasao. Tsutomu (Springer-Verlag, 2013);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 ...
Crafting a Usable Microkernel, Processor, and I/O System with Strict and Provable Information Flow Security Tiwari, Mohit; Oberg, Jason K.; Li, Xun; Valamehr, Jonathan; Levin, Timothy; Hardekopf, Ben; Kastner, Ryan; Chong, Frederic T.; Sherwood, Timothy (2011);High assurance systems used in avionics, medical implants, and cryptographic devices often rely on a small trusted base of hardware and software to manage the rest of the system. Crafting the core of such a system in a way ...
Extended Abstract: Trustworthy System Security through 3-D Integrated Hardware Huffmire, Ted; Valamehr, Jonathan; Sherwood, Timothy; Kastner, Ryan; Levin, Timothy; Nguyen, Thuy D.; Irvine, Cynthia E. (IEEE International Workshop on Hardware-Oriented Security and Trust, 2008-06-01);While hardware resources in the form of both transistors and full microprocessor cores are now abundant, economic factors prevent specialized hardware mechanisms required for secure processing from being integrated into ...