Efficient unification of quantified terms

Conventional logic-programming languages rely fundamentally on symbolic computation with quantifier-free terms. Much theoretical logic uses the richer vocabulary of quantified terms, however. In this paper we sketch some first steps in a program of research for developing data structures and algorithms to support efficient computation directly on quantified terms. We describe a simple concept of quantified term, and efficient unification algorithms for both structure-sharing and non-structure-sharing representations of those terms. The efficiency of the approach results from the techniques used to represent terms, which enable naive substitution to implement correct substitution for quantified terms. The non-structure- sharing unification algorithm described here has been prototyped by modification of a conventional logic-programming interpreter.     

Conditional Term Graph Rewriting with Indirect Sharing

For reasons of efficiency, term rewriting is usually implemented by term graph rewriting. In term rewriting, expressions are represented as terms, whereas in term graph rewriting these are represented as directed graphs. Unlike terms, graphs allow a sharing of common subexpressions. In previous work, we have shown that conditional term graph rewriting is a sound and complete implementation for a certain class of CTRSs with strict equality, provided that a minimal structure sharing scheme is used. In this paper, we will show that this is also true for two different extensions of normal CTRSs. In contrast to the previous work, however, a non-minimal structure sharing scheme can be used. That is, the amount of sharing is increased.     

Matrix-free GPU implementation of a preconditioned conjugate gradient solver for anisotropic elliptic PDEs

Many problems in geophysical and atmospheric modelling require the fast solution of elliptic partial differential equations (PDEs) in “flat” three dimensional geometries. In particular, an anisotropic elliptic PDE for the pressure correction has to be solved at every time step in the dynamical core of many numerical weather prediction (NWP) models, and equations of a very similar structure arise in global ocean models, subsurface flow simulations and gas and oil reservoir modelling. The elliptic solve is often the bottleneck of the forecast, and to meet operational requirements an algorithmically optimal method has to be used and implemented efficiently. Graphics Processing Units (GPUs) have been shown to be highly efficient (both in terms of absolute performance and power consumption) for a wide range of applications in scientific computing, and recently iterative solvers have been parallelised on these architectures. In this article we describe the GPU implementation and optimisation of a Preconditioned Conjugate Gradient (PCG) algorithm for the solution of a three dimensional anisotropic elliptic PDE for the pressure correction in NWP. Our implementation exploits the strong vertical anisotropy of the elliptic operator in the construction of a suitable preconditioner. As the algorithm is memory bound, performance can be improved significantly by reducing the amount of global memory access. We achieve this by using a matrix-free implementation which does not require explicit storage of the matrix and instead recalculates the local stencil. Global memory access can also be reduced by rewriting the PCG algorithm using loop fusion and we show that this further reduces the runtime on the GPU. We demonstrate the performance of our matrix-free GPU code by comparing it both to a sequential CPU implementation and to a matrix-explicit GPU code which uses existing CUDA libraries. The absolute performance of the algorithm for different problem sizes is quantified in terms of floating point throughput and global memory bandwidth.     

一种资源共享的快速加解密AES算法的实现

针对AES算法的特点,提出一种适用于在FPGA上实现的快速加解密资源共享的AES算法。对传统的AES加解密的s_box进行变换,使用一张查找表实现了加解密过程的资源共享,有效的节省了硬件实现面积。并对AES加解密的列混合变换进行了改进,从而达到资源共享,节省资源。本方案对轮密钥扩展,列混合变换及其逆变换等操作进行了优化处理,并在加密计算及解密计算中对S-盒,列混合变换等关键计算部件进行了复用,并且采用AES轮内流水结果和密钥并行处理,可在一块芯片上同时支持128位、192位、256位三种密钥长度的加解密算法。实验结果表明本设计相比于其他设计具有更高的性能。     

基于区块链的云计算数据共享系统研究

云计算用户通过云平台进行数据共享时面临数据不可控和敏感数据泄露的风险,传统通过数据加密上云的方式在灵活性和执行效率方面存在弊端。借助区块链的去中心化共识和不可篡改等特点,提出了基于区块链的模型和实现方案。采用私链与公链双层结构,通过元数据按规范查询和解析数据,查询结果可验证。数据在私链中存储,公链中存储私链块头,计算通过智能合约进行,只返回数据结果,数据不会泄露给第三方。数据加密采用基于身份的公钥加密算法,无需进行公钥证书认证,确保加密性能。仿真结果表明,所提方案具有可行性。通过“金融超市”这一典型的云数据共享场景作为应用实例进一步验证了系统的有效性。     

