服务组合中基于DTMC的可靠性和性能分析

Web服务组合可以通过整合网络上现有的多种异构服务从而形成新的服务。针对服务组合中的可靠性和相关性能评估问题,提出了一种基于离散时间马尔可夫链DTMC(Discrete Time Markov Chain)的评估方法。从不同运行场景的角度,利用DTMC相关性质和公式综合估算了服务组合的可靠性和其他性能,并针对具体服务组合的瓶颈进行了分析,提出了改进措施。与现有的服务组合可靠性和性能分析方法相比,本方法对服务组合中结构复杂和运行场景多样化的特点具有更好的适应性,更全面、准确地评估了服务组合的可靠性和相关性能。实验表明,本方法具有良好的分析效果和指导改进的能力。     

CTMDP基于随机平稳策略的仿真优化算法

基于Markov性能势理论和神经元动态规划(NDP)方法,研究一类连续时间Markov决策过程(MDP)在随机平稳策略下的仿真优化问题,给出的算法是把一个连续时间过程转换成其一致化Markov链,然后通过其单个样本轨道来估计平均代价性能指标关于策略参数的梯度,以寻找次优策略,该方法适合于解决大状态空间系统的性能优化问题.并给出了一个受控Markov过程的数值实例.     

Markov控制过程基于单个样本轨道的在线优化算法

在Markov性能势理论基础上, 研究了Markov控制过程的性能优化算法. 不同于传统的基于计算的方法, 文中的算法是根据单个样本轨道的仿真来估计性能指标关于策略参数的梯度, 以寻找最优 (或次优 )随机平稳策略. 由于可根据不同实际系统的特征来选择适当的算法参数, 因此它能满足不同实际工程系统在线优化的需要. 最后简要分析了这些算法在一个无限长的样本轨道上以概率 1的收敛性, 并给出了一个三 状态受控Markov过程的数值实例.     

随机平稳策略下半Markov决策过程的仿真优化算法

基于性能势理论和等价Markov过程方法,研究了一类半Markov决策过程(SMDP)在参数化随机平稳策略下的仿真优化算法,并简要分析了算法的收敛性．通过SMDP的等价Markov过程,定义了一个一致化Markov链,然后根据该一致化Markov链的单个样本轨道来估计SMDP的平均代价性能指标关于策略参数的梯度,以寻找最优(或次优)策略．文中给出的算法是利用神经元网络来逼近参数化随机平稳策略,以节省计算机内存,避免了“维数灾”问题,适合于解决大状态空间系统的性能优化问题．最后给出了一个仿真实例来说明算法的应用．     

可数半Markov决策过程折扣代价性能优化

讨论一类可数半Markov决策过程（CSMDP）在折扣代价准则下的性能优化问题,运用等价Markov过程方法,定义了折Poisson方程,并由该方程定义了α-势,基于α-势,导出了由最优平稳策略所满足的最优性方程．较为详细地讨论了最优性方程解的存在性问题,并给出了其解存在的一些充分条件。     

闭排队网络当性能函数与参数相关时的性能灵敏度分析

借助于无穷小矩阵摄动方法, 讨论了一类Markov过程, 其稳态性能关于参数摄动的灵敏度分析问题. 然后研究了闭排队网络的稳态性能灵敏度分析问题, 并在参数相关性能函数的情况下, 给出了网络的几种稳态性能的灵敏度公式. 这些公式表明稳态性能灵敏度很容易通过网络势能进行计算.     

基于观测的POMDP 优化算法及其仿真

在分析马尔可夫决策过程（Markov Decision Process, MDP）性能灵敏度的基础上,讨论了部分可观 测马尔可夫决策过程（Partially Observable Markov Decision Process, POMDP）的性能优化问题．给出了POMDP 性能灵敏度分析公式,并以此为基础提出了两种基于观测的POMDP 优化算法：策略梯度优化算法和策略迭 代优化算法．最后以准许控制问题为仿真实例,验证了这两个算法的有效性．     

基于DTMC的工业串行协议状态检测算法

针对现有工业信息安全研究主要集中在工业以太网方面,缺少对串行链路协议防护的研究等问题,提出一种基于离散时间马尔可夫链(Discrete Time Markov Chain,DTMC)的工业串行协议状态检测算法.该算法利用工业控制系统(Industrial Control System,ICS)行为有限和状态有限的特征,...     

连续时间Markov决策过程在呼叫接入控制中的应用

