同步并行算法

关键词： 并行算法 数值 计算机

同步并行算法（精选八篇）

同步并行算法 篇1

早期发展起来的以Von Nenman型计算机为工具的串行处理技术,其信号处理与数值计算速度因受到顺序处理、电信号传播速度以及器件本身的开关速度等因素的影响,越来越滞后于来自大型工程设计的数值分析与科学计算的需要。为了克服传统的Von Nenman型计算机结构对提高运行速度的限制,从60年代起人们就开始并行化技术和计算结构的并行化设计方法的研究。近二十年来,以并行计算技术、并行算法和并行计算机结构为核心的并行化技术得到了长足的发展。

并行计算是计算数学与新一代计算机相结合的产物,是工程与科学研究领域中出现的大规模科学计算的理论基础,是解决规模巨大、时限要求严格的数值计算问题的工具,是对串行计算机技术的革新[1,2,3]。

粒子群优化算法在诸多演化算法中是一种基于群体智能的演化迭代算法,由Kennedy博士和Eberhare教授源于鸟群和鱼群捕食运动行为的研究而提出[4]。与其它演化算法相比,其具有概念简单、个体数目少、计算容易实现等特点,在各类无约束优化、有约束优化、神经网络、模糊控制、路径规划、多目数优化等问题中取得了非常好的应用[5]。因PSO算法易陷入局部极值点,人们对PSO的基本算法提出了许多改进版本[6,8]。文献[6]依据人类的社会活动经验,在粒子群中引入组织的概念,一方面粒子依据自身的最优经验和组织的最优经验进行位置更新,另一方面对组织进行优存劣汰,并产生新组织,保持粒子群的多样性,避免算法的早熟收敛。但该算法在克服早熟收敛问题的同时,却无形中增大了计算量。本文结合已有的并行计算技术,为了满足在尽可能短的时间内实现该算法对优化计算问题求解的需要,对该算法进行了改进,构造出了该方法的同步并行计算算法。仿真试验证明并行算法具有更快的收敛速度。

1同步并行算法的构造

根据指令流与数据流的执行方式,人们一般将并行计划分成单指令流多数据流(SIMD)机和多指令流多数据流(MIMD)机两大类,并行算法相应的也划分为同步并行算法和异步并行算法两大类。对大多数SIMD计算机而言,构造并行算法的原则是从串行算法开始,并将之转换成向量处理器上可执行的程序。图1显示了传统的数值方法及其并行化处理在并行计算过程中的位置[7]。图1中虚线框内所覆盖的内容就构成了采用这一原则研究并行算法所涉及的领域。向量处理器的处理就可以按并行方式处理。

SIMD结构主要包括一个控制单元和一组处理单元,以及多个存储器。它提取并解调指令,然后在控制单元内加以执行,或将指令传递给一系列由一个开关网络连接的相同处理单元,这些处理单元同步操作,SIMD类并行机的结构如图2所示。

2OPSO的同步并行算法

OPSO是依据人类社会活动在基本PSO中引入组织概念,粒子的位置更新既依赖自身的最优经验,又依赖组织的最优经验,组织内部依靠全局最优,组织词为局部最优方法。同时在组织优存劣汰的过程中,会有新的组织加入,从而保持粒子群的多样性,避免算法的早熟收敛。

本文的同步并行算法是通过若干个独立的处理器,对种群的每个组织进行独立的计算,以提高计算的速度。具体算法步骤如下(假定具有n个独立处理器):

(1) 确定组织中粒子规模m。

(2) 初始化n个处理器中的每个组织Sl(l=1,2,…,n),每个组织具有m个粒子$S{}^l=\left\{X{}_i^l|i=1,2,\cdots ,m\right\}$,并随机确定每个粒子初始位置为X${}_i^{l0}$=(x${}_{i1}^{l0}$,x${}_{i2}^{l0}$,…,x${}_{iD}^{l0}$),每个粒子初始速度为V${}_i^{l0}$=(v${}_{i1}^{l0}$,v${}_{i2}^{l0}$,…,v${}_{iD}^{l0}$),D为支撑基的维数。

(3) 评价每个组织中的粒子。计算粒子的适应度值,如果优于该粒子当前个体极值,则将pbest${}_i^l$设置为该粒子的位置,且更新个体极值;如果组织中所有粒子的个体极值中最优的优于组织当前的极值,则将gbestl设置为组织中个体极值中最优的位置,且更新组织极值。

(4) 若n个处理器中至少有一个组织极值更新,则组织极值最差的处理器中的m个粒子随机更新,否则转往(5)。

(5) 用下式对所有的处理器中的粒子的速度和位置进行更新。

(6) 检验是否符合结束条件,若符合则输出结果并结束;否则转往(3)。

3仿真试验

本文选取文献[6]中的4个基准函数来验证OPSPO的性能,如表1所示。分别取2维和10维对这4个基准函数进行PSO,OPSO,OPSPO试验。三种算法的群体数量均取20,c1=c2=2.05,w随迭代次数由0.7线性减少到0.4。表2分别是四个基准函数测试结果。从表2中可以看出:PSO很快陷入早熟收敛,OPSO收敛较慢,而OPSPO收敛速度有明显提高。

4结论

本文根据OPSO的特点,结合已有的并行技术,提出了OPSO的同步并行计算算法。OPSO算法通过组织的优存劣汰过程保持粒子群的多样性,避免算法的早熟收敛,但同时却增加了算法的运行时间。而新的OPSPO在避免早熟收敛问题的同时也提高了收敛速度,降低了运行时间。

摘要：提出带组织的粒子群优化同步并行算法。粒子群优化算法是一种基于群体智能的演化算法,具有良好的优化性能。但由于群体的迅速收敛和多样性低,导致算法早熟收敛。带组织的粒子群优化同步并行算法虽然克服了早熟收敛问题,但无形中却增加了计算时间。结合已有的并行计算技术,构造出了该方法的同步并行计算算法,仿真试验证明并行算法具有更快的收敛速度。

关键词：粒子群优化,演化算法,并行计算

参考文献

[1]Quinn M.Parallel Computing,Theroy and Practice.MaGrawHill,1994.

[2]王嘉谟,沈毅.并行计算方法.国防工业出版社,1987.

[3]胡峰,胡保生.并行计算技术与并行算法综述.电脑与信息技术,1999,5:47-58.

[4]Kennedy J,Eberhart R C.Particle swarm optimization.Proceedings ofIEEE International Conference on Neural Networks,Perth Australia,1995:1942-1948.

[5]Eberhart R C,Shi Y.Particle swarm optimization:Development,appli-cations and resources.Proceedings of the Congress on EvolutionaryComputation,2001:81-86.

[6]许永峰,张书玲.带组织的粒子群优化算法—OPSO.计算机应用与软件,2006.

[7]张宝琳.发展并行数值方法.数值计算与计算机应用,1988:3-4.

同步并行算法 篇2

关 键 词：MOS器件；模型参数；参数提取；器件模型

1 引言

器件的模型和模型参数提取是电子设计自动化（EDA）领域的关键工作[1]。采用遗传算法进行半导体器件模型参数提取是近年来兴起并被广泛使用的一种参数提取方法[2-3]。遗传算法全局搜索能力强、不需进行繁琐的求导运算，不依赖参数初始值等特点，理论上来说只要有足够的迭代次数种能找到最优解[4]。但是，由于遗传算法是一种搜索类算法,较之传统的基于梯度进行迭代计算的解析算法, 每进行一次迭代所需要的时间较长，计算量有了显著增加, 而且对许多复杂问题而言，例如采用的全局优化策略提取复杂模型的大量参数时，标准遗传算法的求解效果往往不是解决这个问题的最有效的方法，必须对算法进行修改与优化，这些因素无疑大大增加了遗传算法的计算量，为此必须考虑算法的耗时问题。本文针对遗传算法自身的耗时问题，讨论了并行遗传算法的特点，并以主从式遗传算法为例，证实了并行计算在参数提取工作中的可行性。

2 并行遗传算法

为了有效的解决遗传算法（GA）在模型参数提取过程中的耗时问题, 提高GA的运行速度，采用并行遗传算法（PGA）是提高搜索效率的方法之一。并行遗传算法[5-6]主要有主从式并行遗传算法、粗粒度并行遗传算法和细粒度并行遗传算法。

2.1 全局PGA模型－主从式模型（master-slave model）

如图1所示，主从式模型分为一个主处理器(master)和若干个从处理器(slaves)。主处理器监控整个染色体种群，并基于全局统计执行选择等全局操作；从处理器接收来自主处理器的个体进行适应度评估等局部操作，再把计算结果传给主处理器。

主从式模型的优点是简单，保留了串行GA 的搜索行为，对计算机体系结构没有严格要求，适合运行在共享存储和分布式存储的并行计算机上。如果适应度估值操作比其他遗传算子计算量大的多时，这是一种非常有效的并行化方法。

2.2 粗粒度PGA模型－分布式模型（distributed model）

该模型又称分布式、MIMD、岛屿模式遗传算法模型。在处理器个数较少的情况下，我们可以将群体分为若干个子群体，每个子群体包含一些个体，每个子群体分配一个处理器，让它们相互独立地并行执行进化。为了防止子群体早熟，每经过一定的间隔(即若干进化代)，各子群体间会交换部分个体以引入其他子群体的优秀基因，丰富各子群体的多样性。除了基本的遗传算子外，粗粒度模型引入了“迁移”算子，负责管理区域之间的个体交换。如图2所示，通常存在两种迁移实现:岛屿模型、踏脚石模型。

2.3 细粒度PGA模型－分散型 (fine-grained model)

细粒度模型又称为邻域模型(neighborhood model)或细胞模型(cellular model)模型。如果并行计算机系统的规模很大，理想情况下处理器多到可以与染色体一一对应，则我们可以将每个个体分配一个处理器，让它们相互独立地并行执行进化，这样就能获得并行遗传算法的最大可能的并发性。如图3所示，在细粒度模型中，通常处理器被连接成平面网格(grid)，每个处理器上仅分配一个个体，选择和交叉只在网格中相邻个体之间进行，所以网格上的邻域关系就限定了个体空间上的关系。由于对处理器数量的要求很高，所以细粒度模型的应用范围不广。

3 基于MPI的主从式遗传算法的的实现

3.1 总体构想

我们采用的主从式并行模型分为一个主处理器(master)和若干个从处理器(slaves)。主处理器监控整个染色体种群，并基于全局统计执行选择等全局操作；从处理器接收来自主处理器的个体进行适应度评估等局部操作，再把计算结果传给主处理器，其个体的分配过程是这样的：假设种群规模为N, 优化模型参数变量个数为M。适应度评估时，程序传给评价函数N个长度为M的向量。并行的任务是master处理器将这个N个长度为M的向量平均分配到各slaves处理器做适应度计算，计算结束后，评价函数返回N个适应度给master处理器。计算各处理器分得的染色体个数的方法是，首先计算出每个处理器至少分配到的染色体个数为AveNum=N/Size，如果处理器个数不能整除行数，这样将有部分处理器分得到（AveNum+1）个染色体，规定多余的染色体分配到编号小的处理器上。

3.2 并行中的消息传递机制

另外，需要注意的是，仅仅依靠例如C，C++，java等编程语言所编写的程序是无法实现上面叙述的染色体在各处理器之间的传递任务。因为，在并行计算环境中，每个进程均有自己独立的地址空间，一个进程不能直接访问其它进程中的数据，因而，在进行并行计算的任务之间进行的数据传输必须通过消息传递机制。消息传递机制，是指用户必须显式地通过发送和接收消息来实现处理器之间的数据交换。

