### 1 stable release

Uses old Rust 2015

1.0.1 | Apr 22, 2019 |
---|

#**1281** in Algorithms

**MIT**license

1MB

170 lines

# 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 switchesallow for a simple implementation of complete`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`

K_ndo not exceed, and achieves`columns`

floor(n/2)`graph without connecting any wires between any three adjacent blocks, thus preserving locality in connections.`

K_n

- 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

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.`floor``(`n`/``2``)`

## 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

images is present in the `.`svg

directory. You can execute it as follows:`examples/`

`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.