网站 要强化内容建设,微信公众号管理工具,公明 网站建设,淄博网站设计制作Basics of Parallel Programming 并行编程的基础 核达到了上限#xff0c;无法越做越快#xff0c;只能通过更多的核来解决问题 Process 进程 有独立的存储单元#xff0c;系统去管理#xff0c;需要通过特殊机制去交换信息 Thread 线程 在进程之内#xff0c;共享了内存…Basics of Parallel Programming 并行编程的基础 核达到了上限无法越做越快只能通过更多的核来解决问题 Process 进程 有独立的存储单元系统去管理需要通过特殊机制去交换信息 Thread 线程 在进程之内共享了内存。线程之间会分享很多内存这些内存就是数据交换的通道。 管理Tasking的方法 Preemptive Multitasking 抢占式多任务 当这个线程/任务在跑时调度者scheduler决定中断和返回。任务自身无法决定 Non-preemptive Multitasking 非抢占式多任务 反过来让任务自身决定何时结束。好处是如果任务全都是自己给的控制能力较强。但是容易发生卡死。比较少用多用于一些实时性非常高的操作系统中 线程的切换很贵 一个线程被中断的话是非常费的至少需要2000 多个CPU cycle 并且新调进来的线程数据不在各级缓存中得从内存中重新调用时间可能需要 10000 ~ 1000000 多个CPU cycle Job System就是用来解决这些问题 并行化编程的两个问题 1.Embarrassing Parallel Problem 让线程各自自主运行完毕不会打断线程不存在swaping 线程的问题。就是一堆独立的问题各自算完然后收口。例如Monte Carlo 积分的算法 2.Non-Embarrassing Parallel Problem 但是真实游戏案例里无法把一个游戏所需的模拟分的那么清楚各个系统之间有很多数据的依赖 Data Race 数据抢占。当读取和写入发生在一个数据但是不同线程里会导致读取后和操作时数据不一致 Locking Primitives 锁算法 Critical Section这段代码只有当前线程可执行并且相关数据只归于当前线程其他线程不得修改。 是阻断式编程 阻断式编程 可能产生死锁。线程未解除锁定将卡死并导致后续相关线程也卡死 在大型系统上百个任务中无法保证每个任务一定会成功一个任务的失败可能导致整个系统的死锁 当高优先级的任务进来后无法打断正在运行的低优先级任务任务优先级失去了意义 因此lock尽量少用 原子性操作 在硬件底层实现保证对变量的读写操作不会被多个任务抢占 Load从内存中加载到一个对于Thread安全的存储空间再查看数值 Store将数据写入内存
核心的想法是避免锁住整段代码。保证执行的指令中对这一个数值的内存的操作是原子性的 空洞代表cpu正在等待 lock free编程避免死锁 wait free理论上的方式通过一套数学方法尽可能避免cpu等待 cpu利用率100%几乎不可能。但是具体的比如堆栈或者队列的操作是可以做到wait free。比如高频的通讯协议。 需要严格的数学推演证明 高级语言在编译器编译后无法知道具体的汇编语言的顺序只保证结果是一致的但是会在多线程中出现很大问题 期望的逻辑是 线程1里a先等于2b在等于0 线程2里监测b等于0的时候a应该要等于2 但实际编译器优化后会任务a和b是两个无关的变量 线程1里有可能b赋值给一个临时变量然后b被赋值为0a还未被赋值2之后a是用临时变量来赋值2 此时线程2里看到了b等于0时a等于2是不成立的 这是并行开发非常容易出现问题的地方 每个CPU和每个不同的架构都会导致不同的顺序 常出现的是PC模拟器上和实机的运行是完全不一致的
C 11 中可以通过显式的要求执行顺序但是性能更低
乱序的原因有大量的数据存储读取因为cpu通常是饥饿的等待数据不会等待指令一条条执行根据指令读取数据而是整块指令和数据混在一整块在cpu中运行
这也是debug正常但release失效的原因。因为debug往往是顺序的但是release是乱序
Parallel Framework of Game Engine 游戏引擎的并行框架 Fixed Multi-Thread 固定多线程 大部分传统引擎的做法根据Task分类成固定的线程彼此之间不侵犯在每个Frame开始的时候交换数据。 在2-4核的情况下较好。 但是很难保证四个线程的workload是一样的会有的轻有的重是个木桶效应所有线程要等待最慢的线程完成任务。 并且很难把负载重的任务分出来给其他闲置的线程。因为通常一个线程访问的数据是尽可能地在一块地方。以保证数据是安全的。另一原因是不同场景不同线程的负载不一样在风景的场景里渲染压力大战斗场景里模拟线程压力大 大概会有1/3的资源浪费 如果固定的线程高于电脑配置的核数还是会发生线程抢占问题。而8核16核的电脑会有浪费 Thread Fork-Join 提取出游戏中一致性非常高但是计算量很大比如动画物理模拟的一些运算到一定时间这些固定好的线程会Fork一些子任务出来专门传递到Work Thread预先申请好的然后计算完后回收Task的结果 可以动态的生成work thread 很多基于unity和unreal的游戏都是这种做法 但还是会造成cpu闲置 虚幻中提供两种Thread Named Thread 明确的告诉是给Game LogicRender 等 Worker Thread用于处理物理动画粒子等 一种更加复杂的架构 可以创建很多任务设置好任务的dependency都扔给核去处理核会自动根据任务之间的dependency来决定执行顺序和并行任务 游戏是有很强的dependency的Task Graph具体实现 在代码中直接加入Link构建好dependency后自动生成Graph 问题 task树的构建是不透明的 真实游戏引擎里task的dependency是动态的不是静态的task graph动态的生成节点是非常复杂的早期并没有wait功能
Job System 协程 是非常轻量的多线程执行的一种方式 实际上是通过Yield可以从函数执行的任意阶段跳出挂起让出执行权。然后可以通过Invoke激活从跳出的节点继续执行 核心就是在任务执行中间能让道出去并且能回来 现代高级语言里很多原生支持如c#go。但c里协程很难实现 线程是一个调硬件的中断也就是整个环境context栈stack都会重置所以创建和中断的消耗性能非常高是直接通知到操作系统的 OS 协程是由程序自己定义的在一个线程里可以在很多的协程里来回切换从cpu上看还是在一个线程里通过程序来定义切换和激活并没有激活核的切换 有栈协程 关键是跳出再重新激活后本地的变量是不会被污染或清空的 无栈协程 相当于本地的变量直接清空。c中实现就相当于汇编中的Go To。对实施者要求很高一旦没写好会产生大量的bug 最大的好处是不需要保存和恢复整个栈的状态切换成本很低。一般是非常底层可能用到 Stackful 是更适合面向更多开发者的协程 Stackless 是用在更加底层只有少数人用的需要更多知识经验的人
协程一个很大的难点在于在不同的操作系统包括原生语言cc汇编语言等底层语言并不支持协程的机制。不同平台需要不同的机制 基于光纤的任务系统 高速的线程管道可以高速的载入各种Job并且自由的进行协程切换, 同时Job还可以设置dependency和priority。 该申请多少个Work Thread? 尽可能的一个work thread 对应一个 核可以是逻辑核可以是物理核一般是逻辑核 让thread的swap几乎为0 一个个生成的Job直接载入Thread然后处理 Job有优先级和依赖问题 根据Job的优先级依赖关系和Work Thread 的饱和状态分配Job给working thread 与 Fork-join不同的就是在这里是一个全并行化的方法 执行模型先进先出先进后出 游戏引擎的工程实现中实现Job System时一般会有LIFO。因为游戏里很多job的产生都是前一个job执行到一半可能会产生多个不同的job。彼此之间是dependency的关系。也就是所当前job所产生的新的job如果未完成的话自身是执行不了的。因此是先进后出的模型。类似堆栈 Scheduler会把Yield的Job扔到一个waiting list里。然后执行下一个任务 因为并不能预估每个Job所需要占用的时间 比如 等待IO 复杂的运算产生非常多的dependency等 从而导致Work Thread的分配不均 Scheduler会通过Job Stealing 把重负担Work Thread未执行的任务分配给空闲的Work Thread 优点 容易实现schedule 容易设计依赖关系 每个堆栈彼此独立 不存在 Thread Switch 缺点 C不能原生支持可以参考Boost源码 不同OS实现方法不同 具体的底层工程非常复杂
Programming Paradigms 编程范式 早期就是POP为主 现代基本都是OOP OOP问题1: 有很多二义性。也就是设计上的问题 如上图例子是在玩家里写攻击敌人还是敌人里写收到攻击 即一个动作function归属于哪个类 而且不同的人对于这个的写法是不一致的 问题2:OOP是一个非常深的继承树。 如上图就受到魔法伤害这个Function来说到底是写在Go那一层还是Monster这一层还是具体的蜘蛛怪物这一层 且每个人对这个问题的看法是不一样的。 问题3:基类会非常庞大臃肿派生类可能只需要基类的几个功能 问题4:OOP的性能很低。 内存是分散的数据会被分散到各个object里 虚函数在内存上各种跳跃函数的重载会有很多指针导致代码执行时跳来跳去 问题5:OOP的可测试性。 OOP测试需要创建所有的环境所有的对象。来测试其中的某个函数是否正确。因为所有的数据被包含在对象当中。对象一层套一层很难写单元测试
Data-Oriented Programming 面向数据编程 CPU的速度越来越快但是内存的访问速度是跟不上导致现代计算机有很复杂的缓存机制 Cache 缓存 L1 Cache就是距离CPU最近的缓存速度最快 L2 Cache是稍微远点的速度略逊于L1 L3 Cache是直接链接内存的速度也是Cache里最慢的 cpu从L1开始一层层查询数据 想cache友好要尊从数据紧凑型。即数据尽量呆在一起 SIMD对4个float的加减乘除看作一个vector一次性做完一次性读4个空间一次性写4个空间。大部分硬件都有支持 LRUCache被填满后 → 最近还在使用的留住 → 最近没用的东西剔除 还有一种随机剔除算法基于概率 每次读写取的是一个cache line。 假设有一个数据这个数据在各级cache之间。每个cache和memory都有一段cpu要保证三个cache和memory中的数据都是一致的。因此是一层层读取一层层写到内存这也是为什么逐行读取数据的效率会比逐列读取数据的效率快上很多倍原因原因就是往下读会导致跳跃Cache Line 造成 Cache Miss DOP的核心思想游戏世界里所有的表达都是数据 代码自身也是数据 主要考虑的就是尽量减少Cache Miss的问题 在DOP中会把数据和代码看作一个整体尽可能保证数据和代码在cache中紧密地在一起内存中可能是分开的。保证代码执行完后数据刚好能处理完。 相当于数据的处理者和要处理的数据是在一起的 例子 把Cache看作一家工厂而言code是工人数据就是产品的材料每个工人都只能处理特定的材料 如果发生在工厂里的材料不是工厂里的工人能够处理的就需要材料等可以处理的工人进来 或者工厂里的功人不能处理现在工厂里的材料也就需要等待新的材料进来 所以最佳实践就是工人和对应能处理的材料一起进入工厂这也就是DOP想要实现的东西
Performance-Sensitive Programming 性能敏感编程 减少执行顺序的依赖度让代码之间的执行尽量不存在上下依赖关系 有两个函数一个在读一个在写同一个变量时当两个线程同时读写的变量在同一个cache line里会加重系统负载 因此要尽量避免两个线程会同时读写一个cache line。即不要让两个线程同时访问很碎的数据尽量让每个线程访问的数据就是自己的一块 现代CPU中会对 Branch 语句比如If 或者 Switch进行优化会直接把预测执行的代码直接加载到cache里。如果发现条件不满足则要swap掉提前加载好的代码可能需要到冷数据内存或硬盘中去读取会等很久 上述例子会反复在ifelse之间跳动从而导致反复切换cache导致性能下降的很低1 优化方式是执行前先进行一次排序。这样只需要执行一次cache切换 提前将数据分组避免复杂的 If 和 Else 使用不同的容器来分组数据让一组容器对应一个处理代码从而减少处理代码在Cache中的swap
Performance-Sensitive Data Arrangements 性能敏感数据编程 当使用OOP的思想去定义一个东西一般使用的是Structure来定义其属性而每一个这个东西都是使用这个整的structure来定义。如左图所示的粒子的定义。这就是AOS架构 这样来定义的话假设我希望修改所有粒子的位置和速度我们却需要去跳跃内存中的其他属性比如颜色和生命周期这样就不利于高性能编程 但是如果使用SOA就可以直接把一整个数组pass进Cache处理会高效很多这样的思想就很像写Shader因为GPU天生的就是数据驱动的
Entity Component System ECS 架构 Component-Based系统最自然的实现方式是使用OOP的方式来实现 但是会导致很多问题 过多的虚函数指针问题 大量的代码是分散在各个类里 数据也是非常分散的 这样的代码实现效率是非常低的 Entity非常轻量就是一个idid指向了一组component。即用了哪些数据 Component一块数据。没有任何业务逻辑没有任何借口。纯数据注意之前讲的Component base有很多接口如ticksetPropertygetProperty。可以进行读写操作但是他本身并不知道自己的意义 System用于处理component。业务逻辑所在地。可能会同时处理好几类的数据。例如有一个moving system根据速度该position。health system会根据damage去调整health的值。
ECS 本质是一个理论框架目的是充分利用Cache多线程和DOP的特性达到高效的目的 是类似于模板或者原型的概念 比如一个NPC就需要几个特定的Component Archetype类似 type of GO
目的是当ECS对上千个Entity检查的时候不能去一个一个与检查Entity是否有特定的Component这个访问就很慢。但是Archetype就节省了很多步骤。 Chunk 将内存定义成一个个Chunk, 然后把一类Archetype的所有的Component按照他的类型一个个去放进去。 一个Chunk里一定是同一类的Archetype 好处是当为了需要处理这个Chunk的时候可以直接提取整条的数据没有损耗的忽略其他数据 大部分CPU操作的耗时