本文采用的是MPI(Massage Passage Interface)消息传递接口。MPI是一个很好的数据传递软件平台，可以通过调用MPI库函数来进行进程调度以及任务间的通信。它实际上是一个消息传递函数库的标准说明，吸取了众多消息传递系统的优点，是目前国际上最流行的并行编程环境之一，其特点是通用性强(只要求网络支持TCP/IP网络协议)、系统规模小、技术比较成熟。本文通过调用MPI的库程序来达到程序员所要达到的并行目的，使异构的计算机群体作为一个紧凑、灵活、经济的计算机资源来使用的并行环境。

3.3 共享内存多处理器主从式并行环境搭建

全局并行化模型并不限定计算机体系结构，它可以在共享内存和分布式内存计算机中高效实现。现在简单介绍一下两种并行编程的方法：分布式内存方法和共享式内存方法。

对于分布式内存的并行计算机，各个处理器拥有自己独立的局部存储器，不存在公用的存储单元，显然，这种方法的问题就产生于分布式内存的组织。由于每个节点都只能访问自己的内存，如果其他节点需要访问这些内存中的数据，就必须对这些数据结构进行复制并通过网络进行传送，这会导致大量的网络负载。他的优点是拥有很好的扩展性，有利于快速构造超大型的计算系统。

在共享内存多处理器计算机中构成并行环境，在共享式内存方法中，内存对于所有的处理器来说都是通用的。这种方法并没有分布式内存方法中所提到的那些问题。而且对于这种系统进行编程要简单很多，因为所有的数据对于所有的处理器来说都是可以使用的，这与串行程序并没有太多区别。这些系统的一个大问题是扩展性差，不容易添加其他处理器。

为了在微机环境下使用MPI构成分布式内存并行环境，只要将PC机联接局域网，然后在每台PC机上安装相应操作系统，并安装MPI软件包即可。分布式内存即种群被一个处理器存储。这个主处理器负责将个体发送给其它从处理器进行评估，并收集计算结果，进行遗传操作来生成下一代。

对于本文所采用的在共享内存多处理器计算机中构成主从式并行环境就更为简单，只要在PC机上安装操作系统（本文安装linux操作系统）和MPI软件包就可以实现并行环境了。在共享内存多处理器计算机中，种群可以保存在共享内存中，每个处理器可以读取被分配到的个体信息并将适应度写回，不会有任何冲突。

4 实验结果分析

将以上方法实现的基于MPI的主从式遗传算法应用于1.2um SOI MOS器件的阈值电压模型参数提取工作中。如图4所示，实验结果表明曲线拟合的效果很好，转移特性曲线最大误差都低于5%。采用并行计算后，参数提取的速度提高了接近2.5倍。

5 结论

从实际的测试效果来看，以上方法实现的程序的简洁有效，智能化程度很高，且具有较高的精确度。因此，本文提出的基于MPI的主从式遗传算法可以解决遗传算法在器件参数提取过程中的耗时问题。该方法简单易用，适合推广使用。

参考文献

[1] J.Liou A,Analysis and Design of MOSFETS: Modeling,Simulation,and Parameter Extraction[M].KLUWER ACADEMIC PUBLISHERS,1998.

