MPI Maelstrom

Description

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.
Sample Input

5
50
30 5
100 20 50
10 x x 10
Sample Output

35

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
MPI Maelstrom
DescriptionnBIT 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. n``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.'' nn``How is Apollo's port of the Message Passing Interface (MPI) working out?'' Swigert asked. nn``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.'' nn``Is there anything you can do to fix that?'' nn``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.'' nn``Ah, so you can do the broadcast as a binary tree!'' nn``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.''nInputnThe 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. nnThe 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. nnNote 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. nnThe 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.nOutputnYour program should output the minimum communication time required to broadcast a message from the first processor to all the other processors.nSample Inputn5n50n30 5n100 20 50n10 x x 10nSample Outputn35
MPI Maelstrom(最短路)
MPI Maelstrom(最短路) Time limit:1000 ms Memory limit:10000 kB OS:Linux judge:https://vjudge.net/contest/297882#problem/G 描述 BIT has recently taken delivery of their new supercomputer, a 32 processor Apo...
Dijkstra-POJ-1502-MPI Maelstrom
MPI Maelstrom Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 7182 Accepted: 4375 DescriptionBIT has recently taken delivery of their new supercomputer, a 32 processor Apollo Ody
G - MPI Maelstrom(最短路中的最长路)
题意:有n个点,求从一个点到其他所有点的最短路中的最长路。SPFA和Dijkstra都可以。 SPFA: #include&amp;lt;iostream&amp;gt; #include&amp;lt;cstring&amp;gt; #include&amp;lt;vector&amp;gt; #include&amp;lt;queue&amp;gt; #include&amp;lt;stdio.h&amp;gt; const int maxn=108; const ...
POJ 1502 MPI Maelstrom 【最短路(迪杰斯特拉)】
Description 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
POJ1502---MPI Maelstrom (最短路:题意杀)
【题目来源】:https://vjudge.net/problem/POJ-1502 【题意】 传讯信息,从第一台装置传入其余各个装置,并且尽可能距离小。然后求出最大的一个。。。。 【思路】 简单的迪杰斯特拉算法就可以过。。但是,主要还是输入的时候。。一不小心被坑了十几发。。。明明输入对了,,但就是过不去。。最后,,弱弱只好用了atoi函数,过了、、、(尴尬到死。。。) 【代码】#incl
mpi fft mpi fft
有关mpi的fft,很不错的东西,自己顶一个
mpi安装程序 mpi
很难找的mpi安装程序,欢迎大家分享 会有用的
MPI课件(MPI并行程序设计)
MPI课件(MPI并行程序设计)MPI课件(MPI并行程序设计)MPI课件(MPI并行程序设计)MPI课件(MPI并行程序设计)MPI课件(MPI并行程序设计)MPI课件(MPI并行程序设计)MPI课件(MPI并行程序设计)
【POJ - 1502】MPI Maelstrom(Dijkstra单源最短路--求一点到其余个点的最小值的最大值)
题干: 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...
MPI学习一 MPI基础及六个接口构成的MPI子集
什么是MPI MPI(Message Passing Interface)是消息传递函数库的标准规范,支持C和Fortran,由众多并行计算机厂商、软件开发组织及并行应用单位共同维护的标准。 MPI是一种标准或规范,不是特指某一个对它的具体实现。MPI是一种消息传递编程模型,并成为此模型的代表和事实上的标准,服务于进程通信MPI是一种库描述,不是一种语言由Fotran+MPI或C+MP
MPI学习五 组通信MPI程序设计
集合通信是包含在通信因子中的所有进程都参加操作  集合通信一般实现三个功能 通信:组内数据的传输同步:组内所有进程在特定的地点在执行进度上取得一致计算:对给定的数据完成一定的操作 集合操作的三种类型: 通信:广播(broadcast)、分散(scatter)、收集(gather)、全互换(alltoall)等同步(barrier):集合中所有进程都到达后,每个进程再接着运行规约
Qlive和Hbase选择
待整理
mpi并行程序设计
mpi并行程序设计
mpi错误
int nproc; MPI_Comm_size( MPI_COMM_WORLD, &nproc); MPI_Comm_rank( MPI_COMM_WORLD, &rank); int allName[nproc]; int num=rank+1; MPI_Gather(&num, 1, MPI_INT, allName,nproc, MPI_INT, 0,MPI_COMM_WORLD); i
MPI 学习笔记
message passing model the Message Passing Interface (MPI) - standard interface MPI is only a definition for an interface 几个重要的概念 communicator: 由一系列进程组成,拥有沟通的能力 每个进程都有 rank 沟通交流靠秩 + tag(标记信息) point-to-p
mpi测试结果
Final测试结果 1041张训练集EPE=2.537 以下为测试集结果 FlowNetS+ft+v,论文中训练集EPE=4.44 以下为测试集结果 Clean测试结果 1041张训练集EPE=2.264 以下是测试集结果: 官方FlowNet训练集误差3.36 以下为测试集结果 ...
MPI并行程序设计
mpi并行程序设计
MPI 并行程序设计
李三立编写的高性能并行计算的数据 适合MPI入门 MPI精华全含其中
MPI学习笔记
++mpi基础教程点击++ mpi官方手册 目前两种最重要的并行编程模型是数据并行和消息传递. 对于机群系统一次通信的开销要远远大于一次计算的开销 应尽可能降低通信的次数. 目前主要的mpi实现 mpich chimp lam 理论上说MPI所有的通信功能可以用它的6个基本的调用来实现 MPI_Init(&amp;amp;amp;amp;amp;amp;amp;argc, &amp;amp;amp;amp;amp;amp;amp;argv) //初始化MPI执行环境,建立多个MPI...
Linux系统安装MPI
1.从MPICH2官网下载源代码 http://www.mcs.anl.gov/research/projects/mpich2/downloads/tarballs/1.0.8/mpich2-3.2.tar.gz2.然后,通过Xshell工具连接虚拟机文件系统,将mpich2-3.2.tar.gz放入虚拟机中。3.解压到/home/mpi/mpich2中,tar -xzvf /home/mpi/...
MPI简介
MPI简介 (消息传递接口是一种编程接口标准,而不是一种具体的编程语言。) 多线程是一种便捷的模型,其中每个线程都可以访问其它线程的存储空间。因此,这种模型只能在共享存储系统之间移植。一般来讲,并行机不一定在各处理器之间共享存储,当面向非共享存储系统开发并行程序时,程序的各部分之间通过来回传递消息的方式通信。要使得消息传递方式可移植,就需要采用标准的消息传递库。这就促成的消息传递接口(
MPI参考手册
MPI库的一些API函数,可以当作手册来使用。
MPI并行编程
《MPI并行编程》讲义,PPT文档。<br>
MPI问题
、今天尝试安装了mpich,因为上课有用,所以就来试着安装以下。。rn2、前面还算是比较顺利,到最后遇见了一个问题:rnrnmpiexec_ubuntu: cannot connect to local mpd (/tmp/mpd2.console_jey); possible causes:rn1. no mpd is running on this hostrn2. an mpd is running but was started without a "console" (-n option)rnrn在网上查了一下,都说是mpdboot没有启动,可是在运行前我明明启动了的,不过好像有点问题,我将运行的结果贴出来:rnrnmpdbootrn/usr/local/bin/mpdboot:53: DeprecationWarning: The popen2 module is deprecated. Use the subprocess module.rnfrom popen2 import Popen4, Popen3, popen2rn/usr/local/bin/mpdlib.py:15: DeprecationWarning: the md5 module is deprecated; use hashlib insteadrnfrom md5 import new as md5newrn/usr/local/bin/mpdlib.py:8: DeprecationWarning: The popen2 module is deprecated. Use the subprocess module.rnimport sys, os, signal, popen2, socket, select, inspectrn/usr/local/bin/mpdlib.py:15: DeprecationWarning: the md5 module is deprecated; use hashlib insteadrnfrom md5 import new as md5newrnmpdboot_ubuntu (handle_mpd_output 373): from mpd on ubuntu, invalid port info:rn/usr/local/bin/mpdlib.py:8: DeprecationWarning: The popen2 module is deprecated. Use the subprocess module.rnimport sys, os, signal, popen2, socket, select, inspectrn/usr/local/bin/mpdlib.py:15: DeprecationWarning: the md5 module is deprecated; use hashlib insteadrnfrom md5 import new as md5newrn57481rn57481rnrnjey@ubuntu:~/Jeydragon/program$ /usr/local/bin/mpdlib.py:8: DeprecationWarning: The popen2 module is deprecated. Use the subprocess module.rnimport sys, os, signal, popen2, socket, select, inspectrn/usr/local/bin/mpdlib.py:15: DeprecationWarning: the md5 module is deprecated; use hashlib insteadrnfrom md5 import new as md5newrn然后我运行:rnmpirun -n 2 ./hello.outrnrn结果显示:rn/usr/local/bin/mpdlib.py:8: DeprecationWarning: The popen2 module is deprecated. Use the subprocess module.rnimport sys, os, signal, popen2, socket, select, inspectrn/usr/local/bin/mpdlib.py:15: DeprecationWarning: the md5 module is deprecated; use hashlib insteadrnfrom md5 import new as md5newrnmpiexec_ubuntu: cannot connect to local mpd (/tmp/mpd2.console_jey); possible causes:rn1. no mpd is running on this hostrn2. an mpd is running but was started without a "console" (-n option)rnrn我想我表达的已经很详细了,这应该是中间一个小小的问题,希望高手指点一下,先感谢了!!!rnrnrn
MPI消息传递接口:LAM/MPI和MPICH安装与配置
随着科学技术的发展,并行计算已经普及到各个领域,人们对高性能计算的需要也越来越大。消息传递接口MPI作为全世界工业、科研机构以>及政符联合制定的一个标准,有力地促进了并行计算的发展。LAM/MPI和MPICH是目前使用最为广泛的免费MPI实现版本,它们都支持MPI 1标准 的全部内容,同时还支持部分MPI 2标准。本文介绍了这两种免费实现版本在Linux平台上的安装配置过程及方法。
【mpi程序界面】----mpi程序如何加入界面
探索当中,希望知道答案的朋友能够帮帮我rn我用的开发环境是Visual Studio 2005,编程语言为C++rnrn
MPI 实验报告
1.Linux操作系统下,下载MPICH2,在单机上配置基本环境,测试MPI基本程序; 2.使用2-4台计算机在同一局域网下搭建集群计算系统,验证构建的集群能够利用MPI进行并行计算。
MPI allgather
MPI allgather,用发送函数和接收函数实现的,c语言描述,用ie打开看
矩阵乘法 mpi
基于mpi的并行计算算法 矩阵乘法 C/C++
MPI的开源代码
OpenMPI的代码实现,有需要的,或者需要MPI运行环境的,下载这个安装好环境就可以运行MPI
mpi programming
Practical MPI Programming MPI Programming Guide Parallel Programming in OpenMP
MPI笔记
MPI笔记Leoeon 2014.07.30MPI笔记 基本框架 点对点通信 1 阻塞型通信函数 2 缓冲通信 3 非阻塞通信 4 持久通信 集合通信 1 阻塞 2 广播 3 汇总与散射 4 汇总与散射 5 归约操作 派生数据类型 1 派生类型 2 打包 进程组与通信子 1 进程组 2 通信子 3 结合 辅助拓扑 1 笛卡尔拓扑 2 无向图拓扑 其他 1 编译与运行 2 IO处理 3 空对象1 基
MPI程序设计
详细介绍了MPI技术的原理,编程方法和程序设计技巧,是MPI程序设计学习的入门教材!
MPI之数据类型
我们知道,比较基本的MPI点对点通信具有无法同时发送不同数据类型(当然前面提到了可以使用MPI_PACKED,但是这样会造成性能的极大损耗),因此MPI提供说明更通用的,混合的非连续通信缓冲区的机制.直到执行(implementation)时再决定数据应该在发送之前打包到连续缓冲中,还是直接从数据存储区收集。这里提供的通用机制允许不需拷贝,而是直接传送各种形式和大小的目标.我们并没有假设MPI库是用
MPI编程问题(*)
有一个二维数组a[N][N],想用并行的方法对其求和,请问如何实现rn是将数组放入VECTOR里面传递给进程还是用其他方法,会不会通信比计算的时间还会长?rn请高手指点一二。
MPI参考手册 MPI函数的C接口
给出主要MPI函数的参考手册。为了节省篇幅,这里仅列出MPI函数的C接口,Fortran 接口子程序的参数与C 接口函数的参数完全类似。除MPI_Wtime和MPI_Wtick外,Fortran接口子程序比C接口函数在最后多出一个整型参数,用于返回错误码。
mpi第五站 - 自定义mpi中的广播
#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;cstdlib&gt; #include &lt;time.h&gt; #include &lt;mpi.h&gt; using namespace std; void my_bcast(void* data, int count, MPI_Datatype datat...
MPI并行计算
主要是mpi入门级操作,sendbuf,sendcount,sendtype, 发送方地址,发送方数据个数,发送方数据类型 dest,sendtag, 目标进程标识,发送消息标识 recvbuf,recvcount,recvtype,接收方的地址 个数 类型 source,recvtag,comm,status 源进程标识 接受消息标识 通信域 返回的状态
MPI参考手册·
并行MPI技术参考手册。mpich2 高性能计算
相关热词 c#入门推荐书 c# 解码海康数据流 c# xml的遍历循环 c# 取 查看源码没有的 c#解决高并发 委托 c#日期转化为字符串 c# 显示问号 c# 字典对象池 c#5.0 安装程序 c# 分页算法