仲裁器

仲裁器是数字设计中常见的模块,应用广泛。仲裁器往往和其他组件使用在一起以组成仲裁电路。如仲裁器+编码器可以实现优先编码器。 逻辑图 下面是一位仲裁器的逻辑图k 只有当输入为1且当前仍未找到1时输出为真,如果之前已经找到1,输出信号会通知其他阶段已经找到了1。 仲裁器可以实现为迭代电路,我们可以先设计1位逻辑电路,然后逐级连接组成多位的仲裁器: 也可以使用超前进位的方式实现: verilog 实现 我们可以使用 casex 语句很方便的实现仲裁器: module Arb_4b(r, g); input [3:0] r; output [3:0] g; reg [3:0] g; always @(*) begin casex(r) 4'b0000: g = 4'b0000; 4'bxxx1: g = 4'b0001; 4'bxx10: g = 4'b0010; 4'bx100: g = 4'b0100; 4'b1000: g = 4'b1000; default: g = 4'hx; endcase end endmodule 当我们想要任意宽度的仲裁器时,可以用下面的实现: module Arb(r, g); // LSB 优先级最高 parameter n=8; input [n-1:0] r; output [n-1:0] g; wire [n-1:0] c = {(~r[n-2:0] & c[n-2:0]), 1'b1}; assign g = r & c; endmodule module Arb(r, g); // MSB 优先级最高 input [n-1:0] r; output [n-1:0] g; wire [n-1:0] c = {1'b1, (~r[n-1:1] & c[n-1:1])}; assign g = r & c; endmodule 可编程优先级仲裁器 使用位片式标记法可以编写优先级可编程的仲裁器,这里使用独热码负责指示标记,功能的实现为下面的语句:...

October 13, 2023 · yunlang

RUST: 如何理解字符串,字符串字面量和字符串切片

如何理解String,str与&str 字符串,字符串字面量和字符串切片是初学 rust 最困惑的一点,一部分是因为它的各种用法繁杂,经常使用;另一部分也是因为它们所提供的方法繁多,并且有着令人疑惑的相互转换。虽然常读常新,但还是想写一篇博客,分享之外也可以让自己在困惑时快速找到参考而不用翻阅大量网页。 从内存开始 通过了解字符串在内存中的表示,我们可以最直观的了解到他们的不同之处,考虑下面的代码和他们创建的布局。 let s1 = String::from("Hello"); let s2 = &s1[1..]; let s3 = "Hello"; 他们的内存布局如下 my_name:s1(String) my_name: s2(&str) my_name:s3(&str) [----------------] [–––––––––––] [--------------] +---+---+---+ +–––+–––+ +---+---+ stack frame | • | 6 | 5 | │ • │ 4 │ | • | 4 | +-|-+---+---+ │–+–+–--+ +-|-+---+ | | | | +-------------+ | | | | +-V-+-V-+---+---+---+---+ | heap frame | H | e | l | l | o | | | +---+---+---+---+---+---+ | | | | | preallocated +–-–+–V–+–––+–––+–––+–––+ read-only │ H │ e │ l │ l │ o │ │ memory +–––+–––+–––+–––+–––+–––+ 我们可以发现下面几条事实:...

March 26, 2023 · yunlang

Part1 Uma to Numa