Distributed artificial bee colony approach for connected appliances in smart home energy management system

In this study, we propose a computational intelligence model for the Internet of Things applications by applying the concept of swarm intelligence (SI) into connected devices. Particularly, decentralized management of smart home energy management system (HEMS) is taken into account in which connected appliances, by sharing information with each other, make the individual decisions for optimizing electricity prices of smart HEMS. Specifically, the study includes two main issues: (a) We propose a framework for decentralized management in smart HEMS; and (b) artificial bee colony (ABC) algorithm, a typical algorithm of SI techniques, has been applied for connected appliances in terms of communication and collaboration with each other to optimize the performance of the energy management system. Moreover, regarding the implementation, we develop and simulate a connected environment of smart home systems to evaluate the proposed approach. The simulation indicates the promising results in terms of optimizing the load balancing problem comparing with the conventional approach of the decentralized management system in smart home applications.     

一种光线与三角形求交算法的硬件架构设计

为了实现实时性的光线追踪平台,提出了一种光线与三角形求交算法的硬件架构设计。首先介绍了一种光线与三角形求交的简洁算法。该算法与其它算法相比使用存储空间最少,却具有相似的性能,便于硬件实现。根据此算法,提出了相应的硬件架构,在架构设计过程中,通过折叠、资源共享、以及多线程等硬件架构设计方法来提高硬件使用率,使有限的硬件资源达到最高的性能。实验结果表明,与现有方案相比,本文硬件架构平台在速度和芯片面积两个方面都存在着较大的提高。为实时光线追踪的实现提供了依据。     

基于线程的短信实时并发算法

主要介绍一种基干线程的短信实时并发算法的设计与实现。算法建立在基干数据缓冲和循环指针技术的数据结构基础上，所设计的getString和setString方法能防止共享数据冲突，确保短信实时并行发送，并提高了短信发送效率。     

联合卡尔曼滤波及其在舰船综合导航系统中的应用

针对ＩＮＳ／ＧＰＳ／ＣＮＳ舰船综合导航系统的特点,设计了用于该系统的联合卡乐意轻滤波器,该联合卡尔曼滤波器具有全局最优性,其结构遵循信息分配原则,其算法改善了数值计算的稳定性和系统的容错性,并减少了信息舆量与计算量,理论分析及仿真结果表明,该联合滤波器能够满足系统精度和容错性的要求。     

Service Sharing for Streaming Video Multicast

In a general context, the sharing of intermediate service results among different processes is seldom feasible because parameters are often different and there may be transactional and side effects. However, in a streaming video multicast environment, a large number of users often request various similar processing on the same stream. Therefore, service sharing is feasible, with a large potential of savings in processing cost. In this paper, we study the problem of determining the service invocation orders for multiple service composition requests in a streaming video multicast with the aim of maximizing the service sharing. We first formally define the problem. After proving the problem is NP-Complete, we develop an optimal algorithm for the base case of two requests. Then for the general case, we develop two heuristic algorithms, namely, a global greedy algorithm and a local greedy algorithm using the optimal algorithm for the base case as the building block. The global greedy algorithm is designed for a system where the existing service composition requests can be recomposed with the arrival of a new request. The local greedy algorithm can be used in a system where the existing service composition requests do not change their service composition solutions with the arrival of a new request. We prove that the global greedy algorithm is a 2-approximation algorithm in terms of maximizing service sharing. Simulation results show that the greedy algorithms can save more service costs compared with a naive algorithm, and are effective compared with the cost lower bound.      

基于ECN的单播流与多播流间带宽共享算法

An ECN-based implementing bandwidth-sharing algorithm for unicast and multicast flows is presented.The algorithm uses a bandwidth allocation strategy to give an incentive to multicast flows in bandwidth allocation according to algorithm of the number of receivers, and to assure the unicast flows get their bandwidth shares fairly.Provided best-effort networks, an ECN-based congestion control algorithm is used to implement differentiated service in bandwidth allocation between unicast flows and multicast flows. In implementation, we solve the problems such asreceiver‘s number estimation, the RTT estimation and compromise between convergence and stability.The simulation results show that the algorithm can implement bandwidth sharing for TCP flows and multicast flows. Atthe same time, the algorithm not only allocates more bandwidth to multicast flows, but promises TCP flows to get their fair bandwidth share.     

