异构多智能体系统模型检查

近几年,模型检查作为一种自动化系统验证方法,已被应用于多智能体系统的验证.由此延伸出的规约描述语言——交替时态逻辑（ATL）,也被给予了高度关注.根据智能体是否可以看到全局信息分为不完全信息和完全信息;根据智能体是否可以记录历史信息分为无记忆能力和无限记忆能力,提出了四种经典的策略类型.这些策略类型是通过ATL的语义进行刻画的.然而,在一个多智能体系统中,考虑完全信息和无限记忆能力时,所有智能体都只能选择这一种策略类型;在考虑不完全信息或无记忆能力时,仅在联合模态操作<>φ和的[[A]]φ里出现的智能体具备这种策略类型,而其他智能体还是完全信息和无限记忆能力策略类型.这可能会导致嵌套联合模态操作中智能体策略类型的不一致,且智能体策略类型取决于逻辑公式和逻辑的语义.而在实际多智能体系统中,智能体的策略类型往往取决于系统本身,且不同智能体具有不同的策略类型,即智能体策略类型是异构的,这种多智能体系统被称为异构多智能体系统.针对这些问题,本文提出了一种在语法层对智能体策略类型进行刻画的系统模型,即带类型解释系统.带类型解释系统在已有的解释系统中为每个智能体引入"策略类型"这一属性,允许不同智能体具备不同的策略类型.带类型解释系统可用于异构多智能体系统的建模.针对新提出的系统模型,对ATL语义进行了研究,设计了ATL模型检查算法,实现了相应的模型检查工具ShTMC.     

A Heterogeneous Mixed-Mode Execution Model for Massively Parallel Systems

In this paper, we consider a massively parallel system that is composed of heterogeneous processors, that is, processors with different processing power, and that combines the advantages of the SIMD and MIMD architectures. The heterogeneous mixed-mode (HeMM) execution model is composed of two main components, which operate in the well-known SIMD and MIMD paradigms. The main computing power comes from a component that is composed of a massive number of processors and operates in a data parallel manner. The other component is composed of a few (or even one) fast processors which operate in the MIMD paradigm. The operation of a small number of processors in an MIMD paradigm has been well demonstrated through actual systems. The processors in this component add flexibility to the execution of the parallel programs such that it adjusts to the changing parallelism of the program to enhance the performance. Based on this execution model we analyze the gains in performance that is obtainable by this new system. We show that substantial performance gains can be obtained by using the HeMM system.     

一种适用于异构存储系统的缓存管理算法

当前数据中心广泛采用虚拟化、混合存储等技术以满足不断增长的存储容量和性能需求,这使得存储系统异构性变得越来越普遍.异构存储系统的一个典型问题是由于设备负载和服务能力不匹配,使得存储系统中广泛使用的条带等并行访问技术难以充分发挥作用,导致性能降低.针对这一问题,提出了一种基于负载特征识别和访问性能预测的缓存分配算法(access-pattern aware and performance prediction-based cache allocation algorithm, Caper),通过缓存分配来调节不同存储设备之间的I/O负载分布,使得存储设备上的负载和其本身服务能力相匹配,从而减轻甚至消除异构存储系统中的性能瓶颈.实验结果表明,Caper算法能够有效提高异构存储系统的性能,在混合负载访问下,比Chakraborty算法平均提高了约26.1%,比Forney算法平均提高了约28.1%,比Clock算法平均提高了约30.3%,比添加预取功能的Chakraborty算法和Forney算法分别平均提高了约7.7%和17.4%.     

一种实时异构嵌入式系统的任务调度算法

异构分布式系统已被广泛应用在实时嵌入式系统中,而调度算法是在进行嵌入式系统综合时,确保系统实现性能目标的一个关键问题,这是一个NP-完全问题.现有的算法主要是启发式算法,性能还有待提高.提出了一个异构分布式系统的动态BLevel优先(dynamic BLevel first,简称DBLF)算法,算法选择就绪任务中动态BLevel值最大的任务进行调度,用插入法为任务分配处理器,遵循以下3个插入原则:满足任务先后顺序关系;任务的最早完成时间(earliest-finish-time,简称EFT)最小;在EFT相等时,优先分配到利用率较低的处理器上.与现有算法比较可以看出,DBLF算法可以有效降低调度长度.     

异构系统编程方法综述

由通用微处理器和专用加速器构成的异构并行系统比传统的同构系统显示出更高的性能和效能,目前已成为高性能计算领域的重要发展趋势。然而,编程问题成为限制异构系统发展的一大挑战,因此引起学术界和业界广泛关注。本文首先阐述了异构系统编程问题的来源;其次分析了近年来面向异构系统编程方法的研究工作,并对其进行分类;最后总结了异构系统编程方法未来的研究问题。     

Interactive Middleware Services for Heterogeneous Systems

