A Self Distributing Virtual Machine for Adaptive Multicore Environments

The use of parallel systems is no longer limited to dedicated clusters as multicore chips are more and more appearing in embedded applications. To meet power, performance and cost targets these systems need to be adaptive. The reconfiguration features of recent FPGAs make new approaches for this type of parallel computing possible: Dynamic reconfiguration at runtime offers an important step to adaptive behavior of systems-on-chip (SoCs). This article analyzes the challenges of such an adaptive SoC. It is shown that many of the requirements for an adaptive FPGA-realization are met by the SDVM, the scalable dataflow-driven virtual machine which has been successfully implemented and tested on a cluster of workstations. The SDVM has evolved to a virtualization layer for multicore-FPGAs, now called SDVM ^R . This virtualization layer allows a transparent runtime-reconfiguration of the underlying hardware to adapt to the changing system environment. Results for a basic application for both systems are presented.     

优先队列的并行插入和删除

优先队列广泛地使用在许多并行算法中(例如,多处理机调度和某些组合优化算法)。在这些算法中,共享优先队列的存取冲突限制了加速比的提高。本文提出一种链表优先队列的并行插入和删除方法,具有较小并行开销和较大的并行度,并且保证和串行存取算法的优先顺序完全一致,即删除操作返回已经插入和正在插入的所有元素中的最佳元素。同时,我们还介绍了目前性能最好的堆的并行插入和删除算法,并对准和链表结构并行插入和删除算法的性能和适用范围进行了比较,进一步提出了散列结构的优先队列。在ENCORE Multimax520多处理机上的实验结果验证了我们的理论分析结果:使用链表结构的并行分枝限界算法性能上可获得很大提高。     

嵌入式多核系统的可调优先级自旋锁

传统自旋锁具有无序竞争的特点,本文对自旋锁机制进行了研究,通过引入优先级和等待次数阈值提出可调优先级自旋锁,保证高优先级任务尽可能多地获得锁,低优先级任务经过一段等待时间后调整优先级、增加获取锁的机会,实现了可调优先级自旋锁并通过实验进行了验证.测试结果表明,可调优先级自旋锁既能够减少传统自旋锁的时间开销,又能保证高优先级处理器核锁申请较快得到响应,验证了可调优先级自旋锁在多核系统中是可用的.     

分布式主动实时数据库基于多优先级队列的优先级分派

事务的分布性和事务触发的不可预测性使得分布式主动实时数据库系统中的事务调度变得较为复杂．该文给出了立即和推迟两种模式下执行的被触发事务的截止期确定方法和事务紧急度计算方法,并结合事务的应用语又提出了一种基于多优先级队列的优先级分派策略,有利于主动事务和被触发事务的顺利提交．     

基于业务的多优先级队列区别服务方案

缓冲队列的管理和调度是有关互连网服务质量的重要话题。鉴于时延是QoS(QualityofService)的一个重要指标,论文提出并详细讨论了一种基于EDF(EarliestDeadlineFirst)的优先级队列PQBEDF(priorityqueuebasedonEDF),针对不同的业务类型采用各自的PQBEDF,这样可以使得“区别”更加合理,且便于各队列采用不同的控制策略。配以异步时分机制,可以对每一类业务的信元保证一个最小的服务速率。     

A Speculative Parallel DFA Membership Test for Multicore,SIMD and Cloud Computing Environments

