跳转至

2021

BHive : An Infrastructure for Adaptive Dynamic Optimization 2003 IEEE

摘要

动态优化逐渐显现出是一种解决传统静态汇编困难的好方法。 但是市面上有大量的针对开发静态优化的编译器框架,但是少有针对动态优化的。

我们实现了一种动态分析和优化的框架,为DynamoRIO动态代码修改系统提供了一种创建额外模块的交互界面。通过简单轻量的API就可以提炼许多DynamoRIO运行时的底层细节,但是只能在单指令流下,而且不同指令显示的细节也是不同的。

该API不仅可以用来优化,也可以instrumentation,热点分析和动态翻译。

为了展现架构的有效性,我们实现了若干优化,一些例子有40%提升,基于DynamoRIO平均有12%加速。

简介

随着现代软件的复杂,还有动态load,共享库等特性,静态分析越来越衰弱。静态分析器去分析整个程序是困难或者不可能的,而静态优化又受限于静态代码分析器的准确性。而且静态优化过多会导致出错时难以debug。

DynamoRIO

Client Interface

Instruction Representation

DynamoRIO API

DynamoRIO Client

Extensions for Adaptive Optimization

Extensions for Custom Traces

Examples

Redundant Load Removal

Strength Reduction

Indirect Branch Dispatch

Custom Traces

Experimental Results

Conclusions

就是这个动态框架好,使用范围广,前途光明

BHive的提取基本块的应该就是 bbuf

https://github.com/DynamoRIO/dynamorio/blob/master/api/samples/bbbuf.c

需要进一步的研究学习

暂无

遇到的问题

暂无

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

参考文献

Static Code Analysis

静态代码分析器的意义

在不运行程序的情况下,预测程序性能表现。得到估计时钟周期,资源占用情况,潜在的代码瓶颈等的分析。以便优化程序,或者为了更好的运行程序反过来对CPU的架构设计提出意见。

在预测的过程中,也会简单进行自动向量化,指令调度等工作。

比如你想看在arm架构下该程序下有什么瓶颈,但是你只有intel的机器,你就可以通过静态代码分析器来分析。但是当前的效果都不是太好。

已有的Static Code Analyzer

IACA

IACA (the Intel Architecture Code Analyzer) is a (2019: end-of-life) freeware, closed-source static analysis tool made by Intel

由于Intel对自己的处理器优化很了解,所有可以更好的预测。 比如 zero-idioms 和 micro-op fusions(聚合,将相邻指令变为一条指令)

zero-idioms —— The processor recognizes that certain instructions are independent of the prior value of the register if the two operand registers are the same. An instruction that subtracts a register from itself will always give zero, regardless of the previous value of the register.

Ithemal

Ithemal (Instruction THroughput Estimator using MAchine Learning) 基于hierarchical LSTM–based 方法。基本块预测器,但是是黑盒。

Long short-term memory (LSTM) is an artificial recurrent neural network (RNN) architecture used in the field of deep learning.

应该是准确度最高的

LLVM-mca

LLVM Machine Code Analyzer 受到IACA启发的相似的工具,是乱序超标量(多条流水线,每周期可以完成2条以上指令,如下图)微架构模拟器。 使用了LLVM后端的调度模型参数。这种重用调度模型的选择对llvm cost 模型提供了经验。其准确性于调度模型有关。

OSACA

Open Source Architecture Code Analyzer

是IACA的开源替代,也和llvm-mca很像。是参数化的乱序模拟器,但是参数来自测量的指令查找表

cost model

LLVM 和GCC 也有cost model,但是是指令层面的,不是基本块层面的。

比如LLVM 至少有3个: 1. a generic, per-instruction IR (Intermediate Representation) cost model for its target-independent optimizations 2. one for instruction scheduling (the scheduling model [14] is also used by llvm-mca); 3. another one for register allocation

基本概念

throughput

Predicting the (average) number of clock cycles a processor takes to execute a block of assembly instructions in steady state

performance models / Processor performance models

指代静态代码分析器,就是别名。

需要进一步的研究学习

暂无

遇到的问题

暂无

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

参考文献

