用快速多项式变换（FPT）计算二维离散富里叶变换（DFT）

本文利用快速多项式变换(FPT)计算N×M 型二维DFT(M=2~m,N=2~(m-r+1),1≤r≤m),所需的乘法及加法次数(复乘及复加)分别为M_u=1/2NMlog_2M-3/2NM+N~2+N(1+log_2M-log_2N)A_d=NMlog_2NM,与通常的以2为基的二维FFT 比较,加法次数相同,乘法次数减少约30—40%,从而提高了计算精度。本算法还适用于并行算法。     

用快速多项式变换 (FPT) 计算二维 DFT的混合算法

本文首先提出用多项式逆变换计算二维DFT的方法(k_2是奇数 或偶数分别讨论),然后再讨论混合算法。对于N×N(N=2~t)二维DFT,混合算法所需的运算量为(?) 与通常以2为基的二维FFT(行列算法)比较,加法次数相同,乘法次数减少,约20-40%。     

DFT的Z变换算法

文中讨论了用Z变换计算DFT的方法。对于N=2~t的DFT,本算法所需的加法及乘法量分别为:(?),与Cooley-Tukey基-2算法比较,乘法量与加法量均减少25%,文中还讨论了本算法在微机上的实现,给出流程图。在运算时间上,本算法与通用FFT算法程序进行比较:节省时间30%。     

二维 DFT 和 DCT 的 Systolic 阵列

超级计算中一个活跃的研究领域是将某些有限和,如离散富里叶变换(DFT)、离散余弦变换(DCT),映射到多处理机阵列上。本文首先通过二维DFT的行列分解算法流程图,给出了计算二维DFT的二种Systolic阵列:一种是由N_1个处理器组成的线性阵列,所花时间步为O(N_1N_2)(设二维DFT为N_1×N_2长的),与行列分解算法在单处理机上顺序执行所花时间相比,加速比为O(N)(设N_1=N_2=N)。这一结果无论是在时间消耗,还是在PE数量上都是目前最优的。另一种是由N_1×N_2个处理器组成的矩形阵列,所需时间为O(N_1+N_2),与行列算法在单处理机上顺序运行所花时间相比,加速比为O(N~2)(这里仍假定N_1=N_2=N)。本文还给出了二维DCT的与二维DFT相似的Systoilc阵列结构。不难将上述阵列推广到多维的情况。     

双字长浮点乘法运算算法设计与分析

文中给出了在计算机上实现双字长浮点乘法运算的算法的计算公式、计算步骤及误差估计,算法原理适用于一般计算机系统的任意字长浮点乘法运算。     

基于单DSP实现并行扩维离散Hartley变换算法的研究

提出了一种将N点的一维离散Hartley变换(简称DHT)分解成N0×N1点的二维DHT(其中N=N0×N1)和一些运算量很小的附加运算的并行扩维DHT算法,此算法通过减少数据相关性的方法突破了DSP高效求解快速离散Hartley变换(简称FHT)时问题规模受片内内存容量限制问题,降低了编程复杂性,并在TMS320C80的单处理单元上进行了该算法实现方法的研究.结果表明,理论分析和试验结果吻合,该算法适合在单DSP上实现.     

1024位RSA算法的FPGA设计研究

改进了高基免减蒙哥马利(Montgomery)算法,使得乘法和加法的总运算量分别减少了约3%和2%。根据平行并行乘法器,设计了适用于模乘运算的一维阵列组合乘法器。基于高基蒙哥马利算法,设计并仿真了1024位密钥的RSA加/解密系统。     

一种基于FMA加速FFT计算的向量化方法

提出一种基于融合乘加指令加速FFT计算的向量化方法,通过变换FFT的蝶形单元运算流程,将传统计算方式中独立的乘法和加法操作组合成次数更少的融合乘加操作,使得DIT基2 FFT算法的蝶形单元计算的实数浮点操作由原来的10次乘(加)操作减少到6次融合乘加操作,DIT基4 FFT算法的蝶形单元计算的实数浮点操作由原来的34次乘(加)操作减少到24次融合乘加操作;优化了蝶形因子的向量访问,减少存储开销。实验结果表明,提出的方法能够显著加速FFT的计算,取得高效的计算性能和效率。     