基于IMOCS算法的IPD团队激励池动态分配问题研究

在IPD项目交付模式实施中，如何有效地解决各参与方的风险分担及利益分配问题一直是阻碍该模式广泛应用的最大瓶颈。通过研究合适的利益分配比例对IPD团队各参与方起到实现整体项目利益最大化的激励作用为出发点，提出激励池模型，引入时间因素、激励机制和满意度，考虑影响因素在整个项目实施过程的动态性，建立了IPD团队动态激励池分配模型，采用IMOCS算法对模型进行求解。通过算例验证了模型、算法的科学性和有效性。优化了激励池分配方案，促进了IPD模式的实施。     

Adaptive indexing for content-based search in P2P systems

One of the major challenges in Peer-to-Peer (P2P) file sharing systems is to support content-based search. Although there have been some proposals to address this challenge, they share the same weakness of using either servers or super-peers to keep global knowledge, which is required to identify importance of terms to avoid popular terms in query processing. As a result, they are not scalable and are prone to the bottleneck problem, which is caused by the high visiting load at the global knowledge maintainers. To that end, in this paper, we propose a novel adaptive indexing approach for content-based search in P2P systems, which can identify importance of terms without keeping global knowledge. Our method is based on an adaptive indexing structure that combines a Chord ring and a balanced tree. The tree is used to aggregate and classify terms adaptively, while the Chord ring is used to index terms of nodes in the tree. Specifically, at each node of the tree, the system classifies terms as either important or unimportant. Important terms, which can distinguish the node from its neighbor nodes, are indexed in the Chord ring. On the other hand, unimportant terms, which are either popular or rare terms, are aggregated to higher level nodes. Such classification enables the system to process queries on the fly without the need for global knowledge. Besides, compared to the methods that index terms separately, term aggregation reduces the indexing cost significantly. Taking advantage of the tree structure, we also develop an efficient search algorithm to tackle the bottleneck problem near the root. Finally, our extensive experiments on both benchmark and Wikipedia datasets validated the effectiveness and efficiency of the proposed method.     

ROCS: an object-oriented class-level testing system based on the Relevant Observable ContextS technique

Given an algebraic specification of a class of objects, we define a fundamental pair as two equivalent terms generated by substituting all the variables on both sides of an axiom by normal forms. For any implementation error in the class, if it can be revealed by two equivalent terms in general, it can also be revealed by a fundamental pair. Hence, we need only select test cases from the set of fundamental pairs instead of equivalent pairs in general. We highlight an algorithm for selecting a finite set of fundamental pairs as test cases. Further, by using the relevant observable contexts technique, we highlight another algorithm to determine whether the objects resulting from executing a fundamental pair are observationally equivalent. If not, it reveals an implementation error.Using these algorithms, we have constructed a system to test object-oriented programs at class-level. We describe in detail the implementation of a prototype system, including the data structure of a Data member Relevant Graph (DRG) for the class, the procedures for the construction and path traversal of the DRG, the generation and execution of relevant observable contexts on the objects under test, and the reporting of implementation errors. The implementation illustrates an innovative idea of embedding testing algorithms into an interpreter to facilitate software testing.     

Image-space visibility ordering for cell projection volume rendering of unstructured data

Projection methods for volume rendering unstructured data work by projecting, in visibility order, the polyhedral cells of the mesh onto the image plane, and incrementally compositing each cell's color and opacity into the final image. Normally, such methods require an algorithm to determine a visibility order of the cells. The meshed polyhedra visibility order (MPVO) algorithm can provide such an order for convex meshes by considering the implications of local ordering relations between cells sharing a common face. However, in nonconvex meshes, one must also consider ordering relations along viewing rays which cross empty space between cells. In order to include these relations, the algorithm described in this paper, the scanning exact meshed polyhedra visibility ordering (SXMPVO) algorithm, scan-converts the exterior faces of the mesh and saves the ray-face intersections in an A-buffer data structure which is then used for retrieving the extra ordering relations. The image which SXMPVO produces is the same as would be produced by ordering the cells exactly, even though SXMPVO does not compute an exact visibility ordering. This is because the image resolution used for computing the visibility ordering relations is the same as that which is used for the actual volume rendering and we choose our A-buffer rays at the same sample points that are used to establish a polygon's pixel coverage during hardware scan conversion. Thus, the algorithm is image-space correct. The SXMPVO algorithm has several desirable features; among them are speed, simplicity of implementation, and no extra (i.e., with respect to MPVO) preprocessing.     

