跳转至

2023

  • 分类于 network
  • 需要 3 分钟阅读时间

Firewall

简介

防火墙是一种网络安全设备，主要是通过硬件和软件的作用于内部和外部网络的环境间产生一种保护的屏障，从而实现对计算机不安全网络因素的阻断。 * 所有流入流出的所有网络通信均要经过此防火墙。 * 功能 * 访问控制、隔离保护 * 组成 * 服务访问政策、验证工具、包过滤和应用网关

功能作用

  • 入侵检测功能
  • 主要有反端口扫描、检测拒绝服务工具、检测CGI/IIS服务器入侵、检测木马或者网络蠕虫攻击、检测缓冲区溢出攻击等功能，
  • 可以极大程度上减少网络威胁因素的入侵，有效阻挡大多数网络安全攻击。
  • 网络地址转换功能(NAT)
  • 分为源地址转换和目的地址转换，即SNAT和DNAT。可以由服务的发起者是谁来区分两者。
  • SNAT: 内部地址要访问公网上的服务时，内部地址会主动发起连接，将内部地址转换成公有ip
    • 修改源ip地址的目的一般都是为了让这个包能再回到自己这里，所以在iptables中，SNAT是在出口，也即POSTROUTING链发挥作用。
    • SNAT主要用于隐藏内部网络结构，避免受到来自外部网络的非法访问和恶意攻击，有效缓解地址空间的短缺问题，
  • DNAT：当内部需要对外提供服务时，外部发起主动连接公有ip的网关，路由器或着防火墙的网关接收到这个连接，然后把连接转换到内部，此过程是由带公有ip的网关代替内部服务来接收外部的连接，然后在内部做地址转换。
    • 修改目的ip地址的原因一般就是为了改变包发送的目的地，让包走出去，而不是留下来，所以在iptables中，DNAT是在入口，也即PREROUTING链中发挥作用，以便让包进入FORWARD表。
    • DNAT主要用于外网主机访问内网主机，以此避免内部网络被攻击。
    • DNAT与端口转发的区别在哪里？
  • 网络操作的审计监控功能
  • 对系统管理的所有操作以及安全信息进行记录，提供有关网络使用情况的统计数据，方便计算机网络管理以进行信息追踪。
  • 强化网络安全服务(类似GFW)
  • 集中化的安全管理，将安全系统装配在防火墙上，在信息访问的途径中就可以实现对网络信息安全的监管。

Linux实现原理

  • Linux系统内核中的安全框架Netfilter，为其他内核模块提供数据包过滤、网络地址转换（NAT）和负载均衡的功能。
  • 常用的iptables和firewalld服务都依赖于Netfilter来过滤数据包，两者自身并不具备防火墙的功能，只是创建并维护规则。
  • 不同之处在于iptables基于“过滤规则链”，firewalld基于zone区域。
  • iptables无守护进程，不能算作真正的服务，firewalld存在守护进程

三表五链 - 三表(应用规则)

  • filter 用于过滤，防火墙，过滤数据包
  • nat 用于网络地址转换、端口转发
  • mangle 用于拆解报文，作出修改，封装报文
  • raw表， 关闭nat表上启用的连接追踪机制，以提高性能。
  • 表规则应用优先级：raw>mangle>nat>filter
  • 每个表中能存在的链如下

三表五链 - 五链(数据包状态/ 过滤规则链)

  • PREROUTING 进入路由之前的数据包
  • INPUT 目的地址为本机的输入数据包
  • FORWARD 目的地址不为本机的包，可以实现转发(需要开启)
  • OUTPUT 源地址为本机的输出数据包
  • POSTROUTING 发送到网卡之前的数据包

Nftables

  • Allows configuration of tables, chains and rules provided by the Linux kernel firewall.
  • Nftables replaces iptables.
  • 解决的iptables的不足
    • 不同协议实现的代码重复
    • Nftables通过增强的通用集和映射基础结构，可以更快地进行数据包分类。
    • 解决语法不一致的问题，并提供更好，更紧凑的语法。
  • OpenWRT和ubuntu都使用Nftables

表

与iptables表的对应关系

nftables簇 iptables实用程序
ip iptables
ip6 ip6tables
inet iptables和ip6tables
arp arptables
bridge ebtables
  • ip（即IPv4）是默认簇，如果未指定簇，则使用该簇。
  • 创建同时适用于IPv4和IPv6的规则，请使用inet。inet允许统一ip和ip6簇，以便更容易地定义规则。

输出解释

table inet warp {
        chain warp-in {
                type filter hook input priority mangle; policy accept;
                ip6 saddr 2606:4700:d0::a29f:c001 udp sport 1701 @th,72,24 set 0x0
        }

        chain warp-out {
                type filter hook output priority mangle; policy accept;
                ip6 daddr 2606:4700:d0::a29f:c001 udp dport 1701 @th,72,24 set 0x46c997
        }
}
  • type 可以是filter、route或者nat。
  • hook 在IPv4/IPv6/Inet地址簇中，可以是prerouting、input、forward、output或者postrouting。其他地址簇中的钩子列表请参见nft(8)。

iptables命令

查看默认表filter的规则

对于每条链，内核会按照顺序依次检查 iptables 防火墙规则，如果发现有匹配的规则目录，则立刻执行相关动作，停止继续向下查找规则目录；如果所有的防火墙规则都未能匹配成功，则按照默认策略处理。 

