基于QNX的PC104总线设备驱动模块的开发

QNX作为最优秀的嵌入式实时操作系统之一,已被应用于诸如医疗仪器、电网通信以及航空航天等任务关键型领域。在掌握QNX微内核结构和消息传递机制的基础上,论述了QNX下资源管理器的原理以及资源管理器与设备驱动程序的关系,具体分析了PC104总线设备驱动程序编写规范和步骤。实现了QNX下应用程序对硬件访问的无关性,大大增强了系统安全性以及移植性等。     

用于辩证分析的多方对话协议

在基于辩论的多agent系统研究中,agent之间的对话博弈一般是双方的,然而现实中的辩论却常常涉及到多方参与者,如何实现多agent系统的多方对话博弈是当前的研究热点之一。用于多方论据博弈的辩证分析模型(DAM-MAG)是一种借鉴中国武术擂台比武思想,将多方对话博弈转化为若干个双方对话博弈的理论模型。DAM-MAG的难点在于多方对话博弈协议的设计和实现。为此,基于该理论模型提出了一种多方对话博弈协议。该协议提供了通过双方对话博弈来解决多方对话博弈问题的方法,为解决多agent系统的多方对话博弈提供了新的途径。     

Self-stabilizing minimum degree spanning tree within one from the optimal degree

We propose a self-stabilizing algorithm for constructing a Minimum Degree Spanning Tree (MDST) in undirected networks. Starting from an arbitrary state, our algorithm is guaranteed to converge to a legitimate state describing a spanning tree whose maximum node degree is at most Δ^∗+1, where Δ^∗ is the minimum possible maximum degree of a spanning tree of the network.To the best of our knowledge, our algorithm is the first self-stabilizing solution for the construction of a minimum degree spanning tree in undirected graphs. The algorithm uses only local communications (nodes interact only with the neighbors at one hop distance). Moreover, the algorithm is designed to work in any asynchronous message passing network with reliable FIFO channels. Additionally, we use a fine grained atomicity model (i.e., the send/receive atomicity). The time complexity of our solution is O(mn²logn) where m is the number of edges and n is the number of nodes. The memory complexity is O(δlogn) in the send-receive atomicity model (δ is the maximal degree of the network).     

The logic of message-passing

Message-passing is a key ingredient of concurrent programming. The purpose of this paper is to describe the equivalence between the proof theory, the categorical semantics, and term calculus of message-passing. In order to achieve this we introduce the categorical notion of a linear actegory and the related polycategorical notion of a poly-actegory. Not surprisingly the notation used for the term calculus borrows heavily from the (synchronous) π-calculus. The cut-elimination procedure for the system provides an operational semantics.     

并行计算通信库测试方法研究及实践

并行计算通信库的测试在并行计算系统中起着重要的作用.对通信库的测试一般都是通过设计一些测试程序对库的各个或几个部分分别进行单独隔离测试.但是有许多库中的错误用这种隔离测试方法测不出来,只有当库的多个部分以某种复杂的、有机的方式组合运行时才会暴露出来.而这种复杂的、有机的组合方式,从设计库的测试角度看很难形成.提出两种新的测试方法,根据通信库结构的分层特性,利用可移植的上层库的测试程序来测试下层库.上层库的测试程序也可看做是下层库的应用程序,但与一般的下层库应用程序不同,它几乎覆盖了下层库的各个部分,且有机地将它们组合起来,运行时形成某种复杂的形态,而仅用下层库的测试程序往往达不到这种形态.这样,逃过下层库测试程序的错误就可能暴露出来.     

Robust gossiping with an application to consensus

We study deterministic gossiping in synchronous systems with dynamic crash failures. Each processor is initialized with an input value called rumor. In the standard gossip problem, the goal of every processor is to learn all the rumors. When processors may crash, then this goal needs to be revised, since it is possible, at a point in an execution, that certain rumors are known only to processors that have already crashed. We define gossiping to be completed, for a system with crashes, when every processor knows either the rumor of processor v or that v has already crashed, for any processor v. We design gossiping algorithms that are efficient with respect to both time and communication. Let t<n be the number of failures, where n is the number of processors. If , then one of our algorithms completes gossiping in O(log²t) time and with O(npolylogn) messages. We develop an algorithm that performs gossiping with O(n^1.77) messages and in O(log²n) time, in any execution in which at least one processor remains non-faulty. We show a trade-off between time and communication in gossiping algorithms: if the number of messages is at most O(npolylogn), then the time has to be at least . By way of application, we show that if n−t=Ω(n), then consensus can be solved in O(t) time and with O(nlog²t) messages.     

SIFT特征分布式并行提取算法

SIFT(scale invariant feature transform)特征在物体检测和识别、图像配准与融合、纹理识别、场景分类、人脸检测、图像检索、三维重建、数字水印、影像追踪等领域具有广泛应用,但存在计算量大、消耗时间长的缺点.基于消息传递机制,采用数据并行策略,提出了在PC机群或COW(cluster ofworkstation)上提取图像SIFT特征的分布式并行算法(DP-SIFT算法):根据特征空间-高斯尺度金字塔的特点提出了高度宽度受限的数据块划分算法,设计了数据分配和特征调整方法;研究了数据块划分和数据发送方法对通信时间的影响,提出了基于消息传递机制的并行图像处理中数据块划分与数据发送方式协同对通信优化的策略;实验结果表明DP-SIFT算法具有良好的加速性能和较高的处理器利用效率,千兆以太网连接32核的PC机群系统图像规模为1024×768时,加速比和处理器效率分别可以达到20和0.6;图像规模为2048×1536时可达18和0.56.     

西方权威“自涉与悖论”论点批判——禁止“矛盾”，殃及“自涉”

对西方维特根斯坦、哥德尔、罗素、哈克、冯·赖特、克里普克、马丁、塔斯基、本奇、森斯伯里、皮亚斯、芬斯勒、鲍茨瓦、莱辛巴哈等权威有关“矛盾、自涉、意义、悖论”等问题的观点进行了批判。讨论了有关“自涉”与“悖论”的最新重点。