Skip to content

Instantly share code, notes, and snippets.

@billxc

billxc/gist:c3032a740d37df4b39ba

Last active August 29, 2015 14:24
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save billxc/c3032a740d37df4b39ba to your computer and use it in GitHub Desktop.
Save billxc/c3032a740d37df4b39ba to your computer and use it in GitHub Desktop.
Download ZIP
Raw
gistfile1.md

#期末复习 ###PPT2：

  • 并行计算的意义
    • 并行计算是解决计算挑战的必由之路
    • ** 并发与并行的区别√**
  • 扩展性 -A computer system, including all its hardware and software resources, is called scalable if it can scale up (i.e. improve its resources) to accommodate ever-increasing performance and functionality demand and/or scale down (i.e. decrease its resources) to reduce cost.
    • Resource Scalability
    • Application Scalability
    • Technology Scalability
  • 加速比
    • 概念
      • 描述对程序并行化之后获得的性能收益
    • 计算公式
      • S: 程序中串行部分的比例，n: 机器规模（或处 理器核的数目）
      • nt = 最优串行算法执行时间/并行程序执行时间
      • 定律
      • Amdahl定律
        • 固定问题规模（工作负载）， 减少响应时间
        • 加速比 = 1/(S + (1-S)/n)
      • Gustafson定律
        • 固定计算时间，扩大问题 规模，提高计算精度
        • 扩展加速比=(1-S) * n + S

###PPT3：

  • ** Flynn分类法（根据同时执行的指令数和数据流来分类） **

    • SISD (Single Instruction , Single Data stream)
      • 传统的机器
    • SIMD
      • 矢量运算
    • MISD
      • 不存在的机器，或者用于容错率
    • MIMD
      • General Purpose Parallel Machines
      • MIMD works asynchronously

  • spmd（了解）

    • Single Program, Multiple Data
    • Multiple autonomous processors simultaneously executing the same program (but at independent points, rather than in the lockstep that SIMD imposes) on different data.

  • 共享存储器的层次结构

  • 并行计算中的操作和开销

    • 操作
      • Computation operations 计算操作
      • Parallel operations 管理进程操作
      • Interaction operations 进程间同步操作
    • 开销
      • Prarllelism overhead 进程管理产生的开销
      • Communication overhead 交换信息产生的开销
      • Synchronization overhead 执行同步指令的开销
      • Load imbalance overhead 负载不均开销（当某些处理器空闲，某些处理器忙碌时产生的开销）

  • PRAM模型，例子好好看

    • Parallel Random Access Machine
    • 同构性 n=1, SISD; n>1, MIMD
    • 同步性
      • 指令级同步
    • 交互机制
      • 进程间通过共享变量（或共享存储器）进行交互
    • 地址空间
      • 单地址空间；均匀存储器访问
    • 存储器模型
      • EREW
    • 应用
      • 问题：n个处理器的EREW PRAM 上，对两个N维向量A、B求内积S，当N很大时，加速比为多少？（假设乘法和加法各占一个时钟周期）
      • 串行：2N-1个周期
      • 并行：[2N-1-(n-1)]/n + logn 个周期
      • 加速比： n/{1+[(nlogn-n+1/(2N-1))]}
      • 特别N>>n时，加速比近似为n
    • 优缺点
      • 优点
        • 简单。多数的理论并行算法，均用PRAM模型或其变异加以描述。也被广泛用来分析并行计算复杂度
      • 缺点
        • 对零通信开销和指令集同步的不现实假设

  • APRAM 不考

  • BSP 看

    • 客服PRAM模型的缺点，保留其简单性
    • 一个BSP计算机由n个处理器-存储器对（节点）组成，他们之间借助通信网络进行互连。
    • 分布式存储的MIMD模型
    • 特点
      • MIMD
      • 超步 计算 通信 路障
      • 可变颗粒度
      • 松同步
      • 非零开销
      • 消息传递或共享变量
    • W：每个超步内的最大计算时间 L：路障同步开销 G：发送每条消息的开销
    • BSP模型中，计算由一系列由同步路障分 开的超步级(superstep)组成。

  • 多级存储结构 看

    • 为了解决内存墙(memory wall)性能瓶颈问题。
    • 在节点内部的cache称为二级cache(L2 cache)。
    • 在处理器内部更小的cache成为一级cache(L1 cache)。
    • L1 cache连接 CPU寄存器和L2 cache，负责缓存L2 cache中的数据到寄存器中
    • 映射策略
      • 直接映射策略
      • n路组关联映射策略
      • 全关联映射策略

  • 并行计算机访存模型

    • UMA (Uniform Memory Access) 模型
      • 物理存储器被所有节点共享
      • 所有节点访问任意存储单元的时间相同
      • 放生访问竞争时，种菜策略平等对待每个节点，即每个节点机会均等；
      • 各节点的CPU可以带有局部私有高速缓存
      • 外围I/O设备也可以共享，且每个节点有平等的访问权利。
    • NUMA (Non-Uniform Memory Access) 模型
      • 物理存储器被所有节点共享，任意节点可以直接访问任意内存模块
      • 节点访问内存模块的速度不同，访问本地存储的速度一般是访问其他节点内存模块的3倍以上
      • 发生访问竞争时，仲裁策略对节点可能是不等价的
      • 各节点的CPU可带有局部私有告诉缓存
      • 外围的I/O设备也可以共享，但对各个节点是不等价的。

  • COMA NOMA 不考

  • CC-NUMA 不考

  • 物理机模型（看）

    • SMP(Symmetric Multi-Processor)
      • Pros
        • 结构对称，采用单一操作系统
        • 所有处理器通过告诉总线或交叉开关与共享存储相连，具有单一的地址空间
        • 通过写/读共享变量完成通信，快捷且编程比较容易
      • Cons
        • 存储器和I/O负载大，易成为系统的瓶颈，限制了系统中处理器的数量
        • 单点失效就会导致整个系统的崩溃
        • 一次成型，扩展性差
    • PVP(Parallel Vector Processors)
    • MPP(Massive Parallel Processor)

      • 专门设计制造高速互连网络

      • 结点内有一个或多个处理器、高速缓存、一个本地存储器和互连网络

      • 每个处理器能访问的只有本地存储器，而不能访问其它处理器的存储器

      • 程序由多个进程组成，每个都有其私有空间，进程间采用消息传递相互作用

      • 使用专用硬件提升性能，技术复杂，成本高

    • Cluster
      • Cluster的每个节点都是一个完整的计算机
      • Cluster各节点都有本地磁盘
      • 哥哥节点通过低成本的商用网络互连
      • 节点与系统网络的网络接口是连接到I/O总线上的(松耦合)，而MPP的网络接口是连接到节点的存储节点上的(紧耦合)
      • 每个节点上有完整的操作系统

