神马文学网并行算法研究进展
来源：百度文库 编辑：神马文学网 时间：2024/05/02 07:20:51
http://media.ccidnet.com/media/ciw/1343/e0501.htm
编者语
并行计算迈入新阶段
尽管我国高性能计算机的发展取得了长足的进步，每秒数十亿次计算能力的并行机相继研制成功。但与之形成鲜明反差的是高性能计算机的峰值性能与其实际应用水平差距很大。并行计算是提升运算效率、缩小这一差距的重要基础。经过多年的发展，我国在并行算法的研究上也取得了显著进展，并行计算的应用已遍布天气预报、石油勘探、航空航天、核能利用、生物工程等领域，理论研究与应用普及均取得了很大发展。
近日，第八届全国并行计算学术会议在大连召开。此次会议的成功举行，昭示了我国并行计算领研究工作进入了新阶段，尤其可喜的是，在这次反映并行计算领域最高水平的学术交流活动中，青年学者所占比例超过了80%，使我国在这一领域的研究呈现生机勃勃的兴旺景象。与会专家一致认为：研究并行计算的算法固然重要，但更要注重并行计算应用的研究；要及时将更好的算法和最新的研究成果投入到实际应用中，从而使高性能计算机充分发挥其效能，使之在社会中发挥更大的作用。
专题内容
并行计算迈入新阶段
可视化并行处理的三种方式
共创NC的设计与实现
专题策划：刘雨
专题撰稿：
装备指挥技术学院电子工程系
淡鹏 张文 李晓梅
北京共创开源软件股份有限公司
董孝峰
中国科学院院士、中国科技大学教授
国家高性能计算中心（合肥）主任
陈国良
我们知道，算法是求解问题的方法和步骤。而并行算法则是指用多台计算机联合求解问题的方法和步骤。现在，并行算法之所以受到极大的重视，是为了提高计算速度（单机受物理速度限制无法满足）、提高计算精度（加密、计算网格等）以及满足实时计算需要（数值天气预报等）。
并行算法主要分为数值计算问题的并行算法（矩阵运算、方程组求解等）和非数值计算问题的并行算法（排序、搜索、图论算法、组合优化等）。
并行算法的研究主要分为并行计算理论（计算模型、下界，问题可并行性，NC类和P-完全性）、并行算法的设计与分析（NC类问题的有效并行算法的设计和分析方法）和并行算法的实现（硬件平台与软件支撑）三个层次。
并行算法研究的新机遇
20世纪70年代～80年代是非数值并行算法研究的辉煌时期。在这期间，并行计算的研究出现了很多设计思想非常巧妙的算法，许多并行计算的算法都是那段时间出现的，那些算法都已收入我们现在的并行算法的教科书中。
20世纪90年代中期，并行算法研究向更宽泛、更实用的方向扩展。在这期间，并行算法研究向并行计算方向扩展，此时的并行计算向更实用的方向扩展。如果你在网上搜索这个时期有关并行计算论文的话，就会发现，这时候的并行计算的论文大都出现在应用领域，真正研究算法的文章则不多。
以前我们在大学开设并行算法课时，学生一般都是纸上谈兵，没有机会将这些算法在并行计算机上实现。那时候的并行计算机都很贵，当时全国高校没有多少并行计算机，当时一般的高校中，甚至是当时的一些超级重点大学中，并行计算机也不多见。
现在情况不一样了，半导体工艺的改进，计算机技术与通信网络的发展，使得我们现在也有条件使用高端并行计算机了。同时，我们也可以用PC机群搭建并行计算环境。许多学校利用几台PC机，通过网络设备将它们连接起来，再利用相应的软件就可以搭建并行计算的实验环境。因此，随着PC机群的日益普及，使得现在一般的高校都可以开设并行计算的课程。从而使得并行计算的研究迎来了新的发展机遇。
并行算法研究的主要内容
任何一个并行算法必须在一个科学的计算模型中进行设计。我们知道，任何算法必须有计算模型。任何并行计算模型必须要有为数不多、有明确定义的、可以定量计算的或者可以实际测量的参数，这些参数可以构成相应函数。目前主流的并行计算模型有：
PRAM（Parallel Random Access Machine）：共享存储的SIMD模型（包括EREW、CREW 、CRCW模型）；
APRAM（phase PRAM）：共享存储的MIMD模型（分相计算）；
BSP（Bulk Synchronous Parallel）：分布存储的MIMD模型（大同步并行，超级步计算，模型参数p、g、L，成本函数）；
LogP：分布存储的MIMD模型（异步并行，点到点通信，模型参数l、0、g、p）；
NHBL（非独占异构分时计算）：分布式PC机群模型；
并行算法虽然五花八门，但经过这么年的发展，也能总结出一般的基本算法。常见的基本算法有：
划分法（partitioning）：最朴素的方法，等分划分，并行求解；
分治法（divide-and-conquer）：逐次由大到小，递归求解；
流水线方法（pipelining）：空间并行，时间重叠；
随机法（randomization）：不确定性算法，算法步引入随机性；
平衡树法（balanced-tree）：求最大/最小等在树上进行；
倍增发（doubling）：指针跳跃，适于求表等问题；
迭代法（iteration）：数值求解法。
此外，并行算法的研究还包括并行复杂性理论。
并行算法研究的主要方向
并行计算在不同的时期，研究的重点是不一样的。当今并行计算的研究主要有两大方向。一个是并行计算，一个是并行应用。
近年来，并行算法的研究更强调算法设计与具体实现方法相结合。目前，并行算法的研究正在向并行计算转移。并行计算的基本研究内容包括：体系结构、并行算法和并行编程。
现今并行算法的研究更讲究实用，更多地集中在应用领域并行算法研究上，例如近年来涌现出的计算生物学、计算流体动力学、数据库管理和计算机辅助设计等等。
此外，并行算法研究的一个新的发展方向是非传统计算方式，它主要包括：
神经计算：利用大量神经元（1012）并行分布式处理；
分子计算：利用大量（分子数1020）分子参与计算，以空间换时间来提高计算能力；
量子计算：利用量子相干叠加原理，使得基于量子位的量子计算具有强大的并行性。
目前存在的问题及对策
目前的并行计算研究主要存在下面三大问题：
一、近几年，并行算法本身的研究呈现低调的局面。
二、优秀的理论成果缺乏实用性，一些研究的结论的确非常漂亮，但拿到实际应用当中却不好用，无法推广。
三、并行算法的研究及推广还不够普遍。把并行算法的研究做得非常深入的人还很少。现有的并行计算机的应用还存在着浪费现象。
针对上面所提到的并行计算研究中存在的三个问题，我们应该通过下面三个措施予以解决。
一、建立完整的科学研究体系
要解决“并行算法本身的研究低调”的问题，需要我们建立完整的学科研究体系，建立一套“理论→设计→实现→应用”完整的研究体系。只有懂得了并行算法的体系结构，所设计出的并行算法的效率才会高
这样还不够，还把自己的身价降下去，要到实践中去，要拜用户为上帝。并行算法的研究不能仅仅是科学家的事情，在我国国民经济建设的主战场当中，有很多并行算法的应用领域。这就要求我们要用诚意感动、说服用户，帮助用户找到典型应用。这样才能保持并行算法研究的可持续发展。
二、形成一体化的研究方法
针对并行算法研究中存在的缺乏实用性的问题，要建立“结构→算法→编程”的一体化研究方法。研究并行计算的人一定要懂并行计算机，作为并行算法的设计者，一定要清楚地知道如何在并行计算机上实现这一算法。这样才能确保并行算法研究的实用性。
三、要重视人才培养
要解决并行计算研究不够普遍的问题，必须重视人才的培养。目前，在国内的高校中有多少开设了并行计算这门课？据我所知并不多。即使在那些超级高校中也未必都开设了并行计算课程。这就使得并行计算人才的系统培养出现短缺。所以我极力主张，要在高校中开设并行计算课程，要重视培养并行算法研究和应用的高层次人才，为并行计算的普及奠定坚实的基础。 （E1）
（根据陈国良院士在第八届全国并行计算大会的演讲录音整理，未经本人审阅）
编者语
并行计算迈入新阶段
尽管我国高性能计算机的发展取得了长足的进步，每秒数十亿次计算能力的并行机相继研制成功。但与之形成鲜明反差的是高性能计算机的峰值性能与其实际应用水平差距很大。并行计算是提升运算效率、缩小这一差距的重要基础。经过多年的发展，我国在并行算法的研究上也取得了显著进展，并行计算的应用已遍布天气预报、石油勘探、航空航天、核能利用、生物工程等领域，理论研究与应用普及均取得了很大发展。
近日，第八届全国并行计算学术会议在大连召开。此次会议的成功举行，昭示了我国并行计算领研究工作进入了新阶段，尤其可喜的是，在这次反映并行计算领域最高水平的学术交流活动中，青年学者所占比例超过了80%，使我国在这一领域的研究呈现生机勃勃的兴旺景象。与会专家一致认为：研究并行计算的算法固然重要，但更要注重并行计算应用的研究；要及时将更好的算法和最新的研究成果投入到实际应用中，从而使高性能计算机充分发挥其效能，使之在社会中发挥更大的作用。
专题内容
并行计算迈入新阶段
可视化并行处理的三种方式
共创NC的设计与实现
专题策划：刘雨
专题撰稿：
装备指挥技术学院电子工程系
淡鹏 张文 李晓梅
北京共创开源软件股份有限公司
董孝峰
中国科学院院士、中国科技大学教授
国家高性能计算中心（合肥）主任
陈国良
我们知道，算法是求解问题的方法和步骤。而并行算法则是指用多台计算机联合求解问题的方法和步骤。现在，并行算法之所以受到极大的重视，是为了提高计算速度（单机受物理速度限制无法满足）、提高计算精度（加密、计算网格等）以及满足实时计算需要（数值天气预报等）。
并行算法主要分为数值计算问题的并行算法（矩阵运算、方程组求解等）和非数值计算问题的并行算法（排序、搜索、图论算法、组合优化等）。
并行算法的研究主要分为并行计算理论（计算模型、下界，问题可并行性，NC类和P-完全性）、并行算法的设计与分析（NC类问题的有效并行算法的设计和分析方法）和并行算法的实现（硬件平台与软件支撑）三个层次。
并行算法研究的新机遇
20世纪70年代～80年代是非数值并行算法研究的辉煌时期。在这期间，并行计算的研究出现了很多设计思想非常巧妙的算法，许多并行计算的算法都是那段时间出现的，那些算法都已收入我们现在的并行算法的教科书中。
20世纪90年代中期，并行算法研究向更宽泛、更实用的方向扩展。在这期间，并行算法研究向并行计算方向扩展，此时的并行计算向更实用的方向扩展。如果你在网上搜索这个时期有关并行计算论文的话，就会发现，这时候的并行计算的论文大都出现在应用领域，真正研究算法的文章则不多。
以前我们在大学开设并行算法课时，学生一般都是纸上谈兵，没有机会将这些算法在并行计算机上实现。那时候的并行计算机都很贵，当时全国高校没有多少并行计算机，当时一般的高校中，甚至是当时的一些超级重点大学中，并行计算机也不多见。
现在情况不一样了，半导体工艺的改进，计算机技术与通信网络的发展，使得我们现在也有条件使用高端并行计算机了。同时，我们也可以用PC机群搭建并行计算环境。许多学校利用几台PC机，通过网络设备将它们连接起来，再利用相应的软件就可以搭建并行计算的实验环境。因此，随着PC机群的日益普及，使得现在一般的高校都可以开设并行计算的课程。从而使得并行计算的研究迎来了新的发展机遇。
并行算法研究的主要内容
任何一个并行算法必须在一个科学的计算模型中进行设计。我们知道，任何算法必须有计算模型。任何并行计算模型必须要有为数不多、有明确定义的、可以定量计算的或者可以实际测量的参数，这些参数可以构成相应函数。目前主流的并行计算模型有：
PRAM（Parallel Random Access Machine）：共享存储的SIMD模型（包括EREW、CREW 、CRCW模型）；
APRAM（phase PRAM）：共享存储的MIMD模型（分相计算）；
BSP（Bulk Synchronous Parallel）：分布存储的MIMD模型（大同步并行，超级步计算，模型参数p、g、L，成本函数）；
LogP：分布存储的MIMD模型（异步并行，点到点通信，模型参数l、0、g、p）；
NHBL（非独占异构分时计算）：分布式PC机群模型；
并行算法虽然五花八门，但经过这么年的发展，也能总结出一般的基本算法。常见的基本算法有：
划分法（partitioning）：最朴素的方法，等分划分，并行求解；
分治法（divide-and-conquer）：逐次由大到小，递归求解；
流水线方法（pipelining）：空间并行，时间重叠；
随机法（randomization）：不确定性算法，算法步引入随机性；
平衡树法（balanced-tree）：求最大/最小等在树上进行；
倍增发（doubling）：指针跳跃，适于求表等问题；
迭代法（iteration）：数值求解法。
此外，并行算法的研究还包括并行复杂性理论。
并行算法研究的主要方向
并行计算在不同的时期，研究的重点是不一样的。当今并行计算的研究主要有两大方向。一个是并行计算，一个是并行应用。
近年来，并行算法的研究更强调算法设计与具体实现方法相结合。目前，并行算法的研究正在向并行计算转移。并行计算的基本研究内容包括：体系结构、并行算法和并行编程。
现今并行算法的研究更讲究实用，更多地集中在应用领域并行算法研究上，例如近年来涌现出的计算生物学、计算流体动力学、数据库管理和计算机辅助设计等等。
此外，并行算法研究的一个新的发展方向是非传统计算方式，它主要包括：
神经计算：利用大量神经元（1012）并行分布式处理；
分子计算：利用大量（分子数1020）分子参与计算，以空间换时间来提高计算能力；
量子计算：利用量子相干叠加原理，使得基于量子位的量子计算具有强大的并行性。
目前存在的问题及对策
目前的并行计算研究主要存在下面三大问题：
一、近几年，并行算法本身的研究呈现低调的局面。
二、优秀的理论成果缺乏实用性，一些研究的结论的确非常漂亮，但拿到实际应用当中却不好用，无法推广。
三、并行算法的研究及推广还不够普遍。把并行算法的研究做得非常深入的人还很少。现有的并行计算机的应用还存在着浪费现象。
针对上面所提到的并行计算研究中存在的三个问题，我们应该通过下面三个措施予以解决。
一、建立完整的科学研究体系
要解决“并行算法本身的研究低调”的问题，需要我们建立完整的学科研究体系，建立一套“理论→设计→实现→应用”完整的研究体系。只有懂得了并行算法的体系结构，所设计出的并行算法的效率才会高
这样还不够，还把自己的身价降下去，要到实践中去，要拜用户为上帝。并行算法的研究不能仅仅是科学家的事情，在我国国民经济建设的主战场当中，有很多并行算法的应用领域。这就要求我们要用诚意感动、说服用户，帮助用户找到典型应用。这样才能保持并行算法研究的可持续发展。
二、形成一体化的研究方法
针对并行算法研究中存在的缺乏实用性的问题，要建立“结构→算法→编程”的一体化研究方法。研究并行计算的人一定要懂并行计算机，作为并行算法的设计者，一定要清楚地知道如何在并行计算机上实现这一算法。这样才能确保并行算法研究的实用性。
三、要重视人才培养
要解决并行计算研究不够普遍的问题，必须重视人才的培养。目前，在国内的高校中有多少开设了并行计算这门课？据我所知并不多。即使在那些超级高校中也未必都开设了并行计算课程。这就使得并行计算人才的系统培养出现短缺。所以我极力主张，要在高校中开设并行计算课程，要重视培养并行算法研究和应用的高层次人才，为并行计算的普及奠定坚实的基础。 （E1）
（根据陈国良院士在第八届全国并行计算大会的演讲录音整理，未经本人审阅）