混合模型下FMM算法中近程计算的优化研究

为提高计算多体问题的效率,通过分析多体问题的典型算法FMM(fast multiple method)的计算特点,提出运用CPU和加速部件FPGA构成混合部件计算其近程作用的方案。重点研究混合计算模型上的近程计算特性和优化策略,从计算、通信和存储多方面分析近程计算,提出分层按块的数据准备策略,及在该策略中修改FMM空间编码方式,使近程计算更好地适应于混合模型,从而提高整个FMM算法的执行效率。实验结果表明了该数据准备策略和采用的空间编码方式的可行性和高效性。     

树结构在N体问题中的应用*

N体问题的数值模拟在每个时间步都需要计算每对粒子之间的相互作用,其复杂度为O(N2).采用树结构代码不仅减少了存储开销,而且更有利于快速计算和并行划分.Barnes-Hut算法(BHA)和快速多极子方法(FMM)都是基于树结构的快速算法.BHA可快速计算各点受到的场力,计算复杂度为O(N log N),但计算精度通常只有1%;FMM通过层次划分和位势函数的多极子展开计算各点位势,其复杂度为O(N),却能达到任意精度.数值结果表明,树结构的并行效果也很好.     

FMM算法中问题规模与空间划分的关系分析

从编译优化和并行优化的角度出发,根据N-Body问题求解的FMM算法的原理,将算法分解为不同的子模块。详细分析了各子模块的计算特性,包括计算量分析、并行性分析、通信量分析和存储量分析。深入剖析问题规模与空间划分层数之间的关系,提出基于问题规模的空间划分策略。以实验验证了空间划分策略的可行性。     

基于雾计算的计算资源分配方案

雾计算可以为用户提供近距离的数据存储、计算和其他服务，因此雾计算中的任务调度和资源分配已经成为一个新的研究热点。考虑终端用户和雾设备通常处于一种相对开放的状态，扩展了雾计算的体系结构，提出一种开放式雾计算环境中基于稳定匹配的计算资源分配方案，利用雾网络中动态的计算资源协同为用户提供计算服务并收取计算收益，同时终端用户向雾服务器提交任务请求并支付一定的费用。基于稳定匹配的思想，利用子任务的优先级列表、子任务和计算服务设备的偏好列表解决子任务与计算服务设备的分配问题，保证任务的完成时间和计算服务设备的收益。通过实验对方案性能进行了分析，实验结果表明该方案的资源分配时间相对稳定，且在执行雾计算任务时延以及任务违规率上都优于SGA算法和ACOSA算法。     

有向无环图的高效归约算法

将一个应用程序部署到给定的片上网络上执行时,需要将应用程序中的每一个子任务都指派给片上网络中的一个节点执行。该问题一般被建模成一组子任务作为顶点的有向无环图,任务在片上网络上的部署过程就等同于一个有向无环图的顶点向一个片上网络拓扑映射的过程。而随着应用程序和片上网络规模的增大,计算一个最优的映射方案是典型的难解问题。为了加速有向无环图到片上网络拓扑的映射过程,提出了有向无环图的归约算法,使归约后的图中的顶点数量尽可能地与给定片上网络中的节点数量相同。提出的图归约算法可以有效地识别出所有可归约子图,这些可归约子图可被归约为单一顶点。新算法的适用范围从嵌套图扩展到了任意图,并且拥有与原算法相同的复杂度量级。还提出了一种并行化的算法思想来加速可归约子图的搜索过程。     

FMM能效分析及其ASIC可行性评估

对快速多极方法(FMM)进行研究,分析其关键计算任务,并在CPU与DSP上进行验证,得出FMM在不同平台上性能和功耗的量化分析结果,给出基于FMM的多核DSP可重构ASIC结构模型。以可重构硬件FPGA为例,对该模型进行预测,结果证明其在涉及大规模浮点计算时具有一定的能效优势。     

时间序列流Top-K不协调子序列的发现

摘要: 针对传统算法中有关时间序列流不协调子序列计算代价比较高的问题,提出了一种快速发现Top-K不协调子序列的算法。该算法通过特殊的数据结构保留计算结果,避免了大量的重复计算,从而达到降低时间复杂度的目的;同时也通过一定的保留策略只保留有用的计算结果并及时清理无用的计算结果,从而达到降低空间复杂度的目的。实验采用随机数据和真实数据进行算法测试,其结果表明,该算法能显著降低计算量从而实现快速发现Top-K不协调子序列的目的。 关键字: 流时间序列;不协调子序列;实时     

用改进Census变换实现光照变化鲁棒光流计算