###并行编程基础

  • 并行编程模型（3种）

    • 共享存储器编程
    • 消息传递编程
    • 数据并行编程

  • 显式、隐式并行

    • 显式并行
      • 在源程序中由程序员使用专用语言构造、编译器命令或库函数对并行性加以显示说明
      • 共享变量模型、消息传递模型、数据并行模型
    • 隐式并行
      • 程序员不显式地说明并行性，而是让编译器或运行支持系统自动加一开发
      • 并行化编译器、运行时间并行化

  • 考编程题

  • 各个编程模型的特点（详论述） | 特征 | 消息传递 | 共享存储 | 数据并行 | |-----------|--------| |典型代表 |MPI,PVM |OpenMP |HPF,IPP| |可移植性 |所有主流并行计算机 |SMP,DSM |SMP,DSM,MPP| |并行粒度 |进程级最大粒度 |线程级细粒度|进程级细粒度| |并行操作方式|异步 |异步 |松散同步| |数据存储方式|分布式存储 |共享存储 |共享存储| |数据分配方式|显示 |隐式 |半隐式| |学习入门难度|较难 |容易 |偏易|

  • 分解——将应用程序划分成多个独立的任务，并确定这些任务之前的相互依赖关系（相关性）

    • 任务分解

      • 根据功能分解

    • 数据分解

      • 数据层级的并行

    • 数据流分解

    • 总结 |分解方式|设计|说明 |---| |任务分解|不同的程序行为采用不同的线程或进程实现|常用于GUI应用程序| |数据分解|多个进程或者线程对不同的数据块执行相同的操作|常用于音频、图像处理和科学计算应用程序| |数据流分解|对数据处理阶段的不同操作进行分解|应注意尽量消除启动和排空延迟|

  • 范型或者模式

    • 任务并行
      • 阶段并行(Phase Parallel)
    • 分治法
    • 几何分解
    • 流水线
    • 总结
    • |范例或模式 |分解方式| |----| | 阶段并行 | 任务分解 / 数据分解| |分治模式 |任务分解 / 数据分解 | |几何分解模式 |数据分解 | |流水线模式 | 数据流分解 |

###并行编程 ####WinAPI

API用法看过一遍，知道是干啥用的，参数需要知道有几个参数，参数的意义

  • 创建线程

  • 管理线程

  • 线程同步

    • 事件、其他同步对象、互锁函数(原子操作)
    • 消息队列

  • 其他

    • 线程池
    • 线程优先级
    • 处理器亲和

  • 创建线程

    • CreateThread() & ExitThread() 最基础、最简单 
      • CreateThread( 
   lpThreadAttributes , 
   dwStackSize , 
   lpStartAddress ,
   lpParameter ,
   dwCreationFlags ,
   dwCreationFlags ,
   lpThreadId )

      - void ExitThread(dwExitCode)

- ThreadFunc(data) { 
 //do the work of the thread 
    return 0; }
    • _beginthreadex() & _endthreadex() 广泛使用
      • _beginthreadex( security , stack_size, start_address, arglist , initflag , threadID )
      • _endthreadex(retval);
      • 只存在于C/C++运行时库的多线程版本中
      • 封装CreateThread() & ExitThread()
    • AfxBeginThread() & AfxEndThread() for MFC

  • Linux

  • OMP 编程或者读题，重点是新功能和数据环境

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment