Flattened Butterfly 扁平蝶形拓扑

news/2024/5/28 4:09:59/
  • Flattened Butterfly 扁平蝶形拓扑
    • 1. 传统蝶形网络 Butterfly Topology
    • 2. 扁平蝶形拓扑 Flattened Butterfly
    • 3.On-Chip Flattened Butterfly 扁平蝶形拓扑应用于片上网络

Flattened Butterfly 扁平蝶形拓扑

扁平蝶形拓扑是一种经济高效的拓扑,适用于高基数路由器。扁平蝶形是通过组合(或扁平化)传统蝶形拓扑每行中的路由器而得到的一种拓扑,同时保留路由器间的连接。

1. Butterfly Topology 传统蝶形网络

在这里插入图片描述

传统蝶形网络可以描述为k-ary n-fly。该网络拥有kn**个终端节点,有**n级**交换节点,每级含**k(n-1)个kxk的交换节点。即k为交换节点的出入度或者度的一半。如上图所示,展示了一个2-ary 3-fly的蝶形网络。

蝶形网络中源节点到目标节点的跳数不会变化,始终是n-1(在系统实现中,终端节点和相邻的交换节点往往集成在一起,故跳数只计算交换网络中的跳数)。在流量均匀分布的情况下蝶形网络的最大通道负载是1,所以网络的最大注入带宽也为1flit/node/cycle。其他不均匀的如从网络一端发送到另一端的流量会增大负载,从而减小最大注入带宽。

蝶形网络的最大缺点就是缺失了路径多样性并缺少对网络局部性的利用。缺失路径多样性使得蝶形网络在非平衡流量模式下性能很差,而缺少局部性的利用在于未利用源节点到目标节点相邻或距离较近的情况下,拓扑进行了绕远。

2. Flattened Butterfly 扁平蝶形拓扑

**扁平蝶形拓扑(Flattened Butterfly)**将同一行中的中间交换节点合并成一个交换节点,从而将非直连拓扑转换为直连拓扑。

在这里插入图片描述

如上图所示,由 4-ary 2-fly 的蝶形网络转换为 4-ary 2-fly 的扁平蝶形网络 以及 由 2-ary 4-fly 的蝶形网络转换为 4-ary 2-fly 的扁平蝶形网络。

图1(a)第一行的路由器R0和R1组合成图1(b)扁平化蝶形拓扑中的单个路由R0’。类似地,图1©的路由器R0、R1、R2和R3被组合成图1(d)的R0’。当一行路由器组合在一起时,完全位于该行本地的通道(例如图 1(a) 中的通道 (R0,R1))将被消除(因为组合而成的路由器的内部可以进行同一行的通信),而其他的所有通道都被保留在扁平蝶形中。例如,图1(a)中的通道(R0,R3)变为图1(b)中的通道(R0’,R1’)。由于扁平蝶形结构中的通道是对称的,因此图 1(b,d) 中的每条线代表一个双向通道(即两个单向通道),而图 1(a,c) 中的每条线代表一个单向通道。

k-ary n-flat是从 k-ary n-fly 蝶形网络衍生而来的扁平蝶形,由N/k(N^(k-1))个(中间路由器的个数),基数为k’=n(k-1)+1(一侧的终端个数再加上中间路由器与其他路由器的连接)的路由器组成,N为网络的大小(一侧的终端节点个数)。

传统蝶形网络中n-1为不同的列,代表不同的dimension,而在扁平蝶形网络中,路由器同样通过n’ = n-1维度的通道连接,对应于蝶形网络中的n-1列路由。每个维度d中,从1到n’,路由器i连接到路由器j:
在这里插入图片描述

例如,在图 1(d) 中,R4’ 在维度 1 中连接到 R5’,在维度 2 中连接到 R6’,在维度 3 中连接到 R0’。图 2 中,扁平蝶形结构中的节点数量 (N ) 被绘制为维数 n’ 和交换机基数 k’ 的函数。该图显示该拓扑仅适用于高基数路由器。可以使用低基数路由器 (k′ < 16) 构建规模非常有限的网络,即使 k′ = 32,也需要许多维度才能扩展到大型网络规模。然而,当 k′ = 61 时,只有三个维度的网络可以扩展到 64K 个节点。
在这里插入图片描述

3. On-Chip Flattened Butterfly 扁平蝶形拓扑应用于片上网络

John Kim, James Balfour, and William J. Dally将扁平蝶形拓扑应用于片上网络。

通过集中在路由器中,扁平蝶形结构显着降低了拓扑的布线复杂性,使其能够更有效地扩展。为了将 64 节点片上网络映射到扁平化蝴蝶拓扑上,折叠了4-ary 3-fly的蝶形网络以生成如图 3(a) 所示的扁平化蝴蝶网络。由此产生的扁平蝴蝶有 2 个维度并使用 radix-10 路由器。每个路由器连接四个处理器节点,因此路由器的集中系数为 4。其余 6 个路由器端口用于路由器间连接:3 个端口用于维度 1 连接,3 个端口用于维度 2 连接连接。路由器的放置如图 3(b) 所示,将拓扑嵌入到平面 VLSI 布局中,每个路由器放置在 4 个处理节点的中间。维度1连接的路由器水平对齐,维度2连接的路由器垂直对齐;因此,行内的路由器是完全连接的,列内的路由器也是完全连接的

