多核多线程复习

lesson1

1. 多核的概念
   单芯片多处理器，简称CMP
   例题：
   为什么说从单核到多核的转变成为不可避免的历史趋势:(D)
   A. 指令级并行的局限
   B. 能耗与散热
   C. 内存墙问题
   D. 以上都是
2. 弗林分类（缩写也要记住）：
   单指令流单数据流(SISD)
   单指令流多数据流(SIMD)
   多指令流单数据流(MISD)
   多指令流多数据流(MIMD)
   例题：
   阵列处理机又称为并行处理机,它的体系结构属于_______计算机。(B)
   A.SISD
   B.SIMD
   C.MIMD
   D.MISD
   弗林(Flynn )根据指令流和数据流的不同组织方式,把计算机系统的结构进行了分类,以下属于弗林分类的是:(ABCD )
   A. 单指令流单数据流(Single Instruction stream Single Data stream – SISD)
   B. 单指令流多数据流(Single Instruction stream Multiple Data stream – SIMD)
   C. 多指令流单数据流(Multiple Instruction stream Single Data stream – MISD )
   D. 多指令流多数据流(Multiple Instruction stream Multiple Data stream – MISD )
   以下哪个不属于SIMD。(D)
   A. 并行处理机
   B. 阵列处理机
   C. 向量处理机
   D. 标量流水线处理机
3. 进程与线程的区别、线程状态
   进程拥有独立的地址空间，而线程和其他线程共享进程的地址空间。
   进程之间的通信可以使用操作系统原语或通过共享存储空间来实现，而线程使用当前程序设计语言的原语或者通过进程共享空间来实现通信。
   进程上下文的切换是重量级的，进程所有状态都要保存。而线程之间的切换是轻量级的，只需要保存当前寄存器的状态
   例题：
   什么是线程、进程,它们之间的关系是什么?
   答:进程是一组离散的(执行)程序任务集合;线程是进程上下文中执行的代码序列,又被称为轻量级进程。进程中可包含一个或多个线程。
   对于进程,以下表述不正确的是:(D )
   A. 进程是指程序在一个数据集合上运行的过程
   B. 进程是系统进行资源分配和调度运行的一个独立单位
   C. 在操作系统中引入进程的目的,是为了使多个程序并发执行,以改善资源利用率及提高系统的吞吐量
   D. 在操作系统中引入进程的目的,是为了减少程序并发执行时所付出的时空开销,使操作系统具有更好的并发性
   对于线程,以下表述不正确的是:( C )
   A. 线程是进程中的一个实体,是被系统调度和分配的基本单元
   B. 每个程序至少包含一个线程,那就是主线程
   C. 线程自己只拥有很少的系统资源,且不可与同属一个进程的其他线程共享所属进程所拥有的全部资源
   D. 同一进程中的多个线程之间可以并发执行,从而更好地改善了系统资源的利用率
   以下表述不正确的是:( C )
   A. 人们习惯上称线程为轻量级进程(lightweight process, LWP ),线程是CPU 调度和分派的基本单元
   B. 在创建或撤消进程时,系统都要为之分配或回收资源
   C. 进程切换的开销也远小于线程切换的开销
   D. 线程切换只需保存和设置少量寄存器的内容,并不涉及存储器管理方面的操作
   在操作系统中引入进程的目的是:(A )
   A. 提高系统吞吐量
   B. 减少程序并发执行时所付出的时空开销
   C. 便于组织程序逻辑
   D. 以上都正确
   在操作系统中引入线程的目的是:(B )
   A. 提高系统吞吐量
   B. 减少程序并发执行时所付出的时空开销
   C. 便于组织程序逻辑
   D. 以上都正确
   ______是CPU 调度和分派的基本单位,______是资源拥有的基本单位。(D)
   A. 线程,线程
   B. 进程,线程
   C. 进程,进程
   D. 线程,进程
4. 进程状态及其转换
   
   例题：
   对于线程生命周期,以下表述正确的是:(D )
   A. 系统中的每个线程都有一个从创建到消亡的过程,我们把这一过程称作该线程的生命周期。
   B. 线程生命周期包括创建、就绪状态、运行状态、等待状态和消亡
   C. 就绪状态的线程运行所需的一切条件都得到满足,已获得必要的资源和设备。但因处理器资源个数少于线程个数,所以该线程不能运行,而必须位于队列中等待分配处理器资源
   D. 以上都正确
5. 片上多核处理器（单芯片多处理器）
   片上多核处理器（Chip Multi-Processor，CMP）就是将多个计算内核集成在一个处理器芯片中，从而提高计算能力。
