基于多核处理器的常见计算任务分析与优化

《基于多核处理器的常见计算任务分析与优化》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于多核处理器的常见计算任务分析与优化摘要本文介绍了三种常见计算任务中针对多核处理器的性能分析与优化设计的新技术，这三种常见计算任务分别是：广泛用于组合搜索与优化的动态规划算法（DP,DynamicProgramming），广泛用于科学计算的矩阵计算，以及集群（Cluster）这样传统的并行计算技术。针对动态规划算法，从其一般形式入手，介绍非连续多元动态规划算法在多核处理器环境下的一系列优化技术；针对矩阵计算，介绍针对多核处理器环境的乱序调度算法；针对多核集群，分析了多核处理器对传统集群技术带来的性能，特别是通信性能上的影响。关键词：多核、动态规划、集群、

2、矩阵计算1　引言人们追求计算能力的脚步从没有放缓，过去数十年的发展证明了摩尔定律——微处理器的性能将以指数方式增长，即每两年翻一番。但是目前的技术已经难以通过提高频率来维持这种增长速度，一个主要的问题就是过度产热（overheat）问题，以及能耗问题。因此，多核处理器设计应运而生，即在同一块芯片上放置两个甚至更多处理核心，通过将应用程序的工作复杂分担到不同的核心来提高应用程序性能。这种处理器也被称为片内多处理器（CMP,ChipMultiprocessor）。本文2至4章将介绍多核处理器对三种常见计算任务的性能影响与相应计算任务的优化设计。这三种计算任务分

3、别是广泛用于组合搜索与优化的动态规划算法（DP,DynamicProgramming），广泛用于科学计算的矩阵计算，以及集群（Cluster）这样传统的并行计算技术。针对动态规划算法，从其一般形式入手，介绍非连续多元动态规划算法在多核处理器环境下的一系列优化技术；针对矩阵计算，介绍针对多核处理器环境的乱序调度算法；针对多核集群，分析了多核处理器对传统集群技术带来的性能，特别是通信性能上的影响。2　动态规划算法的分析与优化2.1　动态规划算法简介动态规划算法（DynamicProgramming,DP）是一种经典的，且为人熟知的算法，用于解决各种组合搜索与优

4、化问题，广泛应用于任务调度、资源管理、自动控制、VLSI设计与生物医学等应用中。动态规划算法的核心是动态规划方程（组），根据方程组，如果每一个子问题的解D[i]只依赖于与其直接相邻的子问题的解，则称其为连续的（Serial），否则，若D[i]依赖于多个非直接相邻的子问题的解，则称其为非连续的（Non-serial）；如果D[i]的函数式中只包含一个递归项，即形如D[i]=Max0

5、续动态规划算法（serialmonadic），如单求解源最短路问题的Dijkstra算法、0/1背包问题；·多元连续动态规划算法（serialpolyadic），如求解全部点对之间最短路的Floyd；·一元非连续动态规划算法（nonserialmonadic），如最长公共子序列问题、寻找序列最优相似比较的Smith-Waterman；·多元非连续动态规划算法（nonserialpolyadic），如最优矩阵添括号问题、RNA二级结构预测所使用的Zuker算法。在这种分类方法中，多元非连续动态规划算法最具有可并行性，一元非连续动态规划和多元连续动态规划算法次

6、之，一元连续动态规划算法几乎不具备可并行计算的部分。对于一元连续动态规划算法，我们只能依靠处理器内部实现的动态调度算法来实现简单的指令级并行，而对于多元非连续动态规划算法，则可以充分利用多核处理器的特性来提高其性能，2.2-2.6中将介绍多元非连续动态规划算法在多核处理器上的一种优化方法。2.2　动态规划方程（组）Zuker是非连续多元动态规划算法的一个典型例子，它是预测RNA二级结构的基对最大化算法。对给定的RNA序列，令S(i,j)表示自索引i至j的RNA子序列折叠结果，其数值表示折叠后的最高基对数量或者是最小自由能。其对应的动态规划方程组如下：Si,

7、j=Si+1,j-1+1Si+1,jSi,j-1maxi

8、,j,&0≤i