https://github.com/RRZE-HPC/OSACA

Kunpeng

多线程SMT (Simultaneous multithreading)

统一的调度器复杂度超级高,只有Intel实现了,但是效果很好。

什么是CPU Die

良品率会更高

自研OpenBLAS+ ,毕申编译器,自研MPI

片间一致性可以到达4P到16P???。Intel可以达到8P

问题

  1. 虽然说是保密的,但是鲲鹏930,950应该已经出来了
  2. 930,950是异构的核(是大小核吗?)

需要进一步的研究学习

暂无

遇到的问题

暂无

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

参考文献

https://bbs.huaweicloud.com/blogs/268031

GPU

这篇聚焦于 GPU 发展的起源,目的和历史。(看历史真好玩)

ISA & Micro-architecture

Instruction Set Architecture(ISA)

指令集架构(Instruction Set Architecture)是指一种类型CPU中用来计算和控制计算机系统的一套指令的集合。

指令集架构主要规定了指令格式、寻址访存(寻址范围、寻址模式、寻址粒度、访存方式、地址对齐等)、数据类型、寄存器。指令集通常包括三大类主要指令类型:运算指令、分支指令和访存指令。此外,还包括架构相关指令、复杂操作指令和其他特殊用途指令。因此,一种CPU执行的指令集架构不仅决定了CPU所要求的能力,而且也决定了指令的格式和CPU的结构。X86架构和ARMv8架构就是指令集架构的范畴。

所以不要说Nvidia是属于x86还是arm了,显卡应该是有自己的架构的。比如NV Tesla架构 、Fermi架构、Maxwell架构、Kepler架构、Turing架构。

而且X86具体到Intel,也有Skylake 架构 Ice lake 架构 Haswell架构等具体的实现

CISC与RISC的历史

复杂指令集(CISC,complex instruction set computer)

RISC:Reduced Instruction Set Computer

Three Performance Knobs

\(\(p(performance)=\frac{IPC*f}{Instruction\ Count}\)\)

在计算机发展初期,计算机的优化方向是通过设置一些功能复杂的指令,把一些原来由软件实现的、常用的功能改用硬件的指令系统实现(减少IC),以此来提高计算机的执行速度。也就是为了减少程序的设计时间,逐渐开发出单一指令,复杂操作的程序代码。设计师只需写下简单的指令,再交给CPU去执行。

但是后来有人发现,整个指令集中,只有约20%的指令常常会被使用到,大约占了整个程序的80%;剩余80%的指令,只占了整个程序的20%。(典型的二八原则)

于是有人提出RISC尽量简化计算机指令功能的想法,主张硬件应该专心加速常用的指令,较为复杂的指令则利用常用的指令去组合。功能简单、能在一个节拍内执行完成的指令被保留,而较复杂的功能用一段子程序来实现,这种计算机系统就被称为精简指令系统计算机。

简单来说,CISC任务处理能力强,适合桌面电脑和服务器。RISC通过精简CISC指令种类,格式,简化寻址方式,达到省电高效的效果,适合手机、平板、数码相机等便携式电子产品。

各种架构

X86架构

1978年6月8日,Intel 发布了新款16位微处理器 8086,也同时开创了一个新时代:X86架构诞生了。

X86指令集是美国Intel公司为其第一块16位CPU(i8086)专门开发的,美国IBM公司1981年推出的世界第一台PC机中的CPU–i8088(i8086简化版)使用的也是X86指令。

为了保证电脑能继续运行以往开发的各类应用程序以保护和继承丰富的软件资源,所以Intel公司所生产的所有CPU仍然继续使用X86指令集。

IA64

IA64,又称英特尔安腾架构(Intel Itanium architecture),使用在Itanium处理器家族上的64位指令集架构,由英特尔公司与惠普公司共同开发,2001年首次推出。

ARM

见 arm.md

MIPS

1981年出现,由MIPS科技公司开发并授权,它是基于一种固定长度的定期编码指令集,并采用 导入/存储(Load/Store)数据模型。

mips是一个学院派的cpu,授权门槛极低,因此很多厂家都做mips或者mips衍生架构。我们平时接触到的mips架构cpu主要用在嵌入式领域,比如路由器。