6. 计算机硬件工艺发展顺序
   电子管数字计算机、晶体管数字计算机、集成电路数字计算机、大规模集成电路数字计算机
   全世界第一台全自动电子数字计算机ENIAC 于哪一年研制成功?(B )
   A.1944 年
   B.1945 年
   C.1946 年
   D.1947 年
   计算机的硬件工艺发展顺序是:(A )
   A. 电子管数字计算机、晶体管数字计算机、集成电路数字计算机、大规模集成电路数字计算机
   B.晶体管数字计算机、电子管数字计算机、集成电路数字计算机、大规模集成电路数字计算机
   C.电子管数字计算机、集成电路数字计算机、大规模集成电路数字计算机、晶体管数字计算机
   D. 电子管数字计算机、集成电路数字计算机、晶体管数字计算机、大规模集成电路数字计算机

lesson2

1. 多核多线程开发流程
   
   其中，第三步确定分解模式有：分任务、分数据、分数据流
   第五步选择并行模型有：Win32,OpenMP,MPI,TBB
2. 分解模式
   任务分解、数据分解、数据流分解
   数据分解：减少数据的关联性 接触面积小点 （ppt第九页）
3. 处理数据依赖的方法
   变量本地化（减少数据关联），改造变量，规约（前提：切片），明确的同步机制

lesson3

1. 句柄
   句柄是一种指向指针的特殊指针。Windows中的句柄实际上是一个唯一的数字,它引用一个Windows对象,例如窗口、图标等。
   Windows内存管理器在移动对象在内存中的位置后，把对象新的地址告知句柄地址来保存。这样只需记住句柄地址就可以间接知道对象具体在内存中的哪个位置。
   句柄地址(稳定)→记载着对象在内存中的地址→对象在内存中的地址(不稳定)→实际对象
   下面哪个说法是正确的(AB )
   A. 每个进程被初始化时,系统为它分配一个句柄表,用于保存该进程使用的内核对象信息
   B. 相同的句柄值在不同的进程中可能标识不同的内核对象
   C. 一个进程中止执行,它使用的内核对象也会被撤销
   D. 内核对象是由进程拥有的
2. 线程执行函数
   记住函数头
3. 创建线程、等待线程、等待多个线程、撤销线程等四个函数，涉及到的所有程序
   创建线程：CreateThread(NULL,0,helloFunc,NULL,0,NULL);
   等待一个线程：WaitForSingleObject(HANDLE hHandle,DWORD dwMilliseconds);
   如：WaitForSingleObject(hThread , INFINITE);
   等待多个线程：WaitForMultipleObjects(numThreads, hThread,TRUE, INFINITE);
   线程退出：BOOL CloseHandle(HANDLE hObject);
   例题：
   简述下列Windows多线程程序设计中常用函数的含义
   答案就是上边的那个
   分析以下程序可能出现的结果及原因

   #include <stdio.h>
   #include <windows.h>
   DWORD WINAPI helloFunc(LPVOID arg ) { 
   	printf(“Created thread says ‘Hello’ \n”); 
   	return 0; 
   }
   void main( ) {
   	HANDLE hThread = 
   		CreateThread(NULL, 0, helloFunc, 
                  			NULL, 0, NULL );
   	printf(“Main thread says ‘Hello’ \n”); 
   	CloseHandle(hThread);
   }
   

   结果：
   (1)Main thread says ‘Hello’
   Created thread says ‘Hello’
   (2)Created thread says ‘Hello’
   Main thread says ‘Hello’
   (3)Main thread says ‘Hello’
   情况三是主线程执行完之后就直接触发CloseHandle(hThread)方法
   期望的结果是情况二，如果想弄成这样的话，可以使用全局变量+轮循(ppt 14)或者WaitForSingleObject

   const int numThreads = 4;
   DWORD WINAPI threadFunc(LPVOID pArg) { 
   int* p = (int*)pArg;
   int myNum = *p;
   printf("Thread number %d\n", myNum);
   return 0;
   }
   void main() {
   	HANDLE hThread[numThreads];
   	for (int i = 0; i < numThreads; i++) {
     		hThread[i] = CreateThread(NULL, 0, threadFunc, &i, 0, NULL);
   	}
   	WaitForMultipleObjects(numThreads, hThread,
   					TRUE, INFINITE);
   }
   

   可能出现
   4444
   0123等
   出现这种结果是因为四个线程共享i，产生数据竞争，既读又写
   解决方法：变量本地化（ppt 24）
