## Abstract

We propose two new instructions, swperm and sieve, that can be used to efficiently complete an arbitrary bit-level permutation of an n-bit word with or without repetitions. Permutations with repetitions are rearrangements of an ordered set in which elements may replace other elements in the set; such permutations are useful in cryptographic algorithms. On a 4-way superscalar processor; an arbitrary 64-bit permutation with repetitions of 1-bit subwords can be completed in 11 instructions and only 4 cycles using the two proposed instructions. For subwords of size 4 bits or greater, an arbitrary permutation with repetitions of a 64-bit register can be completed in a single cycle using a single swperm instruction. This improves upon previous permutation instruction proposals that require log(r) sequential instructions to permute r subwords of a 64-bit word without repetitions. Our method requires fewer instructions to permute 4-bit or larger subwords packed in a 64-bit register and fewer execution cycles for 1-bit subwords on wide superscalar processors.

Original language | English (US) |
---|---|

Pages | 453-461 |

Number of pages | 9 |

State | Published - 2001 |

Event | IEEE International Conference on: Computer Design: VLSI in Computers and Processors (ICCD 2001) - Austin, TX, United States Duration: Sep 23 2001 → Sep 26 2001 |

### Other

Other | IEEE International Conference on: Computer Design: VLSI in Computers and Processors (ICCD 2001) |
---|---|

Country/Territory | United States |

City | Austin, TX |

Period | 9/23/01 → 9/26/01 |

## All Science Journal Classification (ASJC) codes

- Hardware and Architecture
- Electrical and Electronic Engineering