对并行算法的介绍和展望——学期大作业

《计算机系统结构》大作业

对并行算法的介绍和展望

专 业 计算机科学与技术

班 级 111

学 号 111425020133

姓 名 完颜杨威

日 期 2014年4月17日

河南科技大学国际教育学院

对并行算法的介绍和展望

我们知道，算法是求解问题的方法和步骤。而并行算法就是用多台处理机联合求解问题的方法和步骤，其执行过程是将给定的问题首先分解成若干个尽量相互的子问题，然后使用多台计算机同时求解它，从而最终求得原问题的解。并行算法的研究涉及到理论、设计、实现、应用等多个方面，要保持并行算法研究的持续性和完整性，需要建立一套完整的“理论－设计－实现－应用”的学科体系，也就是所谓的并行算法研究的生态环境。其中，并行算法理论是并行算法研究的理论基础，包含并行计算模型和并行计算复杂性等；并行算法的设计与分析是并行算法研究的核心内容；并行算法的实现是并行算法研究的应用基础，包含并行算法实现的硬件平台和软件支撑技术等；并行应用是并行算法研究的发

展动力，除了包含传统的科学工程计算应用外，还有新兴的与社会相关的社会服务型计算应用等。

并行算法主要分为数值计算问题的并行算法和非数值计算问题的并行算法。而并行算法的研究主要分为并行计算理论、并行算法的设计与分析、和并行算法的实现三个层次。现在，并行算法之所以受到极大的重视，是为了提高计算速度、提高计算精度，以及满足实时计算需要等。然而，相对于串行计算，并行计算又可以划分成时间并行和空间并行。时间并行即流水线技术，空间并行使用多个处理器执行并发计算，当前研究的主要是空间的并行问题。并行算法是一门还没有发展成熟的学科，虽然人们已经总结出了相当多的经验，但是远远不及串行算法那样丰富。并行算法设计中最常用的的方法是PCAM方法，即划分，通信，组合，映射。首先划分，就是将一个问题平均划分成若干份，并让各个处理器去同时执行；通信阶段，就是要分析执行过程中所要交换的数据和任务的协调情况，而组合则是要求将较小的问题组合到一起以提高性能和减少任务开销，映射则是要将任务分配到每一个处理器上。任何一个并行算法必须在一个科学的计算模型中进行设计。我们知道，任何算法必须有计算模型。任何并行计算模型必须要有为数不多、有明确定义的、可以定量计算的或者可以实际测量的参数，这些参数可以构成相应函数。并行计算模型是算法设计者与体系结构研究者之间的一个桥梁，是并行算法设计和分析的基础。它屏蔽了并行机之间的差异，从并行机中抽取若干个能反映计算特性的可计算或可测量的参数，并按照模型所定义的计算行为构造成本函数，以此进行算法的复杂度分析。

经过多年的发展，我国在并行算法的研究上也取得了显著进展，并行计算的应用已遍布天气预报、石油勘探、航空航天、核能利用、生物工程等领域，理论研究与应用普及均取得了很大发展。随着高性价比可扩展集群并行系统的逐步成熟和应用，大规模电力系统潮流并行计算和分布式仿真成为可能。目前，并行算法在地震数据处理中应用已较为成熟，近年来向更实用的基于PC机群的并行技术发展.然而，在非地震方法中，并行算法应用较

少见文献报道，研究尚处于初级研究阶段。在大地电磁的二维和三维正、反演问题上，并行计算技术逐渐得到越来越多关注和重视.随着资源和能源需求的增长，地球物理勘探向深度和广度快速发展，大幅增长的数据量使得高性能并行计算机和高效的并行算法在勘探地球物理学中的发展和应用将占据愈来愈重要的地位。计算机技术在生物医学领域已经广泛应用，实践证明，并行算法在生物医学工程的各个领域中具有广泛的应用价值，能有效提高作业效率。随着电子科学技术的发展，电磁问题变得越来越复杂，为了在有限的计算机资源条件下求解大规模复杂电磁问题，许电磁学家已致力于并行算法的研究。接下来，不得不说的是云计算，很长时间以来，云计算已成了一个热闹词汇。云计算特有的优点和巨大的商业前景，让其成为了近年来的IT界最热门词汇之一。当然，这也与中国移动互联网的繁荣紧密相关，它们需要有相应的云计算服务作为支撑。但是，国内云服务商多数采用过于简单粗放的“远程机房+移动大硬盘”模式，不能满足并行图形处理的计算需求，“应尽快认清技术潮流，整合前沿计算工具，以便推进云GPU并行计算服务。在这里，并行算法更是这一技术的关键。