$ sudo iptables -vnL 
Chain INPUT (policy ACCEPT 2211K packets, 855M bytes)
 pkts bytes target     prot opt in     out     source               destination
    0     0 ACCEPT     all  --  tun0   *       0.0.0.0/0            0.0.0.0/0

  • 命令
  • 默认 -t filter
  • -v 显示详细信息，-n显示具体ip和端口数值
  • 输出
  • policy ACCEPT 当前链的默认策略 ACCEPT
  • pkts：对应规则匹配到的报文的个数。
  • bytes：对应匹配到的报文包的大小总和。
  • target：规则对应的target，往往表示规则对应的"动作"，即规则匹配成功后需要采取的措施。
  • prot：表示规则对应的协议，是否只针对某些协议应用此规则。
  • opt：表示规则对应的选项。
  • in：表示数据包由哪个接口(网卡)流入，我们可以设置通过哪块网卡流入的报文需要匹配当前规则。
  • out：表示数据包由哪个接口(网卡)流出，我们可以设置通过哪块网卡流出的报文需要匹配当前规则。
  • source：表示规则对应的源头地址，可以是一个IP，也可以是一个网段。
  • destination：表示规则对应的目标地址。可以是一个IP，也可以是一个网段。

添加的动作

命令部分：-j + 如下动作 * ACCEPT：允许数据包通过。 * DROP：直接丢弃数据包，不给任何回应信息，这时候客户端会感觉自己的请求泥牛入海了，过了超时时间才会有反应。 * REJECT：拒绝数据包通过，必要时会给数据发送端一个响应的信息，客户端刚请求就会收到拒绝的信息。 * SNAT：源地址转换，解决内网用户用同一个公网地址上网的问题。 * MASQUERADE：是SNAT的一种特殊形式，适用于动态的、临时会变的ip上。 * DNAT：目标地址转换。 * REDIRECT：在本机做端口映射。 * LOG：在/var/log/messages文件中记录日志信息，然后将数据包传递给下一条规则，也就是说除了记录以外不对数据包做任何其他操作，仍然让下一条规则去匹配。

iptables管理命令

  • 选择表
  • -t指定表
  • 添加新规则
  • -A在链的最后追加一条规则 
  • -I在链的开头或指定序号插入一条规则 
  • -x显示精确值，不做单位换算
  • 替换规则
  • -R替换一条指定的规则
  • 查看规则
  • -L列出所有规则 
  • -n以数据形式显示地址与端口信息 
  • -v以更加详细的方式显示 
  • --line-numbers查看规则时，显示规则序号
  • 删除或清空规则
  • -D删除指定序号的一条规则 
  • -F清空指定表中的所有规则
  • 设置默认策略
  • -P为指定的链设置默认规则
  • 新建规则链
  • -N新建自定义链
  • 重命名链
  • -E重命名自定义链
  • 删除链
  • -X删除自定义空链 
  • -Z计数器清零

常见实例

Add a NAT rule to translate all traffic from the 192.168.0.0/24 subnet to the host's public IP: 

$sudo iptables -t nat -A POSTROUTING -s 192.168.0.0/24 -j MASQUERADE

$ sudo iptables -t nat -vnL --line-numbers
Chain POSTROUTING (policy ACCEPT 19 packets, 1551 bytes)
num   pkts bytes target     prot opt in     out     source               destination
6        0     0 MASQUERADE  all  --  *      *       192.168.0.0/24       0.0.0.0/0

$ sudo iptables -t nat -D POSTROUTING 6 #delete

有待学习

  • docker相关的iptables的输出
  • OpenWRT上iptables完全是空的，是显示错误还是防火墙用了firewalld
  • node5上的warp的mangle在哪里？

Ubuntu配置

Windows配置

  • 入站规则
  • 出站规则

OpenWRT配置

to finished

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

https://blog.csdn.net/weixin_45649763/article/details/103338747

https://juejin.cn/post/7108726951304495135

https://icloudnative.io/posts/using-nftables/

  • 分类于 toLearn
  • 需要 1 分钟阅读时间

Jupyter AI

Jupyter 简介

Jupyter是一个开源的、交互式的计算环境，可以让用户创建和共享包含实时代码、可视化和文本的文档。

  • 它的名字来源于三个主要的编程语言：Julia、Python和R，这三种语言的开头字母构成了“Jupyter”。
  • Jupyter最初是IPython项目的一部分，旨在提供Python的交互式计算环境。随着时间的推移，它不仅支持Python，还扩展到其他编程语言，包括R、Julia、Scala等。Jupyter的灵感来自于IPython的交互式shell，但在其基础上增加了更多功能和可扩展性。

Jupyter最显著的特点：用户可以通过Web浏览器打开Jupyter笔记本，然后在其中编写代码、运行代码并直接查看代码的输出结果。笔记本中的代码和文本可以交叉编排，使得写作、数据分析和可视化变得非常直观和便捷。

主要的Jupyter组件包括：

  1. Jupyter Notebook：这是最常见的Jupyter界面，以.ipynb后缀的文件保存。它支持多种编程语言的代码运行，交互式地执行和编辑代码块，并支持在代码块中插入Markdown格式的文本以及图像、链接等内容。
  2. Jupyter Lab：这是Jupyter Notebook的下一代界面，提供了更加现代化和灵活的界面。Jupyter Lab将各种组件整合到一个集成的界面中，使得多个笔记本、终端和文件浏览器可以在一个窗口中同时运行。
  3. Jupyter Kernel：Jupyter支持多种编程语言的内核，通过内核，Jupyter可以与特定编程语言进行交互。例如，使用Python内核可以在笔记本中运行和编写Python代码，同样，使用R内核可以运行和编写R代码。

