xbar

Rust implementation of the algorithm described in the conference paper "A locality preserving one-sided binary tree - crossbar switch wiring design algorithm" published in 2015 49th Annual Conference on Information Sciences and Systems (CISS).

One-sided crossbar switches allow for a simple implementation of complete K_n graphs. However, designing these circuits is a cumbersome process and can be automated. We present an algorithm that allows designing automatic one-sided binary tree - crossbar switches which do not exceed floor(n/2) columns, and achieves K_n graph without connecting any wires between any three adjacent blocks, thus preserving locality in connections.

Slides of the conference presentation are provided here.
Paper that contains the pseudocode and mathematical proof is provided here.

I had previously implemented this algorithm in Java. The original paper simply proves that the output can be fit into floor(n/2) columns, but does not provide a way to 'pack' connections into that many columns. In the Java code, the part that handles the packing is quite dirty and was not suitable for iterator-based implementations. I spent some time on how to implement packing efficiently for this implementation and managed to boil down the entire thing into very simple and elegant mathematical expressions.

What can be done with this?

Algorithms like this used to be useful in circuit switching. Frankly, I don't think that this crate will be used by anyone in 2019 and beyond.

Usage

Simple example

extern crate xbar;
use xbar::Crossbar as X;
pub fn main() {
	let n = 5;
	println!("Crossbar for {} terminals has {} rows, \
		formed into {} blocks; and {} columns",
		n, X::rows(n), X::blocks(n), X::columns(n));
	println!("Connections of the crossbar:");
    for con in X::new(n) {
		println!("{:#?}", con);
    }
}

produces the output:

Crossbar for 5 terminals has 20 rows, formed into 4 blocks; and 2 columns
Connections of the crossbar:
Connection {
    start: Position {
        block_idx: 0,
        row_idx: 0,
        abs_idx: 0
    },
    end: Position {
        block_idx: 0,
        row_idx: 1,
        abs_idx: 1
    },
    col_idx: 0
}
...

SVG output

A more sophisticated example that generates .svg images is present in the examples/ directory. You can execute it as follows:

cargo run --example svg_test -- --output test.svg --num_terms 15

Reference

Sahin, Devrim. "A locality preserving one-sided binary tree - crossbar switch wiring design algorithm." Information Sciences and Systems (CISS), 2015 49th Annual Conference on. IEEE, 2015.

Bibtex

@inproceedings{dsahin2015crossbar,
  title={A locality preserving one-sided binary tree - crossbar switch wiring design algorithm},
  author={{\c{S}}ahin, Devrim},
  booktitle={Information Sciences and Systems (CISS), 2015 49th Annual Conference on},
  pages={1--4},
  year={2015},
  organization={IEEE}
}

License

MIT.

kubuzetto/xbar