Show simple item record

dc.contributor.authorSasao, T.
dc.contributor.authorButler, Jon T.
dc.dateMay 21-22, 2012
dc.date.accessioned2013-09-03T22:33:04Z
dc.date.available2013-09-03T22:33:04Z
dc.date.issued2012-05
dc.identifier.citation19th Reconfigurable Architectures Workshop, May 21-22, 2012, Shanghai, China.
dc.identifier.urihttp://hdl.handle.net/10945/35852
dc.description19th Reconfigurable Architectures Workshop, May 21-22, 2012, Shanghai, China.en_US
dc.description.abstractWe demonstrate a circuit that generates a permutation in response to an index. Since there are n! n-element permutations, the index ranges from 0 to n! à ¢ 1. Such a circuit is needed in the hardware implementation of unique-permutation hash functions to specify how parallel machines interact through a shared memory. Such a circuit is also needed in cryptographic applications. The circuit is based on the factorial number system. Here, each non-negative integer is uniquely represented as snà ¢ 1(nà ¢ 1)! +snà ¢ 2(nà ¢ 2)! +...+s11!, where 1 à ¢ à ¤ si à ¢ à ¤ i. That is, the permutation is produced by generating the digits si in the factorial number system representation of the index. The circuit is combinational and is easily pipelined to produce one permutation per clock period. We give experimental results that show the efà ¯à ¬ ciency of our designs. For example. we show that the rate of production of permutations on the SRC-6 reconà ¯à ¬ gurable computer is 1,820 times faster than a program on a conventional microprocessor in the case of 10-element permutations. We also show an efà ¯à ¬ cient reconà ¯à ¬ gurable computer implementation that produces random permutations using the Knuth shufà ¯à ¬ e algorithm. This is useful in Monte Carlo simulations. For both circuits, the complexity is O(n2), and the delay is O(n).en_US
dc.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.en_US
dc.titleHardware index to permutation converteren_US
dc.typeArticleen_US
dc.contributor.departmentDepartment of Electrical and Computer Engineering
dc.subject.authorreconfigurable computeren_US
dc.subject.authorindex to permutation generatoren_US
dc.subject.authorrandom permutation generatoren_US
dc.subject.authorcombinatorial objectsen_US
dc.subject.authorfactorial number systemen_US
dc.subject.authorKnuth shuffleen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record