[2] Kondo M,Onodera H,Tamaru K.Model adaptable MOSFET parameter extraction method using an intermediate model[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1998,17(5):400-405.

[3] Yang P, Chatterjee P K, An optimal parameter extraction program for MOSFET models[J].IEEE Transaction on Electron Devices,1983,30(9):1214-1219.

[4] Li Yiming. An automatic parameter extraction technique for advanced CMOS device modeling using genetic algorithm.Microelectronic Engineering,2006,41(4): 1309-1321.

[5] 康立山，非数值并行算法(第一册)-并行遗传算法[M].科学出版社,2003.

对短波并行体制符号同步的灵巧干扰 篇3

同步是短波并行体制系统实现的重要环节, 攻击数据传输系统的同步系统, 对破坏数据传输而言, 在许多条件下会以小的代价, 取得更好的效果[1]。文献[2]指出针对同步系统的干扰就是实现灵巧干扰技术的一种方法。符号同步是短波并行体制系统实现的又一重要环节, 对并行体制同步的攻击, 已有文献[3,4] 研究对现在正在广泛应用于北约数据链link11和link16的同步过程攻击, 并取得了良好的干扰效果, 本文研究对短波并行高速数据传输系统的符号同步的灵巧干扰技术。

139音并行调制解调器的信号波形结构

1.139音并行数据传输系统前导结构

在传输数据之前, 将传输3个前导信息:

Preamble-1传送持续14个符号周期 (信号存在信息和多普勒估值信息) , 包含14个符号周期的等幅未调制的4音信号, 频率点分别为787.5 Hz、1 462.5 Hz、2 137.5 Hz和2 812.5 Hz, 信号存在信息用来检测信号是否到来, 接收端检测到此信号以确定信号出现, 多普勒频偏估值信号用来估计信号通过信道后所产生的频率偏差。

Preamble-2将传送持续8个符号周期 (用于符号同步建立信息) , 包含3个调制后的数据音, 频率点分别为1 125 Hz、1 800 Hz和2 475 Hz, 符号同步建立信息为接收端建立符号同步提供必要的信息;

第3部分为相位参考帧, 由一个符号周期组成;

最后为块同步及39音数据信息, 每个码元长度为Tsymb=22.5 ms, 如图1所示。

1.2Preamble-2符号同步算法

Preamble-2提供对符号同步捕获的前导信息, 在并行体制的HF MODEM中, 符号同步的含义就是指要确定22.5 ms帧的起始位置, 只有这个位置找到了, 才能确保FFT变换的样点取一帧内, 以保证判决信号抽样点在22.5 ms的中央。

发送端发送完用于信号存在检测和载波同步的信号之后, 在3个正交频率1 125 Hz、1 800 Hz、2 475 Hz上, 连续发送8帧2PSK信号用于符号同步的捕获。对Preamble-2符号同步捕获, 采用的方法是基于内积算法的符号定时同步。采用滑动DFT算法来计算频域内的内积值, 此方法是建立在最大后验概率 (MAP) 准则基础上的内积同步法。具体做法是在时域离散序列内连续开设了2个长为N的观测窗口, 求得其频谱上的频谱值, 通过滑动DFT可算出每滑动一点后对应的频域信号的频谱矢量, 得到其频谱线上前后窗口内的频域值分别为:

E=R0+jX0。 (1)

L=R1+jX1。 (2)

设该频谱线上的内积值为Z, 则

Z=DOT[ (R0+jX0) (R0+jX0) ]=R0R1+X0X1。 (3)

式中, DOT运算就是内积运算, 求得相邻两观测窗口在某频谱线上的内积值, 滑动窗口滑动N点, 必会有同步点出现。根据同步点两窗口的内积值有特殊的统计特性, 最后以两窗口的内积值的统计特性, 应用最大后验概率 (MAP) 准则判决同步帧。判决同步帧的方法是:若在一个滑动周期 (滑动DFT算法滑动N次) 中, 第i次变换对应的内积值DOT满足:

P (Syn/DOTi) =max[ (Syn/DOTj) ], 0≤j≤N-1。 (4)

式中, DOTi为第i次变换的内积值;P (Syn/DOTi) 为当内积值为DOTi时第i点为同点的概率。通过对同步点的捕获, 可以判第i点为同步点。内积同步法在并行体制系统中, 是根据并行体制信号发送的特点而提出的一种简单、可靠的符号同步方案。

2符号同步对系统性能的影响

Speth和Fechtel等人对符号同步的影响进行了研究[5]:在循环前缀内, 受延迟扩展和不受延迟扩展的2个区域, 若时间同步点在延迟扩展影响的区域内会产生ISI, 反之则不会受到影响。在受到延迟扩展影响的区域, 由于nθ的存在, 造成的影响是[6]:

$\begin{array}{l}z{}_{l,k}=\frac{{\rm N}-n{}_{\epsilon }}{{\rm N}}a{}_{l,k}\exp \left\{\frac{\text{j}2\text{π}kn{}_{\epsilon }}{{\rm N}}\right\}+{\rm I}C{\rm I}+{\rm I}S{\rm I}+n{}_{l,k}‚(5)\\ {\rm I}C{\rm I}=\frac{1}{{\rm N}{}_{FF{\rm T}}}{\displaystyle \sum _{n=0}^{{\rm N}{}_{FF{\rm T}}-1-n{}_{\epsilon }}{\displaystyle \sum _{i=-k/2;i\ne k}^{{\rm K}/2-1}a}}{}_{l,i}\exp \left\{\frac{\text{j}2\text{π}i(n+n{}_{\epsilon })}{{\rm N}{}_{FF{\rm T}}}\right\}\cdot \\ \exp \left\{\frac{-\text{j}2\text{π}nk}{{\rm N}{}_{FF{\rm T}}}\right\}‚(6)\\ {\rm I}S{\rm I}=\frac{1}{{\rm N}{}_{FF{\rm T}}}{\displaystyle \sum _{n={\rm N}{}_{FF{\rm T}}-n{}_{\epsilon }}^{{\rm N}{}_{FF{\rm T}}-1}{\displaystyle \sum _{i=-k/2}^{{\rm K}/2-1}a}}{}_{l+1,i}\exp \left\{\frac{\text{j}2\text{π}i(n-{\rm N}{}_{FF{\rm T}}+n{}_{\epsilon })}{{\rm N}{}_{FF{\rm T}}}\right\}\cdot \\ \exp \left\{\frac{-\text{j}2\text{π}nk}{{\rm N}{}_{FF{\rm T}}}\right\}。(7)\end{array}$

式中, l为第l个ofdm符号;k为OFDM符号所在的载波;zl, k为第l个符号第k个子载波的输出;al, k为发射端第l个符号第k个子载波的数据;nl, k为发射端第l个符号第k个子载波上的噪声。由于符号同步误差, 对系统产生的影响主要为ICI和ISI, ICI和ISI为近似为高斯噪声, 其方差为[6]:

$\begin{array}{l}\sigma {}_{\epsilon }^2={\displaystyle \sum _i\left|h{}_i(t)\right|}{}^2\left(2\frac{\text{Δ}\epsilon {}_i}{{\rm N}}-\left(\frac{\text{Δ}\epsilon {}_i}{{\rm N}}\right){}^2\right)‚(8)\\ \text{Δ}\epsilon {}_i=\{\begin{array}{cc}n{}_{\epsilon }-\frac{\tau {}_i}{{\rm T}{}_1},& n{}_{\epsilon }{\rm T}{}_1>\tau {}_i\\ \frac{\tau {}_i-{\rm T}{}_g}{{\rm T}{}_1}-n{}_{\epsilon },& 0<n{}_{\epsilon }{\rm T}{}_1<-({\rm T}{}_g-\tau {}_i)\\ 0,& else\end{array}。(9)\end{array}$

式中, Tg为循环前缀的时间长度;τi为第i条径的时延;T1=T/N, 表示接收端时间抽样间隔;hi为第i条径的信道抽头系数。时间同步误差必须非常准确, 因为时间同步常常对信道估计性能有影响, 而信道估计误差将会对系统带来严重的影响, 由于时间同步误差导致的信道估计误差的方差为[6]:

式中, εT1为时间偏移;W (τ) 为信道估计中窗函数, 可见时间偏差不仅造成相位旋转, 而且同时产生了ISI和ICI, 使解调段信噪比降低。假设前后码元是非相关的, 此时可以近似得到接收端信噪比损失为:

SNRloss=10log (1+ (2nθ/NFFT) ×SNR) 。 (11)

3对符号同步灵巧干扰策略

灵巧干扰的设计方案:首先灵巧干扰要借助于侦察手段, 对目标信号进行参数识别并准确获取目标信号的参数特征, 作为引导施放干扰的依据;然后在干扰引导技术的引导下, 提取不同的信号特征, 根据先验知识和自学习功能, 选择或设计干扰样式, 生成针对性很强的干扰信号;最后再通过干扰引导技术从时间域、空间域、频率域、样式域和过程域等多维空间形成最佳匹配的干扰信号。

对Preamble-2的符号同步捕获的灵巧干扰策略正是基于这种干扰设计方案, 首先对信号进行侦收, 对采集到的信号进行分析后, 干扰样式设计出一种相关性强的干扰信号, 最后由发射端发出干扰信号。

相关性强的干扰信号是利用干扰引导技术, 通过对通信信号的截获, 设计出参数与其相同或接近的相关干扰信号, 表达式为:

式中, Pjam为干扰信号的幅度;ajam (t) 为与信号参数相关的函数;fjam为与通信信号相同或这接近的干扰信号的载频;θjam为与信号相同或接近的干扰信号的相位。因为干扰信号与发送端的信号由很强的相关性, 使得接收端对接收到的符号同步头产生错误判决, 导致符号同步出错。干扰后对OFDM解调的影响, 直接给出加入干扰后接收信号的表达式。

接收端接收到的第q个子载波上的第n个OFDM符号的表达式为:

$R{}_{n,q}={\rm H}{}_{n,q}X{}_{n,q}\text{e}{}^{\text{j}2\text{π}qn{}_{\text{j}\text{a}\text{m}}/{\rm N}{}_{\text{F}\text{F}\text{Τ}}}\times \frac{{\rm N}{}_{\text{F}\text{F}\text{Τ}}-n{}_{\text{j}\text{a}\text{m}}}{{\rm N}{}_{\text{F}\text{F}\text{Τ}}}+J{}_{n,q}$。 (13)

式中, njam的定义为干扰信号对其产生的符号同步偏差。由式分析干扰对符号定时的影响有以下3点:

① 相位旋转2πqnjam/NFFT, 旋转随子载波索引q变化但不随n增加;

② 定时干扰使得同步点落在CP后, 接收端对信号作FFT变换之后, 将包含了下一个OFDM符号的采样, 由此将造成符号间干扰ISI和ICI;

③ 信号的幅度将衰减为$\frac{{\rm N}{}_{\text{F}\text{F}\text{Τ}}-n{}_{\text{j}\text{a}\text{m}}}{{\rm N}{}_{\text{F}\text{F}\text{Τ}}}$;由于人为的干扰信号的引入, 使得信号的有用信噪比降低, 如果收发双方要提高接受信噪比, 则发送端必须提高传输功率。

4对符号同步的灵巧干扰仿真

对符号同步灵巧干扰有了2种干扰效果:① 使得系统的误码率升高, 使得接收端理解信息难度加大, 达到不能理解的程度, 理论表明当误码率达到50%时, 接收方将不能理解其信息内容;② 使得信息传输滞后, 战场上时间就是生命的保障, 干扰同步系统, 将会导致信息的延误或者信息的滞后, 为我方赢得时间。

仿真采用Matlab软件, 在典型短波信道Watterson信道下仿真。采样速率为7 200, FFT点数为128, 单音间隔56.25 Hz, 符号同步音1 125 Hz、1 800 Hz、2 475 Hz, CP长度为34* (1/7 200) =4.732 ms, 调制方式采用DQPSK, 码元长度22.5 ms, 码元速率44.444。

依据式 (13) , 当符号同步错误时, 接收端对数据解调会产生相位旋转与幅度衰减, 对系统实施针对符号同步的灵巧干扰参数njam=54时, 其星座点的变化如图2所示。

图2为采用相干扰波形的灵巧方式干扰方式, 其接收端解调前后星座图的变化。从对比图中可以明显看出, 星座图相位旋转, 幅度衰减, 接收端已经不能很好地对接收到的信号进行正确的解调。

概率准则有时也被称为战术运用准则或效能准则, 是从被干扰对象在电子干扰条件下, 完成给定任务的概率出发来评估干扰效果。有些时候仅仅基于误码率准则, 并不能很好地评估干扰效果。

如当系统本身在复杂的环境下性能就很差, 使得误码率偏高, 这时若使用误码率准则, 就不一定说明干扰效果有效。因此在对符号同步干扰效果评估时, 使用概率准则, 以接收端捕获符号同步的错误概率来评定干扰效果就显得更加直观。对灵巧干扰与多种干扰方式对符号同步捕获概率的影响进行仿真, 如图3所示。

从图3中可见, 当采用相关波形进行干扰, 其频率完全对准符号同步音时, 灵巧干扰效果明显好于瞄准多音干扰、随机多音干扰、随机单音干扰、扫频干扰和噪声干扰, 当干扰功率JSR增大, 符号同步错误概率将增大。可见, 相关性强的灵巧干扰JSR在0 dB时, 对通信系统产生极大的影响, 其错误同步概率达到90%以上, 随机多音干扰等常规干扰, 对系统影响比较小, 都达不到压制通信的目的, 其中若要实现随机多音干扰, 全频段噪声干扰, 其总功率都将非常高, 且达不到更好的干扰效果。灵巧式的相关信号的干扰使得接收端对符号同步的估计产生错误, 而符号同步的错误导致接收端不能正确解调数据, 并且符号同步错误将造成通信双方的数据传递的延误。

5结束语

首先分析符号同步偏差对系统的影响, 而后剖析了39音并行数据传输系统中符号同步捕获算法。对符号同步头的干扰采用灵活的方式, 既可以实现对数据解调的影响, 又能影响通信的建立, 致使通信滞后。具体实施是利用Matlab软件搭建仿真环境, 采用滑动相关法实现了对符号同步的建立, 之后基于对符号同步的灵巧干扰思想, 在短波信道下对高速短波并行体制的符号同步实施灵巧干扰, 并与多种干扰方式进行比较分析。通过理论上的分析与仿真结果验证, 证明了灵巧干扰符号同步的实用性、可行性。

参考文献

[1]朱庆厚.通信同步的干扰 (Ⅱ) [J].航天电子对抗, 2005, 21 (6) :46-48.

[2]RICHARD AP.现代通信干扰原理与技术[M].陈鼎鼎, 译.北京:电子工业出版社, 2005.

[3]郭建蓬, 王可人, 蔡小霞.Link16数据链消息同步段有效干扰策略研究[J].电子对抗技术, 2005, 20 (1) :3-7.

[4]韩冬平, 王敏, 余国文.Link11数据链建模与多普勒校正的干扰效果分析[J].电子信息对抗技术, 2008, 23 (6) :41-46.

[5]SPETH M, CLASSEN R, MEYR H.Frame Synchronization of OFDMSystems in Frequency Selective Fading Channels[J].Vehicular Technology Conference, 1997 (3) :1807-1811.

同步并行算法 篇4

某电网营销管理信息系统(CSGII-MM V2.0,简称“新系统”)主要实现抄核收、用电检查、营销稽查监控、业扩、管理线损等功能的设计、建设过程管理,是实现电力营销全生命周期管理的一个重要环节,为保障新系统顺利实施上线,顺利完成由云南电网营销管理信息系统(PMS,简称“老系统”)到南方电网营销管理信息系统的顺利过渡,应做好数据迁移工作的切实保障,保证南方电网营销管理系统数据的真实、准确和完整。为了保证新系统上线后历史数据的可用性,需研究出行之有效的数据迁移方案,能够将老系统历史数据整理、转换、集中,使得业务操作能够获得历史数据的支撑,充分利用历史数据的价值。

1 系统迁移现状分析

为实现系统内历史数据的有效迁移,需对南方电网营销管理系统现状进行详细分析,分析内容包括迁移原则、业务现状与技术现状[1]。

1.1 迁移原则

数据清理收集工作,应当遵循如下原则进行:完整性原则、真实性原则、有效性原则、统一性原则、保密性原则。

1.2 业务现状

电网营销管理系统为全省大集中,系统数据覆盖省、地市、县级供电单位、国际公司和股份公司各供电单位,数据域包括客户域、电网域、服务域、核算域、帐务域、营销设备域、量测域、管控域、支撑域和其他类数据十大类。

2 数据迁移方案分析

2.1 数据迁移方案一

新老系统数据迁移方案一采用源数据库(老系统数据库)à数据迁移中间库à新系统数据库的方式开展数据的转换和迁移工作,在中间库开展转换、核查和整改工作。首先由老系统数据库采用ORACLE DBLINK技术迁移数据至中间库,在中间库进行数据转换及数据校验、整改工作,再由中间库迁移至新系统,最后进行核心数据功能验证,如图1所示。

2.2 数据迁移方案二

2.2.1 实时数据同步

取消方案一中的中间库数据迁移工作,采用数据同步技术,提前将老系统的数据同步至中间库,在老系统业务停机几小时后即可完成数据同步,开始进行数据转换,既降低方案一中的网络带宽花销,又减少了方案一中老系统至中间库的数据迁移时间。

数据同步需在老系统数据库与中间库上部署数据同步软件,该软件从老系统生产数据库中获取实时数据,与中间库建立连接,将实时数据同步发送至中间库[2]。

数据同步包含首次数据同步与增量数据同步,首次数据同步指数据同步软件将有迁移需求的数据以某时间点为截止全量迁移复制至目标数据库,增量数据同步指首次数据同步结束后到业务系统停止时将所产生的新增数据实时同步至目标数据库。增量数据同步的原理为实时分析源端数据库的日志,生成数据变动的压缩表,以捕获增量数据,数据经压缩和加密后传送至目标数据库,经过目标库数据同步软件的装载后,即实现了增量数据的同步。

2.2.2 分库并行数据转换

在采用实时数据同步的基础上,放弃使用原有中间库,新建4个中间库进行数据转换及校验工作,中间库既作为数据源也作为数据迁移中间库,可实现4个中间库并行的数据转换及迁移工作。在此过程中需要数据同步软件将老系统数据实时同步到4个中间库,正式数据迁移开始之后即可开展数据转换、校验、整改与迁移工作。按此方案,采用并行的数据迁移方式,可在不同的中间库分配不同的供电局业务数据,相较之前的单链路串行数据迁移方式,即需要按顺序依次进行各局数据迁移、转换的方式,此方案极大程度提高了数据迁移所需时间,方案二如图2所示。

2.3 对比结论

试点局上线进行数据迁移工作时采用数据迁移方案一,数据迁移时数据量约为1 T,耗时为4天。由于南方电网营销管理系统后续上线供电局较多,迁移数据量较大,约为2 T,采用方案一耗时较长。在数据迁移过程中,为保障新老系统数据的一致性及数据迁移的成功率,需要对老系统进行业务系统停机处理,若按方案一,需要对老系统停机7天或更久。停机时,无法进行客户算费收费工作,而电网公司业务上不允许长时间对业务系统停机。为保障电网公司利益不受损失,市场营销业务能正常快速开展,综合对比后正式数据迁移采用数据迁移方案二。

3 数据迁移改进方案实施应用

3.1 数据迁移方案实施

3.1.1 全量数据实时同步

通过对业务数据量及服务器性能分析后,4个分库的建设工作顺利完成。在正式数据迁移开始前,需完成全量数据实时同步工作。同步过程需要使用数据同步软件将数据从老系统同步至4个中间库,因此需要在老系统数据库服务器上及4个中间库上分别安装部署数据同步软件。此次同步为异构服务器且不同数据库之间的数据同步,源端(老系统)为AIX服务器,目标端(中间库)服务器为LINUX服务器;源端数据库版本为oracle10g,目标端版本为oracle11g。

由于分为4个中间库,首先需在源数据库和目标数据库创建4个同步队列,随后在源端数据库与4个目标端数据库创建同步用户,最后在源端导出数据库结构并在目标端进行导入。上述准备工作完成后即可开始同步数据,同步完成后进行同步数据比对工作,比对内容为源端与目标端核心数据表的记录数与内容。针对比对后遗漏或缺失的数据表,采取两种方式进行修复:对于数据量比较小的表,通过ORACLE DBLINK技术进行修复;对于数据量比较大的表,采用数据同步软件进行重新同步。

正式上线前一天,首次数据同步开始,通过数据同步软件将老系统数据库数据从AIX主机(老系统数据库)同步至4台LINUX主机(4个中间库)。首次数据同步完成后,开始增量数据同步。在老系统业务停止后,实时增量数据同步结束,开始进行数据比对与修复工作,约两小时后,数据比对修复工作完成,一致率100%,数据同步工作顺利完成。

3.1.2 并行数据转换与迁移

数据同步完成后,在4个中间库同时开展数据转换与迁移工作,根据“南方电网营销系统物理数据模型”为标准,开展新老系统数据转换与迁移工作,将老系统数据编码通过数据库脚本转换为新系统所支持的数据编码。为提升数据迁移脚本执行效率,在数据迁移脚本中适当加入索引能提高数据库的性能,建立索引之后,可以合理的使用资源;此时同样需要由良好的SQL语句进行支持[3],进行SQL语句优化之后,可进一步提升数据迁移时的效率。

在数据同步开始前,针对不同的分库分配了不同的业务数据,如不同的分库同步不同供电局的老系统历史数据,且每个分库的数据量基本一致,因此可以实现四库并行的同步数据转换与迁移工作,与之前方案相比,数据转换将近提升了4倍。

在正式数据迁移时,应设计南方电网营销管理系统的应用级灾备切换场景[4],当数据迁移过程中发生灾难且无法恢复时,致使营销服务中断,应快速切换回老系统,确保公司核心业务系统运行的连续性。

3.2 核心数据功能验证质量提升

迁移完成后,对南方电网营销管理系统数据库与《南方电网营销系统物理数据模型》进行完整性对比,保证数据的安全、完整、真实,如图3所示。

4 结束语

本文通过分析南方电网营销管理系统迁移现状,结合业务现状、技术现状等角度提出了两种数据迁移方案,进行了详细的分析与阐述,并重点描述了方案二的设计原理与实施应用。本文所提出的历史数据迁移改进方案已经应用于云南电网公司南方电网营销管理系统的实施上线工作中,并取得了工程实际的应用经验。该方案为大规模企业级管理信息系统的上线实施数据迁移工作提供了高效实用的技术支持,减少了不必要的损失,节省人力资源。

摘要：为保证南方电网营销管理系统集中部署上线后历史数据的可用性,需按照营销系统数据模型要求完成现有营销管理系统数据的清理、转换和迁移工作。文章提出了两种数据迁移方案,根据电网市场营销业务限制综合分析了第一种传统迁移方案的瓶颈与不足,采用了第二种实时同步、分库并行转换的数据迁移方案,并实践验证了该方案的有效性,大幅度缩短数据迁移时间。文章提出的方案对于大规模企业级管理信息系统的历史数据迁移工作起到一定的参考与借鉴作用,确保新系统按计划稳步高效推广应用。

关键词：营销管理系统,数据迁移,同步,并行

参考文献

[1]田黇.ERP系统集中部署模式下的历史数据迁移方案研究[J].电力信息与通信技术,2014,12(8):77-81.

[2]陈然.大规模电网运行数据实时同步技术研究[J].云南电力技术,2015,(5):24-26.

[3]罗伟,蒋苏湘,周沿东,魏鹏飞.湖南电力营销系统数据库性能优化研究[J].电力信息与通信技术,2014,12(4):30-34.

[4]郭晓艳,王扬,孙轶凡,侯丹,章斌.营销系统应用级灾备体系研究及建立[J].电力信息与通信技术,2014,12(10):13-17.

并行谱聚类算法 篇5

关键词：谱聚类,相似性矩阵,并行

0 引言

聚类分析作为机器学习领域最为重要的一个研究方向, 在近30年间得到了快速的发展。在解决了各个领域的难题的同时, 聚类算法也发展出不同的算法家族。谱聚类算法因为其优点成为聚类算法中发展较快的一种, 并得到了学者们的极大关注。

谱聚类算法是一种点对聚类算法。其将数据看作图中的顶点, 数据间的某种关系看作图中的边, 从而将原始的聚类学习问题转化为图划分的最优化问题, 并依据谱图理论构建相似性图的拉普拉斯矩阵, 将原始的划分问题松弛为计算数据拉普拉斯矩阵的前k大的特征值及其对应的特征向量的问题, 从而简化了聚类求解的过程, 优化了聚类的质量[1,2,3]。

谱聚类算法最大的问题在于计算复杂度过高, 尤其在计算相似性矩阵及求取拉普拉斯矩阵的特征值、特征向量时, 消耗的时间最多。采用抽样的方法可以降低计算的复杂度, 但是当数据是海量的时候, 这种方法依然面临着计算的瓶颈, 因此本文采用并行的方法将计算分配到网络的计算机上, 从而加速谱聚类算法的收敛[4]。

1 并行计算

并行计算是指通过运行在多个通过某种网络连接起来的计算、存储部件上的较小任务的合作求解规模较大的计算问题的一种计算方法。这是一种随着技术进步及性能要求而发展起来的一种用于解决大规模数据计算和存储的技术。并行计算可以大大降低问题求解的规模及求解时间, 并且容错性更高、可用性更好、吞吐率更高, 因此并行计算的概念从刚刚提出即成为研究的热点。

并行计算的基本思想是分而治之[5]。分而治之是计算机算法中最古老最实用的一种算法, 其基本想法是将类似的工作划分为不同的子任务, 每次完成单个子任务, 从而降低计算的复杂度。在并行计算的系统中, 同样利用了这种思想, 其可分为两个部分:

任务并行。根据问题的特性, 把问题分解为类似的子问题, 分配到不同的处理器或者其他计算资源上处理, 从而提高计算资源的利用率。

数据并行。根据数据的存储结构, 把海量的数据分散到不同的存储设备上存储, 形成多个独立的数据存储区域, 实现数据的并行处理。

1.1 并行计算系统

根据弗林分类法 (Flynn’s Taxonomy) , 计算机按照其指令和数据的执行访问方式可以分为4类:单指令单数据计算机 (single instruction single data, SISD) , 单指令多数据计算机 (single instruction multiple data, SIMD) , 多指令单数据计算机 (multiple instruction single data, MISD) 和多指令多数据计算机 (multiple instruction multiple data, MIMD) 。其中SISD为串行计算方式, MISD仅是为了分类的完整提出的一种架构, 在实际中并不存在, SIMD具有部分的并行能力, 主要用在向量机中, MIMD结构中每个计算单元均有独立的指令及数据, 现行的并行计算系统均可归为此类。

在实际的应用中, MIMD结构按照系统内存的结构又可以分为两大类:共享内存和消息驱动[6]。共享内存方式对于内存空间进行统一的编址, 所有的计算单元均可以访问相同的内存, 不同的计算单元通过读写内存共享数据处理结果, 这种结构的通信机制简单, 但是不同的计算单元访问共享内存时需要加锁, 因此可能降低系统处理数据的速率。消息驱动的方式各个计算单元独享内存空间, 不同的计算单元通过某种网络结构连接, 通过发送消息的方式实现计算结果的共享, 这种结构对于内存的压力远远小于共享内存结构, 并且易于动态的改变整个网络的结构, 具有很好可扩展性, 但是整个系统的效率严重依赖于网络的通信能力, 并且系统的负载均衡及结构的设计均需要开发者完成, 导致设计这种结构的并行系统较困难。当前比较流行的共享内存式的并行计算系统有共享存储对称式多处理机系统 (Symmetrical Multi-Processing System, SMP) 、分布共享存储多处理机系统 (Distributed Shared Memory Multi-Processing System, DSM) , 消息驱动的并行计算系统有大规模并行计算机系统 (Massive Parallel Processing System, MPP) 、集群系统 (cluster system) , 下面对其特点一一分析。

SMP。在SMP结构中, 所有的计算单元共享相同的内存地址空间, 所有的计算单元可以直接访问内存的任意地址, 并且对于任意的计算单元, 其访问延迟、访存带宽均是相同的, 因此这种结构又被称为统一内存访问 (uniform memory access, UMA) 。SMP系统的特点是系统中的计算单元的总线结构是相同的, 并且地址空间编码一致, 不同计算单元间通信仅通过读写内存即可以完成, 因此SMP系统的通信延迟很小, 访存带宽较高, 同时SMP系统往往仅运行一个操作系统的实例, 因此易于根据不同计算单元的繁忙程度实现系统的负载均衡。公用访存总线和内存空间虽然带来了通信开销较低的好处, 但是这种方式的可用性较差, 易于导致内存访问的竞争, 并且一旦存储器或者访存总线出现问题, 将导致整个系统无法使用, 并且当扩展系统规模时, 难以设计交叉开关, 因此导致系统的可扩展性较弱, 一般情况下SMP系统中计算单元的数目不超过64个, 这也决定了SMP系统仅适用于计算规模较小的环境。在实际中, SMP系统常见于小规模并行计算机中, 如IBM50, 曙光一号。

DSM。DSM结构中内存在物理上属于不同的计算单元, 但是在逻辑上共享相同的地址编码空间。在这种结构中计算单元对于不同的内存空间的访问速度是不同的, 计算单元通过本地总线访问本地内存, 通过系统总线访问其他地址空间上的内存, 因此导致访存的速度不同, 所以这种结构也被称为非一致内存访问 (non-uniform memory access, NUMA) 。DSM结构屏蔽了系统中计算单元同非本地内存间通过网络的物理结构, 提供统一的编程模式, 大大降低了DSM系统开发的难度。同时系统可以通过网络接入更多的计算单元, 具有较高的可扩展性。DSM系统兼具共享存储结构和消息驱动结构的优点, 因此具有极高的使用价值。

DSM系统通过系统总线访问非本地内存, 其速度严重依赖于共享总线的带宽, 这也导致不同位置内存访问速度的不同, 一种可行的解决办法是加入一致性高速缓存 (cache-coherent) , 采用基于目录的方法维护缓存的一致性, 这是一种常用的DSM结构。

MPP。MPP结构往往包括成百上千的计算单元, 每个计算单元均有自己独立的总线及内存空间, 不同的计算单元间通过专用的网络连接, 计算单元间通过消息共享计算结果和数据。MPP结构的系统具有很强的计算能力和存储能力, 并且可扩展性很高, 容错性能很强, 某个计算单元发生故障不会导致整个系统失效。但是MPP系统采用专用的网络连接, 需要提供专用的通信部件才能实现较高的通信效能, 导致这种系统的研发、维护和使用的开销极高, 因此MPP结构的并行计算系统往往为国家主持开发和使用的。比较著名的MPP系统有IBM SP2和曙光1000。

集群系统。集群系统中每一个计算单元均是一个独立的计算机, 每个计算单元均有独立的CPU、内存和总线系统, 不同的计算单元通过互联网连接, 每一个计算单元均可以独立工作, 也可以协同完成比较复杂的工作。集群系统的结构灵活, 可扩展性极强, 易于更换或者增加节点, 并且集群系统中每一个节点均是独立的计算机, 因此单个节点的失效不会导致整个系统的失效, 具有极高的鲁棒性和恢复能力。相比于MMP系统采用专用通信网络和专用计算机, 集群系统采用互联网通信和普通的计算机, 因此其具有很高的性价比。

集群系统最大的瓶颈为通信开销过高, 并且系统效率严重依赖网络的吞吐率, 如何设计高效低价的通信系统是所有集群系统必须考虑的问题。其次集群系统需要合理的调度计算资源, 因此严重依赖于负载均衡算法的调度。

1.2 并行计算编程模型

上小节中介绍的是并行计算不可或缺的底层的硬件平台, 本节分析当前比较流行的并行计算编程模型。

当前最重要的并行编程模型共有两种, 其一为消息传递, 其二为数据并行。数据并行编程模型编程较为简单, 这种编程模型提供了一种全局的地址空间, 通过指定并行操作的对象即可以实现并行化的编程, 但是这种模型仅仅适用于特定的并行计算系统, 因而应用的范围并不广泛, 常用的有Open MP (Open Multi-Processing) 。消息传递并行编程模型编程较为复杂, 需要开发者控制不同进程间的消息的传递、协调进程的执行, 但是可用于的并行系统极多, 不仅仅可以用于消息传递的并行系统, 也可以用于共享内存的并行系统, 因此得到了更多的关注, 常用的消息传递编程模型有MPI (Message Passing Interface) 、MAP/REDUCE等[6]。下面对这些编程模型进行详细的讨论。

Open MP。Open MP是用于共享内存并行计算系统的一种并行计算编程模型, 它支持在多处理机上编写并行程序, 利用共享内存结构的共享内存空间地址的特性, 高效的实现了程序的并行化。Open MP编程模型包括三部分:运行库 (runtime library) 、环境变量 (environment variable) 和编译器指令 (compiler directive) 。Open MP通过环境变量及编译器指令指示编译器如何并行化程序, 并提供了运行库支撑并行系统的运行。

Open MP编程模型简化了并行编程的难度, 开发人员仅需很小的学习曲线即可以掌握高质量的并行算法设计方法, 并且Open MP的库函数对开发人员屏蔽了底层的并行粒度、负载均衡等并行系统需要解决的难题, 因此可以使得开发人员将精力投入到算法设计本身, 降低开发的代价。同时Open MP作为一种开放的并行计算模型得到主流的计算机硬件软件厂商的支持, 因此采用Open MP的并行程序具有极好的可移植性。但是Open MP编程模型仅仅支持共享内存结构的并行计算系统, 这限制了它的使用范围。

MPI。MPI是一种基于消息传递的并行化编程模型, 是用于非共享式内存并行计算系统的编程接口的标准定义。MPI以较低级的消息传递的方式同步不同计算单元的计算结果, 协调计算单元的负载, 编程形制较Open PM灵活, 并且MPI在当前流行的PC系统中都有相应的实现, 因此具有很好的可移植性和广泛的适用性。此外MPI提供了语言无关的编程接口, 通过函数库的方式实现相应的功能, 因此不需要编译器的直接支持, 这使得MPI程序具有很好的跨平台的特点, 简化了开发人员的学习过程, 因此MPI并行编程模型成为当前最为流行的并行编程模型之一。

虽然MPI编程模型具有非常广泛的适应性, 但是其仍然存在不少的问题。MPI需要开发人员自行解决通信和资源调度的问题, 增大了开发的难度, 并且对MPI程序的调试比较困难, 当系统中某个进程失败时, 将导致系统的崩溃, 鲁棒性不如Open MP模型。

MAP/REDUCE。MAP/REDUCE并行编程模型是谷歌公司最早提出的, 用于解决海量数据环境中大规模计算的问题。MAP/REDUCE编程模型将计算过程分解为了MAP和REDUCE两个阶段[7], MAP阶段根据数据键值归类成不同的分组数据, 经过调度和洗牌后, 不同的分组交由不同的REDUCE程序进行处理, 并通过合并得到最终的结果。MAP/REDUCE并行编程模型将负载均衡、联网通信等复杂的底层实现隐藏在系统的内部, 对外部提供了统一的编程接口, 开发人员只需要实现Map函数和Reduce函数即可完成并行计算的任务。

MAP/REDUCE并行编程模型适用于内部松耦合的任务, 对于这种任务可以高度的并行化, 现在已经实现的云计算平台多采用这种编程模型, 并且模型对于异构的集群系统具有很好的适用性, 部署的代价极低, 因此MAP/REDUCE并行编程模型成为当前最为流行的并行编程方式。但是MAP/REDUCE并行编程模型对于紧耦合的任务无法很好的处理, 计算过程相当繁琐, 并且由于计算过程中需要对中间结果进行归并分组, 因此系统对于通信网络的依赖极重, 其通信效率严重影响系统的性能。图5.3展示了MAP/REDUCE的一般流程。

2 并行谱聚类算法

本节讨论如何利用MAP/REDUCE框架在集群上实现并行化的谱聚类算法, 并通过在图片数据集上的实验验证算法的有效性。

整个计算过程在Hadoop环境下实现, Hadoop是MAP/REDUCE框架的一个开源的java语言实现。

Hadoop框架将计算同数据分离, 底层为分布式文件系统Hadoop Distributed File System (HDFS) , 它负责存储系统中所有的数据, 上层为MAP/REDUCE计算引擎, 负责计算任务的执行。HDFS系统及计算引擎均采用主从结构, 在HDFS系统中主节点被称为Name Node, 负责决定文件块由那些节点存储以及跟踪整个系统中文件存储的整体情况, Data Node节点负责系统中真正的文件的读写以及存储工作。计算引擎通过Job Tracker进程分配计算任务给集群中的节点, 而Task Tracker负责节点中计算任务的执行。Hadoop框架的典型架构如图4所示:

谱聚类算法可以分为三个阶段:预处理阶段, 特征分解阶段和聚类阶段。预处理阶段主要实现计算相似性矩阵和拉普拉斯矩阵, 特征分解阶段主要实现特征值及特征向量的计算并拣选前k小的特征值对应的特征向量作为最终降维后的数据集表征, 聚类阶段利用k-means算法实现最终的聚类。因此, 并行算法的设计可以从这三个阶段着手。

预处理阶段。当数据量规模较大时, 单个计算机的内存很难将所有内容装入内存, 因此可以利用MAP/REDUCE框架将计算分布到不同的机器上去。假定集群中机器的数量为m, 首先将整个数据集平均的分配到m台机器上, 每台机器计算N/un个数据的相似性关系, 并计算相应的度矩阵及最终的拉普拉斯矩阵。基本思想如图5所示:

在每台机器上均有一份完整的数据备份, 这可以减少计算时网络中数据的交换流量。每台机器中完整的数据文件并没有完全装入内存, 而是分片读入的, 这样可以减少计算所需要的内存空间。

计算相似性矩阵的过程实际上分解为两个阶段:第一个阶段为计算相似性值阶段, 第二个阶段为对称化相似性矩阵阶段。

首先进行的是第一个阶段。由于文件中的每行数据表示一个数据点, 因此按照MAP/REDUCE的思想, 首先MAP阶段根据数据行在文件中的偏移将数据读入内存中, 然后根据数据所处行号的不同映射到不同的机器上。在REDUCE阶段, 对每行数据分别计算其同其他数据间的欧氏距离, 并按照其大小关系选择最小的k个保留下来, 这一步为了减少内存空间的使用, 可以仅仅预留前k小的数据的一个有序序列及其所对应的下标, 然后对这前k小的数据计算其相似性, 并在写入文件时将同其他数据间相似性值置为0, 并写入文件中, 写入文件的格式为 (相似矩阵行号, 列号, 值) , 同时为了将其对称化, 每个非零行交换行号、列号后写入两次, 这个阶段完成了基本相似性矩阵的计算, 但是这样得到的相似性矩阵并非对称的, 因此在第二阶段将相似性矩阵对称化。

第二阶段以计算相似性矩阵第一段的输出作为输入, 在MAP阶段以输入文件中的相似性矩阵的行号及列号域作为key值, 相似性值作为值域进行映射, 在REDUCE阶段key域同MAP阶段, 值域为MAP阶段值域的均值, 然后写入文件, 写入文件的格式为 (相似矩阵行号, 列号, 值) , 在完成这两个阶段后得到相似性矩阵即是一个对称的稀疏相似性矩阵, 最终的输出存在不同的节点上。

特征分解阶段。由于预处理阶段得到拉普拉斯矩阵为稀疏对称半正定阵, 因此可以利用Lanczos方法计算特征值及特征向量。Lanczos方法是一种迭代的算法, 首先通过Lanczos迭代计算出一个对称的三对角矩阵T=CTLC, 其中C为迭代过程中得到转移矩阵, L为拉普拉斯矩阵。通过QR方法求解T的特征向量ui, 那么L矩阵的特征向量vi可以通过下式得到:

由于T矩阵的规模远远小于L的规模, 因此整个求解过程计算量最大的是Lanczos迭代过程, 并行化的重点也在这一阶段。

Lanczos迭代过程如算法1所示:

算法1 Lanczos迭代过程

在预处理阶段得到的拉普拉斯矩阵是分布存储在集群上不同的节点, 因此只需要将初始化步骤中得到C0、C1按照预处理阶段数据的分布方案分配到节点去, 然后在每个节点上计算Step 2中的步骤a和b, 最后将各个节点上对部分的aj值的计算加起来, 即可以得到aj, 按照相同的原理计算βj+1, 并在主节点生成CT, 这样即可以完成迭代过程的并行化, 在得到T矩阵后, 然后利用QR分解得到T的特征矩阵, 并将其分配到不同的节点计算L矩阵的特征向量, 并存储在各自的节点上。

聚类阶段。此处采用与计算相似性矩阵时相同的策略, 首先将特征分解阶段得到的前k小的特征值对应的特征向量通过网络传播到每个节点, 然后分割计算任务到各个节点, 每次迭代产生新的聚类中心通过Job Tracker传播到整个网络, 并参与下一轮的计算直到计算过程收敛。

下面分析并行算法的计算复杂度。计算相似性矩阵的第一个阶段的计算复杂度为O (n2) , 其中n为数据点的个数, 对称化阶段的计算复杂度同样为O (n2) , 因此整个阶段的计算复杂度为O (n2) , 整个计算非配到m台机器上去, 因此该阶段的计算复杂度为

采用Lanczos方法计算特征向量所需的时间复杂度为O (k·n2) , 但是由于相似性矩阵及转移向量均是分布在不同的机器上, 因此最终的计算复杂度为:

k-means聚类阶段同样是分布在不同机器上进行的, 因此其计算复杂度为:

因此整个算法的计算复杂度为:

3 实验

实验环境为hadoop集群, 集群中共有三台机器, 每台机器的内存为512MB, CPU为1GHZ、单核, 集群中有一台机器作为中心节点, 并且其本身也参与计算与数据的存储。

实验数据集为来自Corel图像数据集中的5000幅图像, 这些图像共分为35类。每幅图像的色度表示分成了12个格, 并在其上分别计算其颜色直方图、均值、方差等9种颜色特征, 得到一个108维颜色特征向量, 此外将图像纹理通过DWT滤波得到9种子图组合, 并计算每种组合的均值、方差等特征, 得到一个36维的纹理特征向量, 并将二者组合起来表示一幅图像, 因此每幅图像采用一个144维的特征向量表示。

下面为并行谱聚类算法加速的对比:

(单位:秒)

上表的计算结果为3次实验的平均值, 近邻数设置为10, 高斯函数的调节参数设置为5, 类别数设置为35, 特征分解阶段Lanczos生成的转移矩阵的秩同聚类数, k-means聚类阶段迭代次数最大设置为1000。

从表中可以看出, 当增加集群中机器的数目时, 程序整体运行的时间将会减少。但是由于存在网络通信以及Hadoop系统本身会带来一些时间开销, 因此算法计算复杂度的减少并不像理想情况下为线性减少的。同时由于在构建相似性矩阵的阶段job划分较小, 导致Hadoop系统开销过大, 因此使得其加速的效果并不是那么理想。

图6展示采用一台slave与两台slave消耗的时间对比及加速比。图中左侧子图为程序消耗的时间, 左侧图中第一组数据位slave为1台时的结果;右侧子图为加速比, 依次为相似矩阵构建、特征分解、kmeas和总时间的加速比, 加速比的计算方式为:

从图6中可以看出采用更多的机器时可以很好的提高算法的计算速度。

4 结论

本章首先介绍了并行计算的硬件环境以及常用的并行计算模型, 然后在MAP/REDUCE环境下实现了谱聚类算法的并行化, 验证了并行环境对于解决大规模数据处理的有效性和可行性。

在Hadoop环境中构建相似矩阵的过程较为耗时, 因此希望在未来的研究中找到一种较好的映射方法, 改善算法的效率, 提高算法的性能。

参考文献

[1]Donath, Hoffman.Lower bounds for the partitioning of graphs[J].Res Develop, 1973, 17:420-425.

[2]M.Fiedler.Algebraic connectivity of graphs[J].Czechoslovak Math, 1973, 98 (23) :298-305.

[3]Wu, Leahy.An optimal graph theoretic approach to data clustering:theory and its application to image segmentation[J].IEEE Trans on PAMI, 1993, 15 (11) :1101—1113.

[4]Luxburg.A tutorial on spectral clustering[J].Statistics and Computing, 2007, 17 (4) :395-416.

[5]孙世新, 卢光耀, 张艳.并行算法及其应用[M].北京:机械工业出版社, 2005:5-10.

[6]李建江, 薛巍, 张武生, 张卫华.并行计算机及编程基础[M].北京:清华大学出版社, 2011:6-9.

同步并行算法 篇6

随着媒体技术的发展,对音频数据的采集和处理日趋成熟,尤其在消费领域,各种产品层出不穷;然而在信号分选和处理方面,对音频数据采集提出了新的要求。比如盲源分离,他要求多路实时并行同步地采集数据。为满足这些方面的算法应用对音频数据采集的要求,本文对多路并行音频数据采集进行研究。对音频信号盲源分离可实现对强噪声背景,复杂信号环境下的特定信号目标的分选和识别;音频信号盲源分离是在不知道信源数目和混合局,利用多传感器采集的混合数据,需要并行的采集多路音频信号,且要求各路之间有严格的时间相关性,实现办法是各路严格地在同一时刻采样,且各通道在设计和性能上保持一致性。

本文针对盲源分离对音频数据采集的要求,采用模数转换芯片 AD7656及PCI接口芯片S5933设计并实现了一种12路的PCI并行音频数据采集系统。

2 AD7656功能结构与特性

2.1 结构与特性

AD7656是基于iCMOS(industrial CMOS)工艺的一款多通道高分辨率模数转换芯片。iCMOS是美国模拟器件公司(ADI)发布的一种创新的半导体制造工艺,他是将高电压半导体工艺与亚微米CMOS和互补双极型工艺相结合的新技术。与采用传统CMOS制造工艺不同,采用iCMOS 制造工艺的模拟IC 能承受高达30 V电源电压,同时能提供突破的性能水平,降低系统设计成本,而且降低85%的功耗和减小30%的封装尺寸[1,2]。图1给出AD7656 的功能框图。AD7656的主要特性如下:

(1) 6 通道16 b逐次逼近型ADC;

(2) 最大吞吐率为250 kS/s;

(3) 低功耗: 在供电电压为5 V、采样速率为250 kS/s时的功耗仅为160 mW;

(4) 宽带宽输入,高信噪比:输入频率为50 kHz 时的信噪比( SNR) 为85 dB;

(5) 片上2.5 V 基准电压源和基准缓冲器;

(6) 有并行和串行接口;

(7) 与SPI/QSPI/μWire/DSP 兼容的高速串行接口,串行接口可进行菊花链式连接;

(8) 可通过引脚或软件方式配置;

(9) 采用iCMOS工艺技术;

(10) 64 引脚LQFP封装。

AD7656的6个通道是独立的,每个通道包含1个采样保持电路和1个16位SAR模数转换器,由CONVST A、B、C三个启动信号控制3对通道同时采样和转换,将3个信号连接在一起,便可实现6路的同时采样和转换。

2.2 引脚与功能

AD7656 是逐次逼近型转换器,包括1个逻辑控制单元和每通道1个比较器、1个模/数转换器、1个逐次逼近寄存器( SAR) 和1个输出缓冲寄存器。转换中的逐次逼近是按对分原理由控制逻辑电路完成的[3]。部分引脚功能[4]描述如下:

AGND,AVcc,VDD,VSS是模拟地和电源;其中AVcc只给ADC内核供电;

DGND,DVCC,DRIVE是数字地和电源,他是数字电路的参考点;所有电源引脚应该接1个10 μF和1个0.1 μF的去藕电容到相应的地;

V1~V6是信号的输入端,其输入范围是由RANGE决定的;

REFIN/REFOUT 是参考电压的输入输出引脚;

REFCAPA,REFCAPB,REFCAPC是3对ADC的参考电压缓冲去偶引脚, 这几个引脚应该分别接10 μF和0.1 μF的去偶电容;

CONVST A/B/C 是转换启动信号输入,每对有其相关的CONVST信号,当他由低电平向高电平跳变时,相应的一对采样保持器由跟踪进入保持模式,同时开始转换。当然, CONVST输入信号也可以使成对的ADC进入低功耗状态;

STBY,待机模式控制,当他为低电平时,6路ADC同时进入待机模式;

BUSY 是忙信号输出。高电平指示转换正在进行;

RESET 是复位信号输入。上电时,需有一个大于100 ns的高电平复位信号;

CS,RD分别是片选信号和读信号,均为低电平使能;

$\text{S}\text{E}\text{R}/\overline{\text{Ρ}\text{A}\text{R}}$是串行/并行选择输入信号。低电平时选择并行接口模式;

$\overline{\text{Η}}/\text{S}$是硬件/软件选择输入引脚。低电平时,AD7656工作在硬件模式;

$\overline{\text{W}}/\text{B}$是字或字节模式选择。低电平时,结果以字由DB0~DB15输出;

DB0~DB15 并行字输出时的数据输出引脚。

复位时,CONVST需保持高电平,所有寄存器清0,硬件模式下根据各引脚的逻辑电平对AD7656进行配置,复位后,AD7656等待CONVST的一个上升沿启动第一次转换,BUSY是转换正在进行的标志,BUSY脉冲结束,标志转换已经结束,转换的结果保存在6个输出寄存器中,这时,结果可以读出,在并口字读出模式下,读时序如图2所示:

新的转换在CONVST一个大于25 ns的低电平后的上升沿启动,但在结果读出前,不能启动新的转换。

3 并行同步多路采集的系统构成与电路设计

3.1 采集系统构成

根据声信号的盲源分离对传感器的要求,考虑采用2片AD7656实现12路并行数据采集,接口部分采用其高速并行16位口分别与32位PCI总线高低16位相连,然后用软件的方法对12路信号进行分离。同步和时序采用CPLD实现。具体方案图如图3所示。

2块AD的所有控制信号共用,配置也完全一样,在一个CONVST信号控制下同步转换,结果通过循环读送入FIFO,S5933通过FIFO直接DMA通道将数据送入内存,整个流程由CPLD控制逻辑实现同步与协调;通过接受来自PCI总线的命令和修改CPLD程序,可以很好地扩展和修改系统的功能,适应不同的应用需要。

系统设计的重点在AD7656前端和周围电路,这也是实现应用的关键;难点在PCI接口和驱动的实现及整个系统的协调控制上,以下对此分别论述。

3.2 AD7656周围电路的设计

如图4所示,AD7656的外围电路比较简单,除开对电源引脚的去偶,就是控制信号的配置连接。两块AD7656的配置是一样的,相同的信号连接在一起,以保证同时采集和各通道性能的一致性。其中,6个CONVST连接在一起共用为1个CONVST信号,与复位信号RESET,读信号$\overline{\text{R}\text{D}}$,片选$\overline{\text{C}\text{S}}$,待机信号$\overline{\text{S}\text{Τ}\text{B}\text{Y}}$,及忙信号BUSY一起输入到CPLD,由CPLD提供时序控制。其余信号根据需要配置成相应的高低电平。

在A/D的前端,还需要滤波和对信号电平的进行调整[5]。滤波要根据输入信号的范围设计滤波电路,这里直接利用运放设计了有源滤波电路,截止频率设定在30.3 kHz,有源滤波电路如图5所示。截止频率由公式fc=1/RC设定。

信号电平的调整要根据输入信号的范围及A/D可接受的电平范围来调整放大的倍数,整个的前端必须要考虑去噪的效果,同时防止引入其他的噪声。具体的措施有:良好的接地,大面积的铺地;保持各路在设计上的一致性,保证隔离以防止互扰。对电源引脚要去藕和滤波。

值得注意的是:在绘制PCB 版图时[3],要注意将AD7656 的模拟和数字部分分开布局,并把他们放在板上的特定区域,这样可以使地层比较容易分开,使用起来比较方便。数字地层和模拟地层应该在板上的适当的地方连接到一起,可以用0 Ω电阻器,也可以使用磁珠或直接用焊锡直接连接。建议在布线的时候不要将数据线布在该器件的正下方,因为这样做会使信号和噪声混在一起。电源线应该尽量粗一些,这样可以减小电源线的脉冲干扰。去偶电容器应尽量地靠近器件,之间的连线要尽量短以减小感抗。

3.3 时序控制和数据接口的实现

数字接口部分要实现的功能包括A/D的复位、采样转换的启动和转换结果的读出;A/D与FIFO,FIFO与S5933内部FIFO及S5933与驱动程序的协调与同步。

3.3.1 A/D的时序和控制

时序控制都由CPLD产生,对AD7656而言,相关信号是图4中连接到CPLD的几个信号。首先,AD7656上电时需要复位,每次转换需要一个启动信号启动;其次,转换完成后,要在下一次转换开始前,把存于6个寄存器当中的结果读出来。根据这些要求,主要的控制时序有:

复位及转换启动信号的产生

RESET信号由一个5位2进制计数器产生,上电时,计数器对33 MHz的PCI时钟计数,产生一个600 ns的复位脉冲后;计数器清零;重新上电或收到计算机复位指令,再计数产生一个复位脉冲。部分程序如下:

case count is

when "00000" => ad_rst <=′0′;fifo_oe <=′0′;

when "00001" => rd_pfifo <=′1′;fifo_oe <=′1′;

when "00010" => rd_pfifo <=′0′;ad_rst<=′1′;

when "01000" => divider <=DB; --set frequency dividing ratio

when "11100" => ad_rst<=′1′; rd_pfifo<=′1′;

when "11101" => fifo_oe <=′0′;

when "11111" => reset<=′1′;

when others => null;

end case;

转换启动信号CONVST直接对时钟进行分频得到,分频系数divider根据需要由计算机在复位时设定。

转换结果的读出:

在转换结束和下一次转换开始前,要产生6个读信号将结果读出并送到FIFO中去。6个读脉冲也是由计数产生。仿真时序图(见图2)如下:

其中,ad_rd是低电平使能的,而fifo_wclk是上升沿有效。

本文所述数据采集卡数据量比较大,特别是12路的数据要一起送入内存,不得不混杂在一起传输,同步问题就显得尤为重要,否则,在分离数据时就极易发生路与路之间的混叠。为解决同步问题,系统只使用了BPCLK一个时钟,同时,利用EPM7128S的5 ns的延迟,解决A/D与外部FIFO,外部FIFO与S5933内部FIFO之间的读写同步;保证每一个数据都不丢失,每一个数据都不重复读,不插入任何一个无用数据。

3.3.2 数据接口的实现

S5933有PCI总线接口、ADD-ON总线接口和外部只读存储器(NV-RAM)接口3种总线接口[6]。其中NV-RAM接口连接外部E2PROM,用于在系统上电初始化时对S5933内部寄存器进行配置,PCI配置空间可以通过串行或并行E2PROM配置。数据传输则在PCI接口与ADD-ON接口之间进行。PCI接口直接连接至PCI总线,替用户管理PCI总线;ADD-ON接口则面向扩展逻辑,他也是用户最为需要关注的地方。S5933为用户提供MAILBOX方式、FIFO方式和PASS-THRU方式3种数据传输方式。MAILBOX可用来在ADD-ON和PCI总线之间传输命令和控制信息。PASS-THRU为直通通道,S5933芯片和板卡上的本地逻辑通过引脚信号BPCLK,PTATN#,PTWR,PTADR#,PTRDY#的握手来完成PASS-THRU传输。本文采用FIFO方式实现数据DMA传输。

S5933内部有输出FIFO和输入FIFO两个单向的FIFO。每个FIFO的深度是8位,宽度是32位。S5933可通过他的FIFO接口在PCI总线上进行DMA(总线主控)传输。两个FIFO是独立单向的。一个用来将PCI总线上的数据传输到ADD-ON总线,另一个则将ADD-ON上的数据传输到PCI总线。主机和用户CPU可以通过访问控制寄存器的方式来访问FIFO。用户还可以通过WRFIFO#,RDFIFO#,WFULL,RDEMPTY,BPCLK这几个引脚来直接读写FIFO。直接读写FIFO有2种工作方式:同步方式和异步方式。在同步方式下,WRFIFO#,RDFIFO#为FIFO读写使能信号,在BPCLK的上升沿写入和读出数据,输出引脚BPCLK输出33 MHz信号。在异步方式下,WRFIFO#和RDFIFO#为FIFO的写信号和读信号。WRFULL为输出FIFO满信号,RDEMPTY为输入FIFO空信号。在设置时,RDEMPTY为高电平表示系统命令已被ADD-ON全部读出。

本系统采用同步方式将ADD-ON数据以DMA方式送入计算机内存,当写满时,WRFULL变为高电平,产生DMA中断,驱动一次DMA将S5933 FIFO的数据读出。

3.3.3 驱动程序设计

AMCCS5933操作简单,通过他内部FIFO接口在PCI总线上进行DMA高速数据传输,非常符合传输卡应用需要[7]。PCI数据采集设备需要设备驱动程序的支持。控制接口设备的工作,完成数据传输的任务。驱动程序不会独立地存在,而是操作系统的一部分。通过设备驱动程序,多个进程可以同时使用这些资源,从而可以实现多进程运行。

为了完成DMA操作,在自己开发的驱动程序中,首先对硬件中断端口进行虚拟化,编写好中断处理程序,然后根据自己的需要在内存中开辟并锁定一块物理地址连续的内存,同时把首地址返回给应用程序。并和驱动程序申请的资源结合起来,完成DMA操作,DMA操作完时,便会产生中断信号,调用中断服务程序,进行数据拷、DMA通道设置等工作。程序流程如图7所示。

按照以上流程设计驱动程序,关键需要解决问题有:驱动程序访问硬件;DMA传输;中断处理;驱动程序和应用程序通信。

这里选择Numega DriverWorks作为驱动程序开发工具而不是直接使用Microsoft DDK,原因是驱动程序的开发可以采用面向对象的框架结构,开发人员可以通过标准接口访问系统核心。

此外,使用DriverWorks中的DriverWizard向导工具,可以在VC环境中建立驱动程序框架,在此基础上根据具体应用要求添加相应代码实现特定功能,大大简化了开发过程并使程序具有可扩展性。

4 调试与测试

为验证系统的有效性,采用标准信号源产生的正弦波信号对板卡进行了测试。并给出部分测试的结果和数据。由于2个AD7656分别使用了PCI总线的高低16位2路传输,每路只包含6个通道混在一起的数据,测试中上下二路情况是一样的,这里,仅给出上面一路的实验情况及结果。

其中,图8是在输入一路正弦波,分离后该路显示的波形图;图9是输入一路正弦波,第6路下拉到地,其余接参考电位,并按帧分离后的显示结果。

输入正弦波(Vp-p=1 V),由实测数据得到输出信噪比为:60.85 dB。测试结果表明,数据完全分离开了,各路间没有互扰,信噪比达到了设计要求系统经过调试,系统已成功应用于基于盲源分离的战场目标声探测等2个课题研究,实践证明,该系统稳定可靠。

摘要：针对音频BSS(盲源分离)瞬时模型的多信源多传感器问题,提出一种严格的多路并行同步数据采集的ADC方案。首先介绍ADC AD7656的性能特点,提出并实现一种并行同步多路音频数据采集的系统方案。着重介绍AD7656周围电路的设计和控制逻辑的实现,解决多路采集时序及数据分离的难题;设计完成PCI采集系统的数据接口和驱动程序;采用CPLD作控制核心,简化设计,且方便应用的扩展;最后,给出测试结果。该系统已实际应用于相关课题的研究。

关键词：AD7656,并行同步,S5933,音频数据采集

参考文献

[1]佚名.ADI推出iCMOS模拟IC顿起波澜[J].今日电子,2004(12):135.

[2]刘新光.高性能ADC相继出台,工业和通信领域备受关注[J].电子产品世界,2005(2):92-94.

[3]陈茹梅,郭建硕.AD7656型模/数转换器在信号采集系统中的应用[J].国外电子元器件,2006(2):67-71.

[4]ANALOG DEVICES,250 kSPS,6-Channel,SimultaneousSampling,Bipolar 16-/14-/12-Bit ADC———AD765xData Book.

[5]周林,殷侠.数据采集与分析技术[M].西安:西安电子科技大学出版社,2005.

[6]A MCC公司,S5933 32-Bit PCI"MatchMaker"February12,1997 Revised October 1998.

并行机调度遗传算法研究 篇7

并行多机调度问题是NP-Hard问题，它既有丰富的研究内容，同时在生产调度，机械制造等方面有广泛的实际应用价值。但是在实际操作中，人们常常按经验法则 (如处理时间短优先调度或到期日早优先调度) 进行调度，这样得到的调度结果一般不能满足实际环境的需求，而且当并行机数和工件数增加时，问题的复杂度成指数增加，传统方法不适合解决此类问题。目前的并行机调度问题研究大部分是集中于简化问题，然后寻找最优解或次优解。

如何使并行机调度问题更接近实际生产状况并找到次优解成为本问题研究热点之一。遗传算法由于其固有的全局搜索与收敛特性，能够较好地解决此类优化组合问题。用遗传算法解决并行机调度问题已经有相关研究，其中Cheng提出一套方案，利用特殊符号 (*) 和工件号组成染色体，特殊符号为分隔符，将工件分成不同的组，每个工件组指派到不同的并行机中。本文对Cheng的方案进行了改进，并且把工件延迟与提前完成成本、机器闲置时间成本和机器设备启动成本等列入考虑因素，使多机调度问题的解决更接近实际的生产状况，目的在于求得考虑实际因素下的次优调度结果，以降低存货存储、交货延迟的违约、设备及人力等成本。

（二）遗传算法与并行机调度问题

1. 遗传算法

遗传算法是一种模仿自然界中优胜劣汰自然选择规则的随机搜索方法，该算法是从一系列的初始点 (被称为初始种群) 开始，通过循环执行选择、交叉和变异等遗传操作，逐步得到问题接近全局的最优解。

2. 并行机调度问题

考虑并行机调度中的实际需求定义如下并行机调度问题：设有m (m>1) 台并行机M1, M2, …Mm，需要加工n个工件，F时调度工作结束，每个工件订单零时刻到达，可在任一台机器上完成加工。工件一旦分配给某机器加工就必须加工完毕，不许中断。工件i在机器j上加工前准备时间为Zij，加工时间为Tij，工件i的到期时间为Qi，机器j一天的工作时间为Wj，启动成本为Sj，闲置成本权重比例为Rj，则工件i的完成日期Ci为本身加工前准备时间Zij (j为工件i的加工机器) 、加工时间Tij与机器j中i工件之前所有工件消耗时间之和，提前完成时间Bi为max (0, Qi-Ci) ，延迟时间Di为max (0, Ci-Qi) ，机器j的闲置时间为Ij (F减j上最后一个工件完工时间) 。问如何安排每台机器上所加工的工件及加工顺序使成本最小。

（三）算法设计

在Cheng的方案基础上，提出了一个染色体的改进的编码组成方式，重新设计了适应度函数和进化机制。

1. 染色体编码与适应度函数设计

并行机调度问题的染色体必须表示两个方面的信息：一方面确定工件加工所在的机器，另一方面确定每台机器上工件的加工顺序。本算法中染色体编码时用自然数序列表示工件排列，用含数字下标的分隔符*i (0

遗传算法演化过程的目的在于使适应度函数最小化，如果用B, D, S, I分别表示提前、延迟、重启和闲置成本，则演化的目的是要找到最好的排列使得：

F (B*, D*, S*, I*) =min{F (B, D, S, I) }, 适应度函数为F,

Bi, Di, Sj, Rj, Ij意义同上，α (Bi) , β (Di) 分别为提前和延迟完工成本函数，γj的值在机器j上有工件分配时等于1，否则为0。

2. 种群初始化

初始种群的个体分为两类，第一类个体随机生成;另一类个体可以按一定经验法则生成，比如可以把处理时间作为考虑因素，处理时间越短越先安排，确保在最短的时间里做尽可能多的工件，或者按到期日期为标准，越早到期的工件越早安排，可以使大部分工件如期完成。

3. 选择

选择过程的目的是为了从当前群体中选出优良个体，使他们有机会作为父代将其优良的个体信息传递给下一代，使子代向最优解逼近[1]。判断个体优良与否的标准是各自的适应值。每个个体的选择概率采用基于排序的适应度分配 (rank-based fitness assignment) 方法，种群按适应度进行排序，个体的生存概率使用Baker提出的线性排序计算公式求得：其中i为个体排序序号，N为种群大小，1<=η+<=2, η–=2–η+。然后用轮盘赌选择法 (roulette wheel selection) 来决定每个个体的选择份数，选择后的N个个体送到配对库，以备配对繁殖。

4. 交叉

交叉是结合来自父代种群的信息产生新的个体，依据个体基因编码表示方法的不同有多种交叉算法。这里采用两点顺序交叉 (OX) ，顺序交叉能够保留排列并融合不同排列的有序结构单元。如有下面两个父个体，交叉操作步骤如下：

(1) 随机选择两个交叉点”|”，保留交叉点之间的中间段不变。

(2) 把父个体2从第2个交叉点作排列，到达表尾时返回表头继续，得到排列*3 2 7*4 8 4 1*2 5*1 3 6，减去父个体1中已有基因部分4 5*1*3 2得到排列顺序7*4 8 1*2 36，再将这个顺序从第2个交叉点开始复制给子个体1，以此决定子个体1对应位置的未知码x，生成子个体1即q1: (3 64 5*1*3 2 7*4 8 1*2) ，同样产生子个体q2: (*3 2*2 5*13 6 7*4 8 1 4) 。

5. 变异

变异是子代基因按小概率产生的变化。同样可以采用多种方法实现基因变异，如可以采用交换两个基因位置实现变异，但是这种方法个体变异较小，不利于新个体的生成，特别是当交换的两个基因都是数字时，新个体只是改变了两个工件的加工位置。这里使用另外一种方法实现变异操作即首先随机选取父代中的某优秀染色体，对照染色体基因个数 (m+n) 随机生成一个二进制序列，将染色体中对应0的基因选为一组，对应1的基因选为另一组，两组基因重新组合得到子个体。变异操作如下：

6. 种群进化与停止准则

标准遗传算法若在群体选择前 (或后) 保留当前最优值，则最终能收敛到全局最优值。本算法通过改进标准遗传算法，在群体选择作用前保留当前最优解，则保证本算法在某些情况下收敛到全局最优解。

停止准则一般预先设定一个最大的繁殖代数Nmax，在繁殖过程中进行到最大的繁殖代数则停止运行。

综上所述，本并机行排序问题的遗传算法伪码如下：

（四）结果

设有45个工件要在3台机器上加工。在工作提早与延迟完成成本方面，按照工件的重要性将提前与延迟完成成本公式分为三类：

对重要性不高的工件成本公式为：

对重要性一般的工件成本公式为：

对优先权高的工作成本公式为：

工件在不同机器上的加工时间，加工前准备时间，机器启动和闲置成本表略。种群大小为50，最大遗传代数为80，交叉概率为0.6，变异概率为0.01。按本文与Cheng所提算法分别演算，所得结果如表1所示：

由表1可知，本文算法有助于使最后解答的染色体之间的差异性小，每次运算后的解接近最优解。

（五）结束语

本文重新设计了染色体的组成方式，问题的解空间表示得更明确，设计了算法进化机制，求解效率得到提升，考虑了并行机调度问题中的更多实际因素，本算法有一定的实用价值。然而实际影响并行机调度的因素并不限于本文所讨论的范围，另外适应度函数中的权重比例，也需要根据不同工厂的需求做适当的调整。今后将研究影响并行机调度的其它一些因素，使并行机调度问题与实际应用紧密结合，并且考虑把遗传算法与其它算法结合，使遗传算法收敛更快更高效。

摘要：为解决接近实际生产状况的并行机调度问题, 将工件延迟与提前完成成本、机器闲置时间成本、机器启动成本列入考虑因素。在遗传算法的设计上, 提出了一套染色体的组成方式, 设计了适应度函数和进化机制, 使其能较好地表示问题的解空间并提升求解效率, 具有一定的实用价值。

关键词：并行机调度,遗传算法,适应度

参考文献

[1]何军辉, 周泓.求解含调整时间并行机排序问题的遗传算法[J].系统工程理论方法应用, 2002, 12.

[2]欧锦文, 施保昌.平行机排序邻域搜索算法设计[J].计算机工程与应用, 2003, 18.

[3]Cheng, Runwei.Minmax Earliness/Tardiness Scheduling in Identical Parallel Machine System Using Genetic Algorithms[J].International Conference on computers and industrial Engineering, 1995:29:513-517.

[4]张聚, 李平.基于演化算法的车间作业调度问题的求解方法[J].浙江大学学报, 2004, 12.

并行技术领域中调度算法研究 篇8

并行技术是指系统资源足够条件下并行性处理任务, 来达到大幅度提高性能和效率的目的, 一般的并行技术应用在并行计算, 并行工程, 并行服务器等领域。

其中, 并行计算是相对串行计算而言的, 分为时间与空间上的并行, 时间上并行是指流水线技术, 空间上的并行指用多个处理器并发执行计算, 本文中的并行计算主要指空间上的并行, 并行计算的主要目的是快速解决大型且复杂的计算问题, 其中的调度算法是并行计算的主要研究方向之一。

并行服务器作为网络服务器, 提供与客户端之间多对多的连接, 与单机服务器相比在可靠性、可用性、效率及平均响应时间上都有显著的优越性, 有效的调度算法对提高网络的服务性能和传输效率尤为重要。

2. 并行调度算法分析

2.1 并行计算与处理任务的调度算法

在并行计算与处理中, 调度算法的目的是解决如何把复杂应用程序的所有任务调度到多处理器系统中, 并要求最小的执行时间, 一般来说, 并行任务的调度问题可以看作两个逻辑上相对独立的阶段:一是任务映射 (Map) , 即确定任务节点映射到哪一个具体的处理单元上, 可表述为Assign:={ (Ti, Pj) |Ti→Pj, i∈n, j∈k}。其中Ti代表任务节点, Pj代表处理单元, n表示任务节点的个数, k代表处理单元的个数;二是任务的具体调度, 即对于所有的处理单元, 映射在其上的相应任务节点具体何时开始执行, 可表述为:其中ST (Ti) 表示任务Ti的开始执行时间, 在调度算法中, 这两个阶段并不都有明显的分界, 如基于表的调度算法就看不出两个阶段的分界, 根据计算环境的不同, 并行任务在基于同构和异构环境下任务调度算法亦有差异。

2.1.1 基于同构系统的并行任务调度算法[1]

同构系统中并行任务调度主要分为静态调度算法 (也称编译时间调度) 和动态调度算法 (也称实时调度) , 静态调度算法要求任务图和处理单元相关的信息在程序执行前可以精确获取, 调度好的任务节点不能迁移, 此类算法的关键是如何精确获取所需信息;而动态调度算法需要程序实时执行期间得到相应调度信息来实时调度任务, 有许多不确定因素存在, 调度开销较大, 一般用于大型分布式系统的网格计算中, 也适用于含有条件分支和循环的任务图调度。

并行任务调度的常用数学模型有:树结构, Fork-Join结构以及任务图, 典型的并行任务调度模型都是基于图的, 有:任务交互图TIG模型, 任务优先图TPG模型, 时态任务交互图TTIG模型[2], 模型的主要区别如表1所示。

基本任务调度技术包括:表调度, 基于任务复制的调度, 基于任务集群或聚类的调度, 非确定性调度。

表调度的基本思想是通过对节点的优先级别进行排序来构造一个调度列表, 然后从调度列表中顺序取出每个节点分配到使它的启动时间最早的处理器上, 直到任务图中所有节点被调度完, 这是静态的表调度, 而动态的表调度算法在每次分配节点后都重新计算所有未被调度节点的优先级别, 并根据新的优先级别来重新排列节点中的顺序。典型算法有:H L F E T, I S H, E T F, M C P, D L S, M H。

基于任务复制调度算法的思想主要是利用处理器的空闲时间复制前驱任务, 避免某些前驱任务的通信数据的传输, 从而减少处理器等待的时间间隙。根据选择复制任务的不同策略可以形成不同的基于任务复制的调度算法, 一些算法仅仅只复制直接前驱任务, 而有些算法复制所有可能的前驱任务。与其他的调度技术相比, 该类算法有比较高的时间复杂度, 同时大多数情况下要求不受限制的处理器数目。典型的算法有:D S H, B T D H, C P F D, PY, D F R N。

基于任务集群或聚类的调度思想是把给定任务图的所有任务映射到数量不受限的集群上。在算法的每一步, 选择进行集群的任务可以是任一任务而不必是一个就绪任务。在每个集群循环中把上一步的一些集群合并成新的集群。如果两个任务分配到同一个集群, 则表示它们在同一个处理器上执行。除了执行集群的步骤外, 算法还必须对完成映射的集群进行最后的调度, 即对集群中的任务在每个处理器上进行时间先后排序。如果处理器数目有限, 在集群步骤中还必须考虑使集群的数目与可用的处理器数目相等。典型的算法有:M D, L C, E Z, D S C, D C P。

非确定性调度技术又称为随机搜索调度技术, 主要是通过有导向的随机选择来搜索问题的解空间而不是单纯的随机搜索。这类技术组合前面搜索结果的知识和特定的随机搜索特点来产生新的结果。遗传算法是最流行和使用最广泛的该类技术, 它们的调度时间一般高于使用其他技术的调度算法, 适合于某一种任务图的控制参数优化集并不适合于另一种类型的任务图, 即对新的任务图遗传算法需要长时间的训练学习。另外模拟退火方法也属于该类型技术。

2.1.2 基于异构环境的并行任务调度算法[3]

异构环境往往是异构网络、异构处理机、处理器数目可变的节点组成的异构系统, 其任务调度就是如何把复杂应用程序的所有任务合理地调度分配到异构计算机系统中的各个处理机上, 并要求整个应用程序最小时间完成, 任务调度大都是NP完全问题, 从不同角度, 任务调度问题可分类为:静态和动态调度, 集中式和分布式调度, 抢占式和非抢占式调度, 自适应和非自适应式调度。异构环境的调度模型和调度技术分类大致与同构相同, 典型的任务调度算法见表2。

2.2 分布式并行服务器的调度算法

为保证多客户端随机而又基本均衡地将服务请求发往并行服务器中的各节点机, 使得服务器中各节点机接收到的绝大部分请求都不需要再次进行负载平衡调度, 在分布式服务器中引入并行处理机制, 将分布式动态任务调度机制和并行处理机制融为一体形成分布式并行服务器, 目的在于大幅度的提高系统可用性、吞吐率、I/O响应速度以及存储容量等, 该技术已被广泛应用到WWW、视频、教育服务中。

其中, 具有并行I/O接口的分布式并行服务器, 在客服端和服务器端有相应分布式并行I/O接口使得各节点机均可直接与众多客户机交互作用, 可保证80%以上的客户请求均可一次直接发往能提供服务的服务器中的节点机, 少量请求需在节点间动态负载调度[4]。

文献[5]中介绍了电网自动化中的两种高可靠的分布式任务调度算法——全局动态调度ADS算法和上次优先调度LFS算法, 这两种算法是基于ASSIGN-U虚电路路由扩展算法提出的, 可保证电网自动化系统的实时性和高可靠性。其中全局动态调度为每次服务请求都进行全局调度而LFS基本的思想是:调度者先判上一次提供服务的节点还能继续提供服务则选之, 否则进行全局调度, 这样可减少调度;判断的开销以及探测负载信息的节点数量, 提高了整个调度速度。L F S算法可描述如下:

1) .任务请求到来;

2) .调度者在路由表中查找上次的执行者, 若找不到则转5;

3) .调度者将要处理的函数和数据发送给上次的所有执行者;