Jupyter在教育、数据科学、机器学习、数据分析等领域得到广泛应用。它提供了一个方便、实用的平台，帮助用户探索数据、实验算法、展示结果，并通过共享笔记本方便地与其他人交流和合作。

Jupyter vs python

Jupyter 的核心在于 数据分析的 计算-分析-可视化 的快速迭代。

如果不是数据科学，就不太需要Jupyter

Installation in Linux

安装Jupyter Lab

web-forward to local machine

远程访问服务器

Jupyter-AI

  1. Installation
  2. test

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

  1. python 一大特点就是容易可视化，既然这样，我为什么不用jupyter呢？
  2. chatgpt 类的工具都是基于付费API，有两大问题
  3. 国内难以付费
  4. 国内ip一旦访问是很容易封号的。
  5. 一种解决办法是使用有免费API的工具，并且在全流量走cloudflare的wg的服务器上配置服务。

参考文献

上面回答部分来自ChatGPT-3.5，没有进行正确性的交叉校验。

https://jupyter-ai.readthedocs.io/en/latest/users/index.html#installation

  • 分类于 toLearn
  • 需要 1 分钟阅读时间

Parallel_sort

并行排序算法

to learn

PSRS算法

并行正则采样排序算法

PSRS

复杂度分析

简单地讨论一下 PSRS 算法的复杂度。

  • 在第一部分的快速排序中，时间复杂度为O(klogk)，k=n/p
  • 然后，各处理器选择 p-1 个代表元素，代价为O(p)
  • 再由 Proc#0 对所有送来的代表元素进行排序，然后选出主元，这里若使用快速排序，代价为O(p^2 logp^2)
  • 而若使用归并排序，则所需代价为O(p^2)
  • 每个处理器接收到主元后，再对有序数组进行划分，代价为O(k+p)
  • 最后，各个处理器全局交换，并行归并排序，
  • 每个处理器是串行的多路归并问题，时间复杂度为O(k*logp)

考虑到实际应用中，需要排序的数据长度 n 一定远远多于现有的处理器 p，此时可以视 p 为一个小常数，那么 PSRS 排序算法的时间复杂度，就可以简化为 O(klogk+k*logp)~O(klogk)

从消息复杂度的角度看，

  • 播送主元的复杂度为 O(p^2+p)
  • 分区合并（全局交换）部分的消息复杂度与具体算法实现相关，但其最大值不会超过 O(n)

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

上面回答部分来自ChatGPT-3.5，没有进行正确性的交叉校验。

https://dingfen.github.io/mpi&openmp/2021/01/23/psrs_sort.html

  • 分类于 Tutorials
  • 需要 4 分钟阅读时间

ParallelIntroduction

战略层

并行算法设计(详细见陈国良教材)

PCAM

设计并发程序的四个阶段（PCAM设计方法学）：

  1. 划分（Partitioning）:分解成小的任务，开拓并发性
  2. 通讯（Communication）：确定诸任务间的数据交换，监测划分的合理性；
  3. 组合（Agglomeration）：依据任务的局部性，组合成更大的任务；
  4. 映射（Mapping）：将每个任务分配到处理器上，提高算法的性能。

三种基本方法

串改并：现有串行算法改成并行
  1. 从问题开始全新设计并行算法
  2. 前缀和改成线性方程组的问题来并行
  3. 有向环的k-着色并行算法
    1. 将coreId作为颜色，进行二进制处理来颜色压缩。压缩到0-5之后再单独消除颜色
借用法：借用已有算法
  1. 最短路径动态规划转换成矩阵乘法
其他基础方法
  1. 平衡树
    1. 求n个最大值，先串行求部分最大，再用树，成本（处理器个数*时间）最低
    2. 访问存储次数/成本也不是最低的
  2. 倍增技术，指针跳跃
  3. 分治策略
  4. 划分原理（以两个有序数列到归并排序为例）
    1. 均匀划分
    2. 对数划分
    3. 方根划分
    4. 功能划分：基于硬件的Batcher实现，奇偶归并排序，双调序列的实现可以简化网络
  5. 流水线技术
    1. 脉动阵列
  6. 加速级联策略
    1. 先采用最快的方法将问题规模先减小到一个阈值，然后用其余最优的算法求出原问题的解。
    2. 思想其实类似机器学习里的变学习率。例子有平衡树的
  7. 破对称技术
    1. 打破数据的对称，便于分类

指令级并行 ILP

编译器和硬件级别的，一般不会引起程序员的注意。1

挑战： 数据相关

  • 真数据相关
  • 名称相关：两条指令使用了相同的寄存器或者存储器位置，但实际并没有数据流动。寄存器重命名处理
  • 控制相关：主要指指令的执行与分支指令存在先后关系。

解决方案(CPI to 1)：“硬件推测”（Hardware Speculation）