应用Markov决策过程与性能势相结合的方法,给出了呼叫接入控制的策略优化算法.所得到的最优策略是状态相关的策略,与基于节点已占用带宽决定行动的策略相比,状态相关策略具有更好的性能值,而且该算法具有很快的收敛速度.     

闭排队网络基于并行仿真的灵敏度估计和优化算法

基于Markov性能势理论，对一类闭排队网络的灵敏度估计和优化，建立了一种行之有效的并行仿真算法。采用公共随机数，使所有的处理器使用相同的样本轨道，以减少各个处理器之间的通讯时间。在一台SPMD并行计算机上的仿真实例表明，该并行仿真算法对于闭排队网络的优化能显著地提高运算速度。     

An analytic framework for performance modeling of software transactional memory

Analytic models based on discrete-time Markov chains (DTMC) are proposed to assess the algorithmic performance of Software Transactional Memory (TM) systems. Base STM variants are compared: optimistic STM with inplace memory updates and write buffering and pessimistic STM. Starting from an absorbing DTMC, closed-form analytic expressions are developed, which are quickly solved iteratively to determine key parameters of the considered STM systems, like the mean number of transaction restarts and the mean transaction length. Since the models reflect complex transactional behavior in terms of read/write locking, data consistency checks and conflict management independent of implementation details, they highlight the algorithmic performance advantages of one system over the other, which – due to their at times small differences – are often blurred by implementation of STM systems and even difficult to discern with statistically significant discrete-event simulations.     

利用对称多处理器提高NIDS的性能

网络入侵检测系统(NIDS)通过捕获和分析网络数据包判断是否存在攻击行为。由于网络带宽越来越高,NIDS的处理能力越来越难以跟上网络的速度。该文提出了一种利用对称多处理器(SMP)提高NIDS处理能力的方法,通过多个CPU并行的处理网络数据包改善系统的性能。经过对NIDS处理过程的分析,设计了一种有效的并行处理结构,保证在不同CPU上运行的线程能够高度并行的执行。此外,该文提出的线程同步方式既保证了程序功能的正确,又避免了对共享资源的互斥访问,进一步提高了线程的并行度。实验证明,在具有双CPU的SMP结构上实现的NIDS的性能比单CPU系统提高了80%。     

访存密集型应用在SMP机群系统中的性能分析

SMP机群系统因其良好的性价比、卓越的可扩展性与可用性，逐渐成为当前高性能计算机领域的主流结构．这种结点内共享存储、结点间消息传递的两级混合结构是目前并行计算研究的热点,在单个SMP结点中，总线和内存带宽是否满足CPU和I／O的需求对于访存密集型应用的性能影响很大。本文针对访存密集型应用的特点测试分析了在SMP机群中访存冲突对系统性能的影响，结果表明我们的SMP结点存在性能瓶颈，这种量化分析对于设计大规模的基于SMP的机群系统有很好的指导意义．     

A methodology for detailed performance modeling of reduction computations on SMP machines

In this paper, we revisit the problem of performance prediction on SMP machines, motivated by the need for selecting parallelization strategy for random write reductions. Such reductions frequently arise in data mining algorithms.

In our previous work, we have developed a number of techniques for parallelizing this class of reductions. Our previous work has shown that each of the three techniques, full replication, optimized full locking, and cache-sensitive, can outperform others depending upon problem, dataset, and machine parameters. Therefore, an important question is, “Can we predict the performance of these techniques for a given problem, dataset, and machine?”.

This paper addresses this question by developing an analytical performance model that captures a two-level cache, coherence cache misses, TLB misses, locking overheads, and contention for memory. Analytical model is combined with results from micro-benchmarking to predict performance on real machines. We have validated our model on two different SMP machines. Our results show that our model effectively captures the impact of memory hierarchy (two-level cache and TLB) as well as the factors that limit parallelism (contention for locks, memory contention, and coherence cache misses). The difference between predicted and measured performance is within 20% in almost all cases. Moreover, the model is quite accurate in predicting the relative performance of the three parallelization techniques.     

Isogeometric configuration design optimization of shape memory polymer curved beam structures for extremal negative Poisson’s ratio

