[学习笔记]并行程序设计
环境配置见
多线程
OpenMP
- 库：omp.h
- 基本语句
#pragma omp parallel num_threads(线程数)
{
int my_rank=omp_get_thread_num();
//int l=,r=;
//进行对应段的操作
}
#pragma omp parallel for num_threads(线程数)
{
//对最外层for并行
}
#pragma omp critical
{
//临界区
}
example
矩阵乘法
friend matrix operator *(matrix &a,matrix &b){
matrix c;
if(a.m!=b.n){
printf("Error: Matrix Multiplication\n");
return c;
}
c.n=a.n;c.m=b.m;
//行被分割成thread_x块，每块大小为 block_x
int thread_x=sqrt(threadCnt);
int thread_y=threadCnt/thread_x;
int block_x=(c.n+thread_x-1)/thread_x;
int block_y=(c.m+thread_y-1)/thread_y;
#pragma omp parallel num_threads(threadCnt)
{
int threadIdx=omp_get_thread_num();
int l_x=(threadIdx/thread_y)*block_x,r_x=min(c.n,(threadIdx/thread_y+1)*block_x);
int l_y=(threadIdx%thread_y)*block_y,r_y=min(c.m,(threadIdx%thread_y+1)*block_y);
for(int i=l_x;i不定长文本分组
桶排序+基数排序
trie树
PThread
- 库：pthread.h
- 基本语句
void* func/*每个线程执行的函数*/(void* rank){
int my_rank=(long long)rank;
//int l=,r=;
//进行对应段的操作
}
pthread_t* thread=new pthread_t[线程数];
for(int i=0;i<线程数;++i)
pthread_create(&thread[i],NULL,func/*每个线程执行的函数*/,(void*)i);
for(int i=0;iexample
任务队列
#include
#include
#include
using namespace std;
int threadCnt;
queue q;
bool post_completed;//任务是否发布完毕，发布完毕即再也没有更多的任务生成
pthread_mutex_t mutex;//q的临界区
pthread_cond_t cond;//负责广播并唤醒线程的信号
void* do_task(void *rank){
int my_rank=(long long)rank;
while(true){ //条件等待状态，直到所有任务都已完成
pthread_mutex_lock(&mutex);
while(!post_completed&&pthread_cond_wait(&cond,&mutex));//条件等待
if(!q.empty()){//获取任务
int my_task=q.front();q.pop();
bool q_empty=q.empty();
printf("Task %d has been done by thread %d.\n",my_task,my_rank);
pthread_mutex_unlock(&mutex);
if(post_completed&&q_empty){//所有任务已完成
printf("Boasts that all the tasks are completed.\n");
pthread_cond_broadcast(&cond);//广播唤醒所有被阻塞的线程
break;
}
}
else{
pthread_mutex_unlock(&mutex);
if(post_completed)//所有任务已完成
break;
}
}
return nullptr;
}
int main(){
puts("Please input the number of threads:");
scanf("%d",&threadCnt);
int n;
puts("Please input the number of tasks:");
scanf("%d",&n);
pthread_t *thread=new pthread_t[threadCnt];
pthread_mutex_init(&mutex,NULL);
pthread_cond_init(&cond,NULL);
for(int i=0;i 多进程
MPI
- 库：mpi.h
- 基本语句
MPI_Init(NULL, NULL);
MPI_Comm_size(MPI_COMM_WORLD, &processCnt/*进程数*/);
MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
if(my_rank){
//Create message
//Send message to process 0
MPI_Send(&message/*发送的消息的地址*/,len/*发送的消息的长度*/,MPI_CHAR/*发送的消息的类型，z.B. MPI_INT*/,0/*接收方的进程编号*/,tag/*发送的消息的标签*/, MPI_COMM_WORLD);
}
else{
//Create message
//Receive messages
for(int i=1;iexample
矩阵乘法
MPI_Init(NULL, NULL);
freopen("1.txt","r",stdin);
matrix a,b,c;
a.read();b.read();
if(a.m!=b.n){
printf("Error: Matrix Multiplication\n");
exit(-1);
}
c.n=a.n;c.m=b.m;
int processCnt;
MPI_Comm_size(MPI_COMM_WORLD, &processCnt);
//行被分割成thread_x块，每块大小为 block_x
int thread_x=sqrt(processCnt);
int thread_y=processCnt/thread_x;
int block_x=(c.n+thread_x-1)/thread_x;
int block_y=(c.m+thread_y-1)/thread_y;
int my_rank;
MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
int l_x=(my_rank/thread_y)*block_x,r_x=min(c.n,(my_rank/thread_y+1)*block_x);
int l_y=(my_rank%thread_y)*block_y,r_y=min(c.m,(my_rank%thread_y+1)*block_y);
for(int i=l_x;i