Computing Diameter in the Streaming and Sliding-Window Models

We investigate the diameter problem in the streaming and sliding-window models. We show that, for a stream of $n$ points or a sliding window of size $n$, any exact algorithm for diameter requires $\Omega(n)$ bits of space. We present a simple $\epsilon$-approximation algorithm for computing the diameter in the streaming model. Our main result is an $\epsilon$-approximation algorithm that maintains the diameter in two dimensions in the sliding-window model using $O(({1}/{\epsilon^{3/2}}) \log^{3}n(\log R+\log\log n + \log ({1}/{\epsilon})))$ bits of space, where $R$ is the maximum, over all windows, of the ratio of the diameter to the minimum non-zero distance between any two points in the window.     

流和滑动窗口模型下的直径计算

直径作为图的一个重要属性,旨在提出一种在数据流环境下计算不同大小的滑动窗口直径的算法机制.基本思想是:在一维上采取较容易实现的精确算法,主要体现在只保存现在组成了直径和未来可能成为直径的元素;高维时通过投影到低维的方法计算出滑动窗口直径的近似值,并且可以通过投影的个数控制近似解的精度.最后通过对实验数据的分析和解释得到了若干有益的结论,为进一步的研究工作奠定了基础.     

云计算安全模型与管理

安全问题是云计算应用最受关注的问题之一,云计算的资源虚拟化、分布性和动态性等特性使得云安全成为具有挑战性的课题。从云计算的结构特征分析出发,对云计算安全模型的结构和构件进行了剖析,从预防、监控、响应等3个阶段阐述了云安全管理模式,并对云数据安全策略的粘性管理机制进行分析。     

Computing Models for FPGA-Based Accelerators

Field-programmable gate arrays are widely considered as accelerators for compute-intensive applications. A critical phase of FPGA application development is finding and mapping to the appropriate computing model. FPGA computing enables models with highly flexible fine-grained parallelism and associative operations such as broadcast and collective response. Several case studies demonstrate the effectiveness of using these computing models in developing FPGA applications for molecular modeling.     

基于状态的通用自主计算模型

针对目前由于计算系统庞大造成管理工作复杂以及处理突发事件低效的问题,提出一种通用的自主计算模型.通过归纳系统的运行状态和状态变化,利用统计记分方法对状态变化进行判定和标记,实现了包含自我配置、恢复、优化和保护在内的自主计算特性,使系统可以自主地规划最能够满足系统运行需求的方案,从而将繁重的系统配置和突发事件处理任务由管理人员移交给系统自身.实验结果表明,该运用该模型能够在减轻管理负担的情况下,自主地实现系统资源的合理配置与使用.     

流式计算框架下的实时数据库分区技术研究

大数据技术的应用为互联网的发展提供了助力,但其也带来了极高的数据处理压力。它的应用使互联网数据呈现数量级增长。对于数据的后台管理与处置,是保障大数据的根本,尤其是云数据库的正式商用,增加了此过程的难度。基于此,采用流式计算框架,实现数据库的实时分区管理,有效提高数据库服务器的综合负载,从而达到更高效能、更高质量的数据处理。     

DNA计算模型及应用综述

自从Adleman博士最早利用DNA计算成功求解了7个顶点有向图的Hamilton问题以来,DNA计算[1]被引入多个研究领域,成为当今科技发展的热点之一。首先介绍DNA计算的基本原理及编码方法,其次阐述了DNA计算的主要模型,再次总结了国内外研究学者应用DNA计算解决的实际问题,最后列举了DNA计算改进的相关方向。     

一种改进的求凸多边形直径的最优算法

求凸多边形的直径是计算几何中的一个基本问题。该文对Preparata-Shamos提出的最优算法进行了改进,使距离比较中的运算的次数从44n次减少到14n次,并减少了平行边的处理时间。实验结果表明,算法的运行时间减少到原来的53%。     

Coinductive Models of Finite Computing Agents

This paper explores the role of coinductive methods in modeling finite interactive computing agents. The computational extension of computing agents from algorithms to interaction parallels the mathematical extension of set theory and algebra from inductive to coinductive models. Maximal fixed points are shown to play a role in models of observation that parallels minimal fixed points in inductive mathematics. The impact of interactive (coinductive) models on Church's thesis and the connection between incompleteness and greater expressiveness are examined. A final section shows that actual software systems are interactive rather than algorithmic. Coinductive models could become as important as inductive models for software technology as computer applications become increasingly interactive.     

网格计算体系结构应用模型的实例探讨

本文详细阐述了网络计算环境下的体系结构模型中两种主流的模型Globus和0GSA各自的设计思想，技术和特点．以及在技术发展和社会需求影响下两者的结合——GlobusToolkit3的核心功能和关键技术，探讨了网络技术未来的发展方向。     

活体生物计算模型的研究进展及展望