针对当前光流算法在野外光照变化条件下计算精度不高的问题,提出一种基于改进Census变换的变分光流算法.该算法根据图像轮廓信息自适应选择变换窗口形状,以提高深度不连续区域图像子块信息描述的准确性;在变换窗口内构建完整的梯度流向量描述子,克服传统算法由于信息量不够而导致的不同图像子块区分度有限的问题;在构建二进制串时,与基准元素越近的点排在二进制串高位,减弱2帧图像因投影变形对光流求解的影响.在TV_L1变分光流计算框架下,用改进的Census变换描述子构建光流模型中的数据项.对图像进行高斯金字塔分解,并结合加权中值滤波进行分层光流估计.最后以Middlebury和KITTI数据库为测试平台,证明了文中算法的有效性.     

基于并行图计算框架大规模图最大流加速算法

最大流是一个重要的图计算问题,很多实际场景中如城市车流量和排水管道的排水量等问题若转化为最大流问题可以得到有效的解决.已有工作从多个角度对最大流问题进行了探讨,但仍存在一些问题.针对一些分布式图计算系统进行图分割计算复杂度较高,多次计算存在大量冗余工作等问题,提出基于GraphChi框架的大规模图最大流加速算法.根据原图中的割点构建覆盖图,给定源点和汇点后确定覆盖图中唯一路径,在GraphChi框架上并行求解覆盖图路径上各子图的最大流,找到各子图最大流的最小值即为原图的最大流值.在美国路网数据集的测试结果表明,提出的算法可显著缩短大规模图的最大流计算时间并且空间复杂度较低,有很好的加速效果.     

面向实时流数据处理的边缘计算资源调度算法

针对边缘计算带宽限制导致的实时流数据处理计算效率低下的问题,提出一种迭代优化算法FFS+IPFS,通过对应用负载的实时监控,实现合理的边缘节点任务部署,支持实时流数据处理任务.首先,利用贪心算法进行全局任务分配,通过贪心的算法得到一个近似最优的结果;然后,基于监控到的实时任务信息,通过迭代优化进行局部调优,使得同一数据流的任务可以被部署在相近的边缘节点,从而有效减少任务通信的开销.在不同场景下,平均时延相比其他主流算法可降低23％.大量的模拟实验结果表明,所提算法可以实现有效的资源调度,支持边缘计算场景下高效的实时流数据处理应用.     

Automatic dynamics simplification in Fast Multipole Method: application to large flocking systems

This paper introduces a novel framework with the ability to adjust simulation’s accuracy level dynamically for simplifying the dynamics computation of large particle systems to improve simulation speed. Our new approach follows the overall structure of the well-known Fast Multipole Method (FMM) coming from computational physics. The main difference is that another level of simplification has been introduced by combining the concept of motion levels of detail from computer graphics with the FMM. This enables us to have more control on the FMM execution time and thus to trade accuracy for efficiency whenever possible. At each simulation cycle, the motion levels of detail are updated and the appropriate ones are chosen adaptively to reduce computational costs. The proposed framework has been tested on the simulation of a large dynamical flocking system. The preliminary results show a significant complexity reduction without any remarkable loss in the visual appearance of the simulation, indicating the potential use of the proposed model in more realistic situations such as crowd simulation.     

嵌入式操作系统混合任务调度技术与策略研究

针对当前嵌入式系统中时间触发与事件触发混合任务的特点,以μC/OS-II操作系统架构为基础,设计了一种能够同时支持时间触发与事件触发的混合操作系统内核架构。该架构符合OSEK/VDX标准,具有良好的可移植性。针对混合任务调度问题,提出了一种静态周期性可抢占式混合任务调度策略,该策略同时支持中断级与任务级的任务切换,并采用EDF（最早截止时间优先）算法对被抢占的时间触发任务进行恢复,相比OSEKtime OS只能在中断级进行任务切换以及FIFO（先进先出）恢复算法,能够提高系统资源利用率,并最大限度保证任务实时性。实验分析结果表明,所设计的混合操作系统架构移植方便,所提出的混合任务调度策略可行有效,调度过程具有良好的可预测性。     

Learning the Regularization Operator for the Optical Flow Problem

The task of displacement estimation for frames of a video sequence is considered. A new convolutional neural network architecture for the optical flow problem is proposed. The method is based on learning the regularization operator for a fast optimization method. The proposed method has low computational complexity and memory footprint at test time. The neural network architecture is based on unrolling iterations of a fast primal-dual method as layers of a convolutional neural network. Iterations of the optimization method are represented as convolutions with filters that are trained on ground truth data by backpropagation. A real-time implementation using graphics processing units is proposed. Experimental results demonstrate an improved quality of the optical flow field as compared to the optimization method based on a fixed regularization operator.     

