Exploiting flash memory characteristics to improve performance of RAIS storage systems

Redundant array of independent SSDs (RAIS) is generally based on the traditional RAID design and implementation. The random small write problem is a serious challenge of RAIS. Random small writes in parity-based RAIS systems generate significantly more pre-reads and writes which can degrade RAIS performance and shorten SSD lifetime. In order to overcome the well-known write-penalty problem in the parity-based RAID5 storage systems, several logging techniques such as Parity Logging and Data Logging have been put forward. However, these techniques are originally based on mechanical characteristics of the HDDs, which ignore the properties of the flash memory. In this article, we firstly propose RAISL, a flash-aware logging method that improves the small write performance of RAIS storage systems. RAISL writes new data instead of new data and pre-read data to the log SSD by making full use of the invalid pages on the SSD of RAIS. RAISL does not need to perform the pre-read operations so that the original characteristics of workloads are kept. Secondly, we propose AGCRL on the basis of RAISL to further boost performance. AGCRL combines RAISL with access characteristic to guide read and write cost regulation to improve the performance of RAIS storage systems. Our experiments demonstrate that the RAISL significantly improves write performance and AGCRL improves both of write performance and read performance. AGCRL on average outperforms RAIS5 and RAISL by 39.15% and 16.59% respectively.     

A high-performance and endurable SSD cache for parity-based RAID

Solid-state drives (SSDs) have been widely used as caching tier for disk-based RAID systems to speed up dataintensive applications. However, traditional cache schemes fail to effectively boost the parity-based RAID storage systems (e.g., RAID-5/6), which have poor random write performance due to the small-write problem. What’s worse, intensive cache writes can wear out the SSD quickly, which causes performance degradation and cost increment. In this article, we present the design and implementation of KDD, an efficient SSD-based caching system which Keeps Data and Deltas in SSD. When write requests hit in the cache, KDD dispatches the data to the RAID storage without updating the parity blocks to mitigate the small write penalty, and compactly stores the compressed deltas in SSD to reduce the cache write traffic while guaranteeing reliability in case of disk failures. In addition, KDD organizes the metadata partition on SSD as a circular log to make the cache persistent with low overhead.We evaluate the performance of KDD via both simulations and prototype implementations. Experimental results show that KDD effectively reduces the small write penalty while extending the lifetime of the SSD-based cache by up to 6.85 times.     

Software transactional memories: an approach for multicore programming

The recent advance of multicore architectures and the deployment of multiprocessors as the mainstream computing platforms have given rise to a new concurrent programming impetus. Software transactional memories (STM) are one of the most promising approaches to take up this challenge. The aim of a STM system is to discharge the application programmer from the management of synchronization when he/she has to write multiprocess programs. His/her task is to decompose his/her program into a set of sequential tasks that access shared objects, and to decompose each task in atomic units of computation. The management of the required synchronization is ensured by the associated STM system. This paper presents two existing STM systems, and a new one based on time-window mechanism. The paper, which focuses mainly on STM principles, has an introductory and survey flavor.     

半Markov过程基于性能势的灵敏度分析和性能优化

基于性能势的方法 ,研究了一类半Markov过程 (SMP)的性能灵敏度分析和平均费用下的性能优化问题 .将SMP转化为与之等价的离散时间Markov链 (DTMC) ,利用DTMC的性能势 ,对SMP进行灵敏度分析和性能优化 ,得到了SMP基于DTMC性能势的灵敏度分析公式和最优性方程 .最后给出了一个数值例子以表明该方法的应用 .     

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.     

Instant restore after a media failure (extended version)

Media failures usually leave database systems unavailable for several hours until recovery is complete, especially in applications with large devices and high transaction volume. Previous work introduced a technique called single-pass restore, which increases restore bandwidth and thus substantially decreases time to repair. Instant restore goes further as it permits read/write access to any data on a device undergoing restore – even data not yet restored – by restoring individual data segments on demand. Thus, the restore process is guided primarily by the needs of applications, and the observed mean time to repair is effectively reduced from several hours to a few seconds.This paper presents an implementation and evaluation of instant restore. The technique is incrementally implemented on a system starting with the traditional ARIES design for logging and recovery. Experiments show that the transaction latency perceived after a media failure can be cut down to less than a second. The net effect is that a few “nines” of availability are added to the system using simple and low-overhead software techniques.     

Pathways for optimization-based drug delivery