在这里插入图片描述

与数据包源和目的地之间的曼哈顿距离相关的线路延迟是了片上网络传输所需的延迟的下限。当使用最小路由时,这个扁平化蝴蝶网络中的处理器仅相隔 2 跳,这比 2-D 网格的跳数有显着改进。扁平蝶形尝试通过减少中间路由器的数量来接近线路延迟界限,这不仅可以降低延迟,还可以降低能耗。然而,扁平化蝶形网络中连接远程路由器的电线必然比网状网络中的电线更长。通过最佳地插入中继器和流水线寄存器来保留通道带宽,同时容忍可能是几个周期的通道遍历时间,可以很容易地减少长导线对性能的不利影响。较长的通道还需要更深的缓冲区大小来覆盖信用往返延迟,以维持完整的吞吐量。

References:
[1] J. Kim, J. Balfour, and W. Dally, “Flattened Butterfly Topology for On-Chip Networks,” in 40th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO 2007), Chicago, IL, USA: IEEE, 2007, pp. 172–182. doi: 10.1109/MICRO.2007.29.
[2] J. Kim, W. J. Dally, and D. Abts, “Flattened Butterfly : A Cost-Efficient Topology for High-Radix Networks,” 2007.


http://www.ppmy.cn/news/1423410.html

相关文章

Simba:Mamba 增强了 U-ShiftGCN,用于视频中的骨骼动作识别

Simba&#xff1a;Mamba 增强了 U-ShiftGCN&#xff0c;用于视频中的骨骼动作识别 摘要IntroductionRelated WorksMethodologyDown-sampling ShiftGCN Encoder Experiments & ResultsDatasets Simba: Mamba augmented U-ShiftGCN for Skeletal Action Recognition in Video…

求交错且分母为阶乘的和(java)