从上述实例可以看出，并行算法不但涉及的领域广泛，而且更是在各领域中起着至关重要的作用。我们在建立了“理论－设计－实现－应用”的并行算法研究的生态链后,根据其中某一部分的新的发展，就可以推动其他部分的研究，从而维持并行算法研究的可持续性发展。比如，当新的并行计算模型被提出后，研究者便可在其上进行许多经典问题的并行算法研究。又如当来自于实际的新应用问题时，则又会给研究者提供了研究求解新问题的新并行算法等等。传统的并行计算任务往往由大型的并行计算机来完成，因而并行机的研究也就成为并行计算的主要研究方向，典型的并行计算机系统包括阵列处理机、向量处理机、共享存储多处理机、分布式存储多计算机和分布式共享存储多处理机，而进行并行研究的也大多为实力雄厚的科研机构和企业。随着网络的快速发展，基于机群网络的并行计算也成为并行计算研究的一个重要方向。只是拥有机群网络是无法直接进行并行计算的，研究人员在机群网络上实现了一系列的网络通信工具和辅助编程工具以支持基于机群网络

的并行计算。并行算法的常规研究内容包括：(1) 并行计算模型。并行算法作为一门学科，首先研究的是并行计算模型。(2) 设计技术并行算法研究的第二部分是并行算法的设计技术。（3）并行算法分为多机并行和多线程并行。20世纪90年代中期，并行算法研究向更宽泛、更实用的方向扩展。在这期间，并行算法研究向并行计算方向扩展，此时的并行计算向更实用的方向扩展。

现今，尽管我国高性能计算机的发展取得了长足的进步，每秒数十亿次计算能力的并行机相继研制成功。但与之形成鲜明反差的是高性能计算机的峰值性能与其实际应用水平差距很大。并行计算是提升运算效率、缩小这一差距的重要基础。总之，并行算法还需要相当多完善的地方。 并行算法与串行算法最大的不同之处在于，并行算法不仅要考虑问题本身，而且还要考虑所使用的并行模型，网络连接等等。为了并行算法的更好的长远发展，我认为，我们要解决“并行算法本身的研究低调”的问题，需要我们建立完整的学科研究体系，建立一套“理论→设计→实现→应用”完整的研究体系。只有懂得了并行算法的体系结构，所设计出的并行算法的效率才会高。这样还不够，还把自己的身价降下去，要到实践中去，要拜用户为上帝。并行算法的研究不能仅仅是科学家的事情，在我国国民经济建设的主战场当中，有很多并行算法的应用领域。这就要求我们要用诚意感动、说服用户，帮助用户找到典型应用。这样才能保持并行算法研究的可持续发展。针对并行算法研究中存在的缺乏实用性的问题，要建立“结构→算法→编程”的一体化研究方法。研究并行计算的人一定要懂并行计算机，作为并行算法的设计者，一定要清楚地知道如何在并行计算机上实现这一算法。这样才能确保并行算法研究的实用性。要解决并行计算研究不够普遍的问题，必须重视人才的培养。目前，在国内的高校中有多少开设了并行计算这门课？据我所知并不多。即使在那些超级高校中也未必都开设了并行计算课程。这就使得并行计算人才的系统培养出现短缺。所以我极力主张，要在高校中开设并行计算课程，要重视培养并行算法研究和应用的高层次人才，为并行计算的普及奠定坚实的基础。

然而，并行计算在不同的时期，研究的重点是不一样的。当今并行计算的研究主要有两大方向。一个是并行计算，一个是并行应用。目前，并行算法的研究正在向并行计算转移。并行计算的基本研究内容包括：体系结构、并行算法和并行编程。随着社会科学技术的不断发展，我们需要不断调整研究方向。展望并行算法研究的新走向是：并行算法研究内容不断拓宽，并行计算被纳入研究范畴；与广大用户领域结合，注重应用，强调走到用户中去，为用户解决问题；重视新的、非常规计算模式，如神经计算、分子计算和量子计算等，这些模式能够解决某类特定问题，有其自身的优越性。现今并行算法的研究更讲究实用，更多地集中在应用领域并行算法研究上，例如近年来涌现出的计算生物学、计算流体动力学、数据库管理和计算机辅助设计等等。近年来，并行算法的研究更强调算法设计与具体实现方法相结合。研究并行计算的算法固然重要，但更要注重并行计算应用的研究；要及时将更好的算法和最新的研究成果投入到实际应用中，从而使高性能计算机充分发挥其效能，使之在实际中发挥更大的作用，让社会蓬勃发展，让世界更加美好。