使用融合乘加加速快速傅里叶变换计算的向量化方法

融合乘加指令加速快速傅里叶变换计算的向量化方法,通过变换快速傅里叶变换的蝶形单元运算流程,将传统计算方式中独立的乘法和加法操作组合成次数更少的融合乘加操作,使得时间抽取法基2快速傅里叶变换算法的蝶形单元计算的实数浮点操作由原来的10次乘(加)操作减少到6次融合乘加操作,时间抽取法基4快速傅里叶变换算法的蝶形单元计算的实数浮点操作由原来的34次乘(加)操作减少到24次融合乘加操作;优化了蝶形因子的向量访问,减少存储开销。实验结果表明,提出的方法能够显著加速快速傅里叶变换的计算,取得高效的计算性能和效率。     

DFT 的新算法

本文通过对离散富里叶变换(Discrete Fourier Transform,简记作DFT)矩阵的分解与FFT 算法相结合,提出了一个计算DFT 的新算法。由对矩阵的分解把求N=2~t 点的DFT 问题化为求16个N/16阶方阵与相应列向量相乘的问题(N≥16)。从而减少了乘法运算次数,且还具有良好的并行运算性质。     

高精度CFD程序的内外子区域划分异构并行算法

对计算流体力学(Computational Fluid Dynamics, CFD)程序CNS提出一种Offload模式下对任务内外子区域划分的异构并行算法,结合结构化网格下有限差分计算和四阶龙格-库塔方法的特点,引入ghost网格点区域,设计了一种ghost区域收缩计算策略,显著降低了异构计算资源之间的数据传输开销,负载均衡时CPU端的计算与MPI通信完全和加速器端的计算重叠,提高了异构协同并行性。推导了保证计算正确性的ghost区域的参数,分析了负载均衡的条件。在"CPU(Intel Haswell Xeon E5-2670 12 cores×2)+加速器(Xeon Phi 7120A×2)"的服务器上测得该算法较直接将任务子块整体迁至加速器端计算的异构算法性能平均提升至5.9倍,较MPI/OpenMP两级并行算法使用24个纯CPU核的性能,该算法使用单加速器时加速至1.27倍,使用双加速器加速至1.45倍。讨论和分析了性能瓶颈与存在的问题。     

广义Liénard方程Poincaré分岔极限环的唯一性和不存在性

讨论了一类广义Linard方程x¨+f1(x)x.2+εf2(x)x.+g(x)=0的Poincar分岔极限环的唯一性和不存在性。将不对Abel积分进行分项,而是利用一阶Mel′nikov函数直接从整体上进行分析讨论,得出了若干判别准则和充分条件。     

基于内外子区域划分的高阶精度CFD程序异构并行算法

对计算流体力学(CFD)程序CNS提出一种Offload模式下基于内外子区域划分的异构并行算法，结合结构化网格下有限差分计算和四阶龙格库塔方法的特点，引入ghost网格点区域，设计了一种ghost区域收缩计算策略，显著降低了异构计算资源之间的数据传输开销，负载均衡时CPU端的计算与MPI通信完全和加速器端的计算重叠，提高了异构协同并行性。推导了保证计算正确性的ghost区域的参数，分析了负载均衡的条件。在“CPU(Intel Haswell Xeon E5-2670 12 cores ×2)＋加速器(Xeon Phi 7120A ×2)”的服务器上测得该算法较直接将任务子块整体迁至加速器端计算的异构算法性能平均提升5.9倍，较MPI/OpenMP两级并行算法使用24个纯CPU核的性能，该算法使用单加速器时加速1.27倍，使用双加速器加速1.45倍。讨论和分析了性能瓶颈与存在的问题。     

Improved bounds for batch scheduling with nonidentical job sizes

Here, we revisit the bounded batch scheduling problem with nonidentical job sizes on single and parallel identical machines, with the objective of minimizing the makespan. For the single machine case, we present an algorithm which calls an online algorithm (chosen arbitrarily) for the one‐dimensional bin‐packing problem as a sub‐procedure, and prove that its worst‐case ratio is the same as the absolute performance ratio of . Hence, there exists an algorithm with worst‐case ratio , which is better than any known upper bound on this problem. For the parallel machines case, we prove that there does not exist any polynomial‐time algorithm with worst‐case ratio smaller than 2 unless P = NP, even if all jobs have unit processing time. Then we present an algorithm with worst‐case ratio arbitrarily close to 2. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 351–358, 2014     

