Combination generators with optimal cache utilization and communication free parallel execution

Xi He, Max A. Little · 2025

Read Combination generators with optimal cache utilization and communication free parallel execution by Xi He, Max A. Little (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-03980.txt.

Introduction

Xi He and co-authors present a functional design for generators that list combinations, in a 2025 paper. Programs that solve hard search problems often begin by generating every candidate answer, then filter the list down. When few candidates get filtered out, the speed of the whole program rests on the generator itself.

The team argues that generator design should respect the hardware it runs on, not just formal correctness. Their design, built on convolution, aims for two things at once: smooth use of the memory cache, and parallel runs that need no chatter between processors. The paper develops the method within a program-transformation approach, where proofs and code grow together. It speaks to builders of optimization software who need raw generation speed on modern machines, graphics chips included.

Catalog record

CREATORXi He, Max A. Little
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE193 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-03980

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Combination generators with optimal cache utilization and communication free parallel execution Xi He, Max A. Little Abstract We introduce an efficient and elegant combination generator for producing all combinations of size less than or equal to K K , designed for exhaustive generation and combinatorial optimization tasks. This generator can be implemented to achieve what we define as optimal efficiency : constant amortized time , optimal cache utilization , embarrassingly parallel execution , and a recursive structure compatible with pruning-based search. These properties are difficult to satisfy simultaneously in existing generators. For example, classical Gray code or lexicographic generators are typically list-based and sequentially defined, making them difficult to vectorize, inefficient in cache usage, and inherently hard to parallelize. Generators based on unranking methods, while easy to parallelize, are non-recursive. These limitations reduce their applicability in our target applications, where both computational efficiency and recursion are crucial. Our generator overcomes these challenges through three key features: a recursively blocked array layout enabling full vectorization, a divide-and-conquer structure supporting embarrassingly parallel execution, and automatic memory management handled internally by the algorithm. We adapt Bird’s algebra of programming -style calculation to derive our algorithms, a formalism for developing correct-by-construction programs from specifications. As a result, all generators in this paper are first formulated in their clearest specification, and efficient definitions are derived constructively through equational reasoning, resulting in concise and elegant divide-and-conquer definitions. Beyond presenting a combination generator, we extend our approach to construct generators for K K -permutations, nested combinations of combinations, and nested permutation-combination structures. To the best of our knowledge, the literature has not previously reported generators for these nested structures. We also develop sequential variants that produce configurations in Gray code-compatible orders—such as the revolving door ordering—which are particularly useful for constructing nested generators. 1 Introduction Combinations and permutations are among the simplest, yet most fundamental and important, combinatorial objects. Knuth 2005 wrote “Even the apparently lowly topic of combination generation turns out to be surprisingly rich,…. I strongly believe in building up a firm foundation.” Numerous algorithms have been developed for generating combinations. Perhaps the most well-known is the revolving door algorithm , a term coined by Nijenhuis and Wilf 1978 though the method was originally invented by Tang and Liu 1973 . Bitner et al. 1976 later proposed a loopless 1 1 1 A loopless algorithm is one in which, in the worst case, only a small number of operations (or bounded by a constant) are required between successive confgurations, this concept was first introduced by Ehrlich 1973 . version of the algorithm. The revolving door algorithm is an example of a minimal-change algorithm , where each newly generated combination differs only slightly from the previous one. A more restrictive class of Gray code algorithms is known as adjacent-change algorithms , in which successive bitstrings (representing combinations) differ by a single interchange of adjacent bits. Knuth 2011 refers to such algorithms as perfect generators . It has been proven by Ruskey 1984 and Eades et al. 1984 that adjacent-change algorithms do not exist in general for combination generation. Most prior applications of combinatorial generation (CG) have focused on designing generators that produce combinatorial configurations in a specific order, such as Gray code or lexicographic order. The two algorithms— ranking and unranking —associated with these generators have also been widely studied. Ranking algorithms are of interest because they provide perfect hash functions for combinatorial objects, making them useful for cryptographic key generation and hardware/software testing. Unranking algorithms allow for random access to combinatorial objects and facilitate parallel generation. Also, Gray code generators are themselves highly efficient and have therefore been widely used in exhaustive search tasks. A natural connection exists between CG and combinatorial optimization (CO)—the problem of finding an optimal configuration from a finite set with respect to a given objective—by exhaustively evaluating each configuration’s objective value and selecting the best one. However, this connection between CG and optimization is much more nuanced than simple brute-force enumeration. Within the constructive programming community Bird and De Moor 1996 ; Bird and Gibbons 2020 , it has long been recognized that efficient CG can be leveraged to derive efficient CO algorithms. Conversely, Merino and Mütze 2024 recently demonstrated the reverse: if a CO problem over a set X can be solved efficiently, then one can often derive an efficient algorithm for generating the elements of X . In this paper, we focus on designing K -combination/permutation generators (i.e., generators for all combinations or permutations of size less than or equal to K ), along with several related extensions—nested combination and permutation generators—for use in CO and exhaustive enumeration tasks. Many fundamental optimization problems are tied to these combinatorial structures. For instance, the knapsack problem ( De Moor 1995 ) , the K -subset sum ( Parque 2021 ) , the K -medoids problems ( He and Little 2024 ) are all related to K -combinations. The optimal rule list problem ( Angelino et al. 2018 ) is closely linked to K -permutations. Furthermore, neural networks with ReLU or maxout activations ( He et al. 2025 ) and decision trees ( He and Little 2025 ) involve nested combinations and permutations. Additionally, the problem of enumerating cells in a hyperplane arrangement ( Avis and Fukuda 1996 ; Rada and Cerny 2018 ) is a fundamental exhaustive generation task in combinatorial geometry. This exhaustive generation process has practical applications: integer quadratic programming problems ( Ferrez et al. 2005 ) and 0-1 loss linear classification problem He and Little 2023 can be solved exactly through exhaustive cell enumeration. The combination generator proposed in this paper aligns precisely with the geometric description of the cell enumeration method presented by ( Gerstner and Holtz 2006 ) , potentially yielding a much faster alternative to linear programming-based approaches such as those of ( Avis and Fukuda 1996 ; Rada and Cerny 2018 ) . To achieve optimal efficiency for CO and exhaustive generation tasks, we require the generator to satisfy the following criteria: no further asymptotic improvement is possible , optimal cache utilization , inherent embarrassingly parallelism , and compatibility with the recursive thinning method 2 2 2 A commonly used method in combinatorial optimization involves a program that eliminates partial configurations before extending them to complete ones, which is applicable only when configurations are generated recursively. . We believe that combinatorial generators designed with four key factors— generation efficiency , recursiveness , parallelizability , and simplicity —can satisfy the above criteria. Below, we provide justifications for this claim and explain why existing methods often fail to meet these requirements. • Generation efficiency : First, most combinatorial structures have configuration spaces that grow exponentially (or worse) with input size. Consequently, any generator for such objects inherently has exponential (or worse) complexity. As Ruskey 2003 noted, an ideal combinatorial generator should have constant amortized time—that is, generating each configuration should take a constant amount of time on average, regardless of the input size. Second, algorithmic structure should be compatible with modern hardware. Array-based, fully vectorized implementations make better use of multi-level caches and GPUs. In contrast, pointer-based structures like linked lists suffer from poor cache performance and are harder to parallelize. • Recursiveness : Recursive

Read the complete text