xbar

本算法是对在会议论文 "A locality preserving one-sided binary tree - crossbar switch wiring design algorithm" 中描述的算法的 Rust 实现，该论文发表在 2015年第49届信息科学和系统年会（CISS）。

单侧交叉开关 可以简单地实现完全的 K_n 图。然而，设计这些电路是一个繁琐的过程，可以自动化。我们提出了一种算法，允许设计自动化的单侧二叉树-交叉开关，这些开关 不超过 floor(n/2) 列，并且在不连接任何三个相邻块之间的任何电线的情况下实现 K_n 图，从而在连接中保持局部性。

• 会议演示文稿的幻灯片提供如下：这里.
• 包含伪代码和数学证明的论文提供如下：这里.

我之前已经用 Java 实现了此算法。 原始论文只是简单地 证明 输出可以适应 floor(n/2) 列，但没有提供将连接 '打包' 到那么多列的方法。在 Java 代码中，处理打包的部分相当混乱，不适合基于迭代器的实现。我花了一些时间研究如何有效地为这次实现进行打包，并设法将其简化为非常简单而优雅的数学表达式。

这能做什么？

这样的算法过去在电路交换中很有用。坦白说，我认为这个库在2019年及以后不会有人使用。

用法

简单示例

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);
    }
}

生成以下输出

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 输出

在 examples/ 目录中有一个更复杂的示例，它生成 .svg 图像。您可以按如下方式执行它

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

参考

萨欣，德维姆。 "一种局部保真单侧二叉树 - 横杆开关布线设计算法。" 信息科学和系统（CISS），2015年第49届年会。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}
}

许可证

MIT。