目前最活跃的mips是中国的龙芯,其loongisa架构其实是mips的扩展。

DEC Alpha

Alpha是DEC公司推出的RISC指令集系统,基于Alpha指令集的CPU也称为Alpha AXP架构,是64位的 RISC微处理器,最初由DEC公司制造,并被用于DEC自己的工作站和服务器中。作为VAX的后续被开发,支持VMS操作系统,如 Digital UNIX。

侧重超算,目前貌似最活跃是中国申威,神威太湖之光的cpu

RISC-V

2010年提出,受到大家的支持。USTC有团队研究。

Instruction Set Architecture(ISA)的发展展望

90年代,MIPS和Alpha作为知名RISC在与X86竞争计算机市场中失败,又在错过智能终端高速发展的机遇中走向衰弱。2010年发布的RISC-V作为从发明伊始即以开源为最大特色的RISC ISA受到全球学界、产业界的高度关注。全球顶级学府、科研机构、芯片巨头纷纷参与,各国政府出台政策支持RISC-V的发展和商业化。RISC-V有望成为X86和ARM之后ISA第三极。

微架构(Micro-architecture)

实现指令集架构的物理电路被称为处理器的微架构(Micro-architecture)

大多数情况下,一种处理器的微架构是针对一种特定指令集架构进行物理实现。少部分处理器架构设计为了更好的兼容性,会在电路设计上实现多个指令集架构。虽然,指令集架构可以授权给多家企业,但微架构的设计细节,也就是对指令的物理实现方式是各家厂商绝对保密的。

需要进一步的研究学习

暂无

遇到的问题

暂无

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

参考文献

https://www.zhihu.com/question/423489755/answer/1622380842

Big-Endian & Little-Endian

问题是否有意义

鸡蛋从哪头打破,怎么会有哪种更合适呢?对个人生活和社会发展又有什么意义呢?Swift写这段故事,其实是讽刺当时法国和英国的时政,认为真正重要的事情得不到关注、而在一些毫无意义的事情上争论不休。

各个阵营的选择

Motorola的PowerPC系列CPU采用Big-Endian方式存储数据,

而Intel的x86系列则采用Little-Endian方式存储数据。

JAVA虚拟机中多字节类型数据的存放顺序,也就是JAVA字节序是Big-Endian。

很多的ARM,DSP(Digital signal processor)都为小端模式。有些ARM处理器还可以随时在程序中(在ARM Cortex 系列使用REV、REV16、REVSH指令)进行大小端的切换。

忽略大小端的情况

得益于高级语言的发展,在现在的软件开发基本不需关心字节序(除非是socket编程),如Java这类跨平台移植的语言由虚拟机屏蔽了字节序问题。

对于大小端的处理也和编译器的实现有关,在C语言中,默认是小端(但在一些对于单片机的实现中却是基于大端,比如Keil 51C),Java是平台无关的,默认是大端。在网络上传输数据普遍采用的都是大端

大小尾端程序

华为鲲鹏AArch64 和 Intel x86 都是little-endian

需要进一步的研究学习

暂无

遇到的问题

暂无

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

参考文献

LLVM-MCA: Install&RunTests

github

https://github.com/llvm/llvm-project/tree/main/llvm/tools/llvm-mca

Quick Start

安装

下载可执行文件上传服务器,解压

安装遇到的问题

  1. cannot find libtinfo.so.5
  2. sudo apt install libncurses5
  3. ln -s /usr/lib/libncursesw.so.6 /usr/lib/libtinfo.so.5 或者类似的 ln -s /usr/lib/libncurses.so.5 /usr/lib/libtinfo.so.5
  4. 在/snap/core下找到了,但是这是什么目录?是之前Ubuntu的包管理工具,但是已经不用了。

从源码安装

node5

由于之后要写代码的,还是从头安装更好。

cd llvm-project
mkdir build
cmake -S llvm -B build -G "Unix Makefiles" -DLLVM_ENABLE_PROJECTS="clang;llvm-mca" -DCMAKE_INSTALL_PREFIX="~/Install/llvm" -DCMAKE_BUILD_TYPE=Debug -DLLVM_ENABLE_ASSERTIONS=On
cd build
make -j32
make install