Using a continuum-based design sensitivity analysis (DSA) method, a configuration design optimization method is developed for curved Kirchhoff beams with shape memory polymers (SMP), from which we systematically synthesize lattice structures achieving target negative Poisson’s ratio. A SMP phenomenological constitutive model for small strains is utilized. A Jaumann strain, based on the geometrically exact beam theory, is additively decomposed into elastic, stored, and thermal parts. Non-homogeneous displacement boundary conditions are employed to impose mechanical loadings. At each equilibrium configuration, an additional nonlinear analysis is performed to calculate the Poisson’s ratio and its design sensitivity of the SMP material. The design objectives are twofold: for purely elastic materials, lattice structures are designed to achieve prescribed Poisson’s ratios under finite compressive deformations. Also, SMP-based lattice structures are synthesized to possess target Poisson’s ratios in specified temperature ranges. The analytical design sensitivity of the Poisson’s ratio is verified through comparison with finite difference sensitivity. Several configuration design optimization examples are demonstrated.     

MAC and application level performance evaluation of beacon message dissemination in DSRC safety communication

In this paper, an analytic model is proposed for both MAC and application-level performance evaluation of periodic beacon message dissemination in the dedicated short range communications (DSRC) system on highways. Each vehicle can periodically generate beacon messages, which contain the information including position, velocity, direction, etc.. Out-dated message is replaced by the newly generated message. In order to develop a tractable analytic approximation, we first develop a semi-Markov process (SMP) model for the tagged vehicle to capture the periodic message generation, out-dated message replacement, channel contention and backoff behavior in IEEE 802.11 broadcast ad hoc networks. Further, an SMP model with an absorbing state is constructed to derive the message service time distribution. The fixed-point iteration method is utilized to obtain the converged solutions to resolve interactions between the SMPs of different vehicles. Both MAC-level and application-level performance metrics are derived. MAC-level analytic–numeric results are verified through extensive simulations. Application-level analytic–numerical results are evaluated subsequently to provide insights on network parameter settings. To ensure the quality of service (QoS) for a VANET application, application requirements in terms of application-level metrics are specified. Three typical safety-applications are evaluated in order to assess whether their application requirements can be satisfied or not.     

如何测量SMP机群可扩放性

可扩放性是并行计算的一个重要性能标准,但是传统的可扩放性准则并不适用于SMP机群.如何测量SMP机群的可扩放性?试图提出该问题的一个解决方案.首先找出并验证问题的根源--处理器集合不等价性.然后,采用处理器集合的观点来全面、正确地观察系统的行为,而并非像传统的做法那样仅仅使用处理器数来描述并行系统.通过引入性能参考因子的概念,扩展了传统的准则以适应SMP机群体系结构.实验结果显示,扩展后的度量准则适用于SMP机群,且具有较高的准确性.     

A probabilistic task scheduling method for grid environments

This paper presents a probabilistic task scheduling method to minimize the overall mean response time of the tasks submitted to the grid computing environments. Minimum mean response time of a given task can be obtained by finding a subset of appropriate computational resources to service the task. To achieve this, a discrete time Markov chain (DTMC) representing the task scheduling process within the grid environment is constructed. The connection probabilities between the nodes representing the grid managers and resources can be considered as transition probabilities of the obtained DTMC. Knowing the mean response times of the managers and resources, and finding fundamental matrix of the DTMC, the mean response time related to each of the absorbing DTMCs existing inside the overall DTMC can be computed. Minimizing the obtained mean response times and taking into account the probability constraints in each of the absorbing DTMCs, a nonlinear programming (NLP) problem is defined. Solving the NLP problem, the connection probabilities between the managers and resources are obtained. Finally, using the connection probabilities, the best scheduling path within the environment and the minimum mean response time of a particular task can be achieved. In a case in which there is only one optimal scheduling choice within the environment, the proposed method can deterministically find such scheduling by assigning zero or one to the connection probabilities. Results obtained from evaluating the proposed method on the hypothesis and real grid environments show the preference of the proposed method compared to the other methods in minimizing both the overall mean response time of the tasks and total makespan of the environment.     

Current issues in high performance computing I/O architectures and systems

The abundance of parallel and distributed computing platforms, such as MPP, SMP, and the Beowulf clusters, to name just a few, has added many more possibilities and challenges to high performance computing (HPC), parallel I/O, mass data storage, scalable architectures, and large-scale simulations, which traditionally belong to the realm of custom-tailored parallel systems. The intent of this special issue is to discuss problems and solutions, to identify new issues, and to help shape future research directions in these areas. From these perspectives, this special issue addresses the problems encountered at the hardware, architectural, and application levels, while providing conceptual as well as empirical treatments to the current issues in high performance computing, and the I/O architectures and systems utilized therein.