We present techniques to parallelize membership tests for Deterministic Finite Automata (DFAs). Our method searches arbitrary regular expressions by matching multiple bytes in parallel using speculation. We partition the input string into chunks, match chunks in parallel, and combine the matching results. Our parallel matching algorithm exploits structural DFA properties to minimize the speculative overhead. Unlike previous approaches, our speculation is failure-free, i.e., (1) sequential semantics are maintained, and (2) speed-downs are avoided altogether. On architectures with a SIMD gather-operation for indexed memory loads, our matching operation is fully vectorized. The proposed load-balancing scheme uses an off-line profiling step to determine the matching capacity of each participating processor. Based on matching capacities, DFA matches are load-balanced on inhomogeneous parallel architectures such as cloud computing environments. We evaluated our speculative DFA membership test for a representative set of benchmarks from the Perl-compatible Regular Expression (PCRE) library and the PROSITE protein database. Evaluation was conducted on a 4 CPU (40 cores) shared-memory node of the Intel Academic Program Manycore Testing Lab (Intel MTL), on the Intel AVX2 SDE simulator for 8-way fully vectorized SIMD execution, and on a 20-node (288 cores) cluster on the Amazon EC2 computing cloud. Obtained speedups are on the order of $\mathcal O \left( 1+\frac{|P|-1}{|Q|\cdot \gamma }\right) $ , where $|P|$ denotes the number of processors or SIMD units, $|Q|$ denotes the number of DFA states, and $0<\gamma \le 1$ represents a statically computed DFA property. For all observed cases, we found that $0.02<\gamma <0.47$ . Actual speedups range from 2.3 $\times $ to 38.8 $\times $ for up to 512 DFA states for PCRE, and between 1.3 $\times $ and 19.9 $\times $ for up to 1,288 DFA states for PROSITE on a 40-core MTL node. Speedups on the EC2 computing cloud range from 5.0 $\times $ to 65.8 $\times $ for PCRE, and from 5.0 $\times $ to 138.5 $\times $ for PROSITE. Speedups of our C-based DFA matcher over the Perl-based ScanProsite scan tool range from 559.3 $\times $ to 15079.7 $\times $ on a 40-core MTL node. We show the scalability of our approach for input-sizes of up to 10 GB.     

一种基于流量预测的多优先级队列缓存管理算法

在引入优先级因素的流量预测模型基础上,提出了一种多优先级队列的缓存管理算法,该算法通过固定时刻的缓存预分配,结合时划间隔中的缓存竞争,使缓存的分配更加合理而有预见性,仿真实输表明它能够明最降低高优先级数据包的丢包率,同时兼顾低优先级数据包的转发,并且不产生额外的延迟,表明该算法有很好的应用价值。     

Coordinated Services Provision in Peer-to-Peer Environments

In recent years, inspired by the emerging Web services standard and peer-to-peer technology, a new federated service providing (FSP) system paradigm has attracted increasing research interests. Many existing systems have either explicitly or implicitly followed this paradigm. Instead of exchanging files, peers in FSP systems share their computation resources in order to offer domain-specific services. In this paper, we focused on the coordination problem of how to self-organize the service group structures in response to the varying service demand. We presented our solution in the form of a coordination mechanism, which includes a labor-market model, a recruiting protocol, and a policy-driven decision architecture. Peers make their service providing decisions based on their local policies, which can be added, removed, or modified by users. A general methodology is introduced in this paper to facilitate policy design. Specifically, a heuristic inspired by the extremal optimization technique is utilized to handle potential inconsistencies among policies. A stimulus-response mechanism was further applied to make the decision process adjustable. Experiments under five application scenarios verified our ideas and demonstrated the effectiveness of our coordination mechanism.     

Revisiting the Sequential Programming Model for the Multicore Era

Automatic parallelization has thus far not been successful at extracting scalable parallelism from general programs. An aggressive automatic thread extraction framework, coupled with natural extensions to the sequential programming model that allow for a range of legal outcomes rather than forcing programmers to define a single legal program outcome, will let programmers achieve the performance of parallel programming via the simpler sequential model.     

一个基于证券市场的计算网格环境下的资源分配模型

计算网格(Computational Grid)下对资源进行有效管理和调度是十分具有挑战性的问题.论文中提出了一个证券市场模型来实现计算网格环境下的资源分配.在此模式中,资源作为一种证券商品被自由买卖,用户可以方便快捷地实现对系统资源的存取,模拟实验表明证券市场模型是实现计算网格环境下资源分配的一个有效手段.     

Learning to Improve Coordinated Actions in Cooperative Distributed Problem-Solving Environments

Coordination is an essential technique in cooperative, distributed multiagent systems. However, sophisticated coordination strategies are not always cost-effective in all problem-solving situations. This paper presents a learning method to identify what information will improve coordination in specific problem-solving situations. Learning is accomplished by recording and analyzing traces of inferences after problem solving. The analysis identifies situations where inappropriate coordination strategies caused redundant activities, or the lack of timely execution of important activities, thus degrading system performance. To remedy this problem, situation-specific control rules are created which acquire additional nonlocal information about activities in the agent networks and then select another plan or another scheduling strategy. Examples from a real distributed problem-solving application involving diagnosis of a local area network are described.     

实时系统中任务优先级的综合决策模型

