Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 International Journal of Electronics and Telecommunications

1 2025

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: parallel combinatorial algorithms

Sortuj według:

Ogranicz wyniki do:

A new algorithm for generating integer partitions and its parallel implementations on CPU and FPGA

Nałęcz Marek, Mazurek Gustaw

International Journal of Electronics and Telecommunications

2025

Vol. 71, No. 4

In this paper, the long-known bit representation of integer partitions was used in a novel way to develop an algorithm for generating the next partition of an integer n. This algorithm is both loopless and conditionless (and therefore has strictly constant execution time). These features lead to an efficient and highly scalable parallel implementation on a modern multi-core CPU processor or a modern FPGA chip. In the CPU case, just 30 processor clock cycles are required to generate the next partition when n < 128. In the latter case, a single one of the parallel instances uses only 1,595 look-up tables and 962 registers for n < 128. It can produce the next partition in just 6 clock cycles. Even cost-effective FPGAs can hold a few dozen such instances.