Xen虚拟机Credit调度算法的实时性能分析

为了降低开销以及增加灵活性,通过虚拟化技术将多个系统运行在一个通用计算平台上已成为复杂实时嵌入式系统的趋势。Xen是近年来应用最广泛的虚拟化技术,对其默认使用的Credit调度算法进行实时性能分析,使得能够直接对运行在Xen上的实时系统进行可调度性测试,并且可以通过形式化的资源界限函数对Credit的实时性进行直观的评估。首先分析了Credit调度算法的基本实现,提出并且证明了一种配置VCPU参数的方法使得Credit的实时性得到提升,在此基础上,通过证明得到了Credit算法的基本性质,并得出其在最坏情况下为VCPU分配的资源函数曲线。     

GLSC: LSC superpixels at over 130 FPS

Superpixel has been successfully applied in various computer vision tasks, and many algorithms have been proposed to generate superpixel map. Recently, a superpixel algorithm called “superpixel segmentation using linear spectral clustering” (LSC) has been proposed, and it performs equally well or better than state-of-the art superpixel segmentation algorithms in terms of several commonly used evaluation metrics in superpixel segmentation. Although LSC is of linear complexity, its original implementation runs in few hundreds of milliseconds for images with resolution of 481 × 321 stated by the authors, which is a limitation for some real-time applications such as visual tracking which may needs, for instance, 30 FPS for standard image resolution (e.g., 480 × 320, 640 × 480, 1280 × 720 and 1920 × 1080). Instead of inventing new algorithms with lower complexity than LSC, we will explore LSC to modify its structure and make it suitable to be implemented by parallel technique. The modified LSC algorithm is implemented in CUDA and tested on several NVIDIA graphics processing unit. Our implementation of the proposed modified LSC algorithm achieves speedups of up to 80× from the original sequential implementation, and the quality, measured by two commonly used evaluation metrics, of our implementation keeps being similar to the original one. The source code will be made publicly available.     

QSIM中c过滤算法的CLP实现

c-filter是定性仿真算法QSIM中用来生成系统后继状态的主要算法，利用约束逻辑程序CLP，能够给出有关该算法定义的形式化描述，有助于提高算法的效率，文中给出了相关的定义及算法实现。     

A secure file sharing service for distributed computing environments

Distributed cryptographic file systems enable file sharing among their users and need the adoption of a key management scheme for the distribution of the cryptographic keys to authorized users according to their specific degree of trust. In this paper we describe the architecture of a basic secure file sharing facility relying on a multi-party threshold-based key-sharing scheme that can be overlaid on top of the existing stackable networked file systems, and discuss its application to the implementation of distributed cryptographic file systems. It provides flexible access control policies supporting multiple combination of roles and trust profiles. A proof of concept prototype implementation within the Linux operating system framework demonstrated its effectiveness in terms of performance and security robustness.     

Design,implementation, and evaluation of a Programmable Bandwidth Aggregation System for home networks

Bandwidth aggregation is a promising technology that can speed up access to the Internet by bandwidth sharing and multi-path communication. Current Bandwidth Aggregation Systems (BASs) deployed in public networks provide limited performance and flexibility when they are directly used in home networking environments. To reap the full performance benefits of BASs in home networks, they need to be easily and dynamically programmable by home network users. We present the design and implementation of a Programmable Bandwidth Aggregation System (PBAS) that can provide home network users improved performance when sharing bandwidth for activities that access the Internet. We also present an empirical performance evaluation of the system and we demonstrate the superior efficiency of our proposed PBAS over a traditional BAS in terms of computational overheads, loadable code, throughput performance, and programmability.