kunpeng

cmake -S llvm -B build -G "Unix Makefiles" -DLLVM_ENABLE_PROJECTS=all -DCMAKE_INSTALL_PREFIX="~/Install/llvm" -DCMAKE_BUILD_TYPE=Debug -DLLVM_ENABLE_ASSERTIONS=On
#change cmake or -DLLVM_ENABLE_PROJECTS="all"
error
g++: error: unrecognized command line option ‘-mllvm’
g++: error: unrecognized command line option ‘--tail-merge-threshold=0’
g++: error: unrecognized command line option ‘-combiner-global-alias-analysis’
change
cmake -S llvm -B build -G "Unix Makefiles" -DLLVM_ENABLE_PROJECTS="clang;llvm-mca" -DCMAKE_INSTALL_PREFIX="~/Install/llvm" -DLLVM_TARGETS_TO_BUILD=AArch64 -DCMAKE_BUILD_TYPE=Debug -DLLVM_ENABLE_ASSERTIONS=On

使用

clang foo.c -O2 -target x86_64-unknown-unknown -S -o - | llvm-mca -mcpu=btver2
由于不是X86,llc --version 查看到target是 aarch64-unknown-linux-gnu
clang /home/shaojiemike/Download/llvm-project-main/lldb/test/API/lang/c/forward/foo.c -O2 -target aarch64-unknown-linux-gnu -S -o -|llvm-mca -timeline -show-encoding -all-stats -all-views
生成汇编代码,并默认管道到llvm-mca,并开启所有输出。

可以看出是用TSV110Unit的port,默认cpu是tsv110

名词解释

ALU/BRU

算数逻辑单元 ALU 负责处理整数运算指令. 跳转处理单元BRU 负责处理跳转指令. BRU 可以与 ALU 合并, 复用 ALU 的逻辑来计算跳转指令的条件和跳转地址, 也可以作为一个单独的功能单元接入到流水线中.

MDU

乘除法单元 MDU (mult-divide unit)

需要进一步的研究学习

  1. llvm-mca微指令怎么实现的,怎么把汇编变成微指令
  2. 在view里加memory的实现
  3. 考虑了cache命中等影响 https://github.com/andreas-abel/uiCA uops
  4. 鲲鹏架构 https://bbs.huaweicloud.com/community/usersnew/id_1513665626477516

遇到的问题

  1. llvm-mca -mcpu=help竟然会卡住,不知道为什么
  2. 所以说是华为已经写了一个叫tsv110的,实现2个功能?

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

参考文献

样例输出

Iterations:        100
Instructions:      200
Total Cycles:      70
Total uOps:        200

Dispatch Width:    4
uOps Per Cycle:    2.86
IPC:               2.86
Block RThroughput: 0.5


No resource or data dependency bottlenecks discovered.


Instruction Info:
[1]: #uOps
[2]: Latency
[3]: RThroughput
[4]: MayLoad
[5]: MayStore
[6]: HasSideEffects (U)
[7]: Encoding Size

[1]    [2]    [3]    [4]    [5]    [6]    [7]    Encodings:                    Instructions:
 1      1     0.33                         4     20 00 80 52                   mov  w0, #1
 1      1     0.50                  U      4     c0 03 5f d6                   ret


Dynamic Dispatch Stall Cycles:
RAT     - Register unavailable:                      0
RCU     - Retire tokens unavailable:                 0
SCHEDQ  - Scheduler full:                            0
LQ      - Load queue full:                           0
SQ      - Store queue full:                          0
GROUP   - Static restrictions on the dispatch group: 0