硬件推测是一种技术，通过它，处理器可以在不完全确定某些操作结果的情况下，提前执行后续指令。这种技术主要用于提高处理器的性能和执行效率。以下是硬件推测的几个关键方面：

  1. 分支预测（Branch Prediction）：处理器使用分支预测来猜测条件跳转指令的结果（即跳转或不跳转）。如果预测正确，提前执行的指令就可以直接使用，从而避免等待分支决策的延迟。
  2. 数据依赖性推测（Data Dependency Speculation）：处理器可能会提前执行依赖于尚未计算完成的数据的指令。例如，即使前一条指令的结果尚未确定，它也会继续执行依赖于该结果的后续指令。
  3. 乱序执行（Out-of-Order Execution）：这是硬件推测的另一种形式。在这里，处理器根据资源的可用性而不是指令在程序中的顺序来调度指令的执行。
  4. 内存访问推测（Memory Access Speculation）：处理器可能会在所有必要的内存访问权限检查完成之前开始执行依赖于特定内存操作的指令。

这些推测性技术的共同目标是减少因等待数据依赖、分支决策或其他延迟而导致的空闲处理器周期。如果推测正确，这可以显著提高执行速度。然而，如果推测错误，处理器必须“倒回”并重新执行正确的指令路径，这可能导致性能损失。因此，现代处理器设计的一个关键方面是优化这些推测机制以最大限度地减少错误预测的影响。

编译器技术：基本流水线与循环展开
分支预测器
动态调度/乱序执行(out-of-order execution)
  • 有多个功能单元和流水化单元。使得流水线能同时执行多个指令

  • 乱序执行, 循序提交： 记分板 -> Tomasulo算法

  • 重排缓存区ROB：保存已经执行完成，但是还没有提交的指令结果。是乱序执行处理器的核心组件之一。

  • 三点作用：
    1. 指令顺序的维护：尽管指令被乱序执行（以利用处理器资源并提高性能），但最终的结果需要按照程序的原始顺序提交。ROB跟踪每条指令的执行状态，并确保它们在最终提交时是按顺序的。
    2. 分支与异常的支持处理： 区分已提交指令，保证分支预测失败时正常回退，和异常和中断时程序的一致性。
    3. 资源管理：ROB还参与动态地管理处理器资源，如识别哪些指令可以并行执行，以及在资源有限时优先执行哪些指令。

升级方案(CPI lower 1)：多发射架构（Multiple Issue）

与前面的区分

前面的技术是为了消除数据与控制停顿，使得CPI达到理想值1，如果我们想CPI小于一，每个时钟周期就需要发射多条指令。

多发射是一个更广泛的术语，指的是在一个时钟周期内发射（开始执行）多条指令的能力。

主要有三类：

  1. In order superscalar processor
  2. out-of-order superscalar processor
  3. VLIW
超标量架构（Superscalar）

超标量处理器通常具有多个执行单元，如多个整数、浮点和其他专用执行单元，以及复杂的调度和分支预测机制来支持同时处理多条指令。

VLIW

VLIW（Very Long Instruction Word）是一种处理器架构设计，其特点是使用非常长的指令字来编码多个操作，这些操作可以在单个处理器周期内并行执行。VLIW架构的关键特征如下：

  1. 长指令字：VLIW架构的指令字长度远超常规处理器。这些长指令字包含了多个操作（如算术、逻辑操作），这些操作在一个时钟周期内同时执行。
  2. 编译器优化：在VLIW架构中，指令的并行性是在编译时确定的，而不是在运行时。这意味着编译器负责识别可以并行执行的操作，并将它们组合成单个长指令字。
  3. 硬件简化：由于指令级并行性是在编译时处理的，VLIW处理器的硬件可以相对简化，因为它们不需要复杂的运行时指令调度和分支预测机制。这使得VLIW处理器在设计上更简单，功耗更低。
  4. 应用依赖：VLIW架构的效率高度依赖于编译器的优化能力和应用程序代码的特性。在指令流中并行性高的应用中，VLIW架构可以实现很高的性能。

VLIW架构在某些特定的应用场景（如数字信号处理DSP）中效果显著，但在通用计算领域的适用性受到限制，主要是因为编译器在处理普通程序时面临更大的挑战来有效地利用指令级并行性。

实例(超标量处理器能在一个时钟周期内同时发射和执行多条指令来实现指令级并行性。)

  • ARM Cortex-A8 Core 双发射、静态调度(In-order)超标量处理器
  • Intel Core i7 四发射、动态调度(out-of-order execution)超标量处理器
    • 微指令融合。性能更强，但是能耗比显著降低。

数据级并行 DLP

  • 向量张量、SIMD、以及GPU的结构
  • 区别和MLP 概念的不同：MLP（访存并行）是一种通过同时处理多个内存访问来实现并行性的概念。MLP的目标是提高对存储器系统的效率，减少内存访问的延迟时间。它可以通过预取、缓存和内存操作的重叠等技术来实现。

线程级并行 TLP

  • 单机多核系统
  • 运行一组紧密耦合的线程，协同完成任务
  • 缓存一致性协议

超算或者仓库级计算机(WSC Warehouse-Scale Computers) 请求级并行 RLP

  • 请求级并行：由一个或者多个用户发起的多个相对独立的进程
  • 环境： 云计算。
  • 关注成本与收益

并行分类

微处理器器中的并行

ILP 指令级并行

TLP 线程级并行

SMT 同步多线程（Simultaneous Multi-Threading，SMT）是一种在一个CPU 的时钟周期内能够执行来自多个线程的指令的硬件多线程技术。

CMP 单芯片多处理器（Chip multiprocessors）

