Fine-grained updates in database management systems for flash memory

The growing storage capacity of flash memory (up to 640 GB) and the proliferation of small mobile devices such as PDAs and mobile phones makes it attractive to build database management systems (DBMSs) on top of flash memory. However, most existing DBMSs are designed to run on hard disk drives. The unique characteristics of flash memory make the direct application of these existing DBMSs to flash memory very energy inefficient and slow. The relatively few DBMSs that are designed for flash suffer from two major short-comings. First, they do not take full advantage of the fact that updates to tuples usually only involve a small percentage of the attributes. A tuple refers to a row of a table in a database. Second, they do not cater for the asymmetry of write versus read costs of flash memory when designing the buffer replacement algorithm. In this paper, we have developed algorithms that address both of these short-comings. We overcome the first short-coming by partitioning tables into columns and then group the columns based on which columns are read or updated together. To this end, we developed an algorithm that uses a cost-based approach, which produces optimal column groupings for a given workload. We also propose a heuristic solution to the partitioning problem. The second short-coming is overcome by the design of the buffer replacement algorithm that automatically determines which page to evict from buffer based on a cost model that minimizes the expected read and write energy usage. Experiments using the TPC-C benchmark [S.T. Leutenegger, D. Dias, A modeling study of the TPC-C benchmark, in: Proceedings of ACM SIGMOD, 1993, pp. 22-31] show that our approach produces up to 40-fold in energy usage savings compared to the state-of-the-art in-page logging approach.     

PORCE: An efficient power off recovery scheme for flash memory

Flash memory is now replacing hard disk in many embedded applications including cellular phones, digital cameras, car navigation systems, and so on. However, because flash memory has its own characteristics such as “erase-before-write” and wear-leveling, a software layer called FTL (flash translation layer) should be provided. However, most FTL algorithms did not include the power off recovery module though it is very important in portable devices. In this paper, we suggest an efficient power off recovery scheme for flash memory called PORCE (Power Off Recovery sChEme for flash memory). PORCE is tightly coupled to FTL operations and minimizes performance degradation during normal operations by storing recovery information as small as possible. Additionally, PORCE provides cost-based reclamation protocols which include the wear-leveling module. Our empirical study shows that PORCE is an efficient recovery protocol.     

A B-Tree index extension to enhance response time and the life cycle of flash memory

Flash memory has critical drawbacks such as long latency of its write operation and a short life cycle. In order to overcome these limitations, the number of write operations to flash memory devices needs to be minimized. The B-Tree index structure, which is a popular hard disk based index structure, requires an excessive number of write operations when updating it to flash memory. To address this, it was proposed that another layer that emulates a B-Tree be placed between the flash memory and B-Tree indexes. This approach succeeded in reducing the write operation count, but it greatly increased search time and main memory usage. This paper proposes a B-Tree index extension that reduces both the write count and search time with limited main memory usage. First, we designed a buffer that accumulates update requests per leaf node and then simultaneously processes the update requests of the leaf node carrying the largest number of requests. Second, a type of header information was written on each leaf node. Finally, we made the index automatically control each leaf node size. Through experiments, the proposed index structure resulted in a significantly lower write count and a greatly decreased search time with less main memory usage, than placing a layer that emulates a B-Tree.     

FeGC: An efficient garbage collection scheme for flash memory based storage systems

NAND flash memory is a promising storage media that provides low-power consumption, high density, high performance, and shock resistance. Due to these versatile features, NAND flash memory is anticipated to be used as storage in enterprise-scale systems as well as small embedded devices. However, unlike traditional hard disks, flash memory should perform garbage collection that consists of a series of erase operations. The erase operation is time-consuming and it usually degrades the performance of storage systems seriously. Moreover, the number of erase operations allowed to each flash memory block is limited. This paper presents a new garbage collection scheme for flash memory based storage systems that focuses on reducing garbage collection overhead, and improving the endurance of flash memory. The scheme also reduces the energy consumption of storage systems significantly. Trace-driven simulations show that the proposed scheme performs better than various existing garbage collection schemes in terms of the garbage collection time, the number of erase operations, the energy consumption, and the endurance of flash memory.     

A hybrid flash translation layer design for SLC-MLC flash memory based multibank solid state disk

This paper presents the design of a NAND flash based solid state disk (SSD), which can support various storage access patterns commonly observed in a PC environment. It is based on a hybrid model of high-performance SLC (single-level cell) NAND and low cost MLC (multi-level cell) NAND flash memories. Typically, SLC NAND has a higher transfer rate and greater cell endurance than MLC NAND flash memory. MLC NAND, on the other hand, benefits from lower price and higher capacity. In order to achieve higher performance than traditional SSDs, an interleaving technique that places NAND flash chips in parallel is essential. However, using the traditional FTL (flash translation layer) on an SSD with only MLC NAND chips is inefficient because the size of a logical block becomes large as the mapping address unit grows. In this paper, we proposed a HFTL (hybrid flash translation layer) which makes use of chained-blocks, combining SLC NAND and MLC NAND flash memories in parallel. Experimental results show that for most of the traces studied, the HFTL in an SSD configuration composed of 80% MLC NAND and 20% SLC NAND memories can improve performance compared to other solid state disk configurations, composed of either SLC NAND or MLC NAND flash memory alone.     

Using data clustering to improve cleaning performance for flash memory

