Introduction
Sorting networks represent a specialized class of hardware architectures designed to sort a fixed number of inputs through a sequence of "compare-exchange" (CMPX) operations. Unlike software-based sorting algorithms, these networks possess a fixed topology, making them highly efficient for high-speed hardware implementation. However, the design of optimal sorting networks is a notoriously difficult combinatorial problem. The search space for these networks is astronomically large, and verifying the validity of a network—ensuring it sorts all possible input permutations—is computationally expensive, requiring $2^N$ tests for a network of width $N$.
In their 1994 paper, "Learning Sorting Networks By Grammars," Thomas E. Kammeyer and Richard K. Belew propose a novel approach to this challenge by combining evolutionary computing with formal grammars. Instead of attempting to evolve a raw list of operations, the authors utilize genetic algorithms (GA) to evolve the underlying rules that generate these networks.
Methodology: Evolving Grammars
The core innovation of this research is the use of a grammar-based representation within a genetic algorithm. In this framework, the GA does not manipulate individual CMPX operations directly. Instead, it "breeds" grammars consisting of:
- Terminals: Specific, predefined comparison sequences.
- Non-terminals: Recursive rules that dictate how smaller networks are combined to form larger ones.
This approach provides a powerful inductive bias. By evolving grammars, the GA is forced to explore recursive, self-similar structures—patterns that characterize efficient human-designed algorithms like MergeSort. Furthermore, a single evolved grammar can generate an entire family of networks for varying input sizes (e.g., $N=4, 8, 16...$), allowing for a level of abstraction and compression that raw representation lacks.
Verification and Merging Networks
To manage the computational cost of evaluation, the authors focused their evolutionary search on Merging Networks (MNets). While general sorting networks (SNets) require $2^N$ sequences for verification, MNets—which merge two previously sorted lists—can be fully verified in polynomial time using $(N/2 + 1)^2$ input sequences. This efficiency allowed the GA to evaluate the fitness of many more candidates than would have been possible with general sorters.
Hardware Efficiency and Log-Sequential Design
The research emphasizes properties that are critical for physical hardware implementation:
- Log-Sequential Sorters: These are networks designed such that the output can be fed back into the input $\log_2 N$ times to achieve a fully sorted result. This allows for a significantly smaller hardware footprint.
- Log Spectrum: A design with a small number of distinct comparison distances (wire lengths), which simplifies physical chip layout.
- Log Delay: High levels of parallelism that minimize the time required for data to pass through the network.
Key Results and Discovery
The GA successfully discovered a novel network family that is structurally distinct from known designs. Key findings include:
- Minimalist Representation: The discovered grammar requires only two simple rules to generate valid networks for any input size $N = 2^i$.
- Performance: The evolved architecture appears to be a log-sequential sorter that maintains both log spectrum and log delay properties.
- Structural Complexity: Interestingly, the evolved network was found to embed the well-known Canfield-Williamson network of half its size multiple times in an overlapping fashion. This suggests a highly efficient recursive structure that may not be immediately intuitive to human designers.
Conclusion and Future Directions
Kammeyer and Belew demonstrated that grammar-based evolution is a viable method for discovering complex, hardware-friendly circuit architectures. While the search space for merging networks remains difficult to navigate, the ability of a GA to find a two-rule grammar for a scalable sorter highlights the potential of this approach. Future work suggests that these techniques could be extended beyond sorting to discover other types of specialized hardware circuits, leveraging the power of recursive grammars to find efficient, scalable designs.
Summary updated