常用的四种并行模式(这样分感觉不是很对)

  1. 共享内存模式（The shared memory model）
  2. 多线程模式（The multithread model）
  3. 分布式内存/消息传递模式（The distributed memory/message passing model）
  4. 数据并行模式（The data parallel model）

实际的经验

  1. IPCC Preliminary SLIC Optimization 4: EnforceLabelConnectivity

并行常见名词

SM : shared Memory

LM : Local Memory

DM ：distribute memory

并行计算模型

并行计算访存模型（强调时间）

均匀访存模型（UMA）、非均匀访存模型（NUMA）、全高速缓存访存模型（COMA）、一致性高速缓存非均匀存储访问模型（CC-NUMA）和非远程存储访问模型（NORMA）。

UMA（Uniform Memory Access）均匀存储訪问：物理存储器被全部处理器均匀共享，全部处理器对全部SM訪存时间相同，每台处理器可带有快速私有缓存，外围设备共享。

NUMA非均匀存储訪问：共享的SM是由物理分布式的LM逻辑构成，处理器訪存时间不一样，訪问LM或CSM（群内共享存储器）内存储器比訪问GSM（群间共享存储器）快

COMA（Cache-Only MA）全快速缓存存储訪问：NUMA的特例、全快速缓存实现

CC-NUMA（Coherent-Cache NUMA）快速缓存一致性NUMA：NUMA＋快速缓存一致性协议。实际是分布共享的DSM机器

NORMA（No-Remote MA）非远程存储訪问：无SM，全部LM私有。通过消息传递通信

NUMA

NUMA : NUMA (non-uniform memory access) is a method of configuring a cluster of microprocessor in a multiprocessing system so that they can share memory locally, improving performance and the ability of the system to be expanded. NUMA is used in a symmetric multiprocessing ( SMP ) system.

在NUMA下，處理器存取它自己的本地記憶體的速度比非本地記憶體快一些。 非統一記憶體存取架構的特點是：被共享的記憶體物理上是分散式的，所有這些記憶體的集合就是全域位址空間。

RDMA

Remote Direct Memory Access (RDMA) is an extension of the Direct Memory Access (DMA) technology, which is the ability to access host memory directly without CPU intervention. RDMA allows for accessing memory data from one host to another.

远程直接内存访问（英语：Remote Direct Memory Access，RDMA）是一种从一台计算机的内存到另一台计算机的内存的直接内存访问，而不涉及任何一台计算机的操作系统。这允许高吞吐量、低延迟联网，这在大规模并行计算机集群中特别有用。

重点是zero-copy， 不再需要机器缓存，然后拷贝传递信息。 InfiniBand网络默认支持，另一种就是RoCE

relationship between RDMA and NUMA

Most high performance computing clusters are nowadays composed of large multicore machines that expose Non-Uniform Memory Access (NUMA), and they are interconnected using modern communication paradigms, such as Remote Direct Memory Access (RDMA).

结构类型

  • SISD：单指令流单数据流计算机（冯诺依曼机）
  • SIMD：单指令流多数据流计算机
  • MISD：多指令流单数据流计算机， 实际不存在
  • MIMD：多指令流多数据流计算机

    • SIMD-SM

    PRAM（Parallel Random Access Machine）模型是单指令流多数据流（SIMD）并行机中的一种具有共享存储的模型。

    它假设有对其容量大小没有限制的一个共享存储器，并且有多个功能相同的处理器，在任意时刻处理器可以访问共享存储单元。根据是否可以同时读写，它又分为以下三类：PRAM-EREW，PRAM-CREW，PRAM-CRCW（其中C代表Concurrent，意为允许并发操作，E-代表Exclusive，意味排斥并发操作）。在PRAM中有一个同步时钟，所有的操作都是同步进行的。

    具有局部存储器的PRAM模型称作LPRAM模型，具有异步时钟的PRAM模型称作APRAM模型。

    在《并行算法的设计和分析》的第二十章-并行计算理论有额外的定义：

    • 允许任意处理器自由读写的 SIMD-SM。简记为 APRAM-CRCW
    • 只允许所有处理器并发写同一数的SIMD-SM。简记为CPRAM-CRCW
    • 只允许最小号码处理器优先写的SIMD-SM。称作优先PRAM-CRCW。简记为PPRAM-CRCW
    • 一个具有p个处理器的优先PRAM-CRCW模型。称作p-处理器的PPRAM-CRCW。

    几种MIMD

  • PVP并行向量处理机：多VP（向量处理器）通过交叉开关和多个SM（共享内存）相连
  • SMP对称多处理机：多P/C（商品微处理器）通过交叉开关/总线和多个SM（共享内存）相连
  • MPP大规模并行处理机：处理节点有商品微处理器+LM（分布式本地内存）。节点间通过高带宽低延迟定制网络互联，异步MIMD，多个进程有自己的地址空间，通过消息传递机制通信
  • COW工作站机群：节点是完整操作系统的工作站，且有磁盘
  • DSM分布共享存储处理机：快速缓存文件夹DIR确保缓存一致性。将物理分布式LM组成逻辑共享SM从而提供统一地址的编程空间

    • 需要进一步的研究学习

    暂无

    遇到的问题

    暂无

    参考文献

    1. 计算机体系结构 - 量化研究方法第5 版 ↩↩

    • 分类于 Algorithms
    • 需要 2 分钟阅读时间

    Benchmark : GUPS

    Introduction

    GUPS (Giga十亿 UPdates per Second) is a measurement that profiles the memory architecture of a system and is a measure of performance similar to MFLOPS.

    The HPCS HPCchallenge RandomAccess benchmark is intended to exercise the GUPS capability of a system, much like the LINPACK benchmark is intended to exercise the MFLOPS capability of a computer. In each case, we would expect these benchmarks to achieve close to the "peak" capability of the memory system. The extent of the similarities between RandomAccess and LINPACK are limited to both benchmarks attempting to calculate a peak system capability.

    definition of GUPS

    GUPS is calculated by identifying the number of memory locations that can be randomly updated in one second, divided by 1 billion (1e9).

    • The term "randomly" means that there is little relationship between one address to be updated and the next, except that they occur in the space of one half the total system memory. （只用一半内存？）
    • An update is a read-modify-write operation on a table of 64-bit words. An address is generated, the value at that address read from memory, modified by an integer operation (add, and, or, xor) with a literal value, and that new value is written back to memory.

    Extensibility

    • We are interested in knowing the GUPS performance of both entire systems and system subcomponents --- e.g., the GUPS rating of a distributed memory multiprocessor the GUPS rating of an SMP node, and the GUPS rating of a single processor.
    • While there is typically a scaling of FLOPS with processor count, a similar phenomenon may not always occur for GUPS.

    Principle

    Select the memory size to be the power of two such that 2^n <= 1/2 of the total memory. Each CPU operates on its own address stream, and the single table may be distributed among nodes. The distribution of memory to nodes is left to the implementer. A uniform data distribution may help balance the workload, while non-uniform data distributions may simplify the calculations that identify processor location by eliminating the requirement for integer divides. A small (less than 1%) percentage of missed updates are permitted.

    Installation

    Download

    official web or from GitHub

    Usage

    需要进一步的研究学习

    暂无

    遇到的问题

    暂无

    开题缘由、总结、反思、吐槽~~

    参考文献

    上面回答部分来自ChatGPT-3.5，没有进行正确性的交叉校验。

    无

    • 分类于 Tutorials
    • 需要 1 分钟阅读时间

    Echart

    echart

    快速上手

    • 在github仓库dist目录下拷贝echart.js 和 echart.min.js到index.html目录下。

    Vue-ECharts

    参考中文文档

    sudo apt-get install npm