NUMA 深度探索:从UMA到NUMA (翻译及总结) 原文连接:numa-deep-dive-part-1-uma-numa 引言 非一致存储访问(NUMA)是一种在现今多处理器系统中使用的共享内存架构。每个CPU被分配了自己的本地内存,同时可以访问系统中其他CPU的内存。访问本地内存提供了低延时-高带宽的性能。而访问其他CPU的拥有的内存则具有较高的延时和较低的带宽。 现代的应用与操作系统(如ESXi)默认支持NUMA,但为了提供最佳性能,应该考虑在使用NUMA时进行虚拟机配置。不正确的设计可能会导致特定虚拟机,乃至运行在ESXi主机所有虚拟机出现性能不一致或整体性能降低的情况。 这个系列旨在介绍CPU架构,内存子系统以及ESXi系统对CPU及内存的调度策略。让你能够创建一个高性能的平台,为高质量服务和更高的整合率奠定基础。在我们讨论现代计算机架构之前,我们想先复习一下共享内存多处理器的历史,这能让我们更好理解今天为什么要使用NUMA系统。 共享内存多处理器架构的演变 我们往往认为一致内存访问的方式更适合低延迟、高带宽的架构,但现在的计算机系统架构限制了它的实现。我们可以通过回顾历史找到并行计算的关键驱动力来找到原因。 在七十年代引入的关系型数据库使得能够提供多用户并发操作与过度数据生成的系统需求变成了主流。尽管单处理器的性能提升已经很耀眼,但多处理器系统能够更好的满足工作负载。为了提供性价比高的系统,共享内存地址空间成为了研究的重点。 注: 毫无疑问通过共享内存地址可以解决很多成本 早期系统使用交叉开关的方式实现共享内存,然而这种设计的复杂性随着处理器核心的增长而增加,使得基于总线的系统在现今更加流行。是提供更多内存可用性的一种非常有性价比的方式。这提供了更多的内存可用性,同时具有很好的性价比。 但是基于总线的系统也带来了可扩展性问题。最大的问题是带宽的限制,这限制了总线容载处理器的数量。将CPU添加到系统中需要考虑两个主要问题: 当一个CPU被添加时,对每个节点带来的带宽下降。 当添加更多处理器时导致总线长度提升,这会带来更高的延迟 CPU性能的增长,尤其是处理器与内存间的速度剪刀差,在过去和现在都严重制约着多处理器。现今处理器与内存间的速度剪刀差增长态势明显,因此如何高效管理内存系统一直是相关研究的重点。其中的一种策略是通过缓存,但这也带来了很多挑战。这些挑战仍是目前CPU设计者要考虑的重点,比如对缓存结构和替换算法的研究,以避免缓存失效。 缓存监测协议 为每个CPU添加上缓存能够很好的提升性能。一方面更加靠近CPU的内存缩短了CPU的访存时间,另一方面直接访问缓存可以降低总线的带宽负载。 共享内存架构中为每个CPU添加cache的主要挑战在于如何允许内存块的多个备份存在。这被称为缓存一致性问题。 缓存监测协议创建了一个不消耗全部总线资源但能提供正确数据的模型。其中最受欢迎的是写无效协议的引入。CPU在写入本地缓存之前会擦除所有缓存的数据备份,使得随后其他CPU对响应数据在缓存中的访问都会失效,再由最近修改数据的CPU本地缓存中提供相应的数据。 这种模型节省了大量的总线带宽,同时也使得一致内存访问系统在九十年代初期得以出现。我们将在第三部分介绍现代缓存一致性的更多细节。 一致存储访问架构 一致存储访问架构(UMA),又被叫做对称多处理器(SMPs),指的是基于总线的多处理器上,每个处理器的访存行为及访问延迟都是一致的。 在UMA系统中,CPU通过系统总线连接到北桥,北桥包含了内存控制器,所有的与内存相关的访问都需要经过北桥。负责管理I/O设备的I/O控制器也连接到北桥上。因此每个I/O信号也需要经过北桥连接到CPU。 通过添加多个总线和内存通道可以增加北桥的带宽以此消除北桥带来的瓶颈问题。在某些系统中还可以将外部内存控制器添加到北桥上来提高内存带宽,同时增加更多内存支持。但缓存监测协议的广播性质导致UMA的可扩展性受到限制。因此UMA架构无法满足未来的负载需求(现在的高速闪存设备每秒已经要处理成百上千的I/O请求)。 注:越多的I/O访问意味着处理器间的缓存监测协议实现越复杂。 非一致内存访问架构 为了提升共享内存多处理器架构的可扩展性和性能,可以考虑三个关键的点: 非一致内存访问 点到点的内连拓扑 可扩展的缓存一致性解决 1.非一致内存访问 NUMA不再使用内存池而是引入了拓扑属性,根据处理器到内存的路径长度进行分类以避免内存访问延迟和带宽瓶颈的问题。实现NUMA需要对处理器系统和芯片架构进行重设计。九十年代末的SGI超级计算机对NUMA架构的引入使得NUMA开始受到关注。NUMA帮助识别内存的位置,在这种系统中需要确定哪个机箱中存储了特定(需要的)内存。 在世纪初,AMD将NUMA引入到UMA系统统治的商业区域。在2003年AMD Opteron 系列出现,其集成的内存控制器下每个CPU都有属于自己的内存库。每个CPU也有属于自己的内存空间。NUMA的操作系统,例如ESXi能够允许工作负载在多个地址空间上(本地和远程),同时也可以优化内存访问。我们用带着两个CPU的系统来介绍本地内存访问和远程内存访问的区别。 连接在CPU1上的内存被看作是本地内存,而连在其他CPU上的内存(这里是CPU2)被认为是远程内存。远程内存由于需要跨越互联接口连接到内存控制器而具有比本地内存更高的延迟。对于系统架构而言,不同的内存有着不同的位置,造成了“非一致”的访存时间。 2.点对点互联 AMD 在AMD Opteron 微架构中引入了点对点互联的 HyperTransport。而因特尔在2007年放弃了他们的双独立总线架构,在他们的Nehalem架构中开始使用QuickPath Architecture。 Nehalem architecture 被认为是因特尔微架构中的一个重大改变,同时也被认为是真正第一代酷睿系列。目前的Broadwell架构是因特尔酷睿系列的第四代(Intel Xeon E5 v5)。最后一张图片中展示了更多关于因特尔微架构世代的信息。在QuickPath 架构中,内存控制器进入到每个CPU核中,同时在系统中引入了点对点的快速互联路径(QPI)作为CPU在系统中的数据连接。 Nehalem 微架构不仅替代了前端总线,还重新组织了服务器处理器的子系统,使之模块化。这种模块化设计被叫做“Uncore”,同时创建了对缓存和互联速度的设计的构建库。移除前端总线也改善了带宽的可扩展性问题,但当内存容量过大时也需要考虑处理器核间的传输带宽问题。 集成内存控制器和QuickPath 互联都是Uncore的一部分,可以通过模型特定寄存器(MSR)进行访问。它们连接到MSR上,提供了处理器核间内部通信的功能。Uncore的模块化还可以为因特尔提供不同的QPI速度,在目前(2016)因特尔的Broadwell-EP 微架构提供了6.4GT/s,8.0GT/s和9.6GT/s的速度。在CPU之间提供了理论最大带宽为25.6GB/s,,32GB/s和38.4GB/s。为了对比,最新前端总线提供了1.6Gt/s和12.8GB/s的平台带宽。 在推出Sandy Bridge处理器时,英特尔将Uncore重新命名为System Agent,但是Uncore这个术语仍然在当前的文档中使用。在第二部分中,您可以了解更多关于QuickPath和Uncore的信息。 可扩展的缓存一致性 处理器核到L3 cache间提供了一条由上百条线组成的私有通道。这种情况下缩小纳米制造工艺的同时增加处理器核数量需要复杂的设计工作,因此这种架构可扩展性很差。为了增强扩展性,Sandy Bridge 架构通过将L3 cache 移除Uncore 部分并引入可扩展的环形芯片互联架构来增强了可扩展性。依靠此,因特尔可以将L3 cache 以切片的方式进行分区和分发来提供更高的带宽和更高的关联性。每个切片提供了2....