Computing has become more invisible, widespread and ubiquitous since the inception of the Internet of Things (IoT) and Web of Things. Multiple devices that surround us meet user’s requirements everywhere. Multiple Middleware Framework (MF) designs have come into existence because of the rapid development of interactive services in Heterogeneous Systems. This resulted in the delivery of interactive services throughout Heterogeneous Environments (HE). Users are given free navigation between devices in a widespread environment and continuously interact with each other from any chosen device. Numerous interactive devices with recent interactive platforms (for example, Smart Phones, Mobile Phones, Personal Computer (PC) and Personal Digital Assistant (PDA)) are available in the market. For easy access to information and services irrespective of the device used for working and even at the drastic change of the environment, the execution of applications on a broad spectrum of computing devices is propelled by the availability of the above-mentioned platforms. Different applications that need interoperability to coordinate and correspond with each other should be facilitated. Using a standard interface and data format, HE must link various devices from various platforms together to communicate with each other. To aid the interactive services performed by a middleware framework that operates on Application Programming Interface (API) over HEs, this issue aims to endorse an Adaptable Service Application Programming Interface (ASAPI).     

OpenCL: A Parallel Programming Standard for Heterogeneous Computing Systems

We provide an overview of the key architectural features of recent microprocessor designs and describe the programming model and abstractions provided by OpenCL, a new parallel programming standard targeting these architectures.     

A Remote Procedure Call Facility for Interconnecting Heterogeneous Computer Systems

Heterogeneity in hardware and software is an inevitable consequence of experimental computer research. At the University of Washington, the Heterogeneous Computer Systems (HCS) project is a major research and development effort whose goal is to simplify the interconnection of heterogeneous computer systems.     

异构分布式实时仿真系统的容错调度算法

异构分布式实时仿真系统是一类特殊的实时系统,基于改进的SP(spare processor)容错模型(checkpoint-based spare processor,简称CSP)对其容错问题进行了研究.首先,根据仿真系统的特点提出了两个命题,这是后续工作的基础;而后,基于Markov链对仿真任务的最坏反应时间进行了分析,并提出了仿真任务的可调度性分析规则;最后,基于CSP容错模型和上述可调度分析规则提出了异构分布式实时仿真系统的容错调度算法CSP-RTFT.算法的仿真结果表明:该算法较之基于SP模型的算法SP-RTFT可获得更好的稳定性、更高的任务接收率;缺点是资源利用率比PB模型下的算法要低.     

A Novel State Transition Method for Metaheuristic-Based Scheduling in Heterogeneous Computing Systems

Much of the recent literature shows a prevalance in the use of metaheuristics in solving a variety of problems in parallel and distributed computing. This is especially ture for problems that have a combinatorial nature, such as scheduling and load balancing. Despite numerous efforts, task scheduling remains one of the most challenging problems in heterogeneous computing environments. In this paper, we propose a new state transitionscheme , called the Duplication-based State Transition (DST) method specially designed for metaheuristics that can be used for the task scheduling problem in heterogeneous computing environments. State transition in metaheuristics is a key component that takes charge of generating variants of a given state. The DST method produces a new state by first overlapping randomly generated states with the current state and then the resultant state is refined by removing ineffectual tasks. The proposed method is incorporated into three different metaheuristics: genetic algorithms (GAs), simulated annealing (SA), and artificial immune system (AISs). They are experimentally evaluated and are also compared with existing algorithms. The experimental results confirm DST's promising impact on the performance of metaheuristics.     

一种异构实时系统中任务流均衡负载的算术模型

异构环境下如何提高系统自治并发处理的能力,是分布式系统研究领域的重要课题。而异构实时系统中系统自治并发处理的能力则体现在事件驱动任务流控制的资源最优分配。本文针对已有的资源分配策略的缺陷给出了一个通用的任务流均衡负载的算术模型,除了对任务流进行量化,使其可以动态分配以外,还可以在任务流发生变化时在满足系统最大利益的前提下最优化代价函数。另外,由于这个算术模型具有通用性,因此适用于各种资源分配的启发式搜索算法。     

异构多处理器系统Cache一致性解决方案

SoC技术的发展使多个异构的处理器集成到一个芯片成为可能,这种结构已成为提高微处理器性能的重要途径.与传统的多处理器系统一样,Cache一致性问题也是片内异构多处理器系统必须首先解决的问题.本文在分析Cache一致性问题的基础上,对采用不同监听协议的多处理器的集成,以牺牲简单的硬件为代价来完成一致性协议的转化.将此方法并入多处理器芯片封装内来管理,可保证在异构多处理器系统中数据的一致性.     

供应链系统异构知识集成方法研究

