package hardcaml_circuits

  1. Overview
  2. Docs
package hardcaml_circuits
Legend:
Library
Module
Module type
Parameter
Class
Class type

Sorting networks.

A sorting network arranges a fixed configuration of compare-and-swaps to sort data. The static nature of the network means they can be easily implemented in hardware.

This module implements Bitonic_sort and Odd_even_merge_sort networks.

The network construction abstracts over the actual data to be sorted and the compare-and-swap implementation, allowing various configurations:

  • sort lists of integers
  • Bits or Signals combinatorial networks
  • pipelined
  • configure the sort's direction (invert the compare operation)
  • sort arbirary data according to some key

An excellent resource explaining the complexity and correctness of these algorithms is:

http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/indexen.htm

The algorithms are analysed using the 0-1 principle which states that a network that sorts any sequence of 0s and 1s also sorts arbitrary data.

module Config : sig ... end
module Min_or_max : sig ... end
module Min_max : sig ... end
type 'a compare_and_swap = 'a -> 'a -> 'a Min_max.t
val create : Config.t -> 'a compare_and_swap -> 'a list -> 'a list
OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct