Conflict-Free Evacuation Route Planning

GeoInformatica - Given a transportation network, a population, and a set of destinations, the goal of Conflict-Free Evacuation Route Planning (CF-ERP) is to produce routes that minimize the...     

An “Art Gallery Theorem” for pyramids

Every orthogonal polygon can be illuminated by ⌊n/4⌋ lights situated in the vertices of the polygon. In this paper we improve this bound for pyramids, showing that ⌈n/6⌉ guards situated in vertices are always sufficient and sometimes necessary for watching any pyramid of n vertices. Our proof leads to a linear time algorithm for placing those guards.     

Strong Conflict-Free Coloring for Intervals

We consider the \(k\) -strong conflict-free ( \(k\) -SCF) coloring of a set of points on a line with respect to a family of intervals: Each point on the line must be assigned a color so that the coloring is conflict-free in the following sense: in every interval \(I\) of the family there are at least \(k\) colors each appearing exactly once in \(I\) . We first present a polynomial-time approximation algorithm for the general problem; the algorithm has approximation ratio 2 when \(k=1\) and \(5-\frac{2}{k}\) when \(k\ge 2\) . In the special case of a family that contains all possible intervals on the given set of points, we show that a 2-approximation algorithm exists, for any \(k \ge 1\) . We also provide, in case \(k=O({{\mathrm{polylog}}}(n))\) , a quasipolynomial time algorithm to decide the existence of a \(k\) -SCF coloring that uses at most \(q\) colors.     

A nearly optimal algorithm for covering the interior of an Art Gallery

The problem of locating visual sensors can be often modelled as 2D Art Gallery problems. In particular, tasks such as surveillance require observing the interior of a polygonal environment (interior covering, IC), while for inspection or image based rendering observing the boundary (edge covering, EC) is sufficient. Both problems are NP-hard, and no technique is known for transforming one problem into the other. Recently, an incremental algorithm for EC has been proposed, and its near-optimality has been demonstrated experimentally. In this paper we show that, with some modification, the algorithm is nearly optimal also for IC. The algorithm has been implemented and tested over several hundreds of random polygons with and without holes. The cardinality of the solutions provided is very near to, or coincident with, a polygon specific lower bound, and then suboptimal or optimal. In addition, our algorithm has been compared, for all the test polygons, with recent heuristic sensor location algorithms. In all cases, the cardinality of the set of guards provided by our algorithm was less than or equal to that of the set computed by the other algorithms. An enhanced version of the algorithm, also taking into account range and incidence constraints, has also been implemented.     

基于输入端无冲突算法的面向输出排队的交换结构

该文提出了一种全新的面向输出排队的交换结构,该结构将信元存储于输入端,而信元的调度请求面向输出端排队.利用输入端无冲突调度算法,可以使结构对存储器带宽的需求和输入排队交换机一致.该文设计的调度矩阵使算法复杂度和端口规模呈线性关系,且每一步只需要一次按位"与"操作.文章同时证明了结构要达到稳定的充分条件是使用2倍传输加速比.仿真实验表明,对于均匀流量,该结构时延性能和主流交换结构相似,且抖动性能远优于主流交换结构,而在2倍传输加速比时,其时延性能和OQ完全相同;对于非均匀流量,该结构吞吐率性能优于主流交换结构,且在使用1.14倍传输加速比时,其吞吐率性能和OQ相同.     

无冲突Petri网的结构活性判定研究

结构活性作为Petri网的重要结构性质,在Petri网活性判定领域具有较高的研究价值.从Petri网有向回路对结构活性的影响入手,分析与判定无冲突Petri网的结构活性,讨论库所元素及其后置变迁之间是否存在有向回路对Petri网结构活性的影响,研究该类Petri网结构活性判定方法的相关条件与结论,得到无冲突Petri网...     

一种支持向量无冲突访问的质数存储器系统设计方案

ＳＩＭＤ体系结构步入低谷的原因之一是还滑有一个很好的存储器无冲突访问算法。从访问模式的覆盖面来，无疑质数模式最理想的。早在七十年代末的ＢＳＰ并行计算机上就采用了质数存储器的，量由于其它一些问题没有解决，因而带来一些弊端，包括采用交叉开关的实现技术，旨央储空间的记存方式，荐储个数与处理器个数不同等。本文采用了新的实现方式，因而不再存在上述三个问题。     

Analysis of Randomized Protocols for Conflict-Free Distributed Access

We study the following distributed access problem which arises naturally in many settings: given a set of n data items shared among n nodes in a distributed network, all nodes want to access all (or a subset of) the items residing on different nodes in a conflict-free manner. In addition, items may move from one node to the other during access. Our goal is to design distributed protocols so that all nodes access all the desired items as quickly as possible, while at the same time not overloading the storage space of any one node. Using centralized coordination among the nodes it is easy to design an optimal scheme in which all nodes can access all the items in n−1 steps storing only one item at any time. We show that a simple randomized distributed protocol performs almost as well as the optimal (centralized) scheme but with no coordination overhead. Our protocol takes O(n) time with high probability to access all n items which is asymptotically as good as the optimal centralized scheme. The protocol guarantees that the maximum load (the maximum number of items stored in any node) at any time is at most O(log n/log log n) with high probability which is only slightly larger compared to the Ω(1) load of the optimal scheme. Our analysis involves a stochastic analysis of a “balls into bins” problem in a dynamic setting where balls (data items) move into bins (nodes) on request and we study the time and load requirements to move all the balls to the requested bins. A short version of this paper appeared in the Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), 2005.     