Fast multipole method based solution of electrostatic and magnetostatic field problems

Abstact Applications of boundary element methods (BEM) to the solution of static field problems in electrical engineering are considered in this paper. The choice of a suitable BEM formulation for electrostatics, steady current flow fields or magnetostatics is discussed from user's point of view. The dense BEM matrix is compressed with an enhanced fast multipole method (FMM) which combines well-known BEM techniques with the FMM approach. An adaptive grouping scheme for problem oriented meshes is presented along with a discussion on the influence of the mesh to the efficiency of the FMM. The computational costs of the FMM algorithm are analyzed for typical problems in practice. Finally, some electrostatic and magnetostatic numerical examples demonstrate the simple usability and the efficiency of the FMM. Communicated by: U. Langer     

基于云边协同的微电网自动控制系统

微电网及分布式能源的数量、规模快速发展,当前系统无法满足海量相关数据采集、存储、分析计算需求；为适应多微电网控制的高并发、高可靠性的处理要求,提出了基于云边协同的微电网自动控制系统；基于Docker容器技术优化配置云边计算资源；设计了基于云边协同的微电网自动控制系统总体架构,对云边协同功能及主要数据流进行了详细说明；进一步分析了其中微电网控制及能量管理等核心功能及其数据处理需求,提出了云边协同架构下的计算分析任务调度策略,基于带宽资源对迁移任务数据流进行调度,兼顾任务时限要求和服务器的负荷均衡；最后通过运行实例对提出的微电网自动控制系统功能及优越性进行有效性验证,所提系统通过架构、功能和任务调度策略满足了多微电网的控制要求。     

基于Browser/Server结构的远程数据采集

将网络技术融入数据采集系统使得原先在一台机器上完成的工作可以由多台机器分担，这使得数据采集站的负担大大减轻，数据分析的任务可以交给其他计算机完成。通过合理的资源配置，将可以大幅度提高系统的性能，并完成一些原先不可能完成的任务。与传统的Client/Server结构不同，本文介绍了一种基于Browser/Server结构的远程数据采集方法，利用通用网关接口（CGI）进行远程数据采集，从而用一种更简洁的方式将数据采集系统与网络结合起来。同时论述了在CGI程序中与设备驱动程序通讯实现数据采集的方法，并与其他方法进行了比较。最后通过实验证明，采用Browser/Sever结构进行远程数据采集是确实可行的，并且比传统的方法更为方便实用。     

Performance of N-body codes on hybrid machines

N-body codes are routinely used for simulation studies of physical systems, e.g. in the fields of computational astrophysics and molecular dynamics. Typically, they require only a moderate amount of run-time memory, but are very demanding in computational power. A detailed analysis of an N-body code performance, in terms of the relative weight of each task of the code, and how this weight is influenced by software or hardware optimisations, is essential in improving such codes. The approach of developing a dedicated device, GRAPE [J. Makino, M. Taiji, Scientific Simulations with Special Purpose Computers, Wiley, New York, 1998], able to provide a very high performance for the most expensive computational task of this code, has resulted in a dramatic performance leap. We explore on the performance of different versions of parallel N-body codes, where both software and hardware improvements are introduced. The use of GRAPE as a ‘force computation accelerator’ in a parallel computer architecture, can be seen as an example of a hybrid architecture, where special purpose device boards help a general purpose (multi)computer to reach a very high performance.     

智能化刺绣CAD系统中的工作流技术研究

基于智能化刺绣CAD系统向网络化和规模化方向发展的趋势,本文设计并实现了一个面向刺绣CAD的工作流框架,在该框架结构下,刺绣任务的各个执行环节被分解为粒度不同的、独立的节点任务,用户根据实际的工作环境定义这些节点任务的执行序列,工作流引擎根据用户定义控制任务的执行。本文主要介绍了面向刺绣CAD系统的工作流结构框架和其中的关键技术,包括过程定义、通信和调度。文中给出了一个基于该框架的系统实例,实际应用表明该框架是可行和有效的。     

Interval-Valued and Intuitionistic Fuzzy Mathematical Morphologies as Special Cases of \mathbb{L}-Fuzzy Mathematical Morphology

Mathematical morphology (MM) offers a wide range of tools for image processing and computer vision. MM was originally conceived for the processing of binary images and later extended to gray-scale morphology. Extensions of classical binary morphology to gray-scale morphology include approaches based on fuzzy set theory that give rise to fuzzy mathematical morphology (FMM). From a mathematical point of view, FMM relies on the fact that the class of all fuzzy sets over a certain universe forms a complete lattice. Recall that complete lattices provide for the most general framework in which MM can be conducted.