418 L04 Parallel Programming Basics

步骤

• Decomposition
  • 由程序员完成，缺乏对应的编译器
  • Amdahl’s Law：一段代码中无法并行的部分所占比例为s，有p个处理器，则并行的最大加速为$1/(s+\frac{1-s}{p})$
• Assignment
  • 目标：负载平衡、减少通信代价
  • 静态分配
  • 动态分配：（线程池？？）在完成当前任务后，线程自动接收下一个任务
• Orchestration
  • 目标：降低通信/同步的代价，降低负载，保持数据局部性？？
  • 取决于硬件条件
• Mapping
  • 操作系统（pthread），编译器（ISPC），硬件（CUDA thread）
• 注意采用不同的并行方法时，处理器之间交换数据的量
• 同步原语：
  • 互斥锁

      float sum = 0;  // global variable
      void f1()   // SPMD code
      {
          for(...){
              lock();
              sum += 1;
              unlock();
          }
      }
      void f2()
      {
          float local_sum = 0;    // local variable
          for(...) 
          {
              local_sum += 1;
          }
          lock(); // lock放在循环外面
          sum += local_sum;
          unlock();
      }
    

  • memory barrier：所有线程会先完成barrier之前的计算，然后完成barrier之后的。

      float sum;
      void f1()
      {
          for(...){
              sum=0;
              barrier1(); // start barrier
              sum.....;
              barrier2(); // lot of things with barrier
              sum.....;
              barrier3(); // end barrier
          }
      }
    
      float sum[3];       // 连续循环中利用多个全局变量移除依赖性，减少barrier数量
      void f2()
      {
          sum[0] = 0;
          barrier();      // one-time, for init
          for(...){
              sum[(index+1)%3] = 0;
              barrier();  // lot of things with barrier
              index = (index+1)%3;
          }
      }
    

  • 消息传递？？？