4. win32线程同步的实现方法
   全局变量、事件、互斥量、临界区、信号量
   前两个处理先后顺序（同步）问题，后三个处理互斥问题，其中事件是专门处理先后顺序的，互斥量也可处理先后顺序
5. 卖票的

   #include <windows.h>
   #include <iostream.h>
   
   DWORD WINAPI Fun1Proc(LPVOID lpParameter);
   DWORD WINAPI Fun2Proc(LPVOID lpParameter);
   
   int tickets=100;
   HANDLE hMutex;///
   
   void main()
   {
   	hMutex=CreateMutex(NULL,FALSE,NULL);///
   
   	HANDLE hThread1;
   	HANDLE hThread2;
   
   	hThread1=CreateThread(NULL,0,Fun1Proc,NULL,0,NULL);
   	hThread2=CreateThread(NULL,0,Fun2Proc,NULL,0,NULL);
   
   	HANDLE hThreads[2] = {hThread1, hThread2};
   	WaitForMultipleObjects(2,hThreads,TRUE,INFINITE);
   
   	CloseHandle(hThread1);
   	CloseHandle(hThread2);
   
   	CloseHandle(hMutex);///
   }
   
   DWORD WINAPI Fun1Proc(LPVOID lpParameter)
   {
   	while(TRUE)
   	{
   		WaitForSingleObject(hMutex,INFINITE);///
   		if(tickets>0)
   		{
   			Sleep(2);
   			cout<<"thread1 sell ticket : "<<tickets--<<endl;
   		}
   		else
   			break;
   		ReleaseMutex(hMutex);///
   
   	}
   	return 0;
   }
   
   DWORD WINAPI Fun2Proc(LPVOID lpParameter)
   {
   
   	while(TRUE)
   	{
   		WaitForSingleObject(hMutex,INFINITE);///
   		if(tickets>0)
   		{
   			Sleep(2);
   			cout<<"thread2 sell ticket : "<<tickets--<<endl;
   		}
   		else
   			break;
   		ReleaseMutex(hMutex);///
   
   	}
   	return 0;
   }
   

lesson4

1. OpenMp特征
   一种面向共享内存以及分布式共享内存的多处理器多线程并行编程语言。
   执行模型采用Fork-Join的形式
   以下表述错误的是:(D)
   A. OpenMP 可以根据目标系统尽量使用最优数量的线程个数
   B. 使用线程池可以避免为每个线程创建新进程的开销
   C. 线程池通常具有最大线程数限制,如果所有线程都繁忙,而额外的任务将放入队列中,直到有线程可用时才能够得到处理
   D.对于有优先级的线程,也可以使用线程池
   以下表述不正确的是:(D )
   A. OpenMP 的编程模型以线程为基础,通过编译制导语句来显示地制导并行化,为编程人员提供了对并行化的完整控制
   B. OpenMP 的执行模型采用Fork-Join 的形式
   C. Fork-Join 执行模式在开始执行的时候,只有一个叫做主线程的运行线程存在
   D. OpenMP 同时支持C/C++语言和Java 语言

2. “helloworld”中涉及到的函数

   #include “omp.h”
   int main ( ){
   	printf(“Hello from serial.\n”);
   	//串行执行
   	printf(“Thread number = %d\n”,
   			omp_get_thread_num( ));  
   	omp_set_num_threads(4);
   	#pragma omp parallel //开始并行执行
   	{
   		printf(“Hello from parallel. Thread 	number=%d\n”,omp_get_thread_num( ));
   	}//没有，默认并行距离最近的语句结构
   	printf(“Hello from serial again.\n”);
   	return 0;
   }
   

3. 求PI的程序

   OpenMP

   #include "stdafx.h"
   #include <omp.h>
   #include <time.h>
   long num_steps = 100000000;
   double step;
   int main(){
    	clock_t start, stop;
   	double x,pi,sum=0.0;
   	int i;
   	step = 1.0 /(double) num_steps;
   	start=clock();
   	omp_set_num_threads(4);
   	#pragma omp parallel for private(x) reduction( +:sum)
   		for(i=0;i<num_steps; i++){
   			x=(i+0.5)*step;
   			sum = sum+4.0/(1.0+x*x);
   		}
   		pi = sum*steps;
   		stop= clock();
   		printf( "The value of PI is %15. 12f\n",pi);
   		printf("The time to calculate PI was %f seconds\n", ((double)(stop-start)/1000.0));
   		return 0:
   }
   

