MPI Maelstrom MPI 大漩涡(最短路Dijkstra算法详解)

2024-02-23 01:40

本文主要是介绍MPI Maelstrom MPI 大漩涡(最短路Dijkstra算法详解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

MPI Maelstrom MPI 大漩涡

目录

MPI Maelstrom MPI 大漩涡

题意描述

解题思路

注意 :里面我们会用到  atoi()函数

AC


BIT has recently taken delivery of their new supercomputer, a 32 processor Apollo Odyssey distributed shared memory machine with a hierarchical communication subsystem. Valentine McKee's research advisor, Jack Swigert, has asked her to benchmark the new system.
``Since the Apollo is a distributed shared memory machine, memory access and communication times are not uniform,'' Valentine told Swigert. ``Communication is fast between processors that share the same memory subsystem, but it is slower between processors that are not on the same subsystem. Communication between the Apollo and machines in our lab is slower yet.''

``How is Apollo's port of the Message Passing Interface (MPI) working out?'' Swigert asked.

``Not so well,'' Valentine replied. ``To do a broadcast of a message from one processor to all the other n-1 processors, they just do a sequence of n-1 sends. That really serializes things and kills the performance.''

``Is there anything you can do to fix that?''

``Yes,'' smiled Valentine. ``There is. Once the first processor has sent the message to another, those two can then send messages to two other hosts at the same time. Then there will be four hosts that can send, and so on.''

``Ah, so you can do the broadcast as a binary tree!''

``Not really a binary tree -- there are some particular features of our network that we should exploit. The interface cards we have allow each processor to simultaneously send messages to any number of the other processors connected to it. However, the messages don't necessarily arrive at the destinations at the same time -- there is a communication cost involved. In general, we need to take into account the communication costs for each link in our network topologies and plan accordingly to minimize the total time required to do a broadcast.''

Input

The input will describe the topology of a network connecting n processors. The first line of the input will be n, the number of processors, such that 1 <= n <= 100.

The rest of the input defines an adjacency matrix, A. The adjacency matrix is square and of size n x n. Each of its entries will be either an integer or the character x. The value of A(i,j) indicates the expense of sending a message directly from node i to node j. A value of x for A(i,j) indicates that a message cannot be sent directly from node i to node j.

Note that for a node to send a message to itself does not require network communication, so A(i,i) = 0 for 1 <= i <= n. Also, you may assume that the network is undirected (messages can go in either direction with equal overhead), so that A(i,j) = A(j,i). Thus only the entries on the (strictly) lower triangular portion of A will be supplied.

The input to your program will be the lower triangular section of A. That is, the second line of input will contain one entry, A(2,1). The next line will contain two entries, A(3,1) and A(3,2), and so on.

Output

Your program should output the minimum communication time required to broadcast a message from the first processor to all the other processors.

BIT 最近交付了他们的新超级计算机,这是一台带有分层通信子系统的 32 处理器 Apollo Odyssey 分布式共享内存机器。瓦伦丁麦基的研究顾问杰克斯威格特要求她对新系统进行基准测试。
“由于 Apollo 是分布式共享内存机器,内存访问和通信时间并不统一,”瓦伦丁告诉斯威格特。``共享同一内存子系统的处理器之间的通信速度很快,但不在同一子系统上的处理器之间的通信速度较慢。阿波罗和我们实验室机器之间的通信还比较慢。” “

阿波罗的消息传递接口 (MPI) 端口如何工作?”斯威格特问道。

“不太好,”瓦伦丁回答。``要将消息从一个处理器广播到所有其他 n-1 个处理器,它们只需执行 n-1 次发送的序列。这真的会连载事情并扼杀表演。

” “你有什么办法可以解决这个问题吗?

” “是的,”瓦伦丁笑着说。``有。一旦第一个处理器将消息发送给另一个处理器,这两个处理器就可以同时向其他两个主机发送消息。然后将有四台主机可以发送,依此类推。''

``啊,所以你可以将广播作为二叉树进行!''

``并不是真正的二叉树——我们应该利用我们网络的一些特殊功能。我们拥有的接口卡允许每个处理器同时向与其相连的任意数量的其他处理器发送消息。然而,消息不一定同时到达目的地——这涉及到通信成本。一般而言,我们需要考虑网络拓扑中每个链路的通信成本,并相应地进行计划以最大限度地减少广播所需的总时间。”

输入

输入将描述连接 n 个处理器的网络的拓扑结构。输入的第一行将是 n,处理器的数量,这样 1 <= n <= 100。

输入的其余部分定义了一个邻接矩阵 A。邻接矩阵是正方形,大小为 nx n。它的每个条目将是一个整数或字符 x。A(i,j) 的值表示直接从节点 i 向节点 j 发送消息的费用。A(i,j) 的 x 值表示消息不能直接从节点 i 发送到节点 j。

请注意,节点向自身发送消息不需要网络通信,因此 A(i,i) = 0 for 1 <= i <= n。此外,您可以假设网络是无向的(消息可以以相同的开销沿任一方向传播),因此 A(i,j) = A(j,i)。因此,将只提供 A 的(严格的)下三角部分的条目。

程序的输入将是 A 的下三角部分。也就是说,输入的第二行将包含一个条目 A(2,1)。下一行将包含两个条目,A(3,1) 和 A(3,2),依此类推。

输出

您的程序应该输出从第一个处理器向所有其他处理器广播消息所需的最短通信时间。

Sample Input

5
50
30 5
100 20 50
10 x x 10

Sample Output

35

题意描述:本题就是第一行给你多个处理器,接下来的几行就是1-2、1-3、2-3...所用的时间,然后找第一个处理器到所有处理器所需的最短时间。具体如下:

拿题中的数据来说:

 然后我们得到的35就是1-3-2 (30+5)和1-5-4(10+10);35>20即取为35,题目的意思就是就是一个处理器可以同时传给多个处理器,我们只需要传给时间最短的那个,一直到所有的处理器都被传到了,然后找到传达时间最长的输出。

解题思路:很明显是一个从一个点到所有点的最短路问题,其中x表示此路不通,所有我们还要利用字符串记录数据和字符,如果是字符的话直接把那条路的值初始化一个如果是数字的话就利用atoi函数把它转化成数字就可以了,本题我用了dijkstra算法来求,只需要最后加一个判断条件输出最短路里面最大的那个值就可以了。

注意:里面我们会用到  atoi()函数

atoi()函数原型为: int atoi(char *str),用途是将字符串转换成一个整数值,str是待转化成整数值的字符串.成功则返回转化后的整数值,失败返回0.具体看代码

AC:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 110
int inf=999999,n;
int e[N][N],dis[N],book[N];
void dijkstra()
{int u,v,min;//初始化数组1到n的路程 for(int i=1;i<=n;i++)dis[i]=e[1][i];//book数组初始化 for(int i=1;i<=n;i++)book[i]=0;book[1]=1;//顶点为1//算法 for(int i=1;i<=n-1;i++){min=inf;for(int j=1;j<=n;j++){if(book[j]==0&&dis[j]<min){min=dis[j];u=j;}}book[u]=1;for(v=1;v<=n;v++){if(e[u][v]<inf){if(dis[v]>dis[u]+e[u][v]&&book[v]==0)dis[v]=dis[u]+e[u][v];}} 	}	} 
int main(void)
{while(~scanf("%d",&n)){char s[N];for(int i=1;i<=n;i++){for(int j=1;j<i;j++){scanf("%s",s);if(s[0]=='x')e[i][j]=e[j][i]=inf;elsee[i][j]=e[j][i]=atoi(s);//把参数 s所指向的字符串转换为一个整数}}dijkstra();//可别忘了 int maxx=-1;for(int i=1;i<=n;i++)//找里面所用时间最多的 {if(dis[i]>maxx)maxx=dis[i];}printf("%d\n",maxx);}return 0;
}

这篇关于MPI Maelstrom MPI 大漩涡(最短路Dijkstra算法详解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/737138

相关文章

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

OpenHarmony鸿蒙开发( Beta5.0)无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息,即可快速实现设备配网,是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递,利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力,实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后,即可发送相关配网数据。同时还支持与常规Sof

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int