PaSeM:并行无冲突的网络流量会话管理

网络会话管理是网络流量监控、状态防火墙、入侵防御、网络地址转换、负载分流等网络在线业务的关键共性技术,对于准确、快速、灵活地跟踪、分析和处置网络流量中的协议交互过程、端对端行为和通信内容起着基础性支撑作用.近年来,随着P2P(Peer-to-Peer)、VoIP(Voice over IP)、网络流媒体等新兴应用的快速发展,网络流量和会话呈现爆炸式增长,如何实现高效的会话管理成为人们面临的一项挑战.文中提出了一种适用于并行执行环境的网络会话管理方案PaSeM(Parallel Session Management),采用基于散列表的无锁会话表设计和多种并行策略,讨论并解决了在高速网络环境下面临的各种并行冲突问题,给出了会话表查询和动态管理的高效并行算法,实现了对报文和会话的并行无冲突的高效处理.基于G/G2/n1排队模型和空竭服务多重休假M/G+D/1排队模型对PaSeM的性能进行了理论分析,对于稳态下并行处理单元(PE)数量、任务队列长度、存储开销与报文到达速率、会话到达速率之间的关系以及其它关键参数应满足的条件给出了定量计算方法.最后,采用基于IXP2400网络处理器的硬件平台进行了原型开发和实验.实验结果表明,PaSeM对于会话管理和报文处理具有较好的并行加速效果,理论计算值与实验值能较好地吻合,报文处理的并行效率均值接近1,当会话管理单元个数为4时,会话处理并行效率为65.4%(亦即加速比为2.62),当会话管理单元个数为8时,会话处理并行效率仍然达到了48.3%(加速比为3.86),能够满足当前高速网络环境流最处理的性能要求;在最大吞吐量负载下队列长度及其变化幅度都处于合理范围,会话表垃圾比率维持在较低的水平上(实验结果为小于9%),与已有的工作相比为优.     

嵌入式数据库系统中无冲突并发控制协议CCCP

嵌入式实时数据库系统不仅需要较高的成功率．而且往往是在无人工干预的情况下运行,要求事务具备自我调节能力和较强的适应能力．事务必须支持功能替代性,在并发控制策略CCCP中,替代成为并发控制的主体．对于每个实时事务,一个最适合当前运行环境的替代以无冲突的方式调度执行．CCCP基于替代的优先级,对替代进行相容性分析,保护就绪事务,并且有一种开销较低的实现算法．性能分析证明CCCP有利于优选替代,从而有利于提高系统的成功率,适用于嵌入式实时数据库系统．     

Chromatic binary search trees

We propose a new rebalancing method for binary search trees that allows rebalancing and updating to be uncoupled. In this way we obtain fast updates and, whenever the search tree is accessed by multiple users, a high degree of concurrency. The trees we use are obtained by relaxing the balance conditions of red-black trees. The relaxed red-black trees, called chromatic trees, contain information of possible imbalance such that the rebalancing can be done gradually as a shadow process, or it can be performed separately when no urgent operations are present. Received December 5, 1991 / May 2, 1995     

Chromatic binary search trees

We propose a new rebalancing method for binary search trees that allows rebalancing and updating to be uncoupled. In this way we obtain fast updates and, whenever the search tree is accessed by multiple users, a high degree of concurrency. The trees we use are obtained by relaxing the balance conditions ofred-black trees. The relaxed red-black trees, calledchromatic trees, contain information of possible imbalance such that the rebalancing can be done gradually as a shadow process, or it can be performed separately when no urgent operations are present.     

面向多兴趣区域图像处理应用的高效无冲突并行访问存储模型

针对不规则数据访问模式图像处理应用提出了一种通用的高效无冲突并行访问存储模型.在主存储器与处理器之间构建了一种多体存储结构,并将大部分的不规则数据访问模式归类为对图像中多个局部矩形兴趣区域内的任意位置固定大小矩形数据块的无冲突并行访问.为了提高访问效率,只将兴趣区域内的数据缓存在多体存储器中,且不同兴趣区域的重叠数据可以重用.多体存储器的寻址机制是基于提出的地址映射表结构进行动态寻址,而不是采用传统的固定寻址函数,既保证了对任意数据读写操作的编址一致性,又提高了数据重用性.每处理一个新兴趣区域就对地址映射表内容进行一次更新,提出的双表结构与数据块动态调度机制保证了更新过程与计算过程的并行执行.基于提出的存储模型构建了硬件体系结构,并在FPGA上实现,测试结果表明,与直接访问主存储器相比在访存速度上提高了几倍到上百倍.     

The National Portrait Gallery CD-ROM

Courseware Reviews

The National Portrait Gallery CD-ROM