活体生物计算模型是基于生物体内各种生化分子以特定的形式互相协作、处理信息的能力而出现的一种新的计算模型．由于其计算组成部件是直接镶嵌在生物活体里面,并且显示具有一定的计算能力,这可以使人们深人研究生物体信息处理能力以及获得对这种能力的有效控制．该文介绍了近几年几类体内生物计算模型,用于求解NP完全问题、基因逻辑电路、分子自动机研究状况,并对未来的发展方向进行了展望．     

Sliding-Window Scalar Multiplication of Matrices and Earthquake Prediction

A probabilistic model of the point field which enables prediction of major earthquakes by extrapolating the earthquake distribution known from the region seismic history was proposed earlier by A. M. Shurygin. If the seismic region is linear, then the accuracy of prediction can be improved by dividing the region into transform zones and replacing the distribution densities and their estimates by comparison of matrices. A new method was presented and illustrated by the prediction of earthquakes in the Kamchatka and Kuril Islands.     

滑动窗口应用循环展开及其数据通路生成

滑动窗口广泛应用于图像处理、模式识别和数字信号处理中,它具有数据量大、计算密集等特点.可重构硬件为滑动窗口应用提供了一个灵活高效的实现平台.文中基于一种存储、数据调度模型及其相应的数据通路生成技术,研究循环展开对滑动窗口应用的面积、时钟频率和吞吐率的影响.实验结果表明内层循环展开相对于外层循环展开将带来更大的控制复杂度,增加了对芯片面积的需求,然而外层循环展开需要更多的存储资源保存重用数据;当片内存储模块个数增加到一定规模时,时钟频率将随着循环展开不断降低;不同维度的应用,吞吐率随循环展开提升程度不同.     

Integrating Runtime Consistency Models for Distributed Computing

How should distributed systems preserve consistency in the presence of concurrency and failures? For systems designed as assemblies of independently developed components, concurrent access to data or data structures would normally arise within individual programs, and be controlled using mutual exclusion constructs, such as semaphores and monitors. Where data is persistent and/or sets of operations are related to one another, transactions or linearizability may be more appropriate. Systems that incorporate cooperative styles of distributed execution often replicate or distribute data within groups of components. In these cases, group-oriented consistency properties must be maintained, and tools based on the virtual synchrony execution model greatly simplify the task confronting an application developer. All three styles of distributed computing are likely to be seen in future systems-often, within the same application. This leads us to propose an integrated approach that permits applications that use virtual synchrony to interact with concurrent objects that respect a linearizability constraint, and vice versa. Transactional subsystems are treated as a special case of linearizability.     

Computing Equilibria in General Equilibrium Models via Interior-point Methods

In this paper we study new computational methods to find equilibria in generalequilibrium models. We first survey the algorithms to compute equilibria thatcan be found in the literature on computational economics and we indicate howthese algorithms can be improved from the computational point of view. We alsoprovide alternative algorithms that are able to compute the equilibria in anefficient manner even for large-scale models, based on interior-point methods.We illustrate the proposed methods with some examples taken from theliterature on general equilibrium models.     

计算网格中经济模型调度算法

任务调度是网格计算系统的一个重要组成部分。随着网格计算的出现,由于缺少对网格资源的直接管理,给网格任务调度带来了新的挑战。目前的任务调度机制大多数只考虑了任务调度的服务质量(QoS),而没有考虑任务调度的费用。为此,在研究了目前已有的适应启发式任务调度算法之后,提出了在同等费用前提下,将任务调度到能够提供较高QoS的资源中去的任务调度算法。     

一种面向云计算的改进的Mapreduce模型

云计算的核心技术之一是MapReduce技术,目前国内外云计算研究机构都对MapReduce技术特别关注,并进行了基于不同体系结构上的实现研究,尤其是在对其所做的研究是基于开源hadoop平台,这些都为进一步研究提供了机遇;文章对传统MapReduce模型的处理流程进行了介绍,分析了传统处理过程中目前存在的一些问题,最后针对这些问题详细阐述了模型的改进方案,改进的方案保证了ReduceTask均衡和控制了ReduceTask大小。     

并行计算时间模型研究

本文系统地总结和探讨了共享和分布式存储环境下的并行计算时间模型。微观上，结合并行机结构特征和通信机制，揭示了延长算法运行时间的关键因素，并据此提出一些优化原则和效率评价准则，能辅助用户修改并行算法达到最优性能；宏观上，给出了基本消息传递的常用通信原语类型和部分原语操作时间经验公式，能辅助用户选择最优通信原语和问题粒度，正确预测程序的运行时间和性能。     

可满足性(SAT)问题的几种DNA计算模型

DNA计算是一种新的计算方式，其高度并行性和巨大的信息存储容量为NP-完全问题的解决提供了一种全新的方法。主要介绍了几种可满足性(SAT)问题的DNA计算模型，并在编码问题、实现方式、及算法设计等三个方面对其进行了比较。