MPI(Message Passing Interface)是目前最重要的一个基于消息传递的并行编程工具,它具有移植性好、功能强大、效率高等许多优点,而且有多种不同的免费、高效、实用的实现版本,几乎所有的并行计算机厂商都提供对它的支持,成为了事实上的并行编程标准。
MPI是一个库,而不是一门语言,因此对MPI的使用必须和特定的语言结合起来进行。MPI不是一个独立的自包含系统,而是建立在本地并行程序设计环境之上,其进程管理和I/O均由本地并行程序设计环境提供。例如,MPI可以建立在IBM SP2的POE/MPL之上,也可以建立在Intel Paragon的OSF/NX。除了这些商业版本的MPI实现,还有一些免费版的MPI实现,主要有MPICH,LAM和CHIMP。
在Linux环境下搭建MPI环境:
sudo apt-get install mpich
编写C语言或C++代码时,在头文件中包含include "mpi.h"
便可以在代码中使用mpi的并行语句了。
C语言编译mpi程序:mpicc example.c -o example
C++编译mpi程序:mpic++ example.c -o example
运行mpi程序:mpiexec -n 4 ./example
(4为指定运行的进程数)
根据积分法易得,求π值的串行代码如下:
int n = 100, x,sum;
int h = 1.0/n;
for(int i=1; i<=n; i++)
{
x= (i - 0.5)/n;
sun += 4.0/(1+x*x);
}
pi = sum*h;
printf("pi = %d\n",pi);
不难改成mpi并行代码:
//*计算π的C语言 MPI编程代码段*//
#include "mpi.h"
#include <stdio.h>
#include <math.h>
double f(double);
double f(double a)
{
return (4.0/(1.0 + a*a));
}
int main(int argc, char *argv[])
{
int done = 0, n, myid, numprocs, i;
double PI25DT = 3.141592653589793238462643;
double mypi, pi, h, sum, x;
double startwtime = 0.0, endwtime;
int namelen;
char processor_name[MPI_MAX_PROCESSOR_NAME];
MPI_Init(&argc, &argv); //mpi的初始化
MPI_Comm_size(MPI_COMM_WORLD, &numprocs); //获取线程数
MPI_Comm_rank(MPI_COMM_WORLD, &myid); //获取线程id值
MPI_Get_processor_name(processor_name, &namelen); //获取处理器名称
fprintf(stderr, "Process %d on %s\n", myid, processor_name);
n = 0;
while(!done)
{
if(myid == 0)
{
/* printf("Enter the number of intervals: (0 quits)");
scanf("%d",&n); */
if(n == 0)
n = 100;
else
n = 0;
startwtime = MPI_Wtime();
}
MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD); //进行广播传送消息
if(n == 0)
done = 1;
else
{
h = 1.0/(double)n;
sum = 0.0;
for(i=myid+1; i<=n; i+=numprocs) //各线程计算自己的面积
{
x = h * ((double)i - 0.5);
sum += f(x);
}
mypi = h * sum;
MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD); //归约,mypi为发送方,pi为接收方
if(myid == 0)
{
printf("pi is approximately %.16f,Error is %.16f\n",pi, fabs(pi-PI25DT));
endwtime = MPI_Wtime();
printf("wall clock time = %f\n", endwtime-startwtime);
}
}
}
MPI_Finalize(); //mpi结束
return 0;
}
PSRS的排序算法思想如下:
n个元素A[1..n]分成p组,每组A[(i-1)n/p+1..in/p],i=1~p
(1)均匀划分:将n个元素A[1..n]均匀划分成p段,每个pi处理
A[(i-1)n/p+1..in/p]
(2)局部排序:pi调用串行排序算法对A[(i-1)n/p+1..in/p]排序
(3)选取样本:pi从其有序子序列A[(i-1)n/p+1..in/p]中选取p个样本元素
(4)样本排序:用一台处理器对p2个样本元素进行串行排序
(5)选择主元:用一台处理器从排好序的样本序列中选取p-1个主元,并
播送给其他pi
(6)主元划分:pi按主元将有序段A[(i-1)n/p+1..in/p]划分成p段
(7)全局交换:各处理器将其有序段按段号交换到对应的处理器中
(8)归并排序:各处理器对接收到的元素进行归并排序
mpi编程思路如下:
1.获取整个数组的起始位置和子数组大小;
2.调用MPI_Barrier(MPI_COMM_WORLD)进行同步;
3.调用阶段一函数,对子数组进行局部排序,以及正则采样;
4.调用阶段二函数,对正则采样的样本进行排序,选择主元和主元划分;
5.调用阶段三函数,进行全局对全局的发送,并且计算划分的总大小,给新划分分配空间;
6.调用阶段四函数,将全局交换后的数据进行归并排序,并发送各排序好的子列表回根进程;
7.打印输出排好序的数组。
代码如下:
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <assert.h>
#include <sys/time.h>
#include <unistd.h>
#include "mpi.h"
int i,j,k;
int N = 36;
int cmp(const void * a, const void * b) {
if (*(int*)a < *(int*)b) return -1;
if (*(int*)a > *(int*)b) return 1;
else return 0;
}
void phase1(int *array, int N, int startIndex, int subArraySize, int *pivots, int p) {
// 对子数组进行局部排序
qsort(array + startIndex, subArraySize, sizeof(array[0]), cmp);
// 正则采样
for (i = 0; i < p; i++) {
pivots[i] = array[startIndex + (i * (N / (p * p)))];
}
return;
}
void phase2(int *array, int startIndex, int subArraySize, int *pivots, int *partitionSizes, int p, int myId) {
int *collectedPivots = (int *) malloc(p * p * sizeof(pivots[0]));
int *phase2Pivots = (int *) malloc((p - 1) * sizeof(pivots[0])); //主元
int index = 0;
//收集消息,根进程在它的接受缓冲区中包含所有进程的发送缓冲区的连接。
MPI_Gather(pivots, p, MPI_INT, collectedPivots, p, MPI_INT, 0, MPI_COMM_WORLD);
if (myId == 0) {
qsort(collectedPivots, p * p, sizeof(pivots[0]), cmp); //对正则采样的样本进行排序
// 采样排序后进行主元的选择
for (i = 0; i < (p -1); i++) {
phase2Pivots[i] = collectedPivots[(((i+1) * p) + (p / 2)) - 1];
}
}
//发送广播
MPI_Bcast(phase2Pivots, p - 1, MPI_INT, 0, MPI_COMM_WORLD);
// 进行主元划分,并计算划分部分的大小
for ( i = 0; i < subArraySize; i++) {
if (array[startIndex + i] > phase2Pivots[index]) {
//如果当前位置的数字大小超过主元位置,则进行下一个划分
index += 1;
}
if (index == p) {
//最后一次划分,子数组总长减掉当前位置即可得到最后一个子数组划分的大小
partitionSizes[p - 1] = subArraySize - i + 1;
break;
}
partitionSizes[index]++ ; //划分大小自增
}
free(collectedPivots);
free(phase2Pivots);
return;
}
void phase3(int *array, int startIndex, int *partitionSizes, int **newPartitions, int *newPartitionSizes, int p) {
int totalSize = 0;
int *sendDisp = (int *) malloc(p * sizeof(int));
int *recvDisp = (int *) malloc(p * sizeof(int));
// 全局到全局的发送,每个进程可以向每个接收者发送数目不同的数据.
MPI_Alltoall(partitionSizes, 1, MPI_INT, newPartitionSizes, 1, MPI_INT, MPI_COMM_WORLD);
// 计算划分的总大小,并给新划分分配空间
for ( i = 0; i < p; i++) {
totalSize += newPartitionSizes[i];
}
*newPartitions = (int *) malloc(totalSize * sizeof(int));
// 在发送划分之前计算相对于sendbuf的位移,此位移处存放着输出到进程的数据
sendDisp[0] = 0;
recvDisp[0] = 0; //计算相对于recvbuf的位移,此位移处存放着从进程接受到的数据
for ( i = 1; i < p; i++) {
sendDisp[i] = partitionSizes[i - 1] + sendDisp[i - 1];
recvDisp[i] = newPartitionSizes[i - 1] + recvDisp[i - 1];
}
//发送数据,实现n次点对点通信
MPI_Alltoallv(&(array[startIndex]), partitionSizes, sendDisp, MPI_INT, *newPartitions, newPartitionSizes, recvDisp, MPI_INT, MPI_COMM_WORLD);
free(sendDisp);
free(recvDisp);
return;
}
void phase4(int *partitions, int *partitionSizes, int p, int myId, int *array) {
int *sortedSubList;
int *recvDisp, *indexes, *partitionEnds, *subListSizes, totalListSize;
indexes = (int *) malloc(p * sizeof(int));
partitionEnds = (int *) malloc(p * sizeof(int));
indexes[0] = 0;
totalListSize = partitionSizes[0];
for ( i = 1; i < p; i++) {
totalListSize += partitionSizes[i];
indexes[i] = indexes[i-1] + partitionSizes[i-1];
partitionEnds[i-1] = indexes[i];
}
partitionEnds[p - 1] = totalListSize;
sortedSubList = (int *) malloc(totalListSize * sizeof(int));
subListSizes = (int *) malloc(p * sizeof(int));
recvDisp = (int *) malloc(p * sizeof(int));
// 归并排序
for ( i = 0; i < totalListSize; i++) {
int lowest = INT_MAX;
int ind = -1;
for (j = 0; j < p; j++) {
if ((indexes[j] < partitionEnds[j]) && (partitions[indexes[j]] < lowest)) {
lowest = partitions[indexes[j]];
ind = j;
}
}
sortedSubList[i] = lowest;
indexes[ind] += 1;
}
// 发送各子列表的大小回根进程中
MPI_Gather(&totalListSize, 1, MPI_INT, subListSizes, 1, MPI_INT, 0, MPI_COMM_WORLD);
// 计算根进程上的相对于recvbuf的偏移量
if (myId == 0) {
recvDisp[0] = 0;
for ( i = 1; i < p; i++) {
recvDisp[i] = subListSizes[i - 1] + recvDisp[i - 1];
}
}
//发送各排好序的子列表回根进程中
MPI_Gatherv(sortedSubList, totalListSize, MPI_INT, array, subListSizes, recvDisp, MPI_INT, 0, MPI_COMM_WORLD);
free(partitionEnds);
free(sortedSubList);
free(indexes);
free(subListSizes);
free(recvDisp);
return;
}
//PSRS排序函数,调用了4个过程函数
void psrs_mpi(int *array, int N)
{
int p, myId, *partitionSizes, *newPartitionSizes, nameLength;
int subArraySize, startIndex, endIndex, *pivots, *newPartitions;
char processorName[MPI_MAX_PROCESSOR_NAME];
MPI_Comm_size(MPI_COMM_WORLD,&p);
MPI_Comm_rank(MPI_COMM_WORLD,&myId);
MPI_Get_processor_name(processorName,&nameLength);
printf("Process %d is on %s\n",myId, processorName);
pivots = (int *) malloc(p*sizeof(int));
partitionSizes = (int *) malloc(p*sizeof(int));
newPartitionSizes = (int *) malloc(p*sizeof(int));
for ( k = 0; k < p; k++) {
partitionSizes[k] = 0;
}
// 获取起始位置和子数组大小
startIndex = myId * N / p;
if (p == (myId + 1)) {
endIndex = N;
}
else {
endIndex = (myId + 1) * N / p;
}
subArraySize = endIndex - startIndex;
MPI_Barrier(MPI_COMM_WORLD);
//调用各阶段函数
phase1(array, N, startIndex, subArraySize, pivots, p);
if (p > 1) {
phase2(array, startIndex, subArraySize, pivots, partitionSizes, p, myId);
phase3(array, startIndex, partitionSizes, &newPartitions, newPartitionSizes, p);
phase4(newPartitions, newPartitionSizes, p, myId, array);
}
if (myId == 0)
for(k = 0; k < N; k++){
printf("%d ",array[k]);
}
printf("\n");
if (p > 1) {
free(newPartitions);
}
free(partitionSizes);
free(newPartitionSizes);
free(pivots);
free(array);
MPI_Finalize();
}
int main(int argc, char *argv[]) {
int *array;
array = (int *) malloc(N*sizeof(int));
srand(100);
for ( k = 0; k < N; k++) {
array[k] = rand()%100;
}
MPI_Init(&argc,&argv); //MPI初始化
psrs_mpi(array,N); //调用PSRS算法进行并行排序
return 0;
}
文章浏览阅读3.8k次,点赞9次,收藏28次。直接上一个工作中碰到的问题,另外一个系统开启多线程调用我这边的接口,然后我这边会开启多线程批量查询第三方接口并且返回给调用方。使用的是两三年前别人遗留下来的方法,放到线上后发现确实是可以正常取到结果,但是一旦调用,CPU占用就直接100%(部署环境是win server服务器)。因此查看了下相关的老代码并使用JProfiler查看发现是在某个while循环的时候有问题。具体项目代码就不贴了,类似于下面这段代码。while(flag) {//your code;}这里的flag._main函数使用while(1)循环cpu占用99
文章浏览阅读347次。idea shift f6 快捷键无效_idea shift +f6快捷键不生效
文章浏览阅读135次。Ecmacript 中没有DOM 和 BOM核心模块Node为JavaScript提供了很多服务器级别,这些API绝大多数都被包装到了一个具名和核心模块中了,例如文件操作的 fs 核心模块 ,http服务构建的http 模块 path 路径操作模块 os 操作系统信息模块// 用来获取机器信息的var os = require('os')// 用来操作路径的var path = require('path')// 获取当前机器的 CPU 信息console.log(os.cpus._node模块中有很多核心模块,以下不属于核心模块,使用时需下载的是
文章浏览阅读10w+次,点赞435次,收藏3.4k次。SPSS 22 下载安装过程7.6 方差分析与回归分析的SPSS实现7.6.1 SPSS软件概述1 SPSS版本与安装2 SPSS界面3 SPSS特点4 SPSS数据7.6.2 SPSS与方差分析1 单因素方差分析2 双因素方差分析7.6.3 SPSS与回归分析SPSS回归分析过程牙膏价格问题的回归分析_化工数学模型数据回归软件
文章浏览阅读7.5k次。如何利用hutool工具包实现邮件发送功能呢?1、首先引入hutool依赖<dependency> <groupId>cn.hutool</groupId> <artifactId>hutool-all</artifactId> <version>5.7.19</version></dependency>2、编写邮件发送工具类package com.pc.c..._hutool发送邮件
文章浏览阅读867次,点赞2次,收藏2次。docker安装elasticsearch,elasticsearch-head,kibana,ik分词器安装方式基本有两种,一种是pull的方式,一种是Dockerfile的方式,由于pull的方式pull下来后还需配置许多东西且不便于复用,个人比较喜欢使用Dockerfile的方式所有docker支持的镜像基本都在https://hub.docker.com/docker的官网上能找到合..._docker安装kibana连接elasticsearch并且elasticsearch有密码
文章浏览阅读1.3w次,点赞57次,收藏92次。整理 | 郑丽媛出品 | CSDN(ID:CSDNnews)近年来,随着机器学习的兴起,有一门编程语言逐渐变得火热——Python。得益于其针对机器学习提供了大量开源框架和第三方模块,内置..._beeware
文章浏览阅读7.9k次。//// ViewController.swift// Day_10_Timer//// Created by dongqiangfei on 2018/10/15.// Copyright 2018年 飞飞. All rights reserved.//import UIKitclass ViewController: UIViewController { ..._swift timer 暂停
文章浏览阅读986次,点赞2次,收藏2次。1.硬性等待让当前线程暂停执行,应用场景:代码执行速度太快了,但是UI元素没有立马加载出来,造成两者不同步,这时候就可以让代码等待一下,再去执行找元素的动作线程休眠,强制等待 Thread.sleep(long mills)package com.example.demo;import org.junit.jupiter.api.Test;import org.openqa.selenium.By;import org.openqa.selenium.firefox.Firefox.._元素三大等待
文章浏览阅读3k次,点赞4次,收藏14次。Java软件工程师职位分析_java岗位分析
文章浏览阅读2k次。Java:Unreachable code的解决方法_java unreachable code
文章浏览阅读1w次。1、html中设置标签data-*的值 标题 11111 222222、点击获取当前标签的data-url的值$('dd').on('click', function() { var urlVal = $(this).data('ur_如何根据data-*属性获取对应的标签对象