Dispatch Logic - number of cycles where we saw N micro opcodes dispatched:
[# dispatched], [# cycles]
 0,              20  (28.6%)
 4,              50  (71.4%)


Schedulers - number of cycles where we saw N micro opcodes issued:
[# issued], [# cycles]
 0,          3  (4.3%)
 2,          1  (1.4%)
 3,          66  (94.3%)

Scheduler's queue usage:
No scheduler resources used.


Retire Control Unit - number of cycles where we saw N instructions retired:
[# retired], [# cycles]
 0,           3  (4.3%)
 2,           1  (1.4%)
 3,           66  (94.3%)

Total ROB Entries:                128
Max Used ROB Entries:             59  ( 46.1% )
Average Used ROB Entries per cy:  32  ( 25.0% )


Register File statistics:
Total number of mappings created:    100
Max number of mappings used:         29


Resources:
[0.0] - TSV110UnitAB
[0.1] - TSV110UnitAB
[1]   - TSV110UnitALU
[2]   - TSV110UnitFSU1
[3]   - TSV110UnitFSU2
[4.0] - TSV110UnitLdSt
[4.1] - TSV110UnitLdSt
[5]   - TSV110UnitMDU


Resource pressure per iteration:
[0.0]  [0.1]  [1]    [2]    [3]    [4.0]  [4.1]  [5]    
0.66   0.67   0.67    -      -      -      -      -     

Resource pressure by instruction:
[0.0]  [0.1]  [1]    [2]    [3]    [4.0]  [4.1]  [5]    Instructions:
0.33    -     0.67    -      -      -      -      -     mov w0, #1
0.33   0.67    -      -      -      -      -      -     ret


Timeline view:
Index     0123456789

[0,0]     DeER .   .   mov  w0, #1
[0,1]     DeER .   .   ret
[1,0]     DeER .   .   mov  w0, #1
[1,1]     D=eER.   .   ret
[2,0]     .DeER.   .   mov  w0, #1
[2,1]     .DeER.   .   ret
[3,0]     .D=eER   .   mov  w0, #1
[3,1]     .D=eER   .   ret
[4,0]     . DeER   .   mov  w0, #1
[4,1]     . D=eER  .   ret
[5,0]     . D=eER  .   mov  w0, #1
[5,1]     . D=eER  .   ret
[6,0]     .  D=eER .   mov  w0, #1
[6,1]     .  D=eER .   ret
[7,0]     .  D=eER .   mov  w0, #1
[7,1]     .  D==eER.   ret
[8,0]     .   D=eER.   mov  w0, #1
[8,1]     .   D=eER.   ret
[9,0]     .   D==eER   mov  w0, #1
[9,1]     .   D==eER   ret


Average Wait times (based on the timeline view):
[0]: Executions
[1]: Average time spent waiting in a scheduler's queue
[2]: Average time spent waiting in a scheduler's queue while ready
[3]: Average time elapsed from WB until retire stage

      [0]    [1]    [2]    [3]
0.     10    1.7    1.7    0.0       mov    w0, #1
1.     10    2.0    2.0    0.0       ret
       10    1.9    1.9    0.0       <total>

HPCthreeLaws

Amdahl's law

默认问题大小是固定的,导致最终可加速的倍率有上限 s是并行部分的加速比,p是可并行部分。

Gustafson's law

默认问题总时间固定,比如串行时间a,并行时间b,并行部分加速就是核数n, 并行部分就是\(F=\frac{a}{a+b}\)\(\(执行时间=a+b\)\) \(\(系统总执行时间=a+nb\)\) \(\(S=\frac{a+nb}{a+b}=F+n(1-F)\)\) 意义在于,当并行部分较多时,加速比与核数成正比。

Sun-Ni's Law

内存受限系统的加速比

这里的具体计算去看wiki

需要进一步的研究学习

暂无

遇到的问题

暂无

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

参考文献

Static Code Analyzer on Kunpeng Overview

Static Code Analyzer Overview

What Is Static Analysis?

一种通过在程序运行之前自动检查源代码的调试方法。

What Is Static Code Analysis?

经常和source code analysis结合(貌似sourcetail的代码结构分析?

可以分析addresses weaknesses漏洞

IPC - Instructions per cycles

Throughput and Critical Path Analysis

好吧,都是机密,就不写了。

Chen advise

提高访存的方法 C-AMAT

目标

机密

需要进一步的研究学习

暂无

遇到的问题

暂无

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

参考文献