An overview of our research results on the implementation of model predictive control (MPC) on-chip is presented, with central focus the development of small-size, energy efficient controllers suitable for drug delivery systems and devices. Profiling simulations coupled with codesign techniques are used in order to reveal algorithmic bottlenecks and to effectively customize implementation designs. Hardware in-the-loop simulations using a general purpose processor and a field programmable gate array, and emulations of an application specific processor are provided. The performance measurements and estimates illustrate that MPC is suitable for on-chip real-time optimal control of complex systems with fast dynamics.     

一种基于算法骨架的函数式程序变换技术

如何提高函数式程序设计语言在传统冯·诺依曼机器上的执行速度.及效率,一直是该领域中研究的主要论题,对此,并行图归约技术、并行闭包归约、并行编译、并行程序转换等等技术相继成为改善这种状况的措施。     

CEFT: A cost-effective,fault-tolerant parallel virtual file system

The vulnerability of computer nodes due to component failures is a critical issue for cluster-based file systems. This paper studies the development and deployment of mirroring in cluster-based parallel virtual file systems to provide fault tolerance and analyzes the tradeoffs between the performance and the reliability in the mirroring scheme. It presents the design and implementation of CEFT, a scalable RAID-10 style file system based on PVFS, and proposes four novel mirroring protocols depending on whether the mirroring operations are server-driven or client-driven, whether they are asynchronous or synchronous. The comparisons of their write performances, measured in a real cluster, and their reliability and availability, obtained through analytical modeling, show that these protocols strike different tradeoffs between the reliability and performance. Protocols with higher peak write performance are less reliable than those with lower peak write performance, and vice versa. A hybrid protocol is proposed to optimize this tradeoff.     

Composing, analyzing and validating software models to assess the performability of competing design candidates

In a perfect world, verification and validation of a software design specification would be possible before any code was generated. Indeed, in a perfect world we would know that the implementation was correct because we could trust the class libraries, the development tools, verification tools and simulations, etc. These features would provide the confidence needed to know that all aspects (complexity, logical and timing correctness) of the design were fully satisfied (i.e., everything was right). Right in the sense that we built it right (it is correct with respect to its specification) and it solves the right problem. Unfortunately, it is not a perfect world, and therefore we must strive to continue to refine, develop and validate useful methods and tools for the creation of safe and correct software. This paper considers the analysis of systems expressed using formal notations. We introduce our framework, the modeling cycle, and motivate the need for tool supported rigorous methods. Our framework is about using systematic formal techniques for the creation and composition of software models that can further enable reasoning about high‐assurance systems. We describe several formal modeling techniques within this context (i.e., reliability and availability models, performance and functional models, performability models, etc.). This discussion includes a more precise discourse on stochastic methods (i.e., DTMC and CTMC) and their formulation. In addition, we briefly review the underlying theories and assumptions that are used to solve these models for the measure of interest (i.e., simulation, numerical and analytical techniques). Finally, we present a simple example that employs generalized stochastic Petri nets and illustrates the usefulness of such analysis methods. This revised version was published online in June 2006 with corrections to the Cover Date.     

Implementing an extended functional data model using PS-algol

A number of data models have been proposed in the literature to improve the usability of database systems. Most of these proposals have not been implemented. It is felt that a working implementation is a necessary prerequisite for a serious study of these proposals. So far, implementing data models has been a daunting task, requiring a large team. We report here on a simple implementation technique using the persistent algorithmic language. PS-algol, which promises to make the task of implementing data models a manageable one. The feasibility of the approach is demonstrated by implementing an entity-based functional data model (extended function data model) using PS-algol.     

HTAP数据库系统数据共享模型和优化策略

混合事务与分析处理数据库系统(HTAP)因其在一套系统上可以同时处理混合负载而逐渐获得大众认可. 为了不影响在线事务处理(OLTP)业务的写入性能, HTAP数据库系统往往会通过维护数据多版本或额外副本的方式来支持在线分析处理(OLAP)任务, 从而引入了TP/AP端版本的数据一致性问题. 同时, HTAP数据库系统面临资源隔离下实现高效数据共享的核心挑战, 且数据共享模型的设计综合权衡了业务对性能和数据新鲜度之间的要求. 因此, 为了系统地阐释现有HTAP数据库系统数据共享模型及优化策略, 首先根据TP生成版本与AP查询版本的差异, 通过一致性模型定义数据共享模型, 将HTAP数据共享的一致性模型分为3类, 分别为线性一致性, 顺序一致性与会话一致性. 然后, 梳理数据共享模型的全流程, 即从数据版本标识号分配, 数据版本同步, 数据版本追踪3个核心问题出发, 给出不同一致性模型的实现方法. 进一步, 以典型的HTAP数据库系统为例对具体实现进行深入的阐释. 最后, 针对数据共享过程中涉及的版本同步、追踪、回收等模块的优化策略进行归纳和分析, 并展望数据共享模型的优化方向, 指出数据同步范围自适应, 数据同步周期自调优和顺序一致性的新鲜度阈值约束控制是提高HTAP数据库系统性能和新鲜度的可能手段.     