Flash memory offers attractive features for storage of data, such as non‐volatility, shock resistance, fast access speed, and low power consumption. However, it requires erasing before it can be overwritten. The erase operations are slow and consume comparatively a great deal of power. Furthermore, flash memory can only be erased a limited number of times. To overcome hardware limitations, we use the non‐in‐place update mechanism that requires a cleaner to reclaim space occupied by obsolete data. To improve cleaning performance and prolong flash memory lifetime, we propose a new data reorganization method. By this method, data in flash memory are dynamically classified and clustered together according to their accessing frequencies. Experimental results show that this clustering technique significantly improved the cleaning performance for a variety of cleaning algorithms. The number of erase operations performed is greatly reduced and flash memory lifetime is prolonged. Even wearing is ensured as well. Copyright © 1999 John Wiley & Sons, Ltd.     

Novel vertical channel double gate structures for high density and low power flash memory applications

The flash memory technology meets physical and technical obstacles in further scaling. New structures and new materials are implemented as possible solutions. This paper focuses on two kinds of new flash cells for high density and low power memory applications based on the vertical channel double gate structure. The proposed VD-NROM with dual-nitride-trapping-layer and vertical structure can achieve four-bit-per-cell storage capability. And the proposed VSAS-FG cell benefits the high programming efficiency, low power and high density capability, which can be realized without any additional mask and can achieve the self-alignment of the split-gate channel and the floating-gate. The two novel flash cell structures can be considered as potential candidates for different flash memory applications.     

一种高效的星载高速固态存储器坏块管理算法

随着卫星技术的发展和功能的多样化,星载固态存储器需要存储的数据量越来越大,存储速率越来越高,在轨寿命越来越长。基于NAND Flash的星载固态存储器的并行存储方案得到广泛应用。但是由于NAND Flash存在初始坏块,且Flash芯片中坏块分布离散性较大。当固态存储器存储速率较高,并行存储的Flash芯片数增多,坏块经叠加映射后,使固态存储器有效容量损失较大。针对高速固态存储器的坏块问题,提出了一种高效的坏块管理算法,通过对坏块进行地址映射和替换,使固态存储器初始有效容量与装机容量的比值在高速并行存储的情况下仍能保持在97%左右,提高了Flash芯片存储容量的利用率,延长了大容量星载高速固态存储器的使用寿命。     

Determining optimum flash patterns for emergency service vehicles: An experimental investigation using high definition film

An investigation of how emergency vehicle lighting (EVL) can be improved is reported with reference to an analysis of police vehicle road traffic accidents (Study 1). In Study 2, 37 regular drivers were shown film clips of a marked police vehicle, in which flash rate (1 Hz, 4 Hz) and pattern (single, triple pulse) were varied on the blue Light Emitting Diode (LED) roofbar. Results indicate a 4 Hz flash rate conveys greater urgency than a 1 Hz rate, while a 1 Hz, single flash combination was ranked the least urgent of all combinations. Participants claimed they would leave significantly more space before pulling out in front of an approaching police car (gap acceptance) in the 4 Hz single pulse condition in comparison to other EVL combinations. The preliminary implications for which flash characteristics could prove most optimal for emergency service use are discussed with regard to effects on driver perception and expected driving behaviour.     

An object‐oriented interface for the dynamic memory management of sparse discrete mathematical operators in numerical scientific applications

This paper describes an object‐oriented interface for the memory management of sparse discrete mathematical operators in numerical scientific applications. The basic data structure we propose is intended to implement and cope with mathematical vectors in sparse format. This structure allows an effective implementation of more complex data structures, such as matrix and matrix‐like objects, to represent the discrete version of differential operators in numerical application codes. A research example concerning adaptive wavelet algorithms illustrates the possible applications.Copyright © 2002 John Wiley & Sons, Ltd.     

An improved long short-term memory networks with Takagi-Sugeno fuzzy for traffic speed prediction considering abnormal traffic situation

Traffic speed prediction is an emerging paradigm for achieving a better transportation system in smart cities and improving the heavy traffic management in the intelligent transportation system (ITS). The accurate traffic speed prediction is affected by many contextual factors such as abnormal traffic conditions, traffic incidents, lane closures due to construction or events, and traffic congestion. To overcome these problems, we propose a new method named fuzzy optimized long short-term memory (FOLSTM) neural network for long-term traffic speed prediction. FOLSTM technique is a hybrid method composed of computational intelligence (CI), machine learning (ML), and metaheuristic techniques, capable of predicting the speed for macroscopic traffic key parameters. First, the proposed hybrid unsupervised learning method, agglomerated hierarchical K-means (AHK) clustering, divides the input samples into a group of clusters. Second, based on parameters the Gaussian bell-shaped fuzzy membership function calculates the degree of membership (high, low, and medium) for each cluster using Takagi-Sugeno fuzzy rules. Finally, the whale optimization algorithm (WOA) is used in LSTM to optimize the parameters obtained by fuzzy rules and calculate the optimal weight value. FOLSTM evaluates the accurate traffic speed from the abnormal traffic data to overcome the nonlinear characteristics. Experimental results demonstrated that our proposed method outperforms the state-of-the-art approaches in terms of metrics such as mean square error (MSE), root mean square error (RMSE), mean absolute error (MAE), and mean absolute percentage error (MAPE).