March 13, 2023 · yunlang

计算机体系结构-CPU性能提升简述

前言 随着半导体工艺的升级和芯片技术的发展,为了充分提升CPU的性能出现了各种各样的方式,提升工艺能够极大提升CPU性能,但随着摩尔定律的逐渐失效,优化CPU结构成为了提升CPU性能中越来越重要的一部分。 局部性原理 在CPU频率不断提升的情况下,和CPU进行频繁数据交换的内存速度却提升不够。在这种情况下,CPU直接通过内存进行数据交换时,由于需要等待内存的回应,往往会降低CPU的性能。通过在CPU和内存中间插入Cache作为缓存,能够一定程度上弥补这个问题。 Cache的实现原理 Cache利用空间局部性和时间局部性原理,通过在内存和CPU中间插入一块速度更快的存储器,进而CPU可以先尝试和Cache进行交互,减少CPU访问内存的次数,进而提高系统的整体性能。当Cache中不存在相应数据时,我们会将存储器中的数据和相邻的数据“搬运”到Cache中,这样只需一次访问内存我们可以减少n次内存的访问。 多级Cache 如果都用最先进的工艺实现一个Cache,价格和功耗都是我们无法接受的(当Cache过大时,会由于复杂逻辑产生大的功耗)。因此我们采用多级Cache的方案,不同Cache满足不同需求,如Icache和Dcache代表的L1cache独立于每个Core,L2cache可能在由几个Core进行共用,L3cache可能是整个CPU共用一份。 L1cache分解成Icache和Dcache由于流水线的存在。 无Cache Cache虽好,但并不是所有的处理器都提供了Cache,原因主要有三点: Cache会增加功耗和成本,占用过大的芯片面积和发热了。 一些处理器本身工作频率不高,没有需要Cache解决的带宽问题。 Cache无法保证实时性,缓存命中和未命中需要不同的CPU处理时间,无法满足实时控制场景的需要。 流水线 CPU工作的执行单调而乏味,正如流水线上的工人一样,因此我们也可以通过流水线的方式提升CPU的处理速度。 流水线的原理 流水线通过将一个任务分成多个部分,利用类似并行的处理方式提高了模块的利用率,提升了吞吐量。 想象一个拧螺丝的工作需要4步,每一步需要2s中,那我们从开始到最后完成任务需要8s,也就是说这个时候我们8s可以生产一个产品,但无论我们执行那一步,其他的三步(材料+设备)都是空闲的,因此我们可以通过流水线的方式进行全速前进,这样在全速前进下我们2s就可以生产一个产品(虽然第一个产品生产完成其实也需要8s等待)。 流水线并不是越深越好 首先流水线的分级需要插入寄存器;流水线间如果出现依赖可能还需要增加逻辑进行判断;同时一旦发生了跳转,我们需要丢弃掉前面所有的预取指令。 更多情况下,我们的流水线需要在性能和功耗间做一个平衡。 乱序执行 不同指令间的执行在流水线中可能存在冒险,这种情况下我们可能需要停顿流水线或添加更多逻辑,而还有一种方式就是通过乱序执行,让数据相关的指令不在一起执行,从而根本上避免了冒险的产生。 SISD和SIMD 我们学习过的大多数指令都是SISD(Single Instruction Single Data),这种数据操作会通过一个指令完成一次数据的运算。而SIMD(Single Instruction Multiple Data)可以完成单指令多数据的操作,一次性读取所有的操作数并进行运算。 为什么要有SIMD 数据密集型计算的大规模出现:图像、视频、音频等数据的处理需求催生了SIMD类型指令的出现。如果说之前处理一帧数据需要无数条SISD的指令,那么可能只需要一条SIMD指令,极大提升了这类处理需求的指令效率。 单发射与多发射 多发射可以在一个时钟周期执行多条指令,这是由于处理器内部多个执行单元的存在(又增加了处理器核的面积和逻辑复杂性)。让我们的处理器可以达到指令级的并行。 静态多发射 静态多发射依赖于编译阶段对可以并行的指令打包,合并成一个长指令,这种实现实现又叫做VLIW(Very long Instruction Wrod),这种实现简单,所需硬件也简单,但由于指令集的兼容问题,这种实现并不能完全被主流处理器支持。 动态多发射 动态多发射在硬件上完成了指令的并行话操作,实现这种方式的处理器又被叫做超标量处理器(SuperScalar)。需要在处理器硬件上实现增加很多逻辑。 EPIC EPIC结合了VILW和SuperScaler的优点,通过在指令中显式提供bit位表达两条指令间有没有相关性,简化了硬件处理两条指令相关的逻辑。 多核 提升芯片面积(如多发射或其他类似的设计增加)在提升CPU性能的同时也带来了更高的功耗,更昂贵的成本。因此对单核的提升出现了一个瓶颈:无法在提升性能的同时降低功耗(相同工艺)。针对于此,多核的时代来临了。 多核处理器能够让多个任务级做到真正并行,而单核处理器只能称之为并发,现代计算机一般都是多个任务同时运行,在这种情况下多核的优势开始显现出来。 片上多核互联 正如在单核流水线和多发射中存在的冲突问题,多核处理器也不能每个核心单独存在,需要进行互联通信。CPU的通信经历了星型连接,总线连接,交叉开关(Crossbar)连接,到达RingBus阶段。RingBus结合总线型和开关型的优点,在成本功耗与通信效率间达到了平衡。但当处理器核心进一步增多时,RingBus的延迟又成为了新的瓶颈。因此面向众核处理器领域又出现了新的片上互联技术:片上网络(Net On Chip, Noc)。 大小核 当工作任务均匀分配到每个核心,并且实现大的负载时,多核处理器的性能得到了充分的发挥。但当工作任务不是很多时,往往会造成处理器中某些核心的空转,白白浪费了电费。为了解决这个问题,不同的厂商都提出了他们的大小核架构方案。可以通过操作系统的调度实现处理器的均匀负载,针对不同的人物,可以使用不同的核心处理问题。 不同厂商的实现不同,比如ARM的big.LITTLE架构中小核心的存在就是为了低功耗,而Intel的E-Core则提供了多线程处理能力,提供的更多是“能效”方面的提升。 超线程(Hyper-Threading) 在主流的X86处理器中,主流CPU都提供了超线程技术,通过增加一定的控制逻辑电路将一个物理处理器当作两个逻辑处理器使用,更大限度提升CPU的资源利用率。 实现原理 通过增加控制逻辑电路,保存各个线程的状态,使不同线程共享一个核心的资源,通过进行上下文切换进行线程转移。 在超线程处理器上这种线程切换可能只需要一个时钟周期,而对于一般处理器的线程切换可能需要上万个时钟周期。...