Queues with stochastic service rates

The purpose of this paper is to explore an extension of the output discipline for the Poisson input, general output, single channel, first-come, first-served queueing system. The service time parameter, μ, is instead considered a random variable, M. In other words, the service time random variable, T, is to be conditioned by a parameter random variable, M. Therefore, if the distribution function of M is denoted by F_M(μ) and the known conditional service time distribution as B(t |_μ), then the unconditional service distribution is given by B(t) = Pr {T ≤ t}. = ∫_-∞^∞ B(t |_μ) dF_M(μ). Results are obtained that characterize queue size and waiting time using the imbedded Markov chain approach. Expressions are derived for the expected queue length and Laplace-Stieltjes transforms of the steady-state waiting time when conditional service times are exponential. More specific results are found for three special distributions of M: (1) uniform on [1.2]; (2) two-point; and (3) gamma.     

An M/M/1 queue with delayed feedback

We present some results for M/M/1 queues with finite capacities with delayed feedback. The delay in the feedback to an M/M/1 queue is modelled as another M-server queue with a finite capacity. The steady state probabilities for the two dimensional Markov process {N(t), M(t)} are solved when N(t) = queue length at server 1 at t and M(t) = queue length at server 2 at t. It is shown that a matrix operation can be performed to obtain the steady state probabilities. The eigenvalues of the operator and its eigenvectors are found. The problem is solved by fitting boundary conditions to the general solution and by normalizing. A sample problem is run to show that the solution methods can be programmed and meaningful results obtained numerically.     

Scheduling parallel machines with inclusive processing set restrictions

We consider the problem of assigning a set of jobs to different parallel machines of the same processing speed, where each job is compatible to only a subset of those machines. The machines can be linearly ordered such that a higher‐indexed machine can process all those jobs that a lower‐indexed machine can process. The objective is to minimize the makespan of the schedule. This problem is motivated by industrial applications such as cargo handling by cranes with nonidentical weight capacities, computer processor scheduling with memory constraints, and grades of service provision by parallel servers. We develop an efficient algorithm for this problem with a worst‐case performance ratio of + ε, where ε is a positive constant which may be set arbitrarily close to zero. We also present a polynomial time approximation scheme for this problem, which answers an open question in the literature. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Defense spending and economic growth: Extended empirical analysis for the European Union

Previous empirical studies on the defense spending-economic growth nexus such as Kollias et al. (2007 Kollias, C., N. Mylonidis, and S. Paleologou. 2007. “A panel data analysis of the nexus between defense spending and growth in the European Union.” Defense and Peace Economics 18 (1): 75–85.[Taylor & Francis Online], [Web of Science ®] , [Google Scholar]), Mylonidis (2008 Mylonidis, N. 2008. “Revisiting the nexus between military spending and growth in the European Union.” Defense and Peace Economics 19 (4): 265–272.[Taylor & Francis Online], [Web of Science ®] , [Google Scholar]), Dunne and Nikolaidou (2012 Dunne, J. P., and E. Nikolaidou. 2012. “Defense spending and economic growth in the EU15.” Defense and Peace Economics 23 (6): 537–548.[Taylor & Francis Online], [Web of Science ®] , [Google Scholar]) analyzed this relationship in the case of the EU15. This study extends the analysis with the inclusion of more EU members and investigates the long run causal ordering between the two variables. Findings reported herein are not uniformed across all EU members. It is also found that end of Cold War has significant negative impact on defense expenditures of former east-European countries.     

分析电路的改进节点法

本文针对含有理想电压源支路的电路,提出了改进节点法,其解变量为电路真正的独立节点电压(N-M-1),较之混合法(N+M-1)少(因其求解变量为节点电压和理想电压源支路的电流,其中 N 为节点数目,M 为独立电压源支路数)。文中还举例说明了这种方法的应用,并验证了它的正确性.