npm install echarts vue-echarts

    实践

    简单柱状图

    option = {
  title: {
    text: 'Percentage of page walk time overhead caused by data TLB misses',
    subtext: 'GUPS RandomAccess benchmark'
  },
  tooltip: {
    trigger: 'axis',
    axisPointer: {
      type: 'shadow'
    }
  },
  xAxis: {
    name: 'input-data \nsize',
    type: 'category',
    data: ['2^29', '2^30', '2^31', '2^32'],
  },
  yAxis: {
    // name: 'Percentage',
    type: 'value',
    title: 'align'
  },
  series: [
    {
      name: "Percentage",
      data: [13.20, 19.50, 45.22,66.81],
      type: 'bar',
      label: {
        show: true,
        position: 'top'
      },
    }
  ]
};

    需要进一步的研究学习

    暂无

    遇到的问题

    暂无

    开题缘由、总结、反思、吐槽~~

    参考文献

    无

    • 分类于 Architecture
    • 需要 2 分钟阅读时间

    Double 2 int8

    将范围double映射到Int8

    解释PPT：除开int8的映射，还考虑了误差的计算，和重新计算M+空间的double并排序。

    注释：

    1. 采用的是欧式距离（两点直线距离），不是切比雪夫距离（max(delta x, delta y)）
    2. C_2^n ，由于目标函数是所有边的距离和，所以要乘以边的数量。C_2^n 是从n个点中取两个点的组合数，也就是边的数量。
    3. C_k^n , k是支撑点个数，n 是总个数。
    4. 修正M个，因为题目要求求TopM，由于第M个可能是 +delta来的，M+1个可能是-delta导致的，所以要修正M个后面2*delta的范围。

    上面不知道具体怎么实现的（需要看代码）。下面同时要注意溢出的处理。int8溢出加法，可以转化为int16, 再相加。

    _mm256_cvtepi8_epi16

    AVX的操作Int寄存器也是分有无符号

    _epi8 signed char, or _epu8 unsigned char

    去年决赛冠军-上交队的思路

    这是我搜集这么多PPT里的，少有的思路

    👏我要😘开吹了👏

    本来IPCC2022 拿了第二名，我还心有不甘。直到我的风神大人教育了我。

    拿到风神大人的PPT的时候，我醍醐灌顶。

    这么体贴人，不愧是我温迪大人.

    需要进一步的研究学习

    暂无

    遇到的问题

    暂无

    开题缘由、总结、反思、吐槽~~

    参考文献

    无

    • 分类于 Architecture
    • 需要 4 分钟阅读时间

    Disassembly file: objdump

    objdump file

    Disassembly of section .plt:

0000000000402020 <.plt>:
  402020: ff 35 e2 bf 02 00     pushq  0x2bfe2(%rip)        # 42e008 <_GLOBAL_OFFSET_TABLE_+0x8>
  402026: ff 25 e4 bf 02 00     jmpq   *0x2bfe4(%rip)        # 42e010 <_GLOBAL_OFFSET_TABLE_+0x10>
  40202c: 0f 1f 40 00           nopl   0x0(%rax)