4. 子句的掌握：parallel for reduction private barrier
   parallel 后续语句按多线程方式运行
   parallel for 后续的for循环语句按多线程方式运行
   parallel private 并行区变量私有化指导语句，说明后续语句中的某变量在多线程方式运行时被各线程私有化，每次仅容许一个线程访问的变量
   parallel reduction
   如：#pragma omp parallel for private(x) reduction(+:sum)
   每个线程运行都得到一个sum，所有线程都执行完后再把所得的所有sum加起来
   parallel barrier 用于并行区内代码的线程同步，所有线程执行到 barrier 时要停止，直到所有线程都执行到 barrier 时才继续往下执行。

5. 任务调度的方法
   静态调度 static
   动态调度 dynamic
   guided调度
   runtime调度
   以下哪些不是OpenMP 的负载平衡调度方案:(D )
   A.static
   B.dynamic
   C.runtime
   D.public

6. 程序性能分析实例
   高精度性能计数器：

   QueryPerformanceFrequency(
   		(LARGE_INTEGER*)&frequency);
   QueryPerformanceCounter(
   		(LARGE_INTEGER*)&counter);
   

lesson6

1. 非阻塞算法的特征
   无阻塞 只要没有竞争，线程就可以持续执行
   无锁 系统整体持续执行
   无等待 每个线程都可以持续执行，即使遇到竞争
2. 线程安全函数
   一个线程安全的函数通过加锁的方式来实现多线程对共享数据的安全访问。
   非可重入函数可能无法满足线程安全要求，不可用于多线程环境。
   线程函数安全化：
   为共享资源加锁
   对于非线程安全函数：
   (1) 使用作用于整个函数库的锁
   (2) 使用作用于单个库组件/一组组件的锁
3. 数据竞争是指在多线程程序中，不同线程对共享变量的访问没有特定的顺序，发生读写操作和写写操作。

lesson7

1. MPI 特征：
   MPI是一种消息传递编程模型，并成为这种编程模型的代表和事实上的标准。消息传递方式是广泛应用于多类并行机的一种模式，特别是分布存储并行机(分布式系统)。
2. 6个接口函数概念和4个组通信接口概念
   6个接口函数
   （1）初始化：int MPI_Init（int *argc, char ***argv）
   MPI程序的第一个调用，完成MPI程序所有的初始化工作，将命令行参数传给各个进程。
   （2）获取当前进程标识
   int MPI_Comm_rank（MPI_Comm comm,int *rank）
   函数返回时，rank中存放当前进程在给定的通信域中的进程标识号。
   （3）获取通信域包含的进程数
   int MPI_Comm_size（MPI_Comm comm,int *size）
   函数返回时，size中存放指定通信域中的进程数。
   （4）消息发送
   源进程将缓存中的数据发送到目的进程。
   int MPI_Send（void *buf, int count, MPI_Datatype datatype, int dest, int tag,MPI_Comm comm）
   （5）MPI_Recv
   接收源进程source的消息，并且该消息的数据类型和消息标识和本API指定的datatype和tag相一致。
   接收到的消息所包含的数据元素的个数最多不能超过count个。若超过count个，则会发生溢出错误。若少于count个，则只有相应于这个消息的那些地址上的内容被修改。
   count可以是0，这种情况下的数据部分是空的
   （6）MPI程序的结束
   int MPI_ Finalize（）
   MPI程序的最后一个调用，结束MPI程序的运行。它是MPI程序的最后一条可执行语句，否则程序的运行结果是不可预知的。
   四个通信接口
   （1）广播 一个任务给多个进程
   根进程将一条消息发送到组内的所有其它进程，同时也包括它本身在内。
   Int MPI_Bcast（void *buffer, int count, MPI_Datatype datatype, int root,MPI_Comm comm）
   
   （2）散发 分片
   根进程将数据的不同部分分别发送给各个进程。
   Int MPI_Scatter（void *sendbuf, int sendcount, MPI_Datatype data, void *recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm）
   
   （3）收集
   每个进程将自身发送缓冲区中的消息发送到根进程，根进程依据发送进程的进程标识号将它们各自的消息依次存放到自己的消息缓冲区中。
   Int MPI_Gather（void *sendbuf, int sendcount, MPI_Datatype data, void *recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm）
   （4）归约 收集时做的操作
   将每个进程缓冲区中的数据按给定的操作进行运算，并将计算结果返回到根进程的输出缓冲区中。
   Int MPI_Reduce（void *sendbuf, void *recvbuf, int count, MPI_Datatype data,MPI_Op op, int root, MPI_Comm comm）

lesson8

1. TBB的特征：是C++的扩展库