4) .调度者接收上次所有执行者的响应, 若响应都为可执行, 则转1 1;

5) .调度者向其它可执行节点发送请求, 要求返回负载信息和上次执行这类服务的时间;

6) .调度者等待100ms或收到所需的响应数后, 登记响应节点的负载信息, 若响应不满足调度需求, 转8;

7) .调度者从响应者中根据ASSIGN-U虚电路路由扩展算法选择K个替补节点作为执行者, 转9;

8) .调度者重发请求, 再等200ms, 如果响应正常转7.否则认为调度失败, 向用户给出提示;

9) .调度者修改调度互斥量, 若修改不成功且调度者为互斥量所在节点, 或调度者为非互斥量所在节点但检测到互斥量已被其镜像节点修改, 则任务调度结束;

10) .把数据发送到执行者, 并启动服务;

11) .调度者在路由表中标记执行者;

12) .任务调度结束。

电网自动化调度模型中, A D S算法和LFS算法的实现是通过修改Linux内核来完成的, ADS适用于处理数据量大的系统, LFS对处理数据量较小的系统性能较好。

3. 结束语

并行任务调度算法需考虑多处理器系统是松散还是耦合, 任务的优先级别以及实时性要求等诸多因素, 尤其在异构计算环境中, 各个处理单元的处理能力完全不同, 处理单元之间的互联网络也存在带宽和时延的差异, 要设计合理的并行任务调度算法追求低的负载平衡调度和较高执行效率, 需要进一步深入的研究和探讨。

摘要：主要对同构和异构环境下的并行任务调度算法进行分类, 对任务调度模型以及调度算法进行阐述并列表比对;对分布式任务调度, 介绍了两种算法——全局动态调度ADS算法和上次优先调度LFS算法, 最后指出设计合理并行任务调度算法的重要性。

关键词：并行计算,并行服务器,调度算法

参考文献

[1]马丹, 张薇, 李肯立.并行任务调度算法研究[J].计算机应用研究.2001, (11) :91￣94

[2]C Roig, A Ripoll, M A Senar, et al.A New Model for Static Mapping of Parallel Applications with Task and Data Parallelism[C].Proceedings of the International Parallel and Distributed Processing Symposium, 2002.78-85.

[3]李显宁, 钟诚.异构计算机环境下并行任务调度算法研究进展分析[J].计算机科学.2006, (8) :22￣26

[4]刘心松.具有分布式并行I/O接口的分布式并行服务器系统的性能研究[J].电子学报.2002, (12) :1808￣1810