面向期末的并行与分布式程序设计总结_并行程序设计期末

背代码

SSE矩阵乘法

#include <pmmintrin.h>

void sse_mul(int n, float a[][maxN], float b[][maxN], float c[][maxN]){
	__m128 t1, t2, sum;
	for (int i = 0; i < n; ++i) for(int j = 0; j < i; ++j) swap(b[i][j], b[j][i]);
	for (int i = 0; i < n; ++i){
		for (int j = 0; j < n; ++j){
			c[i][j] = 0.0;
			sum = _mm_setzero_ps();
			for (int k = n - 4; k >= 0; k -= 4){ 
				t1 = _mm_loadu_ps(a[i] + k);
				t2 = _mm_loadu_ps(b[j] + k);
				t1 = _mm_mul_ps(t1, t2);
				sum = _mm_add_ps(sum, t1);
			}
			sum = _mm_hadd_ps(sum, sum);
			sum = _mm_hadd_ps(sum, sum);
			_mm_store_ss(c[i] + j, sum);
			for (int k = (n % 4) - 1; k >= 0; --k){ 
				c[i][j] += a[i][k] * b[j][k];
			}
		}
	}
	for (int i = 0; i < n; ++i) for (int j = 0; j < i; ++j) swap(b[i][j], b[j][i]);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

Pthread每个子线程输出字符串

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

int thread_count;
pthread_mutex_init(&mutex, NULL);
void* Hello(void* rank);

int main(int argc, char* argv[]){
	long thread;
	pthread_t* thread_handles;
	//get number of threads from cmd
	thread_count = strtol(argv[1], NULL, 10);
	thread_handles = (pthread_t*)malloc(thread_count*sizeof(pthread_t));
	for(thread = 0; thread < thread_count; thread++)
		pthread_create(&thread_handles[thread],NULL,Hello,(void*)thread);
	printf("Hello from the main thread\n");
	for(thread = 0; thread < thread_count; thread++)
		pthread_join(thread_handles[thread],NULL);
	free(thread_handles);
	return 0;
}

void* Hello(void* rank)
{
	long my_rank = (long)rank;
	pthread_mutex_lock(&mutex);
	printf("Hello from thread %ld of %d\n", my_rank, thread_count);
	pthread_mutex_unlock(&mutex);
	return NULL;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

OpenMP部分

#ifdef _OPENMP
#include <omp.h>
#endif

void Hello(void);
int main(int argc, char* argv[])
{
	int thread_count = strtol(argv[1],NULL,10);
#pragma omp parallel num_threads(thread_count)
	Hello();
	return 0;	
}
void Hello(void)
{
	#ifdef _OPENMP
	int my_rank = omp_get_thread_num();
	int thread_count = omp_get_num_threads();
	#else
	int my_rank = 0;
	int thread_count = 1;
	#endif
	printf("Hello from thread %d of %d\n",my_rank,thread_count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

MPI Hello

#include <mpi.h>

int main(int argc, char* argv)
{
	int myid, numprocs;
	int namelen;
	char processor_name[MPI_MAX_PROCESSOR_NAME];
	MPI_Init(&argc,&argv);
	MPI_Comm_rank(MPI_COMM_WORLD,&myid);//
	MPI_Comm_size(MPI_COMM_WORLD,&numprocs);//这两个对称着记
	MPI_Get_processor_name(processor_name,&namelen);
	fprintf(stderr,"Hello World! Process %d of %d on %s\n",
	myid, numprocs, processor_name);
	MPI_Finalize();//
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

MPI并行排序Send/Recv

//省略版
	int rank, a[1000], b[500];
	MPI_Init(&argc, &argv);//
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);//这个
	if (rank == 0) {
		MPI_Send(&a[500], 500, MPI_INT, 1, 0, MPI_COMM_WORLD);//这个
		sort(a, 500);
		MPI_Recv(b, 500, MPI_INT, 1, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);//和这个
	}
	else if (rank == 1) {
		MPI_Recv(b, 500, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
		sort(b, 500);
		MPI_Send(b, 500, MPI_INT, 0, 0, MPI_COMM_WORLD);
	}
	MPI_Finalize();//
	return 0;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

记理论

• E级（百亿亿次/秒）原型机系统天河三号在国家超级计算天津中心部署
• 推动并行计算的因素：单核频率、功耗/散热、性能的限制，多/众核的需求
• SSE data types: 16字节、8short、4int、2longlong、1dqword、4floats、2doubles
• SSE _mm_store_ss指令功用是对齐向量保存单精度浮点数
• 一个函数被称为线程安全（thread-safe）多个线程并行调用能“正确”执行
• 原子性：一组操作要么全部执行要么全部不执行，则称其是原子的
• 互斥：任何时刻都只有一个线程在执行
• 临界区：是一个更新共享资源的代码段，一次只允许一个线程执行该代码段
• 竞争条件：多个进程/线程尝试更新同一个共享资源时，结果可能无法预测，则存在竞争条件
• 数据依赖：两个内存操作的序，为了保证结果的正确性，必须保持这个序
• 同步：在时间上强制使各执行进程/线程在某一点必须互相等待，确保各进程/线程的正常顺序和对共享可写数据的正确访问
• 阿姆达尔定律：除非一个串行程序的执行几乎全部都并行化，否则不论多少可以利用的核，通过并行化所产生的加速比都会是受限的。S=1/(1-a+a/p)
• Flynn分类法：SISD SIMD MISD MIMD I:指令 D:数据流
• 并行设计的复杂性体现在
  • 足够的并发度
  • 并发粒度
  • 局部性
  • 负载均衡
  • 协调和同步
• 并行算法额外开销
  • 线/进程创建
  • 线/进程间通信
  • 线/进程空闲
  • 额外计算（最优串行算法难以并行化）
• OpenMP循环并行化：创建线程，在线程间分配循环步；要求迭代次数可预测。不检查依赖性
• MPI组通信原语（广播和归约）：MPI_Bcast, MPI_Reduce, MPI_Gather, MPI_Scatter, MPI_Allgather, MPI_Reduce_scatter
• 一般观点，存在控制流问题时SIMD不是很好用。
• SIMD额外开销
  • 打包/解包开销
  • 对齐开销
  • 控制流开销

待续。。。