import java.util.*; public class APP1{public static void main(String[] args){double sum0.0;int n0;int flag1;int fm1;Scanner reader new Scanner(System.in);System.out.println("请输入n的值&#xff1a;");nreader.nextInt();for(int i0;i<n;i){fm*i; …

极狐GitLab x LigaAI,AI 时代研发提效新范式

GitLab 是一个全球知名的一体化 DevOps 平台&#xff0c;很多人都通过私有化部署 GitLab 来进行源代码托管。极狐GitLab 是 GitLab 在中国的发行版&#xff0c;专门为中国程序员服务。可以一键式部署极狐GitLab。 近日&#xff0c;极狐GitLab 和 LigaAI 宣布合作&#xff0c;双…

DDD学习

概述 学习一下DDD 什么是DDD DDD是领域驱动设计&#xff08;Domain Driven Design&#xff09;的缩写&#xff0c;是一种软件开发方法论。它强调将业务领域划分为多个紧凑的、自包含的领域&#xff0c;并通过强调领域模型的重要性来建立一个通用的语言和理解。 DDD鼓励开发…

京西商城——前端项目的创建以及前后端联调

创建VUE项目 在jingxi_shop_project文件夹中再创建一个 frontend 文件夹用来存放前端项目 /jingxi_shop_project/backend/jingxi_shop_project....../frontend/jingxi_shop_web......首先要安装 node.js 和 VUE cli&#xff0c;进入到项目目录内创建项目 vue create jingxi_…

2024 年 Web 前端开发趋势

希腊哲学家赫拉克利特认为&#xff0c;变化是生命中唯一不变的东西。这句话适用于我们的个人生活、行业和职业领域。 尤其是前端开发领域&#xff0c;新技术、开发趋势、库和框架不断涌现&#xff0c;变化并不陌生。最近发生的一些事件正在改变开发人员构建网站和 Web 应用的方…

前后端系统开发之——文章管理

原文地址&#xff1a;前后端系统开发之——文章管理 - Pleasure的博客 下面是正文内容&#xff1a; 前言 主要使用的技术&#xff1a;前端使用的是Vue.js&#xff0c;后端使用的是SpringBoot。如不雷同可以直接跳过了。 文章管理是这个系统最主要的一个功能也是最常规的一个功…

202462读书笔记|《一世珍藏的诗歌200首》——你曾经羞赧地向我问起, 是谁最早在此留下足印

202462读书笔记|《一世珍藏的诗歌200首》——你曾经羞赧地向我问起&#xff0c; 是谁最早在此留下足印 《一世珍藏的诗歌200首》作者金宏宇&#xff0c;很多美好的诗&#xff0c;有徐志摩&#xff0c;戴望舒&#xff0c;林徽因&#xff0c;舒婷等的诗精选&#xff0c;很值得一读…

Python分析之3 种空间插值方法

插值是一个非常常见的数学概念,不仅数据科学家使用它,而且各个领域的人们也使用它。然而,在处理地理空间数据时,插值变得更加复杂,因为您需要基于几个通常稀疏的观测值创建代表性网格。 在深入研究地理空间部分之前,让我们简要回顾一下线性插值。 为了演示的目的,我将使…

FebHost:谁可以注册.CA加拿大域名?

在加拿大&#xff0c;互联网域名的注册管理遵循一套独特的规则。特别是对于代表加拿大身份的顶级域名“.ca”&#xff0c;其申请和注册过程涉及一些严格的条件。这些条件确保了只有符合特定标准的个人或实体才能获得这一具有国家象征意义的网络地址。 首先&#xff0c;想要注册…

算法学习笔记Day6——二维数组的花式遍历

引言&#xff1a;一些操作的最佳算法可能不符合我们的直观思路&#xff0c;但是它对计算机来说是有效的&#xff0c;对于我们来说匪夷所思、八竿子打不着的操作可能正好就能够得出符合要求的操作。这其中有很深的数学变换思维&#xff0c;需要勤于思考&#xff0c;多加练习。 …

C++ | Leetcode C++题解之第23题合并K个升序链表

题目: 题解&#xff1a; class Solution {// 21. 合并两个有序链表ListNode *mergeTwoLists(ListNode *list1, ListNode *list2) {auto dummy new ListNode(); // 用哨兵节点简化代码逻辑auto cur dummy; // cur 指向新链表的末尾while (list1 && list2) {if (list1…

深度探索:Secure Hash Algorithm(SHA)全景解析

title: 深度探索&#xff1a;Secure Hash Algorithm&#xff08;SHA&#xff09;全景解析 date: 2024/4/15 18:33:17 updated: 2024/4/15 18:33:17 tags: SHA安全抗碰撞性算法版本实现细节性能优化发展历史应用案例 密码学中的哈希函数 一、哈希函数的定义 哈希函数是一种数…

PDE判断题

PDE判断题 波动方程满足弱极值原理波动方程满足强极值原理强极值原理波动方程结论 一个均匀细杆&#xff0c;从初始时刻开始受到冷却作用&#xff0c;那么一段时间内&#xff0c;杆上的最高温度一定能在两端或者初始时刻取得。一个定义在全平面上的调和函数&#xff0c;如果有下…

Nodejs 第六十四章(SSO单点登录)

单点登录 单点登录&#xff08;Single Sign-On&#xff0c;简称SSO&#xff09;是一种身份认证和访问控制的机制&#xff0c;允许用户使用一组凭据&#xff08;如用户名和密码&#xff09;登录到多个应用程序或系统&#xff0c;而无需为每个应用程序单独提供凭据 SSO的主要优…

算法训练营第25天回溯(分割)

回溯算法&#xff08;分割&#xff09; 131.分割回文串 力扣题目链接(opens new window) 题目 给定一个字符串 s&#xff0c;将 s 分割成一些子串&#xff0c;使每个子串都是回文串。 返回 s 所有可能的分割方案。 示例: 输入: “aab” 输出: [ [“aa”,“b”], [“a”,“…

免费的壁纸api

# 联想壁纸 from enum import Enumimport requestsclass LenovoTopHeadersTypePage(Enum):"""头部页面类型wallpaper 精选wallpaperHot 热门wallpaperRank 排行"""wallpaper wallpaperwallpaperHot wallpaperHotwallpaperRank wallpaperRankc…

【NEUQ1007】C基础-计负均正

C基础-计负均正 描述 从键盘输入任意20个整型数&#xff0c;统计其中的负数个数并求所有正数的平均值。 输入描述 从键盘输入20个整型数&#xff0c;以空格分隔。 输出描述 输出负数的个数和所有正数的平均值&#xff0c;保留两位小数。 示例 输入 1 2 3 4 5 6 7 8 9 …

【python从入门到精通】-- 第五战:函数大总结

&#x1f308; 个人主页&#xff1a;白子寰 &#x1f525; 分类专栏&#xff1a;python从入门到精通&#xff0c;魔法指针&#xff0c;进阶C&#xff0c;C语言&#xff0c;C语言题集&#xff0c;C语言实现游戏&#x1f448; 希望得到您的订阅和支持~ &#x1f4a1; 坚持创作博文…

《八》QSplitter拆分器以及QDockWidget窗口详解

QSplitter简介 QSplitter拆分器允许用户通过拖动子部件之间的边界来控制它们的大小。 单个拆分器可以控制任意数量的小部件。QSplitter的典型用法是创建几个小部件&#xff0c;并使用insertWidget()或addWidget()添加它们。 常用方法 默认情况下&#xff0c;QSplitter会动态…