实时系统设计中,如何准确而合理地确定每一个任务的优先级是能否保证系统实时性要求的关键问题之一。本文基于模糊集合理论提出了一种任务优先级的综合决策模型,并通过实例进行了说明。     

DTM:一种面向网络计算的动态信任管理模型

在开放的互联网中,信任关系的建立是实现跨自治域资源共享与协同的前提.然而,网络计算环境的分布自治特性,使得各类复杂系统中应用不同的信任管理机制,容易导致信任定义的不一致问题,特别是很多系统为支持多域协作,直接假设实体间信任具有传递特性,而在模型中缺乏该性质成立的条件;此外,网络计算环境中的动态演化特性,使得驱动实体间协作的信任关系随需而变,而现有信任管理模型仅仅关注于系统功能结构,缺乏对这种动态性的描述.文中提出了一种动态信任管理模型DTM,基于信念公式形式化定义了主体间的信任公式,并将信任的传递特性(信任链)解释为模型的一条性质.在该模型中,针对信任关系的动态特征,以时间为参量刻画主体公式集,以事件为触发条件刻画主体间信任的变化,并基于正则事件序列描述信任管理的资源授权过程,可刻画主体间信任的建立过程.最终,设计、实现了一个信任管理系统CROWN-TM,并进行了初步实验分析.     

A Loosely Coupled Distributed System for Reliably Storing Data

An algorithm for storing information redundantly on the nodes of a broadcast network is proposed. A voting technique is used to increase reliability. Since multiple votes are cast only when copies of a data item disagree, the algorithm has the property that communication overhead is minimal. In addition, nodes storing erroneous copies are automatically resynchronized. A Markov analysis is performed which relates parameters of the algorithm to the mean time to failure.     

Relational Model for Robotic Semantic Navigation in Indoor Environments

The emergence of service robots in our environment raises the need to find systems that help the robots in the task of managing the information from human environments. A semantic model of the environment provides the robot with a representation closer to the human perception, and it improves its human-robot communication system. In addition, a semantic model will improve the capabilities of the robot to carry out high level navigation tasks. This paper presents a semantic relational model that includes conceptual and physical representation of objects and places, utilities of the objects, and semantic relation among objects and places. This model allows the robot to manage the environment and to make queries about the environment in order to do plans for navigation tasks. In addition, this model has several advantages such as conceptual simplicity and flexibility of adaptation to different environments. To test the performance of the proposed semantic model, the output for the semantic inference system is associate to the geometric and topological information of objects and places in order to do the navigation tasks.     

构造移动P2P环境下的分布式信任模型

基于固定网络的信任模型缺乏对网络高度动态性的考虑,不能直接应用于移动P2P网络。本文利用节点的报文转发能力,提出了一种移动P2P环境下的分布式信任模型MobTrust。该模型通过分布式存储机制,将节点转发的评价数据备份于K桶中,扩充了评价数据的存储范围。同时,鉴于移动设备有限的计算能力,设计双反馈机制提高评价数据的可靠性,然后以轻量级的方式计算信任度。仿真结果表明,MobTrust能有效降低系统开销,并拥有较高的评价数据利用率和交易成功率。     

A Trust/Honesty Model with Adaptive Strategy for Multiagent Semi-Competitive Environments

In multiagent semi-competitive environments, competitions and cooperations can both exist. As agents compete with each other, they have incentives to lie. Sometimes, agents can increase their utilities by cooperating with each other, then they have incentives to tell the truth. Therefore, being a receiver, an agent needs to decide whether or not to trust the received message(s). To help agents make this decision, some of the existing models make use of trust or reputation only, which means agents choose to believe (or cooperate with) the trustworthy senders or senders with high reputation. However, a trustworthy agent may only bring little benefit. Another way to make the decision is to use expected utility. However, agents who only believe messages with high expected utilities can be cheated easily. To solve the problems, this paper introduces the Trust Model, which makes use of trust, expected utility, and also agents’ attitudes towards risk to make decisions. On the other hand, being a sender, an agent needs to decide whether or not to be honest. To help agents make this decision, this paper introduces the Honesty Model, which is symmetric to the Trust Model. In addition, we introduce an adaptive strategy to the Trust/Honesty Model, which enables agents to learn from and adapt to the environment. Simulations show that agents with the Adaptive Trust/Honesty Model perform much better than agents which only use trust or expected utility to make the decision