基于STM32和USB的多通道数据采集系统设计与实现

意法半导体32位系列微控制器芯片作为高性能、低成本、低功耗的微控制器,在工业生产和自动化控制领域的应用十分广泛。但是随着技术的发展,其通用串行总线的传输速度已经相对较慢。为了使STM32的USB传输速率和性能有更进一步的提升,设计了一种由STM32控制USB通信接口的多通道数据采集系统。首先,该系统采用以STM32的增强型STM32F103为核心的控制电路,实现了10路通道的模拟/数字信号(A/D)数据的采集和转换。然后,利用STM32系统资源对EZ系列通用串行总线(EZ-USB)CY7C68013A的内部从属先进先出(FIFO)缓存器进行读写控制及数据传输处理。最后,数据的处理和显示通过由虚拟仪器(LabVIEW)设计的上位机程序实现。系统测试表明,STM32和EZ-USB组成的系统可以将STM32原有的USB传输速度提升两倍以上,并且采集的数据能在虚拟仪器上位机上实时显示。它可以使STM32更加快速、稳定地采集和处理数据,是一个适用性很强的数据采集系统。     

基于并发策略的分布式文件系统性能优化方案

分布式文件系统是构建分布式存储系统的核心底层子系统,它的性能影响着整个分布式存储系统的性能。针对Hadoop分布式文件系统性能的不足,提出基于并发策略的性能优化方案,改进其写操作性能。实验表明该方案能有效的提高写的性能,提高系统的执行效率。     

Weak atomicity for the x86 memory consistency model

We consider the interaction of weakly atomic Software Transactional Memory (STM) providing single global lock atomicity with the x86 memory consistency model. We show that a practical design for such an STM requires that some program behaviour be disallowed, due to the strictness of the x86 memory consistency model in comparison to the language level memory models hitherto considered in weakly atomic STM designs. We present the design and construction of such an STM that disallows races between a transactional read and a non-transactional write. We also report on a practical application of this STM to elide legacy locks in x86 binaries. This allows software transactional memory to be applied without requiring software to be a priori written with awareness of transactional memory and without any restriction on source language or compiler. As an example, we show how a mainstream multiplayer game can use transactional memory with zero changes and 11% overhead over language level transactional memory, which requires over 700 annotations and severely restricts software development.     

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

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

A high-speed integrated services ATM/STM switch

A new, high-speed switch architecture which uses Asynchronous Transfer Mode (ATM) and Synchronous Transfer Moder (STM) to support integrated voice-data-video, multicasting, and virtual networking services is described. The switch employs autonomous processing units with local memory to store switching information and is built around a modified Banyan network with bit-parallel lines linking its node processors. The system is synchronous and time is slotted with slots organized into frames. Fixed-rate video and other real-time periodic traffic are handled via STM switching, while voice, data, datagrams, and other bursty traffic are ATM switched. Multicasting is realized by allocating dedicated STM bandwidth to real-time periodic sources and virtual ATM bandwidth to bursty sources. Virtual networking is achieved by putting an STM subnetwork into place over which authorized users communicate via ATM and/or STM. Analytic models to determine the switch's performance characteristics are developed and illustrated via examples. The results show that the switch has excellent delay vs. throughput performance for ATM traffic in the presence of STM traffic, and very low blocking-and-loss probability for STM circuit set-up requests in the presence of other traffic.     

Formal Reasoning About Finite-State Discrete-Time Markov Chains in HOL

Markov chains are extensively used in modeling different aspects of engineering and scientific systems, such as performance of algorithms and reliability of systems. Different techniques have been developed for analyzing Markovian models, for example, Markov Chain Monte Carlo based simulation, Markov Analyzer, and more recently probabilistic model-checking. However, these techniques either do not guarantee accurate analysis or are not scalable. Higher-order-logic theorem proving is a formal method that has the ability to overcome the above mentioned limitations. However, it is not mature enough to handle all sorts of Markovian models. In this paper, we propose a formalization of Discrete-Time Markov Chain (DTMC) that facilitates formal reasoning about time-homogeneous finite-state discrete-time Markov chain. In particular, we provide a formal verification on some of its important properties, such as joint probabilities, Chapman-Kolmogorov equation, reversibility property, using higher-order logic. To demonstrate the usefulness of our work, we analyze two applications: a simplified binary communication channel and the Automatic Mail Quality Measurement protocol.