0000000000402030 <_Znam@plt>:
  402030: ff 25 e2 bf 02 00     jmpq   *0x2bfe2(%rip)        # 42e018 <_Znam@GLIBCXX_3.4>
  402036: 68 00 00 00 00        pushq  $0x0
  40203b: e9 e0 ff ff ff        jmpq   402020 <.plt>

0000000000402040 <_ZNSo3putEc@plt>:
  402040: ff 25 da bf 02 00     jmpq   *0x2bfda(%rip)        # 42e020 <_ZNSo3putEc@GLIBCXX_3.4>
  402046: 68 01 00 00 00        pushq  $0x1
  40204b: e9 d0 ff ff ff        jmpq   402020 <.plt>

    .plt节主要实现了使用过程链接表(Procedure Linkage Table)实现延迟绑定的功能。

    openmp相关的执行

    omp_outlined函数

    问题：objdump 程序 有许多 类似 <.omp_outlined..16>: 的函数，但是main函数里并没有调用。实际openmp是怎么执行这些代码的呢？

    在使用了OpenMP指令的C/C++程序编译后,编译器会自动生成一些名为.omp_outlined.的函数。这些函数是OpenMP所需要的运行时支持函数,不是直接在main函数中调用的,其执行方式主要有以下几种:

    1. 一些关键的运行时函数,如线程创建、同步等,是在程序启动时由OpenMP运行时库初始化和直接调用的。
    2. 对于并行region,编译器会在主线程发起并行时调用对应的.omp_outlined.函数创建线程并发布工作。
    3. 一些工作分配,同步等调用也是隐式通过运行时库的支持函数实现的。
    4. 对于并行循环,编译器会将循环体移动到.omp_outlined.函数,在循环分配工作时调用。
    5. 减少指令,作用域变化等也会引发这些函数的调用。

    所以.omp_outlined.函数的执行是隐式通过运行时库触发和调度的,不需要用户代码直接调用。它们是OpenMP实现所必须的,由编译器和运行时库协调完成。用户只需要编写OpenMP指令,不必关心具体的调用细节。

    总体来说,这是一种让并行执行透明化的实现机制,减少了用户的工作量。

    OpenMP的汇编代码

    不同平台不同，有GOMP_parallel_start开头的。也有如下x86平台的

      405854:   48 c7 84 24 a0 00 00    movq   $0x4293b9,0xa0(%rsp)
  40585b:   00 b9 93 42 00 
  405860:   48 8d bc 24 90 00 00    lea    0x90(%rsp),%rdi
  405867:   00 
  405868:   ba 10 5f 40 00          mov    $0x405f10,%edx
  40586d:   be 02 00 00 00          mov    $0x2,%esi
  405872:   4c 89 f9                mov    %r15,%rcx
  405875:   4c 8b 44 24 20          mov    0x20(%rsp),%r8
  40587a:   31 c0                   xor    %eax,%eax
  40587c:   e8 ff cb ff ff          callq  402480 <__kmpc_fork_call@plt>
  405881:   48 8b 7c 24 60          mov    0x60(%rsp),%rdi

    这段汇编代码实现了OpenMP中的并行构造,主要执行了以下几个步骤:

    1. 在栈上写入一个常量0x4293b9,可能是team的参数 (48 c7 84 24)
    2. 准备参数,获取rsp+0x90地址到rdi作为第1参数 (%rdi)
    3. 设置edx为0x405f10,可能是kmp_routine函数地址
    4. esi设置为2,可能表示有2个参数
    5. r15设置到rcx,传入线程号参数
    6. r8传入栈上第0x20个参数,可能是void* shareds参数
    7. 清空eax,一些调用约定使用
    8. 调用 __kmpc_fork_call函数,这是OpenMP的runtime库函数,用来并行执行一个函数
    9. kmpc fork multiple parallel call？
    10. 最后将返回值保存在rdi指定的栈空间上

    所以这段代码实现了调用OpenMP runtime并行执行一个函数的操作,准备参数,调用runtime API,获取返回值的一个流程。

    利用runtime库的支持函数可以实现汇编级别的OpenMP并行性。

    readelf

    各section位置以及含义，参考文档

    $ readelf -S bfs.inj
