|
|
 |
| |
|
|
|
Generating a Shortest B-Chain using Multi-GPUs |
|
|
|
PP: 745-750 |
|
|
doi:10.18576/isl/110307
|
|
|
|
Author(s) |
|
|
|
Hatem M. Bahig,
Dieaa I. Nassr,
|
|
|
|
Abstract |
|
|
| Let B be a finite set of binary operations over the set of natural numbers N. A B-chain for a natural number n, denoted by BC(n), is a sequence of numbers 1 = c0,c1,...,cl = n such that for each i > 0,ci = cj ◦ck, where 0 ≤ j,k ≤ i−1 and ◦ is an operation of B. Generating a shortest B-chain for n plays an important role in increasing the performance of some cryptosystems and protocols. This paper has two purposes. The first is to propose a generic algorithm to generate a shortest B-chain using a single CPU and a single GPU for any B. The second is to propose two strategies to improve the generation of a shortest B-chain using two (or more) GPUs. Using two GPUs, the experimental study shows that the first strategy improves the performance by about 20%, while the second strategy improves the performance by about 30 ∼ 35% in case of B = {+}. It is also possible to combine both strategies when we have at least four GPUs.
|
|
|
|
|
|
|
|