供应链系统流动着大量的异构信息和知识．为了有效地利用现有知识对供应链进行优化管理和运作．供应链不仅要实现信息系统的集成而且需要实现知识集成。本文运用领域本体论(Ontology)、多Agent等技术研究供应链系统异构知识集成的方法．应用资源描述框架模式(RDFS)作为信息和知识的核心转换技术．实现异构知识的转换和集成,为供应链系统异构知识集成提供一个切实可行的技术解决方案。该方案可以保证全程信息数据和知识的正确性、及时性和完整性,进一步促使信息流为决策人员提供及时、可靠和科学的有效决策支持。     

Fault-Tolerant Dynamic Rescheduling for Heterogeneous Computing Systems

As the scale and complexity of heterogeneous computing systems grow, failures occur frequently and have an adverse effect on solving large-scale applications. Hence, fault-tolerant scheduling is an imperative step for large-scale computing systems. The existing fault-tolerant scheduling algorithms belong to static scheduling, and they allocate multiple copies of each task to several processors no matter whether processor failures affect the execution of tasks. Such active replication strategies not only waste resource but also sacrifice the makespan. What is more, they cannot guarantee the successful execution of applications. In this paper, we propose a fault-tolerant dynamic rescheduling algorithm named FTDR, which can overcome above drawbacks. FTDR keeps listening to the processor failure, and reschedules the suspended tasks once failures occur. Because FTDR reschedules the tasks that are suspended because of failures, it can tolerate an arbitrary number of failures. Randomly generated DAGs are tested in our experiments. Experimental results show that the proposed algorithm achieves good performance in terms of makespan and resource consumption compared with its direct competitors.     

A Model for Query Decomposition and Answer Construction in Heterogeneous Distributed Database Systems

The problem of retrieving information from a collection of heterogeneous distributed databases has attracted a number of solutions. However, the task of integrating established database systems is complicated not only by the differences between the database systems themselves, but also by the differences in structure and semantics of the information contained within them. The problem is exacerbated when one needs to provide access to such a system for naive end-users.This paper is concerned with a Knowledge-Based Systems approach to solving this problem for clearly bounded situations, in which both the domain and the types of query are constrained. At the user interface, dialogue is conducted in terms of concepts with which the user is familiar, and these are then mapped into appropriate database queries. To achieve this a model for query decomposition and answer construction has been used. This model is based around the development of an Intensional Structure containing information necessary for the recapture of semantic information lost in the query decomposition process and required in the answer construction process. The model has been successfully implemented in combination with an embedded KBS, within a five-layer representation model.     

异构分布式环境中Alhusaini资源映射算法的改进

为异构分布式系统中提供良好的资源映射算法,可以有效、加速部署在分布式系统中的应用程序的执行,其中Alhusaini算法是该研究领域中成功和具有影响力的算法之一。本文针对该算法的不足提出了一个两阶段动态资源映射的改进算法：第一个阶段仅仅收集数据以提供给第二阶段使用;在第二个阶段选择一组独立的任务并根据这些任务的权值将它们映射到相关资源中去。改进的算法有效地解决了Alhusaini算法存在的算法复杂度过高和在通信密集型应用中算法效率低等问题。     

Distributed Coordination in Heterogeneous Multi-Robot Systems

Coordination in multi-robot systems is a very active research field in Artificial Intelligence and Robotics, since through coordination one can achieve a more effective execution of the robots' tasks. In this paper we present an approach to distributed coordination of a multi-robot system that is based on dynamic role assignment. The approach relies on the broadcast communication of utility functions that define the capability for every robot to perform a task and on the execution of a coordination protocol for dynamic role assignment. The presented method is robust to communication failures and suitable for application in dynamic environments. In addition to experimental results showing the effectiveness of our approach, the method has been successfully implemented within the team of heterogeneous robots Azzurra Robot Team in a very dynamic hostile environment provided by the RoboCup robotic soccer competitions.     

异构系统的异步应用级Checkpointing技术

应用级checkpointing技术是同构系统上最为常用和成熟的容错技术,但在异构系统下的应用还处于起步阶段,还没有一套严谨合理的针对异构系统架构和故障模型特点的实现方案和配置方法。针对这一现况,本文基于CUDA异构系统的体系结构和编程模型,对CUDA程序在CPU和GPU上的执行模式进行分析,提出了一种面向异构系统应用级checkpointing技术的异步执行机制,并基于这一机制对异构系统的检查点优化设置问题进行讨论,设计了一套优化方案。最后在CUDA平台下通过三个实例验证了这一技术的可行性和实用性,并进行了性能评估。结果表明,这种面向CPU-GPU的异构系统的应用级checkpointing异步执行机制是行之有效的,相比CPU-GPU同步执行的checkpointing机制在设置上更为灵活,优化空间更大。而本文基于这一机制所提出的检查点优化设置方法也有效地减少了check-pointing的开销,从而获得了更高的容错性能。