There are 37 section headers, starting at offset 0xbe8e8: 
在文件内 0xbe8e8字节开始

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  序号 节名称               节类型          节的虚拟地址偏移量      节在文件中的偏移量
节大小         每个条目的大小（如果大小固定）  节的标志  节的链接信息    节的额外信息    节的信息对齐方式
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .interp           PROGBITS         00000000004002a8  000002a8
       000000000000001c  0000000000000000   A       0     0     1
  [ 2] .note.gnu.build-i NOTE             00000000004002c4  000002c4
       0000000000000024  0000000000000000   A       0     0     4
  [ 3] .note.ABI-tag     NOTE             00000000004002e8  000002e8
       0000000000000020  0000000000000000   A       0     0     4
  [ 4] .gnu.hash         GNU_HASH         0000000000400308  00000308
       000000000000005c  0000000000000000   A       5     0     8
  [ 5] .dynsym           DYNSYM           0000000000400368  00000368
       00000000000007e0  0000000000000018   A       6     1     8
  [ 6] .dynstr           STRTAB           0000000000400b48  00000b48
       0000000000000b1d  0000000000000000   A       0     0     1
  [ 7] .gnu.version      VERSYM           0000000000401666  00001666
       00000000000000a8  0000000000000002   A       5     0     2
  [ 8] .gnu.version_r    VERNEED          0000000000401710  00001710
       0000000000000110  0000000000000000   A       6     5     8
  [ 9] .rela.dyn         RELA             0000000000401820  00001820
       00000000000000f0  0000000000000018   A       5     0     8
  [10] .rela.plt         RELA             0000000000401910  00001910
       00000000000006c0  0000000000000018  AI       5    24     8
  [11] .init             PROGBITS         0000000000402000  00002000
       000000000000001b  0000000000000000  AX       0     0     4
  [12] .plt              PROGBITS         0000000000402020  00002020
       0000000000000490  0000000000000010  AX       0     0     16
  [13] .text             PROGBITS         00000000004024b0  000024b0
       0000000000026475  0000000000000000  AX       0     0     16
  [14] .fini             PROGBITS         0000000000428928  00028928
       000000000000000d  0000000000000000  AX       0     0     4
  [15] .rodata           PROGBITS         0000000000429000  00029000
       0000000000001180  0000000000000000   A       0     0     16
  [16] .eh_frame_hdr     PROGBITS         000000000042a180  0002a180
       00000000000002ac  0000000000000000   A       0     0     4
  [17] .eh_frame         PROGBITS         000000000042a430  0002a430
       0000000000001780  0000000000000000   A       0     0     8
  [18] .gcc_except_table PROGBITS         000000000042bbb0  0002bbb0
       00000000000005d0  0000000000000000   A       0     0     4
  [19] .init_array       INIT_ARRAY       000000000042dbc8  0002cbc8
       0000000000000010  0000000000000008  WA       0     0     8
  [20] .fini_array       FINI_ARRAY       000000000042dbd8  0002cbd8
       0000000000000008  0000000000000008  WA       0     0     8
  [21] .data.rel.ro      PROGBITS         000000000042dbe0  0002cbe0
       00000000000001f0  0000000000000000  WA       0     0     8
  [22] .dynamic          DYNAMIC          000000000042ddd0  0002cdd0
       0000000000000220  0000000000000010  WA       6     0     8
  [23] .got              PROGBITS         000000000042dff0  0002cff0
       0000000000000010  0000000000000008  WA       0     0     8
  [24] .got.plt          PROGBITS         000000000042e000  0002d000
       0000000000000258  0000000000000008  WA       0     0     8
  [25] .data             PROGBITS         000000000042e258  0002d258
       0000000000000010  0000000000000000  WA       0     0     8
  [26] .bss              NOBITS           000000000042e280  0002d268
       0000000000000180  0000000000000000  WA       0     0     64
  [27] .comment          PROGBITS         0000000000000000  0002d268
       000000000000004a  0000000000000001  MS       0     0     1
  [28] .debug_info       PROGBITS         0000000000000000  0002d2b2
       000000000002a06e  0000000000000000           0     0     1
  [29] .debug_abbrev     PROGBITS         0000000000000000  00057320
       0000000000000a57  0000000000000000           0     0     1
  [30] .debug_line       PROGBITS         0000000000000000  00057d77
       000000000000af9a  0000000000000000           0     0     1
  [31] .debug_str        PROGBITS         0000000000000000  00062d11
       0000000000010328  0000000000000001  MS       0     0     1
  [32] .debug_loc        PROGBITS         0000000000000000  00073039
       0000000000042846  0000000000000000           0     0     1
  [33] .debug_ranges     PROGBITS         0000000000000000  000b587f
       00000000000054c0  0000000000000000           0     0     1
  [34] .symtab           SYMTAB           0000000000000000  000bad40
       00000000000018c0  0000000000000018          35   106     8
  [35] .strtab           STRTAB           0000000000000000  000bc600
       0000000000002177  0000000000000000           0     0     1
  [36] .shstrtab         STRTAB           0000000000000000  000be777
       000000000000016c  0000000000000000           0     0     1
Key to Flags:
  W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
  L (link order), O (extra OS processing required), G (group), T (TLS),
  C (compressed), x (unknown), o (OS specific), E (exclude),
  l (large), p (processor specific)

    字段含义

    • Type 字段，具体含义参考文档1-10
    • Link 字段中的值是节头表中节头条目的索引，索引从0开始，表示第一个节头表条目，依此类推。比如5 代表与[ 5] .dynsym 有关

    值得注意

    One section type, SHT_NOBITS described below, occupies no space in the file, and its sh_offset member locates the conceptual placement in the file.

    so the number "2d258" remains unchanged.

      [25] .data             PROGBITS         000000000042e258  0002d258
       0000000000000010  0000000000000000  WA       0     0     8
  [26] .bss              NOBITS           000000000042e280  0002d268
       0000000000000180  0000000000000000  WA       0     0     64

    .got

    global offset table

    .plt

    This section holds the procedure linkage table. See ‘‘Special Sections’’ in Part 1 and ‘‘Procedure Linkage Table’’ in Part 2 for more information.

    Function symbols (those with type STT_FUNC) in shared object files have special significance. When another object file references a function from a shared object, the link editor automatically creates a procedure linkage table entry for the referenced symbol.

    参考文档2-17 page48

    需要进一步的研究学习

    暂无

    遇到的问题

    暂无

    开题缘由、总结、反思、吐槽~~

    参考文献

    上面回答部分来自ChatGPT-3.5，没有进行正确性的交叉校验。

    无