December 19, 2022 · yunlang

新硬盘挂载后发现 df 查询大小和实际大小不一致--Linux的保留空间

前言 在 Linux 上安装一块新硬盘后,发现硬盘大小和挂载后查询到的大小不一致,大概差了 5% 左右,一种可能就是硬盘分区是留下的保留空间造成的。 细节 mkfs.ext4 的man page提供了一部分的解释。 Specify the percentage of the filesystem blocks reserved for the super-user. This avoids fragmentation, and allows root-owned daemons, such as syslogd(8), to continue to function correctly after non-privileged processes are prevented from writing to the filesystem. The default percentage is 5%. 简单来说,ext文件系统为了保证在硬盘百分百利用下还能够写入 root 用户的关键日志等信息,默认预留了5%的磁盘空间。 但我们可以发现,这部分空间很多时候是不需要预留的,尤其是在大的磁盘分区下(例如NAS),可能会导致大量空间的浪费。 解决 针对这个问题,也已经有了解决方案。可以通过tune2fs命令查看保留空间大小和设置保留空间。 tune2fs -l /dev/sde1 | egrep "Block size:|Reserved block count" # Reserved block count: 36628312 # Block size: 4096 # set the reserved space 1% tune2fs -m 1 /dev/sde1 Reference Decrease Reserve Space...

December 8, 2022 · yunlang